CS 162 Spring 2004 Lecture 13 1/15 CS 162 Operating Systems and Systems Programming Professor: Anthony D. Joseph Spring 2004 Lecture 13: Address Translation 13.0 Main Points Options for managing memory: • Paging • Segmentation • Multi-level translation • Paged page tables • Inverted page tables Comparison among options CS 162 Spring 2004 Lecture 13 2/15 13.1 Hardware Translation Overview CPUTranslation Box (MMU)Physical MemoryVirtual AddressPhysical AddressData read or write (untranslated) Think of memory in two ways: • View from the CPU – what program sees, virtual memory • View from memory – physical memory Translation implemented in hardware; controlled in software. There are many kinds of hardware translation schemes. Start with the simplest!CS 162 Spring 2004 Lecture 13 3/15 13.2 Base and Bounds Base and bounds: Each program loaded into contiguous regions of physical memory, but with protection between programs. First built in the Cray-1. virtual address+>baseboundsphysical addresserror Hardware Implementation of Base and Bounds Translation Program has illusion it is running on its own dedicated machine, with memory starting at 0 and going up to size = bounds. Like linker-loader, program gets contiguous region of memory. But unlike linker-loader, protection: program can only touch locations in physical memory between base and base + bounds. CS 162 Spring 2004 Lecture 13 4/15 codedatastackvirtual memory0boundphysical memory62506250 + bound Virtual and Physical Memory Views in Base and Bounds System Provides level of indirection: OS can move bits around behind the program’s back, for instance, if program needs to grow beyond its bounds, or if need to coalesce fragments of memory. Stop program, copy bits, change base and bounds registers, restart. Only the OS gets to change the base and bounds! Clearly, user program can’t, or else lose protection. With base&bounds system, what gets saved/restored on a context switch?CS 162 Spring 2004 Lecture 13 5/15 Hardware cost: • 2 registers • Adder • Comparator Plus, slows down hardware because need to take time to do add/compare on every memory reference. Base and bounds, Pros: + Simple, fast Cons: 1. Hard to share between programs For example, suppose two copies of “vi” • Want to share code • Want data and stack to be different Can’t do this with base and bounds! 2. Complex memory allocation First fit, best fit, buddy system. Particularly bad if want address space to grow dynamically (e.g., the heap). In worst case, have to shuffle large chunks of memory to fit new program. 3. Doesn’t allow heap, stack to grow dynamically – want to put these as far apart as possible in virtual memory, so that they can grow to whatever size is needed. 13.3 Segmentation A segment is a region of logically contiguous memory. Idea is to generalize base and bounds, by allowing a table of base&bound pairs. CS 162 Spring 2004 Lecture 13 6/15 virtual address+>physical addresserroroffsetvirt seg #seg ptrseg sizephys For example, what does it look like with this segment table, in virtual memory and physical memory? Assume a14 bit addresses divided up as: 2 bit segment ID, and a 12 bit segment offset. Virtual segment # Physical segment start Segment size 0 code 0x4000 0x700 1 data 0 0x500 2 - 0 0 3 stack 0x2000 0x1000CS 162 Spring 2004 Lecture 13 7/15 06ff100014ff30003fff04ff20002fff400046ffvirtual memoryphysical memory This should seem a bit strange: the virtual address space has gaps in it! Each segment gets mapped to contiguous locations in physical memory, but may be gaps between segments. But a correct program will never address gaps; if it does, trap to kernel and then core dump. Minor exception: stack, heap can grow. In UNIX, sbrk() increases size of heap segment. For stack, just take fault, system automatically increases size of stack. Detail: Need protection mode in segmentation table. For example, code segment would be read-only (only execution and loads are allowed). Data and stack segment would be read-write (stores allowed). What must be saved/restored on context switch? Typically, segment table stored in CPU, not in memory, because it’s small. CS 162 Spring 2004 Lecture 13 8/15 Example: What happens with the above segment table, with the following as virtual memory contents? Code does: strlen(x); Virtual memory Main: 240 store 1108, r2 244 store pc +8, r31 248 jump 360 24c … ... Strlen: 360 loadbyte (r2), r3 ... 420 jump (r31) ... x: 1108 a b c \0 ... Initially, pc = 240. Physical Memory x: 108 666 ... Main: 4240 store 1108, r2 4244 store pc +8, r31 4248 jump 360 424c … ... Strlen: 4360 loadbyte (r2), r3 ... 420 jump (r31) Segmentation Pros & Cons: + Efficient for sparse address spaces + Easy to share whole segments (for example, code segment) – Complex memory allocationCS 162 Spring 2004 Lecture 13 9/15 Still need first fit, best fit, etc., and re-shuffling to coalesce free fragments, if no single free space is big enough for a new segment. How do we make memory allocation simple and easy? 13.4 Paging Allocate physical memory in terms of fixed size chunks of memory, or pages. Simpler, because allows use of a bitmap. What’s a bitmap? 001111100000001100 Each bit represents one page of physical memory – 1 means allocated, 0 means unallocated. Lots simpler than base&bounds or segmentation Operating system controls mapping: any page of virtual memory can go anywhere in physical memory. virtual addressphysical addressoffsetphys page #offsetvirtual page #page tablepage table ptrpage table size>error Each address space has its own page table, in physical memory. Hardware needs two special registers – pointer to physical location of page table, and page table size. CS 162 Spring 2004 Lecture 13 10/15 Example: suppose page size is 4 bytes. a b c d e f g h i j k l 3 1 virtual memory physical memory i j k l e f g h 0 4 8 0xC 0x10 4 a b c d page table Where is virtual address 6? 9? Questions: 1. What must be saved and restored on a context switch? 2. What if page size is very small? For example, VAX had a page size of 512 bytes. 3. What if page size is really big? Why not use an infinite page size? Fragmentation: wasted space • External – free gaps between allocated chunks • Internal – free gaps
View Full Document
Unlocking...