[Data Structure] 캐싱

mj·2021년 6월 25일
0

캐싱이란?(Caching)

캐싱은 자료를 임시 메모리에 저장하는 과정으로 추후에 해당 자료가 다시 필요할 때 쉽게 해당 자료를 얻을 수 있다. 캐싱의 목표는 히트(hit, 필요한 항목이 캐시에 존재하는 경우)를 최대화하고 미스(miss, 필요한 항목이 캐시에 존재하지 않는 경우)를 최소화하는 것이다.

캐싱설계

캐싱은 두 가지 요소를 고려해야 한다.

  • 시간적 지연성 : 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높다.
  • 공간적 지연성 : 최근에 접근한 메모리 위치 주변의 위치를 다시 접근할 가능성이 높다.

LFU캐싱 (Least frequently used caching)

LFU(최소 빈도 사용) 캐싱은 운영체제가 메모리를 관리하기 위해 사용하는 캐싱 알고리즘이다. 운영체제는 어떤 블록이 메모리에서 참조된 횟수를 관리한다. 설계상 캐시가 자신의 한계를 초과하는 경우 운영체제는 가장 참조 빈도가 낮은 항목을 삭제한다. 이를 가장 쉽게 구현하는 방법은 해당 블록에 대한 참조가 생성될 때마다 카운터를 증가시키는 것이다. LFU의 단점은 단시간에 반복적인 참조를 할 경우 카운팅이 쌓여 장시간동안 사용되는 블록이 삭제될 수 있다.

LRU(Least Recently used caching)

LRU(가장 오래전 사용) 캐싱은 가장 오래된 항목(가장 최근이 아닌 항목)을 먼저 제거하는 캐싱알고리즘이다. 캐시의 항목에 접근하면 가장 뒤로 보내고, 제거할 때에는 맨 앞에 있는 항목을 제거한다.

0개의 댓글