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

페이지 교체란?

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

이러한 경우, 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하여 새로운 페이지를 메모리에 올려야 한다.
이러한 과정을 페이지 교체라고 부르며, page-out이 된 페이지를 희생양 페이지(victim page)라고 한다.

 

* 페이지 부재란? CPU가 접근하려는 페이지가 메모리에 없는 상황

 

---

 

페이지 교체 알고리즘의 종류

 

• OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO - First In First Out
• LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
• LFU - Least Frequently Used : 사용 빈도가 가장 작은 페이지 교체
• MFU - Most Frequently used : 사용 빈도가 가장 많은 페이지 교체
• NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체

 

---

 

1. OPT

OPTimal Replacement. 최적 교체

 

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법.
• 앞으로 나올 페이지들의 호출 순서와 참조 상황을 예측해야 하므로 실현 가능성이 희박하다.

 

2. FIFO

First In First Out

 

• 가장 먼저 들어온 페이지(가장 오래 있었던 페이지)를 교체하는 기법
• 각 페이지가 주기억장치에 적재될 때마다 시간을 기억해야 한다.
• 이해, 설계가 쉽다.
• 벨레이디의 모순 현상이 발생할 수 있다.

       * 벨레이디의 모순(Belady's Anomaly) : 페이지 수를 증가했는데 페이지 부재가 증가하는 경우 발생.

 

3. LRU

Least Recently Used

 

• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 각 페이지마다 계수기나 스택을 둬서 가장 오랫동안 사용하지 않은 페이지인지 판별함.

       계수기: 페이지 호출 시 해당 호출 시간 저장.
       스택: 페이지 호출 시 페이지 번호를 스택에 저장.

 

• 페이지 번호가 이미 스택에 있다면 해당 번호 pop하고 새로 push 해줌.
• 스택의 가장 아래에 있는 페이지가 가장 오래된 것임.

 

4. LFU

Least Frequently Used

 

• 사용 빈도가 가장 적은 페이지를 교체하는 기법
• 초기에 많이 사용되고 후반에 잘 사용되지 않는 페이지가 계속 적재될 가능성도 있음(단점)

 

 

5. MFU

Most Frequency Used

 

• LFU 알고리즘과 반대로 사용 빈도가 가장 많은 페이지를 교체하는 기법
• 참조 횟수가 적은 페이지가 최근에 참조된 것으로 보고 앞으로 사용될 가능성이 높다고 판단한 알고리즘

 

6. NUR

Not Used Recently

 

• 최근에 사용하지 않은 페이지를 교체하는 기법
• 최근 사용 여부를 확인하기 위해 참조 비트와 변경 비트, 2개의 비트가 사용된다.

       * 참조 비트(Reference Bit) : 0(최근 사용하지 않음), 1(최근 사용함).

         최근 사용되지 않은 페이지 확인. 주기적으로 리셋(reset). 최근 사용시 세팅(set)

       * 변경 비트(Modified Bit) : 해당 페이지에 수정이 있을 시 세팅(set)

교체 순서 우선순위