[컴퓨터구조] 17-2. Virtual Memory - 2

Virtual memory가 없다면 여러개의 프로그램이 돌아가는 multi task system인 경우에, 각 프로그램의 0번지는 physical memory의 한 곳에 mapping 될 것이기 때문에 충돌이 발생할 것이다.

 

이말인 즉슨, single task program이라면 VM이 없어도 되겠지만 multi program이라면 VM이 반드시 있어야 하는 것이다.

https://ahnanne.tistory.com/15

 

TLB Event combinations

cache size가 충분히 크지 못하면 TLB랑 page table은 hit인데 cache는 miss인 경우가 나타날 수 있다.

page table miss는 physical memory에 없다는 뜻이기 때문에 cache가 hit일 수가 없다.

 

TLB Misses

• page가 memory에 있는 경우 (i.e. Valid bit is set)
  
  • 메모리의 PTE를 로드하고 재시도
  • hardware에서 다뤄질 수 있다. 
    
    • 하지만 더 복잡한 page table 구조로 복잡해질 수 있다.
  • 혹은 software에서 다뤄지는 경우 
    
    • 특수한 exception을 일으킨다.(with optimized handler)
• page가 memory에 없는 경우 (page fault)
  
  • OS가 page를 fetching하고 page table에 updating 하는 것을 관장한다.
  • 그러고나서 faulting instruction(page fault 였던 프로그램의 명령)을 재시작한다.

 

TLB Miss Handler

• TLB miss는 다음을 의미한다.
  
  • page는 존재하지만 PTE가 TLB에 없음 -> PTE에서 TLB로의 변환을 로딩하고 referencing을 다시 시도한다.(훨씬 더 자주)
  • 혹은 page가 존재하지 않음 -> 순수 page fault(true page fault)
• TLB miss를 반드시 destination register에 overwritten(덮어쓰기) 전에 인지해야 함
  • Raise exception
• Handler가 memory에서 TLB로 PTE를 복사한다. 
  
  • 그러고나서 instruction 재시작
  • 만약 page가 존재하지 않으면 page fault가 발생할 것이다.

 

Page Fault Handler

• PTE를 찾기 위해 faulting virtual address를 사용한다.
• disk에 page를 위치시킨다.
• 대체할 page를 고른다. (메모리의 위치 선택)
  
  • 만약 dirty인 경우 disk에 처음으로 write한다.
• memory로 page를 읽고 page table을 update한다.
• process를 다시 실행가능하도록 만든다.
  
  • faulting instruction의 재시작

 

Virtual Memory design parameters

 

TLB and Cache Interaction

• 만약 cache tag가 physical address를 사용한다면 
  
  • cache lookup 전에 변환이 필요하다.
• 대체 방식: virtual address tag를 사용
  
  • aliasing(중복) 때문에 복잡함 발생 
    
    • shared physical address에 대한 다른 virtual addressses
• content addressable memory (CAM)
  • 보통은 address가 가면 data가 나오는데
  • CAM은 ref가 들어가면 ref(content)와 matching 된 곳의 값이 나온다.

 

Why not Virtual addressable cache?

• 가상으로 접근되는 cache는 오직 cache misses에 대한 주소 변환만 필요로 할 것이다.

• But, Two programs which are sharing data will have two different virtual addresses for the same physical address (aliasing) so have two copies of the shared data in the cache and two entries in the TLB which would lead to coherence issues
• 그러나 데이터를 공유하는 두 프로그램은 동일한 physical address(aliasing)에 대해 서로 다른 두 개의 virtual address를 가질 것이므로 cache에 공유 데이터의 복사본이 두 개 있고 TLB에 두 개의 항목이 있으므로 일관성 문제가 발생할 수 있다.  
  • Must update all cache entries with the same physical address or the memory becomes inconsistent
  • 같은 physical address를 가진 모든 cache entries를 update 해야 한다. 그렇지 않으면 memory가 일관성이 없을 것이다.

하나의 PA를 공유하는 두 프로그램이 있다고 하면 cache coherence 문제가 발생할 수 있다.

 

Memory Protection

프로그램마다 각각의 page table만 잘 관리하면 이 프로그램은 정해져있는 PA만 access 가능하다.

어떤 task가 다른 task의 page에 access 할 수 없다.

• Multiple processes (programs) run at once
• 각 process는 자기 자신의 page table을 갖는다.
• 각 process는 전체 virtual address 공간을 사용할 수 있다.
• A process can only access a subset of physical pages: those mapped in its own page table
• process는 physical pages의 일부분만 접근할 수 있다: 즉, 자기 자신 소유의 page table에 매핑된 page

 

 

 

• user level code는 text segment에 저장된다.
• user program에 의해 사용되는 Static data(compile 때 아는 데이터)는 heap 공간에 저장된다.
• Dynamic data(runtime 동안에 할당되는 데이터)는 heap 공간에 저장된다.
• user program에 사용되는 stack은 subroutine call와 같은 행위 동안에 임시 데이터를 저장하는 데 사용된다.
• Kernel level code(exception and interrupt handlers)는 kernel text segment에 저장된다.
• kernel에서 사용되는 Static data는 kernel data segment에 저장된다.
• IO device의 memory mapped registers는 memory mapped IO segment에 저장된다.

 

Reducing translation time

• TLB access에 대한 cache access를 overlap 할 수 있다. 
  
  • VA의 상위 비트가 TLB에 접근하는 데 사용되는 반면 하위 비트는 cache의 인덱스로 사용되는 경우 작동한다

Virtual Memory Summary

• virtual memory는 capacity를 증가시킨다.
• physical memory에서 virtual page의 부분집합 
  • virtual page의 일부분(필요한 부분)만이 physical memory에 와 있다.
• Page table 은 virtual pages를 physical pages로 매핑한다.
  
  • address translation
• TLB는 address translation의 속도를 빠르게 해준다.
• 다른 프로그램들에 대한 다른 page tables은 memory protection을 제공한다.
  • 공유 문제

 

2-Level TLB Organization

32bit의 address는 -> 4G의 size

48bit의 address는 -> 64T의 size :사실상 무제한의 크기

 

Multi-level On-Chip Caches

write-allocate: write하려할 때 miss이면 memory까지 가서 cache에 올려 두고 write한다.

 

Questions for the memory hierarchy

• Q1: Where can a entry be placed in the upper level?
  (Entry placement)
• Q2: How is a entry found if it is in the upper level?
  (Entry identification)
• Q3: Which entry should be replaced on a miss?
  (Entry replacement)
• Q4: What happens on a write?
  (Write strategy)

cache와 virtual memory 각각

 

Q1 and Q2: where can an entry be placed/found?

separate lookup table

 

Q3: which entry should be replaced on a miss?

• Easy for direct mapped - only one choice
• Set associative or fully associative
  • Random
  • LRU (Least Recently Used)
    • handling 하기가 쉽지 않음.
• For a 2-way set associative, random replacement has a miss rate about 1.1 times higher than LRU
• LRU is too costly to implement for high levels of associativity (> 4-way) since tracking the usage information is costly

 

Q4: what happens on a write?

• Write-through
  • The information is written to the entry in the current memory level and to the entry in the next level of the memory hierarchy
    • Always combined with a write buffer so write waits to next level memory can be eliminated (as long as the write buffer doesn’t fill)
• Write-back :
  • The information is written only to the entry in the current memory level. The modified entry is written to next level of memory only when it is replaced.
    • Need a dirty bit to keep track of whether the entry is clean or dirty
    • Virtual memory systems always use write-back of dirty pages to disk
• Pros and cons of each?
  • Write-through: data consistency (so are simpler and cheaper), easier to implement
  • Write-back: writes run at the speed of the cache; repeated writes require only one write to lower level

 

Memory summary

• Locality의 원칙:
  
  • 어느 짧은 순간에 비교적 적은 비율의 address 공간에 접근하고자 하는 프로그램
    • Temporal Locality: Locality in Time
    • Spatial Locality: Locality in Space
• Caches, TLBs, Virtual Memory를 모두 그들이 다음 네 질문을 어떻게 다루는지에 보면서 이해해보자

1. entry가 어디에 위치할 수 있는가?
2. entry를 어떻게 찾는가?
3. miss 시에 어떤 entry가 교체되는가?
4. write은 어떤 방식으로 다뤄지는가?

• Page tables은 virtual address를 physical address로 매핑한다.
  
  • TLBs는 빠른 translation을 위해 중요한다.

 

---

Q) page fault의 경우 Hard disk에서 Page table로 가져오고 이를 TLB로 가져온 후에 Physical memory에 가져오는 것인지 아니면 바로 Physical memory에 load 된 다음에 page table과 TLB에 update 되는 것인지?

-> 그러면 Physical memory에 load 되는 data는 반드시 그 직전에 TLB를 거쳐서 온다고 이해했는데 이게 맞는지?

A) No. page fault의 경우 hard disk에서 찾은 다음에 PM에 비어있는 곳을 찾고 공간이 있으면 load 한다.

TLB miss의 경우 Page table을 확인하여 hit라면 tlb에 업데이트 하고 tlb를 통해 pm에 load