[운영체제]페이지 교체 알고리즘(Page Replacement Algorithm)

[운영체제]페이지 교체 알고리즘(Page Replacement Algorithm)

💡 페이지 교체란

페이지 교체 알고리즘은 멀티프로그래밍 환경에서 다수 프로세스가 메모리 상에 공존할 때  혹은 물리메모리보다 더 큰 메모리 공간을 필요로 하는 프로세스가 실행 시 페이지 부재(페이지 폴드 / Page Fault) 를 최소화하면서 효율적으로 실행하기 위한 메커니즘이다.

• 페이지 부재(Page Fault)가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야하는데, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
• 이러한 경우, 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하여 새로운 페이지를 메모리에 올려야 한다.
• 이러한 과정을 페이지 교체라고 부르며, page-out이 된 페이지를 희생양 페이지 (victim page)라고 한다

페이지 교체 알고리즘 유형

요약

• OPT - Optimal: 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO - First In First Out: 가장 먼저 들어온 페이지를 교체
• LRU - Least Recently Used: 가장 오랫동안 사용되지 않은 페이지를 교체
• LFU - Least Frequently Used: 참조 횟수가 가장 적은 페이지 교체
• MFU - Most Frequently Used: 참조 횟수가 가장 많은 페이지 교체
• NUR - Not Used Recently: 최근에 사용하지 않은 페이지 교체
• SCR - Second Chance Replacement: FIFO에서 한 번 더 기회를 주고 교체
• 클럭 알고리즘: SCR과 동일

 

1️⃣ 시간 기반 알고리즘

FIFO(First-In-First-Out) 알고리즘

- 선입선출에 의한 페이지 교체

- 일반적인 상황에서 잘 동작하는 기본적 교체 알고리즘

- 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기때문에 비효율적인 상황이 발생할 수 있다. 빌레이디의 모슨(Belady's Anomaly) 현상 ->  LRU의 필요성 대두

빌레이디 모순 현상 : 페이지 프레임 수가 많으면 페이지 부재수가 줄어드는 것이 일반적이지만,

페이지 프레임수를 증가시켰음에도 페이지 부재가 더 많이 일어나는 현상

 

 

 

LRU(Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법. (마지막 참조시점이 가장 오래된 페이지 교체)

- 최적화(Optimal) 페이지 교체에 근사하기 위한 목적

- 시간지역성(temporal locality)의 성질을 고려해 고안된 알고리즘이다.

- 계수기(Counter)나 스택(Stack)과 같은 별도의 하드웨어가 필요하며, 시간적인 오버헤드가 발생된다. (실제로 구현이 어려움)

- 시간 지역성 : 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질)
- 계수기 : 각 페이지별로 존재하는 논리적인 시계(Logical Clock)로, 해당 페이지가 사용될때마다 0으로 클리어 시킨 후 시간을 증가시켜 시간이 가장 오래된 페이지를 교체)

 

 

 

SCR(Second Chance Replacement)

- Clock Algorithm으로도 불림

- 페이지에 Reference bit 를 두어 교체를 1회 유예

- LRU를 근사하기 위한 목적으로 등장

 

 

LFU(Least-Frequently-Used) 알고리즘

- 페이지의 참조횟수로 교체할 페이지를 결정하는 기법.

- 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 내쫓고 그 자리에 새로 참조될 페이지를 적재한다.

- LFU 알고리즘은 LRU 알고리즘보다 오랜시간 동안의 참조 기록을 반영할 수 있다는 장점이 있다.

- LRU 알고리즘은 직전 참조된 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적인 시간 규모에서의 참조 성향을 고려하기 떄문이다.

- 하지만 LFU는 시간에 따른 페이지 참조 변화를 반영하지 못하고, LRU보다 구현이 복잡하다는 단점이 있다.

• 예를 들어 페이지 참조열이 (1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5)라고 하고 페이지 프레임 수가 4개라고 하자.
  현재 시각에 5번 페이지가 참조되었다고 할때, 교체 알고리즘은 메모리 내에 존재하는 1,2,3,4 페이지 중에 어떤 것을 삭제할 것인지를 결정해야 한다.
  이 때, LRU 알고리즘의 경우 1번 페이지를 교체 대상을 선정한다.
  (1번 페이지가 가장 오래전에 참조되었기 때문에)
  하지만, 1번 페이지는 마지막 참조시점이 다른 페이지들에 비해 오래되기는 했지만 참조횟수가 가장 많았다.
  LRU 알고리즘은 이러한 사실을 알지 못한다.
  이에 비해 LFU 알고리즘은 4번 페이지를 교체 대상으로 선정한다.
  (4번 페이지의 참조횟수가 가장 적기 때문)
  그러나 4번 페이지는 가장 최근에 참조된 페이지로 지금부터 인기를 얻기 시작하는 페이지일수도 있지만 LFU 알고리즘은 이러한 사실을 알지 못한다.

- LRU, LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야 하므로 알고리즘의 운영에 오버헤드가 발생한다.

 

 

 

클럭 알고리즘 = NRU(Not Recently Used) = NUR(Not Used Recently)

- LRU를 근사시킨 알고리즘, 최근에 사용하지 않은 페이지를 교체하는 기법
- LRU 알고리즘은 가장 오래전에 참조된 페이지를 교체하는것에 비해, 클럭 알고리즘은 오랫동안 사용하지 않은 페이지중 하나를 교체한다.
즉, 최근에 참조되지 않은 페이지를 교체대상으로 선정한다는 측면에서 LRU와 유사하지만 교체되는 페이지의 참조시점이 가장 오래되었다는 것을 보장하지는 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있다.
최근의 참조 여부를 확인하기 위해서 각 페이지마다 두 개의 비트 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)가 사용된다.

• 참조 비트 : 페이지가 참조되지 않았을때는 0, 호출되었을때는 1로 지정
• 변형 비트 : 페이지 내용이 변경되지 않았을때는 0, 변경되었을때는 1로 지정
  이 알고리즘은 하드웨어적인 자원으로 동작하기 떄문에 LRU에 비해 교체 페이지의 선정이 훨씬 빠르게 결정된다.
  따라서, 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.

• SCR을 원형 큐를 이용하여 구현한 것이다.
• LRU 알고리즘, LFU 알고리즘과는 달리 하드웨어적인 자원을 통해 동작한다. (해당 알고리즘은 참조 시각 및 참조 횟수를 소프트웨어적으로 유지 및 비교해야 한다.)
• 페이지 프레임의 참조 비트를 조사해서 참조 비트가 1인 페이지는 0으로 바꾼 후 지나가고, 0인 페이지를 찾으면 그 페이지와 교체한다.

 

 

최적 페이지 교체(OPR : Optimal Page Replacement))

- 이론적으로 최적의 페이지 교체 알고리즘(페이지 부재율이 가장 낮은 효율적인 알고리즘이다.)

- 향후 사용될 페이지 내역을 미리 예측하여 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법.

- 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전재하에 알고리즘을 운영하므로 현실적으로

실현은 어려우나 다른 페이지 교체 알고리즘의 성능을 측정하기 위한 척도로서 사용

2️⃣ 빈도 기반

MFU(Most Frequently Used)

- 가장 많이 사용된 페이지가 앞으로는 사용되지 않을것이라는 가정으로 교체

 

LFU(Least Frequently Used)

- 가장 사용 빈도가 적은 페이지를 교체

 

3️⃣ Random

Random

- 무작위 페이지 교체

 

 

 

 

 

참고

https://bibimnews.com/entry/Page-Fault%EC%9D%98-%EC%B5%9C%EC%86%8C%ED%99%94%EB%A5%BC-%EC%9C%84%ED%95%9C-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://eunhyejung.github.io/os/2018/07/24/operatingsystem-study15.html