NUR 페이지 교체 알고리즘: 참조·수정 비트로 교체 후보 고르기

페이지 교체에서 NUR이 보는 정보

가상메모리에서 빈 프레임이 필요해졌을 때, 어떤 페이지를 내보낼지는 시스템 성능에 직접 영향을 준다. NUR(Not Used Recently)은 정확한 최근 접근 시간을 모두 기록하는 대신 참조 비트와 수정 비트만으로 사용 패턴을 판단한다. LRU를 완전히 구현하기 어려운 환경에서 그 근사치로 사용할 수 있는 방식이다.

이 알고리즘은 최근에 참조되지 않은 페이지가 가까운 미래에도 참조되지 않을 가능성이 높다고 가정한다. 또한 수정된 페이지를 교체하려면 디스크 쓰기가 필요하므로, 참조되지 않았고 수정되지도 않은 페이지가 가장 부담이 적은 후보가 된다.

참조 비트는 페이지 접근이 있었을 때 1이 되고, 수정 비트는 페이지에 쓰기가 발생했을 때 1이 된다.

⤢✕

비트 조합이 만드는 교체 후보

NUR은 두 비트의 상태를 기준으로 유효한 페이지를 네 부류로 나눈다. 우선순위는 최근 사용 여부를 먼저, 디스크 쓰기 비용을 함께 고려해 정해진다.

클래스	참조 비트	수정 비트	상태와 교체 비용	교체 우선순위
0	0	0	최근 참조·수정이 없고 디스크 쓰기가 불필요	1순위
1	0	1	최근 참조는 없지만 디스크 쓰기가 필요	2순위
2	1	0	최근 사용됐지만 디스크 쓰기는 불필요	3순위
3	1	1	최근 사용됐고 디스크 쓰기도 필요	4순위

페이지 폴트가 발생하면 클래스 0부터 후보를 찾는다. 해당 클래스가 없으면 클래스 1, 클래스 2, 클래스 3 순서로 넘어간다. 클래스 1과 클래스 3을 내보낼 때는 수정된 내용을 디스크에 기록해야 한다.

⤢✕

모든 페이지가 클래스 3인 상황에서는 참조 비트를 모두 0으로 초기화한 뒤 다시 후보를 찾는다. 그러면 수정 비트 상태에 따라 클래스 0 또는 클래스 1 후보가 생긴다.

참조 비트를 시간 정보로 쓰는 방식

참조 비트는 마지막 접근 시각 자체를 담지 않는다. 대신 운영체제가 일정 시점마다 비트를 0으로 되돌려, 초기화 이후 접근된 페이지와 그렇지 않은 페이지를 구분한다. 이 과정이 없으면 오래전의 접근도 계속 최근 사용으로 남는다.

초기화는 타이머 인터럽트, 시스템 클럭 틱, 또는 페이지 폴트 횟수를 기준으로 수행할 수 있다. 예시로 일정 시간마다 20ms 간격의 타이머 인터럽트를 사용할 수 있다. 초기화 대상은 참조 비트이며, 수정 비트는 디스크 동기화 필요성을 보존하기 위해 유지한다.

⤢✕

수정 비트는 CPU가 메모리에 쓰기 작업을 할 때 하드웨어가 자동으로 설정한다. 페이지를 디스크에 기록한 뒤, 페이지 교체 뒤, 또는 명시적 플러시 뒤에는 초기화할 수 있다. 수정되지 않은 페이지는 디스크 쓰기를 생략할 수 있으므로, 이 비트는 I/O 최적화와 메모리·디스크 일관성 유지에 쓰인다.

교체 로직을 코드로 옮기면

다음 의사 코드는 페이지 테이블을 순회해 각 클래스로 나눈 뒤, 우선순위에 따라 희생 페이지를 선택한다.

def nur_page_replacement():
    # 클래스별 페이지 리스트
    class_0 = []  # (R=0, M=0)
    class_1 = []  # (R=0, M=1)
    class_2 = []  # (R=1, M=0)
    class_3 = []  # (R=1, M=1)

    # 모든 페이지를 클래스별로 분류
    for page in page_table:
        if not page.valid:
            continue

        r = page.reference_bit
        m = page.modified_bit

        if r == 0 and m == 0:
            class_0.append(page)
        elif r == 0 and m == 1:
            class_1.append(page)
        elif r == 1 and m == 0:
            class_2.append(page)
        else:  # r == 1 and m == 1
            class_3.append(page)

    # 우선순위에 따라 교체
    if class_0:
        victim = class_0[0]
    elif class_1:
        victim = class_1[0]
        write_to_disk(victim)  # 디스크 쓰기 필요
    elif class_2:
        victim = class_2[0]
    elif class_3:
        victim = class_3[0]
        write_to_disk(victim)  # 디스크 쓰기 필요
    else:
        # 모든 페이지가 없음 (불가능한 상황)
        reset_all_reference_bits()
        return nur_page_replacement()  # 재시도

    return victim

def reset_all_reference_bits():
    """주기적으로 호출되는 함수"""
    for page in page_table:
        page.reference_bit = 0
        # 수정 비트는 유지

예를 들어 초기 페이지 상태가 다음과 같다면 P1이 클래스 0에 속하므로, 페이지 폴트 시 디스크 쓰기 없이 우선 교체된다.

페이지 | 참조 | 수정 | 클래스
------|------|------|-------
  P1  |  0   |  0   |   0
  P2  |  1   |  0   |   2
  P3  |  0   |  1   |   1
  P4  |  1   |  1   |   3

20ms 후 타이머 인터럽트가 참조 비트를 초기화하면 상태는 다음처럼 변한다. 수정 비트는 그대로 남아 있다.

페이지 | 참조 | 수정 | 클래스
------|------|------|-------
P_new |  0   |  0   |   0  (참조 비트 리셋)
  P2  |  0   |  0   |   0  (참조 비트 리셋)
  P3  |  0   |  1   |   1  (수정 비트 유지)
  P4  |  0   |  1   |   1  (참조 비트 리셋, 수정 유지)

⤢✕

LRU와 비교할 때의 위치

NUR과 LRU는 모두 시간적 지역성을 활용하고, 최근 사용된 페이지를 보호하며, 과거의 사용 패턴으로 다음 접근을 예측한다. 차이는 사용 이력을 얼마나 세밀하게 기록하는지에 있다.

특성	LRU	NUR
하드웨어 요구	타임스탬프/스택	2개 비트
정확도	정확한 최근 사용 시간	대략적 사용 여부
구현 복잡도	높음	낮음
오버헤드	높음 (매 접근마다 업데이트)	낮음 (비트만 설정)
성능	최적에 가까움	LRU 근사치 (90~95%)

NUR은 2개 비트만으로 구현할 수 있고 CPU의 참조·수정 비트 기능을 활용한다. 별도 메모리나 복잡한 자료구조가 필요하지 않으며, LRU 대비 90~95% 성능을 달성한다. 수정 비트를 기준으로 읽기 전용 페이지를 우선 교체할 수 있어 전체 I/O를 줄이는 데도 유리하다.

반대로 정확한 참조 시각은 알 수 없고, 참조 비트 초기화 주기 안에서만 최근성을 구분할 수 있다. 같은 클래스 안의 페이지를 구별하기도 어렵다. LRU보다 성능이 5~10% 낮고 워킹 셋 변화에 덜 민감하며, 클래스 3만 남으면 교체 효율이 떨어질 수 있다. 그래서 실제 구현에서는 Clock 알고리즘과 결합하거나 추가 휴리스틱을 적용한다.

운영체제에서의 활용

Linux의 Two-Handed Clock은 Active 리스트와 Inactive 리스트를 유지하면서 NUR 원리와 2차 기회를 함께 사용한다. 페이지 폴트 시에는 Inactive 리스트 끝에서 페이지를 고르고, 참조 비트가 1이면 Active 리스트로 옮긴다. 참조 비트가 0인 페이지는 교체하며, Active 리스트의 페이지는 주기적으로 Inactive 리스트로 이동한다.

Windows의 Modified Page Writer도 참조·수정 비트를 활용한다. 백그라운드 프로세스가 수정된 페이지를 미리 디스크에 기록해 수정 비트를 0으로 만들고, 이후 교체 시의 비용을 낮춘다. 페이지 폴트 시 대기 시간을 줄이고 디스크 I/O를 분산해 시스템 응답성을 높이는 방식이다.

NUR은 최근 사용 여부와 디스크 쓰기 비용을 함께 고려하는 실용적인 페이지 교체 기법이다. 하드웨어 복잡도를 낮게 유지하면서 LRU에 근접한 성능을 제공하므로, Linux와 Windows를 포함한 현대 운영체제의 페이지 교체 메커니즘에서 핵심 원리로 활용된다.