페이지 교체 알고리즘

프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재가 발생한다. 스왑 영역에서 페이지를 메모리로 가져오는데, 메모리가 꽉찬 경우 메모리에 있는 페이지를 스왑 영역으로 보내야 한다. 페이지 교체 알고리즘은 이때 스왑영역으로 보낼 페이지를 결정하는 알고리즘이다.

페이지 교체 알고리즘의 성능 평가 기준

• 페이지 부재 횟수
• 페이지 요청 후 실제 작업에 들어갈 때까지의 평균 대기 시간
• 전체 작업에 소요되는 시간
  
• 성능이 좋은 알고리즘이더라도 계산이 많이 필요하거나 메모리를 많이 차지한다면 좋은 알고리즘이라 할 수 없음

FIFO(First In First Out)

시간상 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 보낸다.
큐로 구현한다.
시간 locality를 고려하면 가장 오래된 페이지를 선정하는 것이 맞지만, 이 경우 자주 사용되는 페이지가 쫓겨난다는 문제가 있다.

OPT(Optimal Page replacement)

앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다.
이 알고리즘은 미래의 메모리 접근 패턴을 보고 페이지를 선정하기 때문에 성능이 좋지만, 접근 패턴을 아는 것이 불가능하므로 실제로 구현할 수 없다.

페이지 부재: 9

위 그림에서 4번째로 페이지2를 요구할 때, 메모리에 있는 페이지 7, 0, 1 중에 7이 가장 늦게 사용되므로 페이지 7을 스왑영역으로 보내고 페이지2가 들어온다.

아래부터는 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하는 최적 근접 알고리즘들을 살펴본다.

LRU(Least Recently Used)

메모리에 올라온 후 가장 오래 사용되지 않은 페이지를 스왑 영역으로 옮긴다.
최근에 사용되지 않은 메모리는 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다.
메모리 접근 패턴에 따라 FIFO 알고리즘보다 느리기도 하고 빨라지기도 하지만, 일반적으로 FIFO 알고리즘보다 우수한 성능을 가진다.

페이지 부재: 12

위 그림에서 6번째로 페이지3을 요구할 때, 메모리에 있는 페이지 2, 0, 1 중에 접근한 지 가장 오래된 것은 페이지 1이므로 페이지1을 내보내고 페이지 3이 들어온다.

LFU(Least Frequently Used)

프레임에 있는 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다. 사용된 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.

NUR(Not Used Recently)

이 알고리즘은 LRU, LFU와 성능이 거의 비슷하다. 그러나 LRU, LFU에서 접근시간과 접근빈도 값을 유지하며 공간을 차지하는데, NUR은 이러한 불필요한 공간 낭비 문제를 해결한 알고리즘이다.
참조 비트와 변형 비트를 사용하여 예측한다. 메모리 공간은 총 2비트만 추가된다.

• 참조 비트: 페이지에 접근(read or execute)하면 1이 된다.
• 변형 비트: 페이지가 변경(write or append)되면 1이 된다.

모든 페이지는 (0, 0)이 초기 상태이다. 이 상태에서 접근이 발생하면 (1,0)이 되고, 이어서 변경이 일어나면 (1,1)이 된다.
메모리에서 교체할 페이지를 선정할 때 순서는 (0,0) -> (0,1) -> (1,0) -> (1,1)이다.

SCR(Second Chance Replacement, 2차 기회 페이지 교체)

FIFO 페이지 교체 알고리즘은 자주 사용하는 페이지를 고려하지 않기 때문에 성능이 좋지 않다. 이러한 단점을 개선한 FIFO 변형 알고리즘이다.
특정 페이지에 접근하여 성공할(hit) 경우 해당 페이지를 큐의 맨 뒤로 이동시켜 대상 페이지에서 제외한다. 성공한 페이지에게 기회를 한 번 더 주는 것이다.
일반적으로 성능은 LRU, LFU, NUR 보다 약간 낮고 FIFO보다 약간 높다. 또한 큐를 유지하는 비용이 크고 페이지를 맨 뒤로 이동시키는 작업이 추가되는 것이 단점이다.