Beyond Physical Memory: Mechanisms

메모리 계층 구조 

1. cpu의 register = 가장 빠른 저장공간

2. 캐시 메모리

3. 메인 메모리 (DRAM)

4. 굉장히 큰 용량의 저장 장치 (하드디스크, 테이프 등..)

 

 

demand paging

앞서 paging의 속도가 느린 이슈는 TLB로 해결하고, page table이 너무 큰 이슈는 hybrid/ multi level paging으로 해결했다. 

그럼 physical memory 자체의 용량이 부족한 한계점은 어떻게 해결할 수 있을까?

바로 메인메모리를 하드디스크의 캐시처럼 사용하는 demand paging을 통해 우리는 거의 무한대에 가까운 virtual momory공간을 확보할 수 있다.

 

메인메모리의 내용이 캐시메모리에 캐싱되는 것처럼, 하드디스크의 내용이 메인메모리로 캐싱될 수 있다.

 

이때 원하는 page내용이 메인 메모리에 안올라와있으면 page fault라고 한다.

원하는 page내용이 메인 메모리에 올라와있는지 아닌지는 PTE에 추가되는 present bit로 알 수 있다. (존재하면 1, 아니면 0)

 

page fault가 발생하면 메인메모리의 page중에 free인 곳을 찾고, 하드디스크의 swap space에 있는 해당 페이지(block)를 메인메모리로 읽어온다. 

 

만약 메인메모리에 free인 page가 없다면 가장 덜 사용될만한 page를 비우고 page를 교체한다. 

 

이렇게 하드디스크에서 필요할 때 페이지를 가져오는 것을 demand paging이라고 한다.

Bit map

bitmap은 physical frame중에서 어떤 것이 비어있고 어떤 것이 사용중인지 그 정보를 표현하기 위한 방법이다.
사용중이면 1, 사용중이지 않으면 0으로 표현한다.
만약 page frame이 총 1000개라면 1000bits의 bitmap으로 이를 표현할 수 있다. (ex. 1011...110101)
비어있는 page frame을 찾고싶으면 bitmap이 0인 것을 찾으면 되기때문에 메모리 관리가 편해진다.

 

 

캐싱이 가능한 이유 : Locality

특정 지역에 더 많이 접근하게 되는 것을 locality라고 하고, 이러한 특징이 캐싱을 가능하게 한다.

 

1. temporal locality (시간적 지역성) ex. for 반복문 코드

temporal locality때문에 나타나는 현상 : 점점 하드디스크 > CPU쪽으로 데이터가 가까워진다.

 

2. spatial locality (공간적 지역성) ex. 배열

spatial locality때문에 나타나는 현상 : cpu쪽에 있을수록 작은 cash line, 하드디스크쪽에 있을수록 큰 cash line을 둔다.

 

프로세서에 가까워질수록 용량은 작고 스피드는 빠르다. 반대로 프로세서에서 멀어질수록 용량은 크지만 스피드는 매우 느리다.

하지만 locality때문에 cpu는 자신이 무한대에 가까운 용량을 매우 빠른 속도로 사용한다고 착각한다.

 

 

Cash Miss의 다양한 원인들

1. compulsory miss (cold start miss)

처음에는 비어있기 때문에 무조건 발생하는 miss. 피할 수 없는 miss이다.

 

2. capacity miss

용량이 부족하기 때문에 발생하는 miss. 캐시 크기를 늘려서 해결할 수 있다.

 

3. conflict miss

넣을 수 있는 공간보다 넣어야 할 주소가 더 많을 경우 충돌이 일어나 발생하는 miss.

이 경우엔 두가지 해결책이 있다.

캐시 크기를 늘리거나, 4way > 8way 이런식으로 연관성(associativity)을 늘려서 해결할 수 있다.

 

4. Coherence (일관성)

같은 캐시는 어디서 조회해도  같은 값을 사용하고, 한곳에서 업데이트하면 다른 곳에서 가져간 캐시값을 무효화(invalidation)하는 일관성때문에 그 다음번에 같은 캐시를 읽으려고 하면 miss가 발생한다.

 

 

캐시의 종류

1. Direct Mapped Cache

Direct Mapped Cache는 1-way, 즉 하나의 인덱스가 가리키는 cash line이 하나인 캐시이다.

저장하는 것은 tag부분만 저장하고, 나머지는 물리적 주소를 비트로 나타내고 분할하여 구한다.

 

2. Set Associative Cache

Set associative Cache는 하나의 인덱스가 가리키는 cash line이 여러개인 캐시이다.

위 그림은 2-way set associative cache를 보여주고 있다. 이를 위해 인덱스를 반으로 줄여서 옆으로 붙인것을 확인할 수 있다. (cache index bit는 1자리 줄고 cache tag bit가 1자리 늘어남)

 

3. Fully Associative Cache

Set associative Cache처럼 인덱스를 줄이고 cash line을 늘리는 과정을 반복해서 인덱스가 아예 사라진 Set Associative Cache이다.

 

 

캐시에 저장되는 것

캐시에는 주소와 내용이 모두 저장된다.

그런데 주소가 전부 저장되는 것은 아니고, 그중에서도 tag필드만 저장된다. index나 select필드는 physical address를 통해 얻어낼 수 있기 때문에 결과적으로 이 셋을 모두 조합하여 원하는 내용을 찾아낸다.

 

 

캐시들의 구조

앞서 살펴본 메모리 계층구조로 인해 굉장히 다양한 캐시의 구조가 존재한다.

 

1. 하드디스크의 내용을 메모리로 캐싱하는 캐시 : fully associative cache

no conflict miss!

demand paging시에 발생하는 miss는 두가지 종류 뿐이다. (compulsory miss, capacity miss)

 

2. 메모리 캐시 : direct mapped cache 또는 set associative cache

 

3. TLB(주소변환정보를 캐싱, 용도는 다른 캐시들과 다름) : fully associative cache

 

 

*강의자료 출처 : http://csl62.eeec.Berkeley.edu 

*원서 출처 : https://pages.cs.wisc.edu/~remzi/OSTEP/