Virtual Memory ManagementIntroductionTopics for discussionMemory management requirementsMemory management requirements (contd.)...requirements(contd.)Memory management techniques (Covered last class)Memory management techniques (contd.)Basic memory operation: RelocationDemand Paging and Virtual MemoryLocalityDesirable memory characteristicsDemand pagingVirtual Page Number and OffsetPage Size CriteriaDemand paging (contd.)Demand Paging (contd.)Issues in demand pagingIssues in demand paging (contd.)Page mapping and Page TablePage tableAddress translationExamplePage fault handlerPage Fault Handling (1)Page Fault Handling (2)Translation look-aside bufferTLBs – Translation Lookaside BuffersPage Size (1)Page Size (2)Resident Set ManagementResident Set Management (contd.)Load controlLoad Control GraphLoad control (contd.)Page Replacement AlgorithmsOptimal Page Replacement AlgorithmNot Recently Used Page Replacement AlgorithmFIFO Page Replacement AlgorithmThe Clock Page Replacement AlgorithmLeast Recently Used (LRU)Simulating LRU in Software (1)Simulating LRU in Software (2)Modeling Page Replacement Algorithms Belady's AnomalyTwo Level Page TablesBacking Store01/13/19 1Virtual Memory ManagementB.Ramamurthy01/13/19 2IntroductionMemory refers to storage needed by the kernel, the other components of the operating system and the user programs. In a multi-processing, multi-user system, the structure of the memory is quite complex. Efficient memory management is very critical for good performance of the entire system. In this discussion we will study memory management policies, techniques and their implementations.01/13/19 3Topics for discussionMemory management requirementsMemory management techniquesMemory operation of relocationVirtual memory Principle of localityDemand PagingPage replacement policies01/13/19 4Memory management requirementsRelocation: Branch addresses and data references within a program memory space (user address space) have to be translated into references in the memory range a program is loaded into.Protection: Each process should be protected against unwanted (unauthorized) interference by other processes, whether accidental or intentional. Fortunately, mechanisms that support relocation also form the base for satisfying protection requirements.01/13/19 5Memory management requirements (contd.)Sharing : Allow several processes to access the same portion of main memory : very common in many applications. Ex. many server-threads executing the same service routine.Logical organization : allow separate compilation and run-time resolution of references. To provide different access privileges (RWX). To allow sharing. Ex: segmentation.01/13/19 6...requirements(contd.)Physical organization: Memory hierarchy or level of memory. Organization of each of these levels and movement and address translation among the various levels.Overhead : should be low. System should be spending not much time compared execution time, on the memory management techniques.01/13/19 7Memory management techniques (Covered last class)Fixed partitioning: Main memory statically divided into fixed-sized partitions: could be equal-sized or unequal-sized. Simple to implement. Inefficient use of memory and results in internal-fragmentation.Dynamic partitioning : Partitions are dynamically created. Compaction needed to counter external fragmentation. Inefficient use of processor.Simple paging: Both main memory and process space are divided into number of equal-sized frames. A process may in non-contiguous main memory pages.01/13/19 8Memory management techniques (contd.)Simple segmentation : To accommodate dynamically growing partitions: Compiler tables, for example. No fragmentation, but needs compaction.Virtual memory with paging: Same as simple paging but the pages currently needed are in the main memory. Known as demand paging.Virtual memory with segmentation: Same as simple segmentation but only those segments needed are in the main memory.Segmented-paged virtual memory01/13/19 9Basic memory operation: RelocationA process in the memory includes instructions plus data. Instruction contain memory references: Addresses of data items, addresses of instructions. These are logical addresses: relative addresses are examples of this. These are addresses which are expressed with reference to some known point, usually the beginning of the program.Physical addresses are absolute addresses in the memory. Relative addressing or position independence helps easy relocation of programs.01/13/19 10Demand Paging and Virtual MemoryConsider a typical, large program you have written: There are many components that are mutually exclusive. Example: A unique function selected dependent on user choice.Error routines and exception handlers are very rarely used.Most programs exhibit a slowly changing locality of reference. There are two types of locality: spatial and temporal.01/13/19 11LocalityTemporal locality: Addresses that are referenced at some time Ts will be accessed in the near future (Ts + delta_time) with high probability. Example : Execution in a loop.Spatial locality: Items whose addresses are near one another tend to be referenced close together in time. Example: Accessing array elements.How can we exploit this characteristics of programs? Keep only the current locality in the main memory. Need not keep the entire program in the main memory. (Virtual Memory concept)01/13/19 12Desirable memory characteristicsStorage capacityAccess timeCPUcacheMain memorySecondary StorageCost/byteDesirable increasing01/13/19 13Demand pagingMain memory (physical address space) as well as user address space (virtual address space) are logically partitioned into equal chunks known as pages. Main memory pages (sometimes known as frames) and virtual memory pages are of the same size.Virtual address (VA) is viewed as a pair (virtual page number, offset within the page). Example: Consider a virtual space of 16K , with 2K page size and an address 3045. What the virtual page number and offset corresponding to this VA?01/13/19 14Virtual Page Number and Offset3045 / 2048 = 13045 % 2048 = 3045 - 2048 = 997VP# = 1Offset within page = 997Page Size is always a power of 2? Why?01/13/19 15Page Size CriteriaConsider the binary value of address 3045 : 1011 1110 0101for 16K address space the address will be 14 bits. Rewrite:00 1011 1110 0101A 2K address space will have offset range 0 -2047 (11 bits)00 1 011 1110
View Full Document
Unlocking...