[OS]캐쉬(Cache)와 캐쉬 알고리즘(Cache Algorithm)

메모리 계층 구조(memory hierarchy)

출처

 메모리 계층 구조에 대해서 간단히 설명하고 넘어가자.

 메모리 계층 구조는 다음과 같이 작동하도록 구성되어 있다. CPU가 데이터를 처리하기 위해서는 레지스터에 데이터가 존재해야 한다. 하지만 레지스터는 가장 빠른 대신에 가장 비싸기 때문에 용량을 한정적으로 사용해야 한다. 만약 CPU에서 처리하고자 하는 데이터가 레지스터에 있으면 그냥 처리하면 되지만, 없다면 CPU cache인 L1 cache에서 데이터가 있는지 없는지 확인해야 한다. 만약 L1 cache에 데이터가 있다면 그 데이터를 레지스터로 올려서 CPU가 처리하면 되지만, 없다면 L1 cache의 하위 메모리인 L2 cache에서 데이터가 있는지 없는지 확인한다. 즉, 해당 계층 구조 내에서 데이터가 존재하지 않으면 하위 계층 구조를 확인하는 방식으로 메모리 계층 구조는 사용된다.

 다시 말해 피라미드의 아래쪽으로 내려갈수록 용량은 커지지만 속도는 느려진다. 그리고 아래쪽으로 내려갈수록 단위 용량당 저장장치의 가격이 비싸진다. 즉 비싸고 빠른 놈들을 적게 쓰고, 싸고 느린 놈들을 많이 쓰겠다는 의미이다. 그럴려면 CPU가 요구하는 데이터를 적절하게 저장하고 있어야 한다. 계층구조에서 CPU로부터의 거리가 가까운 곳에 존재할수록 속도가 빠르므로 CPU가 데이터를 처리하고 좋다. 하지만 상위 계층일수록 비싸기 때문에 데이터를 계층구조 상에서 어떻게 저장하고 관리할지가 중요한 문제가 된다.

캐쉬 알고리즘(cache algorithm)

 메모리 계층 구조의 성격에 대해서 알아보았다. 결국은 경제성과 효율성 때문에 발생한 문제이다. 만약 가장 싸고도 가장 빠른 저장장치가 있다면 저런 계층 구조를 만들 필요는 없을 것이다. 하지만 현재는 필연적으로 메모리 계층 구조가 필요하고, 이 계층 구조를 효율적으로 사용할 방법이 필요하다. 이에 대한 내용이 캐쉬 알고리즘(cache algorithm)이다. 

 캐쉬 알고리즘(을 이해하기 위해서 먼저 locality에 대한 이해가 필요하다. locality는 temporal locality와 spatial locality로 나눈다.

 temporal locality는 대부분 프로그램은 한 번 접근이 이루어진 메모리 영역에 자주 접근하는 특성을 의미한다.

for (int i = 0; i < 1000; ++i) { total += i; }

 위의 코드에서 변수 total이 저장된 메모리 공간은 1000번 접근이 이루어진다. 이는 temporal locality의 좋은 예이다. 

 spatial locality는 이미 이뤄진 영역 근처에 접근할 확률이 높다는 특성을 의미한다.

void insertionSort(int* arr, int size) { if (arr == nullptr || size == 0) return; int key; for (int i = 1; i < size; ++i) { key = arr[i]; for (int j = i - 1; j >= 0; --j) { if (arr[j] > key){ arr[j + 1] = arr[j]; arr[j] = key; } else { break; } } } }

 위의 코드는 삽입 정렬(insertion sort)이다. 위 코드에서 arr[j + 1] = arr[j]과 같은 코드가 spatial locality의 좋은 예이다. 

 사실 메모리 계층 구조는 temporal locality와 spatial locality 덕분에 성능 향상을 이룰 수 있다. 상위 계층에 저장되어 있는 데이터가 있다면, 그 데이터와 그 주변의 데이터에 프로그램이 접근할 확률이 높다. 그래서 하위 계층에는 locality를 만족하도록 그 데이터와 그 주변의 데이터를 저장한다. 즉 데이터와 그 주변 데이터를 한 번에 저장하려면 블록 단위로 처리할 수 밖에 없다. 그러므로 메모리 계층 구조에서 데이터의 이동은 블록 단위로 이뤄진다.

 그렇다면 L1 cache에 데이터가 없어서 L2 cache로부터 데이터 블록을 읽어 들여야 하는 상황을 살펴보자. 운영체제가 작동하고, 다른 프로그램이 실행되는 상황이라면 cache는 항상 가득 차있다.(하드 디스크는 제외) L1 cache가 가득 찬 상태에서 L2 cache의 데이터 블록을 L1 cache로 읽어 들이려면 L1 cache 중 일부분을 밀어낼 수밖에 없다. 어떤 부분을 밀어낼지에 대한 정책이 캐쉬 교체 정책(cache's replacement policy)이다. 가장 보편적인 캐쉬 교체 정책은 LRU(Least-Recently Used)이다. 용어 그대로 가장 오래 전 접근한 블록에 밀어낸다.