이전 게시글에서 각 페이지는 메모리 보호를 위해 보호 비트와 유효-무효 비트를 활용한다고 밝혔다. 만일 유효-무효 비트가 0인경우 해당 페이지는 프레임과 매핑되어있지 않거나, 스왑 영역으로 내려가있다는 의미이다. 이러한 상황에서 CPU가 해당 페이지를 참조하려한다면 MMU 가 페이지 폴트 트랩을 발생시킨다.

페이지 교체 알고리즘

LRU 알고리즘

Least Recently Used 의 줄임말로, 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다.

LFU 알고리즘

Least Frequently Used 의 줄임말로, 가장 적게 참조된 페이지를 교체하는 알고리즘이다. 참조 기록을 저장해야하기 때문에 관리 오버헤드가 발생한다. 또한 시간에 따른 참조 경향을 확인할 수 없기때문에 이로인한 비효율적인 상황이 발생할 수 있다.

Clock 알고리즘(Second Chance / NUR)

대부분의 시스템에서는 Clock 알고리즘을 채택한다. Clock 알고리즘은 LRU 알고리즘과 마찬가지로 오랫동안 참조되지 않은 페이지를 교체한다는 원칙을 따른다. 하지만 LRU 알고리즘과는 다르게 가장 오랫동안 참조되지 않은 페이지를 퇴출시킨다는 보장을 하지 않는다.

페이지를 순차적으로 탐색하며 참조 비트를 확인하고 값이 1인경우 0으로 바꾸고 지나가되, 값이 0이라면 해당 페이지를 교체한다. 이 알고리즘은 하드웨어의 지원을 받기때문에 속도가 빠르다. 그로인해 많은 시스템에서는 Clock 알고리즘을 페이지 교체 알고리즘으로 선택한다.

페이지 교체 방식

전역 교체 방식

물리 메모리의 모든 프레임이 교체대상이 되는 방식이다. 한 프로세스는 종료된 프로세스가 사용하던 프레임에서 페이지를 퇴출시키고 자신의 페이지를 매핑하는것이 가능하다.

지역 교체 방식

현재 사용되는 프로세스가 매핑된 프레임이 교체대상이 되는 방식이다. 이는 사용중인 프로세스들의 페이지에 미리 프레임이 할당되어 있음을 가정한 경우이다.

스래싱

다중 프로그래밍 환경이 가능한 현재의 운영체제에서 MPD 라는 척도가 있다. 이는 동시에 메모리에 올라간 프롯세의 수를 의미한다. MPD 가 너무 적으면 CPU 이용률이 낮아진다. 프로세스의 수가 적기 때문에 모든 프로세스가 I/O 작업에 들어가고, 이로 인해 준비 큐가 비는 현상이 발생하는 것이다.

CPU 이용률이 감소하면 CPU는 프로세스를 더 많이 적재할 것을 명령한다. 하지만 MPD가 너무 높으면 각 프로세스에게 실행되기 충분할 만큼의 메모리를 제공할 수 없다. 게다가 부족한 메모리로 인해 프로세스에서 페이지 폴트 인터럽트가 터져나오면서 CPU는 인터럽트를 처리하느라 프로세스를 실행할 시간이 없어지고 더욱 낮은 CPU 이용률이 나온다. 이렇게 되면 CPU는 프로세스를 더 많이 적재할 것을 명령하고, 악순환이 발생한다.

워킹셋 알고리즘

첫번째로 워킹셋 알고리즘을 통해 스래싱을 예방할 수 있다. 워킹셋이란 특정 시점에 프로세스가 자주 참조하는 페이지들의 집합을 의미한다. 워킹셋 알고리즘은 모든 워킹셋이 메모리에 적재될 정도의 공간이 있는 경우에만 프로세스에 메모리를 할당한다. 워킹셋 알고리즘은 워킹셋 윈도우라는 변수를 사용한다.

현재 시간이 T 이고, 워킹셋 윈도우의 크기가 D 라면, T-D 시점부터 T 시점까지 참조된 서로 다른 페이지의 집합이 워킹셋이된다. 워킹셋의 크기가 너무 크면 MPD가 낮아져 CPU 이용률이 낮아질 것이고, 워킹셋의 크기가 너무 작다면 수용할 수 있는 페이지의 수가 너무 작아져 빈번한 페이지 폴트를 발생시킬 것이다.

페이지 부재 빈도 알고리즘

다음으로 페이지 부재 빈도 알고리즘을 통해 스래싱을 예방할 수 있다. 페이지 폴트 발생률의 상한선과 하한선을 정하여 하한선 밑으로 내려가면 MPD를 증가시키고, 상한선 위로 올라가면 스와핑을 통해 MPD를 감소시키는 알고리즘이다.