[OS] Memory Management 2

Memory Management Part 2

Paging

• Permit the physical address space of a process to be non-contiguous
• Divide physical memory into fixed-sized blocks called page frames or frames
• Divide logical address space into the same sized blocks called pages
  • Usually, pages(or frames) size is a power of 2 (typically 512B ~ 8KB)
  • Some systems allow huge pages
• To run a program of size n, find n free frames and load the program
• Set up a page table to translate logical to physical addresses
• OS keeps track of all free frames

• Still, some internal fragmentation exists
  • page size = 4KB
  • process size = 72,766 bytes
  • 72,766 bytes / 4KB = 17 pages + 3,134 bytes
  • Internal fragmentation : 4,096(page size) - 3,134 = 962
• If small frame sizes
  • need more mapping entries in the page table

Page Tables

• Each process has its own page table (page table : process level)
  • Page-table base register (PTBR) points to the base address of the page table
• Managed by OS, accessed by MMU
• One page table entry (PTE) per page in virtual address space
• Map Virtual Page Number (VPN) to Page Frame Number (PFN)
  • VPN : An index into the page table
  • Virtual address = <Virtual Page Number(VPN), Offset>
  • Physical address = <Page Frame Number(PFN), Offset>

Address Translation

• Address generated by CPU is divided into Page number(p) and Page offset(d)
• Page number : used as an index into a page table which contains base address of each page in physical memory
• Page offset : combined with base address to define the physical memory address that is sent to the memory unit

• Suppose page size = 4KB, memory size = 256KB
• Number of page frames?
  • Page size = 4KB = 2^12 Bytes, memory size = 256KB = 2^18 Bytes
  • Number of page frames = 2^18 / 2^12 = 64
• How many bits needed for memory address?
  • 18 bits
• How many bits needed for page number and page offset?
  • 6 bits for page number(000000 ~ 111111)
  • 12 bits for page offset

Page Table Entry (PTE)

– V (Valid) bit says whether or not the PTE can be used

• It is checked each time a virtual address is used – R (Reference) bit says whether the page has been accessed
• It is set when a read or write to the page occurs – M (Modify) bit says whether the page is dirty
• It is set when a write to the page occurs – Prot (Protection) bits control which operations are allowed
• Read, Write, Execute, etc. – PFN (Page Frame Number) determines the physical frame

Protection

• Separate page table for each process
  • On context switch, PTBR is set to the corresponding process’s one
  • No way to access the physical memory of other processes
• Page-level protection – Memory protection is implemented by associating protection bits with each PTE – Valid / invalid bit
  • Valid: the page is in the process’ address space and in use
  • Invalid: the page is not allocated – Finer level of protection is possible for valid pages
  • Read-only, read-write, or execute-only protections

Page Table Structure

• High space overhead for page tables – A 32-bit address space with 4KB pages, 4 bytes/PTE:
  • 2^20 x 4 = 4 MB per process – A 64-bit address space with 8KB pages, 8 bytes/PTE:
  • 2^51 x 8 = 254 = 16 PB per process!
• Page tables are too big to fit in a single page – 4 byte/PTE à 1024 PTEs/4 KB page à 4 MB address space

Page Table Solution

• Split the entire page table into smaller page table pieces
• Only map the used portion – Deploy additional indirection levels to locate the page table pieces

Hierarchical Page Tables

Pros – Compact while supporting sparse-address space

• Page-table space in proportion to the amount of address space used – Easier to manage physical memory
• Each page table usually fits within a page – Easier for hardware to walk though page tables – No external fragmentation Cons – More complex than a simple linear page-table lookup

Hashed Page Table

• Virtual Page Number is hashed into a page table
• The page table contains a chain of VPN that falls into the same hash bucket

Inverted Page Tables

• Reverse mapping from PFN à <VPN, PID> – One entry for each page frame in physical memory – Entry consists of the virtual page number with information about the process that owns that page – Need to search through the table to find match – Use hashing to limit the search to one, or at most a few, page-table entries
• Pros & Cons – Decrease memory needed to store page tables: No need to have per-process page tables – Increase time needed to search the table on a TLB miss

Translation Look-aside Buffer (TLB)

• Address translation through page tables takes long
• On a 3-level page table, an address lookup requires 3 memory accesses, one access for each level
• Hardware support to accelerate the address translation
• A cache with 32-1024 entries (TLB entries: <page #, frame #>)

• On a TLB miss, MMU walks through the page table, and store the translation result in TLB
• On a TLB hit, MMU can convert VA to PA without walking through the page table
• On a context switch, TLB should be flushed – Each process has its own VA to PA mapping – Thus, cannot share TLB entries between processes
• Some TLBs with address-space Identifiers (ASIDs) allows to coexist TLB entries from different processes