5. Virtual Memory

Virtual Memory

Main memory를 disk에 대한 cache로 사용한다.

 

Disk access 속도는 매우 느리기 때문에 software로 커버 가능하다.

Hardware로 구현 가능하지만, 비용 대비 성능이 잘 나오지 않기 때문에 software로 구현한다.

 

Cache memory와 독립적이지만, issue는 cache memory와 동일하다.

• Placement(mapping)
• Identification
• Write strategy
• Replacement policy

 

---

Placement, Identification

'Disk에서 가져온 내용을 main memory의 어디에 실을 것인가'

Disk의 virtual page가 main memory의 physical page로 page 단위 mapping 된다.

 

Fully associated mapping과 유사하다.

Virtual page는 무한대의 자유도를 가지며 어디에든 넣을 수 있다.

그리고 software로 구현하기 때문에 구현이 복잡하지도 않다.

 

Page Table

다만 넣은 위치를 page table에 기록한다.

Page table은 각 process마다 존재하며, 모든 virtual page에 대한 정보가 들어있다.

 

Protection

Main memory는 여러 process가 공유하는 영역이다.

때문에 하나의 process가 다른 process의 영역을 침범하지 않도록 protection 해야 한다.

자신의 page table만 참조함으로써 다른 process의 영역을 침범하지 않을 수 있다.

 

Placement

Page table에는 각 virtual page들마다의 다음 내용을 포함하고 있다.

• V(Valid) : virtual page들이 main memory에 caching 되어 있는지
• PPN : 어느 physical page에 caching 되어있는지
• Disk location : disk에서의 address는 무엇인지 

 

 

Creating a Process

Process를 만들 때

• OS는
  • disk나 flash memory에 프로세스의 모든 page들을 위한 공간을 만든다.
  • process의 page table을 만든다.
  • disk의 각 virtual page들의 location을 기록한다.(disk location)
  • 어떤 process, 어떤 virtual page가 각 physical page를 사용 중인지 추적해야 한다.
  • page replacement는 LRU에 근사하게 수행한다.
• Process는
  • process switch(context switch)되어야 한다.
    • Page table (page table register) 교체
    • program counter 교체
    • register 교체

 

Mapping Pages to Storage

Page를 찾는 과정은 다음과 같다.

1. page table에서 virtual page number에 해당하는 곳으로 가서 valid를 확인한다.
2. 해당하는 장소에 가서 page를 참조한다.
   • valid = 1 : page hit : PPN을 이용해서 physical memory의 내용을 참조한다.
   • valid = 0 : page fault : disk location을 이용해서 disk에서 내용을 참조한다.

 

Page Fault Penalty

Page fault가 나면 disk에 가서 가져와야 한다.

그런데 disk access는 너무 오랜 시간이 필요하다.

 

따라서 process switch(context switch)를 해서 다른 process로 바꾼다.

이를 통해 disk에서 page를 가져오는 동안 다른 process의 작업을 더 할 수 있다.

 

Page fault로 인한 손실이 너무 크기 때문에 다음과 같은 조치를 해야한다.

• page를 크게 해서 spatial locality를 최대한 활용한다.
• page table을 이용해서 fully-associative mapping을 한다.(자유도를 최대로 함으로써 address conflict를 줄인다.)
• replacement 알고리즘을 잘 만들어서 page fault가 최대한 안나게 한다.

 

---

Write Strategy, Replacement

Write Strategy

Disk write는 수백만 cycle이 걸린다.

때문에 main memory에 write를 할 때마다 해당 word를 disk에 쓰는 write through는 적절치 않다.

 

따라서 write back을 이용한다.

이를 위해서 page table entry에 dirty bit을 추가한다.

 

Page replacement가 일어날 때 dirty bit이 1라면 해당 page를 disk에 write 한다.

 

Replacement

Page fault rate를 줄이기 위해서 least-recently used(LRU) replacement를 사용한다.

최근에 사용 안된 것을 제거한다.

이를 위해서 page table entry에 reference bit을 추가한다.

 

다만, page의 수가 너무 많기 때문에 완전한 LRU 방식을 사용하기 힘들다.

따라서 LRU에 근사한 방법을 이용한다.

 

Page에 access할 때 1로 set하고, 주기적으로 reference bit을 0으로 clear한다.

만약 reference bit이 0이라면 최근에 이용되지 않은 것이므로 replacement의 대상이 된다.

 

---

Address Translation (Virtual address → Physical address)

CPU가 내는 주소는 virtual address이므로, OS가 page table을 이용해서 physical address로 바꿔야 한다.

 

과정

1. page table register를 통해 현재 process의 page table을 참조한다.
2. virtual page number를 이용해서 해당하는 virtual page의 valid bit를 확인한다.
3. valid bit가 1이면 physical page number와 page offset을 합쳐서 physical address를 만든다.
4. valid bit가 0이면 현재 main memory에 caching 되어있지 않은 것이므로 disk에서 fetch 해야 한다.

 

문제점

Page table은 main memory에 존재한다.

따라서 매 instruction 실행 마다 총 2번의 main memory access가 일어나야 한다.

• address translation을 위해서 main memory에 access
• 실제 내용을 fetch하기 위해서 main memory에 access (cache memory가 없다고 가정)

 

Main memory는 느리기 때문에 좋지 않은 현상이다.

이를 해결하기 위해서 TLB를 사용한다.

 

TLB(Translation Look-aside Buffer)

Address translation을 빠르게 하기 위해서 사용하는 buffer이다.

 

Page의 크기가 크면 locality에 의해서 한동안 동일한 VPN-PPN으로 mapping이 일어난다.

따라서 최근에 사용된 VPN-PPN pair를 buffer에 저장한다.

여기에 사용되는 buffer를 TLB(Translation Look-aside Buffer)라고 한다.

 

Locality가 좋기 때문에 대부분의 page 정보가 TLB에 존재한다.

전형적으로 16-512 PTEs, 0.5-1 cycle for hit, 10-100 cycles for miss, 0.01%-1% miss rate을 가진다.

 

TLB에서 모든 동작을 마쳐야 하기 때문에 page table의 valid, dirty, reference bit도 그대로 복사한다.

 

TLB를 이용한 translation 과정은 다음과 같다.

1. TLB에서 내가 원하는 virtual page의 pair를 찾는다. (parallel matching)
   
   1. TLB hit : 내가 원하는 page number가 있으면 바로 PPN로 바꾼다.
   2. TLB miss
      1. page table에 가서 내가 원하는 page를 찾는다.
      2. page hit : PPN으로 바꾼다.
      3. page miss : disk에서 page를 fetch하고, TLB를 update 한다.