19. Virtual Memory

생성일: 2021년 12월 17일 오후 6:53

Abstraction: Virtual vs. Physical Memory

• Programmer sees virtual memory (무한하다고 착각)
• 현실에서 Physical memory size는 훨씬 작다.
• The system(software + hardware) maps virtual memory addresses to physical memory
• 장점
  • 프로그래머는 메모리의 물리적 크기를 관리 할 필요 X ⇒ 프로그래머의 삶의 질 향상
• 단점
  • 더 복잡한 시스템 스프트웨어와 아키텍쳐
• Auotomatic Management of memory
  • Enables
    • Code and data to be located anywhere in physical memory (relocation)
    • Isolation/separation of code and data of different processes in physical memory (protection and isolation)
    • Code and data sharing between multiple processes (sharing)
  • Problem
    • Physical memory is of limited size (cost)
    • Multiple programs may need the physical memory

Virtual Memory (VM)

• Idea: Give each program the illusion of a large address space while having a small physical memory
• Basic Mechanism
  • Indirection (in addressing) (간접 참조)
  • Address generated by each instruction in a program is a “virtual address”
  • An “address translation” mechanism maps this address to a “physical address”
• Motivation (장점)
  • Virtual memory (VM): A technique using main memory as a “cache” for secondary storage (disk)
  • Virtual memory enables efficient and safe sharing of memory among multiple programs.
  • VM protects the programs from each other
  • The programs sharing the memory change dynamically while the programs are running. The compiler sets each program into its own address space
  • VM translates the program’s address space to physical addresses, enforcing protection of a program’s address space from other programs

A system with Vitual Memory (Page-based)

Page-based Virtual-to-Physical Mapping

Virtual Pages, Physical Frames

• Vitual address space diveded into pages

• Physical address space divided into frames (or we can also call pages)

• A virtual page is mapped to

  • Physical frame, if the page is in physical memory
  • A location in disk, otherwise

• If an accessed virtual page is not in memory, but on disk

  • Virtual memory system brings the page into a physical frame and adjusts the mapping
    → this is called demand paging

• Page table is the table that stores the mapping of virtual pages to physical frames

Physical Memory as a Cache

• Physical memory is a cache for pages stored on disk
• Similar caching issues exist as we have covered earlier
  • Placement, Replacement, Granularity of management, Write policy

Cache/Virtual Memory Analogues

Virtual Memory Definitions

• Page size: the mapping granularity of virtual ⇒ physical address spaces
  • 한 번에 하드 디스크에서 DRAM으로 전송되는 데이터의 양
• Page table: table that stores virtual ⇒ physical page mappings
  • 위치를 찾는 데 사용되는 조회 테이블
• Address translation: the process of determining the physical address from the virtual address

Virtual to Physical Mapping

Address Translation

Virtual Memory Example

How Do We Translate Address?

• Page table
  • Has entry for each virtual page
• Each page table entry has:
  • Valid bit: 가상 페이지가 실제 메모리에 있는지 여부 (그렇지 않은 경우, 하드 디스크에서 가져와야 함)
  • Physical page number: 가상 페이지가 물리적 메모리에 있는 위치
• Page Table for Example
  

Page Table Address Translation Example

Issue: Page Table Size

Page Table Challenges 1

• Callenge 1: Page table is large
  • at least part of it needs to be located in physical memory
  • solution: multi-level (hierarchical) page tables

Multi-Level(hierarchical) Page Tables

• Idea: Organize page table in a hierarchical manner such that only a small first-level page table has to be in physical memory

Page Table Challenges 2

• Challenge 2: Each instruction fetch or load/store requires at least two memory accesses
  1. one for address translation (page table read)
  2. one to access data with the physical address (after translation)
• instruction fetch 또는 load/store 을 위한 두 개의 메모리 액새스는 실행 시간을 크게 저하시킴

Translation Lookaside Buffer (TLB)

• Idea: Cache the page table entries (PTEs) in a hardware structure in the processor to speed up address translation
• Translation lookaside buffer (TLB)
  • Small cache of most recently used translations (PTEs)
  • Reduces number of memory accesses required for most instruction fetches and loads/stores to only one
• Page table accesses have a lot of temporal and spatial locality
  • 연속 명령어 및 로드/저장은 동일한 페이지에 액세스할 가능성 높다

Example Two-Entry TLB

TLB is a Translation (PTE) Cache

• chaching과 prefetching의 문제점들은 모두 TLB에서도 적용된다.
• 예를 들어,
  • Instruction vs. Data TLBs
  • Associativity and size choices and tradeoffs
  • Multi-level TLBs 등

• Page table 대신 모든 참조에서 TLB에 액세스 함 ⇒ TLB는 Valid, Dirty, Reference bit를 포함해야 함

Supporting Virtual Memory

• Virtual memory requires both HW+SW support
• The hardware component is called MMU(memory management unit)

What Is in a Page Table Entry (PTE)?

• Page table is the “tag store” for the physical memory data store
  • Need a valid bit → to indicate validity/presence in physical memory
  • Need tag bits (physical frame number) → to support translation
  • Need bits to support replacement
  • Need a dirty bit to support “write back caching”
  • Need protection bits to enable access control and protection

Address Translation: Page Hit

Address Translation: Page Fault