페이지 교체 알고리즘

안녕하세요 bannavi입니다^ㅅ^

오늘은 페이지 교체 알고리즘에 대해 살펴볼게요

바로 시작하겠습니다^ㅅ^

 

 

 

페이지 교체 정책(page replacement policy)

* 운영체제가 특정 페이지를 물리 메모리에 올리려 하는데, 물리 메모리가 다 차있다면?

- 기존 페이지 중 하나를 물리 메모리에서 저장 매체로 내리고(저장)

- 새로운 페이지를 해당 물리 메모리 공간에 올린다.

 

 

 

페이지 교체 알고리즘(FIFO)

* FIFO Page Repalcement Algorithm

- 가장 먼저 들어온 페이지를 내리자

 

 

 

페이지 교체 알고리즘(OPT)

* 최적 페이지 교체 알고리즘 (OPTimal Replacement Algorithm)

- 앞으로 가장 오랫동안 사용하지 않을 페이지를 내리자

- 일반 OS에서는 구현 불가(앞으로 오래 안쓰일 페이지를 어떻게 아는가? 그것은 신의 영역일것..)

 

Requested Page : 시간대별로 요청이 된 페이지라고 가정하기

 

 

 

 

페이지 교체 알고리즘(LRU) 

* LRU(Least Recently Used) Page Replacement Algorithm

- 가장 오래 전에 사용된 페이지를 교체 -> 지금은 사용안될 확률이 높다

- OPT 교체 알고리즘이 구현이 불가하므로, 과거 기록을 기반으로 시도

 

 

 

 

페이지 스왑 알고리즘(LFU)

* LFU(Least Frequently Used) Page Replacement Algorithm

- 가장 적게 사용된 페이지를 내리자

 

 

 

페이지 스왑 알고리즘 (NUR)

* NUR(Not Used Recently) Page Replacement Algorithm

- LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법

- 각 페이지마다 참조 비트(R), 수정 비트(M)을 둠(R, M)

- (0,0), (0,1), (1,0), (1,1) 순으로 페이지 교체

 

 

 

 

참고: 메모리 지역성

코드 1

코드 2를 실행했다면

그 주변 줄을 실행할 확률이 높다.

 

 

 

스레싱(Thrashing)

- 반복적으로 페이지 폴트가 발생해서, 과도하게 페이지 교체 작업이 일어나, 실제로는 아무일도 하지 못하는 상황