Background
프로그램 전체를 메모리에 올린다고 하더라도 대부분의 프로세스는 할당된 메모리의 일부분만 사용한다. 에러 핸들링 코드나 잘 사용하지 않는 루틴들도 프로그램에 포함되어 있기 때문이다. 그렇기에 사용되는 일부분만 메모리에 올리고 남은 메모리를 다른 프로그램들이 사용할 수 있도록 하는 가상 메모리(virtual memory) 개념이 등장했다.
가상 메모리는 사용자와 논리적 주소를 물리적으로 분리하여 사용자가 메인 메모리 용량을 초과한 프로세스에 주소를 지정해서 메모리를 제한 없이 사용할 수 있도록 한다. 이로써 얻는 이익은 물리적 메모리의 한계를 극복하고, 동시에 더 많은 프로그램을 적재시켜 CPU 이용률과 처리량을 높인다. 또한 프로세스에 할당된 메모리의 크기가 작아지므로 적재하거나 스왑하는 데 소요되는 시간이 적게 걸린다. 프로그래머의 입장에는 프로그램을 위한 큰 가상의 메모리를 가진 것처럼 보인다.
Demand Paging
요구 페이징(demand paging)은 특정 페이지가 필요할 때 그 페이지를 메모리에 올린다. 페이지가 메모리에 현재 존재하는지를 나타내기 위해 페이지 테이블 엔트리마다 valid bit를 둔다. valid bit가 1이면 페이지가 메모리에 존재하고, 0이라면 존재하지 않는다. 페이지 테이블의 크기는 요구 페이징을 사용하더라도 이전과 같고, 단지 valid bit만 추가되었을 뿐이다.
스와핑과 요구 페이징이 메인 메모리의 용량을 극복하는 방법으로 사용된다는 점에서 비슷하지만 차이점이 존재한다. 스와핑은 메모리와 스왑 영역인 backing store 사이에서 프로세스 단위로 스왑 인, 스왑 아웃한다. 반면에 요구 페이징은 discontiguous allocation 중에서도 fixed partition에서 사용되는 기법이다. 프로세스를 고정된 크기인 페이지로 자르고, 필요에 따라 메모리와 backing store 사이에서 페이지 인(page-in), 페이지 아웃(page-out)한다.
Page Fault
참조하고자 하는 페이지가 메모리에 있다면 이전과 같이 페이지 테이블을 참고해 메모리에 접근한다. 하지만 그렇지 않다면 페이지 부재(page fault)로 trap이 발생한다.
페이지 부재 처리 과정
1. CPU가 참조하고자 하는 페이지가 메모리에 있는지 페이지 테이블을 보고 판단한다.
2. 페이지 테이블이 없다면 OS에 trap을 발생시킨다.
3. OS는 backing store에 있는 해당 페이지를 메모리에서 빈 프레임을 찾아 올린다.
4. 페이지 테이블을 수정한다.
5. 실행을 재개한다.
Copy-on-Write
쓰기 복사(copy-on-write)는 부모와 자식 프로세스들이 초기에 같은 페이지를 공유하는 것이다. 여러 프로세스가 동일한 페이지를 사용할 때 별도의 복사본을 만들지 않고 포인터로 공유 페이지를 가리킨다. 임의의 프로세스가 공유 페이지를 수정할 때에만 페이지의 복사본을 만든다.
Page Replacement
페이지 부재가 발생해 빈 프레임에 페이지를 넣으려고 하지만 더 이상 빈 프레임이 없을 수도 있다. 이럴 때는 희생 프레임(victim frame)을 골라서 페이지 아웃하고 새 페이지를 페이지 인한다. 이를 페이지 대치(page replacement)라고 한다. 희생 프레임을 고르는 기준에 따라 여러 알고리즘이 있는데 궁극적으로 페이지 부재를 가장 적게 내는 것이 목표다.
디스크와 메모리 사이에서 페이지를 전송하는 시간을 줄이기 위해서 dirty bit을 사용한다. 페이지가 메인 메모리에 올라온 이후로 수정되었을 경우에만 dirty bit를 1로 표시한다. 그리고 페이지 아웃 시 dirty bit가 1인 경우에만 페이지를 디스크에 쓴다.
페이지 대치 과정
1. 디스크에서 메모리에 올릴 페이지의 위치를 찾는다.
2. 메인 메모리에 빈 프레임을 찾는다.
2-1. 빈 프레임이 있으면 그것을 사용한다.
2-2. 빈 프레임이 없다면 페이지 대치 알고리즘을 사용해 희생 프레임을 선정하여 페이지 아웃한다. 희생 프레임의 dirty bit가 1이라면 디스크에 써준다.
3. 페이지를 페이지 인하고 페이지 테이블을 수정한다.
4. 실행이 중단되었던 시점부터 재개한다.
FIFO Algorithm
큐를 사용해 가장 오래된 페이지를 희생 프레임으로 선정한다.
Optimal Algorithm
긴 시간 동안 사용되지 않을 페이지를 희생 프레임으로 선정한다. 하지만 이것을 알기가 어렵기 때문에 다른 알고리즘들의 성능을 비교할 때 사용한다.
LRU Algorithm
참조된 시간이 가장 오래된 페이지를 희생 프레임으로 선정한다. Optimal alogithm이 미래에 기반한 결정을 내린다면 LRU algorithm은 과거에 기반한 결정을 내린다. 메모리를 참조하는 데 지역성(locality) 특성이 있기 때문에 가능한 알고리즘이다.
하드웨어적인 지원
1. Counter: 페이지 테이블 엔트리 마다 카운터를 두고 페이지가 참조될 때마다 시간을 저장한다.
2. Stack: 페이지 번호들을 스택에 담아두고 페이지가 참조되면 해당 페이지를 top으로 이동시킨다.
3. Reference bit: 초기값은 0이며, 페이지가 참조되면 1로 바꾼다.
Second Chance Algorithm
FIFO algorithm에 reference bit를 추가한 것이다. 희생 프레임이 될 페이지로 reference bit가 0인 가장 첫번째 페이지를 선정한다. 만약 reference bit가 1이라면 0으로 바꾸고 해당 페이지를 그대로 두고 다른 페이지를 찾는다. 즉, 최근에 참조되었다면 메모리에 살아남을 수 있는 기회를 한번 주는거다.
Counting Algorithm
페이지 테이블 엔트리에 페이지가 참조되는 수를 기록한다. 어떤 페이지를 희생 프레임으로 선정할 것인지에 따라 LFU algorithm과 MFU algorithm으로 나뉜다.
