9.3-VM_as_a_Tool_for_Caching

앞으로의 논의를 위해,
SRAM Cache 는 L1, L2, L3 Cache Memory, 즉 CPU 와 Main Memory 사이의 Cache를
DRAM Cache 는 VM System 의 Cache Memory, 즉 Main Memory 에서 Virtual Page 를 Caching 한다고 정해둔다.

DRAM 의 메모리 계층구조상의 위치는 중요하다.
DRAM 은 SRAM 에 비해 10배 정도 느리지만,
Disk 는 100,000 배 정도 느리기 때문에 DRAM 에서의 Cache Miss 는 매우 비싸다.
심지어, Disk 의 Read 속도는 경우에 따라 100,000배 정도 더 느려질 수 있다.
즉, DRAM 은 비용이 매우 큰 Cache Miss를 대비한 Cache 임을 알 수 있다.

이러한 배경 하에,
Virtual Page 의 크기는 매우 크다. 보통 4KB ~ 2MB 정도이다.
또한, DRAM 은 Fully Associative 하다.(Set 이 1개이다.)
Replacement Policy 또한, Miss에 대한 Penalty 가 높기 때문에 훨씬 정교하다.
SRAM 보다 정교하게 OS 에 의해 관리되는데, 그 알고리즘은 여기서 이야기하진 않는다.
Disk 에 대한 접근 시간이 길기 때문에 DRAM Cache 는 Write-back 방법을 사용한다.

다른 Cache 처럼, VM 도 Virtual Page 가 DRAM 어딘가에 Caching 되어있는지 알아야한다.
만약 Caching 되어있다면, 어느 Physical Page 인지 알아야하며,
Caching 이 되어있지 않다면, Disk의 어느 Virtual Page 인지 알아야하며,
Victim Page 를 결정해서, 복사해 Victim Page 를 없애야한다.

이러한 기능은 소프트웨어와
주소변환 하드웨어인 와
로 알려진, VP와 PP 를 맵핑해주는 Physical Memory 에 존재하는 자료구조로 관리된다.

MMU 는 Page Table 을 읽어, Virtual Address 를 Physical Address 로 변환해준다.
OS 는 Page Table의 내용을 관리하며, Page 를 Disk 와 DRAM 사이로 전달해주는 역할을 한다.

위 그림은 Page Table 의 기본적인 구조를 보여준다.
Page Table 은 의 배열로 이루어져있다.
Virtual Address Space 에 있는 각 Page 는 Page Table의 특정 Offset 위치에 PTE가 존재한다.
여기서는 PTE 는 Valid Bit 와 n-bit Address Field 로 구성되어있다고 가정한다.
Valid bit 은 현재 해당 Page 가 DRAM 에 Caching 되어있는지 알려준다.
Valid bit 가 설정되어있을 때, Address Field 는 해당 VP 가 Caching 된 DRAM 상의 Physical Page 의 시작점으로 설정되어 있다.

Vailid Bit 가 설정되어있지 있을 때는,
Address Field 가 Null 이라면 아직 Allocated 되지 않은 것이고,
Null 이 아니라면, 주소는 Disk 의 Virtual Page 를 가르킨다.

CPU가 VP2 에 존재하는 word 를 읽고자 한다고 해보자.
Address Transfer Hardware 는 Virtual Address 를 PTE 2로 향하는 Index로 바꾸고, 읽는다.
Vaild Bit 이 설정되어 있기 때문에, VP2 가 Memory 에 Caching 되어있음을 알 수 있고,
PTE 에 있는 Physical Memory Address 를 사용하여 접근한다.

VM 에서의 Cache Miss 는 Page Fault 라고 불린다.
위의 그림은 VP3, Caching 되지 않은 Page 에 대한 접근 시도 전후를 나타낸 그림이다.
Address Translate Hardware 는 PTE3 를 읽으려고 하는데,
Valid Bit 가 설정되어 있지 않으므로 Page Fault Exception 을 일으킨다.
이것은 Kernel 의 Page Fault Exception Handler 를 유도하게 된다.
Handler 는 Victim Page 를 고르게 되는데, 위의 예제에서는 PP3 에 존재하는 VP4에 해당한다.
VP4 에 변경사항이 있다면, Kernel 은 복사본을 Disk 에 전달한다.
없다면, Kernel 은 VP4 에 대한 PTE 를 변경하여, VP4 가 더이상 Caching 되고 있지 않다는 사실을 반영한다.

그 다음 Kernel 은 Disk 에 있는 VP3 를 메모리의 PP3 로 복사하고, PTE3 를 업데이트하고 반환한다.
Handler 가 반환되고 나서는 실패한 명령어를 다시 실행한다. 즉, 실패했던 Virtual Address 를 Address Translation Hardware 로 재전송한다.
이제는 VP3 가 Caching 되어있기 때문에 Page Hit 가 정상적으로 발생한다.

VM 은 1960년대 초기, 즉 CPU-Memory 간의 성능차이가 크지 않아서 SRAM Cache 가 없었을 때 생겼다. 이로 인해 VM과 Cache 간의 아이디어가 비슷함에도 다른 용어를 사용하게 되었다.
Cache 의 Block 은 VM의 Page 와 유사하다.
Page 를 Disk 와 Memory 사이로 전달하는 것은 Swapping 과 Paging 이라는 용어를 사용한다.
Page 는 Disk 에서 DRAM 으로 되고,
DRAM에서 Disk 로 된다.

Miss 가 발생할 때까지 기다리다가 Swap In 을 하는 전략을 이라고한다.
미리 Miss 를 예측해서 Swap 을 하는 것도 가능하지만,
현대의 시스템은 Demand Paging 을 사용한다.

위의 그림은 OS 가 새로운 Page 를 할당할 때의 모습이다. (예를 들어 malloc)
해당 예제에서는 VP5가 Disk에 할당되어, PTE5가 해당 Disk 를 가르키게 된다.

Miss Penalties 를 고려하면, 프로그램의 성능에 우려가 있을 수 있다.
그러나 프로그램의 Locality 덕분에 VM 은 잘 작동한다.

프로그램 전체에서 사용하는 Page 는 physical Memory 가 실제 가능한 Page 를 넘을 수도 있지만, Locality 는 smaller set of Active Page, 즉 Working Set or Resident Set 으로 작업하게 해준다.
초기에 Working Set 을 Read 하는 OverHead 를 제외하면, 그 후 참조는 Disk 참조를 덜 할 수 있다.

프로그램이 Temporal Locality 를 잘 지키는 한, VM 은 잘 작동한다.
만약 어떤 프로그램이 Temporal Locality 를 잘 지키지 못한다면,
Working Set 이 가능한 Physical Memory 를 초과할 수 있다.
이 때, 이라는 상황이 발생하는데, 이는 Page 가 Swapped In 되고 다시 Out 되는 것이 반복되는 상황이다.
VM은 보통 효율적이지만, 프로그램이 느리다면 Thrashing 은 아닌지 고려해봐야한다.