캐시 기억장치와 지역성 원리

핵심 정리

CPU와 주기억장치 사이의 속도 차이로 생기는 성능 저하를 줄이는 기억장치는 캐시 기억장치이다. 캐시는 CPU와 메인 메모리의 속도 차이를 줄이기 위해 사용된다. 캐시는 CPU와 가까운 곳이나 CPU 내부에 위치할 수 있다.

캐시 기억장치는 지역성의 원리를 이용해 성능을 높인다. 지역성은 프로세서가 짧은 시간 동안 같은 메모리 위치 집합에 반복해서 접근하는 경향이다. 지역성에는 시간적·공간적 지역성 두 유형이 있다. 시간적 지역성은 짧은 시간 안에 같은 데이터를 다시 쓰는 경향이고, 공간적 지역성은 가까운 저장 위치의 데이터를 함께 쓰는 경향이다. 배열의 원소를 순서대로 훑는 순차 지역성은 공간적 지역성의 특별한 경우다.

캐시는 주기억장치의 블록을 어느 캐시 위치에 올릴지 정하는 사상 방식에 따라 나뉜다. 직접 사상 방식에서는 주기억장치 블록이 지정된 하나의 캐시 라인에만 사상된다. 반대 극단인 완전 연관 방식에서는 블록을 어떤 캐시 위치에든 자유롭게 올릴 수 있다. 두 방식을 절충한 N-방향 집합 연관 방식에서는 블록마다 정해진 N개의 장소 중 한 곳에만 올릴 수 있다.

캐시에 쓴 내용을 주기억장치에 언제 반영하는지에 따라 쓰기-통과 정책과 쓰기-백 정책이 나뉜다. 캐시와 메인 메모리에 동시에 쓰는 방식은 쓰기-통과(write-through) 정책이다. 다만 다중프로세서 시스템에서는 쓰기-통과 정책을 사용해도 데이터 불일치가 생길 수 있다. 쓰기 정책만으로 여러 프로세서 사이의 데이터 일관성이 보장되지는 않는다.

캐시에 빈자리가 없으면 저장된 블록 하나를 골라 내보내야 한다. 캐시에 가장 오래 있던 블록을 교체하는 알고리즘은 FIFO이다. 이와 달리 LRU는 가장 오랫동안 사용되지 않은 블록을 교체하는 방법이다. Random 교체는 사용 횟수와 무관하게 임의의 블록을 교체하는 방법이다.

자세히

교체 알고리즘의 기준

FIFO, LRU, Random은 캐시가 가득 찼을 때 교체할 블록을 고른다는 점에서는 같지만, 선택 기준은 서로 다르다. FIFO는 블록이 캐시에 들어온 순서만 보므로, 자주 쓰이는 블록이라도 가장 먼저 들어왔다면 밀려난다. LRU는 마지막 사용 시점을 보므로, 오래전에 들어온 블록이라도 최근에 쓰였다면 남는다. Random은 별도 정보를 참고하지 않는다. 세 방식의 차이는 다음과 같다.