[운영체제] 캐시 메모리

☃️ 캐시 메모리

캐시 메모리: 속도가 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 범용 메모리

• CPU에서는 CPU 고어(고속)와 메모리(CPU에 비해 저속) 사이에서 속도차에 따른 병목현상 완화
• 메인 메모리에서 자주 사용하는 프로그램과 데이터를 저장해둬 속도를 빠르게 함
  • CPU가 어떤 데이터를 원하는지 예측해야 함
• CPU의 속도에 버금갈 만큼 메모리 계층에서 가장 속도가 빠름
• 용량이 적고 비쌈

장점

1. 애플리케이션 성능 개선

메모리는 디스크보다 속도가 빨라서 인 메모리 캐시에서 데이터를 읽는 속도가 매우 빠름
빠른 데이터 액세스는 애플리케이션의 전반적인 성능 개선

2. 데이터베이스 비용 절감

단일 캐시 인스턴스는 수많은 데이터베이스 인스턴스를 대체할 수 있음 > 총 비용 절감

3. 백엔드의 로드 감소

캐싱은 읽기 로드의 상당 부분을 백엔드 데이터베이스에서 인 메모리 계층으로 리디렉션함
데이터베이스의 로드를 줄임: 로드 시 성능 저하되거나 작업 급증 시 작동이 중단되지 않도록 보호

모든 데이터를 캐싱하지 않는 이유

1. 메모리 특성상 데이터 소실 위험
2. 메모리 사용은 비쌈: 방대한 양의 데이터를 모두 메모리에 적재하는 것은 비용 너무 큼

캐싱하기 좋은 데이터

1. 자주 바뀌지 않는 데이터
2. 자주 사용되는 데이터
3. 자주 같은 결과를 반환하는 데이터
4. 오래 걸리는 연산의 결과

☃️ 캐시 미스

캐시 미스, Cache Miss: CPU가 참조하려는 데이터가 캐시 메모리에 없을 때 발생

1. Compulsory Miss: 특정 데이터에 처음 접근할 때 발생
2. Capacity Miss: 캐시 메모리의 공간이 부족해서 발생
3. Conflict Miss: 캐시 메모리에 A와 B 데이터를 저장해야 하는데, A와 B가 같은 캐시 메모리 주소에 할당되어 있어서 발생하는 cache miss (Direct mapping에 자주 발생)

☃️ 캐시 Metrics

Cache Metrics: 캐시의 성능 측정
Hit Latency: 히트가 발생해 캐싱된 데이터를 가져올 때 소요되는 시간

• Hit: CPU에서 요청한 데이터가 캐시에 존재하는 경우

Miss Latency: 미스가 발생해 상위 캐시에서 데이터를 가져오거나 메모리에서 데이터를 가져올 때 소요 되는 시간

• Miss: 요청한 데이터가 캐시에 존재하지 않는 경우
• 상위 캐시: L1 캐시에 데이터가 없어서 L2 캐시에서 데이터를 찾는 경우

Miss rate = Cache misses / Cache accesses
Average access time = Hit latency + Miss rate * Miss latency

캐시의 성능을 높이기 위해서는
1. 캐시의 크기를 줄여 hit latency를 줄이거나
2. 캐시의 크기를 늘려 miss 비율을 줄이거나
3. 더 빠른 캐시를 이용해 latency를 줄이는 방법

☃️ 캐시 메모리의 위치

메인 메모리와 CPU 사이에 위치

☃️ L1, L2 캐시

속도와 크기에 따라 구분됨

L1 Cache

• 매우 빠름
• 비교적 작음
• CPU에 내장
• 데이터 사용/참조에 가장 먼저 사용됨
• Instruction cache & Data cache로 나뉨
  • Instruction cache: 메모리의 TEXT 영역 데이터를 다루는 캐시
  • Data cache: TEXT 영역을 제외한 모든 데이터를 다루는 캐시
• 이 곳에서 데이터를 찾지 못하면 L2 캐시 메모리로 넘어감

L2 Cache

• 목적은 L1과 비슷함
• L1보다 속도가 느림
  • 일반 메모리(RAM)보다는 빠름
• L1 캐시보다 큼

L3 Cache

• L2 캐시로 주로 충분히 처리가 가능해서 웬만한 프로세서에는 달려있지 않음
• 멀티코어 시스템에서 여러 코어가 공유하는 캐시

☃️ 캐시에 올라오는 데이터의 관리

• 캐시는 key/value 형태로 저장됨
• 주소가 키로 주어지면 해당공간에 즉시 접근 가능 (해시테이블과 유사)
• 캐시는 블록으로 나뉨: 각각의 블록은 데이터를 담으며 주소값을 키로 접근 가능
  • 블록의 개수 & 크기가 캐시의 크기 결정

캐시는 임시 데이터.

• 캐시를 저장할 때 캐시가 만료되는 시간을 명시함
  • 캐시는 해당 시간 내에서만 유효. 만료 시간이 경과하면 사용 불가
• 캐시가 만료되는 시간이 있는 이유: source of truth가 아님
  • 데이터베이스의 원본 데이터 변경시 캐시도 변경해야 함

캐시 무효화, Cache invalidation

1. Expiration time
   캐시가 생성될 때 지정한 TTL에 의해 캐시의 수명 결정
   수명이 다한 캐시는 사용되지 않음
   가장 일반적인 전략
   TTL을 보수적으로 정해서 최신의 데이터 반환

2. Freshness Caching Verification
   별도의 검증 절차를 통해 캐시가 유효한지 확인함
   (예) 원본 데이터가 업데이트된 시간과 캐시가 생성된 시간 비교로 캐시의 유효성 판별
   단점: 캐시가 사용될 때마다 추가적인 확인 절차 > 오버헤드 발생

3. Active Application Invalidation
   데이터가 수정되는 코드 수행마다 백엔드에서 연관된 캐시 무력화
   캐시를 세밀하게 관리할 수 있음
   별도의 코드로 캐시를 컨트롤 > 에러 발생하기 쉬움 & 관리 까다로움

☃️ 캐시 간의 동기화

캐시 일관성, Cache Coherence: 공유 메모리 시스템에서 각 클라이언트/프로세서가 가진 로컬 캐시 간의 일관성

• 각 클라이언트가 자신만의 로컬 캐시를 가지고 다른 클라이언트와 메모리를 공유하고 있을 때 캐시의 갱신으로 인한 데이터 불일치 문제 발생
• 캐시 일관성 유지로 데이터 불일치 현상 방지
  • 다른 프로세서가 갱신 캐시 값을 곧바로 혹은 지연하여 다른 프로세서에서 사용할 수 있도록 해야 함

소프트웨어적 해결

• 코드 분석을 통해 안전하게 공유 변수를 사용할 수 있도록 주기 실정
• OR 아예 공유 데이터 변수를 캐시에 저장하지 않도록 설정
• 단점: 컴파일 타임에 문제를 검출 > 캐시 이용률 측면에서 다소 비효율적

하드웨어적 해결

1. 스누피 프로토콜, Snoopy protocol
   각 CPU의 캐시는 공유되는 캐시 데이터 파악하고 있음
   공유되는 캐시 데이터가 갱신되었을 때 이를 기반으로 갱신되지 않은 나머지 데이터 무효화

2. 디렉토리 프로토콜, Directory protocol
   주기억장치의 중앙 제어기가 캐시 일관성 관리
   주기억의 중앙 제어기는 각각 CPU의 캐시 데이터를 가지고 모든 지역 캐시 제어기의 동작을 제어하고 보고 받아 캐시 일관성 관리

☃️ 캐시 메모리의 Mapping 방식

• 캐시 메모리는 메인 메모리에 비해 크기가 매우 작아 메인 메모리와 1:1 매칭은 불가능함
• 캐시가 아무리 CPU에 가깝게 위치해도, 데이터가 캐시 내의 어느 곳에 저장되어있는지 찾기 어려워 모든 데이터를 순회해야 하면 캐시의 장점을 잃음 > 쉽게 찾을 수 있는 구조 필요

Caching line: 캐시에 데이터를 저장할 때 특정 자료구조를 사용하여 묶음으로 저장

1. Direct Mapping (직접 매핑)

• 메인 메모리를 일정한 크기의 블록으로 나눠 각각의 블록을 캐시의 정해진 위치에 맵핑합니다
  • 메모리를 그냥 묶음 단위로 매핑하기 때문에 구현은 쉽지만, 적중률이 낮아질 수 있죠
• 자주 사용되는 다수의 블록이 하나의 위치로 매핑된다면 계속 미스가 발생하고 계속 블록이 교체되죠
• 이미 메모리 블록이 할당되어있을 때 새 블록이 로드되어야 하면 기존 블록은 버리는 원리입니다

2. Full Associative Mapping

• 캐시 메모리의 빈 공간에 마음대로 주소를 저장하는 방식으로, 저장은 간단하지만 조회가 복잡합니다.
• 하는 데이터를 찾기 위해서 모든 태그를 병렬적으로 검사해야 합니다

3. Set Associative Mapping

• direct mapping과 full associative mapping의 장점을 결합한 매핑 방식입니다
• 캐쉬의 블록을 여러 개 묶어서 셋(set)을 구성하고, 셋이 모여 캐쉬가 됩니다
• 그래서 메인 메모리의 블록이 어느 셋에 들어갈지는 정해져 있지만, 그 셋 내의 위치는 임의입니다
• 하나의 셋이 2개의 블록으로 이루어져 있으면 2-way set associative cache.

☃️ 캐시의 지역성

캐시의 지역성, Cache Locality: 데이터에 대한 접근이 시간적/공간적으로 가깝게 발생하는 것

• 캐시의 적중률을 극대화하여 캐시가 효율적으로 동작하도록
• 공간 지역성, Spatial locality: 최근에 사용했던 데이터와 인접한 데이터가 참조될 가능성이 높다
  • 배열, 페이지 접근 등
• 시간 지역성, Temporal locality: 최근에 사용했던 데이터가 재참조될 가능성이 높다
  • loop 등

☃️ 캐시의 지역성 예시

이차원 배열을 가로/세로로 탐색했을 때의 성능 차이

이차원 배열을 반복문으로 탐색하는 전제 하에:

1. 가로로 탐색하면 연속적인 공간을 참조함 > 공간 지역성의 이점 활용 > 성능이 더 좋음
2. 세로로 탐색하면 불연속적 공간을 참조함 > 공간 지역성 X > 성능이 덜 좋음

---

참고:

• [운영체제(OS)] 10. 캐시 메모리(Cache Memory)
• [엔지니어링] CPU와 캐시 (L1/L2/L3 캐시..)
  
• [CS] 캐시 메모리와 지역성
• 캐시 운영 전략
• 캐시 일관성