페이지 교체 알고리즘
개념
•
운영체제는 주기억장치의 용량보다 더 큰 프로그램을 실행하기 위해 가상 메모리 기법을 사용하여 프로그램의 일부만 주기억 장치에 적재하여 사용한다.
•
페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 경우 해당 페이지를 요구해야한다.
•
이후 Demand Paging 과 Page-Fault 가 발생한다.
•
만약 빈 프레임이 없을 경우, 희생 당할 프레임을 고르는 방법들을 페이지 교체 알고리즘 이라고 한다.
•
페이지 교체 알고리즘의 목적은 Page-Fault 의 비율을 줄이는 것이다.
*Page Fault : CPU가 접근하려는 페이지가 메모리에 없는 상황
*페이지 : 가상 메모리를 일정한 크기로 나눈 블록
*프레임 : 물리 메모리를 일정한 크기로 나눈 블록
페이지 교체 알고리즘 종류
FIFO (First In First Out)
•
가장 먼저 들어온 페이지 순서대로 교체하는 알고리즘
•
구현은 간단하지만 성능은 좋지않다.
•
들어온 시간을 저장하거나, 올라온 순서를 큐에 저장한다.
•
직관적으로 프레임의 수가 많아질수록 Page Fault 횟수는 감소해야 하지만 FIFO 알고리즘은 그렇지 않을 수 있다.
◦
이러한 현상을 Belady's Anomaly 라고 한다.
LRU (Least Recently Used)
•
가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
•
즉, 가장 오래 사용하지 않는 데이터는 앞으로도 사용할 확률이 적을 것이라고 가정한다.
•
사용된 시간으로 알 수 있는 부분을 저장해야한다.
•
단점은 프로세스가 주기억장치에 접근할 떄마다 참조된 페이지 시간을 기록해야 하므로 오버헤드가 크다.
•
카운터, 큐, 스택 같은 별도의 하드웨어가 필요하다.
*카운터 : 각 페이지 별로 존재하는 논리적인 시계, 해당 페이지가 사용될 때마다 0으로 초기화한 후, 시간을 증가시킨다.
LFU (Least Frequently Used)
•
참조 횟수가 가장 낮은 페이지를 교체하는 알고리즘 (만약 참조 횟수가 같다면 LRU 방식)
•
LRU 는 직전의 참조된 시점을 반영하지만, LFU 는 참조 횟수를 통해 장기적인 시간 규모의 참조를 반영할 수 있다.
•
단점은 가장 최근에 불러온 페이지가 교체될 수 있고, 오버헤드가 크다.
MFU (Most Frequently Used)
•
참조 횟수가 가장 많은 페이지 교체 알고리즘
•
즉, 가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라고 가정한다.
NUR (Not Used Recently)
•
최근에 사용되지 않은 페이지를 교체하는 알고리즘 (LRU 방식과 유사)
•
교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
•
적절한 성능과 적절한 오버헤드를 가진다.
•
각 페이지마다 참조 비트와 변형 비트가 사용된다.
◦
참조 비트 : 페이지가 참조되지 않았을 때 0, 호출 되었을 때 1
◦
변형 비트 : 페이지의 내용이 변경되지 않았을 때 0, 변경 되었을 때 1
•
교체 시 우선순위는 참조비트 > 변형비트 이다.
