Not Used Recently. 페이지 교체 알고리즘 의 하나로, 최근에 쓰이지 않은 Page 를 골라 내보낸다. LRU 와 목적은 같지만, 마지막 사용 시각을 정확히 기록하는 대신 비트 두 개로 대충 근사한다.
LRU 를 정확히 구현하려면 페이지에 접근할 때마다 시각을 갱신해야 하는데, 이 갱신은 메모리 접근마다 일어나므로 하드웨어 지원 없이는 비용이 너무 크다. NUR 은 그 비용을 비트 두 개로 낮춘 절충안이다.
참조 비트와 변형 비트
각 페이지가 비트 두 개를 갖는다.
| 비트 | 언제 1 이 되나 | 언제 0 으로 돌아가나 |
|---|---|---|
| reference bit (R) | 페이지를 읽거나 쓸 때 하드웨어가 세운다 | 운영체제가 주기적으로 전부 0 으로 민다 |
| modified bit (M) | 페이지에 쓰기가 일어날 때 세운다 | 페이지를 디스크에 기록한 뒤 |
교체 대상은 조합의 우선순위로 고른다.
- — 최근에 안 쓰였고 수정도 안 됐다. 디스크에 쓸 필요 없이 그냥 버리면 되므로 가장 싸다
- — 최근에 안 쓰였지만 수정됐다. 내보내기 전에 디스크에 기록해야 한다
- — 최근에 쓰였고 수정은 안 됐다
- — 최근에 쓰였고 수정도 됐다. 가장 나중에 고른다
clock 방식
실제 구현은 페이지들을 원형으로 늘어놓고 포인터를 돌린다. 포인터가 가리키는 페이지의 R 이 1 이면 0 으로 내리고 다음으로 넘어가고, 0 이면 그 페이지를 교체한다. 시계바늘처럼 돈다고 해서 clock algorithm 이라고 부른다.
R 을 1 에서 0 으로 내리는 것이 “한 번 봐준다” 는 뜻이라 second-chance 라고도 한다. 최근에 쓰인 페이지는 한 바퀴를 버티지만, 그 사이에 다시 안 쓰이면 다음 바퀴에서 교체된다.
정확한 LRU 보다 Page Fault 가 조금 더 나지만, 하드웨어가 비트 하나만 세워주면 되므로 실제 운영체제가 이 계열을 쓴다.