[알고리즘] LRU 알고리즘

 LRU (Least Recently Used) 알고리즘 

코딩테스트 문제에 나온 LRU 알고리즘에 대해 정리해보고자 한다.

LRU 알고리즘은 페이지 교체 알고리즘이기에 페이지 교체 알고리즘에 대해 간단하게 살펴보고 가자.

 

 1. 페이지 교체 알고리즘 

페이지 교체 알고리즘은 새로운 페이지를 실행하려고 하지만 메모리가 없을 때 기존의 어떤 페이지를 교체할지 결정하는 알고리즘이다.

이러한 알고리즘에는 다음과 같은 종류들이 있다.

 

1) FIFO (First-in, First-Out)

• 메모리에 적재된 순서대로 내보내는 알고리즘으로, 큐(queue)를 이용해 저장할 수 있다
  
  
• 장점 : 구현이 간단하고 이해하기 쉽다
  
  
• 단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되어야 하며, Belady의 모순이라는 현상으로 인해 오히려 페이지 부재(page-fault)가 늘어날 수 있다

 

2) Optimal (최적 페이지 교체)

 

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘
  
  
• 장점 : 페이지 부재 발생률이 가장 낮다
  
  
• 단점 : 미래의 참조 패턴을 예측해야 하므로 실제로 구현하는 것은 거의 불가능하다

 

3) LRU (Least Recently Used)

 

• 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
  
  
• 장점 : FIFO 알고리즘보다 더 나은 성능을 보이며, 페이지 부재 발생률도 낮출 수 있다
  
  
• 단점 : 구현이 복잡하고, 페이지 참조 시간을 기록해둬야 하므로 페이지 테이블 업데이트에 대한 오버헤드가 발생할 수 있다

 

4) LFU (Least Frequently Used)

 

• 가장 적게 사용된 페이지를 교체하는 알고리즘
  
  
• 장점 : 사용 빈도가 낮은 페이지를 교체함으로써 페이지 부재 발생률을 개선할 수 있다
  
  
• 단점 : 페이지 사용 빈도를 추적하기 위한 추가적인 메모리 공간이 필요하며, 장기적으로 사용될 가능성이 있음에도 페이지를 교체할 가능성이 있다

 

728x90

 

---

 2. LRU 알고리즘 

LRU(Least Recently Used) 알고리즘은 사용한지(참조되지 않은지) 가장 오래된 페이지를 교체하는 알고리즘이다.

이 알고리즘은 가장 오래된 페이지는 앞으로 더이상 쓰지 않을 확률이 높다는 가정 하에 만들어진 알고리즘이다.

 

LRU 알고리즘을 구현하기 위해선 삭제와 추가를 효율적으로 해줘야 하며, 이를 위해선 연결리스트(Linked List)가 필요하다.

즉, 새로운 페이지를 참조할 때마다 연결리스트의 맨 앞 head에 추가해주면 되고, tail에는 가장 오래된 페이지가 저장된다.

만약 캐시가 가득 차서 가장 오래된 페이지를 없애줘야 한다면, tail 노드에 위치한 페이지만 제거해주면 된다.

이미 캐시에 있는 페이지를 참조할 때는 그 페이지를 맨 앞 head로 옮겨주면 된다.

 

또한, LRU 알고리즘에서 알아둬야 할 개념에는 Cache Hit와 Cache Miss가 있다.

 

• Cache Hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하는 경우
  
  
• Cache Miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우

 

아래의 예시를 통해 좀 더 이해도를 높여보자.

캐시의 크기가 3이고, 참조할 페이지는 [1, 2, 1, 3, 4, 1, 5, 4] 순으로 있다.

1과 2는 캐시 내에 없기에 추가해주면 되고, 1이 먼저 참조되었으므로 head에 2를 추가해준다. 그 다음으로 1을 다시 참조했으므로 1을 가져와 head에 위치시켜 준다. 3 역시 캐시 내에 없으므로 head에 추가해주면 된다.

 

문제는 여기서부터다. 캐시가 가득 찼지만 4라는 새로운 페이지를 추가해줘야 한다. 따라서 가장 오래된 페이지 2를 제거해주고 4를 추가해준다. 그리고 1를 다시 참조했으므로 1을 head로 옮겨준다. 또다시 캐시가 가득 찼으므로 3을 제거해주고 5를 추가해준다. 마지막으로, 4를 다시 한 번 더 참조했으므로 4를 head로 옮겨주면 된다.

 

 

* 연결리스트 : https://valueengine.tistory.com/6

[자료구조] 연결리스트 (Linked List)

 

반응형

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://velog.io/@ddyy094/LRULeast-Recently-Used-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%9E%80
• https://code-lab1.tistory.com/60
• https://dailylifeofdeveloper.tistory.com/355