9.3 VM as a Tool for Caching
가상 메모리는 디스크에 저장된 연속된 바이트 크기 셀 N개를 가진 배열로 구성됩니다. 각 바이트는 유일한 가상 주소를 가지고 배열처럼 index로 접근 가능합니다. 디스크 배열의 바이트들은 메인 메모리에 캐시되어 있습니다. 메모리 계층구조상 다른 캐시들처럼, 디스크에 있는 데이터들은 블록 단위로 나뉘어집니다. 블록은 메인 메모리와 디스크 사이에 데이터 유닛을 전달하는 단위입니다. VM 시스템들은 가상 메모리를 고정된 크기의 블록인 virtual page(VP)로 나누어 관리합니다. 각 가상 페이지들은 P = 2^p 바이트 크기입니다. 이와 유사하게, 물리 메모리도 physical page(PP)로 나누어지고 페이지 사이즈는 가상 페이지와 같은 P 바이트입니다. (물리 페이지는 또한 page frame이라고도 합니다.)
가상 페이지는 크게 3가지 종류가 있습니다.
- Unallocated: 아직 VM 시스템에 의해서 할당되지 않은 페이지. 할당되지 않은 블록은 자신과 연관된 그 어떤 데이터도 가지고 있지 않고 디스크상에서 그 어떤 공간도 차지하고 있지 않습니다.
- Cached: 물리 메모리에 캐시된 상태인 동시에 할당된 페이지.
- Uncached: 물리 메모리에 캐시되지 않았지만 할당된 페이지.
위 그림은 8개 가상 페이지로 구성된 가상 메모리 예시를 보여주고 있습니다. 가상 페이지 0과 3은 아직 할당되지 않았기에 디스크에 존재하지 않습니다. 가상 페이지 1, 4, 6의 경우에는 물리 메모리에 캐시되어 있습니다. 가상 페이지 2, 5, 7은 할당되었으나 현재는 물리 메모리에 캐시되어 있지 않습니다.
9.3.1 DRAM Cache Organization
메모리 계층구조상 여러 캐시들을 구별하기 위해, CPU와 물리 메모리 사이 캐시 메모리인 L1, L2, L3 캐시들을 묶어 SRAM cache라 하겠습니다. 그리고 DRAM cache는 메인 메모리에서 가상 페이지를 캐시하고 있는 VM 시스템 캐시를 뜻한다고 용어 정리를 하겠습니다.
DRAM 캐시의 메모리 계층 구조상 위치는 DRAM 캐시 구조에 큰 영향을 미칩니다. 배운 것을 상기해 보면, DRAM은 SRAM보다 약 10배 정도 느리고 디스크는 DRAM에 비해 10만배 정도 느립니다. 따라서 DRAM 캐시에서 발생한 캐시 미스는 그 비용이 SRAM 캐시에 비해 굉장히 비싸다고 할 수 있습니다. 왜냐하면 DRAM 캐시 미스는 디스크로부터 데이터를 가져오고, SRAM 캐시 미스는 메인 메모리에서 가져오기 때문입니다. 게다가, 디스크 섹터로부터 첫 번째 바이트를 읽는 비용은 해당 섹터에서 연속된 바이트들을 읽는 것보다 약 10만배 정도 느립니다. DRAM 캐시 구조는 이러한 캐시 미스에 의해 야기되는 거대한 비용으로부터 많은 영향을 받았습니다.
캐시 미스로 인한 큰 패널티와 첫 바이트에 접근하는데 드는 큰 비용은 가상 페이지가 큰 용량을 가지는데 영향을 미쳤습니다.(대개 4KB에서 2MB 정도입니다.) 큰 cache miss 페널티 때문에, DRAM 캐시는 완전히 associative합니다. 그 말은 어떤 가상페이지든 간에 물리페이지 어디든 위치할 수 있다는 것을 의미합니다. Cache miss 대체 정책은 중요한 역할을 하는데, 왜냐하면 틀린 가상 페이지를 교체하는 비용이 매우 높기 때문입니다. 따라서 운영체제 DRAM 캐시 대체 알고리즘이 하드웨어 SRAM 캐시 대체 알고리즘 보다 훨씬 더 정교합니다. 이 알고리즘은 책 범위를 벗어나니 넘어가겠습니다. 마지막으로 디스크에 접근하는 시간이 상당히 길기 때문에, DRAM 캐시는 언제나 write-through보다는 wirte-back을 사용합니다.
9.3.2 Page Tables
어떤 캐시든 간에, 가상 메모리 시스템은 항상 가상 페이지가 DRAM 어디에 캐시되었는지 알고 있습니다. 이 방법을 통해 시스템은 가상 페이지가 어떤 피지컬 페이지에 캐시 되어있는지 알아냅니다. 미스가 발생하면, 시스템은 해당 가상페이지가 디스크 어디에 저장되어 있는지 판단하고, 피지컬 메모리로에서 victim 페이지를 선택한 후, 해당 가상 페이지를 victim 페이지에 덮어 씌웁니다.
이 과정은 여러개 요소들로 구성됩니다. 운영체제 소프트웨어, MMU(memory management unit)의 주소 변환 하드웨어 그리고 피지컬 메모리에 저장된 데이터 구조인 page table이 이 요소들입니다. 페이지 테이블은 가상 페이지와 물리 페이지를 맵핑하는 역할을 합니다. 주소 변환 하드웨어는 가상 주소를 물리 주소로 변환할 때마다 페이지 테이블을 읽습니다. 운영체제는 페이지 테이블 내용을 관리하고 페이지들을 디스크와 DRAM사이에 전달하는 역할을 맡습니다.
위 그림은 페이지 테이블 기본 구조를 보여주고 있습니다. 페이지 테이블 하나는 page table entries (PTES) 배열입니다. 가상 주소 공간 각 페이지들은 고정된 offset으로 페이지 테이블에서 PTE를 가집니다. 각 PTE는 valid bit와 n-bit 주소 필드로 이루어져 있습니다. valid bit는 가상 페이지가 현재 DRAM에 캐시되어 있는지 여부를 나타냅니다. valid bit가 유효하면, 주소 필드는 가상 페이지가 캐시되어 있는 DRAM 피지컬 페이지 시작 주소를 가리킵니다. 유효하지 않은 경우, null 주소는 가상 페이지가 아직 할당되지 않았음을 나타냅니다. 할당이 된 경우에는, 주소는 디스크 상 가상 페이지 시작 주소를 가리키고 있습니다.
위 그림은 피지컬 페이지 4개와 가상 페이지 8개로 구성된 페이지 테이블을 보여주고 있습니다. 가상 페이지 4개(VP1, VP2, VP4, VP7)는 현재 DRAM에 캐시되어 있습니다. 페이지(VP0, VP5) 2개는 아직 할당되지 않았고, 나머지 페이지(VP3, VP6)들은 할당되었지만 캐시되어 있지 않습니다. 여기서 주목할 점은 DRAM이 완전히 associative하므로, 어떤 피지컬 페이지든 어떤 가상페이지를 가질 수 있다는 점입니다.
9.3.3 Page Hits
VP2에 있는 word 하나를 CPU가 읽으려할 때 어떤 일이 발생하는지 봅시다. 현재 VP2는 DRAM에 캐시되어 있습니다. 주소 변환 하드웨어는 해당 가상 메모리를 PTE2를 찾아내는 인덱스로 활용하고 이를 메모리로부터 읽어들입니다. (이 과정은 나중에 9.6에서 더 자세히 살펴보겠습니다.) Valid bit가 유효하므로, 주소 변환 하드웨어는 VP2가 메모리에 캐시되어 있다는 사실을 알 수 있습니다. 따라서 PTE에 있는 물리 메모리 주소를 사용해서 읽으려는 워드의 물리 주소를 알아냅니다.
9.3.4 Page Faults
가상 메모리 상 DRAM 캐시 미스는 page fault로 알려져 있습니다.
Figure 9.6은 fault가 발생하기 전 페이지 테이블 상태를 보여주고 있습니다. CPU는 VP3에 있는 워드를 참조합니다. VP3은 DRAM에 캐시되어 있지 않은 상태입니다. 주소 변환 하드웨어는 메모리로 부터 PTE3을 읽고 valid bit에서 VP3이 캐시되어 있지 않음을 알아낸 후, page fault exception을 발생시킵니다. Page fault exception은 커널에 존재하는 page fault exception 핸들러가 victim 페이지를 선택하게끔 합니다. 여기서 victim 페이지는 PP3에 저장되어 있는 VP4로 정해졌습니다. 만약 VP4가 수정되었다면, 커널은 해당 VP4를 복사해서 디스크에 덮어씁니다. 또한, 커널은 VP4가 더 이상 메인 메모리에 캐시되어 있지 않음을 반영하기 위해 VP4에 대한 page table entry를 수정합니다.
그 다음, 커널은 VP3을 디스크에서 복사해 메모리에 있는 PP3에 덮어 씌우고 PTE3을 업데이트한 후 반환합니다. 그 후 핸들러가 반환했을 때, faulting이 발생한 인스트럭션을 재실행합니다. 해당 인스트럭션이 fault를 유발한 가상 주소를 주소 변환 하드웨어에 다시 전송합니다. 이번에는, VP3이 메인메모리에 캐시되어 있고, 페이지 hit이 발생하게 됩니다. 최종적인 그림은 아래 그림과 같은 결과가 됩니다.
가상 메모리는 1960년대 초에 발명되었습니다. 이 당시는 CPU-memory와 SRAM 캐시 간극이 그다지 크지 않았습니다. 가상 메모리 시스템들은 개념은 유사하지만 SRAM 캐시와 다소 다른 용어를 사용했습니다. 가상 메모리에서 블록은 페이지라 합니다. 페이지를 디스크와 메모리 사이에 전달하는 작업을 swapping 또는 paging이라 합니다. 페이지들은 디스크에서 DRAM으로 swapped in 또는 paged in되고 DRAM에서 디스크로 swapped out 또는 paged out됩니다. 미스가 발생히면, 페이지를 swap in하는 마지막까지 기다리는 전략을 demand paging이라 합니다. 미스를 예측하거나, 페이지가 참조되기 전을 페이지 swap in을 예측하는 것도 가능합니다. 하지만 현재 시스템들은 demand paging을 주로 사용합니다.
9.3.5 Allocating Pages
위 그림은 운영체제가 새로운 가상 페이지를 할당했을 때의 상황을 보여줍니다.(예를 들어 malloc 함수를 호출한 경우) 여기서, 디스크에 공간을 만듬으로써, VP5는 할당되고 PTE5가 디스크에 새로 생성된 페이지를 가리키게끔 업데이트합니다.
9.3.6 Locality to the Rescue Again
가상 메모리에서 가장 인상 깊은 점은 이것이 굉장히 비효율적이라는 점입니다. 미스 페널티가 굉장히 큰것을 감안하면, paging이 프로그램 성능을 저하하는 것을 걱정할 수 있습니다. 실제에서는, locality덕에 가상 메모리는 잘 동작합니다.
프로그램이 런타임 동안 참조하는 페이지 총 숫자가 피지컬 메모리 크기를 넘어가도, locality 원리는 어떤 상황에서든 working set 또는 resident set이라 불리는 active set보다 더 작은 set에서 동작하게끔 해줍니다. Working set이 메모리에 페이징 되는 첫번째 오버헤드 이후, 연속된 working set 참조는 hit를 발생시켜 추가적인 disk traffic을 야기하지 않습니다.
프로그램들이 좋은 temporal locality를 가지고 있는 한, 가상 메모리 시스템은 잘 동작합니다. 물론, 모든 프로그램들이 좋은 temporal locality를 가지고 있지는 않습니다. 만약 working set 크기가 physical memory 크기를 넘어간다면, 해당 프로그램은 thrashing을 야기할 수 있습니다. Thrashing은 페이지가 계속 swapped in out하는 것을 말합니다. 비록 가상 메모리는 효율적이지만, 만약 프로그램이 갑자기 느려졌다면 지혜로운 프로그래머는 thrashing이 발생했을 가능성을 고려할 것입니다.
Aside: Couting page faults
리눅스에서 page fault와 이와 관련된 여러 정보들을 getrusage 명령어를 통해 모니터링 할 수 있습니다.
