운영체제 16. 페이징 : 더 작은 테이블

16. 페이징 : 더 작은 테이블

16.1 간단한 해법 : 더 큰 페이지

• 페이지 테이블의 크기를 간단하게 줄일 수 있는 방법이 있다. 페이지 크기를 증가 시키면 된다. 32비트 주소 공간에서 16KB 페이지를 가정해보자. 18비트의 VPN과 14비트의 오프셋을 갖게 된다. 각 PTE(4바이트)의 크기가 모두 동일하다면, 페이지 테이블에 2^18 개의 항목이 있으며, 페이지 테이블의 총 크기는 1MB가 된다. 기존 페이지 테이블 대비 크기가 1/4로 감소된다.
• 페이지 크기의 증가는 부작용을 수반한다. 가장 큰 문제는 페이지 내부의 낭비공간이 증가한다는 것이다. 이를 내부 단편화라 한다. 응용 프로그램이 여러 페이지를 할당 받았지만, 할당받은 페이지의 일부분만 사용하는터에, 결국 컴퓨터 시스템의 메모리가 금방 고갈되는 현상이 발생한다. 이런 연유에서, 많은 컴퓨터 시스템들이 비교적 작은 페이지들을 사용한다.

16.2 하이브리드 접근 방법 : 페이징과 세그멘트

• 선형 페이지 테이블의 동작을 면밀히 분석해보면, 페이징과 세그멘테이션을 효과적으로 결합할 수 있다는 사실을 발견할 수 있다.
• 프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신, 논리 세그멘트마다 따로 페이지 테이블을 두면 어떨까?
• 세그멘테이션에서는 세그멘트의 물리주소 시작위치를 나타내는 베이스 레지스터, 그리고 크기를 나타내는 바운드 또는 리미트 레지스터가 있다. 베이스 레지스터는 세그멘트 시작 주소를 가리키는 것이 아니라 세그멘트의 페이지 테이블의 시작 주소를 갖는다. 바운드 레지스터는 페이지 테이블의 끝을 나타내기 위해서 사용한다.
• 하드웨어에 세 개의 베이스/바운드 레지스터 쌍이 코드와 힙 그리고 스택을 위해서 존재한다고 가정하자. 실행중인 프로세스에서, 각 세그멘트의 베이스 레지스터는 각 세그멘트 페이지 테이블의 시작 물리 주소를 갖게된다. 이 시스템에서 모든 프로세스들은 세 개의 페이지 테이블을 갖는다. 문맥교환시, 이 레지스터들은 새로 시작되는 프로세스의 페이지 테이블 위치값으로 변경된다.
• TLB 미스가 발생하면, 하드웨어는 세그멘트 비트(SN)을 사용하여 어떤 베이스와 바운드 쌍을 사용할지 결정한다. 하드웨어는 그 레지스터에 들어있는 물리주소를 VPN과 조작하여 페이지 테이블 항목(PTE)의 주소를 얻는다.
• 선형 페이지 테이블의 작동과 거의 동일하다. 차이가 있다면 하나의 페이지 테이블 베이스 레지스터를 사용하는 대신 세 개 중의 하나의 세그멘트 베이스 레지스터를 사용하는 것이다.
• 하이브리드 기법에서 핵심은 세그멘트마다 바운드 레지스터가 따로 존재한다는 것이다. 각 바운드 레지스터의 값은 세그멘트의 최대 유효 페이지의 개수를 나타낸다. 예를 들어 첫 세 개의 페이지들은 코드 세그멘트로서 사용 중이라면, 코드 세그멘트 페이지 테이블은 세 개의 항목만 할당을 받을 수 있을 것이고 바운드 레지스터는 3으로 설정된다. 해당 세그멘트의 범위가 넘어가는 곳에 대한 메모리 접근은 예외를 발생시키고, 해당 프로세스는 종료 될 것이다.
• 이 기법 역시 문제가 있다. 첫째, 여전히 세그멘테이션을 사용한다. 빈공간이 많은(Sparsely used)라는 자료구조를 사용하여 페이지 테이블 각 페이지의 할당여부와 위치를 파악한다. 페이지 디렉토리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치정보를 가지고 있다.
• 간단한 2단계 테이블에서, 페이지 디렉토리의 각 항목은 페이지 테이블의 한 페이지를 나타낸다. 페이지 디렉토리는 페이지 디렉토리 항목들로 구성된다. 각 항목은 페이지 테이블의 각 항목과 유사하다. 유효 비트와 페이지 프레임 번호를 갖고 있다. 하지만 PTE의 유효비트와 PDE의 유효비트는 약간 다르다. PDE가 유효하다는 것은, 그 항목이 가리키고 있는 페이지들 중 최소한 하나가 유효하다는 것을 의미한다.

멀티 레벨 페이지 테이블의 장점

• 첫째, 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당된다. 그렇기 때문에, 보다 작은 크기의 페이지 테이블로 주소 공간을 표현할 수 있다.
• 두 번째, 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이하다.

단점

• 한 가지 유의사항은 멀티레벨 테이블에는 추가비용이 발생한다. TLB 미스시, 주소 변환을 위해 두 번의 메모리 로드가 발생한다. 페이지 테이블의 크기를 줄이는데 성공하였으나 메모리 접근 시간이 증가했다.
• 또 하나의 단점은 복잡도다. 페이지 테이블 검색이 단순 선형 페이지 테이블의 경우보다 더 복잡해진다.

2단계 이상 사용하기

• 지금까지는 멀티 레벨 페이지 테이블은 페이지 디렉토리와 페이지 테이블의 2개 단계를 가정했다. 경우에 따라 트리의 단계를 더 증가시키는 것도 가능하다.

16.4 역 페이지 테이블(Inverted page table)

• 여러개의 페이지 테이블 대신 시스템에 단 하나의 페이지 테이블만 둔다. 페이지 테이블은 물리 페이지를 가상 주소 상의 페이지로 변환한다. 역 페이지 테이블의 각 항목은 해당 물리페이지를 사용중인 프로세스 번호, 해당 가상 페이지 번호를 갖고 있다.
• 역테이블에서는 주소 변환을 위해 전체 테이블을 검색해서 원하는 가상 주소 페이지를 갖는 항목을 찾아야 한다.
• 탐색속도 향상을 위해 주로 해시테이블을 사용한다.

16.5 페이지 테이블을 디스크로 스와핑하기

• 마지막으로 중요한 가정을 제거한다. 이제까지는 페이지 테이블이 커널 소유의 물리 메모리 영역에 존재한다고 가정한다. 페이지 테이블 크기를 최대한 줄이더라도, 여전히 모든 페이지 테이블을 메모리에 상주시키기에는 메모리 요구량이 너무 클 수도 있다. 어떤 시스템들은 페이지 테이블들을 가상 메모리에 위치시키고, 메모리가 부족할 경우 페이지 테이블들을 디스크로 스왑(Swap)한다.