참조 지역성Locality of Reference
프로그램이 한동안 주소 공간의 작은 부분만 되풀이해 참조하는 성질로, 최근 쓴 것을 곧 다시 쓰는 시간 지역성과 가까운 주소를 이어 쓰는 공간 지역성으로 나뉜다.
1요약
- 참조 지역성은 Denning 이 1960년대 후반 가상 메모리의 페이지 교체를 연구하며 이름 붙인 프로그램 성질로, 그 위에서 CPU 캐시 · TLB · 작업 집합 · 미리 읽기가 «조금만 가까이 두면 대부분 맞는다»는 가정으로 돈다(Denning 2005).
- 지역성을 어기면 같은 계산도 몇 배 느려진다 — 1000 × 1000 행렬 곱에서 둘째 행렬을 전치해 순서대로 읽게 바꾸자 클럭 수가 원래의 23.4% 로 줄었다(Drepper 2007 6.2.1절).
- 「캐시 부재가 많다」는 부재율과 라인당 원소 수로 가른다 — 1/16(64 B 라인 · 4 B 원소)에 가까우면 정상 순차 접근, 100% 에 가까우면 보폭 · 포인터로 공간 지역성이 깨진 것, 데이터가 커질수록 오르면 재사용 거리가 캐시 용량을 넘은 것이다.
2등장 배경
1959년 Atlas 의 단일 수준 저장 체계는 페이지를 자동으로 옮겼지만, 디스크 접근이 명령 주기보다 약 1만 배 느려 어느 페이지를 내보내느냐에 성능이 달렸고, 다중 프로그래밍과 겹치면 처리량이 무너지는 스래싱이 났다(Denning 2005).
1965년 Wilkes 는 최근 쓴 내용을 작은 빠른 기억 장치에 두는 «slave memory»(오늘의 CPU 캐시)를 냈고, 1966년 Belady 는 사용 비트를 쓰는 교체 알고리즘이 그렇지 않은 것보다 낫다는 것을 보였다(Denning 2005 표 1). 같은 해 Denning 은 최근 창 T 동안 참조한 페이지를 남기는 작업 집합을 제안했고, 1968년 무렵 Belady 와 함께 이 성질을 locality 라 불렀다(Denning 1968 · Denning 2005).
1980년까지 지역성은 «시점 t 에 대상 x 까지의 거리 D(x,t) 가 문턱 이하인 것의 집합»으로 정리되었고, 거리는 시간(마지막 참조 뒤 경과) · 공간(주소 차이) · 비용 셋으로 잴 수 있다(Denning 2005). 지금은 프로세서 캐시 · 디스크 캐시 · 데이터베이스 버퍼 · 웹 캐시가 모두 이 가정 위에 있다.
3쉽게 이해하기 — 조리대와 창고 사이를 오가는 요리사
요리사는 좁은 조리대 앞에서 일하고, 재료는 멀리 있는 창고에 있다. 방금 쓴 소금은 곧 또 쓰니 조리대에 두고(시간), 창고에 가면 양념 한 병이 아니라 그 병이 놓인 쟁반을 통째로 들고 온다(공간). 수프를 끝내고 디저트로 넘어가면 조리대 위 물건이 통째로 바뀌는데, 그 순간만 창고를 자주 오간다.
그림 1 · 요리사가 같은 소금을 다시 쓰고(시간 지역성) 쟁반째 들고 오며(공간 지역성) 다음 쟁반을 미리 가져오면(순차 지역성) 창고까지 가는 일이 드물어지고, 요리가 바뀔 때만 조리대 물건이 바뀐다.
그림 2 · 쟁반 한 판을 들고 오면 첫 병만 창고까지 가고 나머지 열다섯 병은 조리대에서 집는다 — 실제로는 64바이트 라인 하나에 4바이트 원소 16개가 함께 올라와 부재율이 1/16 이 된다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 요리사 | CPU | 명령을 실행하며 주소를 차례로 참조한다 |
| 레시피 | 프로그램 · 반복문 | 같은 코드 · 데이터를 되풀이해 지역성을 만든다 |
| 좁은 조리대 | L1 데이터 캐시 | 최근 쓴 라인의 사본을 몇 사이클 거리에 둔다 |
| 먼 창고 | 주 메모리(DRAM) | 원본이 있는 곳 · 부재 때만 간다 |
| 소금 다시 집기 | 시간 지역성 | 최근 참조한 주소를 곧 다시 참조한다 |
| 쟁반 통째로 | 공간 지역성 · 캐시 라인 | 가까운 주소를 64 B 한 단위로 함께 옮긴다 |
| 다음 쟁반 미리 | 순차 지역성 · 프리페치 | 일정 보폭으로 이어지는 접근을 보고 다음 라인을 먼저 읽는다 |
| 요리 바꿈 | 지역성 집합의 이동 | 국면이 바뀌는 순간 부재가 몰리고 사본이 교체된다 |
⚠ 비유가 맞지 않는 곳: 요리사는 무엇을 남길지 스스로 고르지만, 캐시는 프로그램 뜻을 모르고 교체 규칙(LRU 근사 등)과 주소 비트로만 정한다. 그래서 공간 지역성이 좋은 코드도 주소 보폭이 2의 거듭제곱이면 같은 집합에 몰려 쫓겨난다(동작 4 단계).
4구조 — 거리 기준과 그것을 쓰는 장치
지역성은 «시점 t 에 대상 x 까지의 거리 D(x,t) 가 문턱 이하인 대상의 집합»이다(Denning 2005). 거리를 시간으로 재면 시간 지역성, 주소 차이로 재면 공간 지역성, 일정 보폭의 이어짐으로 보면 순차 지역성이며, 저장 계층의 단계마다 셋 중 기대는 쪽이 다르다.
그림 3 · 저장 계층은 단계마다 옮기는 단위가 커지고, 각 단계의 장치는 시간 · 공간 · 순차 지역성 중 서로 다른 쪽에 기대어 부재를 줄인다.
| 요소 | 값 · 크기 | 역할 | 근거 |
|---|---|---|---|
| 거리 D(x,t) | 시간 · 공간 · 비용 | 지역성 집합에 넣을지 가르는 잣대 | Denning 2005 |
| 시간 지역성 | 마지막 참조 뒤 경과 | 사본을 남겨 두는 근거 · LRU 교체 | Denning 2005 · Belady 1966 |
| 공간 지역성 | 주소 차이 | 한 번에 큰 단위로 옮기는 근거 | Drepper 2007 |
| 순차 지역성 | 일정 보폭의 이어짐 | 다음 단위를 미리 읽는 근거 | posix_ |
| 캐시 라인 | 64 B(예전 32 B) | 캐시가 옮기는 최소 단위 | Drepper 2007 · 커널 ABI cpu cache |
| 작업 집합 W(t,τ) | 창 τ 안에 참조한 페이지 | 지역성 집합의 측정값 | Denning 1968 |
| 미리 읽기 창 | SEQUENTIAL = 기본의 2배 · RANDOM = 끔 | 파일 순차 지역성을 쓰는 크기 | posix_ |
🔑 시간 지역성은 «무엇을 남길까»를, 공간 지역성은 «얼마나 크게 가져올까»를 정한다 — 캐시 교체 규칙과 라인 크기가 각각 그 답이다.
5동작 — 1024 × 1024 정수 배열의 행 · 열 순회
직접 실행 — Python 3.14 로 만든 LRU 집합 연관 캐시 시뮬레이터 · L1d 32 KiB · 8-way · 64집합 · 64 B 라인(설명용 가정 값) · int 4 B 배열 a[1024][1024] 을 한 번 다 읽을 때의 접근 · 부재 횟수를 셌다.
- 배열은 4 MiB 이고 행 하나가 4,096 B, 라인 하나에 원소 16개가 들어간다.
- 행 우선(j 안쪽)으로 a[0][0] 을 읽으면 부재 · 라인 a[0][0..15] 가 올라오고 a[0][1] ~ a[0][15] 15번은 적중한다.
- 행 우선 전체는 접근 1,048,576번 · 부재 65,536번 · 부재율 6.25% 다.
- 열 우선(i 안쪽)은 a[0][0] · a[1][0] · a[2][0] 처럼 4,096 B 씩 건너뛴다 — 집합 번호 (주소 ÷ 64) mod 64 가 모두 같아 한 집합의 8줄에만 들어간다.
- 열 0 을 다 돌고 a[0][1] 로 돌아오면 a[0][0] 과 같은 라인은 이미 쫓겨나 있다 — 열 하나에 라인 1,024개(64 KiB)가 필요해 행 길이를 1,040 으로 늘려 집합을 흩어도 32 KiB 에 들지 않는다.
- 열 우선 전체는 부재 1,048,576번 · 부재율 100% 로 행 우선의 16배다. 행 길이 1,040 판도 같은 값이었다.
- 반복문 순서를 i 바깥 · j 안쪽으로 바꾸면 3 단계의 65,536번으로 돌아온다.
그림 4 · 행 우선은 라인마다 첫 원소만 부재라 6.25% 이고, 열 우선은 4,096 B 보폭이 한 집합에 몰리고 라인 1,024개가 필요해 모든 접근이 부재가 된다.
그림 5 · 프로그램은 작은 지역성 집합 안에서 오래 머물다 국면이 바뀔 때 집합을 옮기고, 부재는 그 전환 순간에 몰린다 — 작업 집합 창 τ 는 지금 집합을 재는 잣대다.
🔑 공간 지역성도 «같은 라인을 다시 쓸 때까지 그 라인이 남아 있는가»라는 시간 거리로 판정된다 — 열 우선은 이웃 주소를 쓰지만 재사용 거리가 캐시보다 길어 이득이 0 이다.
6비교 — 시간 · 공간 · 순차 지역성
| 기준 | 시간 지역성 | 공간 지역성 | 순차 지역성 |
|---|---|---|---|
| 거리 잣대 | 마지막 참조 뒤 경과 | 주소 차이 | 일정 보폭의 이어짐 |
| 쓰는 장치 | 교체 규칙(LRU) · TLB · 작업 집합 | 라인 · 페이지 크기 | 하드웨어 프리페처 · 미리 읽기 |
| 깨뜨리는 코드 | 데이터를 한 번씩만 훑는 큰 순회 | 포인터 추적 · 큰 보폭 · 열 순회 | 무작위 접근 · 해시 탐색 |
| 살리는 기법 | 블로킹(타일링) · 재사용을 가까이 모음 | 반복문 교환 · 구조체 배열 정리 | 순서 읽기 · POSIX_FADV_SEQUENTIAL |
| 너무 믿으면 | 한 번 쓰고 버릴 데이터가 캐시를 밀어냄 | 라인 안 일부만 써서 대역폭 낭비 | 무작위에서 미리 읽기가 헛읽기 |
분석느린 순회는 먼저 공간 · 순차 쪽(접근 순서)을 고치고, 그래도 데이터 크기를 따라 부재가 오르면 시간 쪽(블로킹)을 손댄다. 근거는 동작 7 단계 — 순서만 바꿔도 부재가 1/16 로 줄고, 재사용 거리는 순서가 맞은 뒤에야 의미가 있다(Drepper 2007 6.2.1절).
7실무 진단 — 부재의 지역성 유형 가르기
분석부재율을 «라인당 원소 수의 역수»와 먼저 견주고, 그다음 데이터 크기와 캐시 크기를 견준다. 앞의 비교가 공간 지역성, 뒤의 비교가 시간 지역성을 가르기 때문이다(표 1 · 3 행).
| # | 증상 | 의심 원인 | 구분 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 배열 순회가 느리고 캐시 부재가 많음 | 열 순회 · 큰 보폭 | 공간 | perf stat -e cache-references, | 두 값의 비로 부재율 · 1/(라인 ÷ 원소 크기) 근처면 정상 순차, 100% 근처면 보폭 문제(perf_ |
| 2 | 작은 배열인데 열 순회만 유독 느림 | 2의 거듭제곱 보폭 · 집합 충돌 | 공간 | cat / | (보폭 ÷ 라인) 이 집합 수의 배수면 한 집합에 몰림 → 행 길이에 패딩(커널 ABI cpu cache) |
| 3 | 데이터가 커지면 부재율이 계단처럼 뜀 | 재사용 거리 > 캐시 용량 | 시간 | getconf LEVEL1_DCACHE_SIZE · sysfs size | 한 반복의 작업 데이터 > 해당 캐시 크기면 블로킹(Drepper 2007 6.2.1절) |
| 4 | 파일 처리가 디스크 대기로 멈춤 | 무작위 읽기 · 미리 읽기 꺼짐 | 순차 | strace -e trace= | RANDOM 이면 미리 읽기 없음 · 순서 처리면 SEQUENTIAL(posix_ |
| 5 | 주 페이지 부재가 계속 쌓임 | 작업 집합 > 메모리 | 시간 | perf stat -e major-faults . | 디스크 입출력이 필요한 부재 = major → 가상 메모리 · 스래싱 쪽 진단으로(perf_ |
cache-misses 는 CPU 에 따라 보통 마지막 단계 캐시 부재를 세므로(perf_event_open(2)), L1 만 보려면 perf list cache 로 그 CPU 의 L1d 이벤트 이름을 먼저 확인한다(perf-list(1)).
8시험 대비
www.q-net.or.kr시험에서는 시간 · 공간 · 순차 지역성의 정의와 활용처를 쓰는 정의 · 특징형이 나올 수 있고, 캐시 · 가상 메모리와 묶어 활용 · 비교형도 나올 수 있다. 정의형이면 2 항목에 거리 D(x,t) 를 두고 그림 3 으로 장치별 활용을 보이며, 활용형이면 4 항목 그림 4 의 부재 횟수를 수치로 넣는다.
- 개요 — 정의 · Denning · Belady 의 locality(1968 무렵) · 가상 메모리 교체 연구에서 출발
- 유형 — 시간 · 공간 · 순차 지역성 · 거리 D(x,t) 세 잣대
- 활용 구조 — 그림 3 캐시 라인 64 B · TLB · 작업 집합 W(t,τ) · 미리 읽기
- 사례 — 그림 4 행 우선 65,536 ↔ 열 우선 1,048,576 부재(16배)
- 원리 — 그림 5 국면과 지역성 집합 이동 · 전환 순간의 부재 몰림
- 향상 기법 — 반복문 교환 · 블로킹 · 패딩 · 프리페치 · 비교표
꼭 쓸 키워드
시간 지역성공간 지역성순차 지역성캐시 라인작업 집합재사용 거리프리페치블로킹반복문 교환국면 전환
다른 답안과 차이를 내는 한 가지는 동작 사례처럼 부재 횟수를 «라인당 원소 수»로 직접 계산해, 공간 지역성의 이득이 1/16 이라는 숫자와 그것이 사라지는 조건(재사용 거리)을 함께 보이는 것이다.
9오해와 사실
- 오해이웃 주소를 이어 쓰기만 하면 공간 지역성의 이득을 얻는다.사실같은 라인을 다시 쓰기 전에 그 라인이 쫓겨나면 이득은 0 이다 — 직접 실행에서 256 × 256 배열 열 순회는 행 길이 256 일 때 부재 100%, 패딩을 붙인 272 일 때 6.25% 였다(1,024 B 보폭이 집합 4개에 몰림).
- 오해지역성은 캐시를 위한 하드웨어 개념이다.사실지역성은 가상 메모리의 페이지 교체 연구에서 먼저 이름을 얻었고, CPU 캐시 · 데이터베이스 버퍼 · 웹 캐시는 그 뒤 같은 성질을 쓴 것이다(Denning 2005).
- 오해캐시가 크면 지역성을 신경 쓸 필요가 없다.사실전치 하나로 클럭 수가 23.4% 로 준 측정은 L1d 32 KiB 를 갖춘 CPU 에서 나왔다(Drepper 2007 6.2.1절) — 크기보다 접근 순서가 먼저다.
10핵심 정리
| 개념 | 거리 잣대 | 단위 · 값 | 쓰는 장치 | 깨지는 신호 |
|---|---|---|---|---|
| 시간 지역성 | 마지막 참조 뒤 경과 | 재사용 거리 | LRU 교체 · TLB | 데이터 크기와 함께 부재 상승 |
| 공간 지역성 | 주소 차이 | 라인 64 B | 캐시 라인 · 페이지 | 부재율 100% 근처 |
| 순차 지역성 | 일정 보폭 | 미리 읽기 창 | 프리페처 · fadvise | 무작위 접근 · 헛읽기 |
| 작업 집합 | 창 τ | W(t,τ) 페이지 수 | 페이지 교체 · 부하 조절 | 주 페이지 부재 누적 |
| 집합 충돌 | 주소 비트 | (보폭 ÷ 라인) mod 집합 수 | 집합 연관 캐시 | 작은 배열 열 순회 100% |
| 국면 전환 | 지역성 집합 이동 | 전환 순간 부재 몰림 | 작업 집합 · 교체 규칙 | 주기적 부재 급증 |
11참고 문헌
- 먼저 볼 문헌
- ★ The Locality Principle (P. J. Denning · Communications of the ACM 48(7) 19-24) — 지역성이 가상 메모리에서 태어나 캐시 · 웹으로 퍼진 과정과 거리 D(x,t) 정의를 볼 때
- ★ What Every Programmer Should Know About Memory (U. Drepper) — 캐시 라인 64바이트 · 행렬 전치로 L1d 부재를 줄인 측정을 볼 때
- ★ The Working Set Model for Program Behavior — 창 τ 로 지역성 집합을 재는 작업 집합 정의를 볼 때
- ★ sysfs-devices-system-cpu (Documentation/ABI/testing · cache/index* 속성) — 내 CPU 의 라인 크기 · 집합 수 · 연관도를 확인할 때
- 본문 근거
- A Study of Replacement Algorithms for a Virtual-Storage Computer — L. A. Belady · IBM Systems Journal 5(2) 78-101 · 1966-06 ·
doi.org/10.1147/sj.52.0078· 확인 2026-11-14 - Slave Memories and Dynamic Storage Allocation — M. V. Wilkes · IEEE Transactions on Electronic Computers EC-14(2) 270-271 · 1965-04 ·
doi.org/10.1109/PGEC.1965.264263· 확인 2026-11-14 - perf_event_open(2) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man2/perf_event_open.2.html· 확인 2026-11-14 - perf-list(1) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man1/perf-list.1.html· 확인 2026-11-14 - posix_fadvise(2) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man2/posix_fadvise.2.html· 확인 2026-11-14