크래프톤 정글 week10, day78 - 클럭 알고리즘, NRU 알고리즘, NFU 알고리즘

클럭 알고리즘(Clock Algorithm)

페이지 교체 알고리즘(Page Replacement Algorithm)의 한 종류이며, 이 알고리즘은 페이지 프레임을 효율적으로 관리하기 위해 고안되었다. 클럭 알고리즘은 NRU(Not Recently Used) 알고리즘의 변형으로, 참조 비트(Reference Bit)와 수정 비트(Modified Bit)를 활용한다.

 

클럭 알고리즘의 동작

1. 페이지 프레임 링
   • 모든 페이지 프레임은 환형 링크드 리스트로 연결되어 있다.
   • 각 프레임에는 참조 비트와 수정 비트가 있다.
2. 포인터 사용
   • 알고리즘에는 한 개의 포인터가 사용된다.
   • 이 포인터는 링 상의 프레임들을 차례로 가리키며 회전한다.
3. 페이지 교체 과정
   • 새로운 페이지가 메모리에 적재되어야 할 때, 알고리즘은 포인터가 가리키는 프레임을 검사한다.
   • 만약 프레임의 참조 비트가 0이면(최근에 사용되지 않음), 해당 프레임에 새 페이지를 적재한다.
   • 만약 프레임의 참조 비트가 1이면(최근에 사용됨), 참조 비트를 0으로 리셋하고 포인터를 다음 프레임으로 이동시킨다.
   • 프레임의 수정 비트가 1이면(페이지가 수정됨), 디스크에 해당 페이지를 기록한 후에 새 페이지를 적재한다.
4. 포인터 이동
   • 포인터는 링 상에서 계속 회전하며, 가장 오래전에 사용된 프레임을 찾아 새 페이지를 적재한다.

 

클럭 알고리즘의 장점

1. 최근에 사용된 페이지를 유지할 수 있다.
2. 구현이 다른 알고리즘에 비해 간단하다.
3. 페이지 프레임의 사용 효율성을 높일 수 있다.

클럭 알고리즘의 단점

1. 프레임 링을 순환하는 과정에서 오버헤드가 발생할 수 있다.
2. 페이지의 사용 빈도는 고려하지 않는다.

클럭 알고리즘은 LRU(Least Recently Used) 알고리즘과 유사하지만, 보다 간단한 구현 방식을 가지고 있으며, 페이지 참조 패턴이 비교적 일정할 때 효과적으로 동작하고 가상 메모리 시스템에서 널리 사용되고 있다.

---

NRU(Not Recently Used), NFU(Not Frequently Used)

페이지 교체 알고리즘에서 사용되는 기법이며, 이 기법들은 메모리 관리 시스템에서 페이지 프레임을 효율적으로 사용하기 위해 고안되었다.

NRU(Not Recently Used)

• NRU 알고리즘은 페이지 프레임을 Class 0, Class 1, Class 2, Class 3의 4개 클래스로 나눈다.
• 각 클래스는 페이지의 참조 비트(Reference bit)와 수정 비트(Modified bit)의 조합에 따라 결정된다.
  • Class 0: 참조 비트=0, 수정 비트=0 (최근에 사용되지 않고, 수정되지 않은 페이지)
  • Class 1: 참조 비트=0, 수정 비트=1 (최근에 사용되지 않았지만, 수정된 페이지)
  • Class 2: 참조 비트=1, 수정 비트=0 (최근에 사용된 페이지, 수정되지 않음)
  • Class 3: 참조 비트=1, 수정 비트=1 (최근에 사용되고, 수정된 페이지)
• 페이지 교체가 필요할 때, 가장 낮은 클래스(0 -> 1 -> 2 -> 3 순서)에서 페이지를 교체한다.
• 같은 클래스 내에서는 FIFO(First-In-First-Out) 방식으로 교체한다.

NFU(Not Frequently Used)

• NFU 알고리즘은 페이지의 참조 횟수(aging)를 기준으로 페이지를 교체한다.
• 각 페이지에 대해 참조 횟수를 저장하고, 일정 시간마다 모든 페이지의 참조 횟수를 절반으로 줄인다(aging).
• 페이지 교체가 필요할 때, 가장 작은 참조 횟수를 가진 페이지를 교체한다.
• 같은 참조 횟수를 가진 페이지 중에서는 FIFO 방식으로 교체한다.

NRU와 NFU 알고리즘 장단점

• NRU 알고리즘은 구현이 비교적 간단하고, 최근에 사용된 페이지를 우선적으로 유지하므로 페이지 폴트(Page Fault) 발생 확률을 낮출 수 있다.
• NFU 알고리즘은 페이지의 사용 빈도를 고려하므로, 자주 사용되는 페이지를 유지할 수 있지만, 구현이 복잡하고, 참조 횟수 계산을 위한 오버헤드가 있다.

일반적으로 NRU 알고리즘이 더 많이 사용되지만, 시스템의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요하며, 또한 이러한 알고리즘들은 LRU(Least Recently Used), LFU(Least Frequently Used) 등 다른 페이지 교체 알고리즘과 함께 사용되기도 한다.

 

학습 시간 : 10 ~ 25시