IT › 컴퓨터 시스템 › 운영체제 › 메모리 관리

참조 지역성Locality of Reference

프로그램이 한동안 주소 공간의 작은 부분만 되풀이해 참조하는 성질로, 최근 쓴 것을 곧 다시 쓰는 시간 지역성과 가까운 주소를 이어 쓰는 공간 지역성으로 나뉜다.

1요약

  1. 참조 지역성은 Denning 이 1960년대 후반 가상 메모리의 페이지 교체를 연구하며 이름 붙인 프로그램 성질로, 그 위에서 CPU 캐시 · TLB · 작업 집합 · 미리 읽기가 «조금만 가까이 두면 대부분 맞는다»는 가정으로 돈다(Denning 2005).
  2. 지역성을 어기면 같은 계산도 몇 배 느려진다 — 1000 × 1000 행렬 곱에서 둘째 행렬을 전치해 순서대로 읽게 바꾸자 클럭 수가 원래의 23.4% 로 줄었다(Drepper 2007 6.2.1절).
  3. 「캐시 부재가 많다」는 부재율과 라인당 원소 수로 가른다 — 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쉽게 이해하기 — 조리대와 창고 사이를 오가는 요리사

요리사는 좁은 조리대 앞에서 일하고, 재료는 멀리 있는 창고에 있다. 방금 쓴 소금은 곧 또 쓰니 조리대에 두고(시간), 창고에 가면 양념 한 병이 아니라 그 병이 놓인 쟁반을 통째로 들고 온다(공간). 수프를 끝내고 디저트로 넘어가면 조리대 위 물건이 통째로 바뀌는데, 그 순간만 창고를 자주 오간다.

요리사 CPU 레시피 = 프로그램 조리대 L1 캐시 가깝고 좁다 창고 주 메모리 멀고 넓다 1 2 3 4 1 방금 쓴 소금을 조리대에서 다시 집는다 — 시간 지역성 · 캐시 적중 2 창고에 가면 그 병이 놓인 쟁반을 통째로 든다 — 공간 지역성 · 64 B 캐시 라인 3 옆 쟁반을 쓸 차례가 보이면 미리 가져온다 — 순차 지역성 · 프리페치 4 요리가 바뀌면 쓰던 쟁반을 돌려보내고 새 쟁반을 들인다 — 지역성 집합 이동 · 교체

그림 1 · 요리사가 같은 소금을 다시 쓰고(시간 지역성) 쟁반째 들고 오며(공간 지역성) 다음 쟁반을 미리 가져오면(순차 지역성) 창고까지 가는 일이 드물어지고, 요리가 바뀔 때만 조리대 물건이 바뀐다.

레시피 시작수프 재료를 처음 찾음
창고행소금 쟁반을 통째로 가져옴
다시 집기소금 · 후추를 조리대에서 반복 사용
미리 가져오기다음 쟁반을 순서대로
요리 바꿈디저트 재료로 조리대 교체
드문 창고행바뀌는 순간만 자주 오감
비유 — 쟁반 한 판 실제 — 캐시 라인 하나(64 B) 양념 16병이 놓인 쟁반 나머지 15병 첫 병 = 창고까지 한 번 15병 = 조리대 int(4 B) × 16 = 64 B · 주소 0x10000 ~ 0x1003F a[0][1] ~ a[0][15] 적중 15 a[0][0] 부재 → 라인 전체 적재 부재율 = 1 / 16 = 6.25% 부재(멀리 다녀옴) 적중(가까운 사본) 주소 0x10000 은 설명용 가정 값 · 라인 크기는 CPU 마다 sysfs coherency_line_size 로 확인

그림 2 · 쟁반 한 판을 들고 오면 첫 병만 창고까지 가고 나머지 열다섯 병은 조리대에서 집는다 — 실제로는 64바이트 라인 하나에 4바이트 원소 16개가 함께 올라와 부재율이 1/16 이 된다.

비유 속 역할실제 이름실제로 하는 일
요리사CPU명령을 실행하며 주소를 차례로 참조한다
레시피프로그램 · 반복문같은 코드 · 데이터를 되풀이해 지역성을 만든다
좁은 조리대L1 데이터 캐시최근 쓴 라인의 사본을 몇 사이클 거리에 둔다
먼 창고주 메모리(DRAM)원본이 있는 곳 · 부재 때만 간다
소금 다시 집기시간 지역성최근 참조한 주소를 곧 다시 참조한다
쟁반 통째로공간 지역성 · 캐시 라인가까운 주소를 64 B 한 단위로 함께 옮긴다
다음 쟁반 미리순차 지역성 · 프리페치일정 보폭으로 이어지는 접근을 보고 다음 라인을 먼저 읽는다
요리 바꿈지역성 집합의 이동국면이 바뀌는 순간 부재가 몰리고 사본이 교체된다

⚠ 비유가 맞지 않는 곳: 요리사는 무엇을 남길지 스스로 고르지만, 캐시는 프로그램 뜻을 모르고 교체 규칙(LRU 근사 등)과 주소 비트로만 정한다. 그래서 공간 지역성이 좋은 코드도 주소 보폭이 2의 거듭제곱이면 같은 집합에 몰려 쫓겨난다(동작 4 단계).

4구조 — 거리 기준과 그것을 쓰는 장치

지역성은 «시점 t 에 대상 x 까지의 거리 D(x,t) 가 문턱 이하인 대상의 집합»이다(Denning 2005). 거리를 시간으로 재면 시간 지역성, 주소 차이로 재면 공간 지역성, 일정 보폭의 이어짐으로 보면 순차 지역성이며, 저장 계층의 단계마다 셋 중 기대는 쪽이 다르다.

장치(단계) 옮기는 · 기억하는 단위 기대는 지역성 L1 데이터 캐시 64 B 라인 시간 공간 L2 · L3 + 하드웨어 프리페처 다음 라인 · 일정 보폭 순차 TLB 최근 주소 변환 결과 시간 주 메모리 · 작업 집합 4 KiB 페이지 · 창 τ 시간 저장 장치 미리 읽기 읽기 창(파일 단위) 순차 부재 때 ↓ 아래로 갈수록 단위가 크고 한 번 다녀오는 비용이 크다 · 단위 값 = Drepper 2007 · Denning 1968 · posix_fadvise(2)

그림 3 · 저장 계층은 단계마다 옮기는 단위가 커지고, 각 단계의 장치는 시간 · 공간 · 순차 지역성 중 서로 다른 쪽에 기대어 부재를 줄인다.

요소값 · 크기역할근거
거리 D(x,t)시간 · 공간 · 비용지역성 집합에 넣을지 가르는 잣대Denning 2005
시간 지역성마지막 참조 뒤 경과사본을 남겨 두는 근거 · LRU 교체Denning 2005 · Belady 1966
공간 지역성주소 차이한 번에 큰 단위로 옮기는 근거Drepper 2007
순차 지역성일정 보폭의 이어짐다음 단위를 미리 읽는 근거posix_fadvise(2)
캐시 라인64 B(예전 32 B)캐시가 옮기는 최소 단위Drepper 2007 · 커널 ABI cpu cache
작업 집합 W(t,τ)창 τ 안에 참조한 페이지지역성 집합의 측정값Denning 1968
미리 읽기 창SEQUENTIAL = 기본의 2배 · RANDOM = 끔파일 순차 지역성을 쓰는 크기posix_fadvise(2)

🔑 시간 지역성은 «무엇을 남길까»를, 공간 지역성은 «얼마나 크게 가져올까»를 정한다 — 캐시 교체 규칙과 라인 크기가 각각 그 답이다.

5동작 — 1024 × 1024 정수 배열의 행 · 열 순회

직접 실행 — Python 3.14 로 만든 LRU 집합 연관 캐시 시뮬레이터 · L1d 32 KiB · 8-way · 64집합 · 64 B 라인(설명용 가정 값) · int 4 B 배열 a[1024][1024] 을 한 번 다 읽을 때의 접근 · 부재 횟수를 셌다.

  1. 배열은 4 MiB 이고 행 하나가 4,096 B, 라인 하나에 원소 16개가 들어간다.
  2. 행 우선(j 안쪽)으로 a[0][0] 을 읽으면 부재 · 라인 a[0][0..15] 가 올라오고 a[0][1] ~ a[0][15] 15번은 적중한다.
  3. 행 우선 전체는 접근 1,048,576번 · 부재 65,536번 · 부재율 6.25% 다.
  4. 열 우선(i 안쪽)은 a[0][0] · a[1][0] · a[2][0] 처럼 4,096 B 씩 건너뛴다 — 집합 번호 (주소 ÷ 64) mod 64 가 모두 같아 한 집합의 8줄에만 들어간다.
  5. 열 0 을 다 돌고 a[0][1] 로 돌아오면 a[0][0] 과 같은 라인은 이미 쫓겨나 있다 — 열 하나에 라인 1,024개(64 KiB)가 필요해 행 길이를 1,040 으로 늘려 집합을 흩어도 32 KiB 에 들지 않는다.
  6. 열 우선 전체는 부재 1,048,576번 · 부재율 100% 로 행 우선의 16배다. 행 길이 1,040 판도 같은 값이었다.
  7. 반복문 순서를 i 바깥 · j 안쪽으로 바꾸면 3 단계의 65,536번으로 돌아온다.
행 우선 — j 안쪽 열 우선 — i 안쪽 i=0 i=1 i=2 i=3 적중 15 적중 15 한 라인을 다 쓰고 다음 라인으로 2 i=0 i=1 i=2 i=3 다시 오기 전 쫓겨남 보폭 4,096 B → 모두 집합 0 → 8줄만 남음 열 하나 = 1,024줄 4 5 부재 횟수(접근 1,048,576번 중) 행 우선 65,536 · 6.25% 3 열 우선 1,048,576 · 100% — 16배 6 부재 적중 같은 라인 · 쓰기 전에 사라짐 상자 하나 = 라인 64 B(원소 16개)

그림 4 · 행 우선은 라인마다 첫 원소만 부재라 6.25% 이고, 열 우선은 4,096 B 보폭이 한 집합에 몰리고 라인 1,024개가 필요해 모든 접근이 부재가 된다.

주소 시간 국면 1 · 집합 L1 국면 2 · 집합 L2 국면 3 · 집합 L3 창 τ W(t,τ) ≈ L2 t 부재 전환 순간 = 부재 몰림 · 국면 안 = 적중 대부분 · 띠 높이 · 막대 길이는 모양만 보인 설명용

그림 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,cache-misses ./prog두 값의 비로 부재율 · 1/(라인 ÷ 원소 크기) 근처면 정상 순차, 100% 근처면 보폭 문제(perf_event_open(2))
2작은 배열인데 열 순회만 유독 느림2의 거듭제곱 보폭 · 집합 충돌공간cat /sys/devices/system/cpu/cpu0/cache/index0/{number_of_sets,ways_of_associativity}(보폭 ÷ 라인) 이 집합 수의 배수면 한 집합에 몰림 → 행 길이에 패딩(커널 ABI cpu cache)
3데이터가 커지면 부재율이 계단처럼 뜀재사용 거리 > 캐시 용량시간getconf LEVEL1_DCACHE_SIZE · sysfs size한 반복의 작업 데이터 > 해당 캐시 크기면 블로킹(Drepper 2007 6.2.1절)
4파일 처리가 디스크 대기로 멈춤무작위 읽기 · 미리 읽기 꺼짐순차strace -e trace=fadvise64 ./progRANDOM 이면 미리 읽기 없음 · 순서 처리면 SEQUENTIAL(posix_fadvise(2))
5주 페이지 부재가 계속 쌓임작업 집합 > 메모리시간perf stat -e major-faults ./prog디스크 입출력이 필요한 부재 = major → 가상 메모리 · 스래싱 쪽 진단으로(perf_event_open(2))

cache-misses 는 CPU 에 따라 보통 마지막 단계 캐시 부재를 세므로(perf_event_open(2)), L1 만 보려면 perf list cache 로 그 CPU 의 L1d 이벤트 이름을 먼저 확인한다(perf-list(1)).

8시험 대비

출제 정보 컴퓨터시스템응용(131회, 65회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 시간 · 공간 · 순차 지역성의 정의와 활용처를 쓰는 정의 · 특징형이 나올 수 있고, 캐시 · 가상 메모리와 묶어 활용 · 비교형도 나올 수 있다. 정의형이면 2 항목에 거리 D(x,t) 를 두고 그림 3 으로 장치별 활용을 보이며, 활용형이면 4 항목 그림 4 의 부재 횟수를 수치로 넣는다.

답안 목차
  1. 개요 — 정의 · Denning · Belady 의 locality(1968 무렵) · 가상 메모리 교체 연구에서 출발
  2. 유형 — 시간 · 공간 · 순차 지역성 · 거리 D(x,t) 세 잣대
  3. 활용 구조 — 그림 3 캐시 라인 64 B · TLB · 작업 집합 W(t,τ) · 미리 읽기
  4. 사례 — 그림 4 행 우선 65,536 ↔ 열 우선 1,048,576 부재(16배)
  5. 원리 — 그림 5 국면과 지역성 집합 이동 · 전환 순간의 부재 몰림
  6. 향상 기법 — 반복문 교환 · 블로킹 · 패딩 · 프리페치 · 비교표

꼭 쓸 키워드
시간 지역성공간 지역성순차 지역성캐시 라인작업 집합재사용 거리프리페치블로킹반복문 교환국면 전환

다른 답안과 차이를 내는 한 가지는 동작 사례처럼 부재 횟수를 «라인당 원소 수»로 직접 계산해, 공간 지역성의 이득이 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참고 문헌

  1. 먼저 볼 문헌
  2. ★ The Locality Principle (P. J. Denning · Communications of the ACM 48(7) 19-24) — 지역성이 가상 메모리에서 태어나 캐시 · 웹으로 퍼진 과정과 거리 D(x,t) 정의를 볼 때
    ACM · 저자 공개판(Denning Institute) · 2005-07 · denninginstitute.com/pjd/PUBS/CACMcols/cacmJul05.pdf · 확인 2026-11-14
  3. ★ What Every Programmer Should Know About Memory (U. Drepper) — 캐시 라인 64바이트 · 행렬 전치로 L1d 부재를 줄인 측정을 볼 때
    Red Hat · 저자 공개판 · 2007-11 · www.akkadia.org/drepper/cpumemory.pdf · 확인 2026-11-14
  4. ★ The Working Set Model for Program Behavior — 창 τ 로 지역성 집합을 재는 작업 집합 정의를 볼 때
    P. J. Denning · Communications of the ACM 11(5) 323-333 · 1968-05 · doi.org/10.1145/363095.363141 · 확인 2026-11-14
  5. ★ sysfs-devices-system-cpu (Documentation/ABI/testing · cache/index* 속성) — 내 CPU 의 라인 크기 · 집합 수 · 연관도를 확인할 때
    The Linux Kernel · 2026-11 · raw.githubusercontent.com/torvalds/linux/master/Documentation/ABI/testing/sysfs-devices-system-cpu · 확인 2026-11-14
  6. 본문 근거
  7. 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
  8. 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
  9. 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
  10. perf-list(1) Linux manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man1/perf-list.1.html · 확인 2026-11-14
  11. posix_fadvise(2) Linux manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man2/posix_fadvise.2.html · 확인 2026-11-14