정보처리산업기사 - NUR(Not Used Recently) 페이지 교체 알고리즘 집중 탐색!!

※ 공부 내용의 복습 개념으로 정리된 글입니다.

 

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

NUR 페이지 교체 알고리즘은 페이지 교체 시점에 최근에 사용되지 않은 페이지를 교체하는 방식입니다.

NUR 알고리즘은 LRU(Least Recently Used) 알고리즘의 근사치로서, 구현이 간단하고 성능이 비교적 우수합니다.

이 알고리즘은 각 페이지에 대해 두 가지 정보를 사용합니다.

1. 참조 비트(Reference Bit) : 페이지가 최근에 참조되었는지 여부를 나타내는 비트입니다.
2. 수정 비트(Modified Bit) : 페이지가 최근에 수정되었는지 여부를 나타내는 비트입니다.

이 두 비트의 조합을 통해 페이지 교체 우선순위를 정합니다.

 

비트 조합에 따른 우선순위

NUR 알고리즘은 다음과 같은 네 가지 경우를 고려합니다.

1. 참조 비트 0, 수정 비트 0 : 최근에 참조되지 않았고 수정되지 않은 페이지.
2. 참조 비트 0, 수정 비트 1 : 최근에 참조되지 않았지만 수정된 페이지.
3. 참조 비트 1, 수정 비트 0 : 최근에 참조되었지만 수정되지 않은 페이지.
4. 참조 비트 1, 수정 비트 1 : 최근에 참조되었고 수정된 페이지.

알고리즘은 이들 조합 중 우선순위가 가장 낮은 페이지를 선택합니다.

일반적으로 참조 비트가 0인 페이지를 먼저 고려하며, 그 중에서도 수정 비트가 0인 페이지를 최우선으로 교체합니다.

(0,0) → (0, 1) → (1,0) → (1, 1)

 

 

NUR 알고리즘의 동작 원리

1. 초기화
   • 모든 페이지의 참조 비트와 수정 비트를 0으로 초기화합니다.
2. 페이지 참조 시
   • 참조된 페이지의 참조 비트를 1로 설정합니다.
   • 페이지가 수정된 경우 수정 비트도 1로 설정합니다.
3. 페이지 교체 시
   • 모든 페이지의 참조 비트와 수정 비트를 검사합니다.
   • 가장 낮은 우선순위의 페이지(참조 비트와 수정 비트가 모두 0인 페이지)를 선택하여 교체합니다.
4. 주기적인 초기화
   • 일정한 주기마다 모든 페이지의 참조 비트를 0으로 리셋하여 최근 사용 여부를 다시 평가할 수 있게 합니다.

 

NUR 알고리즘 장단점

• 장점
  1. 구현이 간단
     • NUR 알고리즘은 비교적 간단하게 구현할 수 있습니다.
     • 각 페이지에 대해 참조 비트와 수정 비트를 설정하고 관리하는 방식으로 동작하기 때문에 복잡한 데이터 구조나 계산이 필요하지 않습니다.
  2. LRU의 근사치
     • NUR은 LRU 알고리즘의 근사치로, 최근에 사용되지 않은 페이지를 교체합니다.
     • LRU와 유사한 성능을 보이면서도 구현이 더 간단합니다.
  3. 효울성
     • NRU 알고리즘은 페이지 교체 시 모든 페이지의 참조 비트와 수정 비트를 검사하여 교체할 페이지를 결정합니다.
     • 이는 대체로 효율적인 방법으로, 실제 사용 환경에서 좋은 성능을 보일 수 있습니다.
  4. 메모리 및 시간 절약
     • 참조 비트와 수정 비트를 사용하여 페이지 교체를 결정하는 방식은 메모리와 시간을 절약 할 수 있습니다.
     • 이 방법은 추가적인 데이터 구조를 만힝 사용하지 않기 때문에 메모리 오버헤드가 적습니다.
• 단점
  1. 정확한 최근 사용 정보 부족
     • NUR은 참조 비트와 수정 비트만을 사용하여 페이지 교체를 결정하기 때문에, 정확한 최근 사용 정보를 반영하지 못할 수 있습니다.
     • LRU는 페이지 사용 순서를 정확히 추적하지만, NUR은 근사적으로만 추적합니다.
  2. 참조 비트 초기화 필요
     • NUR 알고리즘은 주기적으로 모든 페이지의 참조 비트를 초기화해야 합니다. 이 초기화 작업은 추가적인 오버헤드를 발생시킬 수 있습니다.
     • 초기화 주기를 잘못 설정하면 알고리즘의 성능에 영향을 줄 수 있습니다.
  3. 수정 비트의 영향 제한
     • 수정 비트는 페이지가 수정되었는지를 나타내지만, 페이지 교체 시 모든 수정된 페이지를 다시 쓰기 위해 I/O 작업이 필요할 수 있습니다.
     • 이는 성능에 부정적인 영향을 미칠 수 있습니다.
  4. 특정 워크로드에 대한 최적화 부족
     • NRU 알고리즘은 일반적인 경우에는 좋은 성능을 보일 수 있지만, 특정한 워크로드에 대해서는 비효율적일 수 있습니다.
     • 예를 들어, 매우 빈번하게 참조되는 페이지와 그렇지 않은 페이지가 혼재된 상황에서는 성능이 떨어질 수 있습니다.

 

NUR 알고리즘 예시

물리 메모리가 3개이고 요구 페이지 순서가 [A, B, C, D, B, A, B, A, C, A] 라고 가정을 할때 예시입니다.

1	2	3	4	5	6	7	8	9	10
A	B	C	D	B	A	B	A	C	A

 

 

교체/성공				교체	성공	교체	성공	성공	성공	성공
old	A(00)	A(00)	A(00)	D(00)	D(00)	A(00)	A(00)	A(10)	A(10)	A(10)
물리 메모리		B(00)	B(00)	B(00)	B(10)	B(10)	B(10)	B(10)	B(10)	B(10)
new			C(00)	C(00)	C(00)	C(00)	C(00)	C(00)	C(10)	C(10)
상태	실패	실패	실패	실패	성공	실패	성공	성공	성공	성공

 

위 그림에서 첫 번째 숫자는 참조비트, 두 번째 숫자는 변경 비트입니다.

모든 작업은 읽기로 가정을 하고 진행됩니다.

 

• 처음으로 요구되는 페이지 A, B, C는 처음 메모리에 올라오는 것으로 전부 참조 비트와 연산 비트가 (0,0)입니다.
• 그 다음 D가 들어 올때 가장 오래된 A가 D로 교체가 됩니다.
• 그 다음 5번째 B가 들어오면서 B가 존재하기 때문에 페이지 성공 횟수가 증가하며 B(1, 0)으로 바뀝니다.
• 그 다음 6번째 A가 들어오면서 B는 대상 페이지에서 제외되고 페이지 C와 D 중 가장 위에 있는 페이지 D가 교체됩니다.
• 이 과정을 반복해 총 페이지 성공 횟수는 5회로 종료됩니다.