Why am I lecturing about Multics? Origin of many ideas in today's OSes Motivated UNIX design (often in opposition) Motivated x86 VM design This lecture is really "how Intel intended x86 segments to be used" Multics background design started in 1965 very few interactive time-shared systems then: CTSS system stable by 1969 about when UNIX got started, by ex-Multics hackers unwieldy: ambitious, many years, many programmers, MIT+GE+BTL Multics high-level goals many users on same machine: "time sharing" remote terminal access (but no recognizable data networks: wired or phone) persistent reliable file system maximize sharing of data where permissible (is this about saving core? or about user interaction?) control access to data Most interesting aspect of design: memory system idea: eliminate memory / file distinction file i/o uses LD / ST instructions no difference between memory and disk files just jump to start of file to run program enhances sharing: no more copying files to private memory this seems like a really neat simplification! GE 645 physical memory system 24-bit phys addresses 36-bit words so up to 75 megabytes of physical memory!!! but no-one could afford more than about a megabyte 645 segments descriptor base register (DBR) holds phy addr of descriptor segment (DS) DS is an arry of segment descriptor words (SDW) SDW: phys addr, length, r/w/x, present CPU has pairs of registers: 18 bit offset, 18 bit segment # five pairs (PC, arguments, base, linkage, stack) early Multics limited each segment to 2^16 words thus there are lots of them, intended to correspond to program modules note: cannot directly address phys mem (18 vs 24) 645 segments are a lot like the x86! 645 paging DBR and SDW actually contain phy addr of 64-entry page table each page is 1024 words PTE holds phys addr and present flag no permission bits, so you really need to use the segments, not like JOS no unified page table! actually a good idea, assuming shared segments don't need to laboriously swap cr3 on context switch Multics processes each process has its own DS Multics switches DBR on context switch we'd like processes to share segments for same instructions or files how to use segments to unify memory and file system? don't want to have to use 18-bit numbers as global identifiers we want to write programs using symbolic names names should be hierarchical (for users) directories, to make segments make sense as a file system Multics file system tree structure, directories and files each file and directory is a segment dir seg holds array of "branches" name, length, ACL, array of block #s, "active" unique ROOT directory path names: ROOT > A > B note there are no inodes, thus no i-numbers so "real name" for a file is the complete path name a bit awkward in the implementation compared to i-numbers no hard links but can always reconstruct path name from segment (this doesn't always work for UNIX FDs or i-nodes) what happens when a program makes a memory reference? program running in segment B calls A$E -- that is, call function named E in segment named A when compiling B: compiler actually generates *two* segments one holds B's instructions one holds B's linkage information CALL instruction is indirect through entry i of linkage segment compiler marks entry i invalid compiler also makes table in B, index i says "A" and "E" when executing B: process refers to "real" B and a per-process copy of B's linkage information call A$E (really call indirect via linkage[i]) faults because linkage[i] is invalid o/s dynamic linker: looks up segment name for i ("A") search path in file system for segment "A" (cwd, library dirs) allocate page table and pages read segment A into memory find free SDW j in process DS, make it refer to A's page table set up r/w/x based on process's user and file ACL search A's symbol table for "E" linkage[i] := j / address(E) restart B now the CALL works via linkage[i] and subsequent calls are fast all memory / file references work this way as if pointers were really symbolic names pointer to memory (segment #) is really a transparent optimization filesystem / segment implications programs start slowly due to dynamic linking creat(), unlink(), &c are outside of this model store beyond end extends a segment (== appends to a file) no need for buffer cache! no need to copy into user space! when are dirty segments written back to disk? only in page eviction algorithm, when free pages are low database careful ordered writes? e.g. log before data blocks? how does shell work? you type a program name the shell just CALLs that program, as a segment! the program eventually returns, e.g. with RET there's a per-process stack segment no fork, no exec buggy program can crash the shell! e.g. scribble on stack process creation was too slow to give each program its own process how to call supervisor? just like x86 8 rings. users at 4. core supervisor at 0. CPU remembers current execution level SDW has max read/write/execute levels call gate: lowers ring level, but only at designated entry stack per ring, call in switches stacks inner ring can always read arguments, write results are Multics rings a general-purpose protected subsystem facility? inner rings have full power over outer, you must trust them can't put more than one subsystem per ring hard to use "outer" rings for virtualization: can they call supervisor? today: user/kernel, server processes and IPC UNIX vs Multics UNIX was less ambitious (e.g. no unified mem/FS) UNIX hardware was small just a few programmers, all in the same room evolved rather than pre-planned quickly self-hosted, so they got experience earlier What did UNIX inherit from MULTICS? A shell that executes commands was obviously a big influence The idea of a hierarchical file system Probably the read-write-execute permission bits What did UNIX reject from MULTICS? segments memory == storage Hierarchical rings of protection (just kernel and user)