캐싱 / 페이지교체 알고리즘

 

 

 

컴퓨터는 작업을 끝낸뒤 결과값을 메모리에 저장한다. 여기서 많은 경우 프로세서의 수행 시간에 비해 메모리 접근 시간이 훨씬 오래 걸리기 때문에 전체 수행 시간의 병목은 얼마나 많이 메모리에 접근했는가로 결정된다. 

 

캐시 메모리는 프로세서와 주 메로리 사이에 작게 존재하지만 처리 속도는 빠른 기억 장치입니다. 

프로세서가 어떤 자료를 필요로 할 때 만약 캐시 메모리에 최신의 그 자료가 존재한다면 프로세서는 굳이 주 메모리에서 자료를 가지고 올 필요없이 바로 캐시 메모리에서 가져옴으로서 컴퓨터의 수행 시간을 줄이는 데 큰 기여를 합니다. 

 

캐시 메모리의 크기를 무한정 키우는 것은 금전적으로 큰 부담이 되는 일이기 때문에 그 크기는 대체로 주 메모리의 크기보다 훨씬 작다.

따라서 캐시 메모리를 사용하면 필연적으로 다음과 같은 문제를 마주하게 됩니다. 

바로 어떤 자료를 캐시 메모리에 저장하고 싶은데 더 이상 공간이 없는 경우입니다. 

이를 해결하기 위해서는 이미 저장된 자료중 무언가를 버려야 합니다.

이때 아무거나 버린다면 바로 다음번에 호출되었는데 캐시메로리에서 없다면 주 메로리로 다시 가지러 가야하기 때문에 수행시간이 늘어나는 결과를 초래합니다. 

 

만약 이후 어떤 자료가 호출될지 모두 알고 있는 상황이라면 이 문제는 쉽게 해결할 수 있습니다. 

바로 현재 캐시 메모리에 남아있는 자료중 가장 늦게 호출될 자료를 버리는 것입니다. 이 전략을 우리는 longest forward distance(LFD)라고 부릅니다.

 

하지만 그리 간단한 문제가 아닙니다. 왜냐하면 우리는 가까운 미래에 어떤 자료가 언제 사용될지 모르기 때문입니다. 

따라서 지금까지 들어온 정보만 가지고 캐시 메모리에서 어떤 자료를 제거할지 결정해야 합니다. 

여러방법중 least recently used(LRU)라는 전략이 있습니다. 

이는 현재 캐시 메모리 상에서 사용한된 지 가장 오래된 자료를 버리는 전략입니다. 

그리고 오늘 이것에 대해 알아보겠습니다.

 

 

LRU Cache

이 이론에 따라 캐시 메모리를 운영한다면 캐시 히트율을 높게 유지할 수 있다는 가정이 깔려있고 실제로 성능이 입증되었으며 가장 많이 사용되는 알고리즘이다.

 

LRU의 원리

 

LRU Cache 의 구현은 Double Linked List(이중 연결 리스트)를 통해 이루어질 수 있다. 

 Head 에 가까운 데이터일 수록 최근에 사용된 데이터이고, Tail 에 가까울 수록 오랫동안 사용되지 않은 데이터로 간주한다. 따라서 새로운 데이터를 삽입할 때, Tail 값을 가장 먼저 삭제시키고 Head 에 데이터를 삽입하도록 하여 캐시 교체 시간 복잡도를 O(1) 로 갖게 된다.

그리고 만약 캐시에 적재된 어떤 데이터를 사용한 경우, 해당 데이터를 Head 로 옮겨 가장 최근에 사용된 값임을 명시한다. 즉, 삭제 우선순위에서 멀어지게 하는 것이다.