[정보처리기사] 페이지 교체 알고리즘 (FIFO/LRU/LFU/NUR)

페이지 교체 알고리즘

페이지 교체 알고리즘은 페이지 부재가 발생했을 때 가상기억장치의 필요 페이지를 주기억장치에 적재해야 하는데 어떤 페이지 프레임을 선택해 교체할 것인지를 결정하는 기법이다.

 

참고로, '교체'는 기억장치 관리 정책의 반입/배치/교체 정책 중 교체정책을말하며 교체 정책이란 어떤 프로그램이나 자료를 주기억장치로부터 제거할 것인가를 결정하는 정책으로 주기억장치에서 제거할 페이지를 선택하는 정책을 말한다.

 

페이지 부재 : CPU가 엑세스한 페이지가 주기억장치에 없는 경우로, 페이지 부재 발생 시 해당 페이지를 주기억장치로 가져와야 함

 

 

FIFO (First In First Out)

- 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

- 각 페이지가 주기억장치에 들어올 때마다 타임스탬프를 찍어 기억하는 방식

 

---

ex-1) 다음의 참조 페이지를 세개의 페이지 프레임을 가진 기억장치에서 FIFO 알고리즘을 사용해 교체했을 시 페이지 부재수는 ? 

 

사용할 페이지 프레임이 없을 경우 가장 먼저 들어와 오래 있었던 페이지를 제거하기 때문에 아래 표처럼 진행하면 총 페이지 부재수는 6번이 된다.

 

참조페이지	2	3	2	1	5	2	3	5
					2를 제거	3을 제거	1을 제거
프레임			(2)	2	(2)	2	(5)	5	5	(5)
	(3)	3	3	3	(2)	2	2
			(1)	1	1	(3)	3
페이지부재	V	V		V	V	V	V

 

 

LRU (Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

- 각 페이지마다 카운터나 스택을 두어 현 시점에서 가장 오랫동안 사용하지 않은 (가장 오래전에 사용된) 페이지를 교체함

 

---

ex-2) 다음의 참조 페이지를 세개의 페이지 프레임을 가진 기억장치에서 LRU 알고리즘을 사용해 교체했을 시 페이지 부재수는 ?

 

사용할 페이지 프레임이 없을 경우 가장 오래전에 사용된 페이지를 제거하기 때문에 아래 표처럼 진행하면 총 페이지 부재수는 5번이 된다.

 

참조페이지	2	3	2	1	5	2	3	5
					제거		제거
프레임			2	2	(2)	2	2	(2)	2	2
	3	3	3	(5)	5	5	(5)
			(1)	1	1	(3)	3
페이지부재	V	V		V	V		V

 

 

LFU (Least Frequently Used)

- 사용 빈도가 가장 적은 페이지를 교체하는 기법

- 즉, 호출된 횟수가 가장 적인 페이지를 교체

- 바로 불러온 페이지가 교체될 수 있다는 단점이 존재함

 

 

NUR (Not Used Recently)

- LRU와 비슷한 방식으로, 최근에 사용하지 않은 페이지를 교체

- LRU 교체의 단점인 시간 오버헤드를 적게하는 방법

- 최근 사용여부를 확인하기 위해 각 페이지마다 두개의 비트 (참조비트/변형비트)를 사용

- 참조비트 : 페이지가 호출되었을 때는 1, 호출되지 않았을 때는 0

- 변형비트 : 페이지 내용이 변경되었을 때는 1, 변경되지 않았을 때는 0