:TITLE[MesaP]; % 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. Now 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) Eliminate prPsbIndexMask using Form-4 and 170000C. 2) Minimal stack check in SPP. 3) Check for source queue pointing elsewhere when Psb points at itself when dequeuing. 4) Eliminate the LU ← (WW) + (xC); from ChkTOL after final quadword in timeout table is zero filled. 5) Consider accelerating Xfer entry in Reschedule. 6) Make some of the MP codes be Reschedule Error traps if can decode what happened in the debugger. % *Psb (Process State Block) format. MC[PsbSize,4]; *Word 0: prPsbLink format. MC[enterFailed,100000]; *Bit 0: = 1 if entry to monitor failed. This means *the Psb is on a Monitor queue. *Bits 1..3: priority of Psb *Bits 4..15B: PsbIndex of next Psb in the queue. *Bit 16B: reserved MC[vector,1]; *Bit 17B: = 1 if psbContext points to a StateVector. %Word 1: prPsbFlags format. 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 Bit 3: unused. Bits 4..15b: PsbIndex of cleanup link. % MC[waiting,2]; *Bit 16b: = 1 if process waiting on a *condition queue. MC[abortPending,1]; *Bit 17b: = 1 if process will be aborted at next wait. *Word 2: Pointer to State Vector or frame. *Word 3: MDShi of process *Condition format. *Bits 0..3 = zero. *Bits 4..15b: PsbIndex of tail of condition queue. 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..3 = zero. ***BUT I SAW SIGN BIT NON-ZERO *Bits 4..15b: PsbIndex of tail of monitor queue. *Bit 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]. *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: ~14.5+43 = ~57.5 cycles in the ordinary case. @ME: prFlags ← MEflags, GoToP[MonitorDsp], At[EscD0,0]; *Monitor Exit. Stack contains long pointer to Monitor. *Timing: ~14.5+43 = ~57.5 cycles in the ordinary case. @MX: prFlags ← MXflags, GoToP[MonitorDsp], At[EscD0,1]; *Monitor Wait. Stack contains time, long pointer to Condition, and long pointer to Monitor. @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. @MR: prFlags ← MRflags, GoToP[MonAndCondDsp], At[EscD0,3]; *Notify Condition. Stack contains long pointer to Condition. @NC: prFlags ← NCflags, GoToP[ConditionDsp], At[EscD0,4]; *Broadcast Condition. Stack contains long pointer to Condition. @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, LoadPage[prPage], GoToP[.+1], At[EscD0,17]; OnPage[xfPage1]; PFetch4[prPda,prPsbLink], GoToP[.+1]; %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. % OnPage[prPage]; prFlags ← SPPflags, Task; prPsbIndex ← T; T ← LSh[Stack&-1,14]; prPsbLink ← (LdF[prPsbLink,4,14]) 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; :IF[LPChecking]; ************************************ LU ← LdF[Stack,0,12], Call[FixConditionQueue]; *Trigger write protect fault if protected. PStore1[prConditionQ,prCondition,0]; LU ← LdF[Stack,0,12], Call[FixMonitor]; :ELSE; ********************************************** T ← LSh[Stack&-1,10], Call[FixConditionQueue]; *Trigger write protect fault if protected. PStore1[prConditionQ,prCondition,0]; T ← LSh[Stack&-1,10], Call[FixMonitor]; :ENDIF; ********************************************* *Don't fetch Monitor if NIL source. Other opcodes allow 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. 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]; T ← prCondition, Call[xfRet]; PStore1[prMonitorQ,prMonitor,0]; LU ← (prMonitor) xor T; T ← (SStkP&NStkP) + 1, LoadPage[prPage], GoTo[ProcessOps1,ALU#0]; prFlags ← REQSameFlags, GoTo[.+1] OnPage[prPage]; Dispatch[prFlags,5,4], DblGoTo[ProcessOps3,processOps2,H2Bit8']; OnPage[xfPage1]; :IF[LPChecking]; ************************************ MonAndCondDsp: LU ← LdF[Stack,0,12], Call[FixConditionQueue]; *Trigger write protect fault if protected. PStore1[prConditionQ,prCondition,0]; MonitorDsp: LU ← LdF[Stack,0,12], Call[FixMonitor]; :ELSE; ********************************************** 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]; :ENDIF; ********************************************* MonitorFetch: 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[ProcessOps3,H2Bit8']; OnPage[prPage]; ProcessOps2: LoadPageExternal[FaultPage]; GoToExternal[StackErrorLoc]; ProcessOps3: 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. :IF[LPChecking]; ************************************ ConditionDsp: LU ← LdF[Stack,0,12], Call[FixConditionQueue]; *Trigger write protect fault if protected PStore1[prConditionQ,prCondition,0], GoTo[ProcessOps]; FixConditionQueue: T ← LSh[Stack&-1,10], Skip[ALU=0]; *Long pointer T ← (Zero) - 1; *Cause map out of bounds. prConditionQhi ← T; :ELSE; ********************************************** ConditionDsp: T ← LSh[Stack&-1,10], Call[FixConditionQueue]; *Trigger write protect fault if protected PStore1[prConditionQ,prCondition,0], GoTo[ProcessOps]; FixConditionQueue: prConditionQhi ← T; :ENDIF; ********************************************* 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. :IF[LPChecking]; ************************************ FixMonitor: T ← LSh[Stack&-1,10], Skip[ALU=0]; *Long pointer prMonitorQhi ← (Zero) - 1, Skip; *Cause map out of bounds. prMonitorQhi ← T; :ELSE; ********************************************** FixMonitor: prMonitorQhi ← T; :ENDIF; ********************************************* T ← Stack&-1; prMonitorQ ← T, Return; PFetch4[PCB,IBuf,4], GoToP[MesaRefill], At[LShift[prPage,10],377]; %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 prFlags MonitorQ to ReadyQ T points at CurrentPsb Output: prPsbIndex CurrentPsb for Requeue prPsbLink four-word buffer contains CurrentPsb Subroutines called: CleanUpQueue RequeueSub Exits: Reschedule % @MW1: T ← prPsbIndexMask, Call[CleanUpQueue], At[ProcessDisp,MWloc]; 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 abort. LU ← (prCondition) and (abortable); LU ← (prPsbFlags) and (AbortPending), Skip[ALU#0]; PFetch1[prPda,prPdaTimeout,pdaTimeout!], GoTo[MW3]; PFetch1[prPda,prPdaTimeout,pdaTimeout!], Skip[ALU=0]; LU ← (prFlags) and (RequeueOccurred), GoTo[ResIfReq]; *Abort *If no wakeup is waiting, set timeout and queue prCurrentPsb on ConditionQ. MW3: prCondition ← (prCondition) and not (wakeup), GoTo[MW4,R Even]; 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]; MW4: LU ← prWaitCount; *LU ← LdF[prPsbFlags,4,12]; *LU ← prWaitCount, GoTo[.+3,ALU=0]; *Put timeout in timeout table. * LoadPageExternal[0]; * T ← CULError, GoToExternal[CrashLoc]; *138d MW with CUL#0 *Jump to zero the timeout. *Use StkP to address prTicks (outside RM 0-77) prSaveStkP ← IP[prTicks]C, GoTo[MW5,ALU=0]; T ← (SStkP&NStkP) xor (377C), Call[prStkPSwap]; **Unnecessary to restore StkP because minimal stack. T ← Stack; *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. LU ← (prWaitCount) + T; prWaitCount ← (prWaitCount) + T, UseCOutAsCIn; *Set up prFlags to requeue from ReadyQ to ConditionQ. Initially, we were set *up to go MonitorQ to ReadyQ. MW5: prFlags ← ReadyQtoConditionQ; T ← RSh[prCurrentPsb,2], Call[AddTimeout]; PStore1[prPda,prWaitCount], Call[prRet]; *Psb.waiting ← TRUE. prPsbFlags ← (prPsbFlags) or (waiting), GoTo[Req&Res]; prStkPSwap: prSaveStkP ← T, StkP ← prSaveStkP, NoRegILockOK, Return; %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: Reschedule % @NC1: @BC1: T ← prPsbIndexMask, Call[CleanUpQueue], At[ProcessDisp,NCBCloc]; BCLoop: T ← prCondition ← (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]; PFetch1[prPda,prPdaTimeout,pdaTimeout!], Call[TGetsPsbIndexMask]; *Fetch PsbIndex↑ into 4-word Psb buffer. T ← prPsbIndex ← (prPsbIndex) and T, Call[FetchPsb]; *Zero timeout. T ← RSh[prPsbIndex,2], Call[AddTimeout]; PStore1[prPda,RZero]; *Psb.waiting ← FALSE. prPsbFlags ← (prPsbFlags) and not (waiting), 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 ← prPsbIndexMask; 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 will have 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 3. 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←4, MWX←11b selects bits 4 through 4+11b prNextPsbLink ← 111C, Call[TGetsPsbIndexMask]; 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,4,12], Disp[.+1]; LU ← (LdF[prReady,4,12]) xor T, GoTo[.+3], At[GQDisp,0]; LU ← (LdF[prMonitor,4,12]) xor T, GoTo[.+2], At[GQDisp,1]; LU ← (LdF[prCondition,4,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,1,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,1,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,1,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 the ready queue. 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 ready queue Output: prCurrentPsb updated to point to highest priority Psb on ready queue for which a state vector is available. xfMX 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 Normal for Fault.Mc 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 xfTemp1) 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 54 cycles to save state for minimal stack opcode 132 cycles to save state for faulted or interrupted process. Timing from RSFindRunnable to Xfer: 77 cycles if minimal stack reload (+9 cycles if ME previously failed); 115 cycles otherwise. Xfer adds about 51 cycles for this entry. Some cycles can be saved by jumping deeper into Xfer. % *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. xfWDC ← 0C; LoadPage[opPage3]; T ← sRescheduleError, GoToP[kfcr]; *Set up StateHi. If presently idle, don't save process. Resc1: prStateHi ← 400C, GoTo[RSFindRunnable,ALU=0]; *Fetch the running Psb into prPsbLink, prPsbFlags, prPsbContext, prPsbMds. PFetch4[prPda,prPsbLink], Task; T ← LOCAL; *See if reschedule is due to an interrupt or fault. LU ← (prFlags) and (SaveStack); *Prepare to save LOCAL in Psb. Need only save the Psb when not preempted. prLocal ← T, GoTo[.+3,ALU#0]; prPsbContext ← (Zero) or T; prPsbLink ← (prPsbLink) and not (vector), GoTo[RSSavePsb]; *Allocate a state vector at the current priority. Return with: *(1) T ← prCurrentSAT ← ptr to the StateAllocTable entry. *(2) prPtrToSV ← ptr to the first SV. T ← (pdaState), Call[SetState]; prPsbLink ← (prPsbLink) or (vector); *Link.vector ← TRUE 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]; T ← 377C; T ← (NStkP) xor T, Task; prStkP ← T; *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, Call[prRet]; PStore4[prState,Stack4,svStack4!], NonQuadOK, Call[prRet]; PStore4[prState,Stack8,svStack8!], NonQuadOK, 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, 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]; *Store prPsbLink, prPsbFlags, prPsbContext, prPsbMds into Current Psb. RSSavePsb: T ← prCurrentPsb, LoadPage[xfPage1]; *Even placement *SavPCinFrame clobbers xfTemp1 (RM 73 = prPrevPsbIndex) and uses LOCAL. PStore4[prPda,prPsbLink], Call[SavPCinFrame]; RSFindRunnable: *Fetch ReadyQ header = pointer to queue tail. PCB ← 1C; *Set PCB to illegal value for Xfer. T ← prReady, Call[FetchPsb]; *Fetch Tail Psb. prCurrentPsb ← T, Skip; RSFRLoop: LU ← (prReady) xor T; T ← prPsbIndexMask, GoTo[NoneReady,ALU=0]; *Go if end of ReadyQ T ← (prPsbLink) and T, Call[FetchPsb]; *Verify SV at the current priority. Return with: *(1) T ← prCurrentSAT ← ptr to the SAT entry. *(2) prPtrToSV ← ptr to the first SV. prCurrentPsb ← T; T ← (pdaState), Call[SetState]; *Link.vector ← 0; if Link.vector was true, then loadstate and run. prPsbLink ← (prPsbLink) and not (vector), GoTo[RSLoadAndGo,R Odd]; StkP ← RZero; *StateVector must be available at current priority to run the process. LU ← prPtrToSV; T ← prCurrentPsb, GoTo[RSFRLoop,ALU=0]; *No, get next process. *This process is runnable and doesn't need to LoadStack. LoadPage[opPage0]; *Link.enterFailed ← FALSE. If not enter failed, goto RSXfer prPsbLink ← (prPsbLink) and not (EnterFailed), GoToP[RSXfer,R>=0]; OnPage[opPage0]; Stack&+1 ← 0C; *Push[FALSE] PStore4[prPda,prPsbLink], GoTo[RSXfer]; OnPage[prPage]; RSLoadAndGo: T ← prPsbContext, LoadPage[opPage0]; *Load Stack0..3. PFetch4[prPda,Stack0], NonQuadOK, CallP[RSLG1]; *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. *Store ptr to newly freed SV in StateAllocTable. T ← prCurrentSAT, LoadPage[opPage0]; PStore1[prPda,prPsbContext], GoToP[.+1]; OnPage[opPage0]; T ← prLocal, Skip; RSXfer: T ← prPsbContext; xfMX ← T; T ← prPsbMds, LoadPage[wrMDSPage]; MDShi ← T, Call[WrMDS1]; *PCB was set to 1 earlier. T ← xfMY ← 0C; *Source ← nil MemStat ← T, LoadPage[xfPage1]; *Know that Normal = 0 **What about break byte handling here?? xfBrkByte ← 40400C, GoToP[Xfer]; RSLG1: prState ← T; *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, GoTo[P4Ret]; OnPage[prPage]; *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,1,3]) + T; *Fetch ptr to first StateVector this priority. PFetch1[prPda,prPtrToSV]; *Save it in prCurrentSAT. prCurrentSAT ← T, Return; *Bypass kludge ok (prPda=0) SaveReturnLink: prReturnLink ← T, Return; FetchCurrentPsb: T ← prCurrentPsb; FetchPsb: PFetch4[prPda,prPsbLink], GoTo[prRet]; StoreCurrentPsb: T ← prCurrentPsb; PStore4[prPda,prPsbLink], GoTo[prRet]; AddTimeout: T ← (prPdaTimeout) + T, Return; 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: T FaultOffset within Pda 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: prConditionQ Used as base-reg-ptr to Fault[fi].queue and Fault[fi].condition. prFlags SrcQ and DestQ spec. for RequeueSub and NWUXXX. prPsbIndex Tell RequeueSub which Psb to requeue. Subroutines called: RequeueSub CleanUpQueue NWUXXX (WakeHead and RequeueSub) Exit: Reschedule % OnPage[opPage0]; *Set prConditionQ to Fault[fi].queue (pda + offset). prFault: *Since Pda is 0, don't have to add it to fault offset. prConditionQ ← T, LoadPage[prPage], At[prFaultLoc]; *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 prIntPdaTimeout pointer into timeout table prIntPsbIndex pointer to Psb matching timeout IBuf-IBuf3 quadword from timeout table 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 + (35+CleanUpQueue+WakeHead)*NOnes + 4*NZeroes = (24+15+10+260) + (35+27+22+130)*NOnes + 4*NZeroes = 309 + 214*NOnes + 4*NZeroes where NZeroes is the 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. The above times assume 130 cycles for RequeueSub0, 260 cycles for Reschedule, and 27 for CleanUpQueue (i.e., that the cleanup link is 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 +210*NOnes for other notifies +9 cycles to CheckForTimeouts +14+Reschedule for 2/3 of the wakeups (no timeout scan done) +43+Reschedule+[28*(NProc+3)/4]+~(35+RequeueSub0)/timeout for the 1/3 of the wakeups that timeout Assuming 150d processes, and two timeouts, this totals to 89+260 + 210*NOnes = 563 cycles 2/3 of the time and 118+260+1064 + 210*NOnes + 165/timeout = 1982 cycles 1/3 of the time Total interference is (1986+563+563)*77/(3*10↑7) = 0.80 percent of all cycles. % OnPage[opPage0]; Interrupt: LU ← (Stack) and (377C); xfWDC ← (xfWDC) + (1000C), GoTo[.+3,ALU#0]; T ← RSh[Stack,10]; prConditionQ ← Sub[pdaLastInterrupt!,20]C, GoTo[Interrupt1]; T ← Stack; *Start with the last interrupt level. 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: cannot resume program after timeout scan unless IBuf is reloaded; *also RequeueOccurred must be preserved following first RequeueSub call *on a fault, if rescheduling were to become 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 = 43 + Reschedule + 28/quadentry + ((28 to 41)+RequeueSub0)/timeout. *Typical numbers are 150 processes, 30 waiting on condition variables (?), *6 of the 30 with timeouts, and 2 or 3 timing out. *7 cycles/psb is 0.27 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); Stack ← 3C; *prTime ← tickSize PFetch1[prPda,prIntPdaTimeout,pdaTimeout!]; *Advance StkP from prTime to prTicks; offset PsbIndex by -4*PsbSize for loop. prIntPsbIndex ← Sub[pdaBlock!,20]C, 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 ← prIntPdaTimeout ← (prIntPdaTimeout) + (RShift[pdaBlock!,2]C); *Note: The 0th timeout table entry is on a 16d-word boundary, so the loop *can begin with a PFetch4. The quadword after the last timeout table *quadword won't page fault (it is in a state vector), so it is ok to fetch *an extra quadword before exiting. *Eliminate the LU ← (WW) - (xC) microinstructions if all unused entries in *the final timeout table quadword are known to be 0. *Replace ALU#0 by ALU>=0 branch condition if maximum timeout is 77776b. ChkTOL: PFetch4[prPda,IBuf]; *Fetch next 4 timeout table entries prIntPsbIndex ← (prIntPsbIndex) + (20C), Task; T ← Stack; WW ← (WW) - (4C), Skip[R>=0]; StkP ← prIntSaveStkP, GoTo[IntExit]; LU ← (IBuf) - T; ChkTOL1: LU ← (IBuf1) - T, GoTo[ChkTO0,ALU#0]; T ← prIntPsbIndex; IBuf ← 0C, GoTo[TimOut]; ChkTO0: LU ← (IBuf2) - T, GoTo[ChkTO1,ALU#0]; T ← (prIntPsbIndex) + (4C); LU ← (WW) + (3C); IBuf1 ← 0C, DblGoTo[ChkTOX,TimOut,ALU<0]; ChkTO1: LU ← (IBuf3) - T, GoTo[ChkTO2,ALU#0]; T ← (prIntPsbIndex) + (10C); LU ← (WW) + (2C); IBuf2 ← 0C, DblGoTo[ChkTOX,TimOut,ALU<0]; ChkTO2: T ← prIntPdaTimeout ← (prIntPdaTimeout) + (4C), GoTo[ChkTOL,ALU#0]; prIntPdaTimeout ← (prIntPdaTimeout) - (4C); T ← (prIntPsbIndex) + (14C); LU ← (WW) + (1C); IBuf3 ← 0C, DblGoTo[ChkTOX,TimOut,ALU<0]; ChkTOX: StkP ← prIntSaveStkP, GoTo[IntExit]; *A timeout adds 22 + (6, 11, 14, or 19) + RequeueSub0 TimOut: PFetch4[prPda,prPsbLink]; prPsbIndex ← T; T ← prIntPdaTimeout, Task; PStore4[prPda,IBuf]; LoadPage[prPage]; prPsbFlags ← (prPsbFlags) and not (waiting), CallP[RequeueSub0]; T ← Stack, GoTo[ChkTOL1]; :END[MesaP];