Virtual Memory, Processes, and Sharing in MULTICS
--- Daley et al., 1968


- objectives of MULTICS VM:

	- large, machine-independent VM; the user is provided with an
	  AS large enough to eliminate the need for overlay techniques;

	- create the ability of one procedure using another procedure
	  knowing only its name (dynamic linking);

	- sharing of procedures and data among users;

- hardware: GE Model 645, implementing segmentation and paging;

- an AS in MULTICS is composed of as many as 2^14 segments, each with
  up to 2^18 36-bit words;

- procedure segments are nonself-modifying, or pure procedures;

- as the size of the AS is considered big, files are always "memory
  mapped".  So, there is no big distinction between files and segments;

- each word is addressed by a generalized address (GA), which consists
  of two parts: segment number and word number;

- GAs are location-independent (virtual addresses);

- Processor:

	- one accumulator A (36 bits);
	- multiplier/quotioent (36 bits);
	- eight index registers (X0..X7);
	- a program counter (PC);
	- descriptor base register (DBR);
	- procedure base register (PBR);
	- 4 base pair registers (BPR);

- the PBR always contains the segment number of the procedure being
  executed;

- each BPR holds a complete GA:
	
	- argument pointer (ap);
	- base pointer (bp);
	- linkage pointer (lp);
	- stack pointer (sp);

- instruction format:

	- segment flag;
	- address;
	- opcode;
	- external flag;
	- addressing mode;

- the address of an instruction is the segment number in the PBR and
  the word number in the PC;

- if the external flag is on, the segment tag is used as an index to
  get the correct base register (ap, bp, lp, sp, I suppose), which
  gives a segment number SN and a word number WN0.  If displacement
  addr. mode is used the addr. mode is used to index one of the 8 
  index registers (the displacement is given in the address field in
  the instruction.) So, the final word number WN is given by:

	WN = WN0 + X[i] + address

- indirect addressing: if the addr. mode indicated indirect
  addressing (its), the GA is used to fetch 2 36-bit words which are
  used to create another GA.  If the addr. mode field of the first
  workd contains the code its (indirect through segment), the segment
  number (1st word) and word number (2nd word) are used to form a new
  GA.  This addressing is augmented by indexing according to the mode field
  of the second word (which can be itself indirect).

- the segment number of a GA is used as an index in an array called
  the descriptor segment of the PROCESS; it has a descriptor for each
  segment known by the process;

- the descriptor segment is found through the descriptor base
  register;

- there is a descriptor for each segment, that has protection
  information and a pointer to the segment's page table IN MEMORY (book);

- the DBR is the first location-dependent structure;


Intersegment linking and addressing:
-----------------------------------

- requirements of intersegment addressing:

	- procedure segments are pure;
	- it must be possible for a process to call a routine by its
	  symbolic name;
	- procedure segments must be invariant to the recompilation of
	  other segments;

- the solution is to have a mechanism that creates an entry in the
  descriptor segment table when the process first references a segment
  by its symbolic name.  Once a segment is known to the process, it may
  be referrenced through the segment number (segment number must not
  appear in the pure code, though!);

- a segment can be called by a process even if no position in the
  descriptor segment of the process has been reserved for the segment;
  hence, a mechanism is provided for assigning a position in the
  descriptor segment (a segment number) when the first reference occurs;

- a SEGMENT REFERENCE NAME is used in pure code; it is then used by a
  directory search algorithm to get the PATH NAME.  The segment is
  then made known to the process;

- if want to address location "x" withing segment D, could use 
  OPR<D>[x];

- after the segment is known to the process, a change must be made
  somewhere, to stop using symbolic name.  This alterable data is
  called the LINK DATA;

- the collection of link data for segment P is called its LINKAGE
  SECTION;

- whenever a procedure segment is made known to a process, a copy of
  the procedure's linkage section is made as a segment within that
  process;

- any data that allows different addresses to be formed from fixed
  code must reside in processor registers.  The linkage pointer (lp)
  is used as a base to point to external segments;

- suppose procedure P is being executed by process alpha and wants to
  access D[x], where D is a data segment and x is a location within D.
  P's linkage section is appended to alpha somewhere, pointed by the
  linkage pointer when P is being executed by alpha (lp points the the
  origin of the portion of a linkage segment relative to the segment
  (procedure) being executed).  As the linkage section was generated
  together with P, external references in P may use fixed indexes for
  all external symbols (e.g., D[x] may be the kth element in the linkage
  data).  Therefore, all references to D[x] point to the same entry in
  the linkage data.  Before the link is established, the pointer in the
  linkage data points somewhere in P where the symbolic name for <D>[x]
  is (with an addressing mode tha causes a fault.)  After established (D
  is now known to alpha), D's segment number is placed in the linkage
  data (this operation is called linking).  Thus, the link data is the
  item to be changed when linking occurs.  "x" is converted to a word
  number by examining D's symbol table;

- when procedure P calls Q, the linkage pointer must be changed to
  point to Q's linkage section (therefore, changing every procedure
  call);

- stack segment is private for each process, pointed by the sp base
  register;

- pointers and variable arguments must be placed in the stack segment,
  linkage segment, or elsewhere (the procedure segment is pure!);

- the ap register points to the list of arguments;