메모리 계층과 멘탈 모델

목표 학습 시간: 105분 + 복습 15분 · 전공 수준 정독용

이 챕터를 다 읽고 나면 당신은 다음을 남에게 설명할 수 있어야 한다: (1) 왜 메모리가 한 종류가 아닌가, (2) SRAM과 DRAM은 무엇이 다른가, (3) 평균 메모리 접근 시간(AMAT)을 계산할 수 있는가, (4) 같은 시간복잡도의 코드가 왜 수 배~수십 배 차이 나는가.

0. 학습 지도 (105분 배분)

1. 문제의 기원 — 메모리 장벽(The Memory Wall)

1.1 두 개의 시계가 따로 논다

컴퓨터 성능을 좌우하는 두 부품, CPU와 메모리(DRAM)는 서로 다른 속도로 빨라져 왔다. 수십 년간 CPU의 연산 속도는 메모리의 접근 속도보다 훨씬 빠르게 개선됐다. 그 결과 오늘날 CPU는 명령 하나를 1나노초도 안 되는 시간에 처리하는데, 메인 메모리에서 데이터 하나를 가져오는 데는 그 수십~수백 배의 시간이 걸린다.

이 격차를 메모리 장벽(memory wall) 이라 부른다. 직관적으로 말하면:

CPU는 1초에 끝낼 일을, 데이터가 도착하기를 100초 동안 기다리며 멍하니 앉아 있을 수 있다.

만약 아무 대책이 없다면, 아무리 빠른 CPU를 만들어도 프로그램은 "메모리를 기다리는 시간"에 발목 잡힌다. 실제로 많은 실무 프로그램의 병목은 연산이 아니라 메모리 접근(memory-bound) 이다. 그래서 "알고리즘의 시간복잡도"만큼이나 "메모리를 어떻게 만지는가"가 중요해진다. 이 한 문장이 이 20시간 전체의 동기다.

1.2 왜 그냥 "빠르고 큰 메모리"를 안 만드나?

세 가지 욕망이 충돌하기 때문이다.

• 빠름을 추구하면(SRAM) 셀 하나에 트랜지스터를 많이 써야 해서 면적·전력·비용이 커지고, 결국 용량을 작게밖에 못 만든다.
• 큼·쌈을 추구하면(DRAM, 플래시, 디스크) 셀을 단순·조밀하게 만들 수 있지만 느려진다.

즉 속도 × 용량 × 비용은 한 기술 안에서 동시에 최적화할 수 없는 삼각형이다. 엔지니어는 이 삼각형을 정면으로 풀려 하지 않고, 여러 기술을 계층으로 쌓아 우회했다. 빠르고 작은 것을 위에, 느리고 큰 것을 아래에 두고, "지금 자주 쓰는 데이터"만 위로 끌어올린다. 이 우회가 통하는 이유는 4절에서 정량적으로 본다.

2. 메모리 기술 — 무엇이 왜 빠르고 느린가

계층을 제대로 이해하려면 각 층이 물리적으로 왜 그런 성질을 갖는지 알아야 한다. 깊게 들어가진 않되, 멘탈 모델은 정확히 잡자.

2.1 SRAM (Static RAM) — 캐시의 재료

• 비트 하나를 보통 6개의 트랜지스터로 만든 플립플롭에 저장한다. 전원이 있으면 값을 스스로 유지한다(static = 정적, 새로 고칠 필요 없음).
• 빠르다(접근 ~1ns 수준). 대신 셀이 커서 집적도가 낮고 비싸다.
• 그래서 SRAM은 레지스터와 L1/L2/L3 캐시처럼 "작지만 초고속" 영역에 쓰인다.

2.2 DRAM (Dynamic RAM) — 메인 메모리의 재료

• 비트 하나를 트랜지스터 1개 + 커패시터 1개로 저장한다. 커패시터에 전하가 있으면 1, 없으면 0.
• 셀이 단순해 집적도가 높고 싸다 → 큰 용량(GB 단위)을 만들 수 있다.
• 대신 커패시터의 전하가 시간이 지나면 새어 나간다. 그래서 주기적으로 값을 다시 써 주는 리프레시(refresh) 가 필요하다(dynamic = 동적). 리프레시와 셀 구조 탓에 SRAM보다 느리다(접근 ~100ns 수준, 행 활성화 등 추가 지연 포함).

핵심 대비: SRAM은 "빠르지만 비싸고 작다", DRAM은 "싸고 크지만 느리다". 이 둘의 성질 차이가 계층의 위/아래를 만든다.

2.3 플래시(SSD)와 자기 디스크(HDD)

• 플래시(SSD): 전원이 꺼져도 값이 유지되는 비휘발성. DRAM보다 훨씬 느리지만(µs 단위) 디스크보다는 빠르고, 움직이는 부품이 없다. 블록 단위 지우기/쓰기, 마모(wear) 등 고유 특성이 있다.
• HDD: 회전 원판 + 헤드의 기계적 이동으로 읽는다. 그래서 접근에 ms 단위가 걸리고, 특히 무작위 접근(seek) 이 치명적으로 느리다. 순차 읽기는 상대적으로 빠르다.

2.4 한 표로 보는 전체 스펙트럼 (대략값, 하드웨어마다 다름)

위→아래로 한 칸 내려갈 때마다 대략 한 자릿수~여러 자릿수씩 느려지고 커진다. 이 "자릿수의 점프"를 몸에 새기는 게 1번 학습 목표다.

2.5 지연을 인간 척도로 — "1 사이클 = 1초" 환산

나노초는 감이 없으니 비율로 바꾸자. CPU 사이클 하나를 1초라고 치면:

당신이 L1에서 처리할 일을 "몇 초"에 끝낼 수 있는데, 메인 메모리까지 내려가면 "몇 분"을 기다리는 셈이다. 메모리에 한 번 내려가는 비용이 이렇게 크다는 감각이, 4절의 정량 분석과 세션 4(캐시)의 모든 최적화의 근거가 된다.

3. 계층 구조와 "캐시"라는 통합 아이디어

3.1 각 층은 아래 층의 캐시다

계층의 핵심 원리는 단순하다: 위층은 아래층의 캐시(cache)다. 캐시란 "느린 저장소의 일부를 빠른 저장소에 복사해 두는 것"이다.

• L1은 L2의 캐시, L2는 L3의 캐시, L3는 DRAM의 캐시, DRAM은 디스크의 캐시(페이지 캐시), 디스크는 원격의 캐시…

데이터를 요청하면 위에서부터 찾는다. 위층에 있으면(히트, hit) 빠르게 끝나고, 없으면(미스, miss) 한 층 내려가 가져오면서 위층에도 복사해 둔다. 그러면 다음 접근은 위층에서 빠르게 처리된다.

요청 → L1 있나? ──있음(히트)→ 끝 (빠름)
          └없음(미스)→ L2 있나? ──있음→ L1에 복사 후 끝
                          └없음→ L3 … → DRAM … → 디스크

3.2 포함 관계와 블록 단위

• 보통 위층은 아래층 내용의 부분집합이다(포함적 캐시의 경우). 위층은 작으니 전부 못 담고, 아래층의 "지금 자주 쓰는 일부"만 담는다.
• 데이터는 바이트 하나씩이 아니라 고정 크기 블록(캐시는 라인, 보통 64B / 가상메모리는 페이지, 보통 4KB) 단위로 층 사이를 오간다. 이건 우연이 아니라 공간적 지역성에 대한 베팅이다(4.1 참조). 세션 4·5에서 다시 깊게 본다.

3.3 이 구조가 만드는 착시

계층이 잘 작동하면, 프로그램에겐 마치 "디스크만큼 크면서 L1만큼 빠른" 단일 메모리가 있는 것처럼 보인다. 물론 이건 착시다 — 착시가 깨지는 건 접근 패턴에 지역성이 없을 때다. 그래서 다음 절의 지역성이 이 모든 것의 작동 조건이다.

4. 지역성과 평균 메모리 접근 시간(AMAT)

여기가 이 세션의 정량적 심장이다. 계층이 "왜, 얼마나" 효과적인지를 숫자로 본다.

4.1 지역성의 두 종류 (정의를 정확히)

• 시간적 지역성(temporal locality): 한 번 접근한 주소는 가까운 미래에 다시 접근될 가능성이 높다. → 캐시는 "한 번 가져온 걸 당분간 붙잡아 두면" 이득. 예) 반복문 카운터 i, 누적 변수 sum, 자주 호출되는 함수의 코드.
• 공간적 지역성(spatial locality): 한 주소를 접근하면 그 근처 주소도 곧 접근될 가능성이 높다. → 캐시는 "한 번에 주변까지 블록으로 끌어오면" 이득. 예) 배열 순차 순회, 구조체의 인접 필드 연속 접근, 순차 실행되는 명령어 스트림.

캐시 라인이 64B인 이유가 바로 공간적 지역성이다. a[0]을 읽을 때 a[1]..a[15]까지 같이 끌어오면, 이어질 순차 접근이 전부 히트가 된다.

4.2 작업 집합(working set)

어느 시점에 프로그램이 "실제로 활발히 쓰는 메모리의 집합"을 작업 집합이라 한다. 핵심 통찰:

작업 집합이 어떤 캐시 층에 들어가면 그 층의 속도를 누리고, 넘치면 한 층 아래로 떨어져 급격히 느려진다.

그래서 같은 알고리즘이라도 데이터 크기가 L2를 넘는 순간 성능이 "절벽처럼" 떨어지는 현상이 관찰된다. 최적화란 종종 "작업 집합을 한 층 위에 욱여넣는" 일이다(세션 4의 블로킹이 정확히 이것).

4.3 평균 메모리 접근 시간 (AMAT) — 공식과 계산

캐시의 효과를 한 수식으로 압축하면:

AMAT = 히트 시간 + 미스율 × 미스 페널티

• 히트 시간(hit time): 그 층에서 바로 줄 때 걸리는 시간.
• 미스율(miss rate): 그 층에서 못 찾을 확률.
• 미스 페널티(miss penalty): 못 찾아서 아래 층까지 갔다 오는 추가 시간.

예제 1 — 한 층 캐시. L1 히트 시간 1ns, 미스율 5%, 미스 페널티(=DRAM 접근) 100ns라 하자.

AMAT = 1 + 0.05 × 100 = 1 + 5 = 6 ns

캐시가 없었다면 매번 100ns였는데, 95%만 히트해도 평균 6ns로 떨어진다. 미스율을 낮추는 것이 곧 성능임을 수식이 보여준다. 만약 미스율이 1%라면 AMAT = 1 + 0.01×100 = 2ns로, 미스율을 5%→1%로 줄였을 뿐인데 평균이 3배 가까이 빨라진다.

예제 2 — 다층 캐시(중첩 AMAT). 미스 페널티 자체가 "아래 층의 AMAT"인 점을 이용해 재귀적으로 계산한다. L1(히트 1ns, 미스율 10%), L2(히트 10ns, 미스율 5%), DRAM(100ns)라면:

AMAT(L2 입장) = 10 + 0.05 × 100 = 15 ns
AMAT(전체)    = 1  + 0.10 × 15  = 1 + 1.5 = 2.5 ns

여기서 배우는 것: L1 미스율을 낮추는 것과 L2를 빠르게/큰 미스율을 줄이는 것 둘 다 전체 AMAT를 끌어내린다. 그리고 미스 페널티가 워낙 크기 때문에(아래 층이 한 자릿수~두 자릿수 느림) 미스율 몇 %p의 차이가 평균에 큰 영향을 준다.

4.4 미스를 부르는 코드 vs 부르지 않는 코드

// 좋은 접근: sum은 레지스터/캐시에서 계속 재사용(시간적),
//            a[i]는 메모리 순서대로(공간적) → 미스율 낮음
long sum = 0;
for (int i = 0; i < n; i++)
    sum += a[i];

// 나쁜 접근: 연결 리스트 순회. 다음 노드가 힙 어디에 있을지 예측 불가.
//            매 노드가 새 캐시 라인 → 거의 매번 미스(pointer chasing)
for (node_t *p = head; p != NULL; p = p->next)
    sum += p->value;

두 코드의 시간복잡도는 똑같이 O(n)이다. 그런데 첫 번째는 캐시 히트의 연속, 두 번째는 미스의 연속이다. AMAT 관점에서 둘의 "한 원소당 평균 비용"이 수 배 차이 난다. 빅오는 같아도 상수가 메모리 계층에서 결정된다 — 이게 이 세션의 가장 중요한 실전 교훈이다.

5. 대역폭 vs 지연, 그리고 직접 측정

5.1 두 개념을 구분하라

• 지연(latency): 한 요청이 시작돼서 결과가 도착하기까지의 시간(예: 100ns). "한 번 갔다 오는 데 얼마나 걸리나."
• 대역폭(bandwidth): 단위 시간당 옮길 수 있는 데이터 양(예: 수십 GB/s). "한꺼번에 얼마나 많이 옮기나."

이 둘은 다르다. 메모리는 지연은 크지만 대역폭은 꽤 높다. 그래서 순차 접근은 (한 번 시작하면 라인을 줄줄이 끌어오므로) 대역폭을 잘 활용해 빠르고, 무작위 접근은 매번 지연을 새로 무는 데다 끌어온 라인의 대부분을 버려 느리다. "데이터를 어떤 순서로 만지느냐"가 같은 양을 옮겨도 속도를 가르는 이유다.

5.2 직접 해보는 실험 (강력 권장 — 체감이 곧 이해다)

큰 정수 배열을 만들고, 두 가지로 합을 구해 시간을 비교하라.

1. 순차 합: for (i=0; i<N; i++) sum += a[i];
2. 스트라이드 합/무작위 합: 큰 간격(예: 캐시 라인보다 큰 간격)으로 띄엄띄엄 접근하거나, 무작위 인덱스 순서로 접근.

배열이 캐시보다 충분히 크면(예: 수백 MB), 순차가 무작위보다 수 배~십수 배 빠른 것을 직접 보게 된다. 또한 배열 크기를 L1→L2→L3→DRAM을 넘도록 키우면서 "원소당 시간"을 그래프로 그리면, 작업 집합이 각 캐시 용량을 넘는 지점마다 계단처럼 느려지는 것을 눈으로 확인할 수 있다. 이 실험 하나가 4절의 모든 수식을 살아 있는 직관으로 바꾼다.

6. 흔한 오해 바로잡기

• ❌ "캐시는 OS나 내가 직접 관리한다." → 하드웨어 캐시(L1~L3)는 하드웨어가 자동으로 채우고 비운다. 개발자는 직접 제어하지 못하고, 접근 패턴(지역성)으로 간접 제어할 뿐이다. (가상 메모리의 페이지 캐시는 OS가 관여하지만, CPU 캐시는 다르다.)
• ❌ "시간복잡도가 같으면 속도도 비슷하다." → 빅오는 점근적 연산 횟수일 뿐, 메모리 접근 패턴이 만드는 상수를 무시한다. O(n) 두 코드가 캐시 행동 때문에 10배 차이 날 수 있다.
• ❌ "캐시 미스는 가끔 나는 사소한 일." → 미스 페널티가 히트의 수십~백 배이므로, 미스율 몇 %p가 평균 성능을 좌우한다(AMAT 예제 참조).
• ❌ "메모리는 다 똑같이 느리다." → 같은 DRAM이라도 순차/무작위, 라인 재사용 여부에 따라 실효 속도가 크게 다르다.

7. 한 장 정리

• CPU와 메모리의 속도 격차(메모리 장벽)가 모든 것의 출발점.
• SRAM(빠르고 작고 비쌈) vs DRAM(싸고 크고 느림, 리프레시 필요)의 물리적 차이가 계층의 위/아래를 만든다.
• 각 층은 아래 층의 캐시이며, 데이터는 블록 단위(라인 64B / 페이지 4KB) 로 오간다.
• 계층이 통하는 조건은 지역성(시간적·공간적)과 작업 집합이 캐시에 들어가는 것.
• 효과는 AMAT = 히트시간 + 미스율 × 미스페널티 로 정량화된다. 미스율 몇 %p가 평균을 좌우한다.
• 빅오가 같아도 상수는 메모리 계층에서 결정된다 — 이 한 문장이 세션 4 이후 모든 최적화의 뿌리다.

8. 복습 (15분) — 답을 가리고 풀어라

개념 인출

Q1. SRAM과 DRAM의 물리적 차이와 그로 인한 성질 차이를 설명하라.

SRAM은 비트당 트랜지스터 6개의 플립플롭으로 값을 스스로 유지해 빠르지만 셀이 커서 작고 비싸다 → 캐시용. DRAM은 트랜지스터 1 + 커패시터 1로 단순·조밀해 싸고 크지만, 전하가 새어 리프레시가 필요하고 느리다 → 메인 메모리용.

Q2. "각 층은 아래 층의 캐시"라는 말을 풀어 설명하라.

위층은 빠르지만 작아서 아래층 내용의 "자주 쓰는 일부"만 복사해 둔다. 요청이 위층에 있으면 히트(빠름), 없으면 미스로 아래층에서 가져오며 위층에 복사해, 다음 접근을 빠르게 만든다.

정량 문제

Q3. L1 히트 1ns, 미스율 4%, 미스 페널티 120ns일 때 AMAT는?

AMAT = 1 + 0.04 × 120 = 1 + 4.8 = 5.8 ns.

Q4. 위에서 미스율을 4%→1%로 낮추면 AMAT는? 몇 배 빨라졌나?

1 + 0.01 × 120 = 2.2 ns. 5.8 / 2.2 ≈ 2.6배 빨라짐. (미스율 3%p 차이가 평균을 2배 이상 가른다.)

Q5. L1(1ns,미스율10%) → L2(8ns,미스율10%) → DRAM(100ns)의 전체 AMAT는?

AMAT(L2) = 8 + 0.10×100 = 18. AMAT(전체) = 1 + 0.10×18 = 2.8 ns.

코드 분석

Q6. 다음 두 코드의 빅오와 실제 속도 차이를 설명하라.

① 배열 순차 합, ② 연결 리스트 순회 합. 둘 다 O(n)이지만, ①은 공간적 지역성으로 캐시 히트의 연속, ②는 노드가 힙에 흩어져 매번 새 라인을 끌어오는 미스의 연속(pointer chasing)이라 한 원소당 평균 비용이 수 배 차이 난다.

연결 고리

Q7. 이 세션의 "지역성"과 "라인/페이지 단위 이동"이 이후 어느 세션으로 이어지는가?

라인 단위 이동·공간적 지역성 → 세션 4(캐시·캐시 친화 코드, 블로킹). 페이지 단위 이동 → 세션 5~6(가상 메모리·페이징·TLB). 작업 집합 개념 → 세션 6의 스와핑/교체 정책.

다음: 세션 2 — 주소·비트/바이트·포인터·프로세스 레이아웃 (별도 파일)