[Operating System] Multi-Level Page Table

 

 

 

프로세스가 작으면 프로세스 안의 페이지도 적어 페이지당 하나씩 존재하는 Page Table Entry도 줄어든다.

프로세스가 크면 페이지의 크기도 커지고 Page Table Entry도 커진다.

 

 

 

 

32비트 아키텍처에서는 가상 주소 공간의 최대 크기가 4GB이다.

0~3GB까지는 code data stack이 들어간다. 전체가 4GB이고 한 조각은 4KB이니 페이지의 최대 개수는 1,000,000이다. (1M)

 

Page Table Entry도 역시 1,000,000개 들어갈 수 있는데..

Page Table도 메모리에 올라가는데, Entry 하나가 4Byte를 차지한다면 Page의 크기는 4096이니 Entry는 총 1024개를 담을 수 있다.

하나의 Page로 Page Table을 저장할 수 없다. 총 1024개의 Page로 하나의 Page Table을 저장할 수 있다. 

 

그림에서는 각 Page들이 연달아서 등장하지만, 메모리에서는 페이지들이 흩어져서 저장된다. 

각 조각을 논리적으로 연결해주기 위해 계층을 하나 추가해 각 Page의 Frame Number를 기록해 줘야 한다. - Outer Page Table

 

이렇게 Page Table을 여러 계층으로 구성하는 설계를 Multi-Level Page Table이라고 부른다.

 

 

 

 

 

2050개의 Page로 구성되는 프로세스가 있다. 당연히 Page Table Entry도 2050개.

 

Page Table도 메모리에 올려지고, 메모리는 Frame 단위로 데이터를 다루며 한 Frame은 4KB이다.

Frame 하나는 1024개의 Page를 저장할 수 있다.

 

Page Table의 첫 번째 Page는 21번 Frame에 저장되어 있고, 두 번째 Page는 24번 Frame에 저장되어 있다.

그러니, Page Table을 구성하는 여러 Page가 메모리의 어떤 Frame에 저장되어있는지 알려주는 계층이 필요하고, Outer Page Table을 도입해 매핑한다.

 

 

 

 

4KB Page를 사용할 때 offset은 12비트로 표현한다.

32비트 주소에서 12비트를 먼저 계산하면 나머지 비트는 모두 Page Number를 표현한다.

 

Page Number는 Page Table에서 몇 번째 Entry인지를 나타내는 정보인데, 2계층 Page Table이라면 값을 찾아갈 때 Outer Page Table에서  n번째 Entry이고, 그 다음 계층에서는 m번째 Entry인지 알아야 한다. 

 

그러니 20비트를 나눠서 특정 부분은 Outer Page Table의 인덱스로 사용하고, 나머지 부분은 Page Table의 인덱스로 사용한다.

 

 

 

 

20비트를 각각 10비트씩 할당해서 사용한다.

 

Page of Page Table에서는 1024개의 Page Table Entry를 저장할 수 있는데, 1024개를 식별하기 위해 10비트가 필요하다. (2^10)

Page Table Entry를 통해 Frame Number를 찾았다면, 그 Frame의 어느 부분을 확인할 지를 결정하는 offset 값을 확인해야 한다.

 

맨 처음 Outer Page Table을 찾아갈 때는 CPU 내부 Page Table Base Register 에서 읽는다.

 

---

 

 

 

32비트 아키텍처에서는 Page Table을 2계층으로 구성하는데, 64비트 아키텍처에서는 Page Table을 4계층으로 구성해야 한다.

가상 주소 공간이 커질수록 Page Table도 커지기에.. 더 많은 계층을 사용해야 더 많은 Page를 연결할 수 있다.

 

계층이 많아질수록 Memory Access를 여러 번 수행해야 하기에 시간이 오래 걸린다. 

이런 문제를 해결하기 위해 Translation Lookaside Buffer라는 특별한 하드웨어를 사용하는 방법이 도입됐다. 

 

 

 

 

좌측은 TLB를 사용하지 않는 컴퓨터에서의 주소 변환 과정을 보여준다. (1계층 Page Table)

가상 메모리의 Page 번호를 보고 Page Table으로 찾아가 Frame 번호를 읽는다. 이후 Frame 번호와 offset을 사용해 주소를 알아낸다.

 

우측은 TLB를 사용하는 컴퓨터에서의 주소 변환 과정을 보여준다. 

CPU 내부에서 TLB를 사용해 최근에 Access한 프로세스의 Page 번호와 그 Page에 해당하는 Frame 번호를 저장한다. 

즉, 5번 Page는 37번 Frame에 위치한다는 정보를 CPU가 알아낼 수 있어 Bus를 타고 메모리로 가지 않아도 된다. 

 

TLB는 Frame 번호와 Page 번호를 함께 저장한다.

Page Table에서는 프로세스의 Page 개수만큼 Page Table Entry가 존재한다. 

Page Table Entry는 연속적으로 존재하기에 굳이 Page 번호를 저장하지 않아도 되지만, TLB에서는 프로세스의 Page 수 만큼 Entry를 저장하지 않는다. 

 

CPU 내부에 저장하는 공간이기에 효율적으로 사용해야 한다. 하드웨어가 허용하는 수 만큼만 저장할 수 있다. 

그렇기에.. TLB의 2번째 칸이라고 해서 프로세스의 2번 Page에 해당하는 내용이 아니다. 그러니 Frame 번호와 Page 번호를 함께 저장해야 한다. 

 

TLB는 CPU 내부 공간이고 병렬로 검색할 수 있어 훨씬 빠르고, 여러 계층을 탐색할 필요 없이 한 번에 찾아갈 수 있다. 

프로그램의 Locality에 따라 Access한 페이지를 자주 Access하는 경향이 있으니 TLB를 사용해 성능을 끌어올릴 수 있다. (반복문 예시)

 

 

 

 

 

TLB는 캐시라고 생각하면 된다. TLB에 원하는 내용이 있으면 hit, 없으면 miss로 처리된다. 

 

TLB에는 P비트 등 제어 정보도 함께 저장하는데, P비트를 확인해 현재 메모리에 올라오지 않은 Page에 접근하는 경우 Page fault Trap이 발생해 보조기억장치에서 해당 Page를 메모리에 올려준다. (Kernel로 Mode Change 발생)

 

즉, Trap이 발생한 후 디스크에게 보조기억장치에서 데이터를 읽으라고 시켜놓고 CPU는 다른 프로세스에게 넘어간다. 

이후 Interrupt가 걸리면 메모리에 데이터를 올리고 해당 데이터를 요구하던 프로세스를 깨워 다시 스케쥴링돼 Page fault가 발생했던 문장을 다시 실행해 작업을 처리한다. 

 

반도체에서 RAM을 읽거나 쓰는데 걸리는 시간은 1ms이고, TLB를 사용한 Associate Lookup 방식을 사용할 때 걸리는 시간은 ε로 표현하고, 이 값은 1ms보다 몇백배는 더 빠르다.

 

내가 원하는 페이지가 TLB에 저장되어있을 확률을 a라고 해보자. TLB에 저장되어있지 않을 확률은 (1-a) 이다.

 

Effective Access Time = (ε +1) α + (ε + 1 + 1)(1 –α) = 2 + ε – α

TLB에 있을 때 걸리는 시간  * TLB에 있을 확률 + TLB에 없을 때 걸리는 시간 * TLB에 없을 확률 

 

여기서 Effective는 평균을 의미한다. 

저 수식에서 ε는 TLB를 읽을 때 걸리는 시간을 의미하고, 1은 RAM을 읽고 쓸 때 걸리는 시간을 의미한다. 

계층이 추가된다면 (ε + 1 + 1 + 1...) 이런 식으로 계속해서 더해진다.

 

사실.. TLB를 도입하지 않는다면 2계층 Page Table을 사용할 때 2 만큼의 시간이 소요되는데..
TLB를 도입하게 되면 2 + ε - α 만큼 걸리게 되니 오버헤드가 좀 더 늘었다고 생각할 수 있다. 

 

여기서 ε는 1에 비하면 매우 작은 수이고, α는 hit 확률이니 hit 확률이 높을수록 EAT는 2보다 작아지게 되니 더 효율적이다. 

계층이 커질수록 효과는 더 커진다.