CSE 120 Principles of Operating Systems Spring 2009Memory ManagementLecture OverviewVirtual MemoryIn the beginning…Virtual AddressesVirtual AddressesFixed PartitionsFixed PartitionsVariable PartitionsVariable PartitionsPagingUser/Process PerspectivePagingPage LookupsPaging ExamplePage Table Entries (PTEs)Paging AdvantagesPaging LimitationsSegmentationSegment LookupsSegment TableSegmentation and PagingSummaryNext time…CSE 120Principles of Operating SystemsSpring 2009Lecture 9: Memory ManagementGeoffrey M. VoelkerMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 2Memory ManagementNext 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)May 7, 2009 CSE 120 – Lecture 9 – Memory Management 3Lecture Overview 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 featuresMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 4Virtual Memory 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…May 7, 2009 CSE 120 – Lecture 9 – Memory Management 5In the beginning… Rewind to the days of “second-generation” computers 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 switchMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 6Virtual Addresses 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 spaceMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 7Virtual Addresses Many ways to do this translation… Start with old, simple ways, progress to current techniquesvmapprocessorphysicalmemoryvirtualaddressesphysicaladdressesMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 8Fixed Partitions 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?)May 7, 2009 CSE 120 – Lecture 9 – Memory Management 9Fixed PartitionsP4’s Base+OffsetVirtual AddressPhysical MemoryBase RegisterP1P2P3P4P5May 7, 2009 CSE 120 – Lecture 9 – Memory Management 10Variable Partitions 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 memoryMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 11Variable PartitionsP3’s Base+OffsetVirtual AddressBase RegisterP2P3<Protection FaultYes?No?P3’s LimitLimit RegisterP1May 7, 2009 CSE 120 – Lecture 9 – Memory Management 12Paging Paging solves the external fragmentation problem by using fixed sized units in both physical and virtual memoryVirtual MemoryPage 1Page 2Page 3Page NPhysical MemoryMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 13User/Process Perspective 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 processesMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 14Paging 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 VPNMay 7, 2009 CSE 120 – Lecture 9 – Memory Management 15Page LookupsPage framePage number OffsetVirtual AddressPage TablePage frame OffsetPhysical AddressPhysical MemoryMay 7,
View Full Document
Unlocking...