페이지 교체 알고리즘

1. 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 하는데, 물리적 메모리에 빈 프레임이 없을 수 있다.

2. 메모리에 올라와 있는 페이지 중 하나를 디스크로 내보내어 (Swap Out) 메모리에 빈 공간을 확보하고, 새로운 페이지를 메모리에 올린다.
   → Page replacement

   • Swap out 된 페이지: Victim page
   • Page replacement algorithm: 페이지 교체 알고리즘은 victim page를 결정하는 방법을 의미하며 다양한 페이지 교체 알고리즘 중에서 가장 적합한 알고리즘을 선택하여 시스템의 성능을 최적화 해야한다.

---

1. OPT (Optimal Algorithm)

• 가장 성능이 좋은 페이지 교체 알고리즘으로, 가장 먼 미래에 참조 될 페이지를 victim page로 설정 (LFD : Longest Foward Distance)

• offline algorithm의 한 형태

• 미래의 페이지 참조 패턴을 내부적으로 알 수 없기 때문에 실제로 사용하기 어려운 알고리즘
  → OPT는 이론적으로 최적의 성능을 제공하기 때문에 다른 페이지 교체 알고리즘들과의 성능 비교에서 상한선을 제공

• 0 → 1 → 2 → 3 → 4 → 2 (프레임 사이즈: 3)

  • 3이 들어올 때 가장 나중에 참조 될 2와 스와핑이 발생한다.
    

---

2. FIFO (First In First Out)

• 가장 먼저 메모리에 들어온 페이지를 가장 먼저 교체하는 알고리즘

• FIFO 알고리즘은 페이지를 Queue 데이터 구조로 관리하고, 페이지 폴트가 발생하면 가장 먼저 큐에 들어온 페이지를 교체

• FIFO 알고리즘은 페이지의 접근 패턴과 상관 없이 동작하기 때문에 최적의 성능을 보장하지는 않음

  • Belady's Anomaly: 프레임 수를 증가시켜도 페이지 폴트가 감소하지 않는 이상 현상이 나타날 수 있다.
    • 프레임 수를 늘려서 더 많은 페이지를 메모리에 보관해봐도 페이지 폴트가 예상보다 더 자주 발생하는 상황
    • FIFO 알고리즘은 페이지 교체를 예측하지 못하고 무작위로 수행하기 때문

• 1 → 3 → 0 → 3 → 5 → 6 → 3 (프레임 사이즈: 3)

  • page fault: 6
    

---

3. LRU (Lesat Recently Used)

• 가장 최근에 사용되지 않은 (참조가 오랫동안 되지 않은) 페이지를 스왑 아웃하는 알고리즘

• 성능이 좋은 편이며 많은 운영 체제에서 채택

• temporal locality 이용: 가장 최근에 참조된 페이지가 가장 가까운 미래에 다시 참조될 가능성이 높다.

• 페이지 교체를 위해 페이지에 시간 또는 접근 순서를 기록하는 카운터를 사용

  • 카운터를 유지하기 위해 추가적인 메모리 사용과 오버헤드 발생 가능성 존재
    → 계수기 또는 스택과 같은 자료구조를 사용

• 7 → 0 → 1 → 2 → 0 → 3 → 0 → 4 (프레임 사이즈: 3)

  • page fault : 6
    

---

4. LFU(Least Frequently Used)

• 가장 사용 빈도가 적은 페이지를 스왑 아웃하는 알고리즘
  → 빈도가 동일한 경우에는 오랫동안 사용되지 않은 페이지를 교체

• 0 → 1 → 2 → 0 → 0 → 1 → 2 → 3 (프레임 사이즈: 3)

  • 3이 들어올 때, 가장 빈도 수가 적은 1 또는 2 중에 더 오랫동안 사용되지 않은 페이지인 1을 교체
    

---

5. NRU (Not Recently Used)

• Clock algorithm

• LRU 알고리즘의 개선형태이며, 오버헤드를 줄이고 메모리 공간 낭비를 최소화 하기위해서 참조비트와 변경비트를 이용해 대상 페이지를 선정한다.

  • 참조비트 : 해당 페이지가 read / execute
  • 변경비트 : 해당 페이지가 write / append
    
  • 페이지를 4개의 클래스로 나눕니다. 이 클래스에 따라 페이지 교체 대상을 선택하며, 가장 낮은 클래스에 속한 페이지가 교체 대상
    → 참조비트가 우선 고려 대상이며 동일한 우선순위의 페이지가 여러개일 경우 무작위 방법 등을 사용한다.

• NRU 과정
  

• LRU와 성능은 비슷하지만 메모리 공간 낭비가 적다.

  • 성능: NRU < LRU
    → NRU가 페이지를 4개의 클래스로 나누고 선택하는 과정에서 일부 정보 손실이 발생할 수 있기 때문

• LRU와 비교하면 NRU는 상대적으로 구현이 복잡

  • NRU에서 페이지를 클래스로 나누고 관리하는 데 추가 비트 및 컨트롤이 필요하며, 이로 인해 하드웨어 및 소프트웨어에서 오버헤드가 발생

• NRU VS LRU

  • NRU 알고리즘과 LRU 알고리즘은 최근에 참조되지 않은 페이지를 교체
  • NRU: 페이지를 변경 여부와 참조 여부에 따라 4개의 클래스로 나누고 Victim 페이지를 선택
  • LRU: 페이지의 참조 시간 순서를 기반으로 페이지를 관리하며, 변경 여부를 고려하지 않음