MulticsMulticsand More VMand More VMMultics Multics (1965(1965--2000)2000)• “Multiplexed 24x7 computer utility”Multi-user “time-sharing”, interactive and batchProcesses, privacy, security, sharing, accounting“Decentralized system programming”• Virtual memory with “automatic page turning”• “Two-dimensional VM” with segmentationAvoids “complicated overlay techniques”Modular sharing and dynamic linking• Hierarchical file system with symbolic names, automatic backup“Single-level store”• Dawn of “systems research” as an academic enterpriseMultics Multics ConceptsConcepts• Segments as granularity of sharingProtection rings and the segment protection level• Segments have symbolic names in a hierarchical name space• Segments are “made known” before access from a process.Apply access control at this point.• Segmentation is a cheap way to extend the address space.How does it affect page table structure?Is it really a fundamental improvement over flat VAS?Paging mechanisms are independent of segmentation.• Dynamic linking resolves references across segments.How does the Unix philosophy differ?Segmentation (1)Segmentation (1)One-dimensional address spacegrowing tablestables may bump[Tanenbaum]Segmentation (2)Segmentation (2)Allows each table to grow or shrink, independently[Tanenbaum]Segmentation with Paging: MULTICS (1)Segmentation with Paging: MULTICS (1)Descriptor segment points to page tablesSegment descriptor – numbers are field lengthsSegmentation with Paging: MULTICS (2)Segmentation with Paging: MULTICS (2)A 34-bit MULTICS virtual addressSegmentation with Paging: MULTICS (3)Segmentation with Paging: MULTICS (3)Conversion of a 2-part MULTICS address into a main memory address[Tanenbaum]Segmentation with Paging: MULTICS (4)Segmentation with Paging: MULTICS (4)Simplified version of the MULTICS TLBMapped FilesMapped FilesWith appropriate support, virtual memory is a useful basis for accessing file storage.• Bind file to a region of virtual memory with mmap syscall.e.g., start address xvirtual address x+n maps to offset n of the file• Offers several advantages over stream file access.uniform access for files and memory (just use pointers)performance: zero-copy reads and writes for low-overhead I/Obut: program has less control over data movementstyle does not generalize to pipes, sockets, terminal I/O, etc.• Sometimes called single-level store or virtual storage.Using File Mapping to Build a VASUsing File Mapping to Build a VASsectionstextdataidatawdataheadersymboltablerelocationrecordstextdataidatawdataheadersymboltablerelocationrecordsBSSuser stackargs/envkernel u-areatextdatatextdataexecutableimagelibrary (DLL)loadersegmentsMemory-mapped files are used internallyfor demand-paged text and initialized static data.BSS and user stack are“anonymous” segments.1. no name outside the process2. not sharable3. destroyed on process exitVM Internals: Mach/BSD ExampleVM Internals: Mach/BSD Examplestart, len,protstart, len,protstart, len,protstart, len,protaddressspace (task)vm_maplookupenterpmappage tablesystem-widephys-virtual mappmap_enter()pmap_remove()pmap_page_protectpmap_clear_modifypmap_is_modifiedpmap_is_referencedpmap_clear_referenceputpagegetpagememoryobjectsOne pmap (physical map)per virtual address space.page cells (vm_page_t)array indexed by PFNMemory ObjectsMemory ObjectsMemory objects “virtualize” VM backing storage policy.• source and sink for pagestriggered by faults...or OS eviction policy• manage their own storage• external pager has some control:prefetchprewriteprotect/enable• can be shared via vm_map()(Mach extended mmap syscall)anonymous VMobject->putpage(page)object->getpage(offset, page, mode)memory objectswappagervnodepagerexternpagermapped files DSMdatabasesreliable VMetc.Memory/Storage Hierarchy 101Memory/Storage Hierarchy 101P$MemoryVery fast 1ns clockMultiple Instructionsper cycleSRAM, Fast, SmallExpensive (cache, registers)DRAM, Slow, Big,Cheaper(called physical or main)$1000-$2000 per GB or so=> Cost Effective Memory System (Price/Performance)Magnetic, Rotational,Really Slow Seeks,Really Big, Really Cheap($2-$10 to $200 per GB)“CPU-DRAM gap”memory system architecture“I/O bottleneck”VM and file cachingvolatilenonvolatileI/O Caching 101I/O Caching 101Data items from secondary storage are cached in memory for faster access time.HASH(object)free/inactive list tailhashfunctionfree/inactivelist headhashbucketarrayhashchainsmethods:object = get(tag)Locate object if in the cache, else finda free slot and bring it into the cache.release(object)Release cached object so its slot maybe reused for some other object.I/O cache: a hash table with an integrated free/inactive list (i.e., an ordered list of eviction candidates).Rationale for I/O Cache StructureRationale for I/O Cache StructureGoal: maintain K slots in memory as a cache over a collection of m items on secondary storage (K << m).1. What happens on the first access to each item?Fetch it into some slot of the cache, use it, and leave it there to speed up access if it is needed again later.2. How to determine if an item is resident in the cache?Maintain a directory of items in the cache: a hash table.Hash on a unique identifier (tag) for the item (fully associative).3. How to find a slot for an item fetched into the cache?Choose an unused slot, or select an item to replace according tosome policy, and evict it from the cache, freeing its slot.Mechanism for Cache Eviction/ReplacementMechanism for Cache Eviction/ReplacementTypical approach: maintain an ordered free/inactive list of slots that are candidates for reuse.• Busy items in active use are not on the list.E.g., some in-memory data structure holds a pointer to the item.E.g., an I/O operation is in progress on the item.• The best candidates are slots that do not contain valid items.Initially all slots are free, and they may become free again as items are destroyed (e.g., as files are removed).• Other slots are listed in order of value of the items they contain.These slots contain items that are valid but inactive: they are held in memory only in the hope that they will be accessed again later.Replacement PolicyReplacement PolicyThe effectiveness of a cache is determined largely by the policy for ordering slots/items on the free/inactive list.defines the replacement policyA typical cache replacement policy is Least Recently Used.• Assume hot items used recently are likely to