[14] 운영체제 - Memory-3

안녕하세요. 굉장히 오래간만에 하는 포스팅인데요! 사실 조금 게을렀던 것도 있지만

운영체제 2차 시험이 있었기 때문에 따로 포스팅하기 양이 애매해서 조금 미뤄둔 것도 있습니다!

오늘은 저번 시간에 이어서 Page table의 구조의 종류와 각 구조에 대해서 공부해보도록 하겠습니다.

그럼 바로 시작하겠습니다!

Page Table의 구조에는 크게 세 가지가  있는데요. 하나하나 살펴보도록 하겠습니다!

1. Hierarchical Paging (계층적 구조)

기본 Page table 구조는 Logical address를 하나의 테이블에 담았다면, 계층적 구조는 그 Logical address를 다시 여러 테이블로 나눈 구조를 말합니다. 예시로는 두 table로 구성한 Two-level Page table 구조입니다.

Two-level page table scheme

왜 멀쩡한 테이블을 다시 여러 테이블로 나누는 것일까요? 예를 들어 설명해보도록 하겠습니다.

4K 페이지 크기인 32-bit 명령어 기계가 있고 각 페이지 entry 사이즈가 4-byte라 가정하겠습니다.

그렇다면 하나의 페이지의 크기가 4K이므로 2^12이며 명령어에서 offset은 12-bit로 표현이 가능하므로

명령어 32-bit 중 12-bit는 offset을 표현하는데 사용이 됩니다. 그럼 20-bit가 남게 되는데요

만일 온전히 20-bit로만 테이블을 접근하게 된다면 각 페이지의 entry 크기가 4-byte이므로

2^2 X 2^20 = 2^22로 Page table의 크기가 굉장히 커지게 됩니다. 이러한 큰 크기를 메모리에 연속으로 할당하는 것은 역시 부담일 수 있기 때문에 20-bit를 다시 각각 10-bit로 나누어, 즉 두 계층의 테이블 구조를 사용하게 됩니다.

다음의 그림을 보시면 더욱 이해가 잘 되실 것입니다.

이러한 계층적 구조는 64-bit 명령어 기계에서는 적합하지 않습니다.

2. Hashed Page table (해시)

Hashed Page table 구조는 32-bit 이상의 명령어 기계에서 주로 사용하는 구조입니다.

명령어 비트 중 Page 테이블의 인덱스의 해당하는 p를 hash function의 입력값으로 넣어 나온 결괏값으로 hash table을 검사하여 해당하는 Physical Memory를 찾아가게 됩니다. 같은 hash 결괏값에 대해서는 리스트를 이용하여 하나의 hash table 위치에 연결해 놓습니다.

3. Inverted page table (역전 구조)

Inverted page table은 말 그대로 역전 구조 테이블입니다. 역전 구조라면 어떤 것의 역전을 말하는 것일까요?

이전의 테이블들은 모두 Logical address를 기준의 테이블이었습니다. 프로세스 당 하나의 테이블을 갖고 있었으며 나누어진 페이지의 순서대로 Page table에 순서대로 대응되는 구조였습니다.

하지만 역전 구조는 그 반대로 Physical address의 입장(?)에서 만들어진 테이블 구조입니다.

첫 번째 프레임은 테이블의 첫 번째에 저장되며 테이블은 각 프레임은 어떤 프로세스와 대응되는지에 대한 정보를 담고 있습니다. 

그러므로 이전에는 테이블에 단순히 몇 번째 프레임인지에 대한 정보만을 담고 있었다면 이번에는 프로세스 번호인 pid 값도 담고 있습니다. 또한 역전 구조 테이블은 프로세스 당 하나가 아닌 전체적으로 하나만 갖고 있어도 되는 장점을 갖고 있지만 테이블의 크기가 크기 때문에 그만큼 검색에 소요되는 시간이 늘어나게 됩니다.

오늘은 간단히 Paging 기법에 사용되는 테이블들의 구조에 대해서만 알아보았습니다.

다음 시간에는 Paging 기법과는 비슷하면서 다른 Segmentation에 대해서 알아보도록 하겠습니다.

감사합니다!