🎪 페이지 교체 알고리즘
페이지 교체 알고리즘, Page Replacement Algorithm: 페이지 폴트 발생 시 backing store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이 때 빈 프레임이 없을 경우 희생당할 프레임을 고르는 알고리즘
- 목표: page-fault 발생 빈도 줄이기
🎪 First-in First-out 알고리즘
가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내기
- 구현 간단함
- 성능은 좋지 않음
- 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장
- Belady's Anomaly 현상 발생
- 프레임의 개수가 많아져도 페이지 폴트가 늘어나는 현상
🎪 OPT (optimal) 알고리즘
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘
- 페이지 폴트 발생이 가장 낮음
- Belady's Anomaly 현상 방지
- 프로세스가 앞으로 사용할 페이지를 미리 알아야 함
- 실제로 구현하기 거의 불가능
- 연구 목적이 대부분
🎪 LRU (Least Recently Used) 알고리즘
가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
- 최적 알고리즘과 비슷한 효과
- 성능이 좋은 편
- 많은 운영체제가 채택
- 프로세스가 주기억장치에 접근할때마다 참조된 페이지 시간을 기록해야 함 > 막대한 오버헤드
Temporal Locality 활용!
시간 지역성, Temporal locality: 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
구현: 연결리스트 큐로 구현
- 사용한 데이터를 큐에서 제거하여 맨 위로 다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터 삭제
- head에 가까울수록 최근에 사용됨. tail에 가까울 수록 오래전에 사용됨
🎪 LFU (Least Frequently Used) 알고리즘
참조횟수가 가장 적은 페이지를 교체하는 알고리즘
- 교체 대상이 여러개라면 가장 오랫동안 사용하지 않은 페이지 교체
- LRU는 직전 참조 시점만 반영하는데 반해 참조횟수를 통해 장기적 시간규모에서의 참조성향 고려 가능
- 가장 최근에 불러온 페이지가 교체될 수 있음
- 막대한 오버헤드
Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트하는 방식
Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트하는 방식
🎪 MFU (Most Frequently Used) 알고리즘
참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
🎪 SCR (Second Chance Replacement)
가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용된 페이지의 교체를 방지함
- FIFO 기법의 단점 보완
- 큐의 상단에서 꺼낸 대상의 참조 비트를 검사하여 0이면 교체 대상 선정. 1이면 0으로 바꿔 큐의 뒤에 삽입
- 만약 모든 페이지의 참조 비트가 세팅되어 있으면 큐의 첫 요소였던 페이지가 두번 검사됨 > 해당 페이지를 내쫓음
🎪 클럭 알고리즘 (Not Recently Used/Not Used Recently)
하드웨어적 자원을 통해 기존 LRU/LFU 알고리즘의 소프트웨어적인 운영 오버헤드를 줄임
- LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않음
- SCR을 원형 큐를 이용해 구현
- 페이지 프레임의 참조 비트를 조사해 참조 비트가 1인 페이지는 0으로 바꾼 후 지나가고, 0인 페이지를 찾으면 그 페이지와 교체
참고:
우당탕탕