:TITLE[MesaP];
%
Ed Fiala 11 July 1984: Add GLOBAL_odd value in Reschedule to make sure that
  Loadgc gets called on entering a new context; some comment changes.
Ed Fiala 17 May 1984: Restored minimal stack error check; added
  At[prNoBackPCFaultLoc]; fix bug where Abortable bit is cleared by
  @NC and @BC reported by Blackman.
Ed Fiala 23 April 1984: Moved refill trap to MesaOP2.mc; created
  prBackPCFault label to save 1 mi; fixed bug at RSSavePsb+4; absorbed
  PC backup for Fault.mc entries to prFaultLoc; bummed 3 mi in MW by
  not saving StkP; use prTicksStkP instead of prSaveStkP.
  Patch out minimal stack errors for now.
Ed Fiala 8 November 1983:  Changed @ME and @MX from Esc to regular
  opcodes; improvement in @REQ; change entry at prFault.
  Change PSB format to 8 words for Klamath, absorbing Timeout word and
  adding Sticky; change timeout scan back to one word fetches again
  @19 cycles/PSB; rewrite Reschedule for Permanent bit, expanded PSB,
  and to fix bug in not saving MDShi.
  Eliminate prIntPdaTimeout, prIntPsbIndex, prPdaTimeout registers;
  add prPsbMds, prPsbData, prPsbSticky, prPsbGarb quadword.
Ed Fiala 13 June 1983: Fix comments in CleanUpQueue; add comments about
  "available" in psb; check for CVQ=MonQ in REQ.
Ed Fiala 9 June 1983: Fix recently introduced bug in NWUXXX.
Ed Fiala 2 June 1983: Fix recently introduced bug in CleanUpQueue.
Ed Fiala 19 May 1983: Change xfWDC counting to distinguish various cases
  when interrupts disabled trap in Reschedule occurs.  Fix RescheduleError
  trap to not save state twice and to zero xfWDC before continuing; make the
  trap not occur and prevent rescheduling if NC or BC executed with interrupts
  disabled.  Added MonExitError (MP 0137) when monitor is already unlocked
  and MX or MW is executed.  Improve RequeueSub speed about 16 cycles.
  Eliminate prQueue register.  Save cycles and 1 mi at BroadcastLoop.  Fix
  (newly introduced) bugs in CleanUpQueue.
Ed Fiala 29 April 1983:  Rewrite RequeueSub, Reschedule, WakeHead, Interrupt,
  CleanUpQueue, MX, and CheckForTimeouts for speed, space, and register
  improvements.  System about 2 percent faster, primarily from CheckForTimeouts
  changes (7 cycles/Psb now compared to 24 cycles/Psb previously); speeded
  Reschedule by a factor of 2; bummed many registers and cycles out of
  RequeueSub also.  Absorbed 3 mi from MesaOP0.Mc at Interrupt.  Eliminated
  potential bug by storing prMonitor in REQ in case of WP fault; made
  CleanUpQueue conform to Princ Ops (now preserves bits 0..3 and bit 16b;
  formerly preserved only bit 16b (abortable)); fixed bug in CleanUpQueue
  which caused it to leave CV pointing at queue head rather than queue tail
  in complicated case.  Fix timing glitch in
  CheckForTimeouts when prTicks=0.  Always generate trap in Reschedule if
  wakeups are disabled rather than just when no processes are ready to run.
  Disable interrupts in Interrupt & RequeueSub to detect problems--the
  Reschedule Error trap will occur if any page, write protect, or frame
  fault occurs at these illegal times.
  Add prWaitCount for MW, prStkP and prLocal for Reschedule; eliminate
  prPsbPriority, prConditionTail, prCleanupLink, prQTemp, prQTemphi,
  prTimeout, prQueueHead, prQueueTail; started using IBuf-IBuf3 and
  prIntPsbIndex in CheckForTimeouts.
  Note Princ Ops changes:
  (1) Ones complement counting in timeout scan as well as MW, when computing
  value to be stored in timeout table eliminates the 1 tick extra delay
  which occurs on wrap around and removes 1 branch condition from the inner
  loop of the timeout scan.
  (2) Assume that the quadword after the last timeout table entry can be
  referenced without a page fault (This works at present because it is in
  a StateVector, which is resident.).
  (3) Would like to assume that the unused timeout table entries in the final
  quadword are all 0 (not presently assuming this).
  (4) Redefine the Reschedule Error trap to mean any entry to the scheduler
  with interrupts disabled.  Disable interrupts during the Interrupt dispatch
  and during RequeueSub.
  (5) In general for most data structures of interest assume not only that
  the structure starts on a 4-word or 16d-word boundary but also that it is
  a multiple of 4 or 16d words long.
Ed Fiala 25 August 1982: Absorbed RequeueSub in its two callers and ExitM2
  in its two callers to speed up MX and MW opcodes, while changing prFault
  slightly; fixed bug in MW not interlocking prPsbIndex; renamed
  RequeueSubPsbFetched to be RequeueSub, ExitM1 to be StoreMonitor;
  eliminated PStore4 after return at RequeueExit as a precaution; moved Fetch
  of ReadyQ^ to RequeueExit; altogether bummed 5 mi.
Ed Fiala 21 May 1982: PushSD for NoPushSD; replace prPsbLink.next by
  prNextPsbLink; bum 2 mi at prFault; convert 2 mi at RSLoadAndFreeState to
  1 mi on prPage.
Ed Fiala 14 May 1982: Reduced tasking time for @SPP, @ME, RequeueExit,
  @MW, UpdateConditionQueue, Interrupt, RSSaveProcess, CheckForTimeoutLoop;
  introduce LinkOrT subr; remove PStore1[prMonitorQ...] at MonitorFetch+1
  and add it at EntryFailed (should be safe against write protect fault;
  improves tasking and speed).  Fixed bug in @MW not refetching current Psb
  after ExitM2 call.  Speeded WakeHead, CleanUpQueue.  Removed PFetch4 at
  opcode dispatch and added it at jumps to EntryFailed and in @MR opcode
  speeding up the process opcodes by 4 cycles each; introduced prIntSaveStkP
  and prIntPdaTimeout registers in CheckForTimeout code; speeded up
  CheckForTimeoutLoop substantially.
Ed Fiala 15 March 1982: bum 1 mi in MXDepart by shuffling ProcessDisp
  offsets, 1 mi in SPPOp; 2 mi in CleanUpQueue.  Eliminated SPPloc because
  there is no room for it in the current dispatch and jump directly to SPPOp
  without minimal stack error check; undid 1 mi bug in Reschedule; speed up
  code at Interrupt a little; replace prPdaTimeout at CheckForTimeouts by
  prCurrentSAT.
Jim Sandman 8 Mar 1982: Implemented SPP.  reordered dispatch to include
  SPP.  added 6 mi.
Ed Fiala 5 March 1982: advanced the call to SavPCinFrame in
  RSSaveProcess; changed T to (Zero) or T there; eliminated RSAllocState,
  RSSVError, RSSVAvailable, and RSSaveStack labels; put in shell for new
  @SPP opcode; fix bug in @MX.
Ed Fiala 11 December 1981: Converted process opcodes to long mode only
  for new instruction set; changed them to Esc opcodes on xfPage1; bummed
  12 mi elsewhere in code; remove Bravo paragraphing and reabsorb MesaPDefs;
  replaced ExitMon subroutine by ExitM1 and ExitM2; absorbed NotifyWakeup
  subr in its two callers using NWUXXX now (eliminates prRtnLink2, saving
  1 RM register).
Jim Sandman 4 December 1981: Put in code to get timeouts from separate
  timeout vector and get mds field from psb.  Added 3 mi in MXWait, 3 mi in
  WakeHead, and 7 mi in CheckForTimeouts to do timeout vector change, and 5 mi
  in RSXfer to do mds field.
Ed Fiala 22 September 1981: P4Ret edits; Idle loop change; minimal
  stack error check bugfix; bum 3 mi.
Original version by Jim Sandman; major changes by Jim Frandeen; other edits
  by Rich Johnsson and Ev Neely.

Other possible changes:
1) Minimal stack check in SPP.
2) Check for source queue pointing elsewhere when Psb points at itself when
dequeuing.
3) Consider accelerating Xfer entry in Reschedule.
4) Make some of the MP codes be Reschedule Error traps if can decode what
happened in the debugger.
5) Eliminate prIntSaveStkP by using prStkP; then don't have to resave StkP
in Reschedule.
6) Go more directly to Interrupt from the Idle loop (no need to save/restore
StkP, test xfWDC).
7) Eliminate the PStore1[prConditionQ,...] in MonAndCondDisp and in
ConditionDisp that is used to trigger write protect faults and instead do
it in CleanUpQueue?
8) SPP is presently illegal with interrupts disabled, but if its exit is
changed from Req&Res to ResIfReq to prevent rescheduling when interrupts
are disabled, then it might continue without a state vector and die later.
What should be done about this?
9) Rescheduling could be avoided in some cases when the current process
is still highest priority after exiting to ResIfReq.
%



MC[PSBSize,10];

%PSB (Process State Block) format.

Word 0: prPsbLink
  Bits 0..2: priority of Psb
  Bits 3..14b: index of next Psb in the queue.
  Bit 15b: monitor entry failed (PSB is on a Monitor queue.)
  Bit 16b: permanent (1 => StateVector is permanently assigned to this
	process and will always be used to save/restore state)
  Bit 17b: preempted by an interrupt or fault
	 (1 => prPsbContext points at a StateVector)
%
MC[EnterFailed,4];
MC[Permanent,2];		*Bit 16b: permanent StateVector asigned to process.
MC[Preempted,1];		*Bit 17b: = 1 if prPsbContext points to a StateVector.

%Word 1: prPsbFlags
Bits 0..2: available (used only by software):
	0	Waiting for join
	1	Transient state between normally running detached process and
		state 3
	2	Transient state between 0 and 4
	3	Transient state between 1 and 5
	4	Dead process (formerly attached=expected to join)
	5	Dead process (formerly detached=did not expect to join)
	6	Normally running attached process
	7	Normally running detached process
Bits 3..14b: PsbIndex of cleanup link.
Bit 15b: reserved
Bit 16b: waiting (process is waiting on a condition queue)
Bit 17b: abort (process will be aborted at next wait)
%
MC[waiting,2];
MC[abortPending,1];

*Word 2: prPsbContext (pointer to StateVector or frame)
*Word 3: prTimeout (ticks of process)
*Word 4: prMDS (value of MDShi for this process)
*Word 5: data
*Word 6: STICKY (value of floating point flags for this process).
*Word 7: unused

*Condition format.
*Bits 0..2 = zero.
*Bits 3..14b: PsbIndex of tail of condition queue.
*Bit 15b: available
MC[abortable,2];	*Bit 16b: = 1 if abortable.
MC[wakeup,1];		*Bit 17b: This is set by NakedNotify if queue empty.

*Monitor format. A process is moved to a monitor lock queue when it has
*failed to enter a monitor because some other process is already inside the
*monitor.
*Bits 0..2 = zero.	***BUT I SAW SIGN BIT NON-ZERO
*Bits 3..14b: PsbIndex of tail of monitor queue.
*Bits 15..16b: available.
MC[monitorLock,1];	*Bit 17b: = 1 if monitor is locked, = 0 if unlocked.

*State Vector format (24b words long).
MC[svNext,0];		*Word 0 is a pointer to the next StateVector (0 if
			*none) when StateVectors are not being used.
MC[svStack,0];		*Word 0..3b: of evaluation stack.
MC[svStack4,4];		*Word 4b..7b of stack.
MC[svStack8,10];	*Word 10b..13b of stack.
MC[svStack12,14];	*Word 14b..15b of stack.
			*Word 16b: StateWord [break : BYTE,  stkptr : Byte].
MC[svLocal,17];		*Word 17b: used to save Local.
MC[svData,20];		*Word 20b..23b: Unspecified.

*DISPATCH TABLES:
Loca[ProcessDisp,prPage,0];
*The following locations must be even.  The last bit is truncated in the
*Flags constant, and the Dispatch picks up 4 bits with a zero in the last bit.
	Set[MEloc,0];
	Set[MRloc,2];
	Set[MWloc,4];	*MWloc to MWloc+2 used
	Set[MXloc,10];	*MXloc to MXloc+1 used
	Set[NCBCLoc,14];	*NCBCloc+1 also used
	Set[REQloc,16];
Loca[FQDisp,prPage,20];	*For RequeueSub
Loca[SQDisp,prPage,40];	*For RequeueSub
Loca[GQDisp,prPage,60];	*For RequeueSub

%Registers preserved across opcodes:

prCurrentPsb	Contains PsbIndex of the current Psb. This points to the front
		of the ready queue.
prPda,prPdaHi	This base register pair points to the Pda. The Pda is assigned
		to location 200000. The register pair RZero and R400 are used
		to point to the Pda.  400 in the high byte works because the
		Pda will not cross a page boundary.
prPsbIndexMask	This contains a mask for the PsbIndex
prTime		Decremented by 1 each scan line.  When 0, CheckForTimeouts
		sets it back to TickSize (3) and adds 1 to prTicks.
prTicks		Current tick count for timeout clock.

Other registers:

prFlags		Holds Opcode dispatch values and flags (described below)

bit 0		0 =>	Notify
		1 =>	Broadcast
bits 1-2  Source Queue:	0 =>	Ready Queue
bits 3-4  Dest Queue:	1 =>	Monitor Queue
			2 =>	Condition Queue
bits 5-10b Opcode Disp
bit 11b		0 =>	Requeue not done
		1 =>	Requeue done
bits 12b-15b	Unused
bit 16b		1 =>	Reschedule entered on Interrupt or fault; save stack
		0 =>	Don't save stack.
bit 17b		0 =>	Source queue not nil
		1 =>	Source Queue nil
%
Set[SourceQbit,1];
Set[DestQbit,3];

Set[SourceIsReadyQ,LShift[0,15]];
Set[SourceIsMonitorQ,LShift[1,15]];
Set[SourceIsConditionQ,LShift[2,15]];
Set[DestIsReadyQ,LShift[0,13]];
Set[DestIsMonitorQ,LShift[1,13]];
Set[DestIsConditionQ,LShift[2,13]];

MC[RequeueOccurred,100];
MC[SaveStack,2];
MC[SourceQNil,1];

MC[ReadyQtoConditionQ,Or[SourceIsReadyQ,DestIsConditionQ]];
MC[ConditionQtoReadyQ,Or[SourceIsConditionQ,DestIsReadyQ]];

MC[MEflags,Add[LShift[MEloc,7],SourceIsReadyQ,DestIsMonitorQ]];
MC[MRflags,Add[LShift[MRloc,7],SourceIsReadyQ,DestIsMonitorQ]];
MC[MWflags,Add[LShift[MWloc,7],SourceIsMonitorQ,DestIsReadyQ]];
MC[MXflags,Add[LShift[MXloc,7],SourceIsMonitorQ,DestIsReadyQ]];
MC[NCflags,Add[LShift[NCBCloc,7],ConditionQtoReadyQ!]];
MC[BCflags,Add[LShift[NCBCloc,7],ConditionQtoReadyQ!,100000]];
MC[SPPflags,Or[SourceIsReadyQ,DestIsReadyQ]];
MC[REQflags,Add[LShift[REQloc,7],SourceIsMonitorQ,DestIsConditionQ]];
MC[REQSameflags,Add[LShift[REQloc,7],SourceIsConditionQ,DestIsConditionQ]];

*Monitor Entry. Stack contains long pointer to Monitor.
*Timing: ~2.25+45 = ~47.25 cycles in the ordinary case.
@ME:	LoadPage[xfPage1], Opcode[361];
	prFlags _ MEflags, GoToP[MonitorDsp];

*Monitor Exit. Stack contains long pointer to Monitor.
*Timing: ~2.25+45 = ~47.25 cycles in the ordinary case.
@MX:	LoadPage[xfPage1], Opcode[362];
	prFlags _ MXflags, GoToP[MonitorDsp];

*Monitor Wait. Stack contains time, long pointer to Condition, and long pointer to Monitor.
*Timing: ~14.5+44+~63.
@MW:	prFlags _ MWflags, GoToP[.+1], At[EscD0,2];
OnPage[xfPage1];
*Skip the wait count argument on the stack here; it will be accessed as a
*regular register later.
	Stack&-1, GoTo[MonAndCondDsp];

*Monitor Reentry. Stack contains long pointer to Condition and long pointer to Monitor.
*Timing: ~14.5+42+~63.
@MR:	prFlags _ MRflags, GoToP[MonAndCondDsp], At[EscD0,3];

*Notify Condition. Stack contains long pointer to Condition.
*Timing: ~14.5+33+61?.
@NC:	prFlags _ NCflags, GoToP[ConditionDsp], At[EscD0,4];

*Broadcast Condition. Stack contains long pointer to Condition.
*Timing: ~14.5+33+61?.
@BC:	prFlags _ BCflags, GoToP[ConditionDsp], At[EscD0,5];

*Set Process Priority. Put priority in TOS into current PSB and requeue
*from ready list to ready list.
@SPP:	T _ prCurrentPsb, GoToP[.+1], At[EscD0,17];
OnPage[xfPage1];
	PFetch4[prPda,prPsbLink], Task;
%Clear priority field and enterFailed bit; clearing enterFailed is harmless
because it is known to be 0.
***Didn't do minimal stack error check here.
%
	prFlags _ SPPflags;
	prPsbIndex _ T, LoadPage[prPage];
	T _ LSh[Stack&-1,15];
OnPage[prPage];
	prPsbLink _ (LdF[prPsbLink,3,15]) or T, GoTo[Req&Res];

*Requeue.  Stack contains a Psb index, a long pointer to a source queue,
*and a long pointer to a destination queue.  Put the source queue in
*MonitorQ, destination queue in ConditionQ.
@REQ:	T _ Stack&-1, GoToP[.+1], At[EscD0,6];
OnPage[xfPage1];
	prPsbIndex _ T;
	T _ LSh[Stack&-1,10], Call[FixConditionQueue];
*Trigger write protect fault if protected.
	PStore1[prConditionQ,prCondition,0];
	T _ LSh[Stack&-1,10], Call[FixMonitor];
%Don't fetch Monitor if NIL source; this can happen legitimately for @REQ
when a timeout is simulated; other process opcodes allow an address fault.
If prConditionQ .eq. prMonitorQ, RequeueSub will malfunction because
prCondition won't be refetched after dequeuing.  This could be made a bug
because SPP fulfills the only reason to requeue a process onto the same
queue; however, at the moment "YIELD" uses REQ.  Note that prCondition .eq.
prMonitor is possible iff prConditionQ/Qhi .eq. prMonitorQ/Qhi.
%
	LU _ (prMonitorQhi) or T;	*Check for nil long pointer.
	prFlags _ REQFlags, Skip[ALU#0];
	  prFlags _ (prFlags) or (SourceQNil), GoTo[ProcessOps];
	PFetch1[prMonitorQ,prMonitor,0], Task;
	T _ prCondition;
	LU _ (prMonitor) xor T;
*PStore1 guards against WP fault.
	PStore1[prMonitorQ,prMonitor,0], Skip[ALU#0];
	  prFlags _ REQSameFlags;
	T _ (SStkP&NStkP) + 1, LoadPage[prPage], GoTo[ProcessOps1];

OnPage[xfPage1];
MonAndCondDsp:
	T _ LSh[Stack&-1,10], Call[FixConditionQueue];
*Trigger write protect fault if protected.
	PStore1[prConditionQ,prCondition,0];
MonitorDsp:
	T _ LSh[Stack&-1,10], Call[FixMonitor];
	PFetch1[prMonitorQ,prMonitor,0], Call[xfRet];
*Note that these opcodes must be minimal stack because the
*stack is not saved while other processes are running.
ProcessOps:
	T _ (SStkP&NStkP) + 1, LoadPage[prPage];
ProcessOps1:
	Dispatch[prFlags,5,4], GoToP[.+3,H2Bit8'];
OnPage[prPage];
	  LoadPageExternal[FaultPage];
	  GoToExternal[StackErrorLoc];
	T _ prCurrentPsb, Disp[ME1];

OnPage[xfPage1];

*All we use ConditionQ for is to fetch and store one word, so we don't need
*to create a perfect base register.
ConditionDsp:
	T _ LSh[Stack&-1,10], Call[FixConditionQueue];
*Trigger write protect fault if protected
	PStore1[prConditionQ,prCondition,0], GoTo[ProcessOps];

FixConditionQueue:
	prConditionQhi _ T;
	T _ Stack&-1;
	prConditionQ _ T;
	PFetch1[prConditionQ,prCondition,0], GoTo[xfRet];

*All we use MonitorQ for is to fetch and store one word, so we don't need to
*create a perfect base register.
FixMonitor:
	prMonitorQhi _ T;
	T _ Stack&-1;
	prMonitorQ _ T, Return;

%Monitor Entry is executed by an entry procedure of a Mesa monitor. It returns
TRUE on the stack if the monitor was not locked; otherwise the running process
is put on the monitor queue, and the stack is left empty.

Input:	prMonitorQ	base register pair points to Monitor
	prMonitor	contains MonitorQ^
	T		points at CurrentPsb
Exits:	EntryFailed	if enter unsuccessful
%
*IF Monitor.locked THEN GoTo EntryFailed; Monitor.lock _ locked
ME1:	prMonitor _ (prMonitor) or (monitorLock), Skip[R Even], At[ProcessDisp,MEloc];
	  PFetch4[prPda,prPsbLink], GoTo[EntryFailed];
*No need to Call Reschedule because no requeue has occurred.
	PStore1[prMonitorQ,prMonitor,0];	*Store Monitor
*Must task here for timing reasons.
LockMonitor&Exit:
	Call[prRet];
*NextInst will hold until page and write-protect faults are impossible.
*This is necessary because write protect faults are possible on the store of
*the monitor (used to implement copy-on-write).
	LU _ NextInst[IBuf];
	Stack&+1 _ 1C, NIRet;	*Push[TRUE].

%Come here if monitor is already locked with prCurrentPsb in T.  Move the
current process from ready queue to monitor lock queue.  PsbLink will be
updated by Requeue.
%
EntryFailed:
	prPsbIndex _ T, Call[StoreMonitor];
	prPsbLink _ (prPsbLink) or (EnterFailed), GoTo[Req&Res];


%Monitor Exit is executed at the end of a Mesa monitor entry procedure.
It unlocks the monitor and, if the monitor queue is non-empty, moves its
first (i.e., highest priority) entry to the ready queue. 

Input:	prMonitorQ	base register pair points to Monitor
	prMonitor	contains MonitorQ^
	T		points at CurrentPsb
Exits:	REQ1
%
@MX1:	Call[MExit], At[ProcessDisp,MXloc];
	T _ (prMonitor) and T;	*Must clear the available bit
	Skip[ALU=0];
	  PFetch1[prPda,prPsbIndex], GoTo[REQ1];
	LU _ NextInst[IBuf];
prTailx:
	NIRet;

prRet:	Return;

MExit:	prMonitor _ (prMonitor) and not (monitorLock), GoTo[.+3,R Odd];
	  LoadPageExternal[0];	*Monitor already unlocked
	  T _ MonExitError, GoToExternal[CrashLoc];
StoreMonitor:
	PStore1[prMonitorQ,prMonitor,0], GoTo[TGetsPsbIndexMask];

%MW (Monitor Exit and Wait) is executed within a monitor to wait on a
condition variable.  It unlocks the monitor, and if MonitorQ is non-empty,
moves its first entry to ReadyQ. If there is no wakeup waiting or abort
pending, then the process executing MW is moved to ConditionQ; otherwise,
it remains on ReadyQ.

Input:	prMonitorQ	base register pair points to Monitor
	prMonitor	MonitorQ^
	prConditionQ	base register pair points to Condition
	prCondition	ConditionQ^
	prWaitCount	time out value (This register is coincident with
			Stack4, the argument to the opcode.)
	prFlags		MonitorQ to ReadyQ
	T		points at CurrentPsb
Output:	prPsbIndex	CurrentPsb for Requeue
	prPsbLink	four-word buffer contains CurrentPsb
Subroutines called:
	CleanUpQueue
	RequeueSub
Exits:	Req&Res
	ResIfReq
%

@MW1:	T _ prPsbIndexMask, Call[CleanUpQueue], At[ProcessDisp,MWloc];
	prTicksStkP _ IP[prTicks]C, Call[MExit];
	T _ (prMonitor) and T;	*T _ tail Psb index
	GoTo[MW2,ALU=0];	*Jump if tail = nil
	  PFetch1[prPda,prPsbIndex], Call[TGetsPsbIndexMask];
	  prPsbIndex _ T _ (prPsbIndex) and T;	*T _ head Psb index
	  PFetch4[prPda,prPsbLink], Call[RequeueSub0];
MW2:	T _ prCurrentPsb;
	prPsbIndex _ T, Call[FetchPsb];
*If PsbFlags.abortPending and Condition.abortable, then reschedule;
*otherwise, if there is a wakeup, clear it and reschedule;
*otherwise, queue the process on the condition queue and reschedule.
	LU _ (prCondition) and (abortable);
*Psb.waiting _ TRUE (which will be stored only if requeue happens below).
	prPsbFlags _ (prPsbFlags) or (waiting), GoTo[MW3,ALU=0];
	LU _ prPsbFlags, Skip[R Even];	*Skip if AbortPending=0
	  LU _ (prFlags) and (RequeueOccurred), GoTo[ResIfReq];	*Abort
	prCondition _ (prCondition) and not (wakeup), DblGoTo[MW4,.+2,R Even];
MW3:	prCondition _ (prCondition) and not (wakeup), GoTo[MW4,R Even];
*If wakeup is waiting, clear it and continue running the current process.
	PStore1[prConditionQ,prCondition,0], Call[prRet];
*Also get here from @NC opcode.
*Time to task below here can be as long as 22 cycles via NextInst trap.
NotifyExit:
	LU _ (prFlags) and (RequeueOccurred), GoTo[ResIfReq];

*If no wakeup is waiting, set timeout and queue prCurrentPsb on ConditionQ.
*Use StkP to address prTicks (outside RM 0-77)
**OK to smash StkP on minimal stack opcode.
MW4:	StkP _ prTicksStkP;
	T _ prWaitCount;
	*LU _ LdF[prPsbFlags,3,12];
	*T _ prWaitCount, GoTo[.+3,ALU=0];	*Put timeout in timeout table.
	*  LoadPageExternal[0];
	*  T _ CULError, GoToExternal[CrashLoc];	*138d MW with CUL#0
*Skip to zero the timeout.
	LU _ (Stack) + T, Skip[ALU=0];
*Timeout _ Ticks+Timeout; add 1 if addition carries (indicating 0 crossing)
*The timeout scan does an extra increment at 0, so the timeout value of 0
*never occurs.
	  T _ (Stack) + T, UseCOutAsCIn;
	prPsbTimeout _ T;
*Set up prFlags to requeue from ReadyQ to ConditionQ.
*Initially, we were set up to go MonitorQ to ReadyQ.
	prFlags _ ReadyQtoConditionQ, GoTo[Req&Res];

%MR reenters a monitor which a process has exited to wait on a condition
variable queue.  If the monitor is locked, the process is placed on the
monitor lock queue as in ME.

Input:	prMonitorQ	base register pair points to Monitor
	prMonitor	contains MonitorQ^
	prConditionQ	base register pair points to Condition
	prCondition	contains ConditionQ^
	prFlags		ReadyQ to MonitorQ
	T		points at CurrentPsb
Subroutines called:
	CleanUpQueue	if enter successful
Exits:	EntryFailed	if enter unsuccessful, else
	BackSPPCandTrap	if abortPending and abortable, else
	LockMonitor&Exit
%
@MR1:	prMonitor _ (prMonitor) or (monitorLock), Skip[R Even], At[ProcessDisp,MRloc];
	  PFetch4[prPda,prPsbLink], GoTo[EntryFailed];
	PFetch4[prPda,prPsbLink];
*Clean up the condition queue.
	T _ prPsbIndexMask, Call[CleanUpQueue];
*Return with PsbIndexMask in T; zero Flags.CleanupLink.
	prPsbFlags _ (prPsbFlags) and not T, Call[StoreCurrentPsb];
*If there is no abort, then push true (=1) and exit.
	LU _ (prPsbFlags) and (AbortPending);
	LU _ (prCondition) and (abortable), Skip[ALU#0];
	  PStore1[prMonitorQ,prMonitor,0], GoTo[LockMonitor&Exit];
	RTemp _ sProcessTrap, GoTo[PRTrap,ALU#0];
	  PStore1[prMonitorQ,prMonitor,0], GoTo[LockMonitor&Exit];
*Trap if condition.abortable and PsbFlags.AbortPending.
PRTrap:	LoadPage[opPage0];
	T _ SStkP, GoToP[BackSPPCandTrap];


%REQ, given a PsbIndex two queue pointers, removes the process from the
source queue and inserts it according to priority into the destination queue.

Input:	prConditionQ	base register pair points to Dest queue (if needed)
	prMonitorQ	base register pair points to Source queue (if needed)
	prPsbIndex	points to Psb to be requeued
Exits:	Reschedule

Note: If REQ is called with SourceQ=nil, it will wind up setting the cleanup
link, so SourceQ=nil is illegal when the source queue is not a condition
variable queue.  If the source is a condition variable queue and
SourceQ#nil, CleanUpQueue will not be called, so cleanup links in the source
queue are illegal.
%
*Jump here from @MX, @REQ.
REQ1:	T _ prPsbIndexMask, At[ProcessDisp,REQloc];
	T _ prPsbIndex _ (prPsbIndex) and T, Call[FetchPsb];
*Jump here from @SPP, MW5, and EntryFailed.
Req&Res:
	xfWDC _ (xfWDC) + 1, UseCTask, Call[RequeueSub];
*Jump here from prFault, Interrupt.
RescheduleCurrent:
	PFetch1[prPda,prReady,pdaReady!], GoTo[Reschedule];

%Notify moves the 1st entry of a condition variable queue to the ready queue.
Broadcast moves all entries of a condition variable queue to the ready queue.

Input:	prConditionQ	base register pair points to Condition
	prCondition	ConditionQ^
	prFlags		ConditionQ to ReadyQ; plus Broadcast bit (bit 0) for
			Broadcast
Exits:	ResIfReq
%
@NC1:
@BC1:	T _ prPsbIndexMask, Call[CleanUpQueue], At[ProcessDisp,NCBCloc];
BCLoop:	T _ (prCondition) and T;
	GoTo[NotifyExit,ALU=0];	*IF condition.tail = nil Then Exit
	PFetch1[prPda,prPsbIndex], Call[WakeHead];
*Loop IF broadcast
	LU _ (prFlags) and (RequeueOccurred), GoTo[ResIfReq,R>=0];
	T _ prPsbIndexMask, GoTo[BCLoop];


%Move the first Psb on ConditionQueue to the ready queue.  WakeHead is called
by @BC or @NC; on interrupt processing when an io controller has set a bit in
NWW corresponding to a condition in Pda.Interrupt; and on fault processing for
the fault condition queue.  The fault and interrupt calls are made through
the NWUXXX subroutine.

Input:	prConditionQ	base register pair points to Condition
	prPsbIndex	Condition.tail^ for Requeue
Output:	prPsbLink	four-word buffer contains Psb pointed to by PsbIndex
Subroutines called:
	RequeueSub
Exits:	Return to caller from RequeueSub
Timing:	28-6 cycles + RequeueSub0
%
WakeHead:	*Returns with PsbIndexMask in T.
	xfWDC _ (xfWDC) + 1, UseCTask;
	T _ APCTask&APC, Call[SaveReturnLink];
*Fetch PsbIndex^ into 4-word Psb buffer.
	T _ prPsbIndex _ (prPsbIndex) and T, Call[FetchPsb];
	T _ prPsbIndexMask;
*Psb.waiting _ FALSE.
	prPsbFlags _ (prPsbFlags) and not (waiting);
*Zero timeout.
	prPsbTimeout _ 0C, GoTo[RequeuePsbFetched];

%CleanUpQueue must be called before accessing a condition variable queue
since the queue pointer may be incorrect.  This occurs when the lowest
priority Psb of the queue has been requeued and Requeue did not know to which
CV queue the Psb belonged (This happens on timeouts and aborts.)  Whenever
the source queue is unknown, Requeue stores the old link field into the Psb's
cleanup link.  The goal of CleanUpQueue is to find the correct head of the CV
queue, and therefore the tail--to which the CV should point.  Cleanup links
are followed until there are no more; the last Psb is declared as the head,
and then the usual links are followed until the tail is found.  @MR zeroes
the cleanup link; CleanUpQueue only fixes the condition variable itself.

Input:	prConditionQ	base register pair points to Condition
	prCondition	ConditionQ^
	T		prPsbIndexMask
Output:	prCondition	updated ConditionQ^
	T		PsbIndexMask
Temps shared with Requeue Temps
	prNextPsbLink
	prPrevPsbLink
Exits:	Return to caller

Timing:	6 cycles when the condition queue is empty, else 27 cycles when the
cleanup link is nil.
%
CleanUpQueue:
	T _ (prCondition) and T;
*Return if the condition queue is empty.
CleanUpQueue1:
	T _ (RZero) + T + 1, Skip[ALU#0];	*Know psbFlags=1
TGetsPsbIndexMask:
	  T _ prPsbIndexMask, Return;
	PFetch1[prPda,prNextPsbLink];	*Fetch prPsbFlags (cleanup link)
	prPrevPsbLink _ T, UseCTask;	*Bypass kludge ok--prPda contains 0
	T _ APCTask&APC, Call[SaveReturnLink];
	T _ (prNextPsbLink) and T;
*Return if the cleanup link is nil.
	LU _ (prPrevPsbLink) - T - 1, GoTo[ReturnLinkRet,ALU=0];
*Otherwise, compare the cleanup link to the CV link.
	T _ prPrevPsbLink _ (Zero) + T + 1, DblGoTo[FCH1,.+2,ALU#0];
*Make the condition queue empty if the list of cleanup links terminates
*with a cleanup link pointing at itself.  It always winds up this way
*when timeouts have made the list empty because the final entry removed
*from the queue had a link field pointing at itself.
*If a nil cleanup link is encountered first, that psb is the queue head.
FindCleanupHead:
	T _ prPrevPsbLink _ (Zero) + T + 1, GoTo[FCH1,ALU#0];
*Clear the wakeup bit and the link field, preserving the abortable bit and
*any garbage in bits 0 to 2.
	  T _ prPsbIndexMask;
	  prCondition _ (Form-2[prCondition]) and not T, GoTo[UpdateConditionQueue];
FCH1:	PFetch1[prPda,prNextPsbLink], Call[TGetsPsbIndexMask];
	T _ (prNextPsbLink) and T;
	LU _ (prPrevPsbLink) - T - 1, GoTo[FindCleanupHead,ALU#0];
*Here, prPrevPsbLink points at queuehead+1.
	T _ (MNBR _ prPrevPsbLink) - 1;
FindQueueTail:
	PFetch1[prPda,prNextPsbLink];	*Fetch next link
	prPrevPsbLink _ T, Call[TGetsPsbIndexMask];
	prCondition _ (prCondition) and not T;	*condition.tail _ nil
	T _ (prNextPsbLink) and T;	*T _ Link.next
	LU _ (MNBR) - T - 1;	*IF Link.next # head then loop
	GoTo[FindQueueTail,ALU#0];
*Here, prPrevPsbLink points at the psb whose Link points at the queue head.
*Hence, prPrevPsbLink points at the queue tail.
	T _ prPrevPsbLink;
	prCondition _ (prCondition) or T;
UpdateConditionQueue:
	PStore1[prConditionQ,prCondition,0], Call[prRet];
ReturnLinkRet:
	APCTask&APC _ prReturnLink, GoTo[TGetsPsbIndexMask];

%Requeue is called to move a Psb:
	1. by Req&Res.  Req&Res is jumped to from
		EntryFailed (ReadyQ to MonitorQ on @ME and @MR);
		@REQ (MonitorQ to ConditionQ = any source Q to and dest Q)
		@MX (MonitorQ to ReadyQ)
		@MW (ReadyQ to ConditionQ)
		@SPP (ReadyQ to ReadyQ).
	2. by @MW (MonitorQ to ReadyQ).
	3. by WakeHead (ConditionQ to ReadyQ); WakeHead may have been called
	by prFault, Interrupt, @NC, or @BC.
	4. by CheckForTimeouts (unknown ConditionQ to ReadyQ).
Input:	prFlags		indicates source and dest queues
	prPsbIndex	PsbIndex of Psb to be requeued
	prPsbLink	4-word buffer contains PsbIndex^
	prCondition, prConditionQ/hi	setup if used
	prMonitor, prMonitorQ/hi	setup if used
Output:	prFlags		set to indicate requeue occurred
	prCondition	updated if ConditionQ modified
	prMonitor	updated if MonitorQ modified
	prReady		contents of ReadyQ header
Temps:	prNextPsbLink	Next link of PsbLink
	prPrevPsbIndex	Points to previous Psb
	prPrevPsbLink	PrevPsbIndex^.
Exits:	Return to caller

Dequeue timing (beginning at RequeueSub0):
  34 cycles if SourceQ is known & only 1 Psb.
  47 + 21/Psb cycles if SourceQ is known & more than 1 Psb
	(+ 14 cycles if header points at Psb being dequeued).
  24 cycles if SourceQ is unknown & Psb points at itself.
  40 + 21/Psb if SourceQ is unknown and the Psb doesn't point at itself.

Enqueue timing (ReqEnqueue to completion):
  41 cycles if DestQ header had nil link, else
  80 cycles if Psb priority .le. priority of existing entries, else
  90 + 23/Psb of .ge. priority.

I think that queues are ordinarily 1 long, and the Psb being dequeued or
enqueued is normally the highest priority in the queue, even when the queue
is long; only when the desination queue is the Ready queue do prospects for
large queues increase.  For a timeout scan, dequeuing from a CV queue should
normally take 24 cycles, but enqueuing onto the ready list might be longer.
130 cycles/requeue is a fair average.
%

RequeueSub0:
	xfWDC _ (xfWDC) + 1, UseCTask;
RequeueSub:
	T _ APCTask&APC, Call[SaveReturnLink];	*Returns PsbIndexMask in T
RequeuePsbFetched:
*Setup DBX and MWX for the WFA and WFB on the Link.next (etc.) fields.
*DBX_3, MWX_11b selects bits 3 through 3+11b
	prNextPsbLink _ 71C, Task;
	T _ (prPsbLink) and T;	*T _ PsbLink.next
*prCondition and prMonitor are valid if a monitor or condition queue is
*involved in the requeue, but prReady has not been loaded; fetch it now.
*Delay a little from RequeuPsbFetched to avoid waiting for the preceding
*PStore1 on entry from WakeHead.
	PFetch1[prPda,prReady,pdaReady!];
	prFlags _ (prFlags) or (RequeueOccurred), GoTo[ReqSQNotNil,R Even];
*The SourceQ is unknown; prPsbFlags.cleanup _ prPsbLink.next.
*If there is more than one Psb in the queue, follow links beginning with
*SourceQ until the pointer to  the Psb being dequeued is found; otherwise,
*no dequeuing is necessary.
	LU _ (prPsbIndex) - T;
*20 cycles from RequeueSub0 to here.
	CycleControl _ prNextPsbLink, prNextPsbLink _ T, NoRegILockOK, Skip[ALU#0];
	  prPsbFlags _ (WFB[prPsbFlags]) or T, GoTo[ReqEnqueue];
	prPsbFlags _ (WFB[prPsbFlags]) or T, GoTo[ReqFetchNext];

ReqSQNotNil:	*Here if the SourceQ is known.
	LU _ (prPsbIndex) - T;
*19 cycles from RequeueSub0 to here.
	CycleControl _ prNextPsbLink, prNextPsbLink _ T, NoRegILockOK, Skip[ALU#0];
*The Psb link points at itself, indicating a single Psb on the queue.
	  T _ 0C, GoTo[ReqStoreSQ];	*Zero SourceQ and done.
*Start search from the queue tail when the queue is known.
	Dispatch[prFlags,SourceQbit,2], Call[ReqQFetch];
*Follow links until the preceding Psb is found.  When done, prPrevPsbIndex
*will point to the Psb preceding the Psb being dequeued, and prPrevPsbLink
*will contain the Link word of the preceding Psb.
*Fetch PrevPsbIndex^ into PrevPsbLink.
ReqFetchNext:
	PFetch1[prPda,prPrevPsbLink];
ReqFetchPrev:
	prPrevPsbIndex _ T, Call[TGetsPsbIndexMask];	*Bypass kludge ok
	T _ (prPrevPsbLink) and T;
	LU _ (prPsbIndex) - T;
	Skip[ALU=0];
	  PFetch1[prPda,prPrevPsbLink], GoTo[ReqFetchPrev];
*We have found the preceding Psb. PrevPsbLink.next _ PsbLink.next
	T _ prNextPsbLink;
	prPrevPsbLink _ (WFB[prPrevPsbLink]) or T;
	T _ prPrevPsbIndex, Call[ReqFin];
*Now we have spliced out the Psb pointed to by PsbIndex from the queue.
*If SourceQ is unknown, we are done.
	Dispatch[prFlags,SourceQbit,2], Skip[R even];
	  GoTo[ReqEnqueue];
	T _ LdF[prPsbIndex,3,12], Disp[.+1];
	LU _ (LdF[prReady,3,12]) xor T, GoTo[.+3], At[GQDisp,0];
	LU _ (LdF[prMonitor,3,12]) xor T, GoTo[.+2], At[GQDisp,1];
	LU _ (LdF[prCondition,3,12]) xor T, At[GQDisp,2];
*If SourceQ points to the Psb being dequeued, point it at the previous Psb.
	T _ prPrevPsbIndex, GoTo[ReqEnqueue,ALU#0];
ReqStoreSQ:	*Queue.tail _ PrevPsbIndex
	  Dispatch[prFlags,SourceQbit,2], Call[ReqQStore];

ReqEnqueue:	*Now we are ready to insert the Psb into the dest queue.
	Dispatch[prFlags,DestQbit,2], Call[ReqQFetch];
	LU _ T;
*8 cycles from ReqEnqueue to here.
	GoTo[ReqDQNotNil,ALU#0];
*If DestQueue.tail = nil, point the Psb being enqueued to itself.
*Then point DestQ to the Psb being enqueued.
	T _ prPsbIndex;
	prPsbLink _ (WFB[prPsbLink]) or T, Call[ReqDQSNil];
	APCTask&APC _ prReturnLink, GoTo[ReqExit];

*If DestQ # nil, MNBR contains DestQ and T contains DestQ.tail.  Insert
*the Psb into DestQ according to priority.  First see if the Psb priority
*is <= the priority of the last Psb in DestQ.  If so, insert the Psb at the
*end of DestQ.  Fetch DestQueue.tail^ into PrevPsbLink.
ReqDQNotNil:
	PFetch1[prPda,prPrevPsbLink], Call[ReqGetPri];
*IF PrevPsbLink.priority >= Psb.priority THEN GoTo ReqAppend
	LU _ (LdF[prPrevPsbLink,0,3]) - T;
	T _ prPrevPsbLink, GoTo[ReqAppend,Carry];
*Continue if Psb priority is .ge. priority of the last Psb in the queue.
*Search the queue for the place to insert it.
ReqFindPri:
	T _ (prPsbIndexMask) and T;	*T _ PrevPsbLink.next
*Fetch PrevPsbLink.next^ into NextPsbLink
	PFetch1[prPda,prNextPsbLink], Call[ReqGetPri];
*IF Psb.priority > NextPsbLink.priority THEN GoTo ReqInsertPsb
	LU _ (LdF[prNextPsbLink,0,3]) - T;
	T _ prNextPsbLink, Skip[Carry];
	  T _ prPsbIndexMask, GoTo[ReqInsertPsb];
	MNBR _ prPrevPsbLink, prPrevPsbLink _ T, NoRegILockOK, GoTo[ReqFindPri];

*Priority is .le. the last Psb's in the queue.  Point the queue head to the
*Psb being enqueued.  Chain it at queue end.
ReqAppend:
	Dispatch[prFlags,DestQbit,2], Call[ReqDQStore];
*Come here when the priority of the Psb to be inserted is .gr. the priority
*of the Psb pointed to by PrevPsbLink.next.  PsbLink.next _ PrevPsbLink.next.
*Change PrevLink.next to point to the Psb being inserted.
ReqInsertPsb:
	T _ (prPrevPsbLink) and T;
	prPsbLink _ (WFB[prPsbLink]) or T;
*Now point PrevLink.next to Psb being enqueued.  PrevPsbLink.next _ PsbIndex.
	T _ prPsbIndex;
	prPrevPsbLink _ (WFB[prPrevPsbLink]) or T;
	PStore4[prPda,prPsbLink], Call[TGetsPsbIndexMask];
	T _ (MNBR) and T, Call[ReqFin];
	APCTask&APC _ prReturnLink;
ReqExit:
	xfWDC _ (xfWDC) - 1, Return;

ReqGetPri:
	T _ LdF[prPsbLink,0,3], Return;

ReqFin:	PStore1[prPda,prPrevPsbLink], GoTo[prRet];

ReqDQSNil:
	Dispatch[prFlags,DestQbit,2];
	PStore4[prPda,prPsbLink], Disp[ReqQS1];
ReqDQStore:
	T _ prPsbIndex, Disp[ReqQS1];
ReqQStore:
	Disp[.+1];
ReqQS1:	prReady _ (WFB[prReady]) or T, At[SQDisp,0];
	PStore1[prPda,prReady,pdaReady!], GoTo[TGetsPsbIndexMask];
	prMonitor _ (WFB[prMonitor]) or T, GoTo[StoreMonitor], At[SQDisp,1];
	prCondition _ (WFB[prCondition]) or T, At[SQDisp,2];
	PStore1[prConditionQ,prCondition,0], GoTo[TGetsPsbIndexMask];

ReqQFetch:
	T _ prPsbIndexMask, Disp[.+1];
	T _ (MNBR _ prReady) and T, Return, At[FQDisp,0];
	T _ (MNBR _ prMonitor) and T, Return, At[FQDisp,1];
	T _ (MNBR _ prCondition) and T, Return, At[FQDisp,2];

%Reschedule takes the first (i.e., highest priority) Psb on the ready queue
and configures the machine to run that process.  The scheduler is always
invoked if Requeue has modified ReadyQ.  Once started, a process runs
until it faults (page, WP, or frame), fails to enter a monitor, waits on a
conditon variable with no wakeups waiting, aborts, or is interrupted by a
microtask which wakes up a higher priority process.

Input:	LU		prFlags AND RequeueOccurred is pending
	LOCAL		points to local frame
	prCurrentPsb	points at currently running process (0 if none)
	prReady		points to tail of ReadyQ
Output:	prCurrentPsb	updated to point to highest priority Psb on ready
			queue for which a state vector is available.
	xfTemp		dest link (pointer to Psb) for Xfer
	xfMY		set to zero for Xfer
	xfBrkByte	set to 40400b for Xfer
	PCB		set to 1 to prevent Xfer faults from smashing the PC
	MemStat		set to Or[FromReschedule!,EarlyXfer!]C for xfer
	MDShi, LOCALhi, GLOBALhi	set to prPsbMds
The following temporaries are used:
	prPsbLink
	prState/hi	Base register pair for referencing Pda.state
	prStkP		to save StkP in SV
	prLocal		to save LOCAL in SV
Subroutines called:
	SavPCInFrame	in MesaOP3.Mc (uses xfOldPC)
Exits:	prTail		if no reschedule necessary
	Xfer		if reschedule occurred (in MesaOP3.Mc)
	kfcr		if xfWDC#0 (in MesaOP3.Mc)
	Crash		if no state vector available (in Fault.Mc)

Timing from Reschedule to RSFindRunnable:
   6 cycles if idle
  73 cycles if not preempted & no permanent SV.
  86 cycles if not preempted & permanent SV.
 121 cycles if preempted & permanent SV.
 149 cycles if preempted & no permanent SV.

Timing from RSFindRunnable to Xfer:
  85 cycles if minimal stack reload with permanent SV
     (+9 cycles if ME previously failed);
  93 cycles if minimal stack reload without permanent SV
     (+9 cycles if ME previously failed);
 115 cycles permanent SV reload;
 139 cycles reload without permanent SV.

Xfer adds about 66 cycles for this entry.  Some cycles can be saved by
jumping deeper into Xfer.

This totals to:
 300 cycles (=149+85+66) preempt & wakeup CV process
 278 cycles (=73+139+66) wait on CV & wakeup preempted process
%

*Reschedule only if requeue occurred and interrupts are not disabled.
*LU _ (prFlags) and (RequeueOccurred) preceded this mi.
*(This refinement allows NC and BC to be executed with interrupts disabled.).
ResIfReq:
	LU _ xfWDC, Skip[ALU#0];
	  LU _ NextInst[IBuf], CallX[prTailx];	*No requeue occurred
	PFetch1[prPda,prReady,pdaReady!], Skip[ALU=0];
	  LU _ NextInst[IBuf], CallX[prTailx];	*Interrupts disabled
	T _ prCurrentPsb, GoTo[Resc1];

Reschedule:
	LU _ xfWDC;
	T _ prCurrentPsb, GoTo[Resc1,ALU=0];
*This error occurs not only when the user has disabled interrupts, but also
*when a fault occurs during an Interrupt or during PSB requeuing.  Such a
*fault can occur when process data structures are non-resident or screwed
*up or when an io task page or write protect fault occurs (but io task
*page and WP faults cause an MP code).
	  LoadPage[opPage3];
	  xfSD _ T _ sRescheduleError, GoToP[.+1];
OnPage[opPage3];
	  xfWDC _ 0C, GoTo[kfcr];
OnPage[prPage];
*Set up StateHi.  If presently idle, don't save process.
Resc1:	prStateHi _ 400C, GoTo[RSFindRunnable,ALU=0];
*Fetch running process's Psb into prPsbLink, prPsbFlags, prPsbContext,
*and prPsbTimeout.
	PFetch4[prPda,prPsbLink], Task;
	T _ (prCurrentPsb) + (4C);
	PFetch4[prPda,prPsbMds], Task;
	T _ LOCAL;
*See if reschedule is due to an interrupt or fault.
	LU _ (prFlags) and (SaveStack);
	LU _ (prPsbLink) and (Permanent), GoTo[Resc2,ALU=0];
*Preempted.  23 cycles to here.
	prLocal _ T, LoadPage[opPage0], GoTo[.+3,ALU=0];
*Preempted and permanent StateVector assigned to the process.
	  T _ prPsbContext, GoToP[.+1];
OnPage[opPage0];
	  prState _ T, GoTo[Resc5];
*Preempted, no permanent SV--allocate SV at current priority.  Return with:
*(1) T _ prCurrentSAT _ ptr to the StateAllocTable entry.
*(2) prPtrToSV _ ptr to the first SV.
OnPage[prPage];
	T _ (pdaState), GoToP[.+1];
OnPage[opPage0];
	T _ (LdF[prPsbLink,0,3]) + T, Call[SetState1];
	T _ prPtrToSV;
	prState _ T, GoTo[.+3,ALU#0];
*No SV available is a fatal error; this should never happen because
*a SV was available when Reschedule started this process, and SPP will
*Reschedule if the priority changes.
	  LoadPageExternal[0];
	  T _ NoStateVectorError, GoToExternal[CrashLoc];	*MPC = 0116.
*Fetch ptr to next SV at this priority.
	PFetch1[prPda,prPtrToSV];
	prPsbContext _ T, Task;	*prPsbContext _ ptr to SV.
*Store ptr to next SV in SAT.
	T _ prCurrentSAT;
	PStore1[prPda,prPtrToSV];
Resc5:	T _ (SStkP&NStkP) xor (377C);
	prStkP _ T, LoadPage[prPage];
	prStkP _ LdF[prStkP,10,10], GoTo[.+1];
OnPage[prPage];
	T _ RSh[MDShi,10], Call[RescPsbFix];
*Timing from Reschedule to here:  44 cycles if permanent SV else 72 cycles.
*Even if StkP is 0, at least two stack words must be saved, so one PStore4
*is needed.  Subsequent PStores could be done only if StkP > 2, 6, etc., but
*time spent testing reduces the average gain and we are tight on space.
	PStore4[prState,Stack0,svStack!], NonQuadOK, Task;
	prPsbLink _ (prPsbLink) or (Preempted);
	PStore4[prState,Stack4,svStack4!], NonQuadOK, Call[prRet];
	PStore4[prState,Stack8,svStack8!], NonQuadOK, Task;
*Save prData and prData1 in SV (only meaningful for faults); smashing the
*next two words is ok since the SV's are 24b long.
	T _ svData;
	PStore4[prState,prData], Call[prRet];
*Store Stack12, Stack13, prStkP, and prLocal; the PStore4 register select
*wraps around, so the registers written are 15b, 16b, 17b, and 0.
	PStore4[prState,Stack12,svStack12!], NonQuadOK, GoTo[RSSavePsb];

*Not preempted.  22 cycles from Reschedule to here.
Resc2:	prPsbLink _ (prPsbLink) and not (Preempted), Skip[ALU#0];
*Not preempted and no permanent StateVector--save LOCAL in PSB.
	  prPsbContext _ T, GoTo[Resc3];
*Not preempted and permanent StateVector--save only LOCAL in StateVector.
	prLocal _ T, Task;
	T _ prPsbContext;
	prState _ T, Call[prRet];
*Store Stack12, Stack13, prStkP, and prLocal; the PStore4 register select
*wraps around, so the registers written are 15b, 16b, 17b, and 0.
	PStore4[prState,Stack12,svStack12!], NonQuadOK;
Resc3:	T _ RSh[MDShi,10], Call[RescPsbFix];
*Store prPsbLink, prPsbFlags, prPsbContext, prPsbMds into Current Psb.
RSSavePsb:
	T _ prCurrentPsb, LoadPage[xfPage1];	*Even placement
*SavPCinFrame in MesaOP3.mc does xfOldPC _ (2*PCB - 2*CODE + PCF) and
*T _ LOCAL-1.
	PStore4[prPda,prPsbLink], CallP[SavPCinFrame];
	LU _ (MemStat) and (Or[FromReschedule!,Trap!]C);
*Set GLOBAL to an impossible value so that Loadgc will always be called
*during the xfer out of the scheduler.  This is necessary if CODE, etc.
*become inconsistent during a fault or trap from the scheduler or during
*a nested trap.
	GLOBAL _ T, Skip[ALU#0];
	  PStore1[MDS,xfOldPC];
	T _ (prCurrentPsb) + (4C), Task;
	PStore4[prPda,prPsbMds];

RSFindRunnable:	*Fetch ReadyQ header = pointer to queue tail.
	MemStat _ FromReschedule;	*Start setting up MemStat for Xfer.
	T _ prReady, Call[FetchPsb];	*Fetch Tail Psb.
	prCurrentPsb _ T, GoTo[.+2];
RSFRLoop:
	LU _ (prReady) xor T;
	T _ prPsbIndexMask, GoTo[NoneReady,ALU=0];	*Go if end of ReadyQ
*Follow the link in the tail PSB to get the head PSB.
	T _ (prPsbLink) and T, Call[FetchPsb];
*Determine whether a SV is at the current priority.  Return with:
*(1) T _ prCurrentSAT _ ptr to the SAT entry.
*(2) prPtrToSV _ ptr to the first SV.
	prCurrentPsb _ T, LoadPage[opPage0];
	T _ (pdaState), CallP[SetState];
*If Link.preempted was true, then load the stack and go.
	LU _ (prPsbLink) and (Permanent), GoTo[RSLoadAndGo,R Odd];
*This process doesn't need to load the stack; jump if no permanent
*StateVector.
	StkP _ RZero, GoTo[RSFR1,ALU=0];
*Permanent StateVector--only LOCAL is of interest.
	T _ (prPsbContext) + (svLocal);
	PFetch1[prPda,xfMX];
RSFR3:	T _ prCurrentPsb, LoadPage[opPage0];
	LU _ (prPsbLink) and (EnterFailed), GoToP[.+1];
OnPage[opPage0];
	prPsbLink _ (prPsbLink) and not (EnterFailed), GoTo[RSFR2,ALU=0];
	Stack&+1 _ 0C;	*Push FALSE
	PStore4[prPda,prPsbLink], GoTo[RSFR2];

OnPage[prPage];
*StateVector must be available at current priority to run the process.
RSFR1:	LU _ prPtrToSV;
	T _ prCurrentPsb, GoTo[RSFRLoop,ALU=0];	*No, get next process.
	T _ prPsbContext;
	xfMX _ T, GoTo[RSFR3];

RSLoadAndGo:
	T _ prPsbContext, FreezeResult;
*Load Stack0..3.
	PFetch4[prPda,Stack0], NonQuadOK, FreezeResult;
*Skip to not free the SV, if it is permanent.
	prState _ T, Skip[ALU#0];	*Bypass kludge ok (prPda=0)
*Store prev. content of SAT in 1st word of freed SV to add this SV to the
*chain; smashing the next 3 words is ok.
	  PStore4[prPda,prPtrToSV], NonQuadOK, Call[RSLG1];
	Nop;
*Fetch the final two stack words, StkP, Local into RM 15b, 16b, 17b, and 0.
*(PFetch4 wraps the RM address from 17b back to 0.).
	PFetch4[prState,Stack12,svStack12!], NonQuadOK, Call[prRet];
	PFetch4[prState,Stack4,svStack4!], NonQuadOK, Call[prRet];
	PFetch4[prState,Stack8,svStack8!], NonQuadOK, Task;
	LU _ StkP _ prStkP;	*Load stack pointer.
	T _ prLocal, LoadPage[opPage0];
	xfMX _ T, GoToP[.+1];
OnPage[opPage0];
RSFR2:	T _ (prCurrentPSB) + (4C);
	PFetch1[prPda,MDShi];
***xfMY should be a don't care here.
*	xfMY _ 0C, Task;	*Source _ nil
***What about break byte handling here?
	xfBrkByte _ 40400C;
	T _ (prCurrentPSB) + (6C);
	PFetch1[prPda,fpSticky];
	T _ MDShi, LoadPage[wrMDSPage];
	LU _ MNBR _ xfMX, CallP[WrMDS1];
	LoadPage[xfPage1];	*Know that Normal = 0
	MemStat _ (MemStat) or (Or[EarlyXfer!,xfTypePSWITCH!]C), GoToP[RetGo];

*Establishes SAT entry using the current priority from prPsbLink.
*Returns with: (1) T _ prCurrentSAT _ ptr to the SAT entry.
*(2) prPtrToSV _ ptr to the first SV or 0 if no SV available.
*T _ ptr to the SAT entry for the current priority.
SetState:
	T _ (LdF[prPsbLink,0,3]) + T;
*Fetch ptr to first StateVector this priority.
SetState1:
	PFetch1[prPda,prPtrToSV];
*Save it in prCurrentSAT.
	prCurrentSAT _ T, Return;	*Bypass kludge ok (prPda=0)

OnPage[prPage];
*Store ptr to newly freed SV in StateAllocTable.
RSLG1:	T _ prCurrentSAT;
	PStore1[prPda,prPsbContext], GoTo[prRet];

RescPsbFix:
	prPsbMds _ T;
	T _ fpSticky;
	prPsbSticky _ T, Return;

OnPage[prPage];
SaveReturnLink:
	prReturnLink _ T, GoTo[TGetsPsbIndexMask];

FetchCurrentPsb:
	T _ prCurrentPsb;
FetchPsb:
	PFetch4[prPda,prPsbLink], GoTo[prRet];

StoreCurrentPsb:
	T _ prCurrentPsb;
	PStore4[prPda,prPsbLink], GoTo[prRet];


NoneReady:
	LoadPage[opPage0];
	T _ prCurrentPsb _ 0C, GoToP[.+1];	*Set to not running.
OnPage[opPage0];
	Call[P4Ret];
*Idle loop
	GoTo[IdleInt,IntPending];
P4Ret:	Return;

%Come here on Page, WriteProtect or Frame faults.  Condition queues affected
are:
	200060	Frame fault queue
	200061	Naked Notified on frame fault
	200062	Page fault queue
	200063	Naked Notified on page fault
	200064	Write protect fault queue
	200065	Naked Notified on WP fault

Input:	xBuf2		Value to restore to StkP
	prConditionQ	FaultOffset within Pda.  Used as base register
			to Fault[fi].queue and Fault[fi].condition.
	prData		Fault Parameter
Output:	prData(1)	For PageFault and WriteProtectFault convert prData to
			LongPtr to faulted page (page portion a 16 bit -1 if
			MapOutOfBounds)
Temps:	prFlags		SrcQ and DestQ spec. for RequeueSub and NWUXXX.
	prPsbIndex	Tell RequeueSub which Psb to requeue.
Subroutines called:
	BackPC (MesaOP0)
	RequeueSub
	CleanUpQueue
	NWUXXX (WakeHead and RequeueSub)
Exit:	Reschedule
%
*Restore StkP for entry from Fault.mc by GoToExternal.
	StkP _ xBuf2, At[prFaultLoc];	*opPage0
prBackPCFault:	*AllocFail in MesaESC enteres here.
	T _ (PCXReg) - 1, Call[BackPC];
*Set prConditionQ to Fault[fi].queue (pda + offset).
*Since Pda is 0, don't have to add it to fault offset.
prFault:	*xfTrap2 in MesaOP3 enters here
	LoadPage[prPage], At[prNoBackPCFaultLoc];
*The cleanup link may be non-zero when a fault happens and it must not be
*smashed.  The consequence is that CleanUpQueue is not called here, and REQ
*must be used instead of NC to restart the process after fault service.
	prConditionQhi _ 400C, CallP[FetchCurrentPsb];
	prFlags _ ReadyQtoConditionQ;	*400b=PdaHi
	prPsbIndex _ T, LoadPage[prPage];
	PFetch1[prConditionQ,prCondition,0], CallP[RequeueSub0];
	PFetch1[prConditionQ,prCondition,1], Task;
	prFlags _ ConditionQtoReadyQ;
	T _ prPsbIndexMask, LoadPage[prPage];
*Point prConditionQ pointing to Fault[fi].condition.
	prConditionQ _ (prConditionQ) + 1, CallP[CleanUpQueue];
*Cleanup interrupt[level].condition returns with PsbIndexMask in T.
*NWUXXX goes to WakeHead, if the queue is non-empty; otherwise, it sets
*the wakeup-waiting bit in the condition variable and returns.
	T _ (prCondition) and T, Call[NWUXXX];
*Does prConditionQ = Fault[frameFault].cond?
	LU _ (prConditionQ) xor (qFrameFaultCOs);
*Frame Fault doesn't convert prData.
	T _ LdF[prData,0,10], Skip[ALU=0];
*Convert page number to long pointer in prData and prData1 for Page or
*WriteProtect fault; otherwise, prData1 is "don't care".  Reschedule stores
*prData(1) in State.data.
	  prData _ LSh[prData,10];
*A fault always requeues the current process, so Reschedule will run some
*other process.  Always save the evaluation stack, prData, and prData1 on
*a fault.
	prData1 _ T, LoadPage[prPage], GoTo[IntExit1];

*Skip if Queue Nil; otherwise, set condition.wakeup _ TRUE
NWUXXX:	LoadPage[prPage], Skip[ALU=0];
	  PFetch1[prPda,prPsbIndex], GoToP[WakeHead];
	prCondition _ (prCondition) or (wakeup), GoToP[.+1];
OnPage[prPage];
	PStore1[prConditionQ,prCondition,0], GoTo[prRet];

%Jump to Interrupt from MesaOP0 knowing NWW#0 and xfWDC = 0 (wakeups are
waiting and not disabled); we know this because IntPending is set true by
NotifyInterrupt (in Initialize.Mc) only when NWW is made non-zero.
StkP is pointing at NWW (StkP+1 points at prTime and StkP+2 at prTicks) and
the saved value of StkP is in prIntSaveStkP.

NWW is zeroed, and WW is set to the previous contents of NWW; then bits in WW
are translated into naked notifies, each of which moves a process from a
condition variable queue to the ready queue or else sets the wakeupWaiting
bit of the condition variable.

xfWDC is set non-zero during the Interrupt routine to detect page and write
protect faults, which are illegal, during interrupt service.

I think that we get here once/field from the UTVFC task (= once per 1/77 sec)
and ? from the RDC task.

Input:	StkP		points at NWW
	prIntSaveStkP	value to restore to StkP
	NWW		mask of new wakeups waiting for service
Output:	prTime		updated if timer interrupt
	prTicks		updated if timer interrupt
Temps:	prConditionQ/hi	updated to point to a Condition in the Pda
	prCondition	Contents of ConditionQ^
	prPsbLink	4-word Psb buffer
	prPsbIndex	set to Condition.tail^ for RequeueSub
	WW		wakeups waiting
	IBuf-IBuf3	are available temps

Subroutines called:
	CleanUpQueue
	NWUXXX (WakeHead and RequeueSub)
Exits:	Reschedule

Timing:	~24 cycles from @NOP to Interrupt
	+15 to FindLevel (or 14 if RHMask[NWW]=0)
	+10 + Reschedule + (36+CleanUpQueue+WakeHead)*NOnes + 4*NZeroes =
	(24+15+10+300) + (36+27+20+130)*NOnes + 4*NZeroes =
	349 + 213*NOnes + 4*NZeroes
where NZeroes = number of zeroes in WW to the right of the left-most one;
4*NZeroes is accelerated by 33 cycles if the right 8 bits are all 0.

Since CheckForTimeouts uses bit 0 in NWW and is initiated with one other
interrupt whose bit is also in the left-half of NWW, its timing is about:
	~24 cycles from @NOP to Interrupt
	+14 cycles to FindLevel
	+28 cycles to skip the LHMask[NWW] zeroes
	+209*NOnes for other notifies
	+7 cycles to CheckForTimeouts
	+17+Reschedule for 2/3 of the wakeups (no timeout scan done)
	+27+Reschedule+[19*NProc]+(7+RequeueSub0)/timeout
		for the 1/3 of the wakeups that timeout
Assuming 150d processes, two timeouts, and one other interrupt, this totals
	90+300 + 209*NOnes = 599 cycles 2/3 of the time and
	100+300+2850 + 209*NOnes + 137/timeout = 3732 cycles 1/3 of the time
Total is (3732+599+599)*77/(3*10^7) = 1.27 percent of all cycles.

The above times assume 130 cycles for RequeueSub0, 300 cycles for
Reschedule, and 27 for CleanUpQueue (i.e., that the cleanup link is 0).
%

OnPage[opPage0];

Interrupt:	**Don't task here until after Stack_0 below.
	LU _ (Stack) and (377C);
	xfWDC _ (xfWDC) + (1000C), GoTo[.+3,ALU#0];
*Start with the middle interrupt level.
	  T _ RSh[Stack,10];
	  prConditionQ _ Sub[pdaLastInterrupt!,20]C, GoTo[Interrupt1];
*Start with the last interrupt level.
	T _ Stack;
	prConditionQ _ pdaLastInterrupt;
Interrupt1:
	Stack _ 0C, Task;
	WW _ T;
	prFlags _ ConditionQtoReadyQ;
FindLevel:	*Set ConditionQhi equal to PdaHi.
	prConditionQhi _ 400C, Call[.+1];
*Find the interrupt level
	WW _ RSh[WW,1], Skip[R Odd];
	  prConditionQ _ (prConditionQ) - (2C), Return;
*This level has an interrupt; level 0 reserved for CheckForTimeouts.
	LU _ (prConditionQ) - (pdaInterrupt), GoTo[.+3,ALU#0];
*This is the final interrupt; check for timeout scan; advance StkP from
*NWW to prTime for timeout scan.
	  Stack&+1, GoTo[CheckForTimeouts,ALU=0];
	  StkP _ prIntSaveStkP;
	PFetch1[prConditionQ,prCondition,0];
*This code is register critical--WW, prConditionQ/Qhi must survive
*CleanUpQueue, WakeHead, and Requeue.
	T _ prPsbIndexMask, LoadPage[prPage];
	T _ (prCondition) and T, CallP[CleanUpQueue1];	*Return PsbIndexMask in T
*Check condition.tail = nil
	T _ (prCondition) and T, Call[NWUXXX];
*Continue interrupt checking if WW .ne. 0
	LU _ WW;
	prConditionQ _ (prConditionQ) - (2C), GoTo[FindLevel,ALU#0];
*Reenable interrupts and Reschedule.
IntExit:
	xfWDC _ (xfWDC) - (1000C);
	LoadPage[prPage];
*Note: RequeueOccurred would have to be preserved following first
*RequeueSub call on a fault, if rescheduling became conditional.
IntExit1:
	prFlags _ (prFlags) or (SaveStack), GoToP[RescheduleCurrent];

%A tick is supposed to be between 15 and 60 msec; 3 field interrupts from
the display driver occur in 3000/77 msec (LF monitor = 40.4 msec) or
3000/60 msec (CSL monitor = 50 msec).

Timing = 27 + Reschedule + 19/PSB + (7+RequeueSub0)/timeout.
Typical numbers are 150 processes, 30 waiting on condition variables (?),
6 of the 30 with timeouts, and 2 or 3 timing out.
19 cycles/PSB is 0.73 percent of all cycles with 150 psbs.
%
CheckForTimeouts:
	Stack _ (Stack) - 1;	*prTime _ (prTime) - 1
*Fetch Psb count into WW
	PFetch1[prPda,WW,pdaCount!], Skip[ALU=0];
	  StkP _ prIntSaveStkP, GoTo[IntExit];
	prFlags _ (prFlags) or (SourceQNil);
*prTime _ tickSize; then advance StkP from prTime to prTicks.
	Stack _ 3C, Call[P4Push];
	Stack _ (Stack) + 1;	*Advance prTicks
*WW _ Psb count - 1.
	WW _ (WW) - 1, Skip[Carry'];
*Make prTicks count skip 0, so that 0, indicating "no timeout", cannot be
*confused with a timeout value.
	  Stack _ 1C;
	T _ prPsbIndex _ pdaBlock;

***Note: The quadword after the last PSB is not supposed to page fault, so it
***is supposed to be ok to fetch an extra quadword before exiting, but this
***requirement didn't make it into the Klamath release for some reason, so I
***had to waste 2 mi.

ChkTOL:	PFetch4[prPda,prPsbLink], Task;
	T _ Stack;
	WW _ (WW) - 1;
	prPsbTimeout _ (prPsbTimeout) - T, GoTo[ChkTOLLast,ALU<0];
	T _ prPsbIndex _ (prPsbIndex) + (PSBSize), GoTo[ChkTOL,ALU#0];
*A timeout adds 7+RequeueSub0
	prPsbIndex _ (prPsbIndex) - (PSBSize);
	LoadPage[prPage], Call[RequeueTimeout];
	T _ prPsbIndex _ (prPsbIndex) + (PSBSize), GoTo[ChkTOL];

RequeueTimeout:
	prPsbFlags _ (prPsbFlags) and not (waiting), GoToP[RequeueSub0];

ChkTOLLast:
	StkP _ prIntSaveStkP, Skip[ALU#0];
	  LoadPage[prPage], Call[RequeueTimeout];
  	GoTo[IntExit];

:END[MesaP];
x3(0,4939)(1,6879)\f2