1Outline• Objectives– Review of undergrad material w.r.t. memory management– Linux details from ch 10,13 sprinkled along the way• Administrative details– Upcoming midterm (next Monday)Review of Memory Management• The traditional memory hierarchy,the virtual memory abstraction.• Hardware and software mechanisms to support the abstraction.• Management policies.• Where are the opportunities for current research?The underlying assumptions that are changing.23Issues• Exactly what kind of object is it that we need to load into memory for each process?What is an address space?• Multiprogramming was justified on the grounds of CPU utilization (CPU/IO overlap). How is the memory resource to be shared among all those processes we’ve created?• What is the memory hierarchy? What is the OS’s role in managing levels of it?4More Issues• How can one address space be protected from operations performed by other processes?• In the implementation of memory management, what kinds of overheads (of time, of wasted space, of the need for extra hardware support) are introduced?How can we fix (or hide) some of these problems?35Memory Hierarchyfunc unitsregistersProcessor$$cache(s)Main Memory*Secondary Storage*DiskRemotememories*not to scaleAirplane analogy:Seat back pocket-limited size andgranularity, immediate accessOverhead bins-bigger, not as convenientCheckedbaggage-big butlimitedaccess“CPU-DRAM gap” (CPS 104) “I/O bottleneck”6From User Program to ExecutableThe executable file resulting from compiling your source code and linking with other compiled modules contains– machine language instructions (as if addresses started at zero)– initialized data– how much space is required for uninitialized dataprog.ccompilerprog.olibclinkerprog47Executable to User Address Space• In addition to the code and initialized data that can be copied from executable file, addresses must be reserved for areas of uninitialized data and stack when the process is created• When and how do the realphysical addresses get assigned?codeinit dataheaderlogical addr space0:0:N-1:stackuninit datalw r2, 42jmp 6symbol tableKernelLinux View of Memory• Physical memory• Kernel memory -- v.m. visible from kernel mode–ZONE_DMA– ZONE_NORMAL1-to-1 mapped– ZONE_HIGHMEMexplicitly mapped into address space• User memory – visible from user mode– ZONE_HIGHMEM0GB3GB4GBlow.9GBUserremappablevirtualphysicalhigh5Allocation Mechanisms• Acquiring regions of physical memory and mapping them (implicitly or explicitly) into the virtual address space• Kernel allocators– Page grained – alloc_pages and get_zeroed_pagekmap into kernel address space– Sub-page-size – rtn logical addresses• kmalloc – physical contiguous chunks• vmalloc – virtually contiguousSlab Allocator• Creates cache of pre-allocated and recycled data structures. Essentially free-lists of various kinds• kmem_cache_alloc – gets an object of the appropriate type from the cache– Inodes, task_structs, etc.611Allocation to Physical Memoryaddr space0addr space10:0:A0-1:Main Memory0:M-1:A1-1:lw r2, 42jmp 6*binary rep ofAssume contiguous allocationStatic loading Partition memory variable (first, best fits)Fragmentation (external)CompactionSwapping12lw r2, 42+Njmp 6+NAllocation to Physical Memoryaddr space0addr space10:0:A0-1:Main Memory0:M-1:A1-1:lw r2, 42jmp 6*binary rep ofAssume contiguous allocationStatic loading Partition memory variable (first, best fits)Fragmentation (external)CompactionSwappingN:free713lw r2, 42+Kjmp 6+KAllocation to Physical Memoryaddr space0addr space10:0:A0-1:Main Memory0:M-1:A1-1:lw r2, 42jmp 6*binary rep ofAssume contiguous allocationStatic loadingPartition memory variable (first, best fits)Fragmentation (external)CompactionSwappingK:free14Pagingvirtual addr space0virtual addr space10:0:A0-1:A1-1:Non-contiguousallocation - fixed size pagesframePhysical Memorypage815PagingDynamic address translation – another case of indirection (as “the answer”)– TLB to speed up lookup (another case of caching as “the answer”)VPN offset29 013addresstranslationPFNoffset+00virtual addressphysical address{Deliver exception toOS if translation is notvalid and accessible inrequested mode.Virtual Memory• System-controlled movement up and down in the memory hierarchy.• Can be viewed as automating overlays - the system attempts to dynamically determine which previously loaded parts can be replaced by parts needed now.• It works only because of locality of reference.• Often most closely associated with paging (needs non-contiguous allocation, mapping table).9Locality• Only a subset of the program’s code and data are needed at any point in time. Can the OS predict what that subset will be (from observing only the past behavior of the program)?• Temporal - Reuse. Tendency to reuse stuff accessed in recent history (code loops).• Spatial - Tendency to use stuff near other recently accessed stuff (straightline code, data arrays). Justification for moving in larger chunks.2/22/2005 18Good & Bad Locality for (i = 0; i++; i<n)for (j = 0; j++; j<m)A[i, j] = B[i, j] for (j = 0; j++; j<m)for (i = 0; i++; i<n)A[i, j] = B[i, j] A[0,0]A[0,1]A[1,0]A[2,0]A[2,1]A[1,1]A[0,0] A[0,1]A[1,0]A[1,1]A[2,0]A[2,1]Assume:arrays laidout in rowsBad locality is a contributing factor in Thrashing(page faulting behavior dominates).10Thrashing• Page faulting is dominating performance• Causes:– Memory is overcommited - not enough to hold locality sets of all processes at this level of multiprogramming– Lousy locality of their programs– Positive feedback loops reacting to paging I/O rates#framespage fault freq.1N• Load control is important (how many slices in frame pie?)–LT/RT strategy (limit # processes in load phase)enough framestoo fewframesdifferencebetween repl. algsQuestions for Paged Virtual Memory1. How do we prevent users from accessing protected data?2. If a page is in memory, how do we find it?Address translation must be fast.3. If a page is not in memory, how do we find it?4. When is a page brought into memory?5. If a page is brought into memory, where do we put it?6. If a page is evicted from memory, where do we put it?7. How do we decide which pages to evict from memory?Page replacement policy should minimize overall I/O.112/22/2005 21Virtual Memory Mechanisms• Hardware support - beyond dynamic address translation needed to support paging or segmentation (e.g., table lookup)–