Khoa học máy tính - Chapter 12: Virtual memory

Chapter 12Virtual MemoryCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionVirtual Memory BasicsDemand PagingThe Virtual Memory ManagerPage Replacement PoliciesControlling Memory Allocation to a ProcessShared PagesMemory-Mapped FilesCase Studies of Virtual Memory Using PagingVirtual Memory Using Segmentation2MMU translates logical address into physical oneVirtual memory manager is a software componentUses demand loadingExploits locality of reference to improve performanceOperating Systems, by Dhananjay Dhamdhere*Virtual Memory Basics3Operating Systems, by Dhananjay Dhamdhere*Virtual Memory Basics (continued)4Operating Systems, by Dhananjay Dhamdhere*Virtual Memory Using Paging MMU performs address translation using page tableEffective memory address of logical address (pi, bi)= start address of the page frame containing page pi + bi5Operating Systems, by Dhananjay Dhamdhere*Demand Paging Preliminaries6Operating Systems, by Dhananjay Dhamdhere*Demand Paging Preliminaries (continued)Memory Management Unit (MMU) raises a page fault interrupt if page containing logical address not in memory7Operating Systems, by Dhananjay Dhamdhere*Demand Paging Preliminaries (continued)A page fault interrupt is raised because Valid bit of page 3 is 08Operating Systems, by Dhananjay Dhamdhere*Demand Paging Preliminaries (continued)At a page fault, the required page is loaded in a free page frameIf no page frame is free, virtual memory manager performs a page replacement operationPage replacement algorithmPage-out initiated if page is dirty (modified bit is set)Page-in and page-out: page I/O or page trafficEffective memory access time in demand paging:9(Empirical) law of locality of reference: logical addresses used by process in a short interval tend to be grouped in certain portions of its logical address spaceOperating Systems, by Dhananjay Dhamdhere*Page Replacement10How much memory to allocate to a processOperating Systems, by Dhananjay Dhamdhere*Memory Allocation to a Process11Operating Systems, by Dhananjay Dhamdhere*Optimal Page SizeSize of a page is defined by computer hardwarePage size determines: No of bits required to represent byte number in a pageMemory wastage due to internal fragmentationSize of the page table for a processPage fault rates when a fixed amount of memory is allocated to a processUse of larger page sizes than optimal value implies somewhat higher page fault rates for a processTradeoff between HW cost and efficient operation12Operating Systems, by Dhananjay Dhamdhere*Paging HardwarePage-table-address-register (PTAR) points to the start of a page table13Operating Systems, by Dhananjay Dhamdhere*Paging Hardware (continued)14Operating Systems, by Dhananjay Dhamdhere*Memory ProtectionMemory protection violation raised if:Process tries to access a nonexistent pageProcess exceeds its (page) access privilegesIt is implemented through:Page table size register (PTSR) of MMUKernel records number of pages contained in a process in its PCBLoads number from PCB in PTSR when process is scheduledProt info field of the page’s entry in the page table15Translation look-aside buffer (TLB): small and fast associative memory used to speed up address translationOperating Systems, by Dhananjay Dhamdhere*Address Translation and Page Fault Generation16Operating Systems, by Dhananjay Dhamdhere*Address Translation and Page Fault Generation (continued)TLBs can be HW or SW managed17Operating Systems, by Dhananjay Dhamdhere*Address Translation and Page Fault Generation (continued)Some mechanisms used to improve performance:Wired TLB entries for kernel pages: never replacedSuperpagesTLB hit ratio18SuperpagesTLB reach is stagnant even though memory sizes increase rapidly as technology advancesTLB reach = page size x no of entries in TLBIt affects performance of virtual memorySuperpages are used to increase the TLB reachA superpage is a power of 2 multiple of page sizeIts start address (both logical and physical) is aligned on a multiple of its own sizeMax TLB reach = max superpage size x no of entries in TLBSize of a superpage is adapted to execution behavior of a process through promotions and demotionsOperating Systems, by Dhananjay Dhamdhere*19Operating Systems, by Dhananjay Dhamdhere*Support for Page ReplacementVirtual memory manager needs following information for minimizing page faults and number of page-in and page-out operations:The time when a page was last usedExpensive to provide enough bits for this purposeSolution: use a single reference bitWhether a page is dirtyA page is clean if it is not dirtySolution: modified bit in page table entry20Operating Systems, by Dhananjay Dhamdhere*Practical Page Table OrganizationsA process with a large address space requires a large page table, which occupies too much memorySolutions:Inverted page tableDescribes contents of each page frameSize governed by size of memoryIndependent of number and sizes of processesContains pairs of the form (program id, page #)Con: information about a page must be searchedMultilevel page tablePage table of process is paged21Operating Systems, by Dhananjay Dhamdhere*Inverted Page TablesUse of hash tableSpeeds up search22Operating Systems, by Dhananjay Dhamdhere*Multilevel Page TablesIf size of a table entry is 2e bytes, number of page table entries in one PT page is 2nb/2eLogical address (pi , bi) is regrouped into three fields:PT page with the number pi1 contains entry for pipi2 is entry number for pi in PT pagebi23Operating Systems, by Dhananjay Dhamdhere*I/O Operations in a Paged EnvironmentProcess makes system call for I/O operationsParameters include: number of bytes to transfer, logical address of the data areaCall activates I/O handler in kernelI/O subsystem does not contain an MMU, so I/O handler replaces logical address of data area with physical address, using information from process page tableI/O fix (bit in misc info field) ensures pages of data area are not paged outScatter/gather feature can deposit parts of I/O operation’s data in noncontiguous memory areasAlternatively, data area pages put in contiguous areas24Operating Systems, by Dhananjay Dhamdhere*Example: I/O Operations in Virtual Memory25Operating Systems, by Dhananjay Dhamdhere*The Virtual Memory Manager26Operating Systems, by Dhananjay Dhamdhere*Example: Page Replacement27Operating Systems, by Dhananjay Dhamdhere*Overview of Operation of the Virtual Memory ManagerVirtual memory manager makes two important decisions during its operation:Upon a page fault, decides which page to replacePeriodically decides how many page frames should be allocated to a process28Operating Systems, by Dhananjay Dhamdhere*Page Replacement PoliciesA page replacement policy should replace a page not likely to be referenced in the immediate futureExamples:Optimal page replacement policyMinimizes total number of page faults; infeasible in practiceFirst-in first-out (FIFO) page replacement policyLeast recently used (LRU) page replacement policyBasis: locality of referencePage reference stringsTrace of pages accessed by a process during its operationWe associate a reference time string with each29Operating Systems, by Dhananjay Dhamdhere*Example: Page Reference StringA computer supports instructions that are 4 bytes in lengthUses a page size of 1KBSymbols A and B are in pages 2 and 530Operating Systems, by Dhananjay Dhamdhere*31Operating Systems, by Dhananjay Dhamdhere*Page Replacement Policies (continued)To achieve desirable page fault characteristics, faults shouldn’t increase when memory allocation is increasedPolicy must have stack (or inclusion) property32Operating Systems, by Dhananjay Dhamdhere*FIFO page replacement policy does not exhibit stack property.33Operating Systems, by Dhananjay Dhamdhere*Page Replacement Policies (continued)Virtual memory manager cannot use FIFO policy Increasing allocation to a process may increase page fault frequency of processWould make it impossible to control thrashing34Operating Systems, by Dhananjay Dhamdhere*Practical Page Replacement PoliciesVirtual memory manager has two threadsFree frames manager implements page replacement policyPage I/O manager performs page-in/out operations35Operating Systems, by Dhananjay Dhamdhere*Practical Page Replacement Policies (continued)LRU replacement is not feasibleComputers do not provide sufficient bits in the ref info field to store the time of last referenceMost computers provide a single reference bitNot recently used (NRU) policies use this bitSimplest NRU policy: Replace an unreferenced page and reset all reference bits if all pages have been referencedClock algorithms provide better discrimination between pages by resetting reference bits periodicallyOne-handed clock algorithmTwo-handed clock algorithmResetting pointer (RP) and examining pointer (EP)36Operating Systems, by Dhananjay Dhamdhere*Example: Two-Handed Clock AlgorithmBoth pointers are advanced simultaneouslyAlgorithm properties defined by pointer distance:If pointers are close together, only recently used pages will survive in memoryIf pointers are far apart, only pages that have not been used in a long time would be removed37Operating Systems, by Dhananjay Dhamdhere*Controlling Memory Allocation to a ProcessProcess Pi is allocated alloci number of page framesFixed memory allocation Fixes alloc statically; uses local page replacementVariable memory allocationUses local and/or global page replacementIf local replacement is used, handler periodically determines correct alloc value for a processMay use working set model Sets alloc to size of the working set38Operating Systems, by Dhananjay Dhamdhere*Implementation of a Working Set Memory AllocatorSwap out a process if alloc page frames cannot be allocatedExpensive to determine WSi(t,∆) and alloci at every time instant tSolution: Determine working sets periodicallySets determined at end of an interval are used to decide values of alloc for use during the next interval39Operating Systems, by Dhananjay Dhamdhere*Shared PagesStatic sharing results from static binding performed by a linker/loader before execution of programDynamic binding conserves memory by binding same copy of a program/data to several processesProgram or data shared retains its identityTwo conditions should be satisfied:Shared program should be coded as reentrantCan be invoked by many processes at the same timeProgram should be bound to identical logical addresses in every process that shared it40Operating Systems, by Dhananjay Dhamdhere*Shared pages should have samepage numbers inall processes41Operating Systems, by Dhananjay Dhamdhere*Copy-on-WriteFeature used to conserve memory when data in shared pages could be modifiedCopy-on-write flag in page table entries Memory allocation decisions are performed staticallyA private copy of page k is made when A modifies it42Operating Systems, by Dhananjay Dhamdhere*Memory-Mapped FilesMemory mapping of a file by a process binds file to a part of the logical address space of the processBinding is performed when process makes a memory map system callAnalogous to dynamic binding of programs and data43Operating Systems, by Dhananjay Dhamdhere*Memory-Mapped Files (continued)44Operating Systems, by Dhananjay Dhamdhere*Case Studies of Virtual Memory Using PagingUnix Virtual MemoryLinux Virtual MemoryVirtual Memory in SolarisVirtual Memory in Windows45Operating Systems, by Dhananjay Dhamdhere*Unix Virtual MemoryPaging hardware differs in architecturesPages can be: resident, unaccessed, swapped-outAllocation of as little swap space as possibleCopy-on-write for forkLack reference bit in some HW architectures; compensated using valid bit in interesting mannerProcess can fix some pages in memoryPageout daemon uses a clock algorithmSwaps out a process if all required pages cannot be in memoryA swap-in priority is used to avoid starvation46Operating Systems, by Dhananjay Dhamdhere*Linux Virtual MemoryPage size of 4 KBOn 64-bit architectures, uses three-level page tableStates for page frames: free, active, inactive dirty, inactive laundered, inactive cleanPage replacement based on a clock algorithmUses two lists called active list and inactive listBuddy system allocator for allocating page framesSeveral virtual memory regions for a process:Zero-filled, file-backed, private memory47Operating Systems, by Dhananjay Dhamdhere*Virtual Memory in SolarisSupports normal pages and superpagesSuperpages:Automatically for processes with large address spacesCan be requested using memcntl system callNot used for memory-mapped filesSolaris 6 introduced priority paging to avoid interference between file processing and virtual memoryPage scanner tries to keep a sufficient number of page frames on cyclic page cache (since Solaris 8)lotsfree parameter indicates how many page frames should be freeUses two-handed clock algorithm on a global basis48Operating Systems, by Dhananjay Dhamdhere*Virtual Memory in WindowsSupports both 32-bit and 64-bit logical addressesPage size is 4 KBProcess address space is either 2 GB or 3 GBTwo-, three- or four-level page tables and various page table entry formatsOn the X-86 architecture:Page frame can be in one of eight states, including: valid, free, zeroed, standby, modified, and badA process must first reserve virtual address space and then commit it for specific entities49Operating Systems, by Dhananjay Dhamdhere*Virtual Memory in Windows (continued)A section object represents a section of memory that can be sharedA process maps a view to access part of a sectionCopy-on-write feature used for sharing pagesPrototype PTE is set-up for shared pagesTLBs are managed by HW (32-bit) or SW (64-bit)Exploits reference locality: loads a few pages before and after a page-faulted page into memoryUses notion of working sets (for memory allocation)Clock algorithmPage lists: free, zero-initiated, modified, standby50Operating Systems, by Dhananjay Dhamdhere*Virtual Memory Using SegmentationA segment is a logical entity in a program, such as a function, a data structure, or an objectOr, a module that consists of some or all of theseConvenient unit for sharing and protection51Operating Systems, by Dhananjay Dhamdhere*Example: Effective Address Calculation in SegmentationLogical address (si, bi) can be specified as ids(alpha, beta)alpha: name of a segmentbeta: id associated with a byte contained in alpha52Operating Systems, by Dhananjay Dhamdhere*Management of MemorySimilarities to paging:Segment fault indicates segment is not in memorySegment-in operation is performed to load segmentSegment-out operations may be needed firstCan use working set of segment for allocationSegments can be replaced on NRU basisDifferences to paging:Can lead to external fragmentationTackled through compaction or through memory reuse techniques (first fit, best fit, etc.)Segments can dynamically grow or shrink in size53Operating Systems, by Dhananjay Dhamdhere*Sharing and ProtectionTwo important issues in protection and sharing of segments are:Static and dynamic sharing of segmentsDetecting use of invalid addressesProtection exception if bi exceeds size of si54External fragmentation exists in a virtual memory using segmentationSolution: segmentation with pagingOperating Systems, by Dhananjay Dhamdhere*Segmentation with Paging55Operating Systems, by Dhananjay Dhamdhere*SummaryBasic actions in virtual memory using paging: address translation and demand loading of pagesImplemented jointly byMemory Management Unit (MMU): HardwareVirtual memory manager: SoftwareMemory is divided into page frames Virtual memory manager maintains a page tableInverted and multilevel page tables use less memory but are less efficientA fast TLB is used to speed up address translation56Operating Systems, by Dhananjay Dhamdhere*Summary (continued)Which page should VM manager remove from memory to make space for a new page?Page replacement algorithms exploit locality of referenceLRU has stack property, but is expensiveNRU algorithms are used in practiceE.g., clock algorithmsHow much memory should manager allocate?Use working set model to avoid thrashingCopy-on-write can be used for shared pagesMemory mapping of files speeds up access to data57