[OS] 페이징(Paging) 기법

페이징(Paging) 기법

• 메모리 가상화에서 가상 주소와 물리 주소를 맵핑시킬 때 페이지 프레임을 단위로 하는 방식
• 고정 분할 및 가변 분할 기법은 각각 내부단편화, 외부단편화의 문제점 존재
• 페이징 기법은 마지막 페이지에서의 내부단편화 1회만 발생하므로 효율적

 

페이지 테이블(Page Table)

페이지 테이블에는 가상 주소, 물리 주소 뿐만 아니라 P, M 등의 Control bit들도 포함된다. P(present) 비트는 해당 페이지가 메모리에 위치하는가에 대한 비트이다. P 비트가 1인 경우 해당 페이지가 메모리에 올라와 있다는 뜻이고 0인 경우 디스크의 swap 영역에 있다는 것을 의미하며 page fault가 일어난다. M(modifiy) 비트는 해당 페이지가 메모리에 적재된 후 수정된 적이 있는지에 대한 여부를 의미한다. 페이지 테이블은 OS가 각각의 프로세스에게 개별적으로 부여하게 되고 각각의 PCB들은 멤버 변수로 해당 페이지 테이블을 가리키게 된다. 대부분의 가상 메모리 기법에서는 페이지 테이블을 실제 메모리가 아닌 가상 메모리에 저장한다. 

 

가상 주소(논리 주소)

페이지 테이블을 통해 사용되는 가상 주소와 물리 주소는 모두 page number와 offset 구조를 가진다. page number를 통해 페이지 테이블의 몇 번째 행에 접근할지를 파악한 후 접근하여 frame number를 얻는다. frame number는 물리 메모리에서의 시작 주소를 의미하므로 여기에 offset을 더해주어 실제 물리 주소로 찾아갈 수 있다.

또한 가상 주소의 비트 사용량을 통해 역으로 OS의 각종 변수 값을 유추할 수 있다. 가상 주소에서 offset이 차지하는 bit수가 o라면, 해당 OS의 page frame size는 2^o 가 된다. 한편, 가상 주소에서 page number가 사용하는 비트 수가 p라면, 해당 OS의 page table의 최대 크기(가질 수 있는 최대 항목 수)는 2^p가 된다.

 

과도한 크기의 page table 문제 해결

1. 계층(n단계) 구조의 페이지 테이블 사용

페이지 디렉토리가 있어 각각의 항목이 페이지 테이블을 가리키도록 하는 방법이다.

 

2. 역페이지테이블 (inverted page table) 사용

page number를 그대로 사용하지 않고 hash function을 통해 얻은 hash value로 사용하는 방법이다.

hash table의 항목 수는 물리 메모리의 페이지 프레임의 수와 동일하고 collision을 해결하기 위해 linked list로 다음 엔트리를 연결하게 된다. hash table에서의 인덱스는 실제 물리 메모리에서의 인덱스와 같다.

 

3. TLB 사용

TLB는 translation look-aside buffer의 약자로 페이지 테이블 항목들을 저장하기 위한 특수 고속 캐시이다. 가장 최근에 참조된 페이지 테이블 항목들을 저장하고 있으며 각 항목들은 똑같이 control bits와 frame number를 가진다. 하지만 TLB에서는 page number를 인덱스로 사용해 각 항목에 접근할 수 없기 때문에 페이지 테이블의 항목들이 가진 정보에 추가로 page number를 저장해야한다. 이를 연관 사상(Associative Mapping)이라고 한다.

 

가상주소가 주어지면 우선 TLB에 해당 page number가 있는지 확인한다. page number가 TLB에 있을 경우 TLB Hit으로, 바로 frame number를 얻어 물리 주소를 구해낸다. 만약 TLB에 page number가 없을 경우 TLB Miss로, 기존과 동일하게 펭페이지 테이블에서 page number를 통해 frame number를 구해낸다. 이후 해당 page number에 관련된 정보들을 TLB에 추가한다. 만약 TLB에 여유 공간이 없을 경우 가장 오래된 항목을 제거해 공간을 확보한다. 한편, 만약 page table에서 P bit가 0이라면 Page Fault로, secondary memory(swap)에 접근해 해당 page frame을 memory로 load한다. 이후 다시 page table에서 물리 주소를 찾아나선다.

---