Locality

개념
기억 장치 내의 정보를 균일하게 Access하는 것이 아닌, 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성

I. Cache Hit율을 극대화하기 위한 Locality의 개요
    가. 지역성(Locality)의 정의

  • 기억 장치 내의 정보를 균일하게 Access하는 것이 아닌, 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성

 

    나. Locality의 전제조건

  • 프로그램은 모든 코드나 데이터를 균등(시간적으로나, 공간적으로)하게 Access하지 않는다는 특성을 기본으로 함.

 

    다. Locality의 원리

  • Cache Access Time의 최소화 + Cache Hit Rate의 최대화
  • Cache Hit Ratio = (Hit 수) / 주기억장치 접근의 총수

 

II. Locality의 종류 및 관리방법
    가. Locality의 종류

구분

내용

사례

시간적 Locality

- Temporal Locality

- 최근에 참조된 기억장소가 가까운 장래에 계속 참조될 가능성이 높은 성질

-순환(Looping)

-서브프로그램

-LRU(Least Recently Used)

공간적 Locality

- Spatial Locality

- 최근에 참조된 기억장소와 가까운 기억정보가 가까운 장래에 계속 참조될 가능성이 높은 성질

-Array

-Sequential Processing

-Pre-fatch

순차적 Locality

- Sequential Locality

- 따로이 분기(branch)가 없는 한 데이터가 기억장치에 저장된 순서대로 순차적으로 인출되고 실행될 가능성이 높음.

 

 

 

* LRU (Least Recently Used) : 사용되지 않고 가장 오래 있었던 블록교체

    나. Locality를 이용한 관리방법

기억장치

계층구조

 (Hierarchy)

- CPU – Cache Memory, -Main Memory

- Access time을 줄이고, 지역성을 이용한 Cache miss를 줄일 수 있음

Cache Access 시간

- Cache Hit ratio를 극대화 할 수 있음

Working Set

- 하나의 페이지가 자주 Access하는 페이지들의 집합을 말하고, Working set를 참조의 지역성을 바탕으로 메인 메모리에 배치하면 Page Fault도 줄이고, Thrashing도 예방가능

 

 

III. Locality 원리의 활용사례
 가. Cache Memory

  • 재배치 알고리즘 구현에 이용

          - LRU (Least Recently Used) : 최근에 가장 적게 사용된 Block을 교체  -> 시간적 지역성

 

  • Fetch 알고리즘 구현에 이용

          - Pre Fetch : 필요한 정보와 예상 정보를 미리 인출하여 배치 ->  공간적지역성


나. Virtual Memory

  •     1) Thrashing 해결

          - Working Set 기법 : 지역성 원리를 이용한 Working Set으로 인한 페이지 교환을 최소화
          - 페이지부재 (Page fault) 로 인한 페이지 교환을 최소화

 

  • 페이지 교체 (Replacement) 알고리즘 구현

다. CDN (Contents Delivery Network)

  • Forward cache server등 지역성 원리를 이용하여 컨텐츠의 신속한 전송

댓글