지난 시간 페이징 방식에 기반한 가상 메모리 기술인 디멘드 페이징에 대하여 학습하였다. 해당 방법론은 프로세스 크기에 비례하여 페이지 테이블 또한 커지는 문제가 발생하였는데, 이를 해결할 방법을 학습하고자 한다.
다계층 페이지 테이블
페이지 테이블 크기 문제를 해결하는 방법
4Kbyte 페이지에 4바이트 엔트리가 1,024개 담긴다. 코드가 많아지면 그에 따라 페이지 테이블을 담고 있는 엔트리도 증가하게 되고, 하나의 페이지에 담기지 않게 된다. 이 많은 양의 엔트리들을 페이지에 논리적으로 분배하기 위한 방법이 존재한다.
첫 번째는 멀티 레벨 페이지 테이블로, 계층적 특성(Hierarchical)을 가진다. 두 번째 방법으로는 Inverted 페이지 테이블이 있는데 성능 이슈로 요즘은 잘 사용하지 않는다.
멀티 레벨 페이지 테이블
각 페이지 인덱스를 담고 있는 데이터 구조인 페이지테이블이 일반적으로 분산되어 있기 때문에, 이를 논리적으로 연결하기 위해 Outer Page를 이용해 계층을 나누는 방법이다. 주소 공간은 Outer Page(10bit) - User Page Table(10bit) - Offset(12bit)로 구성된다. (32bit Address 컴퓨터 기준)
위 도식을 통해 멀티 레벨 페이지 테이블을 정리해보자. 최우단 Frame #41, #49,..., #3700이 코드, 데이터, 스택으로 이루어진 유저 컨텍스트 구역이다. 프레임 번호로 알 수 있듯 메로리 여기저기에 흩어져 있는 상태이다. 중간의 User Page Table에서 0번부터 1023번까지의 연속적으로 프레임 위치를 정리한 것을 확인할 수 있다. 이 페이지 테이블 정보들 또한 흩어져 있기 때문에, 이를 위한 인덱싱을 하는 것이 Outer Page Table이 된다.
TLB
디멘드 페이징 방식의 다계층 페이지 테이블을 읽는 데 걸리는 시간을 줄이는 기술이다. 계층이 늘어날수록 처리 시간 또한 증가하기 때문에 최근에 접근한 프로세스 페이지의 프레임 번호를 캐시 형식으로 저장하는 방식을 이용하였다. Associative memory라고도 한다.
TLB에서는 최근에 액세스한 프로세스의 페이지 번호(테이블 엔트리의 인덱스 값)와, 그 페이지에 해당하는 프레임 번호를 같이 기록한다. 또한 추가적으로 P / T 비트의 여부, P 비트인 경우 1인지 0인지의 제어 정보를 담고 있다. 연산이 병렬로 처리된다는 특징을 갖고 있다.
TLB 캐시 내부에 원하는 정보가 들어 있는 경우 TLB-hit, 들어 있지 않은 경우 TLB-miss라고 한다. 메인 메모리에 없는 페이지를 접근하려 하는 경우 P비트 값이 0이 되고, Page fault라고 하는 인터럽트 트랩이 발샐하게 된다. 그 후 보조기억장치에 접근하여 페이지를 불러온다. 인터럽트이기 때문에, 커널로의 모드 체인지가 발생하게 된다.
페이지 교체 작업
가상 메모리는 보조 기억 장치를 메인 메모리처럼 이용하는 기술. 디멘드 페이징 방식을 통해 필요한 페이지를 보조 기억 장치의 가상 메모리 공간에서 메인 메모리로 그때그때 가져옴. 이 때 메인 메모리에 공간이 없는 경우 기존 페이지를 제거하고 새로운 페이지를 로드하는 페이지 교체가 이루어짐.
Replacement Policy
메인메모리에서 대체시킬 페이지를 선정하는 기준으로, 운영체제 내부에서 자체적으로 이루어진다.
- FIFO Policy : 페이지 선입선출 방식의 대체 알고리즘
- Optimal Policy : 앞으로 사용될 패턴을 미리 살펴본 후, 빈도가 적은 페이지를 방출. 굉장히 이상적이지만, 실제로 적용하여 사용하는 데 무리가 있음.
- Least Recently Used Policy (LRU) : 과거의 패턴을 바탕으로 미래를 예측하는 대체 알고리즘. 현실적인 Optimal Policy라고 볼 수 있다. 그러나 페이지별 시간 카운터 변수가 추가로 필요하기 때문에 오버헤드 문제를 야기한다.
- Clock Policy : 도넛 형태의 테이블을 돌려가며 한 바퀴 처리될 때까지 사용되지 않은 페이지를 방출하는 알고리즘. use 비트가 0인 경우 최근에 사용되지 않은 페이지이다.
요청한 페이지가 현재 물리 메모리에 존재하지 않는 경우를 페이지 폴트 (Page Fault)라고 함. 이 경우 운영체제가 디스크에서 요청된 페이지를 메모리로 로드
