[운영체제] 페이지 교체 알고리즘

1. 페이지 교체 알고리즘이란? 

메모리에 필요한 페이지가 부재할 경우, 새로운 페이지를 할당해야 하는데 이때 현재 메모리에 존재하는 페이지 중 어떤 페이지를 교체할지 결정하는 알고리즘이다.

 

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다. 만약 메모리가 가득 차면, 추가로 페이지를 가져올 때 사용하지 않는 페이지를 꺼내고, 필요한 페이지를 그 페이지가 있던 공간에 넣어야 한다.  이때 기왕이면 수정이 되지 않는 페이지를 선택해야 좋다. 만약 수정이 된 페이지를 꺼내게 되면 하드디스크에 기록을 해야 하므로 오버헤드가 크다. 

 

2. 페이지 교체 알고리즘 종류 

2.1. FIFO 알고리즘 

1. First-in-First-out으로 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘이다. 
2. 처음 프로세스 실행시에 최초 초기화하는 작업만 수행하는 부분을 제외시킬 때 적절한 방법이다. 

2.2. OPT 알고리즘 

1. Optimal 알고리즘으로 앞으로 사용하지 않을 페이지를 가장 우선적으로 내보내는 알고리즘이다.
2. FIFO에 비해 페이지 폴트의 횟수를 현저히 감소시킬 수 있지만 애초에 사용하지 않을 페이지라는 보장이 없기에 실현시킬 수 없는 알고리즘이다.

2.3. LRU 알고리즘

1. Least-Recently-Used로 최근에 사용하지 않은 페이지를 가장 먼저 내보내는 알고리즘이다.
2. 최근에 사용하지 않았으면 나중에도 사용하지 않을 것이라는 가정하에 만들어진 알고리즘이다.
3. OPT 보다는 많은 페이지 폴트가 발생하지만, 실제로 사용 가능한 페이지 교체 알고리즘 중에서는 페이지 폴트가 가장 적다.

 

3. 교체 방식 

1. Global 교체 : 메모리 상의 모든 프로세스의 페이지가 victim page 후보가 되는 교체 방법 
2. Local 교체 : 메모리 상의 자기 프로세스 페이지만 victim page 후보가 되는 교체 방법

 

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

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