[Operating System] 페이지 교체(Page Replacement) 알고리즘

페이지 교체(Page Replacement) 알고리즘?

• 페이지 부재 발생 -> 새로운 페이지를 할당 해야함 -> 현재 할당된 페이지 중 어떤 것을 교체할지 결정하는 방법
• 가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 적재하고 사용하지 않는 부분은 그대로 둠
• 필요한 페이지만 올려도 메모리는 결국 가득 차게 될 것
  • 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있음
• 메모리가 가득 차면 추가로 페이지를 가져오기 위해 안쓴는 페이지는 out하고, 해당 공간에 필요한 페이지를 in 시켜야 함
  • 이때 어떤 페이지를 out 시켜야할 지 결정해야함
  • out 되는 페이지를 victim page라고 함
• 교체되는 페이지는 가능한 수정되지 않은 페이지를 선택해야 좋음
  • 만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸림
• 상황에 맞는 페이지 교체를 위해 페이지 교체 알고리즘이 존재하는 것임

Page Reference String?

• CPU는 논리 주소를 통해 특정 주소를 요구함
• 메인 메모리에 올라와 있는 주소들은 페이지 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나면 페이지 결함이 발생하지 않음
• CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 Page Reference String이다

FIFO(First In First Out) 알고리즘

• 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
• 가장 간단한 방법으로 특히 초기화 코드에서 적절한 방법이다.
  • 초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음
  • 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함

OPT(Optimal Page Replacement) 알고리즘

• 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄
• FIFO에 비해 페이지 결함 횟수를 많이 감소시킬 수 있음
• 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘임

LRU(Least Recently Used) 알고리즘

• 최근에 사용하지 않은 페이지를 가장 먼저 내보내는 알고리즘
• 최근에 사용하지 않았다면 나중에도 사용되지 않을 것이라는 아이디어에서 나옴
• OPT의 경우 미래 예측이지만, LRU의 경우 과거를 보고 판단하므로 실직적으로 사용이 가능한 알고리즘
  • 실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다.
• OPT보다 페이지 결함이 더 일어날 수 있지만, 실제 사용할 수 있는 페이지 알고리즘에서는 가장 좋은 방법

LFU(Least Frequently Used) 알고리즘

• 페이지의 참조 횟수로 교체할 페이지 결정
• 참조횟수가 가장 낮은 페이지를 교체하는 방법
• LRU는 직전 참조된 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적 시간규모에서의 참조성향 고려할 수 있음
• 단점
  • 가장 최근에 불러온 페이지가 교체될 수 있음
  • 구현 더 복잡함, 막대한 오버헤드 발생

MFU(Most Frequently Used) 알고리즘

• 참조 횟수가 가장 많은 페이지를 교체하는 방법
• 가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라는 가정을 이용

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

• 최근에 사용하지 않을 페이지를 교체하는 방법
  • LRU를 근사한 알고리즘
• 교체되는 페이지의 교체 시점이 가장 오래되었다는 것을 보장하지 못함
• 적은 오버헤드로 적절한 성능
• 동일 그룹내에서 선택 무작위
• 각 페이지마다 두개의 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Birty Bit)가 사용됨
  • 참조 비트 : 페이지가 참조되지 않았을 때 0, 호출되었을 때 1 (모든 참조비트를 주기적으로 0으로 변경)
  • 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
• 우선 순위는 참조 비트가 변형 비트보다 크다.
  • 참조 비트 > 변형 비트

교체 방식

• Global 교체
  • 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
• Local 교체
  • 메모리 상의 자기 프로세스 페이지만 교체하는 방식
• 다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음
  • 다양한 프로세스의 페이지가 메모리에 존재함
  • 페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정
  • 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이
• 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적
  • 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적

 

 

 

 

 

출처

https://doh-an.tistory.com/28

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖