So far

OS illusion: memory virtualization
- Each process gets its own private memory
Mechanism: Address translation
Approaches
- Dynamic relocation via base+bounds (BB)
- Segmentation (aka generalized BB)

Who does what?
- Hardware: involved on every mem ref
- OS: Answer wh questions

What’s wrong with segmentation?

External fragmentation

Not flexible, e.g., large unused heap

Paging

Age-old technique, used in all(?) modern systems

Concept

divide (virtual) address space into fixed-sized units (pages)
physical memory is also split into fixed-sized units (page frames)
Segmentation: variable size (code, stack, heap)
Page table per process is needed to translate the virtual address to physical address

Advantages of Paging

Flexibile
- Don’t need an assumption on how the stack and heap grow
Simple
- Page in AS and page frame in memory are the same size
- Easy to allocate and keep a free list

Disadvantages

Time: Too slow
Size: Too much memory
More on these later

Example

(Virtual Page 0 → Physical Frame 3), (VP 1 → PF 7), (VP 2 → PF 5), and (VP 3 → PF 2)

Address translation

movl <virtual address>, %eax

Address space \(= 64\) bytes, so \(6\) bits needed

Page size \(= 16\) bytes, so first two bits give VPN

VPN \(\rightarrow\) virtual page number, Offset: offset within the page

Address translation (contd)

movl 21, %eax

Size does matter

32-bit address space, 4KB pages \(\Rightarrow\) 20-bit VPN and 12-bit offset
20-bit VPN \(\Rightarrow 2^{20}\) translations
4 bytes/page table entry (PTE) \(\Rightarrow 4MB\) of memory needed for each page table!
\(100\) processes would need 400MB of memory just for all those address translations!

Bottomline: Cannot store page tables in MMU of HW

What is in the page table?

The page table is a data structure that maps virtual addresses to physical addresses
- Simplest form: a linear page table
The OS indexes the array by VPN, and looks up the page-table entry

Common flags in a page table entry

Bit	Description
Valid bit	Indicating whether the particular translation is valid
Protection bit	Indicating whether the page could be read from, written to, or executed from
Present bit	Indicating whether this page is in physical memory or on disk
Dirty bit	Indicating whether the page has been modified since it was brought into memory
Reference bit	Indicating that a page has been accessed

Example: x86 Page Table Entry

P: present, R/W: read/write, U/S: supervisor, A: accessed bit, D: dirty bit, PFN: the page frame number

Accessing memory with paging

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// Check if process can access the page
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
else
    // Access is OK: form physical address and fetch it
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
Register = AccessMemory(PhysAddr)

Problems that can be solved

HW involved on every mem ref. HW translates, but where is the page table for the current process?
PTBR
HW must know exact structure of PT
OS
new proc: find pages for stack, heap
grow proc: add new heap page
exit proc: free pages and put them on free list
context switch: do what?

Paging problems

Too slow

To find a location of the desired PTE, the starting location of the page table is needed
For every memory reference, paging requires the OS to perform one extra memory reference

PT too big

32-bit address space, 4KB pages \(\Rightarrow\) 20-bit VPN and 12-bit offset
20-bit VPN \(\Rightarrow 2^{20}\) translations
4 bytes/page table entry (PTE) \(\Rightarrow 4MB\) of memory needed for each page table!
\(100\) processes would need 400MB of memory just for all those address translations!

Operating systems

Introduction to paging

Lecture 18