1&6(3ULQFLSOHVRI2SHUDWLQJ6\VWHPV)DOOLecture 8: Memory ManagementGeoffrey M. VoelkerOctober 19, 2001 CSE 120 – Lecture 8 – Memory Management 20HPRU\0DQDJHPHQWNext few lectures are going to cover memory management● Goals of memory management◆ To provide a convenient abstraction for programming◆ To allocate scarce memory resources among competing processes to maximize performance with minimal overhead● Mechanisms◆ Physical and virtual addressing (1)◆ Techniques: Partitioning, paging, segmentation (1)◆ Page table management, TLBs, VM tricks (2)● Policies◆ Page replacement algorithms (3)2October 19, 2001 CSE 120 – Lecture 8 – Memory Management 3/HFWXUH2YHUYLHZ● 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 featuresOctober 19, 2001 CSE 120 – Lecture 8 – Memory Management 49LUWXDO0HPRU\● 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…3October 19, 2001 CSE 120 – Lecture 8 – Memory Management 5,QWKHEHJLQQLQJ«● 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 switchOctober 19, 2001 CSE 120 – Lecture 8 – Memory Management 69LUWXDO$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 techniques4October 19, 2001 CSE 120 – Lecture 8 – Memory Management 7)L[HG3DUWLWLRQV● Physical memory is broken up into fixed partitions◆ 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?● Advantages◆ 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 8)L[HG3DUWLWLRQVP4’s Base+OffsetVirtual AddressPhysical MemoryBase RegisterP1P2P3P4P55October 19, 2001 CSE 120 – Lecture 8 – Memory Management 99DULDEOH3DUWLWLRQV● Natural extension -- physical memory is broken up into variable sized partitions◆ 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● Advantages◆ No internal fragmentation: allocate just enough for process● Problems◆ External fragmentation: job loading and unloading produces empty holes scattered throughout memoryOctober 19, 2001 CSE 120 – Lecture 8 – Memory Management 109DULDEOH3DUWLWLRQVP3’s Base+OffsetVirtual AddressBase RegisterP2P3<Protection FaultYes?No?P3’s LimitLimit RegisterP16October 19, 2001 CSE 120 – Lecture 8 – Memory Management 113DJLQJ● Paging solves the external fragmentation problem by using fixed sized units in both physical and virtual memoryVirtual MemoryPage 1Page 2Page 3Page NPhysical MemoryOctober 19, 2001 CSE 120 – Lecture 8 – Memory Management 128VHU3URFHVV3HUVSHFWLYH● 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 processes7October 19, 2001 CSE 120 – Lecture 8 – Memory Management 133DJLQJ● 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)» VPN is the index into the table that determines PFN◆ One page table entry (PTE) per page in virtual address space» Or, one PTE per VPNOctober 19, 2001 CSE 120 – Lecture 8 – Memory Management 143DJH/RRNXSVPage framePage number OffsetVirtual AddressPage TablePage frame OffsetPhysical AddressPhysical Memory8October 19, 2001 CSE 120 – Lecture 8 – Memory Management 153DJLQJ([DPSOH● Pages are 4K◆ VPN is 20 bits (220VPNs), offset is 12 bits● Virtual address is 0x7468◆ Virtual page is 0x7, offset is 0x468● Page table entry 0x7 contains 0x2000◆ Page frame number is 0x2000◆ Seventh virtual page is at address 0x2000 (second physical page)● Physical address = 0x2000 + 0x468 = 0x2468October 19, 2001 CSE 120 – Lecture 8 – Memory Management
View Full Document