* The Multics Virtual Memory: Concepts and Design
* Authors: A. Bensoussan, C.T. Clingen, R.C. Daley
* Field: OS/Virtual Memory
* Reference: Communication of the ACM 1972 Vol.15

The basics: Multics has a paged, segmented virtual memory system.
There is no separate file system; instead, each segment is named and
accessed through a directory hierarchy, and memory accesses happen
directly to these segments.

Logical view: each segment is a separate, linear memory with its own
access attributes.  Addresses have the form [name, i] where name is
the segment name and i is the address of the referenced word in the
segment.  Processes correspond to virtual address spaces (i.e. each
process has a Known Segment Table, KST)

Misc: Supervisor uses segmentation also; supervisor lives in the
address space of each process.  Hierarchical directory structure
stores segment attributes in "branches."

Implementation of segmentation (paging is of segments is considered in
the next section):
- Per-process Descriptor Segment (DS, aka. segment table) whose
  entries describe each segment ever accessed by the process
- Descriptor Base Register (DBR) points to the DS of the currently
  executing process (DBR.core) and contains its length (DBR.L).
- Each segment descriptor word (SDW, aka. segment table entry)
  contains:
  1. core: Physical address of the segment
  2. L: Length of segment
  3. acc: Access rights of segment (read, write, execute, append)
  4. F: "Missing segment" bit

An access to memory [s,i] (segment number s, word i) performs:
(Algorithm 1)
  1. DBR.L < s: trap to OS (DS too small & can't contain SDW for s)
  2. Get SDW(s) = DS[s] = DBR.core + s (load DS entry for s)
  3. SDW(s).F == ON: missing segment fault (segment not attached)
  4. SDW(s).L < i: generate fault (invalid segment offset)
  5. Check SDW(s).acc for access rights
  6. Access requested word = SDW(s).core + i

Steps in getting a segment for the first time:
1. Segment referenced by name, causes trap to dynamic linker
2. d.l. searches directory for segment
3. retrieved segment given a number, name->number mapping and segment
   branch address stored in Known Segment Table (KST)
4. access to DS entry for segment traps to segment fault handler
5. segment fault handler looks up segment address & attributes
   by looking up branch address in KST
6. If branch is marked "inactive," a page table is allocated for 
   the segment
-->7. To allocate a page table, add entry to global Active Segment
      Table (i.e. table of segments allocated page tables) and mark
      segment as active in the branch, copy segment map, len to AST
8. Update the DS with segment attributes, turn off missing
   segment flag

--> AST used to ensure all information needed by page fault handler
    are in memory

Implementation of Paging:
- 1K page size
- All segments have page table (PT) with entries called page table
  words (PTW).  Each PTW contains:
  1. core: physical address of page
  2. F: "Missing page" (valid) bit
- Change Algorthm 1: DBR.core and SDW(s).core point to the page tables
  for the DS and segment(s), respectively.  Steps 2 and 6 in algorithm 1
  change to load the page table entry for the word being read and
  loading the page pointed to and then getting the requested word at
  the page offset (figure drawn on board).  Generate a page fault if
  PTW.F is on.
- Associative memory for PT entries and DS entries (TLB)

Page fault handler:
- keeps core map of used and free pages.
- page replacement policy: pseudo-LRU (single usage bit + voodoo)

Page Table Multiplexing (Segment Deactivation):
- Limited number of page tables (fixed number of AST entries):
  # AST entries < #segments
- PT's evicted from AST using approximate LRU: segment with no pages
  in core for the longest time, possible b/c # AST entries > # pages
- Supervisor keeps list of all processes using segment, flips on the
  missing segment bit when deactivated

Discussion:
1. Are the assumptions non-circularity in page-fault handling valid (see
  "Final Assumption")?
2. Is segmentation worth the complexity?
3. Does combining the VM system and file system really ease
   information sharing?