메모리 페이지 교체기법

I. 가상메모리 페이지 교체, 페이지 교체 기법

가. 페이지 교체 기법의 개념

가상메모리 사용 시 물리적 기억장치 사용공간이 없을 때 어떤 페이지 프레임을 내보낼지 결정하는 기법

나. 페이지 교체 기법의 특징

Trade-off	– 페이지 크기에 따른 Trade-off – 크기 클수록 필요 없는 정보 추가, 적재 문제
FIFO Anomaly	– Belady’s Anomaly(벨리디의 모순) – 더 많은 페이지 할당 시 더 많은 부재 발생

 

II. 페이지 교체 기법 종류

교체 기법	개념도	설명
FIFO		– First In First Out – 가장 먼저 들어온 페이지를 내보냄
LFU		– Least Frequently Used – 참조 횟수가 가장 적은 페이지 교체 – 참조 횟수가 동일하다면 LRU 기준 수행
LRU		– Least Recently Used – 참조 시간 기준, 가장 오래된 페이지 교체
OPT		– OPTimal replacement – 가장 오랫동안 사용하지 않을 페이지 교체 – 호출 순소, 참조상황 예측 필요, 실현 희박
NUR		– Not Used Recently – 최근에 사용하지 않은 페이지 교체 – 참조 비트와 변형 비트에 따라 순서 결정
SCR		– Second Chance Replacement – FIFO 기법의 단점을 보완 – 페이지 별 참조 비트 1일 때 0으로 변경, 0 일 때 페이지 교체. 한 번의 기회 더 부여

 

III. FIFO 동작 방법

① 초기화 단계 –  FIFO 메모리 내 데이터 삭제 –  Read/Write 포인터 0번지 초기화 ② 입력 발생 시 –  Write 포인터 증가, 다음 Write 번지 ③ 출력 발생 시 –  Read 포인터 증가, 다음 Read 번지 ④ Read/Write 명령 시 마다 포인터 증가 및 명령 수행 ⑤ FIFO 버퍼는 저장용량 Full까지 입력 가능하며, Empty까지 출력 가능

 

IV. FIFO 이상현상 (Belady’s Anomaly)

가. FIFO 이상 현상의 개념

페이지 교체 알고리즘 중 FIFO에서 페이지 프레임의 개수를 늘렸지만 페이지 부재가 오히려 증가하는 현상

나. FIFO 이상 현상의 원인 및 영향

원인	– Locality를 고려하지 않은 FIFO 한계로 부재 증가
영향	– 페이지 부재율 증가로 성능 저하 및 스래싱 발생

다. FIFO 이상현상 사례 설명

 

V. FIFO 이상현상 발생 해결 방안

구분	해결 방안	설명
페이지 교체 정책	LRU 사용	– 페이지 교체 시점에 가장 최근 참조가 안된 페이지 교체
	OPT 사용	– 앞으로 가장 오랫동안 사용하지 않을 페이지 교체
최적화 원칙 설계	Locality	– 시간, 공간, 순차적 지역성 활용 – 일정기간 참조되는 페이지 유지
	PFF	– 프로세스 페이지 폴트 빈도에 따라 Residence Set 조정, PFF가 높으면 Residence Set 크기 증가, 낮으면 줄임
	Working Set	– 일정기간 동안 참조되는 페이지 집합을 주 기억장치에 유지

VI. FIFO와 LRU 기법 수행

가. FIFO 알고리즘 수행

나. LRU 알고리즘 수행