[Parallel Computing] (14) Virtual Memory

Virtual Memory는 OS가 메인 메모리를 추상화하여 사용하는 개념이다. 각 프로세스는 각자의 고유한 크고 일정한 주소공간을 갖는 것처럼 동작할 수 있다. 또한 실제 메인 메모리 크기보다 더 큰 주소 공간을 가질 수 도 있다. 나머지 부족한 공간은 스토리지를 활용하여 채우게 된다. 프로세스가 특정 주소에 접근을 하면 OS는 이를 실제 주소(Physical Address)로 변환하여 메인 메모리에 접근한다. OS는 각 프로세스 별로 Page Table을 관리한다. 즉 프로세스는 실제 주소로 접근이 불가능하므로 다른 프로세스들이 사용하는 주소에도 접근할 수 없다. 이렇듯 추상화를 사용하면 각 프로세스의 메모리 공간은 보호가 된다. OS가 주소 변환을 수행하면, 매우 느리기 때문에 MMU(Memory Management Unit)을 하드웨어로 구성하여 주소 변환을 수행하도록 한다. 주소 변환을 수행하는 단위를 Page라고 한다. 보통 Page는 4KB로 구성된다. 이 때, 주소 변환은 Page Table를 검색하여 수행한다. Page Table은 PTE(Page Table Entries)의 배열로 구성되어 있으며, PTE 내부에는 Valid bit, n-bit address field가 존재한다. MMU가 이 Page Table을 읽어와서 주소 변환을 수행한다. OS(page fault handler)는 Page Table을 관리하고, 스토리지와 메인 메모리 간의 Page 전송을 수행한다. 스토리지와 메모리의 Page를 교환하는 것을 Swapping이라 한다. 메인 메모리에 해당 Page가 없을 경우 Page fault가 발생했다고 하며, 발생 시점부터 Page를 스토리지로부터 가져온는 때까지 기다리는 것을 Demand paging이라 한다.
Virtual page는 할당 되지 않은 상태이거나 할당되었고, 메인 메모리에 올라와있거나, 할당되었지만 아직 스토리지에 있고 메인 메모리에 올라와있지 않는 상태로 나뉠 수 있다. Page table에 해당 정보를 담아서 처리힌다.
Page table의 크기는 메모리 용량이 커짐에 따라 같이 증가한다. 하나의 Page Table에 다 담을 수 없으므로 hierarchy of page table을 사용한다.
Page Hit의 처리 순서는 아래와 같다.
1. CPU -> MMU로 Virtual Address 전달
2. MMU -> MEM로 PTE Address 전달
3. MEM -> MMU로 PTE 전달
4. MMU -> MEM로 Physical Address 전달

위의 과정을 살펴보면 2/3번은 Memory 접근이다. 만약에 Page를 접근하는데 Locality가 존재한다면, Page Table 자체도 Caching하여 사용하면 Memory 접근을 줄 일 수 있다. Page Table을 저장하는 Cache를 Translation Lookaside Buffer(TLB)라 한다.  
TLB를 활용한 Page Hit의 처리 순서는 아래와 같다.
(a) TLB Hit : 한 번의 메모리 접근이  한 번의 Cache 접근으로 변경.
1. CPU -> MMU로 Virtual Address 전달
2. MMU -> LTB로 VIrtual page number 전달
3. TLB    -> MMU로 PTE 전달
4. MMU -> MEM로 Physical Address 전달

(b) TLB MIss : 한 번의 메모리 접근이 한 번의 Cache 접근 + 한 번의 메모리 접근으로 변경.
1. CPU -> MMU로 Virtual Address 전달
2. MMU -> LTB로 VIrtual page number 전달
2. MMU -> MEM로 PTE Address 전달
3. MEM -> MMU/TLB로 PTE 전달
5. MMU -> MEM로 Physical Address 전달

Page Fault의 처리 순서는 아래와 같다.
1. CPU -> MMU로 Virtual Address 전달
2. MMU -> MEM로 PTE Address 전달
3. MEM -> MMU로 PTE 전달
4. MMU -> OS(Page fault hander)로 PTE Invalid 함을 알림
5. OS -> MEM, DISK로 Victim page 업데이트수행
6. DISK -> MEM로 요청된 Page 전달
7. MMU -> MEM으로 PTE Update 수행
8. OS -> Return to the orginal process
9. CPU -> MMU로 Virtual Address 전달
10. MMU -> MEM로 PTE Address 전달
11. MEM -> MMU로 PTE 전달
12. MMU -> MEM로 Physical Address 전달

메인 메모리에 있는 Page와 스토리지에 있는 Page를 교체할 때, 메인 메모리에 있는 어떤 Page를 교체할 것인가 선택해야 한다. 이를 Page Replacement policies라 하며, LRU, FIFO, Clock등의 알고리즘이 있다.
Clock 알고리즘은 각 Page들을 원형으로 연결하고, 시작점으로부터 바꿀 페이지를 찾는다. 기본적으로 각 Page는 메모리로부터 로드가 되면 0으로 표기하고, page가 사용되었으면 1로 표기한다. 시작점으로부터 0인 페이지를 찾기 시작하는데, 찾으면서 1로 세팅되어있는 값을 0으로 변경한다. 즉 순환하면서 최근에 쓰이지 않은 페이지를 선택한다.

Virtual address를 사용할 때 Data Cache는 어떻게 구성하는 것이 좋을 까?
Virtual address만으로 Cache를 사용하면 보안성에 문제가 발생한다. 각 프로세서는 동일한 virtual 주소값을 가질 수 도 있기 때문이다. 한 프로세서가 Cache를 사용하기 전에 이전에 다른 프로세서가 사용한  Cache를 비우고 사용하면 가능하지만 매우 큰 Overhead가 발생하다.
Physical address만으로 Cache를 사용하면 Virtual address -> Physical address 변환의 레이턴시를 모두 감당해야 하므로 느리다.
두 가지 주소를 모두 활용해서 Cache를 구성할 수 있다.
Cache는 index와 tag로 구성되는 데, 이 때 index/tag를 virtual 혹은 physical로 수행할 것인가에 대해서 케이스를 구분할 수 있다.
1. Virtually indexed, Virtually Tagged
-> 앞서 이야기한 것처럼 TLB를 접근하지 않지만, 프로세스 전환 시 오버헤드로 사용하기 어려움.
2. Virtually indexed, Physically Tagged
-> 주소 변환을 수행하면서, Cache indexing을 수행하고, 변환 결과로 Tag를 비교한다.
-> TLB 접근 시간과 Cache indexing을 동시에 수행하여 Latency를 가릴 수 있다.
3. Physically indexed, Virtually Tagged
-> 주소 변환을 수행한 이후, Physical 주소로 indexing을 수행하고, virtual 주소로 tag 비교를 함.
-> 이렇게 할 이유가 전혀 없음.
4. Physically indexed, Physically Tagged
-> 주소 변환을 수행한 이후, Physical 주소로 indexing/tag 비교를 모두 수행함.
-> TLB 접근 이후 Cache 접근 가능하므로 TLB Latency가 모두 보임.