페이지 교체 알고리즘

1. 무작위

무작위로 대상 페이지를 선정하여 스왑 영역으로 보낸다.

• 알고리즘의 성능이 좋지 않아 거의 사용되지 않는다.

2. FIFO

처음 메모리에 올라운 페이지를 스왑 영역으로 보낸다.

• FIFO 페이지 교체 알고리즘을 큐로 구현한다. 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지 이고 새로운 페이지는 항상 맨 아래 삽입된다.
• 메모리가 꽉 차면 맨위의 페이지가 스왑 영역으로 가고 새로운 페이지가 아래 남은 공간에 들어온다.

3. 최적

미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다.

• 최적 페이지 교체 알고리즘(optimal page replacement algorithm)은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다.
• 페이지 교체 시점으로부터 사용 시점까지 가장 멀리 있는 페이지를 교체 대상 페이지로 선정한다.
• 가장 늦게 사용되는 페이지 C를 스왑 영역으로 보낸다.
  
• 최적 페이지 알고리즘은 미래의 데이터를 참고로 하기 때문에 구현이 불가능하다.

4. LRU

시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다.

• 최적 근접 알고리즘 중 LRU(Least Recently Used page replacement algorithm)은 '최근 최소 사용 페이지 교체 알고리즘'이라고도 한다.
• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다.
• 사용된지 가장 오래된 페이지를 교체 대상으로 선정한다.
• 일반적으로 LRU 페이지 교체 알고리즘의 성능은 FIFO 페이지 교체 알고리즘보다 우수하고 최적 교체 알고리즘보다는 조금 떨어지는 것으로 알려져 있다.

5. LFU

사용 빈도가 적은 페이지를 스왑 영역으로 보낸다.

• 최적 근접 알고리즘 중 LFU 페이지 교체 알고리즘(Least Frequently Used page replacement algorithm)은 '최소 빈도 사용 알고리즘'이라고도 한다. LFU 페이지 교체 알고리즘은 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다.
• 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.
• FIFO 페이지 교체 알고리즘보다 성능이 우수하다.

6. NUR

최근에 사용한 적이 없는 페이지를 스왑 영역으로 보낸다.

• NUR 페이지 알고리즘(Not Used Recently page replacement algorithm)은 LRU, LFU 페이지 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘이다.
• '최근 미사용 페이지 교체 알고리즘'이라고도 불린다.
• 2비트만 추가하여 다른 알고리즘과 유사한 성능을 내고 쉽게 구현할 수 있는 장점이 있다.

7. FIFO 변형

FIFO 알고리즘을 변형하여 성능을 높인다.

• FIFO 페이지 교체 알고리즘은 메모리에 올라온 순서만 고려하고 자주 사용하는 페이지를 고려하지 않기 때문에 성능이 좋지 않다.

2차 기회 페이지 교체 알고리즘

• 2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)은 FIFO와 마찬가지로 큐를 사용하지만, 차이점은 성공한 페이지를 큐의 맨 뒤로 옮겨서 기회를 한 번 더 준다.
• LRU, LFU, NUR 페이지 교체 알고리즘보다 약간 낮고 FIFO 페이지 교체 알고리즘보다 약간 높은 것으로 알려져 있다.
• 큐의 유지비용이 높고 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가되는 것이 단점이다.
  

시계 알고리즘

• 시계 알고리즘(clock algorithm)은 2차 기회 페이지 교체 알고리즘과 유사하여 두 알고리즘을 같은 알고리즘으로 보기도 하지만 실제 구현을 서로 다르다.
  
• 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용한다. 이 포인터가 큐의 맨 바닥으로 내려가면 다음에 다시 큐의 처음을 가리키게 된다.
• 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부른다.

• 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가된다. 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경된다.
• 가리키는 페이지가 스왑 영역으로 쫓겨나면 대상 포인터를 밑으로 이동한다. - 참조 비트가 1인 페이지는 건너뜀으로써 기회를 한 번 더 주고, 메모리의 바닥에 도착하면 원형 큐처럼 다시 메모리의 상단으로 이동한다.
• 참조 비트가 1인 페이지를 건너뛸 떄는 0으로 바꿔두고 포인터가 다시 돌아오면 제외하지 않는다.