CS 162 Operating Systems and Systems Programming Professor Anthony D Joseph 13 1 Hardware Translation Overview Spring 2003 Virtual Address Lecture 13 Address Translation Translation Box MMU CPU 13 0 Main Points Physical Address Physical Memory Options for managing memory Paging Segmentation Multi level translation Paged page tables Inverted page tables Comparison among options Data 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 2003 Lecture 13 1 15 CS 162 Spring 2003 Lecture 13 2 15 13 2 Base and Bounds virtual memory physical memory 0 Base and bounds Each program loaded into contiguous regions of physical memory but with protection between programs First built in the Cray 1 error virtual address bound 6250 data bounds code base stack 6250 bound physical address Virtual and Physical Memory Views in Base and Bounds System 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 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 2003 Lecture 13 3 15 CS 162 Spring 2003 Lecture 13 4 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 error virtual address virt seg offset phys seg ptr physical address 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 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 seg size Physical segment start Segment size 0 code 0x4000 0x700 1 data 0 0x500 2 0 0 3 stack 0x2000 0x1000 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 2003 Lecture 13 5 15 CS 162 Spring 2003 Lecture 13 6 15 virtual memory Example What happens with the above segment table with the following as virtual memory contents Code does physical memory 0 0 6ff 4ff strlen x 1000 14ff Virtual memory Main 240 2000 2fff 3000 store 1108 r2 244 store pc 8 r31 248 jump 360 24c 3fff Strlen 360 loadbyte r2 r3 4000 420 jump r31 46ff x 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 1108 a b c 0 Initially pc 240 Physical Memory 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 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 allocation CS 162 Spring 2003 Lecture 13 7 15 CS 162 Spring 2003 Lecture 13 8 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 Example suppose page size is 4 bytes physical memory virtual memory a b c d 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 e f g h 0 4 4 3 1 8 page table i j k l 0xC e f g h 0x10 error virtual address virtual offset page 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 page table ptr page table offset Fragmentation wasted space External free gaps between allocated chunks Internal free gaps because don t need all of allocated chunk physical address 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 2003 Lecture 13 a b c d Where is virtual address 6 9 page table size phys page i j k l 9 15 With segmentation need to re shuffle segments to avoid external fragmentation Paging suffers from internal fragmentation CS 162 Spring 2003 Lecture 13 10 15 4 What if address space is sparse For example on UNIX code starts at 0 stack starts at 2 31 1 With 1KB pages 2 million page table entries virtual address virt seg Paging Pros Cons simple memory allocation easy to share big page tables if sparse address space virt page offset page table ptr table size page table Is there a solution that
View Full Document
Unlocking...