페이지 교체

  • 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다.
    이때, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
    이 경우에는 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내어 메모리에 빈 공간을 확보하는 작업이 필요하다.
    -> 이것을 페이지 교체(page replacement)라고 한다.
  • 페이지 교체를 할때, 어떠한 프레임에 있는 페이지를 쫓아낼 것인지를 결정하는 알고리즘을 페이지 교체 알고리즘(replacement algorithm)이라고 한다.
    (가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내쫓는 것이 성능을 향상시킬 수 있는 방안이다.)
  • 페이지 교체 알고리즘의 성능은 주어진 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가할 수 있다.

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

  • 최적 페이지 교체(Optimal Page Replacement)
    앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법.
    미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전재하에 알고리즘을 운영하므로 현실적으로 구현이 어렵다.
    페이지 부재율이 가장 낮은 효율적인 알고리즘이다.

  • FIFO(First-In-First-Out) 알고리즘
    페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.
    페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기때문에 비효율적인 상황이 발생할 수 있다.
    빌레이디의 모슨(Belady's Anomaly)현상이 발생할 수 있다.
    (빌레이디 모순 현상 : 페이지 프레임 수가 많으면 페이지 부재수가 줄어드는 것이 일반적이지만, 페이지 프레임수를 증가시켰음에도 페이지 부재가 더 많이 일어나는 현상을 의미)

    content01

  • LRU(Least Recent Used) 알고리즘
    최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법.
    (마지막 참조시점이 가장 오래된 페이지 교체)
    시간지역성(temporal locality)의 성질을 고려해 고안된 알고리즘이다.
    (시간 지역성 : 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질)
    계수기(Counter)나 스택(Stack)과 같은 별도의 하드웨어가 필요하며, 시간적인 오버헤드가 발생된다. (실제로 구현이 어려움)
    (계수기 : 각 페이지별로 존재하는 논리적인 시계(Logical Clock)로, 해당 페이지가 사용될때마다 0으로 클리어 시킨 후 시간을 증가시켜 시간이 가장 오래된 페이지를 교체)

    content02

  • 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에 비해 교체 페이지의 선정이 훨씬 빠르게 결정된다.
      따라서, 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.

출저