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

program마다 사용할 수 있는 address space가 있음

• CPU에는 여러 프로그램들이 존재하고 각 프로그램마다는 주소가 존재한다.
• HDD에는 각 프로그램이 사용할 수 있는 virtual memory 공간이 할당되어 있다.
• program마다 사용할 수 있는 용량이 100GB라고 하고 실제(physical) 메모리에는 10GB만 있다고 해 보자
• 프로그램은 100GB를 사용할 수 있지만 실제로 bus를 통해 가는 경로는 PM(Physical memory)에서 간다.
  • 근데 어떻게 10GB에서 오는데 100GB를 사용?

• VM에서 일부분은 PM에 존재하지만 VM의 나머지 부분은 hard disk에 있다. 그래서 PM에 없다면 100만배를 기다려서 hard disk에 갔다와야 하기 때문에 잠시 stop 해 놓고 갔다오는 도중에 다른 program을 실행시키도록 한다.
• 이 때의 miss rate을 최소화하기 위해서 fully associativity 방식을 사용해야 한다.
  • 이를 통해 프로그램 할당된 여러 address 들이 모두 같은 0번지를 가지겠지만 이것이 실제 PM에 mapping 될 때는 다른 곳에 위치하게 되는 것이다.
  • 근데 fully associative는 어디에 위치했는지를 아는 것이 중요하다.
    • 어디 들어있다고 기록을 하는 장치(table)가 PM에 따로 존재 -> Page Table

 

• performance 즉, miss rate을 제일 신경써야 한다.
• 가져오는 단위가 cache에서는 block이었는데 hard disk는 page이다.

• miss-rate을 줄이기 위해서
  1. Block size를 늘린다.(Block보다 더 큰 Page 단위)
  2. associativity를 늘린다. (-> fully associativity; 늘릴수 있는 최대의 associativity)
     • VM에서는 무조건 fully associativity
  3. capacity size를 키운다.

• address가 어디 들어있는지를 알려주기 위해 각각의 VM마다 Page Table(PT)를 준다.
  • 내가 쓰고 있는 page는 다른 사람들 보고 access하지 못하게 할 수 있다.

 

miss rate을 최소화하기 위해서 fully associative를 사용 -> 아무데나 들어갈 수 있음

이 때 어디 들어왔는지 어떻게 아느냐? -> Page Table

프로그램마다 page table을 갖기 때문에 A 프로그램의 0번지와 B 프로그램의 0번지는 다른 곳에 위치해 있다.

1. CPU가 page table에 가서 해당 page에 접근한다.
2. 이 때, Memory에 올라온 상태가 아니면(invaild), Interupt를 발생한다.
3. OS 내부의 ISR에서 이 인터럽트를 처리하러 Disk에서 page를 찾는다.
4. 찾은 Page를 Memory에 올려 Frame화 한다.
5. page table을 업데이트 한다.
6. CPU에게 다시 수행하라고 명령한다.

 

Virtual memory

Virtual Memory

• 더 큰 memory인 것 같은 착각을 가져온다.
• Main memory(DRAM)은 hard disk에 대한 cache 처럼 행동한다.

cache <-> Main memory : hardware 적인 이동

CPU에는 각 여러개의 프로그램이 있을텐데 각각 cache의 메모리를 사용하는 것이다.(virtual mermoy)

main memory <-> Hard disk : OS가 관리

 

Memory Hierarchy

stall 하기에 너무 긴 시간이 걸리는 경우는 page fault

 

Hard disk

• Nonvolatile(비휘발성), rotating magnetic storage

• Takes milliseconds to seek correct location on disk

sector가 하나의 데이터를 저장하는 단위

 

Disk Sectors and Access

• surface당 수만 개의 트랙이 있으며 각 트랙은 sector로 구분됩니다
• 각 sector는 다음을 기록한다. 
  • Sector ID
  • Data (512 bytes, 4096 bytes proposed)
  • Error correcting code (ECC)
  • 결함 및 기록 오류를 숨기기 위해 사용됨
  • Synchronization(동기화) fields and gaps
• sector에 대한 접근은 다음을 수반한다.
  
  • 만약 다른 접근이 pending 중이면 Queuing delay
  • Seek: move the heads
  • Rotational latency
  • Data transfer
  • Controller overhead

 

Disk Access Example

• 주어진 조건 – 512B sector, 15,000rpm, 4ms average seek time, 100MB/s transfer rate, 0.2ms controller overhead, idle disk
• Average read time
  • 4ms seek time
    + ½ / (15,000/60) = 2ms rotational latency
    + 512 / 100MB/s = 0.005ms transfer time
    + 0.2ms controller delay
    = 6.2ms
• 만약 실제 average seek time이 1ms이면 – Average read time = 3.2ms

 

Disk Performance Issues

• 제조업체는 average seek time를 인용한다.
  
  • 모든 가능한 seek에 기반
  • Localiity와 OS scheduling은 더 작은 실제 average seek times을 초래한다. 
    • 한 track의 sector에 access하면 다음에도 그 근처를 access할 확률이 높다.
• 똑똑한 disk controller가 disk에 물리적 sector를 할당한다. 
  • host에게 logical한 sector를 제시한다.
  • SCSI, ATA, SATA
• Disk drives는 caches 를 포함한다. (RAM)
  • Prefetch sectors in anticipation of access
  • Avoid seek and rotational delay

 

Virtual Memory

• Virtual addresses
  • Programs은 virtual addresses를 사용한다.
  • hard drive에 저장되는 전체 virtual address space
  • DRAM에 존재하는 virtual address data의 부분집합
  • CPU가 virtual address를 physical address(DRAM addresses)로 변환(translate)한다. 
    • page table에 기반하여 translate
  • hard drive로부터 fetch되는 DRAM에 있지 않은 데이터 
    • OS가 page fault 발생시킴(cache의 miss와 같은 것)
• Memory Protection
  
  • 각 프로그램은 각자의 virtual to physical mapping 정보(Page Table)를 가지고 있다.
  • 두 프로그램은 다른 데이터에 대해 동일한 virtual address를 가질 수 있다.
  • 프로그램은 다른 프로그램이 실행 중인지 여부를 알 필요가 없다.
  • 하나의 프로그램(혹은 바이러스)은 또 다른 프로그램에 의해 사용되는 메모리를 방해할 수 없다.

 

Cache/Virtual Analogues

Physical memory는 virtual memory에 대한 캐시로 동작한다.

 

 

Virtual Memory Definitions

• Page size: hard disk에서 DRAM으로 한 번에 이동되는 메모리의 양
• Address translation: virtual address에 의해 physical address를 결정
• Page table: virtual addresss를 physical addresses로 변환하기 위해 사용되는 lookup table

 

Virtual and Physical Address

physical memory에서 대부분의 accesses는 hit이다.

하지만 프로그램은 virtual memory의 큰 용량을 갖고 있다.

• 모든 프로그램은 각자의 Virtual address 용량을 모두 사용한다.
• 그런데 이 중에서 Physical address에 있는 것은 일부분만이 들어와 있다.

 

Address Translation

VPN: Virtual Page Number

PPN: Physical Page Number

• Virtual address = virtual page number + page offset
• page size가 4k라고 하면 그 4k가 되는 page 중에서 어디인지를 알아내는 것이 page offset이다.
• Virtual address에서나 physical address에서의 page는 똑같을 것이기 때문에 동일한 page offset이 존재한다.
• 따라서 VPN -> PPN 변환 과정이 translation의 전부이다.

 

Vitual Memory Example

• System
  • Virtual memory size: 2 GB = 2³¹ bytes
  • Physical memory size: 128 MB = 2²⁷ bytes
  • Page size: 4 KB = 2¹² bytes
• Organization:
  • Virtual address: 31 bits
  • Physical address: 27 bits
  • Page offset: 12 bits
  • # Virtual pages = 2³¹/2¹² = 2¹⁹ (VPN = 19 bits)
  • # Physical pages = 2²⁷/2¹² = 2¹⁵ (PPN = 15 bits)

Virtual Memory Example

• 19-bit virtual page numbers (VPN)
• 15-bit physical page numbers (PPN)

virtual page number 7FFFF -> 111 1111 1111 1111 1111 -> 19bit

 

 

• 위에서 봤듯이 page offset은 12 bit이기 때문에 3byte이므로 0x247C의 주소에서 뒤의 47C는 page offset을 나타낸다.
  • 47C -> 0100 0111 1100
• 따라서 VPN는 0x2가 되고 이를 PPN으로 변환해야 한다.
  • 0x2는 VPN에서 00002를 뜻하고 이는 Physical memory의 7FFF에 있다.
  • 00002 (VPN) => 7FFF (PPN)
  • 그래서 Virtual address의 2부분을 7FFF로 바꿔주면 된다.
• 따라서 최종적으로 Physical address는 0x7FFF47C 가 된다.

위 그림에서 VM과 PM이 이어진 것은 누구를 통해서 이루어 지는가?(Virtial memory를 Physical memory의 어디에 두어야 하는가)

• fully associative

 

How to perform translation?

• Page table
  • 각 virtual page에 대한 entry
  • Entry fields:
    • Valid bit: physical memory에 있는 페이지라면 1
    • Physical page number: 페이지가 위치한 곳

 

Page Table Example

Virtual page number로 page table에 먼저 접근해서 있으면 해당 table에서 Physical page number와 page offset을 합쳐 physical address를 만들어 낼 수 있다.

 

Page Table Example 1

What is the physical address of virtual address 0x5F20?

Page Table Example 2

What is the physical address of virtual address 0x73E0?

• VPN = 7
• Entry 7 is invalid (V = 0) -> page fault
  
  • Virtual page는 disk로부터 physical memory로 page되어야 한다.(page fault)

 

Mapping Pages to Storage

Replacement and Writes

hard disk 까지 가야하는 경우를 대비하여 miss rate을 줄여야 하기 때문에 performance가 중요하다.

• page fault rate을 줄이기 위해서, least recently used (LRU) replacement가 선호된다.
  • 페이지에 접근할 때 PTE(page table entry)안에 Reference bit (aka use bit)이 1로 설정된다.
  • 주기적으로 OS에 의해 0으로 초기화 된다.
    
    • 주기적으로 0으로 바꿔주기 때문에 자주 쓰는 주소는 계속 1로 되어있을텐데 쓴 지 오래 된 것은 0으로 바뀌는 구조이다.
  • A page with reference bit = 0 has not been used recently
• Disk는 write하는데 수백만 cycle이 걸린다. 
  • Write through is impractical - 매우 비효율적
    • memory에 써질 때마다 disk에 올리는 것 -> 미친짓
  • Use write-back
    • 계속 memory만 write하다가 memory page가 쫓겨 나야 할 때 memory에 써지는 방식
    • 즉, 메모리의 한 부분이 새로운 내용으로 바뀌려고 할 때
  • Dirty bit in PTE set when page is written
    • 메모리가 쓰여졌는지(내용이 바뀌었는지) 확인하는 bit

 

Page Table Challenges

• Page table이 큰 것 
  
  • 보통 physical memory에 위치함
• Load/store는 2개의 main memory 접근을 요구한다. (중요한 부분)
  • 하나는 translation을 위한 것 (page table read)
  • 하나는 데이터 접근을 위한 것 (after translation)
  • 즉, 실제 메모리에 접근하기 전에 Page Table을 통해 어디에 있는지를 먼저 보는 것이다.
• 근데 page table도 결국은 DRAM이기 때문에 느리다.
• 이 두 번 access 하는 것도 더 줄일 수 있을까? -> locality 사용
• memory performance를 반으로 줄일 수 있다. 
  
  • 우리가 더 똑똑해지지 않는다면...

 

Translation Lookaside Buffer (TLB)

• 일종의 page table cach
• most recent translations의 small cache(가장 최근에 변환된 것의 캐시 기능)
• 대부분의 loads/stores에 대한 memory access의 수가 2에서 1로 감소한다.
• TLB에 없으면 miss이기 때문에 PT가서 가져옴
• TLB가 꽉차면 쫓겨낼 때 메모리에 write

 

따라서 CPU에서 바로 Page table을 보고 물리적 주소로 변환하는 것이 아니라 중간에 있는 TLB를 먼저 봐서 최근에 access했던 virtual page가 physical page의 어디에 위치해 있는지 찾고 바로 해당 값으로 변환하는 것이다.
(물론 값이 있다면)

• TLB가 hit면 바로 가져옴
• TLB가 miss면 Page table에 가서 만약 valid 이면 최근에 access만 안 되었을 뿐이지 있다는 뜻이므로 TLB로 옮겨서 Physical memory로 찾아가고
• page table에 가봤더니 valid가 0이면 physical memory에 데이터가 존재하지 않는다는 뜻이기 때문에 page fault이고 Hard disk로 가는데 이는 시간이 너무 많이 걸리기 때문에 그냥 이 프로그램은 stop 시키고 기다리고 있는 다른 프로그램을 실행시켜 준다.

 

• 정리하자면 원래는 CPU에서 접근하고자 하는 virtual address가 있는데 이는 Physical addess로 변환되어야 한다. 그런데 변환을 하려면 fully associative 구조에서 찾아야 하기 때문에 page table을 이용하여 가상 메모리 공간을 index로 지정한 곳을 보고 변환을 하는 것이다. 그런데 여기서 또 page table에서 변환을 했던 것을 TLB에 기록하여 page table을 들리지 않고 물리적 주소를 얻을 수 있게 된다.
  • 즉, CPU가 어떤 virtual address를 사용하려고 하는데 TLB를 먼저 봐서 최근에 virtual page에서 physical page로 변환되었던 적이 있나 보고, 만약 있다면 그 값으로 바로 변환이 되고
  • 값이 없다면 상위 단계인 page table에 가서 해당 virtual address에 해당하는 physical address가 있나 보고, 있다면 그 주소로 변환이 되고 만약 없다면 hard disk에 가서 가져와야 하는 것이다.

 

TLB

• Page table accesses: high temporal locality
  • 큰 page 크기, 동일한 페이지에 액세스할 가능성이 높은 연속 loads/stores
• TLB
  • Small: accessed in < 1 cycle
    • CPU와 거의 같은 cycle
  • Typically 16 ~ 512 entries
  • Fully associative, N-way도 적은 비율로 사용하긴 함.
    • -> 99 % hit rates typical
      • -> 거의 memory access를 한 번만 한다는 의미
  • 대부분의 loads/stores에 대한 메모리 접근 수가 2에서 1로 감소한다.

 

Example 2-Entry TLB

• 2개 짜리 TLB
• TLB를 먼저 봐서 같은 것이 있다면 해당 Physical page number를 바로 가져와서 사용한다.
• cache랑 다른 점
  • cache에서는 Tag이던 게
  • TLB에서는 Virtual Page Number이다.

 

Fast Translation Using a TLB

☞ The next few slides are excerpts(발췌) from the book, COD, and Prof. Mary Jane Irwin’s lecture notes (PSU).

• TLB miss -> Page Table에서 가져옴
  • valid로 판단
• Page Table miss -> Page fault -> Hard disk에서 가져옴

 

Trasnlation Lookaside Buffers (TLBs)

• 다른 cache들 처럼 TLB는 fully associative, set-associative, direct-mapped로 구성될 수 있다.
• TLB access time은 일반적으로 cache access time보다 짧다.(TLB는 cache보다 훨씬 더 작기 때문에) 
  
  • TLB는 일반적으로 최첨단 기계에서도 512 entries를 넘지 않는다.

 

Translation Lookaside Buffers (TLBs)

• TLB miss는 page fault인가 아니면 그저 TLB miss에 그치는가? 
  
  • 만약 page가 main memory에 로드되면 TLB miss는 page table에서 TLB로 translation 정보를 로딩함으로써 관리될 수 있다. (hardware로든 software로든)
    • Takes 10’s of cycles to find and load the translation info into the TLB
    • TLB에서 translation 정보를 찾고 로드하는데 10 cycles이 걸린다.
  • 만약 page가 main meory에 없으면, 이건 진짜 순수(true) page fault이다.(빼도 박도 못함)
    
    • page fault를 처리하기 위해 1,000,000 cycles을 소모해야 한다.
• TLB misses는 true page fault보다 훨씬 더 빈번하게 일어난다.

 

진행과정

1. CPU에서 실행을 원하는 프로그램의 Virtual address가 나온다.
2. TLB에 찾아가서 PA(Physical Address)가 있는지 확인하여 hit다? 그러면
   1. cache에 있으면 cache를 통해
   2. cache에 없으면 main memory를 통해 CPU로 전달된다.
3. 그러나 TLB miss이면 page table에 일단 가고,
   1. 가서 page table hit면 TLB에 가져다 놓고 PA로 변환되어 cache or memory를 통해 CPU로 전달된다.

Q) TLB 에서 virtual page number를 확인하는데 fully associative랑 n-way set이랑 다른가?

A)

1. Fully Associative:
   • 모든 TLB 엔트리는 어떤 VPN이든 매핑될 수 있습니다.
   • VPN이 주어지면 TLB의 모든 엔트리를 동시에 검색하여 해당 VPN이 있는지 확인합니다.
   • 이 방식은 유연성이 높지만, 복잡한 검색 회로가 필요하고 비용이 높습니다.
2. n-way Set Associative:
   • TLB는 여러 "set"으로 나뉘며, 각 set 내에는 "n"개의 엔트리가 있습니다.
   • 주어진 VPN의 일부 (index)는 해당 VPN이 위치해야 할 set을 결정합니다.
   • 해당 set 내에서만 VPN을 찾기 위해 "n"개의 엔트리를 동시에 검색합니다.
   • 이 방식은 fully associative보다 회로가 단순하고, 대부분의 경우에서 높은 성능을 제공합니다.

결론적으로, 두 방식 모두 TLB에서 VPN을 찾는 데 사용되지만, 검색 방식과 구조가 다릅니다. Fully associative는 TLB의 모든 엔트리를 검색하는 반면, n-way set associative는 특정 set 내의 엔트리만 검색합니다.