Skip to main content

페이지 교체 알고리즘


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


페이지 교체 알고리즘 (page replacement algorithm)은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.

페이지 교체 알고리즘에는 FIFO, 최적 페이지 교체, LRU, LFU, MFU 등이 있고, 이번에는 FIFO, 최적 페이지 교체, LRU 알고리즘에 대해 알아본다.


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


  • 가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지를 교체한다
  • 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐 (Queue)에 저장하는 방식

장점​

  • 가장 간단한 페이지 교체 알고리즘이다

단점​

  • 위의 예시에서 2번 메모리처럼 활발히 사용되는 메모리가 0,3 queue 순서에 밀려 사라졌다 다시 메모리에 적재되는 현상이 나타날 수 있고, 이로인해 페이지 부재율이 높아지고 실행 속도가 떨어질 위험이 있다.

FIFO2

  • Belady의 모순

    Belady의 모순이란,
    페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순


최적 페이지 교체 (Optimal Page Replacement, OPT)​


  • 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다
  • 프로세스가 앞으로 사용할 페이지를 미리 알아야하는 전제조건이 있다

  • 페이지 7의 경우, 18번째까지 가서 쓰일 것을 미리 알고 있기 때문에 페이지 2와 7을 교체한다 (4번째)
  • 페이지 1의 경우 올라와 있는 {2,0,1} 중 페이지 1이 14번째 참조로 가장 뒤에 쓰이기 때문에 페이지 1과 3을 교체한다 (6번째)

장점​

  • 알고리즘 중 가장 낮은 페이지 부재율을 보장한다

단점​

  • 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없기 때문에 구현의 어려움이 있다

LRU 페이지 교체 알고리즘 (Least Recently Used)​


  • 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘이다
  • 최적 알고리즘이 실제 구현이 어렵기 때문에, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다
  • LRU 알고리즘은 최적 알고리즘보다 페이지 교체 횟수가 높지만 FIFO 알고리즘 보다 효율적이다

  • 페이지 2의 경우 직전의 페이지 부재(page 4)에서 페이지 2가 바로 다음에 사용될 것을 모르기 때문에 {2,0,3} 중 가장 오랫동안안 사용되지 않았던 페이지 2를 교체한다 (9번째)
  • 페이지 0의 경우 가장 오랫동안 사용되지 않았던 페이지 4를 페이지 0과 교체한다. (11번째)

장점​

  • 많은 운영체제가 채택한 알고리즘이며 좋은 알고리즘이라고 평가 받고있음

단점​

  • 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야 함

면접에 나올 수 있는 질문​


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

A. 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법


Q. Input과 알고리즘이 주어졌을 때 페이지 부재 횟수 구하기

A. Input이 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 일 경우,

FIFO : 15회
최적 페이지 교체: 9회
LRU: 12회


Q. FIFO와 LRU 알고리즘에 적합한 자료구조는 무엇인가?

A. FIFO는 메모리에 올라온 지 가장 오래된 페이지를 교체하는 방식으로 FIFO 방식으로 동작되는 큐(Queue)의 사용이 적합하고,

LRU의 경우 순위의 교체가 빈번하게 이루어지므로 배열이나 우선순위 큐 대신 연결리스트(Linked List)로 구현하는 것이 적합하다.


참고​



기여자​



Jongminfire
📦