21 - 페이지 교체

페이지 교체의 개념과 방법

19 - 페이징 기법

위 게시물에서 살펴본 것과 같이

페이지란 프로세스를 일정하게

자른 크기 단위이다.

 

이러한 페이징 기법 덕분에

실제 물리 주소보다 큰 프로세스를

실행할 수 있게 되었는데,

 

이 과정에서 운영체제는 페이지를 적절히

선정하거나 내쫓는 기능을 해야 한다.

 

이때, 전체 프로세스 중

필요한 페이지만 메모리에 적재하는 기법을

요구 페이징(Demand paging)이라고 한다.

 

위와 같은 요구 페이징 시스템이

안정적으로 작동하기 위해서는

페이지 교체와 프레임 할당 방법을

알아야 한다.

 

이번 본문에서는 페이지 교체를

중점적으로 살펴볼 예정이다.

 

페이지 교체 알고리즘

앞서 살펴본 요구 페이징 시스템을

계속 사용하다 보면 언젠가는

메모리가 가득 차게 된다.

 

이러한 상황에서 새로운 페이지를

받기 위해 어떤 페이지를 내보낼지

결정하는 알고리즘을

페이지 교체 알고리즘이라고 한다.

 

20 - 페이지 테이블 엔트리

페이지 교체 알고리즘은

위 게시물에서 언급된 페이지 폴트가

가장 적게 일어나는 알고리즘이

좋은 알고리즘으로 평가된다.

 

페이지 참조열

페이지 폴트 횟수를 알기 위해서는

페이지 참조열(Page reference string)을

참고하면 된다.

 

// CPU가 접근한 페이지 순서
2 2 3 5 5 5 3 3 7

// 페이지 참조열
2 3 5 3 7

 

페이지 참조열은 CPU가 접근한

페이지들 중, 연속된 페이지를 없애어

위와 같이 나타낼 수 있다.

 

페이지 교체 알고리즘 종류

페이지 교체 알고리즘의 종류에는

FIFO(First-In-First-Out), 최적,

LRU(Least-Recently-Used)

페이지 알고리즘이 있다.

 

이에 대한 설명은 다음과 같다.

 

페이지 교체 알고리즘 종류	설명
FIFO	메모리에 적재된 페이지 순서대로 다시 내쫓는다.
최적	앞으로 사용 빈도가 가장 낮을 페이지를 내쫓는다. 이론적으로는 가장 낮을 폴트율을 보장한다. 그러나 현실적으로는 불가능에 가깝다.
LRU	현재까지 사용 빈도가 가장 낮았던 페이지를 내쫓는다.