[운영체제] 페이지 교체 전략

 

페이지 교체 전략이란 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지 할당을 위해 어떤 페이지 프레임을 선택하여 교체할지 결정하는 기법이다.

페이지 부재(Page Fault, PF)란 메모리에 적재된 페이지 중 사용해야 하는 페이지가 없을 때를 의미한다.

---

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. NUR

Not Used Recently

 

최근에 사용하지 않은 페이지를 교체하는 기법

최근 사용 여부를 확인하기 위해 참조 비트와 변경 비트, 2개의 비트가 사용된다.

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

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

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

교체 순서 우선순위

 

---

6. SCR

Second Chance Replacement

 

가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 기법

FIFO 기법의 단점 보완하는 기법이다.

최근 참조 여부를 저장하는 참조 비트를 사용.

참조 비트: 0(최근 참조한 적 없음), 1(페이지 참조 시 1로 세팅)

FIFO 대기열 큐의 front의 참조 비트가 1인 경우 페이지 교체하지 않고 참조 비트를 0으로 바꾸고 큐의 뒤로 보낸다. (기회 한 번 더 줌)

0인 경우는 해당 페이지가 교체됨.

---

참고 : 위키백과, 2016 시나공 정보처리기사 필기

LRU참고 : http://judoboyjin.egloos.com/4545185