Lecture 10:Lecture 10:Memory ManagementMemory ManagementCSE 120: Principles of Operating Systemsguest starring Amin VahdatProject 2 Due 11/14CSE 120 – Lecture 10: Memory Management 2Memory 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)CSE 120 – Lecture 10: Memory Management 3Lecture 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 featuresCSE 120 – Lecture 10: Memory Management 4Virtual MemoryVirtual Memory OS provides Virtual Memory (VM) as the abstraction formanaging memory◆ Indirection allows moving programs around in memory◆ Allows processes to address more or less memory thanphysically installed in the machine» Virtual memory enables a program to execute with less than itscomplete data in physical memory» Many programs do not need all of their code and data at once (orever) – no need to allocate memory for it» OS adjusts amount of memory allocated based upon behavior Requires hardware support for efficient implementation Let’s go back to the beginning…CSE 120 – Lecture 10: Memory Management 5In the beginningIn the beginning…… 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 switchCSE 120 – Lecture 10: Memory Management 6Virtual 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 space Many ways to do this translation…◆ Start with old, simple ways, progress to current techniquesCSE 120 – Lecture 10: Memory Management 7Fixed 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?)CSE 120 – Lecture 10: Memory Management 8Fixed PartitionsFixed PartitionsP4’s Base+OffsetVirtual AddressPhysical MemoryBase RegisterP1P2P3P4P5CSE 120 – Lecture 10: Memory Management 9Variable 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 memoryCSE 120 – Lecture 10: Memory Management 10Variable PartitionsVariable PartitionsP3’s Base+OffsetVirtual AddressBase RegisterP2P3<Protection FaultYes?No?P3’s LimitLimit RegisterP1CSE 120 – Lecture 10: Memory Management 11PagingPaging Paging solves the external fragmentation problem by using fixed sizedunits in both physical and virtual memoryVirtual MemoryPage1Page2Page3Page NPhysical MemoryCSE 120 – Lecture 10: Memory Management 12User/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 processesCSE 120 – Lecture 10: Memory Management 13PagingPaging 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 VPNCSE 120 – Lecture 10: Memory Management 14Page LookupsPage LookupsPage framePage number OffsetVirtual AddressPage TablePage frame OffsetPhysical AddressPhysical MemoryCSE 120 – Lecture 10: Memory Management 15Paging ExamplePaging Example Pages are 4K◆ VPN is 20 bits (220 VPNs), offset is 12 bits Virtual address is 0x7468◆ Virtual page is 0x7, offset is 0x468 Page table entry 0x7 contains 0x2◆ Page frame base is 0x2 * 0x1000 (4K) = 0x2000◆ Seventh virtual page is at address 0x2000 (3rd physical page) Physical address = 0x2000 + 0x468 = 0x2468CSE 120 – Lecture 10: Memory Management 16Page Table Entries (Page Table Entries (PTEsPTEs)) Page table entries control mapping◆ The Modify bit says whether or not the page has
View Full Document