Chapter 8 Virtual Memory

of 105

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
105 pages
0 downs
3 views
Share
Description
Chapter 8 Virtual Memory. Operating Systems: Internals and Design Principles. Operating Systems: Internals and Design Principles. You’re gonna need a bigger boat. — Steven Spielberg, JAWS, 1975. Hardware and Control Structures. Two characteristics fundamental to memory management:
Transcript
Chapter 8Virtual MemoryOperating Systems:Internals and Design PrinciplesSeventh EditionWilliam StallingsOperating Systems:Internals and Design PrinciplesYou’re gonna need a bigger boat.— Steven Spielberg, JAWS, 1975Hardware and Control Structures
  • Two characteristics fundamental to memory management:
  • all memory references are logical addresses that are dynamically translated into physical addresses at run time
  • a process may be broken up into a number of pieces that don’t need to be contiguously located in main memory during execution
  • If these two characteristics are present, it is not necessary that all of the pages or segments of a process be in main memory during execution
  • TerminologyExecution of a ProcessContinued . . .Operating system brings into main memory a few pieces of the programResident set - portion of process that is in main memoryAn interrupt is generated when an address is needed that is not in main memory (segment/page fault)Operating system places the process in a blocking stateExecution of a Process
  • Piece of process that contains the logical address is brought into main memory
  • operating system issues a disk I/O Read request
  • another process is dispatched to run while the disk I/O takes place
  • an interrupt is issued when disk I/O is complete, which causes the operating system to place the affected process in the Ready state
  • Implications
  • More processes may be maintained in main memory
  • only load in some of the pieces of each process
  • with so many processes in main memory, it is very likely a process will be in the Ready state at any particular time
  • A process may be larger than all of main memory
  • Real and Virtual MemoryTable 8.2 Characteristics of Paging and SegmentationThrashingPrinciple of LocalityProgram and data references within a process tend to clusterOnly a few pieces of a process will be needed over a short period of timeTherefore it is possible to make intelligent guesses about which pieces will be needed in the futureMaking good guesses avoids thrashingPaging BehaviorDuring the lifetime of the process, references are confined to a subset of pagesSupport Needed for Virtual MemoryPaging
  • The term virtual memory is usually associated with systems that employ paging
  • Use of paging to achieve virtual memory was first reported for the Atlas computer
  • Each process has its own page table
  • each page table entry contains the frame number of the corresponding page in main memory
  • Entry k contains the frame # of page k (if page k is in memory)
  • Memory Management FormatsAddress TranslationSimple PT StructureSimple page table: one PT per processSize is a problem – for 32-bit addresses, half for OS, half for user space, the number of pages in a user process is 232/pagesize. For pagesize = 210, page table would have 222 entries. PER PROCESS!Solution? Page the page table!Hierarchical PT StructureStill, one PT per process, but only load the parts being used; e.g, a two-level page table consists ofA page directory, or root page table, in which each entry points to a small page tableThe individual page tables, each of which points to a portion of the total virtual address space Hierarchical PT ExampleFor a 32-bit address, 4-Kbyte (212) pages:Simple address: 20-bit page #, 12-bit offsetHierarchical address: 20-bit page # is now split into two parts: 10 bits to select an entry in the root page table and 10 bits to select an entry in the corresponding smaller page tableRegardless of the page table format, there are 220 pages of length 212.Two-Level Hierarchical Page TableAddress TranslationInverted PT Structure
  • Simple page tables, hierarchical page tables occupy a lot of space: each process has its own PT, size of each PT is proportional to size of virtual address space.
  • Another approach: one page table maps everything in memory. Page table size is fixed.
  • Inverted PT Structure
  • Page number portion of a virtual address is mapped into a hash value
  • hash value points to inverted page table
  • Fixed proportion of real memory is required for the tables regardless of the number of processes or virtual pages supported
  • Structure is called inverted because it indexes page table entries by frame number rather than by virtual page number
  • Inverted Page TableInverted Page TableEach entry in the page table includes:Virtual Memory Problems
  • Page tables can occupy large amounts of memory
  • Solution: hierarchical or inverted page tables
  • Address translation using page tables increases execution time
  • Solution: Translation Lookaside Buffer (TLB)
  • Translation LookasideBuffer (TLB)
  • To overcome the effect of doubling the memory access time, most virtual memory schemes make use of a special high-speed cache called a translation lookaside buffer
  • Each virtual memory reference can cause two physical memory accesses:
  • one to fetch the page table entry
  • one to fetch the data (or the next instruction)
  • Use of a TLBTLB OperationAssociative Mapping
  • The TLB only contains some of the page table entries so we cannot simply index into the TLB based on page number
  • each TLB entry must include the page number as well as the complete page table entry
  • The processor is equipped with hardware that allows it to interrogate simultaneously a number of TLB entries to determine if there is a match on page number
  • Direct Versus Associative LookupTLB and Cache OperationPage Size
  • The smaller the page size, the lesser the amount of internal fragmentation
  • however, more pages are required per process
  • more pages per process means larger page tables
  • for large programs in a heavily multiprogrammed environment some portion of the page tables of active processes must be in virtual memory instead of main memory
  • the physical characteristics of most secondary-memory devices favor a larger page size for more efficient block transfer of data
  • Paging Behavior of a ProgramExample: Page SizesPage Size
  • Contemporary programming techniques used in large programs tend to decrease the locality of references within a process
  • SegmentationSegmentation allows the programmer to view memory as consisting of multiple address spaces or segmentsSegment OrganizationEach segment table entry contains the starting address of the corresponding segment in main memory and the length of the segmentA bit is needed to determine if the segment is already in main memoryAnother bit is needed to determine if the segment has been modified since it was loaded in main memoryAddress TranslationCombined Paging and SegmentationAddress TranslationCombined Segmentation and PagingProtection and SharingSegmentation lends itself to the implementation of protection and sharing policiesEach entry has a base address and length so inadvertent memory access can be controlledSharing can be achieved by segments referencing multiple processesProtection RelationshipsREVIEWVirtual memory: a technique for executing processes that aren’t entirely in memory which provides the illusion of large memoryUse a combination of RAM + diskSwap parts of the program (pages) in and out of memory as neededPage tables keep track of the pagesProblems: page table storage, extra memory references.Operating System SoftwarePolicies for Virtual Memory
  • Key issue: Performance
  • minimize page faults
  • Fetch PolicyDetermines when a page should be brought into memoryDemand Paging
  • Demand Paging
  • only brings pages into main memory when a reference is made to a location on the page
  • many page faults when process is first started
  • principle of locality suggests that as more and more pages are brought in, most future references will be to pages that have recently been brought in, and page faults should drop to a very low level
  • Prepaging
  • Prepaging
  • pages other than the one demanded by a page fault are brought in
  • exploits the characteristics of most secondary memory devices
  • if pages of a process are stored contiguously in secondary memory it is more efficient to bring in a number of pages at one time
  • ineffective if extra pages are not referenced
  • should not be confused with “swapping”
  • Determines where in real memory a process piece is to resideImportant design issue in a segmentation systemPaging or combined paging with segmentation placing is irrelevant because hardware performs functions with equal efficiencyFor NUMA systems an automatic placement strategy is desirablePlacement PolicyReplacement Policy
  • Deals with the selection of a page in main memory to be replaced when a new page must be brought in
  • objective is that the page that is removed be the page least likely to be referenced in the near future
  • The more elaborate the replacement policy the greater the hardware and software overhead to implement it
  • Frame Locking
  • When a frame is locked the page currently stored in that frame may not be replaced
  • kernel of the OS as well as key control structures are held in locked frames
  • I/O buffers and time-critical areas may be locked into main memory frames
  • locking is achieved by associating a lock bit with each frame
  • Basic AlgorithmsOptimal Policy
  • Selects the page for which the time to the next reference is the longest
  • Produces three page faults after the frame allocation has been filled
  • Least Recently Used (LRU)
  • Replaces the page that has not been referenced for the longest time
  • By the principle of locality, this should be the page least likely to be referenced in the near future
  • Difficult to implement
  • one approach is to tag each page with the time of last reference
  • this requires a great deal of overhead
  • LRU ExampleFirst-in-First-out (FIFO)
  • Treats page frames allocated to a process as a circular buffer
  • Pages are removed in round-robin style
  • simple replacement policy to implement
  • Page that has been in memory the longest is replaced
  • FIFO ExampleClock Policy
  • Requires the association of an additional bit with each frame
  • referred to as the use bit
  • When a page is first loaded in memory or referenced, the use bit is set to 1
  • The set of frames is considered to be a circular buffer
  • Any frame with a use bit of 1 is passed over by the algorithm
  • Page frames visualized as laid out in a circle
  • Clock Policy ExampleClock PolicyComparison of AlgorithmsClock PolicyCombined ExamplesPage BufferingImproves paging performance and allows the use of a simpler page replacement policyReplacement Policy and Cache Size
  • With large caches, replacement of pages can have a performance impact
  • if the page frame selected for replacement is in the cache, that cache block is lost as well as the page that it holds
  • in systems using page buffering, cache performance can be improved with a policy for page placement in the page buffer
  • most operating systems place pages by selecting an arbitrary page frame from the page buffer
  • Resident Set Management
  • The OS must decide how many pages to bring into main memory
  • the smaller the amount of memory allocated to each process, the more processes can reside in memory
  • small number of pages loaded increases page faults
  • beyond a certain size, further allocations of pages will not effect the page fault rate
  • Resident Set SizeFixed-allocationVariable-allocationallows the number of page frames allocated to a process to be varied over the lifetime of the process
  • gives a process a fixed number of frames in main memory within which to execute
  • when a page fault occurs, one of the pages of that process must be replaced
  • Replacement Scope
  • The scope of a replacement strategy can be categorized as globalor local
  • both types are activated by a page fault when there are no free page frames
  • VM Policies - Review
  • Key issue: Performance
  • minimize page faults
  • Resident Set Management SummaryFixed Allocation, Local ScopeNecessary to decide ahead of time the amount of allocation to give a processIf allocation is too small, there will be a high page fault rateVariable Allocation Global Scope
  • Easiest to implement
  • adopted in a number of operating systems
  • OS maintains a list of free frames
  • Free frame is added to resident set of process when a page fault occurs
  • If no frames are available the OS must choose a page currently in memory
  • One way to counter potential problems is to use page buffering
  • Variable Allocation Local ScopeWhen a new process is loaded into main memory, allocate to it a certain number of page frames as its resident setWhen a page fault occurs, select the page to replace from among the resident set of the process that suffers the faultPeriodically, reevaluate the allocation provided to the process and increase or decrease it to improve overall performanceVariable AllocationLocal ScopeDecision to increase or decrease a resident set size is based on the assessment of the likely future demands of active processesFigure 8.19Working Set of Process as Defined by Window SizeW(t, Δ) Page Fault Frequency (PFF)Requires a use bit to be associated with each page in memoryBit is set to 1 when that page is accessedWhen a page fault occurs, the OS notes the virtual time since the last page fault for that processDoes not perform well during the transient periods when there is a shift to a new localityTime-between-page-faults: easier to measure & is equal to 1/PFF so may be a good substituteVariable-interval Sampled Working Set (VSWS)Evaluates the working set of a process at sampling instances based on elapsed virtual timeDriven by three parameters:Cleaning PolicyConcerned with determining when a modified page should be written out to secondary memoryLoad Control
  • Determines the number of processes that will be resident in main memory
  • multiprogramming level
  • Critical in effective memory management
  • Too few processes, many occasions when all processes will be blocked and much time will be spent in swapping
  • Too many processes will lead to thrashing
  • MultiprogrammingProcess SuspensionIf the degree of multiprogramming is to be reduced, one or more of the currently resident processes must be swapped outUnix
  • Intended to be machine independent so its memory management schemes will vary
  • early Unix: variable partitioning with no virtual memory scheme
  • current implementations of UNIX and Solaris make use of paged virtual memory
  • UnixPaging System and Kernel Memory AllocatorUNIX SVR4 MemoryManagement FormatsTable 8.6 UNIX SVR4 Memory Management Parameters (page 1 of 2)Table 8.6 UNIX SVR4 Memory Management Parameters (page 2 of 2)Page Replacement
  • The page frame data table is used for page replacement
  • Pointers are used to create lists within the table
  • all available frames are linked together in a list of free frames available for bringing in pages
  • when the number of available frames drops below a certain threshold, the kernel will steal a number of frames to compensate
  • “Two Handed” Clock Page ReplacementKernel Memory AllocatorThe kernel generates and destroys small tables and buffers frequently during the course of execution, each of which requires dynamic memory allocation.Most of these blocks are significantly smaller than typical pages (therefore paging would be inefficient)Allocations and free operations must be made as fast as possibleLazy Buddy
  • Technique adopted for SVR4
  • UNIX often exhibits steady-state behavior in kernel memory demand
  • i.e. the amount of demand for blocks of a particular size varies slowly in time
  • Defers coalescing until it seems likely that it is needed, and then coalesces as many blocks as possible
  • Lazy Buddy System AlgorithmLinux Memory Management
  • Shares many characteristics with Unix
  • Is quite complex
  • Linux Virtual Memory
  • Three level page table structure:
  • Address TranslationLinux Page Replacement
  • Based on the clock algorithm
  • The use bit is replaced with an 8-bit age variable
  • incremented each time the page is accessed
  • Periodically decrements the age bits
  • a page with an age of 0 is an “old” page that has not been referenced is some time and is the best candidate for replacement
  • A form of least frequently used policy
  • Kernel Memory Allocation
  • Kernel memory capability manages physical main memory page frames
  • primary function is to allocate and deallocate frames for particular uses
  • A buddy algorithm is used so that memory for the kernel can be allocated and deallocated in units of one or more pages
  • Page allocator alone would be inefficient because the kernel requires small short-term memory chunks in odd sizes
  • Slab allocation
  • used by Linux to accommodate small chunks
  • Windows Memory ManagementVirtual memory manager controls how memory is allocated and how paging is performedDesigned to operate over a variety of platformsUses page sizes ranging from 4 Kbytes to 64 KbytesWindows Virtual Address Map
  • On 32 bit platforms each user process sees a separate 32 bit address space allowing 4 Gbytes of virtual memory per process
  • by default half is reserved for the OS
  • Large memory intensive applications run more effectively using 64-bit Windows
  • Most modern PCs use the AMD64 processor architecture which is capable of running as either a 32-bit or 64-bit system
  • 32-Bit Windows Address SpaceWindows PagingOn creation, a process can make use of the entire user space of almost 2 GbytesThis space is divided into fixed-size pages managed in contiguous regions allocated on 64 Kbyte boundariesRegions may be in one of three states:Resident Set Management SystemWindows uses variable allocation, local scopeWhen activated, a process is assigned a data structure to manage its working setWorking sets of active processes are adjusted depending on the availability of main memorySummary
  • Desirable to:
  • maintain as many processes in main memory as possible
  • free programmers from size restrictions in program development
  • With virtual memory:
  • all address references are logical references that are translated at run time to real addresses
  • a process can be broken up into pieces
  • two approaches are paging and segmentation
  • management scheme requires both hardware and software support
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks