:TITLE[MesaP];
%
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?
%



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):
0Waiting for join
1Transient state between normally running detached process and
state 3
2Transient state between 0 and 4
3Transient state between 1 and 5
4Dead process (formerly attached=expected to join)
5Dead process (formerly detached=did not expect to join)
6Normally running attached process
7Normally 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:

prCurrentPsbContains PsbIndex of the current Psb. This points to the front
of the ready queue.
prPda,prPdaHiThis 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.
prPsbIndexMaskThis contains a mask for the PsbIndex
prTimeDecremented by 1 each scan line. When 0, CheckForTimeouts
sets it back to TickSize (3) and adds 1 to prTicks.
prTicksCurrent tick count for timeout clock.

Other registers:

prFlagsHolds Opcode dispatch values and flags (described below)

bit 00 =>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 11b0 =>Requeue not done
1 =>Requeue done
bits 12b-15bUnused
bit 16b1 =>Reschedule entered on Interrupt or fault; save stack
0 =>Don’t save stack.
bit 17b0 =>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:prMonitorQbase register pair points to Monitor
prMonitorcontains MonitorQ↑
Tpoints at CurrentPsb
Exits:EntryFailedif 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:prMonitorQbase register pair points to Monitor
prMonitorcontains MonitorQ↑
Tpoints 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:prMonitorQbase register pair points to Monitor
prMonitorMonitorQ↑
prConditionQbase register pair points to Condition
prConditionConditionQ↑
prWaitCounttime out value
prFlagsMonitorQ to ReadyQ
Tpoints at CurrentPsb
Output:prPsbIndexCurrentPsb for Requeue
prPsbLinkfour-word buffer contains CurrentPsb
Subroutines called:
CleanUpQueue
RequeueSub
Exits:Reschedule
%

@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:prMonitorQbase register pair points to Monitor
prMonitorcontains MonitorQ↑
prConditionQbase register pair points to Condition
prConditioncontains ConditionQ↑
prFlagsReadyQ to MonitorQ
Tpoints at CurrentPsb
Subroutines called:
CleanUpQueueif enter successful
Exits:EntryFailedif enter unsuccessful, else
BackSPPCandTrapif 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:prConditionQbase register pair points to Dest queue (if needed)
prMonitorQbase register pair points to Source queue (if needed)
prPsbIndexpoints 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:prConditionQbase register pair points to Condition
prConditionConditionQ↑
prFlagsConditionQ to ReadyQ; plus Broadcast bit (bit 0) for
Broadcast
Exits:Reschedule
%
@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:prConditionQbase register pair points to Condition
prPsbIndexCondition.tail↑ for Requeue
Output:prPsbLinkfour-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:prConditionQbase register pair points to Condition
prConditionConditionQ↑
TprPsbIndexMask
Output:prConditionupdated ConditionQ↑
TPsbIndexMask
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:prFlagsindicates source and dest queues
prPsbIndexPsbIndex of Psb to be requeued
prPsbLink4-word buffer contains PsbIndex↑
prCondition, prConditionQ/hisetup if used
prMonitor, prMonitorQ/hisetup if used
Output:prFlagsset to indicate requeue occurred
prConditionupdated if ConditionQ modified
prMonitorupdated if MonitorQ modified
prReadycontents of ReadyQ header
Temps:prNextPsbLinkNext link of PsbLink
prPrevPsbIndexPoints to previous Psb
prPrevPsbLinkPrevPsbIndex↑.
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:LUprFlags AND RequeueOccurred is pending
LOCALpoints to local frame
prCurrentPsbpoints at currently running process (0 if none)
prReadypoints to tail of ReadyQ
Output:prCurrentPsbupdated to point to highest priority Psb on ready
queue for which a state vector is available.
xfTempdest link (pointer to Psb) for Xfer
xfMYset to zero for Xfer
xfBrkByteset to 40400b for Xfer
PCBset to 1 to prevent Xfer faults from smashing the PC
MemStatset to Or[FromReschedule!,EarlyXfer!]C for xfer
MDShi, LOCALhi, GLOBALhiset to prPsbMds
The following temporaries are used:
prPsbLink
prState/hiBase register pair for referencing Pda.state
prStkPto save StkP in SV
prLocalto save LOCAL in SV
Subroutines called:
SavPCInFramein MesaOP3.Mc (uses xfOldPC)
Exits:prTailif no reschedule necessary
Xferif reschedule occurred (in MesaOP3.Mc)
kfcrif xfWDC#0 (in MesaOP3.Mc)
Crashif 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);
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:
200060Frame fault queue
200061Naked Notified on frame fault
200062Page fault queue
200063Naked Notified on page fault
200064Write protect fault queue
200065Naked Notified on WP fault

Input:xBuf2Value to restore to StkP
prConditionQFaultOffset within Pda. Used as base register
to Fault[fi].queue and Fault[fi].condition.
prDataFault Parameter
Output:prData(1)For PageFault and WriteProtectFault convert prData to
LongPtr to faulted page (page portion a 16 bit -1 if
MapOutOfBounds)
Temps:prFlagsSrcQ and DestQ spec. for RequeueSub and NWUXXX.
prPsbIndexTell 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:StkPpoints at NWW
prIntSaveStkPvalue to restore to StkP
NWWmask of new wakeups waiting for service
Output:prTimeupdated if timer interrupt
prTicksupdated if timer interrupt
Temps:prConditionQ/hiupdated to point to a Condition in the Pda
prConditionContents of ConditionQ↑
prPsbLink4-word Psb buffer
prPsbIndexset to Condition.tail↑ for RequeueSub
WWwakeups waiting
IBuf-IBuf3are 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];