[Operating System] Page Replacement

 

 

 

Demand Paging 방식에서는 필요한 Page를 동적으로 메모리로 가져온다. 

메모리에 빈 자리가 없다면 메모리에 있는 Page를 보조기억장치로 보내고 다른 Page를 메모리로 가져오는데, 이 작업을 Page Replacement 라고 부른다.

 

Page Replacement에서는 메모리에서 Swap Out 할 Page를 결정하는 작업이 가장 중요하다. 

이 작업은 운영체제가 알아서 결정하는데, 보통 가까운 미래에 사용될 것 같은 Page는 그대로 두고 나중에 사용될 것 같은 메모리는 보조기억장치로 옮기는 방식을 사용한다.

 

 

 

 

Reference String은 프로그램이 실행되면서 접근하는 주소들의 Page번호만 시간 순서대로 나열한 부분이다.

 

맨 처음 7번 Page를 Access 해야 하는데 메모리에는 아무 것도 올라오지 않았다. 

Page Fault가 발생하고, 이후 0 1 2 Page를 Access 할 때도 역시 Page Fault가 발생한다. 

 

2번 Page를 가져오려 하는데, 이미 메모리가 꽉 차서 가져올 수 없다. 

이 때 Replacement 알고리즘이 수행된다.

 

FIFO 방식을 사용할 때는 가장 먼저 들어온 Page를 먼저 Swap Out 하고, 예시에서는 Page Fault가 15번 발생한다.

 

Page Fault는 프로세스를 중단시키고 블럭 상태로 바꾸고.. Replacement 알고리즘을 실행하고 Disk I/O가 발생하는 오버헤드가 매우 큰 작업이다. 

Page Fault를 최대한 줄여보자. 

 

 

 

 

FIFO 대신 Optimal Policy방식을 사용해보자. 

Replace 실행 시 앞으로 들어올 Reference String을 확인하고 가장 나중에 사용될 Page를 줄이는 방식으로 동작한다.

 

Page Fault도 9번밖에 발생하지 않는 방식이지만, 실제로 사용하기에는 문제가 있다. 

 

미래에 어떤 Page에 접근할지에 대한 정보가 있어야 사용할 수 있는데, 과거에 해당 프로그램을 실행해서 그 결과를 기록해 뒀을 때는 미래에 어떤 Page에 접근할지를 알 수 있지만, 프로그램을 처음 실행할 때는 미래에 어떤 Page에 접근할 지 전혀 알 수 없다. 

 

 

 

 

과거를 통해 미래를 예측하는 Least Recently Used 방식을 사용해보자. (프로그램의 Locality 기반)

Page를 참조 할 때 마다 그 Page를 기록해두고, Replace 할 때 최근에 접근한 Page는 유지하고 제일 오래 전에 접근한 Page를 Swap Out 한다. 

 

Page Fault는 9번 발생했고, FIFO보다는 적고 Optimal보다는 많다.

 

LRU 방식이 성능은 좋지만, 오버헤드가 크다. 

Page를 참조 할 때 마다 그 시간과 Page 번호를 매번 기록해 둬야 하는데, 이 작업이 가볍지가 않다. 

따라서 운영체제 개발자들은 LRU를 구현할 때 좀 더 간단한 방식인 Clock Policy를 사용한다. 

 

 

 

 

 

Clock Policy는 LRU를 흉내 내는 방식이다.

 

각 Page에는 Page 번호와 Use Bit로 최근에 해당 Page에 접근했는지 여부를 저장한다. (접근한 적이 있으면 1)

Use Bit가 1이면 해당 Page의 Use Bit를 0으로 설정하고 넘어간다. 

Use Bit가 0인 Page를 만나면 해당 Page를 Swap Out 하고 보조기억장치로부터 새로운 Page를 가져온다. 

 

시계 방향으로 순회하면서, Next FIt 알고리즘처럼 직전에 확인한 Page의 다음 Page를 검사한다. 

 

 

 

 

 

성능을 비교해보면 FIFO - CLOCK - LRU - OPT 순서대로 나열된다. 

메모리의 크기가 커질수록 Page Fault수도 줄어들고, 메모리가 너무 커져서 모든 Page가 메모리에 있으면 Page Fault가 0으로 수렴한다.

 

컴퓨터는 여러 프로세스를 실행시켜야 하고.. 하나의 프로세스에 메모리를 많이 할당할수록 한 번에 다룰 수 있는 프로세스가 줄어든다. 

따라서 운영체제는 적당한 메모리를 프로세스마다 할당하게 된다. 

 

 

 

 

 

Clock Policy의 개선안으로 Enhanced Clock Policy가 도입됐다.

Page Fault를 당하는 정도는 같지만, 전반적으로 시스템의 성능을 끌어올린다. 

 

기존 Clock Policy는 Use Bit를 바탕으로 Swap Out 대상을 결정하는데, Enhanced Clock Policy 에서는 Use Bit와 Modify Bit를 사용해 Swap Out 대상을 결정한다. 

 

00 01 10 11 네 가지 조합을 보고, 나열한 순서대로 우선순위가 설정된다. 

수정이 안 된 페이지는 Swap Out 하더라도 디스크에 Write 하지 않는다. 그러니 00 은 01보다 Swap Out 우선순위가 더 높다. 

 

 

Page Fault가 발생할 확률을 p라고 두자. 

 

Effective Access Time = (1 –p) x memory access +

p x { page fault overhead + [swap page out ] + swap page in + restart overhead (instruction re-execution time + memoryaccess) }