(13) 페이지 교체 알고리즘

1. 페이지 교체 알고리즘

> 가상 메모리 기법을 사용하는 경우

1-1) 요구 페이징 기법

프로세스가 특정 페이지를 요구할 때, 메모리에 해당 페이지가 없으면 필요한 그 페이지만 backing store에서 메모리로 적재를 하고 사용하지 않는 부분은 그대로 적재하지 않고 두는 방식

 

1-2) 페이지 교체 알고리즘 정의

1-1)의 요구 페이징 기법을 통해 올라온 페이지들이 메모리에 가득 차게 되면

어떤 페이지를 다시 backing store로 돌려보내 page-out을 시키고, 그 공간에 page-in을 시킬 공간을 확보하게 됨

 

이때, page-out되는 페이지를 victim-page라고 함.

기왕이면 수정되지 않는 페이지를 선택하는데, 수정이 있는 페이지일 경우 수정사항을 보조저장장치 backing store에 있는 값도 수정해야 하기 때문

 

 

2. 알고리즘 종류

2-1) FIFO

(a) 정의

가장 간단한 알고리즘, 메모리에 올라온지 가장 오래된 페이지를 교체.

알고리즘 수행을 위한 data로 각 페이지가 올라온 시간을 기록 / 순서를 queue에 저장하는 방식을 보통 사용

(b) 문제점

위와 같이 2번 메모리가 적재된 프레임이 활발히 사용되는 경우
0, 3의 queue 순서에 밀려 활발히 사용되는 2번이 사라졌다 다시 메모리에 적재되는 현상이 나타날 수 있고

페이지 부재율이 높아지고 실행 속도가 떨어질 위험

(c) 해결

프레임의 수를 늘리면 해결 가능
( 프레임 수가 작을 수록 교체가 빈번하게 일어나기 때문에 )

 

2-2) OPT / 최적 페이지 교체

(a) 정의

앞으로 가장 사용되지 않을 페이지를 알고리즘으로 선택해 우선적으로 내보내는 알고리즘

(b) 문제점

앞으로 사용되지 않을 것이라는 확신을 갖기 어려우므로, 정확한 FIFO보다는 개선되었지만, 정확한 알고리즘이라고

생각하기는 어려움

 

2-3) LRU (least-recently-used)

(a) 정의

가장 오래 사용되지 않은 페이지를 교체하는 알고리즘

최근에 사용하지 않은 페이지를 가장 먼저 교체한다.

(b) 특징

FIFO 알고리즘보다 효율적이며 과거의 데이터를 이용(페이지 사용 빈도를 체크)하기 때문에

OPT 알고리즘보다 현실적이며 잘 동작한다.

---

참조

https://gyoogle.dev/blog/computer-science/operating-system/Page%20Replacement%20Algorithm.html

페이지 교체 알고리즘 | 👨🏻‍💻 Tech Interview

https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

페이지 교체(page-replacement) 알고리즘

https://copycode.tistory.com/122

운영체제 24장 - 메모리 관리(11) : 페이지 교체 알고리즘 -