Virtual memory

Doo Seok Jeong @Emerging Computing Lab 1

 Bare five-stage pipeline
Source: Computer Organization and Design

• What if we don’t have

enough memory(< 4GB)?
Physical address
• How do we allocate memory
Physical address
among multiple processes?

I-cache • How do we isolate

D-cache processes from each other
(and/or share data)?
Physical
address

Physical address Memory

DRAM
controller Physical
address

Doo Seok Jeong @Emerging Computing Lab 2

 Problem 1: memory size

MIPS has a 32-bit address space: 232 = 4GB

• Each program can access any of these 232 bytes.
• What if we don’t have 4GB of memory?
• What if we want to run multiple programs simultaneously?

Program address space Physical RAM (1GB)

Program crashes!

Doo Seok Jeong @Emerging Computing Lab 3

 Problem 2: process isolation

Memory map
Stack
• Each program has a 232 byte address space.
• Different parts of the address space are reserved for different usages
(e.g., program code, stack, static/global variables, etc)

What if we want to run multiple programs simultaneously?

• Each process runs a program that is built according to the memory
map (built by a compiler).
• Data from different processes may be mapped to the same
addresses. Heap
• Processes will overwrite data at the same addresses.
• How can we protect data from one process being read or written by Static/global
another process?
Code (text)

Doo Seok Jeong @Emerging Computing Lab 4

 Naive solution: base and bound (segmentation)

CPU mem
To address the size problem, we can limit the address space access
during compilation such that we allocate fewer than 232 bytes to
each program. Logical
address
When loading a program,
+ Base address
• We define base and bound addresses,
where the program’s address space will start and end. Physical Base address
• We will load these into a base register and bound register. address
• When accessing memory, the base register will be added to >
the logical address to create the physical address.
• Physical address will be compared to the bound address.
If physical addr > base address, segmentation fault! Physical
memory Segmentation
fault

Doo Seok Jeong @Emerging Computing Lab 5

 Segmentation

• The operating system (OS) allocates memory and sets the base and bound
addresses.
• Only the OS can update base and bound registers by running in a privileged
mode.

Problems
• The address space of each process should be predefined and limited. DRAM (4GB)
• Processes cannot share data.
• Segmentation results in fragmentation.

Some architectures still use segmentation these days.

• For instance, x86 supports segmentation, but rarely used

Doo Seok Jeong @Emerging Computing Lab 6

 Solution: virtual addressing

Virtual addressing is an indirection that indeed solves many problems.

• All programs own a virtual address (VA) space of 232 bytes.
• The OS maps every VA to a physical address (PA).
• The memory management unit (MMU) translates the Vas to PAs.

wo/ virtual memory, program addr = physical addr wo virtual memory, program addr maps to RAM addr
32b program addr space <4GB DRAM 32b program addr space MMU <4GB DRAM

Program
crashes!

Doo Seok Jeong @Emerging Computing Lab 7

 How does virtual addressing work?

Divide the memory into pages 20b 12b

• A page is a unit of reference in the physical memory. Page number Offset
• Typical page size is 4kB (12 bits)
0x00000000 4kB
Processor accesses the memory with a virtual address. 0x00001000 4kB
Page number Offset MMU 0x00002000 4kB
20b 12b 0x00003000 4kB
• VA is divided into a page number (identifier of a virtual page) 0x00004000 4kB
and an offset (address within the identified virtual page) 0x00005000 4kB

MMU translates the virtual address into a physical address. DRAM

• The page number is replaced by the base address, which is stored in the
memory
• The offset chooses the specific byte in the physical page.

Mapping between virtual and physical pages is called a page table.

Doo Seok Jeong @Emerging Computing Lab 8

 Page tables
For Process 2: Page tables
A page table entry (PTE) is a mapping between lb $t0, 0x00002001 Process 1: VPN 0 PPN 2
• Virtual page number (VPN) and Physical page number
PTBR Process 1: VPN 1 PPN 6
(PPN)
Process 1: VPN 2 PPN 1
+
Each process receives its own page table Process 1: VPN 3 PPN 5
• Page tables are stored in DRAM. PTE <-
VPN+PTBR
• Base address of the current page table is stored in the Process 2: VPN 0 PPN 0
page table base register (PTBR). Process 2: VPN 1 PPN 7
Process 2: VPN 2 PPN 3
When accessing memory (e.g., lb $t0, VPN+offset), Process 2: VPN 3 PPN 4
• First DRAM access: PTE <- VPN(PTBR)
• Second DRAM access: t0 <- offset(PTE) t0 <- 0x00003 +
DRAM
0x001 0x00000000 4kB
Two DRAM access required for every load/store 0x00001000 4kB
instruction. 0x00002000 4kB
0x00003000 4kB
0x00004000 4kB
0x00005000 4kB
Doo Seok Jeong @Emerging Computing Lab 9
 Demand paging

When we don’t have enough RAM?

• For instance, a 1GB DRAM on a MIPS machine. Page table DRAM
• Or running 100 processes on such a machine VPN 0 PPN 2 1 0x00000000 4kB
VPN 1 DPN 130 0 0x00001000 4kB
We use a DRAM as a cache VPN 2 PPN 1 1 0x00002000 4kB
• Store all data on a disk. VPN 3 PPN 5 1
0x00003000 4kB
• Bring only accessed pages to the DRAM, which is called
demand paging. 0x00004000 4kB
0x00005000 4kB
Add a valid bit to the PTE
• If valid=0, the page is not the disk
• Then, a page fault occurs, which brings the page (DPN
130) to the DRAM.
• If the DRAM is full, evict a page, swapping it out to the
disk.

Accessing a disk takes millions of cycles: use software

(OS)

Doo Seok Jeong @Emerging Computing Lab 10

 Handling page faults

Page fault valid=0

exception

If page fault, Page fault

System call
• Hardware exception: like an interrupt. handler
• Page fault handler is called; OS is invoked. Write to disk
• If DRAM is full, the OS chooses a page to evict.
• Swap page: write back an old page, read a new page Swap
from the disk.
• Update the page table Read from
• Jump back to return instruction that caused the page disk
fault Update
Evict page -> DPN
page table
New page -> PPN

Return

Doo Seok Jeong @Emerging Computing Lab 11

 Does virtual memory solve the problems?

20b 12b

Problem 1: not enough memory Page number (VPN) Offset

Example 1: MIPS machine with a 1GB DRAM Page table

• Use smaller PPNs than VPNs. 0x00000 18b PPN
• Assuming 4KB pages, VPNs are 20b while PPNs 18b.
0x00001 18b PPN
0x00002 18b PPN
Example 2: 100 processes running on the same machine
• Each process can use 10MB memory (2,500 pages). 0x00003 18b PPN

What if memory is not large enough? DRAM

• Use a disk 4kB
4kB
4kB
4kB
4kB
4kB

Doo Seok Jeong @Emerging Computing Lab 12

 Does virtual memory solve the problems?

Problem 2: program isolation

Example 1: Location independence Page tables

• Compile a program assuming it had the entire 232 byte address
Process 1: VPN 0 PPN 2
space.
• Each process has a separate page table, mapping the same Process 1: VPN 1 PPN 6

addresses to different physical locations. Process 1: VPN 2 PPN 1

Process 1: VPN 3 PPN 5
Example 2: Protection
• Page table mapping ensures one process doesn’t access the data Process 2: VPN 0 PPN 0
for the other processes. Process 2: VPN 1 PPN 7
Process 2: VPN 2 PPN 3
Example 3: Data sharing
Process 2: VPN 3 PPN 4
• Mat VPNs of several processes to the same PPNs to enable data
sharing.
• Add read (R), write (W), execute (x) bits to PPNs for access
restriction.

Doo Seok Jeong @Emerging Computing Lab 13

 Does virtual memory solve the problems?

Problem 3: Fragmentation

Example 1: Multiple processes running

• Each process gets allocated 4KB pages upon access.
• The OS keeps account of free pages.
• Once a process exits, its allocated memory is freed.

Process 1: VPN 0 PPN 2 4kB

Process 1: VPN 1 PPN 6 4kB
Process 1: VPN 2 PPN 1 4kB
Process 1: VPN 3 PPN 5
4kB
4kB
Process 2: VPN 0 PPN 0
4kB
Process 2: VPN 1 PPN 7
Process 2: VPN 2 PPN 3
4kB
Process 2: VPN 3 PPN 4 4kB

Doo Seok Jeong @Emerging Computing Lab 14