[Memory] Virtual memory caches

* 이 글은 coursera에서 진행되는 HW/SW Interface 강의를 요약한 내용입니다.

지난 포스트에서 Virtual memory를 왜 쓰는지와 Virtual memory를 쓰기 위한 mechanism인 indirection에 대해서 설명했다.거기서 언급한 내용 중에 용량 문제를 해결하기 위해서 virtual memory를 쓴다고 했었는데 이에 대해서 조금 더 다뤄보겠다.

 사실 virtual memory는 disk에 저장되면서 필요할 때만 physical memory로 load되서 access가 된다. 그러면 상식적으로 생각할때 virtual memory 크기는 physical memory보다는 훨씬 클 것이다. 그러면 과연 이 많은 virtual memory속 data를 physical memory로 옮길 수 있을까?그런데 사실 이런 형태는 얼핏 보기엔 cache와 비슷하다. 

당연히 virtual memory 속 데이터를 physical memory로 표현할 수 없다. 이 때문에 앞에서도 언급한 것처럼 필요한 것만 load하고 나머지는 disk 속 virtual memory에 있어야 한다. 또 자주 쓰는 것은 자주 쓰는 것대로 physical memory에 있어야 cpu가 data access하는데 있어서 빠르게 할 수 있을 것이다. 그래서 위의 그림같이 DRAM이 virtual memory에 대한 일종의 cache 역할을 한다. 그리고 vitual memory에 무언가 들어있는 단위의 형태를 page라고 한다. 여기서 data access에 대한 내용을 잠깐 살펴보겠다. 아래의 예시는 Intel core 2 due의 memory hierarchy를 표현한 것이다.

우리가 잘 알고 있는 것처럼 Data access rate는 SRAM > DRAM > HDD로 정의된다. 이중 SRAM과 DRAM 사이의 Miss panalty는 33배다. 이 말은 만약 CPU에서 cache miss가 발생했을 때 DRAM으로부터도 있는지 없는지를 확인해야 하는데 이러면서 속도 저하가 cache hit이 발생했을 때에 비해서 33배정도 차이가 난다는 것이다. 그런데 문제가 심각한 것은 앞에서 언급한 DRAM이 cache로 사용될때이다. 지금 latency와 throughput을 보면 알겠지만 이전 SRAM과 DRAM의 차이보다 훨씬 크게 나타난다. 다시 말해서 virtual memory에서 page miss가 발생하면 속도 저하가 심하게 나타난다는 것이다. 결국 성능 유지를 위해서는 CPU cache management와는 약간 다르게 되어야 한다.

 이를 위해서 한번에 데이터를 옮기는 단위, page block size가 대략 4~8kb에서 많게는 4MB까지 cpu data보다 훨씬 크다.miss panalty가 발생했을 때 cost가 크기 때문에 최대한 miss가 발생할 여지를 줄이고 한번에 많이 page를 옮겨야 한다. 그리고 이런 연유때문에 무작정 쓰는 Write-through 방식보다는 확인해보고 쓰는 write-back 방식이 적절할 것이다.

 또한 direct mapped 방식이나, set-associative 방식이 아닌, Fully associative 방식을 취함으로써 virtual page(virtual memory상에 caching되어있는 요소들)가 Physical page 아무데나 위치할 수 있게 해야 될 것이다.

 하나씩 따져보면 다 연관된 내용이긴 하지만 이렇게 한번에 다뤄지는 데이터도 크기 때문에 보통 cache내에서 발생하는 replacement policy도 조금 더 복잡해진다. 당연히 이런 miss가 최대한 발생이 안되게끔, 그리고 access횟수가 적게끔 구성되는게 이 policy의 목적이 될 것이다. 이때문에 이 부분에 대해서는 hardware의 support를 받는다. 

 이 그림은 지난 포스트 마지막에 소개했던 그림인데 physical memory size가 상대적으로 작은 이상 memory management unit이 필요하다고 했었다. 이 mmu에서 하는 역할이 Address translation이다. cpu에서 memory에 있는 Data를 access할때 이용하는 virtual address를 physical memory address로 바꿔주는 것이다. 그러면 그때 중간의 indirection을 위한 layer 또는 table 이 필요하다.이 table을 page table(PT)이라고 하고, 그 Page table안에 들어있는 각각의 요소를 Page Table Entries(PTEs)라고 한다.

결국 Page table에는 Physical memory를 가리키는 영역도 존재하고, virtual memory를 가리키는 영역도 존재하는데, 이런 table을 process마다 각각 하나씩 가진다. 여기서 보라색으로 표현되어 있는 것이 cached 상태이고, 회색부분이 virtual memory 를 가리키는 영역은 말그대로 uncached된 상태를 나타낸다.

위의 그림이 MMU에서 일어나는 address translation이다. 맨 먼저 CPU 가 어떤 physical memory영역을 읽어오기 위해서 이에 대한 virtual address를 생성하게 되는데, 보통 page number 와 offset으로 나눠지게 된다. 이때 offset은 reference에 대한 상대적인 기준이 된다. 그래서 offset 부분은 virtual address나 physical address나 동일하다. 결국 address translation이라고 하는 건 그 앞의 page number를 정의해주는 것이 되겠다. 그러면 page number를 가지고 page table에서 참고해서 physical page number를 만들어내는 게 전체 과정일텐데, 앞에서 언급한 cache의 특성상 virtual page number가 가리키는 영역에 들어있는 physical page number가 유효한지 아닌지를 판별해줘야 하고 이 역할을 page table내에 있는 valid bit이 해주게 된다. 당연히 valid bit이 set되어 있으면 그곳에 들어있는 physical page number를 그대로 사용하면 될것이고, 아니면 다시 disk로 넘어가서 또 있는지 없는지를 판별해야 된다. 이 과정이 Page Hit/Page Fault인데 이 부분은 뒤에서 더 설명하겠다. 아무튼 process마다 이런 page table을 가지고 있을 것이고, 그렇게 따지면 전체적으로 봤을때 page table은 엄청 많을 것이다. 그러면 cpu에서 mmu로 넘어갈때 어떤 page table을 읽을 건지에 대해서 정의해주면 좋을 거 같다. 이때 Page table base register(PTBR) 혹은 Page Directory Base Register(PDBR)을 쓴다. intel CPU reference를 살펴보면 CR3 register를 이용해서 PTBR을 사용한다고 설명되어 있는데 관심있으면 읽어보면 좋을거 같다.

앞에서 말한대로 Page Hit과 Page Fault에 대한 설명을 잠깐 해보려고 한다. 이건 cache Hit/Miss와 거의 똑같다. 다만 Page Fault는 이전 포스트에서 다뤘던 exception이란 개념이 들어있기 때문에 이 부분만 언급하겠다. 

 말그대로 Page Fault는 Page를 읽어오려고 했는데 실패한 경우를 말한다. 바꿔 말하면 page가 Physical memory에 없다는 이야기가 되고, 또 다른 한편으로는 valid bit이 set되지 않은 상태를 말한다. 그래서 Page fault가 발생하게 되면 page fault handler가 동작하는데 이게 일종의 exception handler다. 그런데 그 포스트에서도 말한 것처럼 page fault는 다른 exception과 조금 다른 형태로 동작한다. 

exception이 발생하게 되면 해당 page를 생성하고, 다시 memory에 load하는 과정을 수행한다. 즉 이 load 과정이 두번 수행되는 것이다. 이때는 fault가 발생하지 않고 제대로 physical memory에 load될 것이다. 그런데 한가지 고려해볼 사항이 있다. 이 글의 제목처럼 지금 cache의 형태로 배우고 있는데 만약 physical memory에 data가 꽉차있어서 page fault가 발생해도 data를 load할 수 없는 경우가 발생하는 것이다. 분명 cache에서는 Least Recently Used(LRU)라는 replacement policy가 있어서 가장 덜 쓰인 cache 내용물을 대체했다. 이걸 그대로 쓸 수 있을까?

 당연히 된다. 종류도 Cache에 쓰인 replacement policy와 동일하다. 잠깐 검색해보기로는 LRU 말고도 Not Recently Used (NRU), clock algorithm같은 게 있다고 한다. 이게 궁금한 사람은 다음 문서를 참고하면 좋을 거 같다.

LRU를 적용한다고 가정했을 때  Physical memory에 있는 Data중 virtual page 4를 찾았을때 이걸 page fault로 인해서 생성된 page로 대체하고, 이전에 가리키던 부분은 다시 virtual memory를 가리키게 해야 한다. 예를 들어 VP3가 생성되었을 때는 다음과 같이 될 것이다.

앞에서 말했던 것처럼 이런 게 다 cache의 구조와 비슷한 것이고, 이런 게 가능한 이유도 cache와 마찬가지로 locality를 적용하기 때문이다. 그 중에서도 temporal locality는 개인적으로 사람의 행동 형태와도 유사한 거 같다. 아무래도 사람의 행동도 시간에 따라 continuous 하기 때문에, 아무래도 최근에 한 일을 다음에 할 일로 예측할 수 있다. 이렇게 현재 시점에서 프로그램이 돌아갈 때 사용되고 있는 virtual page들의 집합을 working set이라고 한다. 당연히 temporal locality가 좋은 program는 하나의 virtual page만 집중적으로 참고하고 새롭게 page를 만들 필요가 없기 때문에 그만큼 working set이 작게 된다. 결국 working set은 작으면 작을수록 좋다.

 이런 개념은 전체적인 memory 크기와도 연관이 있는데 working set size가 전체 memory에 비해서 작으면 그만큼 적은 working set으로도 돌아갈 수 있기 때문에 좋은 성능을 나타낸다. 반대로 이런 프로그램들이 점점 많아져서 전체 memory에 비해서 working set size의 합이 커지게 된다면, mmu의 page table에서는 계속 page fault가 발생하면서 안쓰는  page와 쓰는 page간의 swapping이 발생할 것이다. 물론 이게 한번이면 좋은데 프로그램 수가 많다보니 이런 현상은 계속 발생할 수밖에 없고 결국은 전체 성능에 영향을 미치게 된다. 이런 현상을 보통 Thrashing 현상이라고 한다. 당연히 thrashing을 막기 위해서는 physical memory의 크기를 늘리던가, 실행되고 있는 프로그램의 수를 줄여야 하고, wikipedia에 보면 프로그램 별로 priority를 주던가 spartial locality를 향상시킴으로써 해결할 수 있다고 한다.

 크게 Virtual memory가 cache로써 쓰이는 동작에 대해서 살펴봤다.