Paging - Page Table Structure, Segmentation

Paging

Page Table Structure

1) Hierarchial Paging

- 계층 구조를 갖는 Paging 기법이다.

- Page table의 사이즈를 줄이기 위해 고안된 방법이다.

- 하나의 logical address를 여러 개의 Page table을 통해 여러 Level로 나누어 주어 page table의 사이즈를 줄이기 위한 방법이다.

- 간단한 방법으로는 Two-level page table 방법이 있다.

위와 같은 형태의 계층 구조로 되어있다. Level 1인 outer page table에서는 해당 page number가 valid한지 invalid한지 판단한다. 즉, invalid하다면 level 2에 page table이 존재하지 않는 것이기 떄문에 memory 절약을 할 수 있게 되는 것이다. valid하다면 outer page table이 가리키고 있는 level 2의 page table에서 page number를 찾아 frame number를 통해 physical address를 계산한다.

P1은 outer page table의 entry 개수(인덱스)이고 P1을 통해 Level 2의 page table의 시작주소를 알 수 있다. P2값을 통해 frame number를 알 수 있다. 만약 64bit를 사용한다면 P1은 42, P2는 10, offset은 12bit를 가진다. 만약 계층 구조의 page table을 사용하지 않는다면 page number는 52bit를 사용하게 되어 size가 더욱 커질 것이다.

level을 늘려서 page table의 사이즈를 더 줄일 수 있다. 실제 Linux에서는 Level 3의 계층 구조를 사용하고 있다. 위 그림에서 하나의 page table을 추가하여 P1->P2->P3을 거쳐 frame number를 찾는 구조로 되어있다.

2) Hashed page table

- Hashing 기법을 사용해 page table을 관리하는 방법이다.

- page table에는 가상의 page number가 해싱되어 있다.

- 각 index에 해당하는 entry를 chain형태로 관리해준다.

- 가상 page number와 매칭되는 number를 chain에서 찾아내고, matching되는 number를 찾으면 frame number를 추출해 physical address를 계산한다.

logical address로 받은 주소로 page number를 hashing function을 통해 index값을 얻는다. 이 index값을 통해 hashed page table에서 page number와 매칭되는 frame number를 찾아 physical address로 바꿔준다. 해당 index에는 여러개의 (page number, frame number)로 이루어진 entry들이 chain으로 연결되어 있을 수도 있다. 이 chain에서 해당 page number와 일치하는 값을 찾아 frame number를 알아낸다.

3) Inverted page table

- 각각의 process가 page table을 가지면 전체 사용되는 page table의 사이즈가 너무 커지기 때문에 시스템적으로 하나의 page table만 사용하는 방법이다.

- 하나의 엔트리에는 실제 page와 frame이 mapping되어 있다.

- table의 entry는 (Process ID, page number)와 같이 이루어져 있고 table의 index가 frame number를 나타내는 방식으로 page table이 구성되어 있다.

- process ID를 찾기 위해서 전체의 table을 검색해야 한다는 단점이 있다.

page table에서 process id를 기준으로 찾기 때문에 위 부터 순차적으로 검색해야 한다. frame number는 index를 기준으로 되어있기 때문에 해당하는 process id를 찾으면 해당 index를 frame number로 넘겨서 physical address를 계산한다. 모든 logical address에 대해서 page table을 순차적으로 검색해야한다는 점에서 Search time이 엄청 커질 수 도 있다는 단점이 있다.

Segmentation

- User의 Memory-View를 제공해주는 Memory Management 전략이다.

- Segment라는 Logical unit을 사용하고 프로그램은 segment의 집합으로 이루어져있다.

- segment는 main program, procedure등 여러 가지가 나뉘어 저장되어 있다.

- logical address는 (segment number, offset)의 튜플로 구성되어있다. 

- Segment table : segmentation도 page와 비슷한 구조로 시작 주소와 offset을 가지고 physical address를 찾기 때문에 segment table을 사용한다. table에는 두가지 entry가 있다.

-> base : 메모리 내에 있는 physical address의 시작 주소를 가지고 있다.

-> limit : segment의 길이를 나타낸다.

- Segment-table base register(STBR) : Segment table의 시작주소를 담고있는 register이다.

- Segment-table length register(STLR) : 프로그램에 사용되는 Segment의 수를 담고있는 register이다. 즉, 프로그램의 길이를 나타낸다고 생각해도 된다.

- Protection

-> Segment table에도 각각의 entry에 Protection을 위한 valid bit가 존재한다. valid bit가 0인 경우 정상적이지 않은 segment를 뜻한다.