MEMORY VIRTUALIZATION: Segmentation and Paging
Andrea Arpaci-Dusseau CS 537, Fall 2019
ADMINISTRIVIA
Academic Misconduct Policy
– 0 points on P1 if have copied code from someone else
– 0 on projects P1-P8 if you repeat problem on 2 projects
– Notifying people next week; send me email before then if you have something to explain
– Project 2 Due Monday evening; Handin dirs available; tests soon
– Project 3 (Shell in Linux): Available soon; Due > 1 week after P2
– Continue to work alone; P4 will be xv6 with partner – Homeworks
– One due today, two due next Tuesday, more to come…
AGENDA / LEARNING OUTCOMES
Memory virtualization
What is segmentation?
What is paging?
Pros and cons of each?
Where are page tables stored and how are they organized?
0KB 1KB 2KB
the code segment: where instructions live
the heap segment: contains malloc’d data dynamic data structures (it grows downward)
0KB 64KB 128KB 192KB 256KB 320KB 384KB 448KB 512KB
Operating System (code, data, etc.)
(free)
Process C (code, data, etc.)
Process B (code, data, etc.)
(free)
Process A (code, data, etc.)
(free)
(free)
Program Code
Heap
(free)
Stack
15KB
16KB
(it grows upward) the stack segment: contains local variables
arguments to routines, return values, etc.
ABSTRACTION: ADDRESS SPACE
Review: MEMORY ACCESS (Logical)
Initial %rip = 0x10 %rbp = 0x200
0x10: movl 0x8(%rbp), %edi 0x13: addl $0x3, %edi 0x19: movl %edi, 0x8(%rbp)
%rbp is the base pointer:
points to base of current stack frame
%rip is instruction pointer (or program counter)
Fetch instruction at addr 0x10 Exec:
load from addr 0x208
Fetch instruction at addr 0x13 Exec:
no memory access
Fetch instruction at addr 0x19 Exec:
store to addr 0x208
5 total memory accesses
Review: HOW TO VIRTUALIZE MEMORY
Problem: How to run multiple processes simultaneously? Logical addresses are “hardcoded” into process binaries How to avoid collisions?
Possible Solutions for Mechanisms (covered previously):
1. Time Sharing
2. Static Relocation
3. Dynamic Relocation: Base Register
4. Base+Bounds
Review: 3) Dynamic Relocation
Goal: Protect processes from one another Requires hardware support
– MemoryManagementUnit(MMU)
MMU dynamically changes process address at every memory reference
– Processgenerateslogicalorvirtualaddresses(intheiraddressspace) – Memoryhardwareusesphysicalorrealaddresses
Process runs here
Logical address
OS can control MMU
MMU
Physical address
CPU
Memory
Review: Implementation with BASE REG
Translation on every memory access of user process
MMU adds base register to logical address to form physical address
MMU
registers
mode no =
user? yes
32 bits
1 bit
base
mode
+ base
logical address
physical address
Two-Minute Neighbor chat
• Why must it be hardware that adds the base register to each logical address to form physical address?
• Does the base register contain a logical or a physical address?
• One big problem with base register approach?
Review: 4) Base and Bounds Advantages
Provides protection (both read and write) across address spaces Supports dynamic relocation
Can place process at different locations initially and also move address spaces
Simple, inexpensive implementation: Few registers, little logic in MMU Fast: Add and compare in parallel
logical phy address add
error
registers
mode no =
user? yes
32 bits
32 bits
1 bit mode
yes bounds?
<
no
base
bounds
+ base
sic res
a s
Review: Base and Bounds DISADVANTAGES
Disadvantages
– Eachprocessmustbeallocatedcontiguouslyinphysicalmemory
Must allocate memory that might not be used by process
– Nopartialsharing:Cannotsharelimitedpartsofaddressspace
0
Code
Heap
Stack
2n-1
5) Segmentation
Divide logical address space into logical segments
• Each segment corresponds to logical entity in address space
(code, stack, heap)
Each segment has separate base + bounds register
Each segment can independently:
• be placed separately in physical memory
• grow and shrink
• be protected (separate read/write/execute bits)
0
Code
Heap
Stack
2n-1
Segmented Addressing
Process now specifies segment and offset within segment How does process designate a particular segment?
– Use part of logical address
• Topbitsoflogicaladdressselectsegment
• Low bits of logical address select offset within segment
What if small address space, not enough bits? – Implicitly by type of memory reference – Special registers
Segmentation Implementation
MMU contains Segment Table (per process)
• Each segment has own base and bounds, protection bits
• Example: 14 bit logical address, 4 segments;
How many bits for segment?
How many bits for offset?
remember:
1 hex digità4 bits
Segment
Base
Bounds
RW
0
0x2000
0x6ff
10
1
0x0000
0x4ff
11
2
0x3000
0xfff
11
3
0x0000
0x000
00
chat: Address Translations with Segmentation
14 bit logical address, 4 segments;
Translate logical (in hex) to physical 0x0240:
0x1108: 0x265c: 0x3002:
Segment
Base
Bounds
RW
0
0x2000
0x6ff
10
1
0x0000
0x4ff
11
2
0x3000
0xfff
11
3
0x0000
0x000
00
Top 2 bits à Segment: 0
0x2000 + 0x240 = 0x2240
Top 2 bits à Segment: 1
0x0000 + 0x108 = 0x0x108
Top 2 bits à Segment: 2
0x3000 + 0x65c = 0x2240
Remember:
1 hex digità4 bits
Top 2 bits à Segment: 3
Offset > Bounds (and no R/W)
Visual Interpretation
Virtual (hex)
load 0x2010, R1
0x00
0x400
0x800
0x1200
0x1600
0x2000
0x2400
Segment numbers: 0: code+data
1: heap 2: stack
Physical
heap (seg1)
stack (seg2)
Visual Interpretation
Virtual (hex)
load 0x2010, R1
0x00
0x400
0x800
0x1200
0x1600
0x2000
0x2400
Segment numbers: 0: code+data
1: heap 2: stack
Physical
0x1600 + 0x010 = 0x1610
heap (seg1)
stack (seg2)
Visual Interpretation
Physical
0x1600 + 0x010 = 0x1610
0x00
0x400
0x800 load 0x1010, R1
Virtual
heap (seg1)
stack (seg2)
0x1200
0x1600
0x2000
0x2400
Segment numbers: 0: code+data
1: heap 2: stack
load 0x1100, R1
load 0x2010, R1
0x400 + 0x010 = 0x410
0x400 + 0x100 = 0x500
PHYSICAL Memory Accesses
0x0010: movl 0x1100, %edi
0x0013: addl $0x3, %edi
0x0019: movl %edi, 0x1100
%rip: 0x0010
1. Fetch instruction at logical addr 0x0010
2. Exec, load from logical addr 0x1100
v
Physical addr: 0x4v013
4. Exec, no load
5. Fetch instruction at logical addr 0x0019
Physical addr:
6. Exec, store to logical addr 0x1100
Physical addr:
Physical addr: 0x40
v
10
Physical addr: 0x5900
3. Fetch instruction at logical addr 0x0013
Seg
Base
Bounds
0
0x4000
0xfff
1
0x5800
0xfff
2
0x6800
0x7ff
v
0x4019
0x5900
v
0KB 1KB 2KB
Stack goes 16K à 12K, in physical memory is 28K à 24K where instructions live
15KB
16KB
(it grows upward)
the sAtadckdsetgomenbt:ase
contains local variables arguments to routines, return values, etc.
= 28K – 1K = 27K
HOW DO STACKS GROW ?
Program Code
Heap
(free)
Stack
the code segment:
Segment base is at 28K
the heap segment: contains malloc’d data dynamic data structures (it grows downward)
Virtual address 0x3C00 = 15K
à top 2 bits (0x3) segment ref, offset is 0xC00 = 3K
How do we make CPU translate that ?
Negative offset = subtract max segment from offset = 3K – 4K = -1K
Advantages of Segmentation
Enables sparse allocation of address space Stack and heap can grow independently
• Heap: If no data on free list, dynamic memory allocator requests more from OS
(e.g., UNIX: malloc library makes sbrk() system call)
• Stack: OS recognizes reference near outside legal segment, extends stack implicitly
Different protection for different segments
• Enables sharing of selected segments
• Read-only status for code
Supports dynamic relocation of each segment
0
Code
Heap
Stack
2n-1
Disadvantages of Segmentation
Each segment must be allocated contiguously
May not have sufficient physical memory for large segments? External Fragmentation
FRAGMENTATION
1-Minute chat: Match Description
Description
1. one process uses RAM at a time
2. rewrite code and addresses before running
3. add per-process starting location to virt addr to obtain phys addr
4. dynamic approach that verifies address is in valid range
5. several base+bound pairs per process
Name of approach
Candidates: Segmentation, Static Relocation, Base, Base+Bounds,Time Sharing
pAGING
FRAGMENTATION
Definition: Free memory that can’t be usefully allocated
Types of fragmentation
External: Visible to allocator (e. g. , OS) Internal: Visible to requester
Internal
useful
free
Paging
Goal: Eliminate requirement that address space is contiguous Eliminate external fragmentation
Grow segments as needed
Idea:
Divide address spaces and physical memory into fixed-sized pages
Size: 2n, Example: 4KB
Process 1
Process 3 Logical View
Process 2
Physical View
Translation of Page Addresses
How to translate logical address to physical address? – High-order bits of address designate page number
– Low-order bits of address designate offset within page
20 bits 12 bits
32 bits Logical address
Physical address
page number
page offset
translate
frame number
page offset
No addition needed (unlike segmentation); just append bits correctly…
Address Format
Given known page size, how many bits are needed in address to specify offset in page?
Given number of bits in virtual address and bits for offset, how many bits for virtual page numb
Given number of bits for vpn, how many virtual pages can there be in an address space?
Page Size
16 bytes 1 KB
1 MB 512 bytes
4 KB
Low Bits (offset)
Virt Addr Bits
High Bits (vpn)
# of Virt Pages
128 1M
6
10
12
7
20
10 20 32 16 32
64
4
10
20
9
12
1K
4K
er?
VirtUALàPhysical PAGE Mapping
Number of bits in virtual address
need not equal
number of bits in physical address
How should OS translate VPN to PPN?
VPN offset
Addr Mapper
PPN offset
0
1
0
1
0
1
1
0
1
1
0
1
0
1
For paging, OS needs general mapping mechanism What data structure is good?
Linear PAGETABLES
What is a good data structure ?
Simple solution: Linear page table aka array
VPN 0
2^n
Virt Mem Phys Mem
PER-PROCESS PAGETABLE
P1 P2 P3
Virt Mem Phys Mem
FILL IN PAGETABLE
P1 P2 P3
Page Tables:
P1 3 1
7 10
P20 P38 45
29 6 11
0 1 2 3 4 5 6 7 8 9 10 11
Neighbor chat: HOW BIG IS A PAGETABLE?
How big is a typical page table?
– assume 32-bit address space
– assume 4 KB pages
– assume 4 byte entries
Key: Figure out how many PTEs (Page table entries)
Where Are Pagetables Stored?
HOW BIG IS A PAGETABLE?
How big is a typical page table?
– assume 32-bit address space
– assume 4 KB pages
– assume 4 byte page table entries (PTEs)
Final answer: 2 ^ (32 – log(4KB)) * 4 = 4 MB
– Pagetablesize=Numentries*sizeofeachentry
– Numentries=numvirtualpages=2^(bitsforvpn) – Bitsforvpn=32–numberofbitsforpageoffset
= 32 – lg(4KB) = 32 – 12 = 20
– Numentries=2^20=1MB
– Pagetablesize=Numentries*4bytes=4MB
WHERE ARE PAGETABLES STORED?
Implication: Store each page table in memory
Hardware finds page table base with register (e.g., CR3 on x86)
What happens on a context-switch?
Change contents of page table base register to newly scheduled process Save old page table base register in PCB of descheduled process
Other Pagetable info
What other info is in pagetable entries besides translation? – valid bit
– protection bits
– present bit (needed later) – reference bit (needed later) – dirty bit (needed later)
Pagetable entries are just bits stored in memory
– AgreementbetweenhwandOSaboutinterpretation
Memory Accesses with Paging
Fetch instruction at logical
• Access page table to get
• Mem ref 1
• Learn
• Fetch instruction at
Exec, load from logical
0x0010
addr
0x0010: movl 0x1100, %edi
Assume PT is at phys addr 0x5000 Assume PTE’s are 4 bytes
Assume 4KB pages
How many bits for offset? 12
2 Simplified view 0
of page table 80 99
: 0x5000
0 2
ppn
for
vpn
vpn
0 is at
ppn
0x2010
(Mem
ref 2)
0x1100 ppn
: 0x5004
• • •
addr Access page table to get
1 0
0x0100
for
vpn
Mem ref 3
vpn from
1 is at
ppn
Pagetables are slow! Double memory references •
Learn Movl
into
reg
(Mem ref 4)
Advantages of Paging
No external fragmentation
– Any page can be placed in any frame in physical memory
Fast to allocate and free
– Alloc: No searching for suitable free space
– Free:Doesn’thavetocoalescewithadjacentfreespace
Simple to swap-out portions of memory to disk (later lecture)
– Pagesizematchesdiskblocksize
– Canrunprocesswhensomepagesareondisk
– Add “present” bit to P TE
Disadvantages of Paging
Internal fragmentation: Page size may not match size needed by process
– Wasted memory grows with larger pages
– Tension? Why not make pages very small?
Additional memory reference to page tableàVery inefficient – Pagetablemustbestoredinmemory
– MMUstoresonlybaseaddressofpagetable
– Solution:AddTLBs(futurelecture)
Storage for page tables may be substantial
– Linearpagetable:RequiresPTEforallpagesinaddressspace – Entryneededevenifpagenotallocated
– Pagetablesmustbeallocatedcontiguouslyinmemory
– Fixwithsegmentationandpagingpagetables(next)
Code
Heap
Stack