5. Virtual Memory

OS의 목표 중 하나는 physical memory가 부족할 때, 프로세스가 최대한 동작하게 만드는 것이다. 가령 user의 code 영역은 프로세스마다 physical memory에 저장할 필요가 없을 것이다. Virtual memory는 physical memory가 훨씬 더 많은 것처럼 환상을 주는 OS의 핵심 스킬이다.

 

Locality of reference

프로세스 내부에서 얼마나 연속적이거나 근처에서 참조하는지 나타내는 지표를 locality라고 한다. 크게 2가지의 locality가 있다.

• Spatial: 참조한 address 근처 address를 참조
• Temporal: 참조한 address 다시 참조

프로세스는 code의 10%에 90%의 시간을 쓸만큼, locality를 고려해 code를 작성하는 것은 매우 중요한 일이다. Locality를 고려해 code를 작성한다면, 프로세스가 적은 address space만을 사용할 수 있게 된다.

 

Memory hierarchy

Register가 비용이 비싸지만, 제일 빠르고 disk가 제일 저렴하지만, 제일 느린 구조로 이루어져 있다. 그렇기 때문에 locality를 고려해 code를 작성해야, replacement를 최소화하여 overhead를 줄일 수 있게 된다.

 

Virtual memory

Intuition

기본적으로 데이터는 disk에 저장되며, 참조가 될 때마다 main memory, cache, register에 올라오게 된다. Disk의 속도가 매우 빠른 것처럼 만들기 위한 노력이며, 이를 위해서 OS는 page의 위치를 관리할 수 있는 메카니즘, 어떤 page가 memory에 있을지 결정하는 policy가 있어야 한다.

 

Virtual address space mechanism

Virtual address space에서 각 page는 다음 3개의 상태(위치)를 가진다.

• Physical main memory
• Disk
• Nothing(free)

 

또한 page table에 present bit이 추가되어 총 3가지, permission, valid, present bit을 가지게 된다. Page가 memory에 있으면, present bit이 1로 설정되고, disk에 있으면 0으로 설정된다. PTE에 present bit이 0이면, OS는 trap(page fault)을 날리고 disk에 접근해서 데이터를 가져와 main memory에 올린다.

 

Virtual memory mechanism

Hardware랑 OS가 협력해서 VA를 PA로 바꾸게 된다. Adderss 참조가 이루어지면, 다음의 과정이 수행된다.

1. TLB 확인
   1. TLB hit (done)
   2. TLB miss
      1. PTE present bit 1 (page is in physical memory, done)
      2. PTE present bit 0 (page fault)
         1. OS에 Trap 날리기
         2. OS는 memory에서 victim 선택
         3. Disk에서 해당 page를 memory로 옮김
         4. Page table update, present bit update
         5. Done

 

Page fault가 발생하면, CPU pipeline은 멈추고, 업데이트 이후에 해당 instruction을 다시 수행하게 된다.

 

Virtual memory policy

Page fault를 최소화하기 위해, victim page를 잘 선택해야 한다. 이를 위해 OS는 2가지 방식을 사용할 수 있다.

• Page selection: disk to memory
• Page replacement: memory to disk

 

Page selection

Disk에서 memory로 언제 page가 load되는지 결정하는 방법이다. 크게 2가지 방식이 있다.

• Demand paging: page fault가 발생했을 때, page load한다.
  • 프로세스가 시작할 때, 아무 page도 load되지 않는다.
  • 새롭게 접근되는 page의 page fault cost는 항상 지불하게 된다.
• Pre-paging: 참조가 되기 전에, 예측해서 page load한다.
  • Sequential access같은 패턴들을 예측해서 미리 page를 load한다.
  • 예측이 틀리면 큰일난다.

 

실제로는 두가지를 잘 섞어서 load할 page를 결정한다.

 

Page replacement

Main memory에 page가 가득 차 있을 때, 어떤 page를 victim으로 설정할 것인지에 대한 방법론이다. Victim page가 modify되었으면, dirty bit을 set해두고 disk에 작성한다. 만약 victim page가 clean하다면, 그냥 버린다.

 

이를 최적화하려면 미래에 장기간 사용이 안될거 같은 page를 discard하면 된다. Page fault를 최소화할 수 있다는 장점이 있지만, OS가 미래를 예측해야 하는 단점이 있다.

 

대표적인 교체 방법으로는 FIFO, LRU가 있다.

• FIFO
  가장 처음 참조된 친구를 버린다.
  장점: fair, easy to implement
  단점: 어떤 page는 항상 필요할 수 있음
• LRU
  장기간 사용 안된 친구를 버린다.
  장점: Temporal locality를 가지면, LRU가 best이다.
  단점: hard to implement(page 참조 횟수 counting), 적합하지 못한 workload있음
• Clock algorithm
  PTE에 clock bit 추가
  참조되면 1로 설정, 아니면 0으로 유지
  Page fault 발생 시, PTE를 돌면서 1이면 0으로 변경, 0인 PTE 찾으면 해당 PTE victim으로 설

 

FIFO performance issue

FIFO의 경우, 메모리 크기가 커질수록 오히려 성능이 감소할 수 있다. 가령 ABCDABEABCDE의 access가 있고 3 pages나 4 pages를 메모리에 저장할 수 있다고 생각해보자.

위 그림처럼 page fault가 발생하게 되고, 3 pages일 때 9 miss, 4 pages일 때, 10 miss가 발생하게 된다.

 

LRU problem

자주 접근하는 page가 많을 경우, 자주 접근하고 있음에도 지속적으로 교체될 수 있다. 가령 큰 파일을 읽는 경우가 그러하다. 이를 해결하기 위해 page를 참조하는 횟수를 기록하여 가장 덜 사용되는 page를 victim으로 선정하는 방법이 있다. LFU(Least-frequently-used) 방법이다.

 

LRU implementation

LRU 구현은 SW, HW 2가지 방법으로 가능하다.

• SW perfect LRU
  OS가 page에 참조하는 시간을 기록해 ordered list로 관리한다.
  Page가 참조되면, 맨 앞으로 옮긴다.
  반대로 fault가 발생하면, 맨 뒤에 있는 친구를 지운다.
  참조할 때는 느리지만, replacement할 때는 빠르다.
• HW perfect LRU
  각 page에 참조 시간을 기록하는 register를 구현한다.
  Page 참조할 때마다, 시간을 기록한다.
  Victim 선정이 필요할 때, register를 훑어보고 oldest를 선택한다.
  참조할 때는 빠르지만, replacement할 때는 느리다.

실제로 사용할 때는, perfect LRU를 사용하지 않는다. 가장 오래된 page를 victim으로 선정하기 보다는, 적당히 오래된 page를 찾아 victim으로 선정해 사용한다.

 

Clock algorithm

Clock algorithm은 앞선 설명처럼, clock bit를 따로 관리하여 victim을 설정하는 방식이다. PTE를 훑으면서 bit가 1이면 0으로 바꾸고, 0이면 victim으로 선정한다.

 

이를 확장해서 한번에 여러 page를 replace하기도 한다. Replacement 과정에서 발생하는 비용이 크기 때문에, 한번에 여러개의 victim을 찾는 것이다.

 

또 다른 확장으로는, chance를 추가하는 것이다. Bit가 0으로 설정된 page를 모두 찾아서, 그들 중에 하나를 victim으로 사용하는 것이다. 이러면 LRU와 비슷해진다.

 

마지막으로는 dirty page를 victim으로 선정하는 것이다. 이들은 어차피 disk에 작성되어야 하기 때문에 교체 비용이 크다. 따라서 메모리에서 교체할 겸, disk에도 작성한다고 생각하면 된다.