Page Fault의 최소화를 위한 페이지 교체 알고리즘

 

Prologue

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

  한정된 물리 메모리 공간에서 페이지 폴트를 최소화하며 프로세스에 메모리를 할당하기 위한 페이지 교체 알고리즘에 대해서 알아보겠습니다.

 

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

- 멀티프로그래밍 환경에서 프로세스의 원활한 수행을 위해 주메모리에서 디스크 스왑영역으로 교체할 페이지를 선택하는 알고리즘

 

페이지 교체 알고리즘의 유형

<페이지 교체 알고리즘의 유형>

시간 기반 알고리즘

FIFO

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

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

- Belady's Anomaly 로 인해 LRU의 필요성 대두

LRU(Least Recently Used)

- 페이지 중 가장 오랫동안 사용되지 않은 페이지를 교체

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

SCR(Second Chance Replacement)

- Clock Algorithm으로도 불림

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

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

OPT(Optimal)

- 이론적으로 최적의 페이지 교체 알고리즘

- 향후 사용될 페이지 내역을 미리 예측하여 가장 최적의 교체 페이지를 선정

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

빈도 기반

MFU(Most Frequently Used)

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

LFU(Least Frequently Used)

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

Random

Random

- 무작위로 페이지 교체

 

이 포스트는 IT토픽의 주요 내용과 핵심 키워드를 간략히 설명하는 것이 목적으로, 디테일한 내용에 대해서는 깊이 다루지 않습니다.