CSE 120CSE 120Principles of OperatingPrinciples of OperatingSystemsSystemsWinter 2007Winter 2007Lecture 9: Memory ManagementLecture 9: Memory ManagementKeith Keith Marzullo Marzullo and Geoffrey M. Voelkerand Geoffrey M. VoelkerFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 2 © 2007 Keith Marzullo and Geoffrey M. VoelkerMemory ManagementMemory 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 competingprocesses 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)February 13, 2007 CSE 120 – Lecture 9 – Memory Management 3 © 2007 Keith Marzullo and Geoffrey M. VoelkerLecture OverviewLecture 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, efficientimplementations, and other VM tricks and featuresFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 4 © 2007 Keith Marzullo and Geoffrey M. VoelkerVirtual MemoryVirtual Memory The abstraction that the OS will provide for managingmemory is virtual memory (VM)◆ Virtual memory enables a program to execute with less than itscomplete 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 basedupon its behavior◆ VM requires hardware support and OS management algorithmsto pull it off Let’s go back to the beginning…February 13, 2007 CSE 120 – Lecture 9 – Memory Management 5 © 2007 Keith Marzullo and Geoffrey M. VoelkerIn the beginningIn 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 switchFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 6 © 2007 Keith Marzullo and Geoffrey M. VoelkerVirtual AddressesVirtual Addresses To make it easier to manage the memory of processesrunning in the system, we’re going to make them usevirtual addresses (logical addresses)◆ Virtual addresses are independent of the actual physicallocation 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 physicaladdresses (with help from OS)◆ The set of virtual addresses that can be used by a processcomprises its virtual address spaceFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 7 © 2007 Keith Marzullo and Geoffrey M. VoelkerVirtual AddressesVirtual Addresses Many ways to do this translation…◆ Start with old, simple ways, progress to current techniquesvmapprocessorphysicalmemoryvirtualaddressesphysicaladdressesFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 8 © 2007 Keith Marzullo and Geoffrey M. VoelkerFixed PartitionsFixed 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 aprocess is not available to other processes◆ Partition size: one size does not fit all (very large processes?)February 13, 2007 CSE 120 – Lecture 9 – Memory Management 9 © 2007 Keith Marzullo and Geoffrey M. VoelkerFixed PartitionsFixed PartitionsP4’s Base+OffsetVirtual AddressPhysical MemoryBase RegisterP1P2P3P4P5February 13, 2007 CSE 120 – Lecture 9 – Memory Management 10 © 2007 Keith Marzullo and Geoffrey M. VoelkerVariable PartitionsVariable Partitions Natural extension -- physical memory is broken up intovariable 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 producesempty holes scattered throughout memoryFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 11 © 2007 Keith Marzullo and Geoffrey M. VoelkerVariable PartitionsVariable PartitionsP3’s Base+OffsetVirtual AddressBase RegisterP2P3<Protection FaultYes?No?P3’s LimitLimit RegisterP1February 13, 2007 CSE 120 – Lecture 9 – Memory Management 12 © 2007 Keith Marzullo and Geoffrey M. VoelkerPagingPaging Paging solves the external fragmentation problem byusing fixed sized units in both physical and virtualmemoryVirtual MemoryPage 1Page 2Page 3Page NPhysical MemoryFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 13 © 2007 Keith Marzullo and Geoffrey M. VoelkerUser/Process PerspectiveUser/Process Perspective Users (and processes) view memory as onecontiguous address space from 0 through N◆ Virtual address space (VAS) In reality, pages are scattered throughout physicalstorage The mapping is invisible to the program Protection is provided because a program cannotreference memory outside of its VAS◆ The address “0x1000” maps to different physical addresses indifferent processesFebruary 13, 2007 CSE 120 – Lecture 9 – Memory Management 14 © 2007 Keith Marzullo and Geoffrey M. VoelkerPagingPaging Translating addresses◆ Virtual address has two
View Full Document