이번에는 정보처리기사 필기 과목인 운영체제의 페이징 교체 알고리즘을 알아보기로 해요.
페이지 교체 알고리즘
자주 사용하지 않는 부분을 보조 기억 장치의 페이지 파일로 매핑하는 알고리즘
LRU, LFU, NUR, FIFO, MFU, OPT, SCR 등이 있습니다.
LRU(Least Recently Used)
최근에 사용하지 않은 페이지를 교체
페이지마다 계수가(Counter)와 스택(Stack)을 두어 사용할 때마다 계수를 카운팅합니다.
LFU(Least Frequentyl Used)
사용 횟수가 가장 적은 페이지를 교체
NUR(Not Used Recently)
최근에 사용하지 않은 페이지를 교체
최근에 사용 여부를 확인하기 위해 참조 비트와 변형 비트를 사용합니다.
참조 비트: 페이지 호출 시 1, 호출하지 않을 시 0
변형 비트: 변경했을 때 1, 변경하지 않을 때 0
FIFO(First In First Out)
먼저 적재한 페이지부터 교체
페이지 수를 증가시켰는데 페이지 부재가 더 많이 발생하는 벨레이디의 모순(Belady’s Anomaly) 현상이 발생합니다.
MFU(Most Frequentyly Used)
사용 횟수가 가장 많은 페이지를 교체
OPT(OPTimal replacement)
가장 오랫동안 사용하지 않을 것으로 예측한 페이지를 교체
벨레이디가 제한
SCR(Second Chance Replacement)
FIFO 기법의 단점을 보완하는 기법으로 교체 대상을 판별하기 전에 참조 비트를 검사하여 1일 때 한 번의 기회를 더 부여
참조 비트가 1이면 큐의 맨 뒤로 피드백합니다.