11CMSC 412Memory Management:Paging and Virtual MemoryAnnouncements• Reading:– Today: Chapter 9.2-9.4– Next time: Chapter 9.5-9.6, 1022Logical vs. Physical Addresses• The concept of a logical address spacethat is bound to a separate physicaladdress space is central to propermemory management.– Logical address – generated by the CPU;also referred to as virtual address.– Physical address – address seen by thememory unit.• Just as in Project 2.Basic Relocation Hardware33Swapping• Main memory is big, but what if we run out?• A process can be swapped temporarily outof memory to a backing store, and thenbrought back into memory for continuedexecution.– Backing store (disk) bigger than main memory• Major part of swap time is transfer time;total transfer time is directly proportionalto the amount of memory swapped.– But disk is slower than main memory• Swapping used on UNIX, Linux, Windows, …Schematic View of Swapping44Contiguous Allocation• Main memory usually into twopartitions:– Resident operating system, usually heldin low memory with interrupt vector.– User processes then held in high memory.• Single-partition allocation– Subdivide user-space into fixed-sizechunks of memory. Each process gets afull chunk.• What if the process doesn’t need that much?• What if it needs more?Contiguous Allocation• Multiple-partition allocation– Hole – block of available memory; holes ofvarious size are scattered throughout memory.– When a process arrives, it is allocated memoryfrom 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 1055Dynamic Storage-AllocationProblem• How to satisfy a request of size n froma list of free holes?• Goal: efficient utilization of storage.– If we have n processes that require mbytes of memory where m < n, we can fitall processes in memory at once.• Goal: fast allocation times.– The time to find a hole of necessary sizeDynamic Storage-AllocationProblem• First-fit: Allocate the first hole that is bigenough.• Best-fit: Allocate the smallest hole that isbig enough; must search entire list, unlessordered by size. Produces the smallestleftover hole.• Worst-fit: Allocate the largest hole; mustalso search entire list. Produces the largestleftover hole.• First-fit and best-fit better than worst-fit interms of speed and storage utilization.66Fragmentation• External Fragmentation – totalmemory space exists to satisfy arequest, but it is not contiguous.• Internal Fragmentation – allocatedmemory may be slightly larger thanrequested memory; this sizedifference is memory internal to apartition, but not being used.Reducing Fragmentation• Compaction– Shuffle memory contents to place all freememory together in one large block.• Compaction is possible only if usingrelocatable logical addresses.• I/O problem– Pin job in memory while it is doing I/O.– Or, do I/O only into OS buffers.77Non-Contiguous Allocation• Can eliminate external fragmentationand improve storage utilization byallowing process memory to be non-contiguous.– Break the process memory into differentchunks and allocate chunks in differentparts of physical memory.• Could you do this using the schemeyou have implemented for GeekOS sofar?Paging• Divide physical memory into fixedsized chunks called frames (pages),logical memory into same-sized pages– typical frames are 512 bytes to 64 Kbytes– When a process is to be executed, loadthe pages that are needed into memory.• Have a map from pages to frames– Called the page table.88Address Translation Scheme• Address generated by CPU is divided into:– Page number (p) – used as an index into the pagetable, which contains base address of each pagein physical memory.– Page offset (d) – combined with base address todefine the physical memory address that is sentto the memory unit.• Consider 32-bit addresses on Pentium:– 4096-byte pages (12 bits for the offset)– 20 bits for the page numberAddress Translation99Paging ExampleFree FramesBefore allocationAfter allocation1010Paging Fragmentation• If we have 4K pages, and a processrequires 15K of memory, how manypages will we need?• Suffer from internal fragmentation:last page likely not completely used– On average 50% of a page lost per processto internal fragmentation• How does this impact our choice ofpage size?Implementation of Page Table• Page table is kept in main memory.• Page-table base register (PTBR) pointsto the page table.1111Memory Protection• Memory protection by associatingprotection bit with each frame.• Valid-invalid bit attached to eachentry in the page table:– “valid” indicates that the associated pageis in the process’ logical address space,and is thus a legal page.– “invalid” indicates that the page is not inthe process’ logical address space.Valid/Invalid Bit Example1212Problem: Page Table Size• One page table can get very big– 220 entries (for most programs, mostitems are empty)• Simple Solution– Page-table length register (PRLR)indicates size of the page table.• But not as good for “sparse” addressspacesHierarchical Page Tables• Break up the logical address spaceinto multiple page tables.• Simplest case: a two-level page table.– Used on the Pentium. The outer table iscalled the page directory, which points toindividual page tables. Each page table isitself a page.1313Two-Level Paging Example• A logical address (on 32-bit machinewith 4K page size) is divided into:– a page number consisting of 20 bits.– a page offset consisting of 12 bits.• Since the page table is paged, thepage number is further divided into:– a 10-bit page number.– a 10-bit page offset.Two-Level Paging Example• Thus, a logical address is as follows:where p1 is an index into the outerpage table, and p2 is the displacementwithin the page of the outer pagetable.page numberpage offsetpip2d10 10 121414Address-Translation Scheme• Address-translation scheme for a two-level 32-bitpaging architectureProblem: Still too big?• What about 64 bit address spaces?• Two-level page table:– Page num: 52 bits, or 252 entries in pagedirectory!• More levels of hierarchy?– Further subdivide the page number.• 32-bit SPARC: three-level scheme.• 32-bit 68030: four-level
View Full Document
Unlocking...