Demand Paging(요구페이징)
필요한 프로그램의 부분만 메모리에 적재하는 방법으로 가상 메모리 시스템에서 많이 사용된다.
요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행 과정에서 실제로 필요해질 때 적재된다.
특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재하며, 한번도 접근되지 않은 페이지는 물리적 메모리에 적재되지 않는다.
이를 통해 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는데 들었던 입출력 오버헤드가 감소하며 응답시간이 단축된다.
Page fault (페이지 부재) : CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않은 경우.
페이지 교체 알고리즘
페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다.
이 때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있는데 이 경우에 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내고 메모리에 빈 공간을 확보하는 작업이 필요하다.
이를 페이지 교체라고 하며 페이지 교체를 할 때 어떤 프레임에 있는 페이지를 쫓아낼 것이지 결정하는 알고리즘이 페이지 교체 알고리즘이다.
페이지 부재율을 최소화하는 것이 페이지 교체 알고리즘의 목표이다.
FIFO(First in First out)
메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
가장 간단한 방법으로 초기화 코드에서 적절한 방법이다.
페이지의 향후 참조 가능성을 고려하지 않고 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에 비효율적인 상황이 발생할 수 있으며 빌레이디의 모순현상이 발생할 수 있다는 단점이 존재한다.
- 빌레이디의 모순 : 페이지 프레임 수가 많으면 페이지 부재수가 줄어드는 것이 일반적이지만 페이지 프레임 수를 증가시켰음에도 페이지 부재가 더 많이 일어나는 현상
OPT(Optimal Page Replacement)
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법
미래에 어떤 페이지가 어떠한 순서로 참조될 지 미리 알고 있다는 전제하에 알고리즘을 운영하므로 현실적 구현이 어려우며 페이지 부재율이 가장 낮은 효율적인 알고리즘이다.
LRU(Least Recently Used)
최근에 사용하지 않은 페이지를 먼저 내보내는 알고리즘
최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다
OPT의 경우 미래예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘이다.
OPT보다는 페이지 부재율이 높지만 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다.
LRU에서 교체 페이지 선정 방법
스택을 사용하여 참조된 페이지 번호를 스택에 쌓는다.
페이지가 접근될 때 마다 스택에 쌓으면 스택의 바닥에는 오랫동안 접근되지 않은 페이지가 존재하게 되어 페이지를 교체할 때 스택의 bottom만 확인한다.
LFU(Least Frequently Used)
페이지의 참조 횟수로 교체할 페이지를 결정하는 방법
물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 내쫓고 그 자리에 새로 참조될 페이지를 적재한다.
시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 구현이 복잡하다.
* LRU, LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야 하므로 알고리즘의 운영에 오버헤드가 발생한다.
NRU(Not Recently Used)
하드웨어적인 지원을 받아 LRU와 LFU알고리즘에서 발생한 시간적인 오버헤드를 줄인 방식
LRU를 근사시킨 알고리즘이라고 하며 오랫동안 사용하지 않은 페이지 중 하나를 교체한다.
최근에 참조되지 않은 페이지를 교체 대상으로 선정하는 측면에서 LRU와 비슷하지만 교체되는 페이지의 참조 시점이 가장 오래됐다는 것을 보장하지 못한다.
참조비트(Reference Bit)와 변형비트(Modified Bit, Dirty Bit)를 사용한다.
- 참조 비트 : 페이지가 참조될 때는 1, 참조되지 않았을 때는 0으로 지정한다.
- 변형 비트 : 페이지 내용이 변경되었을 때 1로 지정한다.
다음과 같이 참조비트와 변형비트의 값에 따라 교체될 페이지의 순서가 결정된다.
| 참조비트 | 변형비트 | 교체순서 |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 2 |
| 1 | 0 | 3 |
| 1 | 1 | 4 |
SCR(Second Chance Replacement)
가장 오랫동안 메모리에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지한 것으로 FIFO기법의 단점을 보완하는 기법
각 페이지마다 참조 비트를 두고 FIFO기법을 이용하여 페이지 교체 수행 한다.
- 참조비트가 0일 경우
페이지 교체 - 참조비트가 1일 경우
참조비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백시켜 다음 순서를 기다리게 한다.
메모리에 올라와있는 페이지들을 원형큐로 구성하고 포인터 한 개를 둔다.
포인터가 첫번째로 만나는 참조비트가 0인 페이지를 교체 대상으로 선정하고, 참조비트가 1인 경우에는 0으로 바꿔주고 그냥 지나간다.
그 후 다음 한바퀴를 돌았을 때 여전히 0이면 한바퀴 도는 동안 참조하지 않았다는 의미이므로 교체 대상이 될 수 있고, 다시 1이 된다면 참조되었다는 의미이므로 교체 대상이 되지 않게 된다.
교체 대상이 되기 전에 참조비트를 검사하여 1일 경우 한번의 기회를 더 부여하기 때문에 second chance라고 한다.
