[운영체제] 페이지교체 알고리즘

페이지 부재

프로세스 실행 시 참조할 페이지가 주기억장치에 없는 현상

페이지 부재 빈도(PFF;Page Fault Frequency)는 페이지 부재가 일어나는 횟수를 의미

 

페이지 부재 빈도 방식

페이지 부재율(Page Fault Rate)에 따라 주기억장치에 있는 페이지 프레임의 수를 늘리거나 줄여 페이지 부재율을 적정 수준으로 유지하는 방식

 

페이지 교체 알고리즘

페이지 부재가 발생했을 때 가상 기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데,

이때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 교체할지 결정하는 기법

OPT (OPTimal Replacement, 최적교체)	앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법 (실현 가능성이 희박하다)
FIFO (First In First Out)	가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법
LRU   (Least Recently Used)	최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
LFU   (Least Frequently Used)	사용 빈도가 가장 적은 페이지를 교체하는 기법 => 프로그램 실행초기에만 많이 사용되고 그 후로 사용되지 않을 경우에도 프레임을 계속차지할 수 있음
NUR   (Not Used Recently)	최근에 사용하지 않은 페이지를 교체하는 기법
SCR   (Second Chance Replacement)	가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 의 단점을 보완한 기법

 

페이지 크기

페이지크기가 작을 경우	페이지의 단편화가 감소하고, 핸 개의 페이지를 주기억장치에 이동하는 시간이 줄어듬 프로그램 수행에 필요한 내용만 주기억장치에 적재 가능, Locality(국부성)에 더 일치할 수 있기 때문에 기억장치 효율이 좋아짐 페이지 맵 테이블의 크기가 커지고, 매핑속도가 늦어짐 디스크 접근 횟수가 많아져서 I/O시간은 늘어남
페이지크기가 클 경우	페이지 맵 테이블의 크기가 작아지고, 매핑속도가 빨라짐 I/O 횟수가 줄어들어 효율성이 증가함 페이지의 단편화가 증가되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 늘어남 프로그램 수행에 불필요한 내용까지도 주기억장치에 적재될 수 있음

 

국부성(Locality, 구역성)

프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론

스래싱을 방지하기 위한 워킹셋 이론의 기반

가상 기억장치 관리의 이론적인 근거가 됨

Locality 종류

시간 구역성 (Temporal Locality)	프로세스가 실행되면서 하나의 페이지를 일정 시간 동안 집중적으로 액세스하는 현상   => Loop(반복, 순환), 부프로그램(Sub Routine), Totaling(집계) 에 사용되는 변수(기억장소)
공간 구역성   (Spatial Locality)	프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상   => 배열 순회(Array Traversal), 순차적 코드의 실행, 프로그래머들이 관련된 변수들을 서로 근처에 선언하여 할당되는 기억장소, 같은 영역에 있는 변수를 참조할 때 사용

 

워킹셋(Working Set)

프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합으로, 자주 참조되는 워킹 셋을 주기억장치에 상주시킴으로써 페이지 부재 및 페이지 교체 현상을 줄일 수 있고, 이로 인해 기억장치 사용이 안정됨

 

스래싱(Thrashing)

프로세스의 처리 시간보다 페이지 교체 시간이 더 많아지는 현상

자주 페이지 부재가 발생함으로써 인해 나타나는 현상으로 전체 시스템의 성능이 저하됨

다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 특정 시점까지는 높아지지만 다중 프로그래밍의 정도가 더욱 커지면 스레싱이 나타나고, CPU의 이용률은 급격히 감소한다.

스래싱 방지 기법

• 다중 프로그래밍의 정도를 적정 수준으로 유지
• 부족한 자원 증설
• 페이지 부재 빈도 조절
• Working Set 유지
• 적정 프레임 수 제공