303. NUR (Not Used Recently)

핵심 인사이트 (3줄 요약)

본질: NUR (Not Used Recently)은 페이지 교체 시 **참조 비트(Reference Bit)**와 **변형 비트(Modified Bit)**의 조합을 통해, "최근에 사용되지 않은 페이지를 우선적으로 쫓아내는" 합리적 추론 기반의 알고리즘이다.

가치: 완벽한 과거 이력을 추적하는 대신 단 2비트의 상태 정보만으로 페이지의 가치를 4개 그룹으로 분류하며, 특히 **'수정되지 않은 페이지'**를 먼저 버려 디스크 쓰기 오버헤드를 줄이는 실용성에 집중한다.

융합: 클럭 알고리즘(Clock Algorithm)의 이론적 모태가 되는 개념이며, 하드웨어가 비트를 찍어주고 소프트웨어가 주기적으로 비트를 초기화하는 하드웨어-소프트웨어 협력형 메모리 관리의 전형이다.

Ⅰ. 개요 및 필요성

개념: 각 페이지에 부착된 2개의 상태 비트(참조 비트, 변형 비트)를 사용하여 페이지들을 4가지 등급으로 나누고, 가장 낮은 등급의 페이지부터 교체 대상으로 선정하는 방식이다.
필요성: LRU는 성능이 좋지만 구현이 너무 비싸다. 반면 FIFO는 너무 멍청하다. NUR은 **"2비트 정도의 힌트만 있으면 LRU와 90% 이상 비슷한 효과를 낼 수 있다"**는 효율성 중심의 사고방식에서 탄생했다. 특히 내용이 바뀐 페이지(Dirty)를 쫓아낼 때 드는 디스크 쓰기 비용(Penalty)을 알고리즘의 판단 기준에 넣었다는 점이 핵심이다.
💡 비유: 중고차 시장에서 차를 고를 때, 모든 주행 기록을 다 뒤지는 대신(LRU), **"최근에 시동 걸었나?(참조)"**와 "사고 나서 수리했나?(변형)" 두 가지만 보고 가성비 좋은 차를 골라내는 것과 같습니다.
등장 배경: 초기 운영체제에서 메모리 관리의 병목은 '페이지 교체 결정 시간'과 '디스크 I/O 시간'이었다. NUR은 이 두 가지 병목을 동시에 잡기 위해 비트 연산만으로 즉각적인 결정을 내릴 수 있도록 설계되었다.

┌──────────────────────────────────────────────────────────────┐
│             NUR (Not Used Recently)의 4단계 우선순위 그룹              │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  [그룹 1] (0, 0): 참조 안 됨, 수정 안 됨 -> **최우선 교체 대상**       │
│  [그룹 2] (0, 1): 참조 안 됨, 수정 됨 -> 교체 후보 (쓰기 비용 발생)     │
│  [그룹 3] (1, 0): 참조 됨, 수정 안 됨 -> 살려둠 (기회 부여)            │
│  [그룹 4] (1, 1): 참조 됨, 수정 됨 -> **최후순위 교체 대상**           │
│                                                              │
│  * 판단 순서: (참조 비트, 수정 비트)                                 │
└──────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 방 정리를 할 때, "오래 안 쓴 물건" 중에 "버려도 엄마한테 안 혼나는 것(Clean)"을 1순위로 버리고, "공부할 때 썼던 것(Referenced)"이나 "내가 직접 고친 소중한 것(Modified)"은 끝까지 남겨두는 영리한 정리법입니다.

Ⅱ. 아키텍처 및 핵심 원리

2비트의 상호작용 메커니즘

참조 비트 (Reference Bit):
- 하드웨어(MMU)가 해당 페이지를 읽거나 쓸 때 무조건 1로 세팅한다.
- 소프트웨어의 개입: OS는 일정 시간마다(예: 100ms) 모든 페이지의 참조 비트를 0으로 초기화(Reset)한다. 그래야 "최근(Recently)"의 기준이 유지된다.
변형 비트 (Modified / Dirty Bit):
- 하드웨어가 해당 페이지에 '쓰기' 연산을 할 때 1로 세팅한다.
- 이 비트는 페이지가 디스크로 완전히 나갈 때까지 유지된다.

교체 우선순위의 논리 (Victim Selection)

NUR은 다음 순서로 Victim을 찾는다.

1순위 (0,0): 최근에 읽지도 않았고 내용도 그대로다. 그냥 지우면 끝이므로 가장 경제적이다.
2순위 (0,1): 최근에 읽지는 않았지만 예전에 내용이 바뀌었다. 쫓아내려면 디스크에 써야 하는 수고가 들지만, 안 쓰이는 건 확실하니 버린다.
3순위 (1,0): 최근에 읽었다. 곧 또 쓰일 확률이 높으므로 살려준다.
4순위 (1,1): 최근에 읽었고 내용도 바뀌었다. 시스템에서 가장 귀하신 몸이다.
📢 섹션 요약 비유: 회사에서 인원 감축을 할 때, "일도 안 하고(R=0) 자기 자리 정돈도 안 된(M=0)" 직원을 1순위로 내보내고, "일은 잘하는데(R=1) 사고를 좀 친(M=1)" 핵심 인재는 끝까지 보호하는 인사 고과 시스템입니다.

Ⅲ. 비교 및 연결

NUR vs LRU vs FIFO 비교

비교 항목	FIFO	NUR (NRU)	LRU
기준	시간 (순서)	최근성 + 비용 (2비트)	사용 이력 (순위)
적중률	낮음	중상 (실용적)	최상 (이론적)
오버헤드	없음	낮음 (비트 초기화만 필요)	매우 높음
성격	맹목적	합리적 추론	철저한 기록

NUR과 클럭 알고리즘의 관계

NUR은 '분류 방법'에 대한 이론이고, 이를 원형 큐 포인터로 구현한 실체가 바로 클럭 알고리즘이다. 학술적으로는 NRU (Not Recently Used)라고도 불리며, 현대 OS 교체 로직의 뼈대를 이룬다.

📢 섹션 요약 비유: NUR이 "어떤 기준으로 벌점을 줄 것인가"라는 교칙이라면, 클럭 알고리즘은 선생님이 "교실을 돌며 벌점을 체크하는 행위" 그 자체입니다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

데이터베이스 엔진의 버퍼 풀 교체 (PostgreSQL) 데이터베이스는 OS보다 메모리를 훨씬 더 많이 쓴다. PostgreSQL 같은 DB는 내부적으로 NUR의 원리를 딴 Clock Sweep 알고리즘을 쓴다. 수만 개의 데이터 페이지를 다 LRU로 줄 세우면 쿼리 실행보다 장부 정리가 더 오래 걸리기 때문이다. "방금 쿼리에서 썼나?" 비트만 확인하며 빠르게 훑고 지나가는 NUR 방식이 대용량 데이터 처리의 숨은 공신이다.
저전력 임베디드 장치의 메모리 관리 배터리 효율이 중요한 워치나 IoT 기기에서는 CPU가 매번 메모리 사용 시간을 기록하는 것이 큰 부담이다. NUR은 하드웨어가 비트를 찍어주는 기능만 있으면 소프트웨어 부하가 거의 없으므로, 저전력 환경에서 메모리 효율을 극대화하는 가장 선호되는 방식이다.

도입 체크리스트

비트 리셋 주기 튜닝: 참조 비트를 너무 자주 리셋하면 모든 페이지가 (0,X) 그룹이 되어 FIFO처럼 변하고, 너무 가끔 리셋하면 모든 페이지가 (1,X) 그룹이 되어 교체 대상을 못 찾는다. 시스템 워크로드에 맞는 적절한 리셋 주기가 성능의 핵심이다.
📢 섹션 요약 비유: 일기 검사를 매일 하면 어제 일만 기억나고(리셋 과다), 1년에 한 번 하면 뭐가 중요한지 모릅니다(리셋 부족). 일주일 단위(적절한 주기)로 검사해야 누가 공부를 꾸준히 하는지 알 수 있습니다.

Ⅴ. 기대효과 및 결론

정량적 기대효과

디스크 I/O 절감: Modified Bit를 고려함으로써, 수정 안 된 페이지를 우선 교체하여 불필요한 디스크 쓰기 횟수를 30~50% 줄일 수 있다.
CPU 오버헤드 최소화: 복잡한 정렬 알고리즘 없이 단순 비트 비교만으로 교체가 가능하여 컨텍스트 스위칭 시간을 단축한다.

결론

NUR(Not Used Recently)은 "완벽한 기억보다는 영리한 짐작"이 낫다는 것을 증명한 알고리즘이다. 모든 참조 기록을 보관하려는 욕심을 버리고, 단 2비트의 단서와 주기적인 망각(Reset)을 통해 현대 컴퓨팅의 거대한 메모리 바다를 효율적으로 항해하는 지혜를 제공한다.

📢 섹션 요약 비유: NUR은 가장 적은 노력으로 가장 큰 효과를 내는 '파레토 법칙'의 하드웨어적 실천입니다. 사소한 2비트가 시스템 전체의 생사여탈권을 쥐고 있는 셈입니다.

📌 관련 개념 맵

개념 명칭	관계 및 시너지 설명
참조 비트	페이지가 읽히거나 쓰였음을 알리는 '최근성'의 증거.
더티 비트	내용이 바뀌었음을 알리는 '비용'의 증거 (Modified Bit).
클럭 알고리즘	NUR의 4그룹 분류 체계를 시계 바늘 순회 방식으로 구현한 실체.
LRU	NUR이 지향하는 목표 지점이자, 시간적 지역성을 극한으로 추적하는 모델.
2차 기회	NUR의 (1,0) 그룹 페이지에 대해 비트를 깎으며 한 번 더 살려주는 철학.

👶 어린이를 위한 3줄 비유 설명

NUR은 장난감 상자에서 어떤 걸 버릴지 결정할 때 두 가지 질문만 던지는 거예요. "오늘 가지고 놀았니?", "망가져서 고쳤니?"
오늘 놀지도 않았고 멀쩡한 장난감(0,0)은 미련 없이 버리고, 내가 고친 소중한 장난감(M=1)은 좀 더 아껴주는 식이죠.
질문 두 개만으로 엄청 빠르게 정리 대상을 고를 수 있어서, 엄마(컴퓨터)가 아주 좋아하는 청소 방법이랍니다!