페이지 교체 알고리즘
페이지 교체 알고리즘은 컴퓨터 운영 체제에서 메모리 관리 기법의 일종으로, 프로세스가 샐행될 때 필요한 페이지를 메모리에 적재하기 위해 어떤 페이지를 제거할지 결정하는 알고리즘입니다. 페이지 교체 알고리즘은 주로 가상 메모리를 사용하는 시스템입니다.
페이지 교체 알고리즘 종류
- OPT : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
- FIFO : First In First Out
- LRU : Least Recently Used 가장 오랫동안 사용되지 않은 페이지 교체
- MFU : Most Frequently used : 참조 횟수가 가장 많은 페이지 교체
- NUR : Not Used Recently : 최근에 사용하지 않은 페이지 교체
OPT (Optimal Page Replacement) - 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
가장 오랫동안 사용되지 않을 페이지를 교체하는 방식입니다. 이론적으로 최적의 성능을 제공하지만, 미래의 페이지 참조를 예측해야 하므로 실제 구현이 불가능합니다.
- 장점 : 이론적으로 가장 적은 페이지 폴트를 발생시킨다.
- 단점 : 실제 시스템에 적용할 수 없다
FIFO (First in First out) - 가장 먼저 들어온 페이지를 교체
FIFO 알고리즘은 가장 먼저 메모리에 적재된 페이지를 가장 먼저 교체하는 방식입니다. 큐를 사용하여 페이지를 관리하며, 큐의 앞부분에 있는 페이지가 교체됩니다.
- 장점 : 구현이 간단하다.
- 단점 : 가장 오랫동안 사용되지 않은 페이지를 교체할 수도 있어 비효율적이다.
LRU (Least Recently Used) - 가장 오랫동안 사용하지 않은 페이지를 교체
LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식입니다. 최근에 사용된 페이지는 계속 메모리를 유지하려고 합니다.
- 장점 : 자주 사용되는 페이지가 메모리에 남아 있게 되어 성능이 좋다.
- 단점 : 구현이 복잡하며, 최근 사용된 시간을 기록하고 관리해야 한다.
LFU (Least Frequently Used) - 참조 횟수가 가장 낮은 페이지를 교체
LFU 알고리즘은 사용 빈도가 가장 적은 페이지를 교체하는 방식입니다. 각 페이지 참조 횟수를 기록하여 가장 적게 참조된 페이지를 교체합니다.
- 장점 : 자주 사용되는 페이지를 메모리에 남겨두어 효율적이다.
- 단점 : 최근에 집중적으로 사용된 페이지가 오래된 페이지보다 먼저 교체될 수 있다.
MFU (Most Frequently Used) - 참조 횟수가 가장 많은 페이지 교체
MFU 알고리즘은 LFU의 반대 개념으로, 사용 빈도가 가장 많은 페이지를 교체하는 방식입니다. 이 알고리즘은 최근에 적게 사용된 페이지가 앞으로도 적게 사용될 것이라는 가정을 바탕으로 합니다.
- 장점 : 사용 패턴이 일정한 경우 효율적일 수 있다.
- 단점 : 비효율적일 수 있으며, 실제로 많이 사용되지 않는다.
NUR (Not Used Recently, Not Recently Used) - 클럭 알고리즘
LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 메모리 공간 낭비 문제를 해결한 페이지 교체 알고리즘이다. 이 알고리즘은 각 페이지에 대해 두 구지 비트를 유지합니다.
- 참조 비트 : 페이지가 최근에 참조되었는지를 나타냅니다.
- 변경 비트 : 페이지가 수정되었는지를 나타냅니다.
NUR 알고리즘의 작동 방식
1. 참조 비트와 변경 비트 설정
1. 참조 비트는 CPU가 페이지를 참조할 때마다 설정됩니다.
2. 변경 비트는 페이지가 수정되었을 때 설정됩니다.
2. 비트 초기화
1. 일정 시간 간격으로 모든 페이지의 참조 비트를 0으로 재설정합니다.
2. 변경 비트는 페이지가 실제로 디스크에 기록될 때만 0으로 재설정됩니다.
3. 페이지 교체 시기
1. 페이지 프레임이 모두 사용 중일 때 페이지 폴트가 발생되면, 교체할 페이지를 선택해야 합니다.
2. 모든 페이지를 네 가지 카테고리로 분류합니다.
1. 참조 비트 0, 변경 비트 0 : 최근에 참조되지 않았고 수정되지 않은 페이지.
2. 참조 비트 0, 변경 비트 1 : 최근에 참조되지 않았고, 수정된 페이지.
3. 참조 비트 1, 변경 비트 0 : 최근에 참조되었고 수정되지 않은 페이지.
4. 참조 비트 1, 변경 비트 1 : 최근에 참조되었고 수정된 페이지
4. 페이지 교체
1. 위의 네 가지 카테고리 중 우선순위에 따라 교체할 페이지를 선택합니다. 가장 우선적으로 교체되는 페이지는 (참조 비트 0, 변경 비트 0)인 페이지 입니다. 만약 이런 페이지가 없다면 (참조 비트 0, 변경 비트 1)인 페이지를 선택하고, 그 다음 (참조 비트 1, 변경 비트 0) 그리고 마지막으로 (참조 비트 1, 변경 비트 1) 순으로 선택합니다.
2. 선택된 페이지는 메모리에서 제거되고, 새로운 페이지가 그 자리에 적재됩니다.
- 장점 :
- 구현이 비교적 간단하다.
- 페이지 교체를 위해 모든 페이지를 순차적으로 검사할 필요가 없습니다.
- 참조 비트와 변경 비트를 이용하여 효율적인 페이지 교체 결정을 내릴 수 있습니다. - 단점 :
- 참조 비트와 변경 비트를 주기적으로 초기화해야 하므로 약간의 오버헤드가 발생할 수 있습니다.
- LRU(Least Recently Used) 알고리즘처럼 정확하게 최근 사용 패턴을 반영하지 못 합니다.
[참고]
