Lru_adv

title: 2025-09-18 author: 강병호 date: 2025-09-18 category: TIL/강병호/2025/09 (파일 경로 : TIL/{이름}/{연}/{월}) layout: post (자유) —

LRU 알고리즘을 구현하기 위해서는 표준적인 TLB 레지스터이상의 하드웨어 자원을 필요로 한다. 일반적인 컴퓨터에는 거의 탑재되어 있지 않고 주로 수십개 이상의 CPU를 탑재하는 하이엔드 서버(데이터베이스 서버)에 존재해야 한다.

실제 위 구현 방식에서 계수기 값, 스택 갱신은 메모리 참조 때 마다 수행되어야 하기 때문. 이를 소프트웨어로 하기 위해 인터럽트 사용시 10배 이상 메모리 참조 속도가 느려지며 프로세스 속도가 저하된다.

결국 LRU 알고리즘의 메모리 오버헤드를 감당할 수 있는 시스템이 존재하지 않는다.

LRU 근사 페이지 교체 방식

LRU 알고리즘의 기본 원칙인 시간 지역성을 이용하는 것은 효과적이기에 이 원칙을 그대로 들고간 알고리즘으로 참조 비트 를 활용한다.

• 부가적 참조 비트 알고리즘

  단일 참조 비트가 아닌 각 페이지마다 8비트 크기의 시프트 레지스터를 두어 더 상세한 사용 기록을 유지하도록 한다.

  1. 일정 시간 간격마다 타이머 인터럽트 발생
  2. 운영체제가 참조 비트를 8비트 정보의 최상위 비트로 이동시키고 나머지 비트들을 하나씩 오른쪽으로 이동시킴 ⇒ 시프트 레지스터는 가장 최근 8구간 동안의 그 페이지 사용 기록을 담게 된다.

  e.g.) 0110111 > 11000100

• 2차 기회 알고리즘

  기존적인 LRU 근사 방식으로 FIFO + 참조 비트를 통해 두 번쨰 기회를 부여하는 것

  1. 페이지 교체가 필요하면 포인터가 가리키는 페이지 검사
  2. 참조 비트가 1이면 최근에 사용된 것이니 추가적인 기회 부여(참조 비트 0으로 변경)
  3. 다음 포인터의 페이지 참조 비트가 0이면 최근 사용되지 않았기에 교체

  주로 순환 큐, 포인터를 이용해 구현되어 클록 알고리즘이라고도 불린다.

  최악의 경우는 모든 페이지의 참조 비트가 1인 경우이며 O(N+M)의 복잡도를 가지게 된다.

  모든 페이지를 돈 경우로 이 경우에는 FIFO 처럼 동작하기에 FIFO에 기반한 알고리즘인 것이다.

  

• 개선된 2차 기회 알고리즘

  참조 비트 + 변경 비트를 이용한 개선으로 I/O 쓰기의 오버헤드를 줄이는 것이다.

  다음 네 가지 등급으로 조합한다.

  1. (0, 0) : 최근 사용 X + 변경 X ⇒ 우선 교체
  2. (0, 1) : 최근 사용 X + 변경 O ⇒ I/O 읽기 작업이 존재하기에 교체에 적합하지 않음
  3. (1, 0) : 최근 사용 O + 변경 X ⇒ 다시 사용될 가능성이 높음
  4. (1, 1) : 최근 사용 O + 변경 O ⇒ 다시 사용될 가능성이 높으며 I/O 읽기 작업 존재

  이는 2차기회 알고리즘에서 I/O 접근 횟수를 줄이기 위해 페이지에 추가적인 우선순위를 부여한 것이다.