Virtual Memory

• main memory가 2차 저장장치(disk)를 위한 캐시로 이용된다.

• 가상 메모리를 사용하는 두 가지 이유
  • 다수의 프로그램을 동시에 수행할 때 메모리를 효과적으로 공유할 수 있다
  • 작고 제한된 크기의 메인 메모리에서 프로그래밍해야 하는 제약을 제거한다

• 각 프로그램은 자신만의 virtual address space에서 컴파일된다.
  • 이 프로그램에 의해서만 접근 가능한 분리된 메모리 영역
• 가상 메모리는 이 주소공간을 physical address로 변환해주고,
  이 변환 과정이 주소공간을 protect해준다.

• VM의 block은 page라고 불리고,
  VM의 miss는 page fault라고 불린다.

• VM을 갖는 프로세서는
  virtual address (가상 주소)를 만들어내고,
  가상 주소는 하드웨어 + 소프트웨어에 의해 physical address (실제 주소)로 변환된다.
  이를 adddress mapping 또는 address translation이라고 한다.

Page Fault

• On page fault, the page must be fetched from disk
  • 이 과정에서, 수백만 사이클이 소요된다.
• Try to minimize page fault rate,
  • Fully associative placement
  • smart replacement algorithms(LRU, ...)

• fully associative에서 가장 어려운 점은, entry의 위치를 알아내는 것이다. 어디에도 있을 수 있기 때문이다. 그렇다고 다 검색하고 앉아있는 건 비실용적이다
  -> page table

page table

가상 주소의 페이지 번호로 인덱스되어있고, 대응되는 실제 페이지 번호를 갖고 있다.
메모리 내부에 존재한다

• 각 프로그램은 본인만의 page table을 갖고 있으며,
  page table은 그 프로그램의 가상 주소공간을 메인 메모리로 사상한다.
• page table register는 CPU에 있으며,
  physical memory 내에 있는 page table의 시작 주소를 point한다

• cache와 마찬가지로 valid bit을 이용한다.
  • v = 0이면 해당 page는 main memory에 존재하지 않고, page fault가 발생한다
  • v = 1이면 해당 page는 main memory 내부에 있고, 그 entry는 실제 page 번호를 갖고 있다.

• 메모리 내의 페이지가 언제 쫒겨날지를 미리 알 수 없기 때문에,
  OS는 프로세스를 생성할 때 프로세스의 모든 페이지를 위한 공간을 플래시 메모리나 디스크 상에 마련한다. 이를 swap space라고 한다.
  • v = 0일 때, PTE(page table entry)는 disk의 swap space 주소를 refer할 수 있다.

Replacement and Write

• page fault rate를 줄이기 위해, LRU replacement 방식을 따른다.
  • 완벽하게 LRU를 구현하는 것은 expensive하기 때문에,
    유사 LRU 방식을 사용한다
  • reference bit(= use bit) (in PTE) 는 페이지가 접근될 때마다 1 값을 갖고, OS는 주기적으로 이를 0으로 초기화한다.
    • r bit = 1 : "Don't replace this page"
  • 이를 통해, reference bit = 0이면 최근에 이용하지 않았다고 판단한다

• write-back을 이용한다.
  • 캐시에서는 write-through를 이용할 수 있었지만,
    VM의 경우 다은 계층(disk)에 쓰는 것은 수백만 cycle이 소요된다.
    그래서 disk에 쓰기 위해 write-through로 구현하고 쓰기 버퍼를 첨가하는 것은 매우 비실용적이다.
  • 대신 write-back 방법을 이용하고,
    각각의 write 동작은 main memory 상의 page에만 수행된다.
    그리고 page가 메모리에서 교체될 때 disk로 복사된다.

---

TLB : Fast translation

• page table은 main memory에 저장된다
• 따라서 메모리 접근이 두 번 필요하게 된다
  1. 테이블에서 physiacl address를 얻기 위한 메모리 접근
  2. 실제 데이터를 얻기 위한 메모리 접근

• page table에 접근하는 것은 좋은 지역성을 갖는다
• 따라서 최근에 사용된 변환을 추적하는 특별한 캐시,
  TLB (Translation Look-aside Buffer)를 이용한다.

TLB Miss

• TLB hit이면, physical address를 가져오고, reference bit은 1이 된다.
  쓰기를 수행하면, dirty bit도 1이 된다.

• 만약 miss가 나면, 이게 단순히 TLB miss인지, page fault인지 알아야 한다

• TLB miss
  • page가 memory에 있긴 하다
  • 메모리(PTE)에서 주소 copy해서 TLB에 저장해주고 참조를 다시 시도한다

• Page Fault
  • OS가 처리해줘야 한다.
  • Use faulting virtual address to find PTE
  • Locate page on disk
  • Choose page to replace
    • if dirty, write to disk first (write-back)
  • Read page into memory and update page table
  • Make process runnable again
    • restart from faulting instruction

• TLB는 page table보다 훨씬 적은 entry를 가지고 있기 때문에,
  TLB miss는 page fault보다 빈번히 발생한다.
  

---

Memory Hierarchy

• 메모리 계층의 많은 부분들이 정량적으로는 다를지라도
  어떻게 계층이 동작하는지를 결정하는 원칙과 특징들은 정성적으로 유사하다
• cache에 사용되는 용어에 기반한다

Block Placement

블록을 어디에 위치시킬 수 있는가?

• associativity에 따라 결정된다

1. Direct mapped (1-way associative)
   • 집합의 수 = 캐시의 블록 수
   • 집합 당 블록 수 = 1
   • One choice for placement

2. n-way set associative
   • 집합의 수 = 캐시의 블록 수 / n
   • 집합 당 블록 수 = n
   • n choices within a set

3. Fully associative
   • 집합의 수 = 1
   • 집합 당 블록 수 = 캐시 내 블록 수
   • Any location

• Higher associativity는 miss rate을 줄여주지만,
  complexity, cost, access time을 증가시킨다.

Finding a Block

블록을 어떻게 찾는가?

1. Direct mapped
   • 위치 파악 방법 (Location method) : Index
   • 비교 횟수 (Tag comparision) : 1

2. n-way set associative
   • 위치 파악 방법 : set index, then set에 있는 모든 entry search
   • 비교 횟수 : n

3. fully associative
   • 위치 파악 방법 : 모든 entry search or Full lookup table
   • 비교 횟수 : entry 개수 (캐시 크기) or 0

• Hardware cache : reduce comparisons to reduce cost
• Virtual memory : full table lookup makes full associativity feasible.
  Also, benefit in reduced miss rate

Replacement

cache miss 시, 어느 블록을 교체시키는가?

• LRU
  • complex and costly hardware for high associativity

• Random
  • easier to implement

• Virtual memory : LRU approximation with hardware support

Write Policy

쓰기 시 어떤 일이 발생하는가?

• Write-through
  • upper level(캐시)와 lower level(메인 메모리)에 모두 update한다
  • 구현이 간단하지만, write buffer를 요구한다

• Write-back
  • upper level만 update한다
  • block이 replace될 때, lower level을 update한다
  • more state가 필요하다

• Virtual memory : lower level(disk)에 쓰기를 수행할 때 매우 큰 latency가 발생하기 때문에 write-back이 더 실용적이다.

---

3C Model

Compulsory miss (cold miss)

• First access to a block

Capacity miss

• Finite cache size
• block이 replace되고 나중에 다시 그 block을 가져올 때 발생

Conflict miss (collision miss)

• non-fully associative cache에서
  다수의 block들이 하나의 set에 대해 competition
• 같은 크기의 fully associative cache에서는 발생하지 않는다

---

Cache Design

Design change	Effect on miss rate	Negative performance effect
cache size 증가	capacity miss 감소	access time 증가
associativity 증가	conflict miss 감소	access time 증가
block size 증가	compulsory miss 감소	miss penalty 증가 For very large block size, miss rate 증가