Memory ManagementIntroductionTopics for discussionMemory (No abstraction)The notion of address spaceSwappingSchematic View of SwappingContiguous AllocationBasic memory operation: RelocationHardware Support for Relocation and Limit RegistersContiguous Allocation (Cont.)Dynamic Storage-Allocation ProblemFragmentationMemory management requirementsMemory management requirements (contd.)...requirements(contd.)Memory management techniques (Covered last class)Memory management techniques (contd.)Demand Paging and Virtual MemoryLocalityDesirable memory characteristicsPagingDemand pagingVirtual Page Number and OffsetPage Size CriteriaDemand paging (contd.)Demand Paging (contd.)Issues in demand pagingIssues in demand paging (contd.)Page mapping and Page TableSlide 31Page 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/14/19Page 1 Memory ManagementB.Ramamurthy01/14/19Page 2Introduction•Memory 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/14/19Page 3Topics for discussion•Memory Abstraction and concept of address space•Memory management requirements•Memory management techniques•Memory operation of relocation•Virtual memory •Principle of locality•Demand Paging•Page replacement policies01/14/19Page 4Memory (No abstraction)User programOS in RAMUser programOS in ROMUser programDeviceDrivers ROMOS in RAM01/14/19Page 5The notion of address space•An address space is set of addresses that a process can use to address memory.•Each process has its own address space defined by base register and limit register.•Swapping is a simple method for managing memory in the context of multiprogramming.01/14/19Page 6Swapping•A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution.•Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images.•Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed.01/14/19Page 7Schematic View of Swapping01/14/19Page 8Contiguous Allocation•Main memory usually into two partitions:–Resident operating system, usually held in low memory with interrupt vector.–User processes then held in high memory.•Single-partition allocation–Relocation-register scheme used to protect user processes from each other, and from changing operating-system code and data.–Relocation register contains value of smallest physical address; limit register contains range of logical addresses – each logical address must be less than the limit register.01/14/19Page 9Basic memory operation: Relocation•A 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/14/19Page 10Hardware Support for Relocation and Limit Registers01/14/19Page 11Contiguous Allocation (Cont.)•Multiple-partition allocation–Hole – block of available memory; holes of various size are scattered throughout memory.–When a process arrives, it is allocated memory from a hole large enough to accommodate it.–Operating system maintains information about:a) allocated partitions b) free partitions (hole)OSprocess 5process 8process 2OSprocess 5process 2OSprocess 5process 2OSprocess 5process 9process 2process 9process 1001/14/19Page 12Dynamic Storage-Allocation Problem•First-fit: Allocate the first hole that is big enough.•Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. Produces the smallest leftover hole.•Worst-fit: Allocate the largest hole; must also search entire list. Produces the largest leftover hole.How to satisfy a request of size n from a list of free holes.First-fit and best-fit better than worst-fit in terms of speed and storage utilization.01/14/19Page 13Fragmentation•External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous.•Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used.•Reduce external fragmentation by compaction–Shuffle memory contents to place all free memory together in one large block.–Compaction is possible only if relocation is dynamic, and is done at execution time.–I/O problem•Latch job in memory while it is involved in I/O.•Do I/O only into OS buffers.01/14/19Page 14Memory management requirements•Relocation: 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/14/19Page 15Memory management requirements (contd.)•Sharing : Allow several processes to access the same portion of main memory : very common in many applications. Ex. many server-threads
View Full Document
Unlocking...