VM as a Tool for Caching

Virtual Page & Physical Page

• 개념적으로, 가상 메모리는 N개의 연속적인 byte 사이즈의 cell로 디스크 상에서 이루어져 있음
• 각각의 byte는 고유한 virtual address를 갖게 되고 array의 index로서 역할을 함

• disk에서 배열의 내용은 main memory 에 캐시됨

• 메모리 계층구조에서의 다른 여느 캐쉬와 같이 disk의 데이터는 block(transfer unit) 으로 나누어져서 disk와 main memory 사이에서 왔다 갔다 하게 됨
• VM 시스템은 virtual memory를 고정 사이즈의 블럭으로 나누어서 관리를 하는데 이를 virtual pages(VPs)라고 함
• 마찬가지로 physical memory도 physical pages(PPs)로 나누어짐

• Virtual page의 상태는 항상 3가지 상태 중 하나임
• Unallocated : VM 시스템에 의해 아직 한번도 할당되지 않은 page들. 할당도 한번도 안됐기에 disk에서 공간 차지도 안함
• Cached : physical 메모리에 캐시되어 있는 할당된 페이지
• Uncached : physical 메모리에는 캐시되지 않은 할당된 페이지

Page Tables

• 다른 여느 캐시와 같이, VM 시스템은 virtual page가 DRAM의 어딘가에 캐시가 되어있는지를 알 수 있는 방법이 필요함
• 캐시되어 있다면, 어떠한 physical page가 캐쉬된 값인지 알아야 하고
• 캐시되어 있지 않다면, physical memory에서 victim page를 선택하고 disk에서 virtual page를 복사하여 해당 자리에서 붙여넣어야 함(victim page를 대체)

• 위와 같은 동작은 OS(software)와 MMU(address translation hardware) 그리고 physical memory에 저장되어 있는 page table(virtaul page —(map)→ physical page) 에 의해 가능해짐
• MMU는 virtual address를 physical page로 변환할 때마다 page table을 읽음
• OS는 page table의 내용을 유지하는 역할과 disk와 DRAM사이에 page를 전달하는 역할을 수행함

• Page table은 page table entries(PTEs)의 배열임

• 각각의 PTE RK valid bit와 n-bit address field로 되어있다고 가정
• valid bit : virtual page가 DRAM에 캐쉬되었는지를 알려줌
• valid bit가 1이면 address field는 DRAM의 해당하는 physical page의 주소를 가리키게 됨
• valid bit not set, null address는 virtual page에 아무것도 할당되지 않았다고 알려주는 것임. 혹은, address가 disk의 virtual page를 가리킬 수 있음

• 위 Page table에서 VP1, 2, 4, 7 이 캐쉬되었고(Cached) VP 0, VP 5는 아직 할당되지 않음(Unallocated) VP3, VP6은 할당되었지만 캐시되지않음(Uncached)

Page Hits

• CPU가 VP2에 포함되어 있는 virtual memory(DRAM에 캐쉬된) 를 읽으려고 하는 상황을 가정해보자

• address translation hardware(MMU)가 virtual address를 PTE 2를 가리키기 위한 index로 사용하고 메모리로부터 PTE 2를 읽어오게 됨
• valid bit가 1이기에 MMU는 VP2가 메모리에 캐시되어있다는 것을 알고 PTE의 address로 physical address에 접근하여 데이터를 가져옴

Page Faults

• DRAM cache miss가 page fault임

• Fig9.6 을 보면 CPU가 캐시되지 않은 PTE 3을 체크하고 valid bit가 set 되지 않았으므로 page fault exception을 발생시킴
• kernel에 있는 page fault exception handler를 호출. → victim page를 선택함
• 위 예시에서는 VP4(PP 3 위치의) 가 선택되었고 만약 VP4 가 수정되었다면 kernel은 VP4를 disk 로 다시 복사함
• 그리고 PTE4의 VP4에 해당하는 valid bit값을 업데이트함
• 그 후, VP3의 값을 메모리상의 PP3로 복사하고 PTE 3의 값을 업데이트 한 후 return

• page fault exception handler가 return된 후, 해당 virtual address에 대한 읽기 작업을 다시 수행. 이제는 캐시되어 있으므로 page hit가 발생

page 관련 용어

• swapping( or paging) : disk와 memory 사이에 page를 이동시키는 것

• swapped in(paged in) : disk에서 DRAM으로 페이지가 들어오는 것

• swapped out(paged out) : DRAM → disk 페이지 이동

• demand paging : 페이지를 swap-in 하는 마지막 시점까지 기다리는 전략

Allocating Pages

• VP5는 disk에서 공간을 만들고, PTE 5를 업데이트 함으로써 할당됨

Locality가 Paging 에서도 역할을 함

• miss에 대한 penalty로 paging이 프로그램의 성능을 많이 파괴할거라 생각하는데, 실제적으로는 virtual memory가 잘 작동하게 됨(locality에 의해)

• 프로그램이 참조하는 page가 physical memory의 사이즈를 넘어가는 상황에서도, principle of locality는 프로그램이 activate pages의 smaller set(working set, resident set)에서 작업을 한다는 것을 항상 보증함

• working set이 처음에 memory에 paged in 되는 overhead가 끝나고 나면, 그다음의 working set에 대한 순차적 참조는 hit를 계속해서 내기 때문에 disk traffic이 추가적으로 발생하지 않음

• 그러나 모든 프로그램이 좋은 temporal locality를 내지는 않기 때문에 , working set의 사이즈가 physical memory의 사이즈를 넘어가는 경우도 있음!!
• 이러한 상황에서 프로그램은 thrashing이라는 page가 계속해서 swap-in, swap-out이 발생하는 현상을 겪게 되고 프로그램의 성능을 매우 안좋게 만들어버림