Virtualizing Memory: Paging
Virtualizing Memory:
Paging
Questions answered in this lecture:
Review segmentation and fragmentation
What is paging?
Where are page tables stored?
What are advantages and disadvantages of paging?
CSE 2431
Introduction to Operating Systems
Based on slides by Andrea C. Arpaci-Dusseau
Remzi H. Arpaci-Dusseau
Reading
Chapter 18: Introduction to Paging
Review:
Match Description
Name of approach
(covered previous lecture):
Segmentation
Static Relocation
Base
Base+Bounds
Time Sharing
Description
one process uses RAM at a time
rewrite code and addresses before running
add per-process starting location to virt addr to obtain phys addr
dynamic approach that verifies address is in valid range
several base+bound pairs per process
Review: Segmentation
Assume 14-bit virtual addresses, high 2 bits indicate segment
Segments:
0=>code
1=>heap
2=>stack.
0x0000
0x1000
0x2000
0x3000
0x4000
0x4000
0x5000
0x6000
0x7000
0x8000
Virt Mem
Phys Mem
?
?
?
Code
Heap
Stack
Seg Base Bounds
0
1
2
0xfff
0xfff
0x7ff
0x4000
0x5800
0x6800
Where doe segment table live?
All registers, MMU
Review:
Memory Accesses
0x0010: movl 0x1100, %edi
0x0013: addl $0x3, %edi
0x0019: movl %edi, 0x1100
Physical Memory Accesses?
1) Fetch instruction at logical addr 0x0010
Physical addr:
Exec, load from logical addr 0x1100
Physical addr:
2) Fetch instruction at logical addr 0x0013
Physical addr:
Exec, no load
3) Fetch instruction at logical addr 0x0019
Physical addr:
Exec, store to logical addr 0x1100
Physical addr:
Seg Base Bounds
0 0x4000 0xfff
1 0x5800 0xfff
2 0x6800 0x7ff
0x4010
0x5900
0x4013
0x4019
0x5900
%rip: 0x0010
Total of 5 memory references (3 instruction fetches, 2 movl)
Problem: Fragmentation
Definition: Free memory that can’t be usefully allocated
Why?
Free memory (hole) too small or scattered
Rules for allocating memory prohibit using this free space
Types of fragmentation
External: Visible to allocator (OS)
Internal: Visible to requester (process; e.g., if must allocate at some granularity)
Segment A
Segment C
Segment D
Segment B
Segment E
No contiguous space; no hole big enough!
useful
free
Allocated to requester
Internal
External
Paging
Goal: Eliminate requirement that address space is contiguous
Eliminate external fragmentation (but not necessarily internal)
Grow segments as needed
Idea: Divide address spaces and physical memory into fixed-sized pages
Size: 2n, Example: 4KB
Physical page: page frame
Process 1
Process 2
Logical View
Physical View
Process 3
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
page number
frame number
page offset
page offset
Logical address
Physical address
32 bits
translate
20 bits
12 bits
No addition needed; just append/concatenate bits correctly…
How does format of address space determine number of pages and size of pages?
Quiz: Address Format
Page Size
Low Bits (offset)
16 bytes
4
1 KB
10
1 MB
20
512 bytes
9
4 KB
12
Given known page size, how many bits are needed in address to specify offset in page?
Quiz: Address Format
Page Size
Low Bits
(offset)
Virt Addr Bits
High Bits
(vpn)
16 bytes
4
10
6
1 KB
10
20
10
1 MB
20
32
12
512 bytes
9
16
5
4 KB
12
32
20
Given number of bits in virtual address and bits for offset,
how many bits for virtual page number?
Correct?
7
Quiz: Address Format
Page Size
Low Bits
(offset)
Virt Addr Bits
High Bits
(vpn)
16 bytes
4
10
6
Virt Pages
1 KB
10
20
10
1 MB
20
32
12
512 bytes
9
16
7
4 KB
12
32
20
Given number of bits for vpn, how many virtual pages can there be in an address space?
64
1 K
4 K
128
1 MB
VirtUAL => Physical PAGE Mapping
How should OS translate VPN to PPN?
For segmentation, OS used a formula (e.g., phys addr = virt_offset + base_reg)
For paging, OS needs more general mapping mechanism
What data structure is good?
0
1
0
1
0
1
VPN
offset
1
1
0
1
0
1
1
0
PPN
offset
Addr Mapper
Big array: pagetable
Number of bits in
virtual address format does not need to equal
number of bits in physical address format
The Mapping
Virt Mem
Phys Mem
P2
P3
P1
Virt Mem
Phys Mem
P2
P3
0
1
2
3
4
5
6
7
8
9
10
11
P1
Page Tables:
P1
3
1
7
10
P2
0
4
2
6
P3
Quiz:
Fill in Page Table
8
5
9
11
Where Are Pagetables Stored?
How big is a typical page table?
– assume 32-bit address space
– assume 4 KB pages
– assume 4 byte entries
Final answer: 2 ^ (32 – log(4KB)) * 4 = 4 MB
Page table size = Num entries * size of each entry
Num entries = num virtual pages = 2^(bits for vpn)
Bits for vpn = 32– number of bits for page offset
= 32 – lg(4KB) = 32 – 12 = 20
Num entries = 2^20 = 1 MB
Page table size = Num entries * 4 bytes = 4 MB
Implication: Store each page table in memory
Hardware finds page table base with register (Page Table Base Register; PTBR)
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 PT info
What other info is in pagetable entries besides translation (some of this info covered in more detail later)?
valid bit (whether page is valid or not)
protection bits (how page can be accessed by process)
present bit (needed later)
reference bit (needed later)
dirty bit (needed later)
Pagetable entries are just bits stored in memory
Agreement between hw and OS about interpretation
Memory Accesses
with Pages
0x0010: movl 0x1100, %edi
0x0013: addl $0x3, %edi
0x0019: movl %edi, 0x1100
Assume PT is at phys addr 0x5000
Assume PTE’s are 4 bytes
Assume 4KB pages
How many bits for offset?
Simplified view
of page table
2
0
80
99
Pagetable slows access!!! Doubles memory references
Physical Memory Accesses with Paging?
1) Fetch instruction at logical addr 0x0010; vpn?
Access page table to get ppn for vpn 0
Mem ref 1: 0x5000
Learn vpn 0 is at ppn 2
Fetch instruction at 0x2010 (Mem ref 2)
Exec, load from logical addr 0x1100; vpn?
Access page table to get ppn for vpn 1
Mem ref 3: 0x5004
Learn vpn 1 is at ppn 0
Movl from 0x0100 into reg (Mem ref 4)
12
Old: How many mem refs with segmentation?
5 (3 instrs, 2 movl)
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’t have to coallesce with adjacent free space
Just use bitmap to show free/allocated page frames
Simple to swap-out portions of memory to disk (later lecture)
Page size matches disk block size
Can run process when some pages are on disk
Add “present” bit to PTE (Page Table Entry)
Disadvantages of Paging
Internal fragmentation: Page size may not match size needed by process
Wasted memory grows with larger pages
Tension?
Additional memory reference to page table –> Very inefficient
Page table must be stored in memory
MMU stores only base address of page table in PTBR
Solution: Add TLBs (cache for PTEs (future lecture))
Storage for page tables may be substantial
Simple page table: Requires PTE for all pages in address space
Entry needed even if page not allocated
Problematic with dynamic stack and heap within address space
Page tables must be allocated contiguously in memory
Solution: Combine paging and segmentation (future lecture)
Stack
Code
Heap
/docProps/thumbnail.jpeg