6 3ULQFLSOHV RI 2SHUDWLQJ 6 VWHPV DOO Lecture 8 Memory Management Geoffrey M Voelker 0HPRU 0DQDJHPHQW Next few lectures are going to cover memory management Goals of memory management Mechanisms To provide a convenient abstraction for programming To allocate scarce memory resources among competing processes to maximize performance with minimal overhead Physical and virtual addressing 1 Techniques Partitioning paging segmentation 1 Page table management TLBs VM tricks 2 Policies Page replacement algorithms 3 October 19 2001 CSE 120 Lecture 8 Memory Management 2 1 HFWXUH 2YHUYLHZ Virtual memory warm and fuzzy Survey techniques for implementing virtual memory Fixed and variable partitioning Paging Segmentation Focus on hardware support and lookup procedure Next lecture we ll go into sharing protection efficient implementations and other VM tricks and features October 19 2001 CSE 120 Lecture 8 Memory Management 3 9LUWXDO 0HPRU The abstraction that the OS will provide for managing memory is virtual memory VM Virtual memory enables a program to execute with less than its complete data in physical memory A program can run on a machine with less memory than it needs Can also run on a machine with too much physical memory Many programs do not need all of their code and data at once or ever no need to allocate memory for it OS will adjust amount of memory allocated to a process based upon its behavior VM requires hardware support and OS management algorithms to pull it off Let s go back to the beginning October 19 2001 CSE 120 Lecture 8 Memory Management 4 2 Q WKH EHJLQQLQJ Rewind to the days of batch programming Programs use physical addresses directly OS loads job runs it unloads it Multiprogramming changes all of this Want multiple processes in memory at once Overlap I O and CPU of multiple jobs Can do it a number of ways Fixed and variable partitioning paging segmentation Requirements Need protection restrict which addresses jobs can use Fast translation lookups need to be fast Fast change updating memory hardware on context switch October 19 2001 CSE 120 Lecture 8 Memory Management 5 9LUWXDO GGUHVVHV To make it easier to manage the memory of processes running in the system we re going to make them use virtual addresses logical addresses Virtual addresses are independent of the actual physical location of the data referenced OS determines location of data in physical memory Instructions executed by the CPU issue virtual addresses Virtual addresses are translated by hardware into physical addresses with help from OS The set of virtual addresses that can be used by a process comprises its virtual address space Many ways to do this translation Start with old simple ways progress to current techniques October 19 2001 CSE 120 Lecture 8 Memory Management 6 3 L HG 3DUWLWLRQV Physical memory is broken up into fixed partitions Advantages Hardware requirements base register Physical address virtual address base register Base register loaded by OS when it switches to a process Size of each partition is the same and fixed How do we provide protection Easy to implement fast context switch Problems Internal fragmentation memory in a partition not used by a process is not available to other processes Partition size one size does not fit all very large processes October 19 2001 CSE 120 Lecture 8 Memory Management 7 L HG 3DUWLWLRQV Physical Memory Base Register P1 P4 s Base P2 P3 Virtual Address Offset P4 P5 October 19 2001 CSE 120 Lecture 8 Memory Management 8 4 9DULDEOH 3DUWLWLRQV Natural extension physical memory is broken up into variable sized partitions Advantages Hardware requirements base register and limit register Physical address virtual address base register Why do we need the limit register Protection If physical address base limit then exception fault No internal fragmentation allocate just enough for process Problems External fragmentation job loading and unloading produces empty holes scattered throughout memory October 19 2001 CSE 120 Lecture 8 Memory Management 9 9DULDEOH 3DUWLWLRQV Base Register P3 s Base P1 Limit Register P2 P3 s Limit Virtual Address Offset Yes P3 No Protection Fault October 19 2001 CSE 120 Lecture 8 Memory Management 10 5 3DJLQJ Paging solves the external fragmentation problem by using fixed sized units in both physical and virtual memory Physical Memory Virtual Memory Page 1 Page 2 Page 3 Page N October 19 2001 CSE 120 Lecture 8 Memory Management 11 8VHU 3URFHVV 3HUVSHFWLYH Users and processes view memory as one contiguous address space from 0 through N Virtual address space VAS In reality pages are scattered throughout physical storage The mapping is invisible to the program Protection is provided because a program cannot reference memory outside of its VAS The address 0x1000 maps to different physical addresses in different processes October 19 2001 CSE 120 Lecture 8 Memory Management 12 6 3DJLQJ Translating addresses Virtual address has two parts virtual page number and offset Virtual page number VPN is an index into a page table Page table determines page frame number PFN Physical address is PFN offset Page tables Map virtual page number VPN to page frame number PFN One page table entry PTE per page in virtual address space VPN is the index into the table that determines PFN Or one PTE per VPN October 19 2001 CSE 120 Lecture 8 Memory Management 13 3DJH RRNXSV Physical Memory Virtual Address Page number Offset Page Table Physical Address Page frame Offset Page frame October 19 2001 CSE 120 Lecture 8 Memory Management 14 7 3DJLQJ DPSOH Pages are 4K Virtual address is 0x7468 Virtual page is 0x7 offset is 0x468 Page table entry 0x7 contains 0x2000 VPN is 20 bits 220 VPNs offset is 12 bits Page frame number is 0x2000 Seventh virtual page is at address 0x2000 second physical page Physical address 0x2000 0x468 0x2468 October 19 2001 CSE 120 Lecture 8 Memory Management 15 3DJH 7DEOH QWULHV 37 V 1 1 1 2 M R V Prot 20 Page Frame Number Page table entries control mapping The Modify bit says whether or not the page has been written The Reference bit says whether the page has been accessed The Valid bit says whether or not the PTE can be used It is set when a write to the page occurs It is set when a read or write to the page occurs It is checked each time the virtual address is used The Protection bits say what operations are allowed on page Read write execute The page frame number PFN determines physical page October 19 2001 CSE 120 Lecture 8 Memory Management 16 8
View Full Document
Unlocking...