3. 운영체제

1. 페이지 교체 알고리즘

- 페이지 부재 ( Page Fault ) : 원하는 페이지가 메모리에 없는것 ( 하드에 존재 )

- 스래슁 : CPU가 임의의 작업을 해야하는데 하드에서 가져오기만 반복 (페이지 부재가 원인)

페이지 교체 알고리즘은 페이지부재의 최소화가 목적이다.

1.1 FIFO

프레임 개수가 늘어남에 따라 밸러디 변이 또는 어노말리 현상이 발생할 수 있다.(페이지 부재가 많아진다.)

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

1.2 무작위

1.3 2차 기회

1.4 NUR

참조비트(read), 변형비트(write)가 존재한다.

1. 00의 페이지를 가장먼저 교체

2. 01

3. 10

4. 11

1.5 최적교체(OPT)

미래를 보고 사용하지 않는 페이지를 교체

페이지부재가 최소화됨

미래예측이라는 비현실성으로 잘 사용되지 않음

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

7번의 FP

1.6 LRU

현재까지 제일 오래동안 사용하지 않은 페이지를 교체

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

11번의 FP

1.7 LFU

빈도수가 가장 적은것을 교체

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

10번의 PF

1.8 MFU

빈도수가 가장 많은것을 교체

1.9 Working Set (작업 세트)

자주 등장하는 페이지에 대해서 집합을 구성

메모리에 저장하고 집합은 페이지를 교체하지 않음