페이지 테이블(Page Table)

이전 포스팅에서 살펴본 바와 같이 페이지 테이블은 MMU가 논리 주소를 물리 주소로 변환하는 과정에서 페이지와 프레임을 매핑해주는 역할을 한다.

OS는 각 프로세스마다 하나의 page table을 할당한다. 페이지 테이블이 256개 이하인 경우 레지스터를 이용할 수 있지만 대부분의 경우 메인 메모리에 저장된다.

메인 메모리를 이용한 페이지 테이블에서는 페이지 테이블에 대한 최소한의 정보를 레지스터에 저장해 실행 속도를 높일 수 있다.

• PTBR(Page Table Base Register): 페이지 테이블에 대한 메모리 주소를 저장
• PTLR(Page Table Length Register): 페이지 테이블의 크기를 저장, memory protection에 이용됨.

한계

하지만 이렇게 레지스터를 이용하더라도 메인 메모리에 전적으로 페이지 테이블을 저장하는 경우 두 가지 한계를 가진다.

1. 속도 저하 문제: 데이터에 접근하기 위해서는 페이지 테이블 + 실제 데이터 접근, 총 두 번의 메모리 접근이 필요하다.
2. 용량 문제: 각 프로세스마다 하나의 페이지 테이블을 가지고 있기 때문에, 메모리에 로드되는 프로세스가 많아질수록 페이지 테이블이 메모리를 차지하는 공간도 많아지게 된다.

TLB(Translation Look-aside Buffers)

속도 저하 문제를 해결하기 위해 TLB가 이용된다. TLB는 주소 변환을 위한 고속의 메모리 장치이다. 연관 메모리(associative memory)이기 때문에 빠른 검색이 가능하다. 페이지 번호와 프레임 번호가 key-value 형태로 저장되며 용량은 주로 2K bytes 이하이다.

CPU가 특정 페이지를 요구하면 MMU는 먼저 TLB에 해당 페이지에 대한 정보가 있는지 찾아본 후, 정보가 있으면 페이지 번호에 해당하는 프레임 번호를 가져오고, 정보가 없으면 메인 메모리에 있는 페이지 테이블에 접근해 해당 프레임을 가져온다. 이때 해당 정보를 TLB에 캐싱해놓는데, 만약 TLB가 다 찼다면 교체 알고리즘에 따라 저장 정보를 교체한다.

메모리 보호

페이지 테이블에 부가적인 정보를 붙여서 메모리 보호 기능을 수행할 수 있다.

• 보호 비트(Protection bits)

  • 페이지 테이블의 각 엔트리에 붙여져 해당 페이지가 read-only인지 read-write인지를 표시한다.

• 유효-무효 비트(Valid-invalid bit)

  • 해당 페이지가 합법적인지를 나타낸다.

출처: Operating System Concepts(10th ed)

위 예시의 경우, 프로세스가 6개의 페이지로 나뉘어져 있다. 페이지 테이블의 0~5번 엔트리는 valid bit가 붙어있고, 6, 7번 엔트리는 invalid 비트가 붙어있다. 만약 6번 혹은 7번 페이지에 접근하려고 할 경우 trap을 발생시켜 메모리를 보호할 수 있다.

공유 페이지(Shared page)

프로세스 간에 공유되는 페이지는 각 프로세스의 페이지 테이블에서 같은 프레임을 가리키도록 만들어 메모리 사용량을 줄일 수 있다. 각 프로세스는 text(code) 영역과 data 영역을 다른 페이지로 분리해서 text 영역(read-only)을 다른 프로세스와 공유함으로써 메모리 활용도를 높일 수 있다. 물론 이렇게 의미단위로 페이지를 분리할 경우 내부 단편화 현상이 더 많이 일어날 수 있다.

여러 페이지 테이블 구조

TLB를 이용해 속도 저하 문제를 해결했다면 이번엔 용량 문제의 해결책으로 어떤 것이 있는지 알아보자

Hierarchical Page Table

페이지 테이블을 계층적으로 구성하는 방법으로, 쉽게 말하면 페이지 테이블을 다시 페이징하는 방법이다.

예시로 two-level paging을 살펴보자.

논리 주소 공간이 $2^{8}$ bytes, 페이지 크기가 16 bytes라고 할 때, 계층적 페이징을 사용하지 않으면 위 그림의 왼쪽처럼 page number를 나타내는 비트는 4개가 된다.

two-level paging에서는, page number를 나타내는 비트를 반으로 나눠 outer page number와 inner page number를 나타내도록 한다. MMU는 CPU가 낸 논리 주소를 통해 outer page에 먼저 접근한 후 inner page로 접근한다(결과적으로 non-heirarchical에 비해 메모리 접근이 한번 더 늘어나지만 TLB를 이용해 최적화할 수 있다).

이 방법이 왜 메모리 사용량을 줄일 수 있는지 의아할 수 있다. 언뜻보면 페이지 테이블이 하나 더 추가된 것처럼 보일 수 있기 때문이다.

이렇게 계층적으로 페이지를 관리하면, 페이지 테이블을 하나 쓸때는 불가능한 일이 한 가지 가능하다. 만약 어떤 inner page table의 엔트리가 모두 비어있다면, outer page table의 해당 엔트리에 이를 마킹해둔다. 모든 엔트리가 비어있는 inner table은 물리 메모리에 저장하고 있을 필요가 없기 때문에 결과적으로 메모리 사용률을 줄일 수 있다.

Hashed Page Table

• Logical address space가 32bit보다 커질 때 주로 사용한다.

• 가상 페이지 넘버가 페이지 테이블에 해싱된다.

  • 페이지 테이블은 같은 위치로 해싱된 요소들의 연결 리스트를 가진다.
• 연결 리스트를 따라 가상 페이지 번호와 일치하는 요소가 있는지 검색하고 일치하는 요소의 physical frame을 얻는다.

Inverted Page Table

일반적인 페이지 테이블은 현제 페이지가 어떤 프레임에 저장되어있는가를 나타내는 반면 inverted page table은 각각의 프레임들이 어떤 프로세스의 어떤 페이지에 할당되어 있는가를 나타낸다.

따라서 각 항목은 메모리의 각 frame에 대응되며 전체 시스템에 존재하는 페이지 테이블은 한 개 뿐이다.

페이지 테이블을 획기적으로 줄일 수 있으나 특정 프레임을 탐색하기 위해서는 전체 페이지 테이블을 탐색해야되기 때문에 시간이 오래걸린다. 잘 사용되지 않는다고 한다.