페이지 교체
페이지 부재가 발생해 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이 경우에 물리적 메모리에 비어있는 프레임이 없을 수가 있어 다른 페이지 중 하나를 디스크로 내보내야 한다. 이 때, 어떤 페이지를 내보내고 새로운 페이지를 추가할지 결정하는 알고리즘을 페이지 교체 알고리즘 이라고 한다.
- 페이지 교체 알고리즘의 목표: 페이지 부재율 최소화
- 페이지 교체 알고리즘의 평가 기준: page reference string에 대해 페이지 부재율 계산해 평가
해당 번호의 페이지가 메모리에 이미 올라와 있다면 hit, 메모리에 없다면 부재가 발생했다고 말한다.
1. 최적 페이지 교체
= optimal algorithm, MIN, OPT
페이지 교체 시, 가장 오랜 기간동안 사용되지 않을 페이지를 교체한다.
페이지 부재는 6번 발생한다. 하지만, 미래를 예측하는 것은 어려운 일이므로 현실성이 떨어진다.
빌레디의 오프라인 최적 알고리즘은 다른 알고리즘보다 가장 적은 페이지 부재율을 보장할 수 있다. 따라서 어떤 교체 알고리즘의 성능이 최적 알고리즘과 유사하다면, 더 이상 그 시스템을 위한 교체 알고리즘의 연구가 필요하지 않음을 말할 수 있다.
2. 선입선출 알고리즘
= FIFO
페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내보낸다. 페이지의 향후 참조 가능성을 고려하지 않고 물리적 메모리에 들어온 순서대로 내보내므로 비효율적인 상황이 발생할 수 있다.
- 가장 먼저 물리적 메모리에 들어온 페이지가 계속해서 많은 참조가 이루어진 경우
frame이 3개일때, 페이지 부재가 9번 발생한다.
frame이 4개이면 페이지 부재가 10번 발생한다.
물리적 메모리의 공간이 늘어났어도 오히려 성능은 더 나빠졌다. 위의 경우와 같이 FIFO 알고리즘에서 메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황을 Belady's anomaly라고 부른다.
3. LRU(Least Recently Used) 알고리즘
LRU는 메모리 페이지의 참조 성향 중 하나인 시간 지역성(temporal locality)를 이용한다. 시간 지역성은 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 말한다.
즉, LRU는 이 성질을 이용해 페이지 교체시 가장 오래전에 참조가 이루어진 페이지를 내보낸다.
8개의 페이지 부재가 발생한다.
- LRU를 하드웨어로 구현: 각 페이지마다 카운터를 둬 참조될때마다 카운터에 system clock을 저장한다. 페이지들을 스캔해보고 가장 오래된 clock을 가진 페이지를 교체한다.
- 문제점: 모든 페이지와 카운터들을 검색해야한다.
- LRU를 소프트웨어로 구현: double linked list로 구현, 페이지가 참조될때마다 리스트의 front로 옮긴다. 페이지 교체 방식은 리스트의 가장 맨 끝에 있는 페이지를 제거한다. 이렇게 하면 모든 페이지를 검색해보지 않아도 된다.
- 문제점: 너무 비싸다.
4. NRU(Not Recently Used) 알고리즘
= 클럭(second-chance) 알고리즘, NUR(Not Used Recently)
오랫동안 참조되지 않는 페이지 중 하나를 교체한다. 즉, 최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 것은 LRU와 유사하나 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 않는다는 점이 다르다.
이 알고리즘은 하드웨어적인 지원으로 동작하기 때문에 LRU에 비해 페이지 관리가 훨씬 빠르고 효율적이다. 그래서 대부분의 시스템에서 클럭 알고리즘을 사용한다고 한다.
교체할 페이지를 고르기 위해 페이지 프레임들의 Reference bit를 순차적으로 조사한다.
- 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅
- 한바퀴를 돌면서 참조비트가 1인 페이지는 0으로 변경 후 지나감
- 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체
페이지가 참조되면 1이 되고 한 바퀴 도는 동안에 사용되지 않으면 0이 된다. 또 다시 한바퀴를 도는 동안 사용되지 않은 페이지는 참조되지 않았다는 뜻이므로 해당 페이지를 교체 대상 페이지로 선정한다.
대상 페이지 선정 순서
참조비트, 변경 비트
참조 비트를 먼저 우선적으로 고려한다.
(0, 0) -> (0, 1) -> (1, 0) -> (1, 1)
만약 모든 페이지가 (1, 1)이되면 모든 페이지 비트를 (0, 0)으로 리셋시킨다.
시곗바늘이 한바퀴를 도는데 소요되는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄일 수 있도록 설계되어 2차 기회 알고리즘이라고도 부른다.
5. LFU(Least Frequently Used) 알고리즘
LFU는 페이지의 참조 횟수로 교체시킬 페이지를 결정한다. 즉, 메모리 내에 있는 페이지 중, 과거에 참조 횟수가 가장 적었던 페이지를 내보내고 그 자리에 새로 참조될 페이지를 적재시킨다. 최저 참조 횟수가 같은 페이지가 여러개라면 상대적으로 더 오래전에 참조된 페이지 하나를 선정해 내보낸다.
- Incache-LFU: 메모리에 적재될 때부터 참조 횟수를 세는 방식
- Perfect-LFU: 메모리에 적재 여부와 상관없이 페이지의 과거 총 참조 횟수를 세는 방식
- 장점: 참조 횟수를 정확히 반영 가능
- 단점: 메모리에서 쫓겨난 페이지의 참조 기록까지 모두 보관해야 하므로 오버헤드가 상대적으로 크다.
Reference string: 1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5
page frame: 4
현재 시각에 5번 페이지가 참조되었다고 하면, <1, 2, 3, 4> 번 페이지 중 하나를 내보내야 한다.
LRU 알고리즘은 가장 오래전에 참조된 1번 페이지를 교체 대상으로 선정할 것이다. 하지만 1번 페이지는 막 참조 시점이 다른 페이지들에 비해 오래되긴 했지만 참조 횟수가 가장 많았다. LRU는 이러한 정보를 인지하지 못한다.
그에 반해, LFU는 참조 횟수가 가장 적은 4번 페이지를 교체 대상으로 선정한다. 하지만 4번 페이지는 가장 최근에 참조된 페이지로 앞으로 참조가 더 될 가능성이 있지만 LFU는 이 사실을 인지하지 못한다.
