Digital Design and Computer Architecture - Lecture 23b: Virtual Memory

This post is a derivative of Digital Design and Computer Architecture Lecture by Prof. Onur Mutlu, used under CC BY-NC-SA 4.0.

You can watch this lecture on Youtube and see pdf.

I write this summary for personal learning purposes.

Readings

• Virtual Memory
• Required
  • H&H Chapter 8.4

Ideal Memory

• Zero access time (latency)
• Infinite capacity
• Zero cost
• Infinite bandwidth (to support multiple accesses in parallel)

Abstraction: Virtual vs. Physical Memory

• Programmer sees virtual memory
  • Can assume the memory is “infinite”
  • If you have a limited size memory, you can provide the illusion to the programmer that there’s actually a lot of memory so that the programmer doesn’t need to manage memory
• Reality: Physical memory size is much smaller than what the programmer assumes
• The system (system software + hardware, cooperatively) maps virtual memory addresses to physical memory
  • Virtual memory address is some name for the data that the programmer is trying to access and internally that name gets mapped to a particular location that could be in the main memory or the disk.
  • The system automatically manages the physical memory space transparently to the programmer
• + Programmer does not need to know the physical size of memory nor manage it -> A small physical memory can appear as a huge one to the programmer -> Life is easier for the programmer
• – More complex system software and architecture

A classic example of the programmer/(micro)architect tradeoff

Benefits of Automatic Management of Memory

• Programmer does not deal with physical addresses

• Each process has its own mapping from virtual -> physical addresses

• Enables
  • Code and data to be located anywhere in physical memory (relocation)
    • If some part of physical memory is not available, you can put the program in to other part of physical memory -> that’s called relocation and this is essential for system management
  • Isolation/separation of code and data of different processes in physical memory (protection and isolation)
    • Let’s assumethat programmer X write a program and programmer Y writes a program. They both use addresses from 0 to maybe 5000. If these were physical addresses you have a problem. But what the system does is it basically translate those addresses.
  • Code and data sharing between multiple processes (sharing)
    • If the processes actually need to share the data, different programs can be mapped to the same physical location.

A System with Physical Memory Only

CPU’s load or store addresses used directly to access memory

• Examples:
  • most Cray machines
  • early PCs
  • Many embedded systems

The Problem

• Physical memory is of limited size (cost)
  • What if you need more?
  • Should the programmer be concerned about the size of code/data blocks fitting physical memory?
  • Should the programmer manage data movement from disk to physical memory?
  • Should the programmer ensure two processes (different programs) do not use the same physical memory?
• Also, ISA can have an address space greater than the physical memory size
  • E.g., a 64-bit address space with byte addressability
  • What if you do not have enough physical memory?

Difficulties of Direct Physical Addressing

• Programmer needs to manage physical memory space
  • Inconvenient & hard
  • Harder when you have multiple processes
• Difficult to support code and data relocation
  • Addresses are directly specified in the program
• Difficult to support multiple processes
  • Protection and isolation between multiple processes
  • Sharing of physical memory space
• Difficult to support data/code sharing across processes

Virtual Memory

• Idea: Give the programmer the illusion of a large address space while having a small physical memory
  • So that the programmer does not worry about managing physical memory
• Programmer can assume he/she has “infinite” amount of physical memory
• Hardware and software cooperatively and automatically manage the physical memory space to provide the illusion
  • Illusion is maintained for each independent process

Basic Mechanism

• Indirection (in addressing)
• Address generated by each instruction in a program is a “virtual address”
  • i.e., it is not the physical address used to address main memory
  • called “linear address” in x86
• An “address translation” mechanism maps this address to a “physical address”
  • called “real address” in x86
  • Address translation mechanism can be implemented in hardware and software together. In today’s systems, it’s implemented cooperatively between the hardware and software.

A System with Virtual Memory (Page based)

As opposed to CPU directly accessing, generating physical addresses. Add another structure called a page table. Each process has its own page table and the purpose of the structure is to the address translation from a virtual address to physical address. So the programmers uses virtual addresses. They can do whatever they want with the addresses and the system maps those virtual addresses to physical locations.

• Address Translation: The hardware converts virtual addresses into physical addresses via an OS-managed lookup table (page table)
• This also enables access protection

Virtual Pages, Physical Frames

• Virtual address space divided into pages
• Physical address space divided into frames
• A virtual page is mapped to
  • A 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

• In other words, we’re using physical memory as a cache to the disk. Everything starts out it’s in the disk and we slowly start bringing data into the physical memory and mapping data into the physical memory.
• Physical memory is a cache for pages stored on disk
  • In fact, it is a fully associative cache in modern systems (a virtual page can potentially be mapped to any physical frame)
• Similar caching issues exist as we have covered earlier:
  • Placement: where and how to place/find a page in cache?
  • Replacement: what page to remove to make room in cache?
  • Granularity of management: large, small, uniform pages?
  • Write policy: what do we do about writes? Write back?

Cache/Virtual Memory Analogues

Cache	Virtual Memory
Block	Page
Block Size	Page Size
Block Offset	Page Offset
Miss	Page Fault
Tag	Virtual Page Number

Page Fault - This means that the page that you’re looking for is not in physical memory, it’s in the disk. So somebody needs to bring the page from the disk into the physical memory and that is done by the operating system today with some hardware support.

Virtual Memory Definitions

• Page size: amount of memory transferred from hard disk to DRAM at once
• Address translation: determining the physical address from the virtual address
• Page table: lookup table used to translate virtual addresses to physical addresses (and find where the associated data is)

Virtual and Physical Addresses

• Most accesses hit in physical memory (Hope)
• But programs see the large capacity of virtual memory

Address Translation

Virtual Memory Example

• System:
  • Virtual memory size: 2 GB = 2^31 bytes
  • Physical memory size: 128 MB = 2^27 bytes
  • Page size: 4 KB = 2^12 bytes (given by ISA)
• Organization:
  • Virtual address: 31 bits
  • Physical address: 27 bits
  • Page offset: 12 bits
  • # Virtual pages = 2^31/2^12 = 2^19 (VPN = 19 bits)
  • # Physical pages = 2^27/2^12 = 2^15 (PPN = 15 bits)