[운영체제] Paging 과 Multi-Level Paging

/* Paging */

페이징 (Paging)은 base and bound, segmentation과는 달리 address space (virtual memory)를 고정된 크기로 나눈다.
한 단위를 page라고 한다.

 

 

 

 

 

 

 

 

 

 

첫번 째 그림처럼 총 64바이트 4개의 페이지가 있다고 가정하자. (1 페이지당 16바이트). 

64바이트를 addressing하려면 6비트가 필요하다.

페이지가 4개로 나뉘기 때문에 상위 2비트는 vpn (virtual page number)를 가리키고 나머지는 offset이다.

physical address로 addressing 될때 offset은 그대로 가져오고 VPN -> PFN의 과정에서만 변환이 일어난다.

 

paging을 사용하면 메모리를 고정된 크기로 나누어 할당하고 관리하기 때문에 메모리 관리가 편해진다. 그리고 경계가 붙어있으므로 external fragmentation이 존재하지 않는다. (internal fragmentation은 존재한다.)

 

/* Page Table */

위의 address translation은 page table에서 이루어진다. 

page table은 프로세스마다 존재하고, 오늘날 page의 개수는 많아 mmu 같은 하드웨어에 배치하지 않고 물리 메모리에 배치한다.

 

page table에서 virtual page number가 key가 되고, physical frame number가 value가 된다고 했을 때,

key값에 해당되는 부분을 순서대로 정렬해서, key값이 연속하고 정렬되어있게 되면 이것을 index로 대치가 가능하다.

즉 key는 사라지고(위치가 대신함) value값만 남아서 하나의 배열 table형태가 되는 것이다. (key값은 index가 대신함.)

 

page table은 여러 page table entry로 구성되어 있다.

 

이러한 기법은 address translation이 필요할 때마다 물리적 메모리에 접근을 해야해 느리다는 단점이 있다.

이런 단점은 TLB로 개선될 수 있다.

/* TLB */

TLB (translation lookaside buffer)는 mmu안에 존재하고 캐시 메모리를 담당한다.

캐시메모리를 사용하여 address translation 정보를 저장했다가 다시 사용할 수 있다.

 

VPN을 가지고 TLB에서 매칭되는 Entry가 있는지 찾는다. 캐시메모리이므로 한번에 비교 가능.

찾으면 TLB hit, 못찾으면  TLB miss.

 

1. TLB hit:

TLB entry의 protection bit를 살펴보고 access가 가능한지 확인한다.

잘못된 접근일 경우 protection fault exception이 발생해서 trap으로 진입하고,

올바른 접근이면 page table entry의 PFN와 offset을 조립하여 physical address를 얻어낸다.

 

2. TLB miss:

첫번째 방법: PTBR(page table base register)을 사용하고, VPN을 index로 사용하여 page table에서 PTE(page table entry)를 읽어온다. (하드웨어적 처리)

두번째 방법: TLB miss가 났을때 TLB_miss exception을 발생시키는 것이다. (trap 발생.)

 

TLB는 하나 존재하고 여러 프로세스가 이를 공유하기 때문에 TLB에는 같은 VPN이 존재할 수도 있다.

따라서 이 경우 TLB의 VPN 정보가 어떤 프로세스의 것인지 헷갈리지 않게 하기 위해 context switching시에 TLB는 다 지운다.

하지만 이렇게 하면 비용이 너무 크기 때문에 ASID를 이용하는 방법도 있다.

ASID를 각 TLB entry마다 따로 부여해서 해당 entry가 어떤 프로세스가 저장한 정보인지를 구별할 수 있게 한다.

/* Multi-Level Paging */

multi level paging은 page table을 물리 메모리에 넣을때에도 paging의 장점을 살려서 넣어보자는 발상에서 시작한다.

 

 

page table을 page크기로 자르고 각각의 page table 시작주소를 page directory에 둔다. (page table을 위한 page table 느낌)

그런데 위 그림의 page directory를 보면 세번째 entry는 유효하지 않은 것을 볼 수있다. 이말은 즉, 세번째 entry를 위한 페이지 테이블은 없어도 된다는 이야기이다. (할당할 필요가 없다)

즉, 이렇게 위의 그림에서 multi level paging을 이용하면, 크기가 일정한 3개의 페이지 테이블만 있으면 된다.

 

일반 paging에서 PTBR(page table base register)를 사용했던 것과 달리, multi level paging의 mmu에서는 PDBR(page directory base register)라는 것을 사용한다.

 

이때 page directory도 page 크기에 맞게 준비되고, PDBR은 page directory가 물리 메모리의 어떤 페이지에 들어가는지를 알려준다.