출처 - https://github.com/jmxx219/CS-Study (opens in a new tab)

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

페이지 교체 알고리즘의 목표는 페이지 부재율을 최소화 하여 성능을 높이는 것

• 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 메모리에 적재되지 않았을 경우(Page Fault (opens in a new tab)), 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법
  • 메모리가 꽉 차있으면 기존 페이지 중 하나를 물리 메모리에서 디스크의 스왑 영역으로 보내야 하는데, 이떄 기존 페이지들 중에서 어떤 것을 내려서 교체할 지 결정함
  • 대상 페이지(victim page): 교체할 페이지
• 페이지 교체 알고리즘 종류
  • 간단한 알고리즘
    • Random: 무작위로 대상 페이지를 선정하여 페이지 교체
    • FIFO: 가장 먼저 들어와서 가장 오래 있었던 페이지 교체
  • 이론적 알고리즘
    • OPT: 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
  • 최적 근접 알고리즘
    • LRU: 가장 오랫동안 사용되지 않은 페이지 교체
    • LFU: 참조 횟수가 가장 적은 페이지 교체
    • NUR: 최근에 사용하지 않은 페이지 교체
    • FIFO 변형: SCR과 clock 알고리즘
• 페이지 교체 알고리즘의 성능 평가 기준
  • 같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수, 페이지 성공 횟수

◽ OPT(Optimal Replacement, 최적 교체)

• 개념
  • 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방법
  • 가장 이상적이고 효율적인 방법이지만 페이지의 참조 상황을 미리 예측해야 하기 떄문에 실현 가능성이 희박함
    • 실현이 거의 불가능하기 때문에 실제로 사용하기 보다는 연구 목적을 위해 사용됨
• 특징
  • 모든 페이지 교체 알고리즘 통틀어서 page fault 발생이 가장 적음
  • Belady's Anomaly 현상이 발생하지 않음
• 최적 페이지 교체 알고리즘에 근접하는 방법이 개발됨(최적 근접 알고리즘)
  • 최적 페이지 교체 알고리즘은 미래의 데이터를 참고하기 때문에 구현이 불가능하지만, 최적 근접 알고리즘은 과거의 데이터로부터 미래를 예측하기 때문에 최적 페이지 교체 알고리즘과 유사한 성능을 보임
  • LRU(최근 최소 사용 알고리즘), LFU(최소 빈도 사용 알괴즘), NUR(최근 미사용 알고리즘) 등 존재

◽ FIFO(First in First Out)

• 개념
  • 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 방법
  • 가장 구현이 간단한 방법이지만 성능은 좋지 않음
• 구현 방법
  • 큐로 구현하여 메모리의 맨 위에 있는 페이지가 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입됨
  • 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 보내짐
• 단점
  • 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어지는 문제점 존재
    • 이를 개선한 것이 2차 기회 페이지 교체 알고리즘(SCR)임
  • Belady's Anomaly (opens in a new tab) 현상이 발생함
    • Belady의 이상현상(Belady's Anomaly): 프레임의 개수가 많아져도 page fault가 줄어들지 않고 늘어나는 현상을 말함
    • 직관적으로는 프레임의 개수가 많아지면 page fault가 줄어들어야 하지만 FIFO 알고리즘을 사용하면 그렇지 않을 수 있음
    • 예시) 페이지 프레임의 개수에 따른 페이지 폴트 횟수 비교
      • 페이지 프레임 개수가 4개일 때 더 많은 페이지 폴트가 증가하는 것을 볼 수 있음
      
      페이지 프레임 3개 페이지 프레임 4개

◽ LRU(Least Recently Used)

• 개념
  • 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 방법
  • 가장 많은 운영체제가 채택하는 알고리즘으로, 간단하면서 효율적인 알고리즘
• 구현 방법 종류
  1. 카운터로 구현
     • 카운터로 각 페이지마다 사용된 시간을 저장하고, 가장 오랫동안 참조되지 않은 데이터를 제거함
       • 카운터는 각 페이지 별로 존재하는 논리적인 시계로, 카운터가 가장 작은 것이 가장 오래 전에 참조되었음을 의미함
     • 가장 작은 카운터를 찾기 위한 시간과 페이지 테이블이 변경될 때마다 시간 값을 관리해야 하기 때문에 오버헤드가 발생함
  2. 스택으로 구현
     • 참조된 순서만 기억하며 페이지 번호가 기록됨
     • 페이지가 참조되면 해당 페이지 번호를 삭제하고 다시 삽입하여 스택의 가장 위로 올림
       • 스택의 top은 항상 최근에 사용된 페이지들이 있고, 스택의 bottom에 가장 오랫동안 참조되지 않은 페이지가 존재하게 됨
     • 대상 페이지를 bottom에서 바로 찾을 수 있어 찾는 시간이 필요없고, 대신 참조할 때마다 스택의 위치 이동이 일어나기 떄문에 오버헤드가 발생함
• 특징
  • 시간 지역성 성질을 고려한 방법
  • 페이지가 언제 사용되었는지에 대한 시간 정보가 필요함
  • FIFO 알고리즘보다 성능이 우수하지만, OPT 알고리즘보다 성능이 떨어짐
  • Belady's Anomaly 현상이 발생하지 않음
  • LFU, NUR보다 비교적 구현이 쉽고 오버헤드가 적음
• 단점
  • 프로세스가 주기억장치에 접근할 때마다 참조되 페이지 시간을 기록해야하기 때문에 막대한 오버헤드가 발생함
  • 카운터나 스택, 큐와 같은 별도의 하드웨어 지원이 반드시 필요함

LRU에 근사한 알고리즘(LRU approximation algorithm)

LRU 구현에는 하드웨어의 지원이 있어야 하지만, 지원이 어려운 경우가 존재함
이때 하드웨어 대신 참조 비트(Reference bit)를 사용하여 LRU에 근사하는 여러 알고리즘이 사용됨

1. Reference bit Algorithm(참조 비트 알고리즘)

   • 참조 비트: 0으로 초기화 되고, 페이지가 참조되면 1로 바꾸어 저장되는 비트로 주기적으로 초기화됨
   • 참조 비트는 어떤 페이지가 특정 시점까지 사용되었는지, 사용되지 않았는지 알 수 있음
   • 하지만 페이지의 사용 순서까지는 모름

2. Additional-Reference Bits Algorithm(부가적 참조 비트 알고리즘)

   
   • 참조 비트 쉬프트 방식(reference bit shift)으로, 각 페이지 별로 8비트의 참조 비트를 만들어 사용함
   • 일정 시간 간격으로 기록함으로써 페이지 참조 순서에 대한 추가적인 정보를 얻을 수 있음(누가 먼저 사용되었는지 판별할 수 있음)
     • 일정한 시간 간격마다 모든 페이지의 참조 비트를 오른쪽으로 shift 연산을 수행하고, 도중에 참조를 하면 1로 set 함
     • 8비트의 참조 비트 기록을 정수로 변환했을 때, 가장 낮은 정수값을 가지는 페이지가 가장 오랫동안 참조되지 않은 페이지가 됨
   • 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 공간이 많아짐

3. Second-Chance Algorithm (2차 기회 알고리즘)

   • FIFO 기반으로, 한 번의 기회를 더 주는 알고리즘
   • 페이지가 선택될 때마다 참조 비트를 확인하여 참조 비트가 0이면 바로 교체하고, 1이면 한 번 더 기회를 주고 다음 페이지를 선택하는 알고리즘

◽ LFU(Least Frequently Used)

• 개념
  • 참조 횟수가 가장 적은 페이지를 교체하는 방법
    • 만약 대상 페이지가 여러 개인 경우, LRU 알고리즘에 따라 페이지를 교체함
  • 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정함
• 특징
  • LRU는 직전 참조된 시점만 반영하지만, LFU는 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있음
  • LRU와 성능이 비슷하며, FIFO 보다 성능이 우수함
• 종류
  • Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
  • Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식
• 단점
  • 낭비되는 메모리 공간이 많음
    • 페이지 접근 빈도를 표시하기 위한 추가 공간 필요
  • 초기에 한 페이지를 집중적으로 참조하다가 이후에 다시 참조하지 않는 경우 문제가 될 수 있음
    • 앞으로 사용하지 않아도 초기에 사용된 참조 횟수가 높아서 메모리에 계속 남아있기 때문

◽ NUR = NRU(Not Used Recently, Not Recently Used)

• 개념
  • 최근에 사용하지 않은 페이지를 교체하는 방법
  • LRU와 LFU의 불필요한 공간 낭비 문제를 해결한 알고리즘
• 구현 방법
  • 최근 사용 여부를 확인하기 위해 각 페이지마다 두 개의 비트(참조 비트, 변형 비트)를 사용하여 미래를 추정함
    • 참조 비트: 초기값이 0이며, 페이지에 접근(read/execute)하면 1이 됨
    • 변형 비트: 초기값이 0이며, 페이지가 변경(write/append)하면 1이 됨
  • 각 페이지의 상태
    • Class 0 - (0, 0): 모든 페이지의 초기 상태
    • Class 1 -(0, 1): 페이지에 쓰기 또는 추가와 같은 변경이 일어난 경우
    • Class 2 -(1, 0): 페이지에 읽기 또는 실행과 같은 접근이 발생한 경우
    • Class 3 -(1, 1): 접근과 변경 두 가지 연산이 모두 발생한 경우
  • NUR에서는 대상 페이지를 선정할 때 페이지를 위와 같이 4가지의 클래스로 나누고, 가장 낮은 클래스의 랜덤한 페이지를 선택함
    • 우선 고려 대상은 참조 비트임
  • 모든 페이지의 비트가 (1, 1)일 경우에는 어떤 페이지가 더 자주 사용되는지 알 수 없어 교체 알고리즘을 정상적으로 사용할 수 없음
    • 따라서 NRU에서 모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 (0, 0)으로 초기화 함(reset)
• 특징
  • LRU와 LFU와 성능이 비슷하며, FIFO보다 성능이 우수함
  • NUR은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 수 있음
  • 쉽게 구현할 수 있음
• 단점
  • 각 페이지의 참조를 유지 및 업데이트하고 비트를 수정하기 위해서는 추가적인 하드웨어 지원이나 소프트웨어 오버헤드가 필요함
    • 이 때문에 실제로 LRU 알고리즘을 더 많이 사용함

FIFO 변형 알고리즘(SCR, clock)

• FIFO 알고리즘을 기본으로 하되 페이지에 접근할 때마다 순서의 변화를 주어 성능을 향상한 알고리즘
• SCR Algorithm과 clock Algorithm 존재

◽ SCR(Second Chance Replacement, 2차 기회 페이지 교체)

• 개념

  • FIFO 기법의 단점을 보완하는 기법으로, 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하는 방법
  • 한 페이지에 접근했을 때 page fault 없이 성공하면 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외시킴
    • 즉, 성공할 기회를 한 번더 주는 알고리즘

• 구현 방법

  • FIFO 알고리즘과 reference bit을 함께 사용함
    • 페이지 교체 수행 중 참조 비트가 0일 경우에는 교체하고, 참조 비트가 1일 경우에는 참조 비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백 시켜 다음 순서를 기다리게 함
  1. FIFO 순서대로 page를 검색함
     1. reference bit이 0이면 page를 교체함
     2. reference bit이 1이면 기회를 한번 더 줌
        1. reference bit을 0으로 clear함
        2. page를 큐의 뒤에 삽입하고 다음 page 검사로 옮김
        • reference bit을 0으로 초기화하기 때문에 다음 검사 때는 교체의 대상이 될 수 있음

• 특징

  • 큐의 맨 뒤로 옮기면 대상 페이지로 선정될 확률이 줄어드는 특징을 이용함
  • LRU, LFU, NUR보다 성능이 약간 낮고, FIFO보다 성능이 약간 높음

• 단점

  • 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가됨

◽ clock 알고리즘

• 개념
  • SCR을 원형 큐를 이용하여 구현한 알고리즘
  • 한 바퀴를 도는 동안 사용되지 않은 페이지는 참조 되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘
• 구현
  • 각 페이지에 참조 비트를 사용해서 교체 대상을 선정함
    • 초기값은 0이고, 페이지를 성공적으로 참조하면 0에서 1로 변경됨
  • 대상 페이지를 가리키는 포인터를 사용하는데, 포인터가 큐의 맨 아래로 내려가면 시계처럼 다시 큐의 처음을 가리키게 됨
    1. 참조 비트가 0인 것을 찾을 떄까지 포인터를 이동시킴
    2. 참조 비트가 1인 경우, 0으로바 바꾼 후 건너뜀
    3. 참조 비트가 0인 경우 페이지를 교체함
• 특징
  • LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만, 교체 되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 않음
    • LRU: 가장 오랫동안 사용되지 않은 페이지를 찾는데 효과적
    • clock: 최근에 참조된 페이지를 보존하는데 효과적
  • 참조 비트가 1인 페이지를 대상 페이지에 제외함으로써 SCR처럼 기회를 한 번 더 제공함
    • 하지만 대상에서 제외되는 경우는 단 한 번뿐이고, 참조 비트가 1이면 다시 0으로 바꾸기 때문에 한 바퀴를 돌아 포인터가 오면 제외하지 않음
  • NUR에 비해 각 페이지 당 참조 비트 하나만 추가하면 되기 때문에 추가 공간이 적게 듦
• 단점
  • 알고리즘이 복잡하고 계산량이 많음

Ref

• [OS] 페이지 교체 알고리즘 (FIFO, LRU, LFU, NRU, NUR) (opens in a new tab)
• OS는 할껀데 핵심만 합니다. 17편 페이지 교체 알고리즘 (opens in a new tab)
• [운영체제] 페이지 교체 알고리즘 (opens in a new tab)