[CS] LRU 페이지 교체 알고리즘: java 구현 방법

LRU 알고리즘의 원리

LRU 알고리즘(Least Recently Used) 캐시에서 가장 오래 전에 참조된 페이지를 교체하는 방식으로 작동. 이를 구현하기 위해 다음 두 가지 주요 작업을 수행:

1. 페이지 확인: 요청된 페이지가 캐시에 있는지 확인.
2. 페이지 교체: 요청된 페이지가 캐시에 없을 경우, 가장 오래 전에 사용된 페이지를 교체.

Java에서의 LRU 알고리즘 구현

• Java에서 LRU 알고리즘을 구현하기 위해 LinkedHashMap을 사용.
  • 해시 테이블과 연결 리스트를 결합한 형태로, 해시 테이블의 빠른 검색 속도와 연결 리스트의 순서 유지 기능을 제공.

LinkedHashMap의 구성

LinkedHashMap 생성자:

• capacity: 캐시의 크기
• loadFactor: 해시 테이블의 로드 팩터, 일반적으로 0.75
• accessOrder: true로 설정하면 최근 접근 순서로 정렬, false로 설정하면 삽입 순서로 정렬

LRU 캐시 구현 코드

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public void refer(int key) {
        if (!cache.containsKey(key)) {
            System.out.println("해당 페이지를 캐시에 추가: " + key);
        } else {
            System.out.println("해당 페이지를 캐시에서 접근: " + key);
        }
        cache.put(key, key);
    }

    public void display() {
        System.out.println(cache.keySet());
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        int[] testPages = {1, 3, 0, 3, 5, 6, 3};

        for (int page : testPages) {
            cache.refer(page);
            cache.display();
        }
    }
}

작동 방식

이 예시에서, 캐시는 최대 3개의 페이지를 저장. 페이지가 캐시에 추가되거나 접근될 때마다, LinkedHashMap은 페이지의 순서를 최신화. 캐시가 가득 차면, 가장 오래 전에 참조된 페이지 (캐시의 첫 번째 요소)가 자동으로 제거.

REF