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

1. FIFO

1) 예제

3개의 페이지 프레임을 갖는 시스템에서 페이지 참조순서가 1,2,1,0,4,1,3 일때 FIFO 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태는?

4 1 3

---

1  2  1  0   4   1   3

1  1  1  1   4   4   4

    2  2  2   2   1   1

            0   0   0   3

O O X  O  O  O  O - 6번의 페이지 부재가 발생했다.

 

 

2) 예제

3개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 FIFO 방법을 사용한다면 몇번의 페이지 부재가 발생하는가?

(단, 현재 기억장치는 모두 비었다고 가정)

요청된 페이지 번호 순서 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2

페이지 부재 - 9

---

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

 

 

 

 

3) 예제

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

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

7번

---

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

https://www.youtube.com/watch?v=qEgXhnujBA8&t=29s

 

 

 

 

 

2. LRU (Least Recently Used)

최근에 사용하지 않은 페이지 교체

 

1) 예제

 

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

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

6번

---

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

 

2) 예제

3개의 페이지 프레임을 갖는 시스템에서 페이지 참조순서가 1,2,1,0,4,1,3 일때 LRU 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태는?

1, 4, 3

---

1	2	1	0	4	1	3
1	1	1	1	1	1	1
	2	2	2	4	4	4
			0	0	0	3
O	O	X	O	O	X	O

 

 

3) 예제

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

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

5회

---

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
O	O	O	X	X	O	X	X	O

 

https://www.youtube.com/watch?v=9CCAK-N8Nwg

 

 

 

 

 

 

3. LFU (Least Frequently Used)

참조횟수가 적은 페이지 교체

 

 

1) 예제

3개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 LFU 방법을 사용한다면 몇 번의 페이지 부재가 발생하는가?

(단, 현재 기억장치는 모두 비었다고 가정)

요청된 페이지 번호 순서 2, 3, 1, 2, 1, 2, 4, 2, 1, 3, 2

5번

---

위 헤더가 참조횟수이다.

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

 

 

2) 예제

4개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 LFU 방법을 사용한다면 페이지 대치의 최종 결과는?

(단, 현재 기억장치는 모두 비었다고 가정)

요청된 페이지 번호 순서 2, 3, 1, 3, 1, 2, 4, 5

2,3,1,5

---

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

 

 

그 외에도 OPT(나중계산), NUR(참조비트, 변형비트), SCR(FIFO 개선) 가 있음

 

https://www.youtube.com/watch?v=eyF_y15iYi4