페이지 교체 알고리즘 - LRU(Least Recently Used Algorithm)

페이지 교체 알고리즘

페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법입니다.

페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있습니다.

LRU 알고리즘

여러 페이지 교체 알고리즘 중 가장 대표적인 LRU 알고리즘에 대해 알아봅시다.

캐시에서 메모리를 다루기 위해 사용되는 알고리즘으로, 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜줍니다.

LRU : 가장 오랫동안 참조되지 않은 페이지를 교체
단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생할 수 있다.

4초 : 1은 재참조된 것이므로, 가장 오랫동안 참조되지 않은 순으로 저장된 순서를 변경한다.
6초 : cache size가 가득차 5가 들어갈 수 없으므로, 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.

구현

class LRU {
  constructor(size) {
    this.cache = [];
    this.capacity = size; // 캐시 용량 제한
    this.missTime = 5; // 캐시 있는 경우의 실행시간
    this.hitTime = 1; // 캐시 없는 경우의 실행시간
  }

  put(value) {
    if (this.capacity === this.cache.length) {
      // 캐시 용량 포화
      this.cache.shift();
    }

    this.cache.push(value);
  }

  get(value) {
    const index = this.cache.findIndex((e) => e === value);

    // 캐시에 값 있는 경우
    if (index !== -1) {
      this.put(...this.cache.splice(index, 1));
      return this.hitTime;
    }

    // 캐시에 값 없는 경우
    this.put(value);
    return this.missTime;
  }
}

const data = [1, 2, 1, 3, 4, 5];
const cache = new LRU(3);

let totalRuntime = 0;

data.forEach((v) => {
  const time = cache.get(v);
  totalRuntime += time;

  console.log(cache, `Runtime: ${totalRuntime}`);
});