Virtual MemoryProcess ExecutionLocality and Virtual MemorySupport Needed for Virtual MemoryPagingSlide 6Page Table StructureAddress Translation in a Paging SystemSharing PagesPage Tables and Virtual MemoryMultilevel Page TablesSegmentationAddress Translation in a Segmentation SystemSegmentation: commentsSharing in Segmentation SystemsCombined Segmentation and PagingAddress Translation in a (simple) combined Segmentation/Paging SystemSimple Combined Segmentation and PagingOperating System SoftwareFetch PolicyPlacement policyReplacement PolicySlide 23Slide 24Basic algorithms for the replacement policyThe LRU PolicyNote on counting page faultsImplementation of the LRU PolicyThe FIFO PolicyComparison of FIFO with LRUThe Clock PolicyThe Clock Policy: an exampleComparison of Clock with FIFO and LRUSlide 34Page BufferingSlide 36Cleaning PolicySlide 38Resident Set SizeSlide 40Replacement ScopeFixed allocation + Local scopeFixed allocation + Global scopeVariable allocation + Global scopeVariable allocation + Local scopeThe Working Set StrategyThe Working Set StrategySlide 48Slide 49The Page-Fault Frequency StrategyLoad ControlSlide 52Process Suspension1Virtual MemoryVirtual MemoryChapter 8Chapter 82Process ExecutionProcess ExecutionThe OS brings into main memory only a few pieces of the program (including its starting point)Each page/segment table entry has a present bit that is set only if the corresponding piece is in main memoryThe resident set is the portion of the process that is in main memoryAn interrupt (memory fault) is generated when the memory reference is on a piece not present in main memory3Locality and Virtual MemoryLocality and Virtual MemoryPrinciple of locality of references: memory references within a process tend to clusterHence: only a few pieces of a process will be needed over a short period of timePossible to make intelligent guesses about which pieces will be needed in the futureThis suggests that virtual memory may work efficiently (ie: trashing should not occur too often)4Support Needed forSupport Needed forVirtual MemoryVirtual MemoryMemory management hardware must support paging and/or segmentation OS must be able to manage the movement of pages and/or segments between secondary memory and main memoryWe will first discuss the hardware aspects; then the algorithms used by the OS5PagingPagingEach page table entry contains a present bit to indicate whether the page is in main memory or not.If it is in main memory, the entry contains the frame number of the corresponding page in main memoryIf it is not in main memory, the entry may contain the address of that page on disk or the page number may be used to index another table (often in the PCB) to obtain the address of that page on diskTypically, each process has its own page table6PagingPagingA modified bit indicates if the page has been altered since it was last loaded into main memoryIf no change has been made, the page does not have to be written to the disk when it needs to be swapped outOther control bits may be present if protection is managed at the page level a read-only/read-write bit protection level bit: kernel page or user page (more bits are used when the processor supports more than 2 protection levels)7Page Table StructurePage Table StructurePage tables are variable in length (depends on process size)then must be in main memory instead of registersA single register holds the starting physical address of the page table of the currently running process8Address Translation in a Paging SystemAddress Translation in a Paging System9Sharing PagesSharing PagesIf we share the same code among different users, it is sufficient to keep only one copy in main memoryShared code must be reentrant (ie: non self-modifying) so that 2 or more processes can execute the same codeIf we use paging, each sharing process will have a page table who’s entry points to the same frames: only one copy is in main memoryBut each user needs to have its own private data pages10Page Tables and Virtual MemoryPage Tables and Virtual MemoryMost computer systems support a very large virtual address space32 to 64 bits are used for logical addressesIf (only) 32 bits are used with 4KB pages, a page table may have 2^{20} entriesThe entire page table may take up too much main memory. Hence, page tables are often also stored in virtual memory and subjected to paging When a process is running, part of its page table must be in main memory (including the page table entry of the currently executing page)11Multilevel Page TablesMultilevel Page TablesSince a page table will generally require several pages to be stored. One solution is to organize page tables into a multilevel hierarchy When 2 levels are used (ex: 386, Pentium), the page number is split into two numbers p1 and p2p1 indexes the outer paged table (directory) in main memory who’s entries points to a page containing page table entries which is itself indexed by p2. Page tables, other than the directory, are swapped in and out as needed12SegmentationSegmentationTypically, each process has its own segment tableSimilarly to paging, each segment table entry contains a present bit and a modified bitIf the segment is in main memory, the entry contains the starting address and the length of that segmentOther control bits may be present if protection and sharing is managed at the segment levelLogical to physical address translation is similar to paging except that the offset is added to the starting address (instead of being appended)13Address Translation in a Address Translation in a Segmentation SystemSegmentation System14Segmentation: commentsSegmentation: commentsIn each segment table entry we have both the starting address and length of the segmentthe segment can thus dynamically grow or shrink as neededaddress validity easily checked with the length fieldBut variable length segments introduce external fragmentation and are more difficult to swap in and out...It is natural to provide protection and sharing at the segment level since segments are visible to the programmer (pages are not)Useful protection bits in segment table entry:read-only/read-write bit Supervisor/User bit15Sharing in Segmentation SystemsSharing in Segmentation SystemsSegments are shared when entries in the segment tables of 2 different processes point to the same
View Full Document
Unlocking...