페이지 교체 알고리즘

한번쯤은 들어봤을 페이지 교체 예시로 FIFO, LRU, LFU...등등이 있다

​

페이지 교체의 궁극적인 목표는 메모리에서 앞으로 사용할 가능성이 적은 페이지를 교체하여 페이지 부재(Page Fault)를 줄이고 시스템의 성능을 향상시키는 것이며 이를 통해 시스템이 메모리 자원을 보다 효율적으로 사용하도록 돕고, 페이지를 불필요하게 자주 디스크에서 로드하거나 저장하지 않도록 한다.

​

여러 알고리즘이 존재하니 살펴보자

​

무작위 페이지 교체 알고리즘 ( randompagereplacement algorithm )

특별한 로직없이 무작위로 선정하기때문에 지역성을 고려하지않아 만일 자주 사용하는 페이지가 선정된다면 굉장히 성능면에서 떨어지며 효율적이지 않다.

​

FIFO 페이지 교체 알고리즘 ( First In First Out page replacement algorithm )

메모리에 가장 먼저 들어온 페이지를 대상으로 선정하여 스왑 영역으로 쫓아낸다.

무조건 오래된 페이지를 대상으로 선정하기 때문에 성능면에서 떨어진다.

FIFO에만 일어나는 ( Belady`s Anomaly ) 페이지 수를 늘렸는데 프레임의 수 늘어나는 현상이 생길 수도 있다.

즉 메모리 프레임 수가 증가할수록 페이지 부재율이 오히려 증가할 수도 있다 => 비효율적이다.

​

ex) 페이지 요청 순서가 [ 2, 0, 4, 3, 0, 2, 1, 7, 9, 7, 4, 9, 5, 1, 4 ] 임의로 이렇게 되어있다 치자

캐시의 크기가 3일때 FIFO 식으로 페이지 교체를 한다면

2	0	4	3	0	2	1	7	9	7	4	9	5	1	4
​	​	​	​	​	​	​	​	​	​	​	​	​	​	​
2	2	2	3	3	3	3	7	7	7	7	7	5	5	5
​	0	0	0	0	2	2	2	9	9	9	9	9	1	1
​	​	4	4	4	4	1	1	1	1	4	4	4	4	4
M	M	M	M	H	M	M	M	M	H	M	H	M	M	H

​

총 Hit - 4번

총 Miss - 11번

Page Fault (페이지 부재) : 11

​

----------------------------------------------------------------------

​

LRU 페이지 교체 알고리즘 ( LeastRecently Used page replacement algorithm )

'최근 최소 사용 페이지' => 가장 오랫동안 사용하지 않은 페이지를 교체

알고리즘 시간을 기준 or 카운터나 참조 비트로 구현가능

​

ex) 페이지 요청 순서가 [ 5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1 ] 임의로 이렇게 되어있다 치자

캐시의 크기가 3일때 LRU 식으로 페이지 교체를 한다면

​

5	0	1	0	2	3	0	2	4	3	3	2	0	2	1	2	7	0	1	1
​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​
5	5	5	5	2	2	2	2	2	2	2	2	2	2	2	2	2	2	1	1
​	0	0	0	0	0	0	0	0	3	3	3	3	3	1	1	1	0	0	0
​	​	1	1	1	3	3	3	4	4	4	4	0	0	0	0	7	7	7	7
M	M	M	H	M	M	H	H	M	M	H	H	M	H	M	H	M	M	M	H

​

총 Hit - 8번

총 Miss - 12번

Page Fault (페이지 부재) : 12

​

----------------------------------------------------------------------

​

LFU 페이지교체알고리즘 ( LeastFrequently Used page replacement algorithm )

페이지가 몇 번 사용 되었는지를 기준으로 선정 => 페이지 마다 사용한 횟수를 세고 가장 적은 페이지를 스왑으로

if 빈도 횟수가 같다면 방식을 주어서 ex) FIFO로 하세요 가장 늦게 사용된걸 쓰세요...

즉 hit를 낼때마다 빈도 횟수가 올라간다 보면됨

​

ex) 페이지 요청 순서가 [ 5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1 ] 임의로 이렇게 되어있다 치자

캐시의 크기가 3일때 LFU 식으로 페이지 교체를 한다면

​

5	0	1	0	2	3	0	2	4	3	3	2	0	2	1	2	7	0	1	1
​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​
5	5	5	5	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2
​	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
​	​	1	1	1	3	3	3	4	3	3	3	3	3	1	1	7	7	1	1
M	M	M	H	M	M	H	H	M	M	H	H	H	H	M	H	M	H	M	H

총 Hit - 10번

총 Miss - 10번

Page Fault (페이지 부재) : 10

​

----------------------------------------------------------------------

​

최적 페이지 교체 알고리즘(optimal page replacement algorithm) - OPT

앞으로 사용하지 않을 페이지를 스왑 영역으로 넘김

가장 가까운 미래에 사용될 페이지를 교체하는 방식이며 이 알고리즘은 이론적으로 가장 최적화된 페이지 교체 알고리즘실제로는 구현하기 어렵지만 페이지 교체 알고리즘 성능 비교에서 기준이 됨

​

ex) 페이지 요청 순서가 [ 5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1 ] 임의로 이렇게 되어있다 치자

캐시의 크기가 3일때 OPT 식으로 페이지 교체를 한다면

​

5	0	1	0	2	3	0	2	4	3	3	2	0	2	1	2	7	0	1	1
​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​	​
5	5	5	5	2	2	2	2	2	2	2	2	2	2	2	2	7	7	7	7
​	0	0	0	0	0	0	0	4	4	4	4	4	4	1	1	1	1	1	1
​	​	1	1	1	3	3	3	3	3	3	3	0	0	0	0	0	0	0	0
M	M	M	H	M	M	H	H	M	H	H	H	M	H	M	H	M	H	H	H

총 Hit - 11번

총 Miss - 9번

Page Fault (페이지 부재) : 9