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
  design first, then implementation
  system stable by 1969
    so pre-dates UNIX, which started in 1969
  ambitious, many years, many programmers, MIT+GE+BTL

Multics high-level goals
  many users on same machine: "time sharing"
  perhaps commercial services sharing the machine too
  remote terminal access (but no recognizable data networks: wired or phone)
  persistent reliable file system
  encourage interaction between users
    support joint projects that share data &c
  control access to data that should not be shared

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

[per-process state]
  DBR
  DS, SDW (== address space)
  KST
  stack segment
  per-segment linkage segments

[global state]
  segment content pages
  per-segment page tables
  per-segment branch in directory segment
  AST

645 segments (simplified for now, no paging or rings)
  descriptor base register (DBR) holds phy addr of descriptor segment (DS)
  DS is an array 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 per-process page table, only per-segment
    so all processes using a segment share its page table and phys storage
    makes sense assuming segments tend to be shared
    paging environment doesn't change on process switch

Multics processes
  each process has its own DS
  Multics switches DBR on context switch
  different processes typically have different number for same segment

how to use segments to unify memory and file system?
  don't want to have to use 18-bit seg numbers as file names
  we want to write programs using symbolic names
  names should be hierarchical (for users)
    so users can have directories and sub-directories
    and path names

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
    o/s tables have path name where unix would have i-number
    presumably makes renaming and removing active files awkward
    no hard links

how does a program refer to a different segment?
  inter-segment variables contain symbolic segment name
  A$E refers to segment A, variable/function E
  what happens when segment B calls function A$E(1, 2, 3)?

when compiling B:
    compiler actually generates *two* segments
    one holds B's instructions
    one holds B's linkage information
    initial linkage entry:
      name of segment e.g. "A"
      name of symbol e.g. "E"
      valid flag
    CALL instruction is indirect through entry i of linkage segment
    compiler marks entry i invalid
    [storage for strings "A" and "E" really in segment B, not linkage seg]

when a process is executing B:
    two segments in DS: B and a *copy* of B's linkage segment
    CPU linkage register always points to current segment's linkage segment
    call A$E is really call indirect via linkage[i]
    faults because linkage[i] is invalid
    o/s fault handler
      looks up segment name for i ("A")
      search path in file system for segment "A" (cwd, library dirs)
      if not already in use by some process (branch active flag and AST knows):
        allocate page table and pages
        read segment A into memory
      if not already in use by *this* process (KST knows):
        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
        also set up copy of A's linkage segment
      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

how does A get the correct linkage register?
  the right value cannot be embedded in A, since shared among processes
  so CALL actually goes to instructions in A's linkage segment
    load current seg# into linkage register, jump into A
    one set of these per procedure in A

all memory / file references work this way
  as if pointers were really symbolic names
  segment # is really a transparent optimization
  linking is "dynamic"
    programs contain symbolic references
    resolved only as needed -- if/when executed
  code is shared among processes
  was program data shared?
    probably most variables not shared (on stack, in private segments)
    maybe a DB would share a data segment, w/ synchronization
  file data:
    probably one at a time (locks) for read/write
    read-only is easy to share

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!
    but no buffer cache => ad-hoc caches e.g. active segment table
  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?
    I don't know, probably separate flush system calls

how does shell work?
  you type a program name
  the shell just CALLs that program, as a segment!
  dynamic linking finds program segment and any library segments it needs
  the program eventually returns, e.g. with RET
  all this happened inside the shell process's address space
  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 valuable is the sharing provided by segment machinery?
  is it critical to users sharing information?
  or is it just there to save memory and copying?

how does the kernel fit into all this?
  kernel is a bunch of code modules in segments (in file system)
  a process dynamically loads in the kernel segments that it uses
  so kernel segments have different numbers in different processes
    a little different from separate kernel "program" in JOS or xv6
  kernel shares process's segment# address space  
    thus easy to interpret seg #s in system call arguments
  kernel segment ACLs in file system restrict write
    so mapped non-writeable into processes

how to call the kernel?
  very similar to the Intel x86
  8 rings. users at 4. core kernel at 0.
  CPU knows current execution level
  SDW has max read/write/execute levels
  call gate: lowers ring level, but only at designated entry
  stack per ring, incoming call switches stacks
  inner ring can always read arguments, write results
  problem: checking validity of arguments to system calls
    don't want user to trick kernel into reading/writing the wrong segment
    you have this problem in JOS too
    later Multics CPUs had hardware to check argument references

are Multics rings a general-purpose protected subsystem facility?
  example: protected game implementation
    protected so that users cannot cheat
    put game's code and data in ring 3
    BUT what if I don't trust the author?
      or if i've already put some other subsystem in ring 3?
    a ring has full power over itself and outer rings: you must trust
  today: user/kernel, server processes and IPC
    pro: protection among mutually suspicious subsystems
    con: no convenient sharing of address spaces

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 at user level (not built into kernel)
  a single hierarchical file system, with subdirectories
  controlled sharing of files
  written in high level language, self-hosted development

What did UNIX reject from MULTICS?
  files look like memory
    instead, unifying idea is file descriptor and read()/write()
    memory is a totally separate resource
  dynamic linking
    instead, static linking at compile time, every binary had copy of libraries
  segments and sharing
    instead, single linear address space per process, like xv6
  (but shared libraries brought these back, just for efficiency, in 1980s)
  Hierarchical rings of protection
    simpler user/kernel
    for subsystems, setuid, then client/server and IPC

The most useful sources I found for late-1960s Multics VM:
  1. Bensoussan, Clingen, Daley, "The Multics Virtual Memory: Concepts
     and Design," CACM 1972 (segments, paging, naming segments, dynamic
     linking).
  2. Daley and Dennis, "Virtual Memory, Processes, and Sharing in Multics,"
     SOSP 1967 (more details about dynamic linking and CPU). 
  3. Graham, "Protection in an Information Processing Utility,"
     CACM 1968 (brief account of rings and gates).