메모리 관리와 페이징 기법
목표
•
프로그래밍할 때 physical 메모리를 신경 쓰지 않도록 abstraction을 제공한다.
physical memory address와 분리된 logical memory address를 사용해서
프로세스마다 0번지부터 최대 번지까지의 메모리를 사용할 수 있다고 가정하고 프로그래밍한다.
•
메모리 자원을 오버헤드를 줄이면서 최적의 성능을 내도록 할당한다.
•
프로세스 간 메모리 isolation을 제공한다. 공유 메모리를 설정하지 않으면 별개의 메모리를 가지고 동작한다.
시스템 구분
•
Batch Programming: 메모리 관리가 필요 없고 실행되어야 하는 태스크를 실행시키고 실행이 끝나면 내려주는 작업만 한다. I/O가 발생하면 처리하는 동안 CPU Utilization이 떨어진다.
•
Multiprogramming: 여러 개의 프로세스가 동시에 메모리를 점유한다. 각각의 프로세스는 자기만의 메모리 공간이 필요하다. 프로세스들마다 격리된 메모리 공간을 할당해주는 로직이 필요하다. Partitioning, Paging, Segmentation 등이 있다.
•
메모리 관리에 있어서 필요한 사항들
Protection: 특정 프로세스가 다른 프로세스 메모리공간 침해하면서 의도치 않은 동작 방지.
Fast translation: 필요한 메모리를 빨리 찾을 수 있어야 함.
Fast Context Switching: 컨텍스트 스위칭 빨라야함.
메모리 관리 이슈
•
다수의 프로세스에 격리된 메모리를 할당하고 Protection, 데이터 쉐어링 등의 기능을 제공해야 한다.
•
Virtual Memory: 프로그램은 항상 모든 코드나 데이터가 메모리에 올라가 있을 필요는 없다. 읽히지 않는 메모리도 존재하고, 실행되지 않는 branch도 있다. 가상 메모리를 사용하면 이러한 특성을 통해 physical 메모리를 적게 사용하면서 프로그램을 실행할 수 있다. 각 프로세스의 메모리 공간을 격리시키고, 세컨더리 스토리지(디스크)의 일부를 메모리처럼 사용하면서 swap in, swap out을 통해 physical 메모리보다 큰 메모리 공간을 할당할 수 있는 기능을 제공한다. 보통 physical memory의 두 배 이상을 가상메모리로 설정한다.
가상 메모리에서는 메모리를 Physical Memory와 Logical Memory로 구분한다.
Physical Memory는 실제 하드웨어이고 Logical Memory는 Physical Memory를 직접 건드리지 않도록 추상화해놓은 것이다.
메모리 주소 바인딩
•
프로그램이 실행될 때 프로세스가 동작할 수 있는 코드, 데이터 섹션을 메모리에 로드시키는 시점에 따라 3가지로 구분된다.
1.
Compile Time: 컴파일되면 변수 이름은 사라지고 주소값으로 대체된다. 컴파일하고 어셈블리 코드 실행을 보면 변수 이름이 없는 이유이다. 메모리 주소로 매핑되어서 직접 메모리 주소를 사용한다. 컴파일 타임에 메모리 주소를 바인딩한다는 것은 바이너리 이미지를 만드는 시점에 결정한다는 것이다. 컴파일할 때 어디서부터 어디까지의 주소를 사용한다고 지정한다. 실제로 메모리에 올라갈 때 컴파일 타임에 지정된 주소로 할당된다. 실제로는 잘 사용되지 않는다. 펌웨어 레벨이나 임베디드 시스템에서는 사용된다. 다른 프로그램이 실행될 때 똑같은 메모리 주소를 가진다면 프로그램을 올리지 못한다.
2.
Load Time: 컴파일 타임의 문제를 해결하기 위해서 로드하는 시점에 피지컬 메모리에 만들어질 위치를 결정한다. 프로그램 크기를 지정하고 운영체제가 메모리를 보고 연속적으로 할당할 수 있는 공간을 찾아서 넣어준다. 그럼 시작 위치를 base address로 하고 프로세스 내에서의 위치에 base address를 더하면 정상적으로 동작한다. 메모리 참조값을 base가 어딘지에 따라서 로드 타임에 주소 연산해줘야 하고, 실행되지 않을 수도 있어도 모든 분기에 대해서 처리를 해줘야 한다. 따라서 로드 시간이 굉장히 길어질 수 있다.
3.
Execution Time: 동일하게 로드 타임에 적절한 위치에 할당받고 코드에 있는 주소값을 그대로 가져와서 수행 시에 base address와 계산해서 처리한다. 실행 시간이 늘어날 위험이 있지만 최적의 방법이다. 주소 연산 오버헤드를 줄이기 위해서 MMU라는 유닛을 만들었다. 특수한 목적의 하드웨어이다. 주소 연산에 특화되어 있으며 로지컬 주소를 피지컬 주소로 변경하는 역할을 한다. 저사양 컴퓨터는 MMU가 없다. MPU라는 프로텍션 기능만 가진 유닛이 존재한다. MMU는 CPU 대부분에 존재하고 로지컬 메모리를 MMU에 CPU가 전달하면 피지컬 메모리로 전환해준다. 피지컬 메모리는 프로그램 실행 시마다 달라질 수 있다. 하지만 변수의 주소값을 출력해보면 항상 같게 나오는 것을 확인할 수 있다. 따라서 로지컬 메모리를 통해 abstraction되어 있고 프로그래밍 시에 실제로 접근하는 주소는 로지컬 메모리인 것을 확인할 수 있다.
메모리 주소 할당
1.
Contiguous Allocation: 연 연속적으로 메모리를 할당하는 방법이다. 다른 프로세스의 메모리 영역을 침범하지 않는지 계산하고 메모리를 할당한다. 단점은 프로세스가 종료되고 메모리를 반납했을 때 빈 공간이 생기는데, 다른 프로세스를 빈 공간에 할당하면 프로세스 크기 차이에 따라서 남는 공간이 발생한다. 이 공간이 하나의 프로세스를 돌리기에 부족하다면 해당 공간은 사용할 수 없다. 프로세스가 생겼다 없어지는 과정에서 hole이 다수 발생하면 memory Utilization이 떨어진다. 이를 해결하기 위해서 hole들을 모아서 하나의 큰 블록으로 재배치하는 방법이 있다. 이를 compaction이라고 한다. 하지만 I/O가 많이 발생하고 프로세스들을 복사해서 재배치하는 과정의 오버헤드가 크기 때문에 잘 쓰이지 않는다. Hole의 사이즈를 최대한 줄이는 것이 중요하므로 새로 올라오는 프로세스를 어느 hole에다 할당할 것이냐가 중요하고, first fit, best fit, worst fit 방식이 존재한다. First fit은 메모리를 스캔하다가 첫 번째 발생하는 빈 공간에 메모리를 할당하는 방법이다. Best fit은 가장 크기가 비슷한 hole에다가 프로세스를 할당하는 방식으로 홀의 개수, 위치, 사이즈를 운영체제가 관리해야 하는 오버헤드가 존재한다. Worst fit은 가장 큰 홀에 먼저 프로세스를 할당하는 방식이다. 실제로는 first와 best fit의 성능이 비슷하게 나온다. 어떤 방식을 사용해도 hole이 발생하고 프로세스 사이에서 생기는 홀로 인해 메모리가 단편화되는 현상을 external fragmentation이라고 한다. Compaction으로 해결하는 방법이 있으나 I/O로 인한 오버헤드 문제가 발생한다.
1.
Paging: 페이지란 논리 메모리를 일정한 크기로 나눈 블록이다. 프로세스를 logical address 단에서 지정된 크기만큼으로 자른다. 페이지 크기와 똑같은 크기만큼 피지컬 메모리도 분할해서 슬롯을 만든다. 이것을 프레임이라고 한다. 운영체제가 정책에 따라서 페이지를 프레임에 할당하고 몇 번 페이지가 몇 번 프레임에 들어가 있는지 페이지 테이블을 관리한다. 하지만 페이징 기법을 사용해도 fragmentation이 발생하는데, 페이지 단위로 분할한 프로세스 내부에서 페이지 단위보다 작은 메모리를 차지하는 부분은 단편화가 발생한다. 이것을 internal fragmentation이라고 한다. 하지만 internal fragmentation은 external fragmentation보다 메모리 낭비가 훨씬 줄어드므로 실제로 페이징 기법이 사용된다.
Address Translation
1.
논리 주소: page number와 offset으로 이루어져 있다 (p, d). 페이지 번호는 페이지 테이블의 index와 동일하다. offset은 페이지 내에서 어느 위치로 접근해야 하는지의 값이다. 페이지 테이블이 몇 번 프레임에 페이지를 할당할지 결정한다.
2.
물리 주소: : frame number와 offset으로 구성되어 있다 (f, d).
3.
Page table: 프로세스마다 개별적으로 가지고 있으며 운영체제가 관리하여 페이지 번호와 프레임 번호를 매핑한다. 하나의 페이지당 하나의 엔트리를 차지한다. 각 엔트리 크기는 int(4바이트)이다. 페이지 번호는 인덱스로, 프레임 정보를 데이터로 관리한다. 페이지 테이블은 각각의 프로세스를 독립적으로 관리하기 위한 가상 주소 공간으로, 페이지 테이블이 메모리 전체의 0번지부터 max 번지까지의 페이지를 다 사용할 수 있다고 가정한다. 페이지 테이블은 메모리 상에 존재하며 위치를 알아내기 위해 PTBR(Page Table Base Register)와 PTLR(Page Table Length Register)를 사용한다.
4.
과정: CPU가 자신의 내부의 MMU에 논리 주소를 전달하면 p 부분은 페이지 테이블을 참조하여 프레임 번호로 변경하고, d 부분은 그대로 프레임 번호와 합쳐서 물리 주소로 변환한다.
•
32비트 주소 체계에서 20비트는 페이지 번호, 12비트는 오프셋으로 사용한다. 20비트를 사용하면 (2^{20}) = 1메가개(약 105만 개)의 페이지 번호를 가질 수 있다. 따라서 논리 메모리 공간을 1메가개만큼의 페이지로 나눌 수 있다. 이렇게 나눠진 페이지들을 페이지 테이블을 통해 관리한다. 32비트 주소 체계에서의 페이지 하나의 크기는 4KB이다. 20비트를 통해 페이지 번호를 지정하고 12비트를 통해 오프셋 정보를 표현한다. 1메가개의 페이지 * 4KB의 페이지 크기이므로 32비트 운영체제에서 메모리 크기는 최대 4GB가 된다.
•
운영체제에서는 free frame list를 관리하여 새로운 프로세스가 실행될 때 free frame에서 선택해서 할당한다. 비어있는 프레임보다 새로 실행되는 프로세스의 페이지가 더 많으면 오버플로우가 발생하므로 이미 메모리에 있는 프로세스를 디스크로 swap out 후에 swap in 해야 한다.
TLB
1.
TLB 개념: 페이지 테이블은 크기가 크다. 1메가개의 페이지 엔트리 * 한 칸당 4바이트 = 4MB가 된다. 여러 개의 프로세스가 동시에 존재하므로 페이지 테이블을 캐시에서 관리할 수는 없으므로 메모리에서 관리한다. 하지만 물리 메모리 주소를 알아내기 위해서 매번 메모리에 접근해야 한다면 매번 두 번씩 접근해야 하므로 비효율적이다. 따라서 TLB를 사용해서 해결한다.
•
TLB는 MMU 내부에 존재하는 버퍼 메모리이다. TLB는 associative memory로 병렬 탐색이 가능해서 아주 빠른 속도로 페이지 테이블을 탐색할 수 있다. CAM(content addressable memory)이라고도 부른다. TLB에 페이지 테이블을 캐싱해 두고 메모리 액세스가 필요할 때 TLB부터 참조해서 Cache hit이 발생하면(값이 캐시에 있으면) 메모리에 액세스하지 않고 한 번에 물리 메모리에 접근할 수 있다. Cache hit이 발생하지 않으면 메모리로 액세스해야 한다.
•
TLB는 하드웨어로 구현되어 있고 Cache hit이 98% 이상으로 성능이 굉장히 좋다. 이렇게 높은 확률을 가지는 이유는 Locality 때문이다.
2.
Locality: Spatial Locality와 Temporal Locality가 있다. 프로그램은 반복을 많이 사용하고 일반적으로 코드의 20%가 80% 이상의 작업을 차지한다. Temporal Locality는 반복에 의해서 가장 최근에 사용된 데이터가 빠른 미래에 사용될 가능성이 높다는 개념이다. Spatial Locality는 인근에 있는 메모리 영역에 대한 접근 가능성이 높다는 개념이다. 따라서 메모리를 가져올 때 주변의 데이터를 한 번에 많이 가져오면 메모리 접근 횟수를 줄일 수 있다.
3.
Context Switching 발생 시: 새로운 프로세스가 올라왔을 때 기존 프로세스의 페이지 테이블 정보는 쓸모가 없으므로 전부 invalid 상태로 변경한다. 처음 context switching이 발생했을 때는 Cache miss가 발생하고 운영체제가 메모리에 접근해서 Temporal, Spatial Locality를 고려해서 페이지 테이블을 가져와서 캐시를 업데이트한다.
4.
EAT (Effective Access Time): 메모리 액세스 시간 성능을 수식으로 나타낸다. 엡실론 = TLB 접근 시간, 메모리 액세스 = 1, Cache hit 확률 = 알파. 왼쪽은 TLB에서 hit이 났을 때의 시간, 오른쪽은 메모리 액세스를 해야 할 때의 시간이다.
메모리 Protection
1.
페이징 기법 Protection: 프로세스가 5개의 페이지로 이루어져 있는데 6번째 페이지에 접근하는 등 유효하지 않은 페이지에 접근하는 문제가 발생할 수 있다. 따라서 페이지 테이블에서 하나의 비트를 활용하여 유효한 페이지는 valid, 유효하지 않은 페이지는 invalid로 관리한다.
하지만 swap out으로 인해서 해당 페이지가 invalid인 상황일 수도 있다. 따라서 페이지 테이블에서 invalid인 경우는 2가지 상황이 존재한다. 유효하지 않은 메모리에 접근하는 경우 protection으로 exception 인터럽트를 발생시키는 경우, 디스크에서 swap in 시켜서 valid로 바꿔주는 경우이다.
2.
PTE (Page Table Entry) 구조:valid bit: 엔트리가 사용될 수 있는지 여부를 관리. Reference bit: 페이지가 엑세스 되었는지를 관리하는 비트. Modify bit: 페이지가 write으로 인해 변경되었는지 관리. Protection bit: 권한 관리 (read, write, execute 등). 나머지 20비트는 Frame Number이다.
페이지 테이블 구조
•
한 프로세스마다 페이지 테이블을 하나씩 가지고 있고 20비트 개 만큼의 엔트리에 페이지 크기가 4KB 이므로 메모리 전체를 사용한다고 가정한 것이다. 하지만 하나의 프로그램이 메모리 전체를 사용하는 경우는 거의 없다. valid로 체크되어 있는 엔트리에 대해서만 페이지를 할당하면 된다.
•
구현 방법으로 hierarchical, hashed, inverted page table이 있다. Hierarchical page table 방식만 실제로 사용된다.
1.
Hierarchical Page Table: 페이지 테이블의 depth를 나누고, 페이지 넘버를 표현하는 20비트를 10비트씩 쪼개서 앞부분을 첫번째 depth의 outer page table접근에 사용하고 뒷부분을 나눠진 page table에 접근하는데 사용한다. 최악의 경우 메모리를 전부 다 쓰고 모든 페이지가 valid인 경우 outer page table의 사이즈는 2의10승이므로 4*2의10승은 4KB, page table은 4kbyte의 페이지가 2의10개만큼으로 분리되어서 4MB의 크기를 가지므로 총 4.4MB의 크기를 가지게 된다. 싱글 레벨의 경우 4MB의 크기를 가지므로 더 크다. 하지만 전부다 valid로 사용하는 경우는 거의 없고 outer page table에서 invalid라면 페이지 테이블에 할당하지 않으면 된다. 만약 한개의 페이지만 valid인 경우라면 outer page table은 그대로 4kb를 유지하지만 page table은 한개의 페이지 테이블에서 한개의 페이지만 생성하면 되므로 4kb가 되어 총 크기가 8kb로 극단적으로 줄어든다.
2.
Hashed Page Tables: 페이지 번호를 해싱하여 저장하고, 해싱된 결과가 같은 값을 가지는 엔트리들을 linked list로 관리하는 방식이다.
3.
Inverted Page Table: 피지컬메모리의 입장에서 프레임마다 할당받은 페이지가 있고, 어떤 프레임에서 어떤 Pid 의 프로세스를 할당받았는지를 frame table 로 관리하는 방식이다.
physical address 를 logical address 로 역으로 연산하는 과정이 복잡하고 하드웨어 아키텍쳐에 맞지 않아서 사용하지 않는다
Shared Page
•
동일한 프로그램에서 여러 개의 프로세스를 생성하는 경우 코드 섹션이 동일하다. 운영체제에서 이 코드 섹션 페이지를 공유하도록 하여 중복을 줄여 메모리를 아끼는 것이 가능하다.
•
dynamic linking되는 공유 라이브러리의 경우에도 여러 프로세스들이 같은 물리적 주소를 공유하게 할 수 있다. 공유 라이브러리는 여러 프로세스에서 공통적으로 사용되므로 프로세스마다 로드하는 것이 아니라 한 번만 로드하고 각 프로세스의 페이지 테이블에서는 shared page를 가리키는 엔트리를 생성하여 물리적으로 같은 메모리 주소를 공유한다.
페이징의 장점
•
external fragmentation이 발생하지 않는다.
•
physical memory 할당이 쉽다. free frame list를 통해서 빈 프레임을 할당하고 할당된 프레임은 list에서 제거하면 된다.
•
fork()하는 경우 코드 섹션은 동일하므로 공유해서 사용함으로써 메모리를 아낄 수 있다.
•
공유 라이브러리 또한 라이브러리를 메모리에 한 번만 로드하고 프로세스들이 공유해서 사용할 수 있으므로 효율적이다.
페이징의 단점
•
internal fragmentation이 발생할 수 있다. 하지만 external fragmentation과 비교해 훨씬 작은 수준이므로 무시할 수 있다.
•
페이지 테이블의 사이즈가 커서 캐싱할 수 없다. TLB를 MMU 내부에 하드웨어로 구현해 캐싱할 수 있게 했고, Hierarchical paging을 통해서 사이즈를 줄임으로써 해결했다.
Segmentation
정의
•
프로그램을 여러 개의 세그먼트로 나누어 메모리에 로드하는 기법이다. Contiguous Allocation과 비슷한 방법으로 메모리 내의 빈 공간에 프로세스를 세그먼트 단위로 나누어 로드한다. segment table을 관리하여 세그먼트들을 관리한다. 세그먼트 테이블은 세그먼트 번호와 오프셋으로 논리적 주소를 나누어 관리한다. 세그먼트 테이블을 참조하여 base 주소를 찾고, 오프셋이 범위를 넘어가지 않는지 체크하고 통과하면 base 주소를 더해서 physical 주소를 읽는다. 마찬가지로 external fragmentation이 발생한다.
•
프로그램은 코드 세그먼트, 데이터 세그먼트, 스택 세그먼트 등으로 나뉜다. 만약 공유되는 페이지가 여러 개 있고 fork가 일어난 경우 몇 번 페이지가 공유하는 페이지인지 관리하기 어렵다. 하지만 Segmentation을 사용하면 sharing이 편리하고 protection도 쉽다(코드 세그먼트는 쓰기 불가 등). 단점은 external fragmentation이 발생한다.
Hybrid Approach
•
Page Segment: 프로세스를 세그먼트 단위로 나누고 나눠진 것을 페이징한다. 세그먼트 테이블과 페이지 테이블이 각각 생성된다. hierarchy가 늘어나지만 세그먼트가 페이지로 나눠져 있으므로 세그먼트 테이블이 줄어든다. 세그먼트를 위해 페이지 크기는 하나로 고정되지 않고 여러 개의 사이즈의 페이지가 존재해서 필요한 크기를 사용하기도 한다. 이렇게 하면 세그먼트 단위로 용도에 따라 나누고 그것을 페이징해서 external fragmentation이 발생하지 않고 internal fragmentation도 multiple page size를 사용해서 많이 줄일 수 있다. 실제로 이 방법이 사용된다.
•
Pentium System: Page Segment가 적용된 시스템이다. selector는 세그먼트 주소를 저장하고 descriptor table을 통해서 physical address를 받고 offset을 더해서 page가 된다. 실제로 offset은 page number이다. 하단부는 hierarchical paging으로 구현되어 있다. Directory는 outer page table에 해당한다. page는 inner page table 주소가 된다. Directory를 참조하고 페이지 테이블을 참조해서 base 주소를 가져다가 offset 값을 적용하면 physical address가 나온다. 의미 있는 단위인 세그먼트로 나누고, 페이지로 다시 나눠서 hierarchical paging으로 구현한다. 그냥 paging보다 locality가 더 좋아진다.
실제 아키텍처 사례
•
A-32: 인텔 32비트 CPU 아키텍처로, 서로 다른 크기의 페이지를 사용하는 기법을 적용한다. PAE(Page Address Extension) 기법을 써서 4GB보다 큰 메모리 공간을 사용한다.
•
x86-64: 48비트 주소 체계를 사용하며, 64비트를 다 쓸 필요가 없다. 현재 가장 큰 메모리가 1TB이기 때문에 그만큼의 physical address가 필요 없다.
•
ARM: Two Level로 페이징해서 사용한다. 임베디드에서 많이 사용된다. 페이지 사이즈를 자잘하게 쪼개서 사용한다. internal fragmentation을 줄일 수 있고 큰 영역은 큰 걸 할당하면 페이지 테이블 크기도 줄일 수 있다.
