OutlineReview of Memory ManagementIssuesMore IssuesMemory HierarchyFrom User Program to ExecutableExecutable to User Address SpaceLinux View of MemoryAllocation MechanismsSlab AllocatorAllocation to Physical MemorySlide 12Slide 13PagingSlide 15Virtual MemoryLocalityGood & Bad LocalityThrashingQuestions for Paged Virtual MemoryVirtual Memory MechanismsRole of MMU Hardware and OSSlide 23Slide 24Alpha Page Tables (Forward Mapped)A Page Table Entry (PTE)Inverted Page Table (HP, IBM)Linux Page TableMemory Management Unit (MMU)The OS Directs the MMUThe Translation Lookaside Buffer (TLB)Care and Feeding of TLBsHardware Managed TLBsSoftware Managed TLBsWhere Pages Come FromSlide 36Slide 37PowerPoint PresentationSlide 39Slide 40Slide 42Policies for Paged Virtual MemoryFetch Policy: Demand PagingPrefetching IssuesPlacement PolicyPage Replacement PolicyThe Page Caching Problem (aka Replacement Policy)Replacement AlgorithmsLRULRU Approximations for PagingClock AlgorithmPractical ConsiderationsThe Paging DaemonFIFO with Second Chance (Mach)Illustrating FIFO-2CVariable / Global AlgorithmsVariable Space AlgorithmsBacking Store = DiskRotational MediaA Case for Large PagesA Case for Small PagesMMU GamesSlide 69Simulating Usage BitsCopy-on-WriteThings ChangeDistributed Shared Memory (DSM)DSM IssuesDSM StatesConsistency ModelsExample - the ProblemExample - Sequential ConsistencyExample - Weaker ConsistencyOutline•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.3Issues•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?5Memory 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 Executable The 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.olibc linkerprog7Executable 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 real physical addresses get assigned?codeinit dataheader logical 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.9GBUserremappablevirtualphysicalhighAllocation 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.11Allocation 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:free13lw 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 Memorypage15PagingDynamic address translation –another case of indirection (as “the answer”)–TLB to speed up lookup (another case of caching as “the answer”)VPN offset29013addresstranslationPFNoffset+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).Locality•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.01/14/19 18Good & Bad Locality for (i = 0; i++; i<n)for (j = 0;