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

1 개요

페이지 교체 알고리즘은 메모리가 꽉 찼을 때 스왑 영역으로 보낼 페이지를 결정하는 알고리즘이다.

 

2 무작위 페이지 교체 알고리즘

말그대로 특별한 로직 없이 무작위로 선정한 페이지를 스왑 영역으로 보내는 방식이다. 지역성을 전혀 고려하지 않았기 때문에 성능이 안 좋다.

 

3 FIFO

선입선출 알고리즘으로 가장 먼저 들어온 페이지를 스왑 영역으로 쫓아낸다.

 

4 최적 페이지 교체 알고리즘

앞으로 사용하지 않을 페이지를 스왑 영역으로 보낸다. 미래의 메모리 접근 패턴을 알아야 하기 때문에 구현이 불가능하다.

 

5 LRU 페이지 교체 알고리즘

가장 오랫동안 사용하지 않은 페이지를 옮긴다.

시간에 기반한 구현과, 카운터에 기반한 구현, 참조 비트 시프트 방식을 이용한 구현 방법이 있다.

 

6 LFU 페이지 교체 알고리즘

페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다.

 

7 LUR 페이지 교체 알고리즘

최근 미사용 페이지 교체 알고리즘으로 추가 비트 2개를 이용해 미래를 추정한다.

참조 비트 : 페이지에 접근하면 1이 된다.

변경 비트 : 페이지가 변경되면 1이 된다.

교체 기준은 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾는다.

만약 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (0,0)으로 초기화한다.

 

8 FIFO 변형 알고리즘

8.1 2차 기회 페이지 교체 알고리즘

FIFO에서 특정 페이지를 부재 없이 성공한 경우 다시 큐의 맨뒤로 옮겨서 기회를 한 번 더 주는 방식이다.

8.2 시계 알고리즘

원형 큐를 이용하는 방식이다. 포인터가 시계처럼 한 방향으로 돈다.