NUR (페이지 교체 알고리즘)

NUR(Not Used Recently, 최근에 사용되지 않음) 알고리즘은 페이지 교체 알고리즘 중 하나로, LRU를 단순화하여 구현 비용을 줄인 근사 알고리즘이다. 하드웨어 지원 없이도 사용할 수 있으며, 최근에 참조되지 않은 페이지를 우선적으로 교체하는 방식을 취한다.

1 개념

• NUR은 참조 비트(reference bit)와 변경 비트(modified bit)를 사용하여 각 페이지의 사용 상태를 판단한다.
• 운영체제가 주기적으로 모든 페이지의 참조 비트를 0으로 초기화함
• 교체 대상 선택 시 각 페이지의 비트를 기반으로 우선순위를 부여함

2 페이지 분류

각 페이지는 (R: 참조 비트, M: 변경 비트)의 조합에 따라 다음 네 가지 클래스로 나뉜다:

1. 클래스 0: R = 0, M = 0 → 최근에 사용되지 않았고 수정되지 않음 (최우선 제거 대상)
2. 클래스 1: R = 0, M = 1 → 최근에 사용되지 않았지만 수정됨 (제거 시 디스크 기록 필요)
3. 클래스 2: R = 1, M = 0 → 최근에 사용되었고 수정되지 않음
4. 클래스 3: R = 1, M = 1 → 최근에 사용되었고 수정됨 (제일 나중에 제거함)

3 동작 방식

1. 주기적으로 참조 비트를 0으로 초기화 (타이머 또는 페이지 교체 횟수 기준)
2. 페이지 부재 발생 시, 0~3 순서로 클래스를 검사하여 가장 낮은 클래스에 속하는 페이지를 선택
3. 동일 클래스 내에서는 FIFO 방식 적용 가능

4 장점

• LRU보다 구현이 간단하고 성능도 준수함
• 하드웨어 지원 없이도 운영체제 수준에서 구현 가능
• 페이지 변경 여부(M 비트)를 고려해 디스크 입출력을 최소화함

5 단점

• 정확한 LRU가 아님 (최근 사용 시점 정확히 판단하지 못함)
• 참조/변경 비트가 필요하며, 일부 시스템에서는 해당 비트를 직접 사용할 수 없음
• NUR 주기 설정이 적절하지 않으면 성능 저하 가능

6 활용

• 임베디드 시스템, 소형 운영체제 등에서 LRU 대체 알고리즘으로 사용
• 하드웨어 자원이 제한된 환경에서 효율적인 페이지 교체 전략으로 활용

7 같이 보기

• 페이지 교체 알고리즘
• LRU (페이지 교체 알고리즘)
• FIFO (페이지 교체 알고리즘)
• 참조 비트
• 변경 비트
• Clock 알고리즘

8 참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson
• Stallings, W. (2018). Operating Systems: Internals and Design Principles. Pearson