[운영체제] 페이지 테이블

페이지 테이블의 구조

• 32비트 주소체계를 사용하는 경우 컴퓨터가 있다고 할 때, 주소 공간의 크기는 2의 32승이다.
• 페이지 하나의 크기가 4KB라면 이는 약 2^12이다.
• 페이지 테이블에 2^20개(2^32/2^12)의 정보가 저장되어야 하고, 항목 당 4바이트가 사용된다면 각 프로세스는 2의 22승, 즉 4MB의 페이지 테이블 공간을 물리메모리에 필요로 하게 된다.
• 애초에 페이징이라는 것이 연속된 메모리에 공간을 할당하는 것이 불합리해서 그 문제를 해결하기 위해 고안된 것인데, 페이지 테이블 때문에 4MB라는 공간을 연속해서 사용해야 한다는 모순이 발생한다.
• 따라서 페이지 테이블 구조를 개선해야 한다. 페이지 테이블 자체도 더 작은 단위로 쪼개서 메인메모리에 탑재한다.
• 이를 구현하기 위해 계층적 페이징(Hierarchical paging), 해시 페이지 테이블(Hashed page table), 역 페이지 테이블(Inverted page table)이 사용된다.

계층적 페이징

• 논리주소를 구성하는 값 중 페이지 번호를 의미하는 p를 분할한다.
• 예를 들어 2단계 페이징 기법이라면, 20비트인 p를 p1, p2로 각각 10비트씩 분할한다. 그런 후 상위 부분인 p1을 위해서 바깥페이지 테이블(outer page table)을 구성하고, 하위 부분인 p2를 위해서 안쪽페이지테이블(innter page table)을 구성한다. 바깥 페이지 테이블이 안쪽 페이지 테이블을 인덱싱하고, 안쪽 페이지 테이블은 최종적으로 프레임으로 사상된다.
• forward mapped page table이라고도 부른다.
• p1은 10비트이므로 바깥 페이지 테이블에는 2의 10승개의 항목이 기록되고 한 항목은 4바이트씩이므로, 바깥 페이지 테이블의 크기는 2의 12승으로 4KB이다. (이는 정확히 한 페이지이다.) 바깥 페이지 테이블의 1024개(2^10)의 항목들이 각각 p2에 해당하는 안쪽 페이지 테이블을 인덱싱하므로 안쪽 페이지 테이블은 총 1024개의 페이지를 보유해야 한다.
• 결과적으로 총 1025개의 페이지가 필요하다. 만약 2단계 페이지를 하지 않았다면 2의 22승만큼의 연속된 크기를 차지했을 것이다. 하지만 계층적 페이징 기법을 활용하면 1025개의 페이지 각각이 메모리 어느 곳에 위치해도 괜찮게 된다.
• 정리 : 처음 바깥 페이지 테이블의 시작주소로 접근하여 거기에 p1의 값을 더해 해당 항목을 찾아가고, 거기서 안쪽 페이지 테이블의 시작주소를 얻어 그 값에 p2를 더해 안쪽 페이지 테이블 내의 항목을 찾아낸다. 그리고 그 항목의 내용으로부터 해당 페이지에 사상되는 프레임번호를 얻고 거기에 d값(오프셋)을 더해 최종 물리주소를 얻어낸다.

계층적 페이징 확장

• 만약 컴퓨터가 32비트 주소체계가 아니고 64비트 주소체계라면 문제가 커진다. 32비트 주소체계에서 생기는 p비트가 20비트로 커서 이를 2단계로 구분한 것인데, 64비트 주소체계의 p비트는 52비트이기 때문이다. 만약 2단계로 처리한다면 안쪽 페이지을 위해서는 한 페이지의 크기의 페이지 테이블을 활용해야 하므로 바깥 페이징에서 42비트를 사용하게 된다. 이는 결국 연속하는 2의 44승 만큼의 공간이 필요하다는 뜻이 된다.
• 이는 너무 크다. 따라서 2단계 이상의 다단계 페이징 주소변환을 사용한다.
• p1은 32비트, p2,p3는 10비트를 어드레싱하여 총 3단계의 페이지 테이블을 구성한다.
• 하지만 이런 방식을 사용하면 한 번의 주소결속을 위해 물리메모리를 4번 접근하게 되므로 속도가 저하될 수 있다.

해쉬 페이지 테이블

• '해쉬 페이지 테이블(Hashed Page Table)'을 사용한다. 논리주소에 대한 해쉬값을 이용해 바로 물리주소로 사상한다.
• 일반적으로 해쉬 기법을 사용할 경우 입력도메인의 크기가 출력도메인의 크기보다 훨씬 크다. 그에 따라 해쉬값이 겹치는 경우가 생긴다. 그런 경우를 collision(충돌)이 발생했다고 한다. 이러한 충돌 문제를 해결하기 위해 해쉬 테이블의 각 항목에 연결리스트를 두어 충돌이 일어난 논리 주소(가상 페이지 번호라고 부른다)에 대한 물리주소 값 쌍을 리스트로 관리한다.
• 이에 따라 해쉬 테이블의 각 항목은 3가지 정보의 필드를 가지게 된다. 필드1은 가상 페이지번호, 필드2는 사상되는 페이지의 프레임번호(물리주소 상의 프레임번호), 필드3는 연결 리스트 상 다음 원소에 대한 포인터. 이상이다.
• 정리 : 논리주소 값이 들어오면 해쉬 함수를 통해 해쉬 값으로 변환한다. 그 값으로 해쉬 페이지 테이블의 항목을 찾아가, 첫번째 항목의 필드1에 있는 가상페이지 번호와 비교한다. 매치되면 해당항목의 필드2의 프레임 번호를 사용해 물리주소로 변환하고, 매치되지 않으면 매치가 될 때까지 연결리스트를 따라가면서 필드1과 비교한다.
• 확장 : 해쉬 테이블은 테이블 각 항목이 한 프레임을 가리키지만 '클러스터 페이지 테이블'에서는 16 프레임 등의 여러 프레임을 가리키게 된다. 따라서 한 개의 페이지 테이블 항목이 여러 프레임에 대한 변환 정보를 가질 수 있고, 이에 대해 매번 해시값을 구할 필요가 없어 속도 상에도 유리하다. 이러한 '클러스터 페이지 테이블'은 메모리 접근이 비연속적으로 전체 주소공간에 대해 넓게 퍼져 있는 경우인 sparse address spaces에 유용하다.

역 페이지 테이블

• 페이지 테이블을 위한 많은 메모리 용량이 요구되는 이유는 각 프로세스마다 하나씩 페이지 테이블을 보유하기 때문이다. 이러한 문제를 해결하기 위해 페이지 테이블을 하나만 두고, 메인메모리 각 프레임마다 페이지 테이블의 한 항목을 할당한다. 대신 페이지 테이블의 각 항목에는 해당 프레임에 올라와 있는 프로세스의 정보(PID)와 페이지 번호(논리공간 순번)를 함께 기록하여 프로세스 간 동일 프레임이 사상하는 충돌을 방지한다. 결국, 그냥 페이지 테이블과는 달리 역 페이지 테이블은 페이지 테이블에 프로세스 정보를 포함시킴으로서 프로세스별 페이지 테이블을 만들지 않는다는 것으로 볼 수 있다. 결과적으로 시스템 내에는 하나의 페이지 테이블만 존재 하게 되어 적은 용량만을 요구하게 된다.
• 이러한 역페이지 테이블의 문제점은 주소변환이 될 때마다 페이지 테이블을 한 번씩 탐색해야 하므로 시간이 소모된다는 것이다. 하지만 여기에 해쉬 테이블을 추가로 사용해 탐색 개수를 줄일 수 있다. 단, 이 경우에도 해쉬 테이블 접근으로 인해 메모리 접근 횟수가 증가하게 된다. 하지만 그럼에도 주소변환을 위해 평균적으로 테이블 크기의 반에 해당하는 탐색 오버헤드를 감소시킬 수 있다는 장점이 있다.
• PID와 페이지 번호를 이용해 해쉬 값을 구한 다음, 그 값을 인덱스로 역페이지 테이블에 접근한다. 각 항목에는 페이지 번호와 PID가 수록되어 있어 현재 주소변환을 하고자하는 프로세스의 프레임 번호인지 체크할 수 있다. 일치한다면 해당 프레임번호를 활용하고, 일치하지 않으면 체인 포인터를 활용해 따라가면서 매치를 시도한다. 여기서 프레임번호는 역페이지 테이블이기 때문에 따로 저장되어 있지 않고 테이블의 인덱스가 프레임번호가 된다.