--

🟪 Cache Hit

메모리가 캐시에 존재하고 있을 경우 Cache Hit라고 한다.

🟪 Cache Miss

메모리가 캐시에 존재하지 않을 때 Cache Miss라고 한다.

🟪 Least Recently Used

가장 오랫동안 "참조"되지 않은 페이지를 교체하는 방식이다. 캐시가 가득 찼을때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요하다.
사용된지 가장 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘이다.

💟 원리

가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정

• 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지번호를 추가한다.
  그러면 맨 뒤에 있는 페이지번호가 가장 오랫동안 참조되지 않은 페이지번호가 된다.

• Doubly Linked List 를 사용하고 head 에 가까운 node 일수록 가장 최근에 참조된 페이지, tail 에 가까운 node 일수록 가장 오랫동안 참조되지 않는 페이지이다.

  • hit 일 때 : 기존 페이지 삭제 후 맨 앞에 다시 추가
  • miss 일 때 : 맨 앞에 추가
  • cache size 를 넘어서게 될 때 : tail 에 가장 가까운 페이지 삭제 후 맨 앞에 다시 추가

캐시의 크기는 3이다.
새로운 참조값은 맨 앞에 추가한다.
이미 3개의 참조값이 캐시에 들어있다면 맨 뒤에 있는 참조값을 제거하고 새로운 참조값을 맨 앞에 추가한다.
새로운 참조값이 이미 캐시에 들어있는 값이라면 기존 위치에서 제거하고 다시 맨 앞에 추가한다.

• 캐시 리스트의 크기는 3 이다.
  
  
• 참조값 1 이 캐시 리스트의 맨 앞에 추가된다.
  ↳ miss , 참조값 1은 캐시리스트에 없는 값이므로.
  
  
• 참조값 2 가 캐시 리스트의 맨 앞에 추가된다.
  ↳ miss , 참조값 2는 캐시리스트에 없는 값이므로.
  
  
• 참조값 1 이 캐시 리스트의 맨 앞에 추가된다.
  ↳ hit , 참조값 1은 캐시리스트에 있던 값이므로 기존 위치에서 지워지고 다시 맨 앞에 추가 된다.`
  
  
• 참조값 3 이 캐시 리스트의 맨 앞에 추가된다.
  ↳ miss , 참조값 3는 캐시리스트에 없는 값이므로.
  
  
• 참조값 4 가 캐시 리스트의 맨 앞에 추가된다.
  ↳ miss , 참조값 4는 캐시리스트에 없는 값이므로.
  : 캐시리스트가 가득 찼으므로 리스트의 맨 뒤에 있는 = 가장 오랫동안 참조되지 않은 참조값 2가 삭제되고, 참조값 4가 캐시리스트의 맨 앞에 추가된다.
  
  
• 참조값 1 이 캐시 리스트의 맨 앞에 추가된다.
  ↳ hit , 참조값 1은 캐시리스트에 있던 값이므로 기존 위치에서 지워지고 다시 맨 앞에 추가 된다.
  
  
• 참조값 5 가 캐시 리스트의 맨 앞에 추가된다.
  ↳ miss , 참조값 5는 캐시리스트에 없는 값이므로.
  : 캐시리스트가 가득 찼으므로 리스트의 맨 뒤에 있는 = 가장 오랫동안 참조되지 않은 참조값 3이 삭제되고, 참조값 5가 캐시리스트의 맨 앞에 추가된다.
  
  
• 참조값 4 가 캐시 리스트의 맨 앞에 추가된다.
  ↳ hit , 참조값 4는 캐시리스트에 있던 값이므로 기존 위치에서 지워지고 다시 맨 앞에 추가 된다.

🦄 출처 : 이 글의 모든 내용과 사진들은 사과개발자의 일상 블로그의 LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법 게시물에서 가져온 것입니다.

: 티스토리 사이트의 daily_D님의 사과개발자의 일상 블로그의 LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법 게시물