CPS110: Landon Cox Page 1 of 24 Address spaces and memory management Review of processes Process = one or more threads in an address space Thread = stream of execution; unit of concurrency Address space = memory space that threads use; unit of data Address space abstraction Address space = all the memory data the process can use as it runs. Includes program code, stack, data segment Hardware interface (physical reality): one memory of small size, shared between processes Application interface (abstraction provided by OS): each process has its own memory, as large as the virtual address space Illusions provided by address spaces Address independence: same numeric address can be used in different address spaces (i.e. different processes), yet remain logically distinct Protection: one address space can’t access data in another address space (actually controlled sharing) Virtual memory: an address space can be larger than the amount of physical memory on the machines Uni-programming 1 process runs at a time (viz. one process occupies memory at a time) Always load process into the same spot in memory (and reserve some space for the OS) fffff (high memory) . . operating system . 80000 7ffff . . user process . 00000 (low memory) Achieves address independence by always loading process into same physical memory location Problems with uni-programming?CPS110: Landon Cox Page 2 of 24 Multi-programming and address translation Multi-programming: more than 1 process is in memory at a time Need to support address translation Need to support protection Must translate addresses issued by a process so they don’t conflict with addresses issues by other processes Static address translation: translate addresses before execution (translation remains constant during execution) Dynamic address translation: translate addresses during execution (translation may change during execution) Is it possible to run two processes at the same time (both are in memory) and provide address independence with only static address translation? Does this achieve the other address space abstractions? Achieving all the address space abstractions requires doing some work on every memory referenceCPS110: Landon Cox Page 3 of 24 Dynamic address translation Translate every memory reference from virtual address to physical address Virtual address: an address viewed by the user process (the abstraction provided by the OS) Physical address: an address viewed by the physical memory Translation enforces protection One process can’t even refer to another process’s address space Translation enables virtual memory A virtual address only needs to be in physical memory when it’s being accessed Change translations on the fly as different virtual addresses occupy physical memory Many ways to implement translator Does dynamic translation require hardware support? Address translation Lots of ways to implement the translator. Remember big picture: Tradeoffs: Flexibility (e.g. sharing, growth, virtual memory) Size of translation data Speed of translation User process Translator (MMU) Physical memory Virtual address Physical address User process Translator (MMU) Physical memory Virtual address Physical addressCPS110: Landon Cox Page 4 of 24 Base and bounds Load each process into contiguous regions of physical memory; prevent each process from accessing data outside its region if (virtual address > bound) { trap to kernel; kill process (core dump); } else { physical address = virtual address + base } Process has illusion of running on its own dedicated machine with memory [0, bound) This is similar to linker/loader, but also protects processes from each other. As with all translation data, only kernel can change base and bounds. During context switch, must change all translation data (base and bounds registers) What to do when an address space grows? Low hardware cost (2 registers, adder, comparator), low-overhead (add and compare on each memory reference) Bound 0 Virtual memory Physical memory Physical memory size Base + bound Base 0CPS110: Landon Cox Page 5 of 24 Hard for a single address space to be larger than physical memory But sum of all address spaces can be larger than physical memory Swap an entire address space out to disk, swap address space for new process in Can’t share part of an address space between processes External fragmentation Processes come and go, leaving a mishmash of available memory regions Process 1 start: 100KB (phys. mem. 0-99KB) Process 2 start: 200KB (phys. mem. 100-299KB) Process 3 start: 300KB (phys. mem. 300-599KB) Process 4 start: 400KB (phys. mem. 600-999KB) Process 3 exits (frees phys. mem. 300-599 KB) Process 5 start: 100KB (phys. mem. 300-399KB) Process 1 exits (frees phys. mem. 0-99KB) Process 6 start: 300KB 300KB are free (400-599KB; 0-99KB), but not contiguous This is called “external fragmentation”: wasted memory between allocated regions. Can waste lots of memory Allocation strategies to minimize external fragmentation Best fit: allocate the smallest memory region that can satisfy the request (least amount of wasted space) First fit: allocate the memory region that you find first that can satisfy the request In worst case, must re-allocate existing memory regions (by copying them to another area) Physical memory Virtual memory Data (p1) Data Data Code Code Code Data (p2) Virtual memory Virtual address (process 1) Virtual address (process 2)CPS110: Landon Cox Page 6 of 24 Hard to grow address space Might have to move to different region of physical memory (which is slow) How to extend more than one contiguous data structure in virtual memory? What parts of the address space might grow as the process runs?CPS110: Landon Cox Page 7 of 24 Segmentation Segment: a region of continuous memory Base and bounds used a single segment. Let’s generalize this to allow multiple segments, described by a table of base and bound pairs. Segment # Base Bound Description 0 4000 700 Code 1 0 500 Data 2 Unused 3 2000 1000 Stack In segmentation, a virtual address takes the form (Virtual segment #, offset) Could specify virtual segment # via the high bits of the address, or via a special register, or implicit to the