페이지 교체 알고리즘이란?
운영체제에서는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 일부의 프로그램만 주기억장치에 할당하여 사용한다. 이를 가상메모리 기법이라한다.
페이징 기법으로 메모리를 관리하는 운영체제에서 주기억장치에 할당되지 않았을때, 어떤 페이지 프레임을 선택하고 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라 한다.
※ 페이지 : 가상 메모리를 일정한 크기로 나눈 블록
※ 프레임 : 물리 메모리를 일정한 크기로 나눈 블록
페이지 교체 알고리즘의 종류
- OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
- FIFO - First In First Out : 가장 먼저 사용된 페이지 교체
- LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
- LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체
- MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체
1. OPT(Optimal)
1) 가장 이상적인 알고리즘
2) 앞으로 사용될 페이지 중 가장 늦게 사용될 페이지 교체
3) 뒤에 사용될 페이지 내용들을 알아야하기 때문에 사실상 불가능함.
2. FIFO(First In First Out)
1) 메모리에 가장 먼저 할당된 페이지를 먼저 내보낸다.
2) 구현하기 가장 간단한 알고리즘
3) 메모리에 할당된 시간을 저장하거나 올라온 순서를 큐에 저장
3. LRU(Least Recently Used)
1) 사용된 시간을 저장하며, 사용된 시간을 기준으로 가장 오랫동안 사용되지 않은 페이지 교체
2) 가장 오래 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 높다는 가정에 만든 알고리즘
3) 큐로 구현 가능 (페이지 존재 시, 삭제 후 다시 offer. 교체가 필요하다면 큐 poll 후 교체
4) 프로세스가 주기억장치에 접근할 때마다 시간을 관리해야하기 떄문에 막대한 오버헤드 발생.
4. LFU(Least Frequently Use)
1) 페이지의 참조 횟수로 교체페이지 결정
2) LRU는 단순 시간만을 참고하지만 LFU는 횟수를 통해 장기적으로 사용 여부 판단하여 고려
3) 최근 할당된 페이지가 교체될 수도 있으며, 구현이 어렵다.
5. MFU(Most Frequently Use)
1) LFU와 반대로 많이 참조된 페이지 교체
2) 오히려 많이 사용된 페이지가 앞으로 안쓰인다는 가정하의 알고리즘
LFU, MFU는 실제 사용하지 않는다.
1) 구현에 상당한 비용이 발생
2) 완벽한 구현이 어렵다.
