지역성 (Locality)

I. 집중적 액세스, Locality의 개념

가. Locality의 의미

• CPU가 기억장치의 특정 부분에 위치한 데이터나 프로그램 코드를 집중적으로 액세스하는 현상
• 컴퓨터의 구성요소 간 속도 차이로 인한 병목현상이 발생하지만 Locality의 특성을 이용하여 고비용/고속 저장장치의 효율적 사용 및 속도 향상 가능

나. Locality의 목표

목표	설명
빠른 접근 시간	– Cache Access Time의 최소화
적중률 최대화	– Cache Hit Rate의 최대화

• Cache Hit Rate = Hit 수 / 기억장치 접근의 총 수

 

II. Locality의 유형

유형	설명	사례
Temporal Locality (시간적 지역성)	– 최근 액세스 된 기억 장소가 가까운 미래에 다시 액세스 가능성 높음	반복 루프 서브 루틴 공통 변수 LRU
Spatial Locality (공간적 지역성)	– 액세스된 기억장소와 인접한 기억장소가 액세스될 가능성 높음	배열(Array) Pre-Fetch
Sequential Locality (순차적 지역성)	– 분기가 발생하지 않는 한, 명령어들은 기억장치에 저장된 순서대로 인출되어 실행되는 특성

• Sequential Locality(순차적 지역성)는 별도의 유형으로 구분하지 않고 공간적 지역성에 포함시키기도 함

 

III. Locality 활용 사례

가. Cache Memory 활용 사례

사례	설명	유형
LRU (Least Recently Used)	– 캐시 교체 알고리즘 구현 – 참조 시간 기준 교체 블록 선정 – 가장 오랫동안 미사용 블록 교체	시간적 공간적
선인출 (Pre-Fetch)	– 캐시 인출 알고리즘 구현 – 향후 필요 예측 정보의 블록을 미리 캐시로 인출하여 배치	공간적 시간적

• Cache Memory는 Locality 특성을 이용하여 적중율(Hit Rate)을 높여 고속 기억장치 효율적 이용

나. Virtual Memory 활용 사례

사례	설명	유형
워킹셋 (Working Set)	– Thrashing 해결 기법 – 특정 시간 실행 프로그램의 최근 참조 페이지 집합	시간적 지역성

다. Network 활용 사례

사례	설명	유형
CDN (Content Delivery Network)	– 콘텐츠의 효율적 전달 위해 여러 노드에 데이터 저장하여 제공 – 서비스 요청자와 가까운 서버에서 콘텐츠 제공	공간적 지역성

 

IV. Locality 소스코드 사례

소스코드	설명
for (i=0; i<10; i++) data[i+1] = data[i] + 1; [실행] data[1] = data[0] + 1; data[2] = data[1] + 1; …	[시간적 지역성] – data[1]는 다음 순환에서 read [공간적 지역성] – data[0]부터 data[9] 까지 read