7. 운영체제 - 페이지 교체 알고리즘 - LRU(Least Recently Used)

1. 정의

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

2. 특징

 - 설계 복잡

 - 계수기나 스택과 같은 별도의 하드웨어 필요, 오버헤드가 발생 

  * 계수기 : 각 페이지당 가지고 있는 논리적 시계, 해당 페이지가 사용될때마다 0으로 클리어, 시간이 가장 오래된 페이지를 교체

3. 시험문제

2017년 5월 7일 정보처리기사 - 운영체제

47. 가상메모리의 교체정책 중 LRU(Least Recently Used) 알고리즘으로 구현할 때 그림에서 D 페이지가 참조될 때의 적재되는 프레임으로 옳은 것은? (단, 고정 프레임이 적용되어 프로세스에 3개의 프레임이 배정되어 있고, 4개의 서로 다른 페이지(A, B, C, D)를 B, C, B, A, D 순서로 참조한다고 가정한다.)

B		C		B		A		D
B		B		B		B		B
		C		C		C
						A

B	C	B	A	D
B	B	B	B	B
	C	C	C	D
			A	A
X	X	O	X	X

 - 가장 최근에 사용안한것 교체 즉, C를 가장최근 까지 안써서 교체하였다.

 

2017년 5월 7일 정보처리기사 - 운영체제

60. LRU 교체 기법에서 페이지 프레임이 3일 경우 페이지 호출 순서가 3인 곳(화살표 부분)의 빈 칸을 위에서부터 아래쪽으로 옳게 나열된 것은?

														↓
4		2		0		5		2		1		7		3
4		4		4		5		5		5		7
		2		2		2		2		2		2
				0		0		0		1		1

① 3, 2, 1 ② 7, 3, 1

③ 7, 2, 3 ④ 5, 2, 3

4	2	0	5	2	1	7	3
4	4	4	5	5	5	7	7
	2	2	2	2	2	2	3
		0	0	0	1	1	1
X	X	X	X	O	X	X	X

 - 2를 가장최근에 사용하지 않으므로 3으로 교체하였다.

2015년 8월 16일 정보처리기사 - 운영체제

60. 4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때, LRU 페이지 교체 알고리즘을 사용할 경우 몇 번의 페이지 결함이 발생하는가?

페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 1, 2, 5

① 5회 ② 6회 ③ 7회 ④ 8회

1	2	3	1	2	4	1	2	5
1	1	1	1	1	1	1	1	1
	2	2	2	2	2	2	2	2
		3	3	3	3	3	3	5
					4	4	4	4
X	X	X	O	O	X	O	O	X

 - 페이지 부재 5회!

이상으로 LRU 끝!

fifo보다는 아니지만 간간히 나온다!

출처

 - 정보처리기사문제

 - 시나공