2018년 1회 정보처리기사 기출문제 53번

53. 페이지 교체기법 중 LRU와 비슷한 알고리즘 이며, 최근에 사용하지 않은 페이지를 교체하는 기법으로 시간 오버헤드를 줄이기 위해 각 페이지마다 참조 비트와 변형 비트를 두는 교체기법은?

    ① FIFO              ② LFU

    ❸ NUR              ④ OPT

 

300x250

---

🔍 문제 요약

최근에 사용하지 않은 페이지를 교체하며, 참조 비트(Reference Bit)와 변형 비트(Modified Bit)를 이용하여 시간 오버헤드를 줄인 알고리즘은?

 

---

🧠 보기 분석

번호 기법 설명 적합 여부

① FIFO (First-In First-Out)	먼저 들어온 페이지를 먼저 교체	LRU와 무관 ❌
② LFU (Least Frequently Used)	가장 적게 사용된 페이지를 교체	LRU와 구조 다름 ❌
❸ NUR (Not Used Recently) ✅	참조 비트 + 변형 비트 이용해서 최근 사용되지 않은 페이지 교체	✅ 정답!
④ OPT (Optimal)	앞으로 가장 오래 사용되지 않을 페이지를 교체 (이론적인 최적 방법)	실제 구현 불가 ❌

---

✅ 정답은: ❸ NUR (Not Used Recently)

📌 NUR 기법이란?

• LRU의 대체 알고리즘 (실제로 구현이 쉬움)
• 각 페이지에 두 개의 비트 사용:
  • R (Reference Bit, 참조 비트): 최근에 접근했는가?
  • M (Modified Bit, 변형 비트): 페이지가 변경되었는가?
• OS가 주기적으로 이 비트를 검사하여, 가장 덜 사용되고, 수정되지 않은 페이지를 먼저 제거함
• 오버헤드 ↓, LRU처럼 동작하면서도 구현이 간단함

---

🔁 관련 기법 비교표

알고리즘 개념 실제 구현 여부 오버헤드

LRU	가장 오래 사용하지 않은 페이지 제거	구현 어려움	⛔ 높음
NUR	최근 사용 안 한 페이지 제거 (R/M 비트 기반)	✅ 쉬움	✅ 낮음
FIFO	가장 오래된 페이지 제거	쉬움	낮음
OPT	앞으로 가장 오래 사용 안 할 페이지 제거	❌ 이론 전용	불가능

---

🎯 최종 정답

➡️ 정답: ❸ NUR