[정보처리산업기사] 페이지 교체 알고리즘

페이지 교체 알고리즘

- 페이지 부재가 발생하였을 경우 가상기억장치의 필요한 페이지를 주기억장치의 어떤 페이지 프레임을

 선택하여 교체해야 되는지 결정하는 알고리즘

 

1. FIFO(First In First Out)

- 가장 먼저 들어온 페이지를 먼저 교체시키는 방법 (주기억장치에 가장 오래 머물렀던 페이지를 교체)

ex) 참조페이지 : 1,2,3,4,1,2,5,1,2 / 프레임 : 3개

1	1	1	4	4	5
	2	2	1	1	1
		3	3	2	2

 

2. OPT(OPTimal replacement)

- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법(실현 불가능)

 

3.LRU(Least Recently Used)

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

ex) 참조페이지 : 1,2,3,4,1,3,5,3 / 프레임 3개

1	1	1	4	4	5
	2	2	2	1	1
		3	3	3	3

 

4. LFU(Least Frequently Used)

- 사용 횟수가 가장 적은 페이지를 교체하는 방법

 

5. NUR(Not Used Recently)

- 최근에 사용하지 않은 페이지를 교체하는 방법

- LRU와 다르게 페이지마다 2개의 비트를 두어 호출이나 변형이 되었는지 체크를 하여 우선순위를 부여한다.

- 변형이나 호출이 되었으면 1, 아니라면 0

- 둘다 0일때 우선순위가 높다.