목차
캐시 관리 방법
캐시는 데이터의 처리 속도를 높이고 시스템의 효율성을 증가시키는 데 큰 도움이 됩니다.
캐시는 자주 사용되는 데이터나 명령어를 빠르게 접근할 수 있도록 저장하는 고속 데이터 저장소입니다.
캐시 아키텍쳐
적절한 크기의 캐시를 올바른 위치에 배치하는 기술은 많은 기술을 요구합니다. 대표적으로 지역성과 매핑을 활용하는 방법이 있습니다.
지역성
1.
시간 지역성
•
시간 지역성은 한 번 접근된 데이터가 가까운 미래에 다시 접근될 가능성이 높다는 원리를 말합니다. 예를 들어, 루프 내에서 반복적으로 사용되는 변수들이 이에 해당합니다. 캐시에서 이러한 데이터를 장시간 동안 유지하면, 빠른 접근이 가능해져 성능이 향상됩니다.
2.
공간 지역성
•
공간 지역성은 메모리 상에서 서로 인접한 위치에 있는 데이터가 연속해서 접근될 가능성이 높다는 원리입니다. 예를 들어, 배열의 요소들이 순차적으로 접근되는 경우가 이에 해당합니다. 이를 통해 캐시 블록 내에 연속적인 데이터를 로드함으로써 효율을 높일 수 있습니다.
공간 지역성을 최대한 활용하기 위해, 즉 캐시 히트를 위해서 C#의 스택과 큐는 링크드 리스트가 아닌 기본 배열로 구현되어 있습니다.
스택에서 첫 번째 요소를 가져올 때 공간 지역성에 따라 다음 요소들을 가져온다면 스택의 Pop 과정에서 캐시 히트가 발생할 확률이 높습니다.
매핑
캐시 메모리의 설계에는 다양한 매핑 전략이 사용되며, 각각의 전략은 데이터를 캐시에 어떻게 배치할지 결정합니다.
1.
직접 매핑
•
각 메모리 블록은 캐시 내의 한 위치에만 매핑됩니다. 이는 구현이 간단하고 비용이 낮지만, 다른 데이터들과의 충돌이 발생할 수 있는 단점이 있습니다.
2.
완전 연관 매핑
•
메모리 블록은 캐시의 어떤 위치에도 저장될 수 있습니다. 이 방식은 충돌을 최소화하지만, 관리 비용이 높고 검색 시간이 길어질 수 있는 단점이 있습니다.
3.
집합 연관 매핑
•
이 방법은 직접 매핑과 완전 연관 매핑의 중간 형태입니다. 캐시를 여러 개의 집합으로 나누고, 각 집합 내에서는 완전 연관 매핑을 사용합니다. 이 방식은 충돌을 줄이면서도 검색 시간과 구현 비용의 균형을 맞춥니다.
교체 정책
•
교체 정책
◦
캐시의 공간이 한정되어 있기 때문에, 어떤 데이터를 캐시에서 제거할지 결정하는 정책이 필요합니다. 가장 흔한 교체 정책은 LRU (Least Recently Used), FIFO (First In First Out), LFU (Least Frequently Used) 등이 있습니다.
위의 매핑 과정을 조금 더 자세히 읽어보시면 교체 정책은 직접 매핑에는 사용할 수 없다는 것을 알 수 있습니다.
직접 매핑의 경우, 캐시가 부족해서 교체할 메모리 공간을 선택해야 할 때, 메모리 공간이 이미 정해져 있기 때문에 위 정책들이 무용지물입니다.
캐시 일관성
캐시 일관성은 다중 시스템에서 각 프로세서의 캐시 사이에 저장된 데이터의 일관성을 유지하는 메커니즘을 말합니다.
다중 시스템에서는 여러 프로세서 혹은 쓰레드가 동시에 같은 메모리 위치에 접근하고 수정할 수 있기 때문에, 모든 프로세서의 캐시에 저장된 데이터가 최신 상태를 반영하도록 하는 것이 중요합니다.
계속해서 프로세서와 쓰레드를 함께 사용하는 것이 불편하기 때문에, 이후 설명에서는 프로세서라고만 하겠습니다.
캐시 일관성 문제
캐시 일관성 문제는 다음과 같은 상황에서 발생할 수 있습니다
•
갱신 문제 : 한 프로세서가 데이터를 변경했을 때, 다른 프로세서의 캐시에도 그 변경이 반영되어야 합니다.
•
무효화 문제 : 어떤 프로세서가 데이터를 변경하면, 다른 프로세서의 캐시에 있는 같은 데이터는 더 이상 유효하지 않게 되어야 합니다.
MESI
MESI 프로토콜은 다중 프로세서 시스템에서 캐시 일관성을 유지하기 위해 널리 사용되는 기술입니다.
MESI는 Modified, Exclusive, Shared, Invalid의 네 가지 상태를 기반으로 각 캐시 라인의 상태를 정의합니다.
MESI 프로토콜의 네 가지 상태
1.
Modified (M)
•
해당 캐시 라인은 수정되었으며, 다른 어떤 캐시에도 이 데이터의 복사본이 존재하지 않습니다. 이 상태의 데이터는 주 메모리와 불일치하는 유일한 복사본입니다. 메모리에 쓰기 전에는 이 데이터를 다른 캐시나 메모리로 전송할 때 먼저 메모리에 업데이트해야 합니다.
2.
Exclusive (E)
•
해당 캐시 라인은 메모리와 일치하지만, 수정되지 않았습니다. 이 상태는 해당 프로세서만이 이 데이터를 가지고 있음을 나타내며, 다른 프로세서의 캐시에는 이 데이터의 복사본이 없습니다. 데이터를 수정하면 Modified 상태로 전환됩니다.
3.
Shared (S)
•
해당 캐시 라인은 하나 이상의 캐시에 존재하며, 모든 복사본은 메모리와 일치합니다. 이 상태의 데이터는 읽기 전용이며, 어떤 프로세서도 데이터를 수정할 수 없습니다. 데이터를 수정하려면 먼저 다른 모든 캐시의 해당 라인을 무효화해야 합니다.
4.
Invalid (I)
•
해당 캐시 라인은 유효하지 않거나 사용할 수 없는 상태입니다. 이 상태는 데이터가 무효화되었거나, 처음 사용하기 전의 상태를 나타냅니다. 유효한 데이터를 읽거나 쓰기 위해서는 캐시 라인을 다시 채워야 합니다.
예를 들어, 만약에 a라는 메모리에서 캐시 라인을 프로세서 A가 가져왔다고 합시다. 이때는 Exclusive 상태가 됩니다. 여기서 프로세서 B가 a라는 동일한 메모리에서 변수를 가져온다면 두 캐시 라인은 Shared 상태가 됩니다.
그때 프로세서 A가 a를 수정하기 위해 요청을 보낸다면, 프로세서 A의 캐시 라인은 Modified 상태가 되고 프로세서 B의 캐시 라인은 Invalid 상태가 됩니다.
