[OS] Paging 교체 방법 / 페이지 테이블 오버헤드 / 쓰레싱 (Thrashing)

페이지 교체 기법

페이지 부재(Page Fault): 주기억장치에 참조하려는 페이지가 없는 경우

페이지 폴트 발생 시 주기억장치 내에 어떤 페이지와 교체할 것인지 결정 필요함

 

최적 교체 (OPTimal Replacement): 가장 오랫동안 참조되지 않을 페이지 교체

FIFO (First In First Out): 메모리에 가장 먼저 올라온 페이지 먼저 교체

LRU (Least Recently Used): 참조된 지 가장 오래된 페이지 교체

LFU (Least Frequently Used): 사용 빈도가 가장 적은 페이지 교체

SCR (Second Chance Replacement): 참조 bit를 두어 프로세스가 참조한 페이지를 1로 세팅

NUR (Not Used Recently) : 두 개의 하드웨어 비트로 페이지가 호출될 때, 페이지 내용이 변형되었을 때 각 1로 세팅

 

Belady's Anomaly

FIFO 알고리즘에서 발생하는 이상현상

페이지 프레임 수가 늘면 페이지 폴트가 줄어야 하는데 오히려 늘어나는 이상현상

 

페이지 프레임 수:3  /  페이지 폴트 수: 9

페이지 프레임 수: 4  /  페이지 폴트 수: 10

 

 

LRU 알고리즘 구현 방법

1. Counter Implementation: 페이지가 실행된 시간을 페이지 테이블에 저장

2. Stack Implementation: 실행되는 페이지에 따라서 페이지 넘버를 스택으로 쌓아서 관리

-> 하드웨어의 지원이 필요함

 

LRU Approximation 알고리즘

하드웨어의 지원 없이 reference bit를 사용하여 구현하는 알고리즘

페이지 참조가 있을 때마다 하드웨어가 그 페이지에 대한 참조 비트를 설정함

 

 

 

페이지 테이블 오버헤드

공간적 오버헤드: 페이지 테이블에 매핑 정보들을 저장하기 위해 큰 메모리 공간이 요구됨

시간적 오버헤드:

1. 페이지 테이블에 접근
2. 페이지 테이블을 기반으로 실제 메모리에 접근

 

완화방안

시간적 오버헤드: 페이지 테이블을 캐시로 만든 TLB (Translaction Look-aside Buffer) 활용함

공간적 오버헤드: 페이지 테이블 크기 조정

- 페이지의 크기를 늘려서 페이지 테이블 갯수 줄이기 -> 내부 단편화 발생 가능

- 프로그램을 세그멘트 단위로 나누고, 분할된 세그멘트를 페이지 단위로 분할하여 메모리에 적재

 

 

쓰레싱 (Thrashing)

: 페이지 교체가 너무 자주 일어나 프로그램 수행 시간보다 페이지 교체 소요 시간이 더 큰 경우

다중 프로그래밍의 정도가 커지면 스레싱 현상이 자주 일어남

 

해결책

- 다중프로그래밍 정도를 낮춤

- 프로세스들에 충분히 큰 페이지 프레임을 할당

- 프로세스들이 가질 수 있는 페이지 프레임 수를 늘림

- 지역 교환 / 우선순위 교환 알고리즘 사용