Lru

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

• LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?

  • 강병호

    LRU 알고리즘은 최근의 과거를 가까운 미래의 근사치로 보아 가장 오랜 기간 동안 사용되지 않은 페이지를 교체하는 알고리즘이다. 이는 운영체제에서 최근에 접근했던 데이터가 가까운 미래에 다시 접근될 가능성이 높다는 원리로 이를 활용하여 페이지 교체를 수행한다.

• LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?

  • 강병호

    하드웨어 자원을 이용하여 프레임들이 최근 사용된 시간 순서를 파악해야 한다.

    • 계수기의 활용

      각 페이지가 마지막으로 언제 사용되었는지의 값을 직접 기록하는 직관적인 방식

      1. CPU에 논리적인 counter 를 두어 메모리에 접근할 때 마다 counter++;
      2. 페이지가 참조될 때마다, CPU 계수기의 현재 값(레지스터의 내용)이 해당 페이지의 사용 시간 필드에 복사
      3. 각 페이지의 마지막 참조 시간을 확인하여 시간 값이 가장 작은 페이지가 교체

      장점

      직관적이며 간단함

      단점

      • LRU 페이지를 찾기 위한 페이지 테이블 탐색
      • 메모리 참조 마다 메모리 쓰기 작업을 필요로 함(2번)
      • 페이지 테이블이 변경될 때마다 시간 값을 관리하는 overflow가 존재

    • 스택의 활용

      페이지 번호의 스택을 유지하여 처리하는 방식

      1. 페이지 참조 시 마다 페이지 번호는 스택 중간에서 제거되어 스택 꼭대기에 처리
      2. 오래 사용되지 않은 페이지는 bottom에 존재하여 페이지 교체가 이루어진다. (삭제 처리를 위해 스택은 double linked list 로 구현된다.)

    장점

    교체에 필요한 페이지를 탐색하는 과정이 필요 없습니다.

    단점

    페이지 참조 시마다 스택의 중간에서 맨 위로 옮기는 경우 최악의 경우 N개의 포인터 값을 변경해야 하는 오버헤드가 발생할 수 있다.