메모리 페이지 교체기법

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 알고리즘 수행

 

One Comment

콘텐츠 사용 시 출처 표기 부탁 드리고, 궁금한 점이나 의견은 댓글 남겨주세요^^

도리의 디지털라이프에서 더 알아보기

지금 구독하여 계속 읽고 전체 아카이브에 액세스하세요.

Continue reading