페이지 테이블

0. 시작하기에 앞서...

가상 메모리에 대한 문서를 작성하기 전에, 

가상 메모리를 이해하는데, 필요한 선행 지식 중 하나인 페이지 테이블에 대해 정리한다.

이 문서는 Wikipedia의 문서를 번역하며, 개인적인 코멘트를 더해 작성되었다.

1. 페이지 테이블

가상 메모리를 사용하는 운영 체제에서 개별 프로세스는 자신만의(고유의) 가상 주소 공간을 가지고 있다.

32비트 프로세스는 0x00000000 ~0xFFFFFFFF까지 표현될 수 있기에 4GB 크기의 주소 공간을,

64비트 프로세스는 0x000000000000000 ~ 0xFFFFFFFFFFFFFFFF까지 표현될 수 있기에 16EB 크기의 주소 공간을 가진다.

각 프로세스들의 가상 메모리는 물리 메모리의 각기 다른 영역에 분산되어 로드될 수 있거나,

page-out 되어 paging file(하드 디스크에 존재하는)에만 저장될 수 있다.

프로세스가 특정 메모리에 접근하려 하면, 운영체제는 프로세스의 가상 주소를 시스템의 물리 메모리 주소로 변환해 주어야 한다.

페이지 테이블은 가상 주소와 물리 메모리 주소의 매핑 테이블이며, 개별 매핑 데이터는 Page-Table-Entry(PTE)라고 한다.

페이지 테이블은 프로세스마다 하나씩 존재하게 되며, 메인 메모리 (RAM)에 상주하게 된다.

즉, 많은 프로세스가 구동될 수록, 페이지 테이블로 인한 메인 메모리 사용이 커짐을 의미한다.

참고로, 가상 메모리와 물리 메모리의 관계는 아래 그림과 같이 표현될 수 있다.

2. Virtual address -> Physical address 변환 과정

CPU의 MMU(Memory Management Unit)는 최근에 맵핑된 페이지 테이블의 정보들을 TLB라는 연관 캐쉬에 저장한다.

(TLB : Translation Lookaside Buffer)

TLB는 자주 쓰는 페이지 테이블의 주소를 저장해 둠으로써, translation의 속도를 향상시켜 주는 역할을 한다.

1) 가상 주소가 물리 메모리 주소로 변환되어야 할 때, 먼저 TLB를 검색한다.

TLB에서 검색이 성공하면 (TLB hit), 즉시 물리 메모리 주소를 반환하며, 프로세스는 해당 주소로 접근이 가능하다.

2) 만약, TLB에서 검색이 실패하면 (TLB miss), 통상적으로 핸들러는 해당 가상 주소에 맵핑된 물리 메모리 주소가 있는지

페이지 테이블을 검색하게 된다. (Page walk)

3) 페이지 테이블에서 일치하는 맵핑 데이터를 찾았다면, 해당 정보를 TLB에 업데이트하고,

1) 번 과정으로 돌아가 해당 가상 주소의 물리 메모리 주소로의 요청을 재개하게 된다.

3) 과정에서 페이지 테이블에서도 적절한 물리 메모리 주소를 찾기 못하게 되는 경우가 있는데, 이는 두 가지 이유에서 비롯된다.

첫번째는 가상 메모리 주소 자체가 유효하지 않은 경우이다.

이 경우, 운영체제는 해당 가상 주소 접근을 요청한 프로세스에게 segmentation fault를 발생시키게 된다.

두번째가 일반적인 경우인데, 해당 가상 메모리 주소가 물리 메모리에 존재하지 않는 경우이다.

이 경우, 해당 page가 다른 메모리 접근 요청에 의해 물리 메모리 공간이 부족해져 page-out 된 상황이다.

Page가 page-out되면, 하드디스크의 보조 저장소로 옮겨지게 되며, 

이 저장소가 우리가 알고 있는 paging file 또는 swap file이다.

다시 돌아가서, 프로세스가 접근하려는 가상 메모리 주소가 물리 메모리에서 page-out 된 상황이라면,

운영체제는 page fault 를 발생시키며, 아래와 같은 순서로 다시 물리 메모리로 로드시킨다.

a. 물리 메모리가 꽉 차지 않았다면(empty frame이 존재한다면), 

페이징 파일에 존재하는 데이터를 램에 존재하는 empty frame으로 로드하면서, 페이지 테이블과 TLB의 내용을 갱신한다.

b. 물리 메모리에 empty frame이 존재하지 않는다면, (즉, 여유 공간이 없다면)

램에서 empty로 변경할 페이지를 찾은 후 (이 과정에서 page replacement alogorithm이 적용된다)

페이지의 데이터가 변경되었다면, 이를 다시 paging file에 쓴 후 해당 page를 empty frame으로 변환시킨다.

그리고, 로드하려 했던 데이터를 방금 empty frame으로 만들었던 곳으로 로드하면서, 페이지 테이블과 TLB의 내용 역시 갱신한다.

이 경우 페이지 테이블이나 TBL 업데이트에는 page-out된 page에 대한 제거 과정도 포함된다.

a/b 과정을 모두 거치게 되면, 해당 가상 주소의 물리 메모리 주소로의 요청을 재개하게 된다.

지금까지의 과정을 TLB와 페이지 테이블 관점에서 정리하면, 아래 그림과 같다.

일반적인 경우엔 지금까지의 설명한 과정을 거치지만, 

공유 Memory Mapped File의 경우 아래 그림과 같이프로토타입 페이지 엔트리 테이블를 찾는 과정이 하나 더 들어가게 된다.

3. 페이지 테이블 데이터

가장 단순한 페이지 시스템은 종종 프레임 테이블과 페이지 테이블을 함께 유지한다.

프레임 테이블은 어느 프레임이 매핑되어 있는지에 대한 정보를 들고 있다.

조금 더 진보된 시스템에서는 프레임 매핑 정보 외 부가적인 정보들도 함게 포함한다.

페이지 테이블은 가상 주소의 페이지와 물리 메모리 프레임간의 매핑 정보를 들고 있다.

그리고, 다음과 같은 부가 정보들을 포함한다.

• reference bit (accessed bit)
• valid bit (present bit)
• dirty bit (modified bit)
• process ID information

1) Reference bit

Page replacement alogorithm에 사용되며, 해당 페이지에 대한 접근이 있었는지에 대해 기록한다.

2) Valid bit

하드 디스크와 같은 이차 저장 장치는 물리 메모리의 총량을 증가시키는데 사용될 수 있다.

Page 단위의 메모리는

• 페이징 파일에서 물리 메모리로 page-in 될 수 있고,
• 물리 메모리로부터 페이징 파일로 page-out 될 수 있다.

위 페이지 테이블의 정보 중 present bit는 이 page가 물리 메모리에 있는지, 페이징 파일에 있는지 여부를 나타내는데 사용된다.

3) Dirty bit

Dirty bit는 가상 메모리 관리 시스템의 성능을 향상시키는 데 아주 중요한 역할을 수행한다.

어떤 page가 물리 메모리로 page-in 된 이후, 내용이 전혀 달라진 게 없다면

이 page가 추후 paging file로 page-out 될 때, 달라진 게 없으므로 내용을 다시 복사하지 않아도 되게 된다.

그와 반대로 page-in 된 이후 내용이 달라진 것이 있다면, page-out 될 때 반드시 해당 내용을 pagine file에 써야 할 것이다.

이 과정에서 page-out 되기까지 해당 page의 내용이 변경 되었는지를 기록하는 것이 dirty bit 이다.

만약, 이 dirty bit 이 없었다면, 모든 page-out 과정에서 page data copy가 발생할 것이고, 이는 불필요한 성능 하락을 발생시킨다.

4) Process ID information

가상 메모리 관리 시스템은 어떤 페이지가 어느 프로세스와 연관이 있는지 알고 있어야 한다.

두 개의 프로세스가 각기 다른 목적을 위해 동일한 주소의 가상 메모리에 접근한다고 가정해 보자.

(가상 주소는 프로세스별로 독립적이므로, 주소가 같다고 해서 같은 메모리를 가리키는 것은 아니다)

페이지 테이블은 두 프로세스가 요청한 가상 메모리 주소에 대해 정보를 각기 저장시킬 수 있어야 한다.

이를 구분하기 위해 페이지 테이블은 두 개의 정보를 기록할 때 각기 다른 identifier를 부여하거나,

해당 process id를 기록해 두어야 한다.

이러한 방식을 대체하고자 하는 방식이 페이지 테이블을 프로세스별로 두는 것이다.

최근의 OS는 이 방식을 더 많이 사용한다.

즉, 프로세스별 페이지 테이블이 존재하고, 이들은 메인 메모리(RAM)에 상주하는 것이다.

4. 페이지 테이블의 종류

페이지 테이블은 다음과 같은 종류가 있다고 한다.

• Inverted
• Multi-level
• Virtualized
• Nested

이 중 x86 이 사용하는 것은 Multi-level 방식이라고 한다.

만약 Single-level 즉, 하나의 page table로 4GB의 주소 공간을 표현하기 위해선 2 ^ 20개의 PTE가 필요하다.

(4GB / 4KB(1 page size) = 2 ^ 32 / 2 ^ 12 = 2 ^ 20)

2 ^ 20개면 1024 * 1024개의 PTE 정보를 가져야 하는데, 

이러면 페이지 테이블의 크기가 너무 커져서, 2 or 3 level paging을 하게 된다.

Page directory와 page table로 나누어, 이들의 관계로 전체적인 크기를 감소시키는 것이다.

음... 더 이상 자세한 내용은 wikipedia 페이지를 참고하기 바란다. (정리 귀차늠 -_-)

웹질 하다가 페이지 테이블 종류와 설명에 대한 유투브를 찾아냈다.

http://www.youtube.com/watch?v=Vw1B-U0Frws

출처  : http://egloos.zum.com/sweeper/v/2988646 by 수까락