*-----------------------------------------------------------
Title[Process.mc...November 19, 1982 11:00 AM...Taft];
* Processes (PrincOps, chapter 10)
*-----------------------------------------------------------
%
CONTENTS, by order of occurence
Process instructions
ME Monitor Entry
MX Monitor Exit
MW Monitor Wait
MR Monitor Reentry
NC Notify Condition
BC Broadcast Condition
REQ Requeue
SPP Set Process Priority
DI Disable Interrupts
EI Enable Interrupts
Scheduling
MesaFault Fault handling
MesaReschedTrap Reschedule trap
InterruptLongRunningOpcode Reschedule called explicitly from emulator
MesaInterrupt Interrupt handling
CheckForTimeouts Check for process timeouts
MesaReschedule PrincOps Reschedule operation
Subroutines
Pop2MinimalStack Prepare 2 long pointer arguments
Pop1MinimalStack Prepare 1 long pointer argument
FetchCPFlags Fetch current process's flags
FetchCPLink Fetch current process's link
TestMonitorLock Test and set monitor lock
EnterFailed Handle failure to enter monitor
ExitMonitor Exit from monitor
NotifyWakeup Perform naked notify
WakeHead Awaken head process on CV queue
Requeue Move process from one queue to another
CleanUpCVQueue Clean up condition queue
%
TopLevel;
*-----------------------------------------------------------
* Base registers
*-----------------------------------------------------------
* PDA * Process data area -- permanently assigned
* Following two registers must be IFU-addressable and mutually xor 1.
BR[MLBR, 34]; * Monitor lock
BR[CVBR, 35]; * Condition variable
BR[RQBR, IP[PDA]]; * Ready queue -- know it is word 0 of the PDA
*-----------------------------------------------------------
* R register usage
*-----------------------------------------------------------
* Permanently assigned:
* PSB Process State Block (PsbIndex*SIZE[ProcessStateBlock])
* PTC Process Timeout Count, in ~50 ms ticks
* WDC Wakeup Disable Counter
* WP Wakeups Pending
* TickCount Counter to divide down vertical field interrupts to make ticks
* IndexMask Constant mask for extracting Q.tail words
* RTemp0-3 are used for general scratch purposes.
* The remaining RTemps are uniformly assigned for specific purposes:
RME[Process, RTemp4]; * -> PSB being worked on
RME[DQBRReg, RTemp5]; * MemBase value for Requeue destination queue
* B0=1 => Requeue has been done
RME[SQBRReg, RTemp6]; * MemBase value for Requeue source queue
* B15=1 => source queue is NIL
* BRConst[XX] generates a constant to select base register XX, and with
* bit 0 = 1 to set the Requeue flag in DQBRReg (if relevant).
M[BRConst, Add[100000, LShift[IP[#1], 10]]C];
*-----------------------------------------------------------
* Process/monitor data structures
*-----------------------------------------------------------
* Priority: TYPE = [0..7];
* Note: a Queue has the same structure as the words containing
* CV.tail, ML.tail, PSBL.next, and PSBF.cleanup.
* QueueHandle: LONG POINTER TO Queue;
* Queue: TYPE = MACHINE DEPENDENT RECORD [
* reserved1 (0: 0..3): [0..17B] ← 0,
MC[Q.tail, 7774]; * tail (0: 4..13): PsbIndex,
* reserved2 (0: 14..15): [0..3];
MC[shcQ.tail, 44]; * ShC for masking Q.tail: Count = 0, LMask = 4, RMask = 2
* PsbHandle: TYPE = POINTER TO ProcessStateBlock; -- PDA-relative
* PsbIndex: TYPE = [0..1024);
* Invariant: for any given PSB, PsbHandle = 4*PsbIndex.
* ProcessStateBlock: TYPE = MACHINE DEPENDENT RECORD [
MC[PSB.link, 0]; * link (0): PsbLink,
MC[PSB.flags, 1]; * flags (1): PsbFlags,
MC[PSB.context, 2]; * context (2): POINTER, -- to Frame or StateVector
MC[PSB.mds, 3]; * mds (3): CARDINAL ];
MC[sizePSB, 4]; Set[logSizePSB, 2];
* PsbLink: TYPE = MACHINE DEPENDENT RECORD [
MC[PSBL.failed, 100000]; * failed (0: 0..0): BOOLEAN,
MC[PSBL.priority, 70000]; * priority (0: 1..3): Priority,
MC[PSBL.next, 7774]; * next (0: 4..13): PsbIndex,
* permanent (0: 14..14): BOOLEAN,
MC[PSBL.preempted, 1]; * preempted (0: 15..15): BOOLEAN ]; -- know this is bit 15
* PsbFlags: TYPE = MACHINE DEPENDENT RECORD [
* available (0: 0..2): [0..7],
* reserved (0: 3..3): BIT ← 0,
MC[PSBF.cleanup, 7774]; * cleanup (0: 4..13): PsbIndex,
MC[PSBF.waiting, 2]; * waiting (0: 14..14): BOOLEAN, -- know this is bit 14
MC[PSBF.abort, 1]; * abort (0: 15..15): BOOLEAN ]; -- know this is bit 15
* Condition: TYPE = MACHINE DEPENDENT RECORD [
* reserved (0: 0..3): [0..17B] ← 0,
MC[CV.tail, 7774], * tail (0: 4..13): PsbIndex,
MC[CV.abortable, 2]; * abortable (0: 14..14): BOOLEAN,
MC[CV.wakeup, 1]; * wakeup (0: 15..15): BOOLEAN ]; -- know this is bit 15
* Monitor: TYPE = MACHINE DEPENDENT RECORD [
* reserved (0: 0..3): [0..17B] ← 0,
MC[ML.tail, 7774]; * tail (0: 4..13): PsbIndex,
* available (0: 14..14): BIT,
MC[ML.locked, 1]; * locked (0: 15..15): BOOLEAN ]; -- know this is bit 15
* StateVector: TYPE = MACHINE DEPENDENT RECORD [
MC[SV.stack, 0]; * stack: ARRAY[0..7] OF UNSPECIFIED,
MC[SV.stkp, 16]; * breakbyte, stkp: BYTE,
MC[SV.frame, 17]; * frame: ControlLink,
MC[SV.data, 20]; * data: ARRAY[0..1] OF UNSPECIFIED ];
* TimeoutVector: TYPE = ARRAY PsbIndex OF TICKS;
* FaultIndex: TYPE = [0..7];
* InterruptLevel: TYPE = [0..WordSize);
* Process Data Area (PDA) format, relative to PDA base register
* ProcessDataArea: TYPE = MACHINE DEPENDENT RECORD [
* SELECT OVERLAID * FROM
* header => [
MSC[PDA.ready, 0]; * ready: Queue,
MSC[PDA.count, 1]; * count: CARDINAL, -- number of PSBs in PDA
MSC[PDA.timeout, 2]; * timeout: POINTER TO TimeoutVector,
* available: ARRAY [3..7] OF UNSPECIFIED,
MC[PDA.state, 10]; * state: ARRAY Priority OF POINTER TO StateVector,
MC[PDA.interrupt, 20]; * interrupt: ARRAY InterruptLevel OF RECORD [
* condition: Condition, available: UNSPECIFIED],
MC[PDA.fault, 60]; * fault: ARRAY FaultIndex OF RECORD [
* queue: Queue, condition: Condition]],
* blocks => [
* block: ARRAY [0..0) OF ProcessStateBlock],
* ENDCASE];
MC[StartPsb, 20]; * = SIZE[ProcessDataArea]/Size[ProcessStateBlock]
*-----------------------------------------------------------
NewOp; ESCEntry[ME]; * Monitor Entry
* m: LONG POINTER TO Monitor ← PopLong[]; mon: Monitor; MinimalStack[];
* mon ← Fetch[m]↑;
* IF ~mon.locked THEN {mon.locked ← TRUE; Store[m]↑ ← mon; Push[TRUE]}
* ELSE EnterFailed[m];
*-----------------------------------------------------------
RTemp0← A0, MemBase← MLBR, Call[Pop1MinimalStack]; * MLBR← m
Fetch← RTemp0, Call[TestMonitorLock]; * Does not return if already locked
* Here with Q = monitor with locked bit set; StkP advanced.
LockMonitorAndExit:
Stack← (Store← 0S)+1, DBuf← Q, * Store monitor and push TRUE
NextOpcode; * This cannot fault, so CF not needed
*-----------------------------------------------------------
NewOp; ESCEntry[MX]; * Monitor Exit
* m: LONG POINTER TO Monitor ← PopLong[]; MinimalStack[];
* IF Exit[m] THEN Reschedule;
*-----------------------------------------------------------
RTemp0← A0, MemBase← MLBR, Call[Pop1MinimalStack]; * MLBR← m
Fetch← RTemp0, Call[ExitMonitor];
RTemp1← (ID)-1, Branch[MesaReschedule1]; * RTemp1← IL-1; reschedule if requeued
*-----------------------------------------------------------
NewOp; ESCEntry[MW]; * Monitor Wait
* t: Ticks ← Pop[]; c: LONG POINTER TO Condition ← PopLong[];
* m: LONG POINTER TO Monitor ← PopLong[];
* flags: PsbFlags; cond: Condition; requeue: BOOLEAN;
* MinimalStack[]; CleanupCondition[c]; requeue ← Exit[m];
* flags ← Fetch[@PDA.block[PSB].flags]↑; cond ← Fetch[c]↑;
* IF ~(flags.abort AND cond.abortable) THEN {
* IF cond.wakeup THEN {cond.wakeup ← FALSE; Store[c]↑ ← cond}
* ELSE {
* timeout: POINTER TO TimeoutVector ← Fetch[@PDA.timeout]↑;
* StorePda[@timeout[PSB]] ← IF t=0 THEN 0 ELSE MAX[1, ticks+t];
* flags.waiting ← TRUE; Store[@PDA.block[PSB].flags]↑ ← flags;
* Requeue[src: @PDA.ready, dst: c, psb: PSB]; requeue ← TRUE};
* IF requeue THEN Reschedule[];
*-----------------------------------------------------------
T← Stack&-1, MemBase← CVBR;
RTemp3← T, Call[Pop2MinimalStack]; * RTemp3← t, CVBR← c, MLBR← m
T← A0, MemBase← CVBR, Call[CleanUpCVQueue];
T← A0, MemBase← MLBR;
Fetch← T, Call[ExitMonitor];
* Test for abort pending
MemBase← PDA, Call[FetchCPFlags]; * Returns RTemp1=flags, T=@PSB.flags
RTemp2← T, MemBase← CVBR; * Save @PSB.flags
PD← Fetch← 0S, RTemp1, Branch[.+2, R even]; * Fetch[c], test flags.abort
PD← (Add[CV.abortable!]S) AND MD;
T← A0, RTemp0← MD, * RTemp0← cond
Branch[.+2, ALU=0]; * Branch if PSB not aborting or CV not abortable
RTemp1← (ID)-1, Branch[MesaReschedule1]; * Aborting, don't wait
* Test for wakeup pending
RTemp0← (RTemp0) AND NOT (CV.wakeup),
Branch[.+2, R even]; * cond.wakeup is bit 15
Store← T, DBuf← RTemp0, Branch[MesaReschedule]; * Wakeup pending, don't wait
* Set timeout and requeue PSB onto condition
T← RTemp3, RBase← RBase[PTC]; * T← timeout
T← (PTC)+T, RBase← RBase[MesaRegsMain],
Branch[.+3, ALU=0]; * Branch if timeout is zero (= infinity)
PD← T-1; * Generates carry unless T=0
RTemp3← T+1, XorSavedCarry;
T← (ID) OR (RTemp1), MemBase← PDA; * Know ID = 2 = PSBF.waiting
Store← RTemp2, DBuf← T; * Store updated flags
Fetch← PDA.timeout; * Compute @PDA.timeout[PSB]
T← RSH[PSB, logSizePSB];
T← T+MD;
DQBRReg← BRConst[CVBR]; * dst = c
SQBRReg← BRConst[RQBR]; * src = ready
Store← T, DBuf← RTemp3, Branch[Requeue&Resched];
*-----------------------------------------------------------
NewOp; ESCEntry[MR]; * Monitor Reentry
* c: LONG POINTER TO Condition ← PopLong[];
* m: LONG POINTER TO Monitor ← PopLong[]; mon: Monitor; MinimalStack[];
* mon ← Fetch[m]↑;
* IF ~mon.locked THEN {
* flags: PsbFlags; CleanupCondition[c]; flags ← Fetch[@PDA.block[PSB].flags]↑;
* flags.cleanup ← PsbNull; Store[@PDA.block[PSB].flags]↑ ← flags;
* IF flags.abort THEN {
* cond: Condition ← Fetch[c]↑; IF cond.abortable THEN ProcessTrap[]};
* mon.locked ← TRUE; Store[m]↑ ← mon; Push[TRUE]}
* ELSE EnterFailed[m];
*-----------------------------------------------------------
RTemp0← A0, MemBase← CVBR,
Call[Pop2MinimalStack]; * CVBR← c, MLBR← m, MemBase← MLBR
Fetch← RTemp0, Call[TestMonitorLock]; * Does not return if already locked
T← A0, MemBase← CVBR, Call[CleanUpCVQueue];
T← (PSB)+1, MemBase← PDA; * PSB.flags is word 1
Fetch← T, RTemp2← NOT (IndexMask);
RTemp2← (RTemp2) AND MD; * Zero cleanup link
Store← T, DBuf← RTemp2, Branch[.+2, R odd]; * abort is bit 15
MemBase← MLBR, Branch[LockMonitorAndExit];
* Abort pending. RTemp0 contains cond (left over from CleanUpCVQueue).
PD← (RTemp0) AND (CV.abortable);
Branch[.+2, ALU=0];
T← sProcessTrap, Branch[SavePCAndTrap];
MemBase← MLBR, Branch[LockMonitorAndExit];
*-----------------------------------------------------------
NewOp; ESCEntry[NC], * Notify Condition
* c: LONG POINTER TO Condition ← PopLong[]; cond: Condition;
* MinimalStack[]; CleanupCondition[c];
* IF (cond ← Fetch[c]↑).tail#PsbNull THEN {WakeHead[c]; Reschedule[]};
*-----------------------------------------------------------
RTemp3← A0, Branch[NotifyBroadcast];
*-----------------------------------------------------------
NewOp; ESCEntry[BC], * Broadcast Condition
* c: LONG POINTER TO Condition ← PopLong[]; cond: Condition; requeue: BOOLEAN;
* MinimalStack[]; CleanupCondition[c];
* WHILE (cond ← Fetch[c]↑).tail#PsbNull DO WakeHead[c]; requeue ← TRUE; ENDLOOP;
* IF requeue THEN Reschedule[];
*-----------------------------------------------------------
RTemp3← T-T-1, Branch[NotifyBroadcast];
* This code is shared by NC and BC. RTemp3 = 0 if NC, -1 if BC.
* Note that we actually call CleanUpCVQueue every iteration.
* This is ok since it is an idempotent operation.
NotifyBroadcast:
MemBase← CVBR, Call[Pop1MinimalStack]; * CVBR← c
Nop;
BroadcastLoop:
T← A0, Call[CleanUpCVQueue]; * Returns Process = ALU = c.tail
RTemp3← (RTemp3)+1, Branch[.+2, ALU=0];
RTemp3← (RTemp3)-1, Call[WakeHead];
MemBase← CVBR, RTemp3, Branch[BroadcastLoop, R<0];
RTemp1← (ID)-1, Branch[MesaReschedule1];
*-----------------------------------------------------------
NewOp; ESCEntry[REQ]; * Requeue
* psb: PsbHandle ← Pop[]; dstque: QueueHandle ← PopLong[];
* srcque: QueueHandle ← PopLong[]; MinimalStack[];
* Requeue[src: srcque, dst: dstque, psb: Index[psb]]; Reschedule[];
*-----------------------------------------------------------
T← Stack&-1, MemBase← CVBR;
Process← T, Call[Pop2MinimalStack]; * CVBR← dstque, MLBR← srcque
* Dirty both queues so that if a write-protect fault is to occur, it will occur now.
SQBRReg← T-T-1, Branch[ReQSQNil, ALU=0]; * Branch if srcque=NIL
T← Fetch← 0S;
SQBRReg← BRConst[MLBR]; * srcque in MLBR
Store← T, DBuf← MD, FlipMemBase, Branch[.+2];
ReQSQNil:
T← A0, FlipMemBase;
Fetch← T, DQBRReg← BRConst[CVBR]; * dstque in CVBR
Store← T, DBuf← MD, Branch[Requeue&Resched];
*-----------------------------------------------------------
NewOp; ESCEntry[SPP]; * Set Process Priority
* priority: Priority ← Pop[]; link: PsbLink; MinimalStack[];
* link ← Fetch[@PDA.block[PSB].link]↑; link.priority ← priority;
* Store[@PDA.block[PSB].link]↑ ← link;
* Requeue[src: @PDA.ready, dst: @PDA.ready, psb: PSB]; Reschedule[];
*-----------------------------------------------------------
T← TIOA&StkP;
T← T-1, MemBase← PDA;
Fetch← PSB, PD← T; * Know link is word 0
T← DPF[Stack&-1, 3, 14, MD], Branch[SPPMinimalStackErr, ALU#0];
Process← Store← PSB, DBuf← T;
DQBRReg← BRConst[RQBR]; * Requeue from ready to ready
SQBRReg← BRConst[RQBR], Branch[Requeue&Resched];
SPPMinimalStackErr:
Branch[StackError];
*-----------------------------------------------------------
NewOp; ESCEntry[DI]; * Disable Interrupts
* IF WDC=WdcMax THEN InterruptError[]; WDC ← WDC+1;
*-----------------------------------------------------------
T← (ID)-1, RBase← RBase[WDC], Branch[AdjustWDC]; * T← 1
*-----------------------------------------------------------
NewOp; ESCEntry[EI]; * Enable Interrupts
* IF WDC=0 THEN InterruptError[]; WDC ← WDC-1;
*-----------------------------------------------------------
T← T-T-1, RBase← RBase[WDC]; * T← -1
* Actually, should test for WP#0 only if WDC=0 now, but incrementing WDC
* more than once is uncommon, as is having WP#0 just at the moment DI is
* executed; and MesaReschedTrap will sort this out anyway.
AdjustWDC:
PD← WP; * Any interrupt requests in?
T← (WDC)+T, Branch[.+2, ALU=0];
PD← T, Reschedule; * Yes, cause a reschedule trap
Branch[.+2, ALU<0]; * WDC wrapped around?
WDC← T, NextOpcode; * Normal exit
T← sInterruptError, Branch[SavePCAndTrap]; * Over-incremented/decremented
*-----------------------------------------------------------
MesaFault: * Fault handling
* Suspend current process and invoke fault handler
* Enter: T = FaultVector offset = 2*FaultIndex for fault handler
* FaultParam0, FaultParam1 = fault parameters, if any
* RBase = MesaRegsMain
* Exit: Puts current process on fault queue, awakens handler, and
* performs a Reschedule.
*-----------------------------------------------------------
TopLevel;
KnowRBase[MesaRegsMain];
MemBase← LF, XferFlags, Branch[.+2, R<0]; * Branch if xf.invalidContext
RestoreStkP;
* LF is the truth, not LFShadow!
GFShadow← DummyRef← 0S;
MemBase← MLBR;
LFShadow← VALo;
* Requeue[dst: @PDA.fault[fi].queue, src: @PDA.ready, psb: PSB];
RTemp0← T+(PDA.fault);
RTemp1← PDAHi;
RTemp0← (BRLo← RTemp0)+1; * MLBR← @PDA.fault[fi].queue
BRHi← RTemp1;
T← PSB, MemBase← CVBR; * Process← PSB to requeue
BRLo← RTemp0; * CVBR← @PDA.fault[fi].condition
BRHi← RTemp1;
DQBRReg← BRConst[MLBR]; * Destination is fault queue
SQBRReg← BRConst[RQBR]; * Source is ready queue
Process← T, MemBase← PDA,
Call[Requeue]; * Move PSB to fault queue
* NotifyWakeup[@PDA.fault[fi].condition];
* PC ← savedPC; -- done by hardware
* SP ← savedSP; -- done by RestoreStkP (above)
* Reschedule[preemption: TRUE];
Call[NotifyWakeup]; * CVBR points to CV already
Branch[NoMoreInts]; * Go preempt current process
*-----------------------------------------------------------
MesaReschedTrap: * Reschedule trap
*-----------------------------------------------------------
TopLevel;
DontKnowRBase;
* If a broken instruction was being executed, that instruction is now complete,
* so reset the Break byte. (A Reschedule is deliberately requested during
* dispatch of the broken opcode to cause this to occur.)
Break← A0, At[MesaTrapBase, 14];
* Immediately reset the Reschedule trap condition and restart the IFU, so
* that if we subsequently decide there is nothing to do (either here or
* later), we can simply exit with a NextOpcode.
RBase← RBase[WDC];
PD← WDC, NoReschedule;
T← NOT (PCX'), Branch[MesaIntDisabled, ALU#0];
T← WP, PCF← T; * WP#0 means interrupt pending
MesaReschedTest:
WP← (WP) AND NOT T, * Clear interrupts we will process
RestoreStkP, * Needed if came from InterruptLongRunningOpcode
Branch[MesaInterrupt, ALU#0];
NextOpcode; * No interrupt, resume execution
MesaIntDisabled:
T← A0, PCF← T, Branch[MesaReschedTest];
*-----------------------------------------------------------
InterruptLongRunningOpcode:
* Called when the Reschedule condition is found true during a long-running opcode.
* Caller should restore the stack to a valid intermediate state before calling.
* Enter: RBase undefined
* Exit: If an interrupt is not actually pending, turns off Reschedule and returns;
* RBase = MesaRegsMain, T clobbered.
* Otherwise, aborts the current instruction, initiates the interrupt, and
* does not return.
*-----------------------------------------------------------
Subroutine;
RBase← RBase[WDC];
T← WP, NoReschedule;
PD← WDC, Branch[NoIntPending, ALU=0];
* If WP#0 and WDC=0 then allow the interrupt to take.
* Note that we do NOT clear the Break byte in this case, since we want it
* to be saved as part of the interrupted process state.
Branch[.+2, ALU#0];
PD← T, Branch[MesaReschedTest];
Nop;
* There is not really any interrupt pending after all. It is likely (but not
* guaranteed) that the Reschedule was initiated because the current instruction
* is a broken opcode from which we are proceeding. For this eventuality, we
* turn off Reschedule and turn on RescheduleNow. This forces a Reschedule trap
* to occur at the end of execution of the current opcode; but the RescheduleNow
* condition is NOT visible to the Reschedule branch condition. This means that
* the current opcode will now run to completion (unless some legitimate interrupt
* comes along) and THEN the Reschedule trap will occur to reset the Break byte.
NoIntPending:
RBase← RBase[MesaRegsMain];
RescheduleNow, Return;
*-----------------------------------------------------------
MesaInterrupt: * Interrupt handling
* Enter: T = interrupt request mask
* PSB#0 if interrupted from normal emulation; PSB=0 if from idle loop.
* RBase = MesaRegsAlt
*-----------------------------------------------------------
TopLevel;
Nop; * Placement
RBase← RBase[MesaRegsMain];
* Test for an interrupt occurring on the 60 hz timer channel (channel 0),
* and do CheckForTimeouts when one occurs. The following instruction preserves
* the interrupt requests in XferFlags with channel 0 masked off, but puts the
* unmasked requests through the ALU. Masking off bit 0 is important because
* it corresponds to xf.invalidContext. Claim: if PSB#0 and an interrupt occurs
* then the context is always valid; if PSB=0 then xf.invalidContext is irrelevant.
* (Reason for using XferFlags is that CheckForTimeouts is terribly short of registers.)
XferFlags← LDF[T, 17, 0];
DQBRReg← A0, MemBase← PDA, * No requeue done yet
Branch[CheckForTimeouts, ALU<0];
* For each interrupt that is pending, check the naked CV in the corresponding
* slot in the PDA.interrupt array.
* RTemp3 keeps the PDA-relative pointer, and XferFlags is used to shift the
* interrupt request bits.
* wakeups: PACKED ARRAY InterruptLevel OF BIT ← WP;
* FOR level: InterruptLevel DECREASING IN InterruptLevel DO
* IF wakeups[level]#0 THEN
* requeue ← requeue OR NotifyWakeup[@PDA.interrupt[level].condition];
* ENDLOOP;
CheckNakedCVs:
RTemp3← Add[PDA.interrupt!, 40]C, * @PDA.interrupt[LAST[InterruptLevel]+1]
Branch[CheckNakedCVLoop];
NakedCVWakeup:
BRLo← RTemp3, Call[NotifyWakeup]; * Returns with ALU#0
CheckNakedCVLoop:
RTemp3← (RTemp3)-(2C), Branch[NoMoreInts, ALU=0];
XferFlags← (XferFlags) RSH 1, Branch[.-1, R even];
MemBase← CVBR; * Notify this CV
T← PDAhi;
BRHi← T, Branch[NakedCVWakeup];
* All interrupt requests have been processed, and XferFlags is zero.
* If we were interrupted from normal emulation (PSB#0), do a Reschedule iff
* the interrupt actually caused any processes to be requeued.
* If we were interrupted from the idle loop (PSB=0), go reconsider the ReadyQ.
NoMoreInts:
PD← PSB, MemBase← PDA;
RTemp1← T-T-1, DblBranch[MesaReschedule1, IdleReschedule, ALU#0];
*-----------------------------------------------------------
CheckForTimeouts: * Check for process timeouts
* This is invoked every time an interrupt is requested on the 60 hz timer channel.
* Enter: MemBase = PDA
* Exit: MemBase = PDA
* RBase = MesaRegsMain
* Exits to CheckNakedCVs
* Clobbers T, Q, Cnt, RTemp0-3, Process, DQBRReg, SQBRReg, TrapParam
*-----------------------------------------------------------
* Scan PSBs only every third tick
RBase← RBase[MesaRegsAlt];
TickCount← (TickCount)-1;
T← (Fetch← PDA.count)+1, Branch[.+2, ALU<0];
RBase← RBase[MesaRegsMain], Branch[EndTimeoutScan];
* requeue: BOOLEAN ← FALSE; count: CARDINAL ← Fetch[@PDA.count]↑;
* vector: POINTER TO TimeoutVector ← Fetch[@PDA.timeout]↑;
* FOR psb: PsbIndex IN [StartPsb..StartPsb+count) DO
* timeout: Ticks ← FetchPda[@vector[psb]]↑;
* IF timeout#0 AND timeout=PTC THEN {
* flags: PsbFlags ← Fetch[@PDA.block[psb].flags]↑; flags.waiting ← FALSE;
* Store[@PDA.block[psb].flags]↑ ← flags; StorePda[@vector[psb]]↑ ← 0;
* Requeue[src: NIL, dst: @PDA.ready, psb: psb]};
* ENDLOOP;
KnowRBase[MesaRegsAlt];
TickCount← Fetch← T, T← MD; * TickCount← 2; fetch PDA.timeout;
* know PDA.timeout = PDA.count+1 = 2
Cnt← T; * Count of PSBs involved in scan
T← PTC← (PTC)+1, RBase← RBase[MesaRegsMain];
RTemp3← (Sub[StartPsb!, 1]S)+MD+1; * @vector[StartPsb]
RTemp3← (Fetch← RTemp3)+1;
PD← A0, Q← T;
* RTemp3 = address of timeout word; MD = timeout from previous iteration;
* TrapParam = ALU = timeout from 2 iterations ago; Q = PTC.
* PrincOps deviation: this fetches 2 words beyond the end of the timeout vector.
* This might cause a page fault if the end of the vector is page-aligned!
TimeoutScanLoop:
RTemp3← (Fetch← RTemp3)+1, T← MD, Branch[NonzeroTimeout, ALU#0];
TrapParam← T, Branch[.-1, Cnt#0&-1];
EndTimeoutScan:
Branch[CheckNakedCVs];
NonzeroTimeout:
PD← (TrapParam)#Q; * vector[psb] = PTC?
TrapParam← T, Branch[DoTimeout, ALU=0];
ResumeTimeoutScan:
PD← TrapParam, DblBranch[TimeoutScanLoop, EndTimeoutScan, Cnt#0&-1];
* This process has timed out. RTemp3 = @vector[psb+3], where psb is the PsbIndex
* of the process which has timed out.
DoTimeout:
Fetch← PDA.timeout;
RTemp3← (RTemp3)-(3C);
T← (RTemp3)-MD; * T← psb index of timed-out process
T← LSH[T, logSizePSB];
Process← T+(LShift[StartPsb!, logSizePSB]C)+1; * @PDA.block[psb].flags
T← A0, Fetch← Process; * Fetch PSB.flags; know PDA.flags = 1
SQBRReg← NOT (DBuf← T), * SQBRReg=-1 => src=NIL
Store← RTemp3, T← MD; * vector[psb] ← 0
T← T AND (Not[PSBF.waiting!]C);
DQBRReg← BRConst[RQBR]; * dst = ReadyQ
Process← (Store← Process)-1, DBuf← T, * Store PSB.flags, fix psb pointer
Call[Requeue];
* Now get back in sync with the timeout scan.
* RTemp3 = @vector[psb], where psb is the index of the process which just timed out.
* TrapParam = vector[psb+1]. Resume by fetching vector[psb+2] and testing vector[psb+1].
RTemp3← (RTemp3)+(2C);
RTemp3← (Fetch← RTemp3)+1, Branch[ResumeTimeoutScan];
*-----------------------------------------------------------
Requeue&Resched:
* Do a Requeue followed by a Reschedule.
* Arguments as for Requeue.
*-----------------------------------------------------------
MemBase← PDA, Call[Requeue];
*-----------------------------------------------------------
MesaReschedule: * PrincOps Reschedule operation
* Also includes SaveProcess, LoadProcess, AllocState, FreeState, and
* part of Fault, suitably flattened out into in-line code.
* Process/monitor opcodes normally branch here when they are done.
* Can get here at the end of interrupt processing also.
* Enter: DQBRReg[0] = 1 iff a Requeue has been done.
* Exit: Resumes execution of this or some other process.
*-----------------------------------------------------------
RTemp1← (ID)-1; * RTemp1← instruction length -1
* Here RTemp1 = -1 if came from MesaInterrupt or MesaFault; = IL-1 if came from
* process/monitor opcode. Thus "RTemp1<0" is synonymous with "preemption".
* IF ~reschedule THEN RETURN;
MesaReschedule1:
MemBase← PDA, DQBRReg, Branch[.+2, R<0];
NextOpcode; * No Requeue, resume normal execution
*-----------------------------------------------------------
* Save state of current process.
* Can get here due to a Fault, after requeueing CurrentPSB onto a fault queue.
* RTemp1 = -1 if preempted, instruction length -1 otherwise.
*-----------------------------------------------------------
* link: PsbLink ← Fetch[@PDA.block[PSB].link]↑;
* context: PsbContext ← Fetch[@PDA.block[PSB].context]↑;
* IF ValidContext[] THEN StoreMds[@LocalBase[LF].pc]↑ ← PC;
* IF (link.preempted ← preemption) THEN {
* state: StateHandle ← AllocState[link.priority]; SaveStack[state];
* Store[@state.frame]↑ ← LF; Store[@PDA.block[PSB].context]↑ ← state}
* ELSE Store[@PDA.block[PSB].context]↑ ← LF;
* Store[@PDA.block[PSB].link]↑ ← link;
* Validity of context is indicated by XferFlags[xf.invalidContext], which
* is checked by SavePCInFrame.
Fetch← PSB; * Know PSB.link is word 0
T← MD, RTemp1← (RTemp1)-(PCX'), * PCX or PCX+IL
Branch[NotPreemption, R>=0];
* Here to preempt current process.
* AllocState: PROCEDURE [priority: Priority] RETURNS [state: StateHandle] = {.
* state ← Fetch[@PDA.state[priority]]↑; IF state=NIL THEN ERROR;
* Store[@PDA.state[priority]]↑ ← Fetch[state]↑;
* Careful not to clobber TrapParam (=FaultParam0) and RTemp3 (=FaultParam1) until
* they are stored.
* Must call SaveStack before removing StateVector from list, because SaveStack
* might generate a StackError trap (during interrupts only, never during faults).
RTemp2← T OR (PSBL.preempted);
RTemp4← LDF[T, 3, 14]; * Extract link.priority
RTemp4← (RTemp4)+(PDA.state);
Fetch← RTemp4, * Fetch head of state list
Call[SavePCInFrame];
RTemp0← PD← MD, MemBase← PDA; * RTemp0← head StateVector
T← (Fetch← RTemp0)+(SV.data), * Fetch successor
Branch[NoStateVector, ALU=0]; * Branch if list empty
* The following is really part of FaultTwo rather than SaveProcess:
* Store[@state.data[0]]↑ ← LowHalf[parameter]; -- = FaultParam0
* Store[@state.data[1]]↑ ← HighHalf[parameter]; -- = FaultParam1
* Note: must not store frame until after SaveStack, because SaveStack may clobber
* state.frame if the stack is completely full.
T← (Store← T)+1, DBuf← FaultParam0;
Store← T, DBuf← FaultParam1,
Call[SaveStack]; * Save stack, StkP, Break; doesn't clobber MD;
* returns T = @state.frame
Store← T, DBuf← LFShadow, T← MD; * state.frame ← LF
Store← RTemp4, DBuf← T, * Store successor as head
Branch[EndSaveProcess]; * Use RTemp0 = state as context
NoStateVector:
Breakpoint, Branch[.]; * No state vector for preempted process
* Here if preemption not in progress: just save PC and use LF as context.
NotPreemption:
RTemp2← T AND NOT (PSBL.preempted);
Call[SavePCInFrame]; * Returns LF in T
RTemp0← T, MemBase← PDA;
* Together again here.
* Now RTemp0 = context (frame or state vector); RTemp2 = updated PSB.link.
EndSaveProcess:
T← PSB;
Store← T, DBuf← RTemp2;
T← (PSB)+(PSB.context);
Store← T, DBuf← RTemp0;
*-----------------------------------------------------------
* Check ready queue for new process to run.
* Can get here after saving current process (above), or after processing
* an interrupt from BusyWait (below).
* A process is runnable if either it already has a StateVector (i.e., the
* process was preempted) or a free StateVector is available at the
* process's priority level.
*-----------------------------------------------------------
* link: PsbLink; psb: PsbIndex; queue: Queue;
* queue ← Fetch[@PDA.ready]↑; IF queue.tail = PsbNull THEN GOTO BusyWait;
* link ← Fetch[@PDA.block[queue.tail].link]↑;
* DO
* psb ← link.next; link ← Fetch[@PDA.block[psb].link]↑;
* IF link.vector OR ~EmptyState[link.priority] THEN EXIT;
* IF psb = queue.tail THEN GOTO BusyWait;
* ENDLOOP;
* psb ← PSB; PC ← savedPC ← 0; LF ← LoadProcess[]; running ← TRUE;
* Xfer[dst: LF, src: 0];
* EXITS BusyWait =>
* {IF ~InterruptsEnabled[] THEN RescheduleError[]; running ← FALSE; RETURN};
IdleReschedule:
Fetch← PDA.ready; * Fetch queue
RTemp0← Fetch← MD; * Fetch link word of tail PSB
T← (IndexMask) AND MD, FreezeBC;
FindRunnableProcess:
PSB← Fetch← T, Q← T, * Fetch link word of next PSB
Branch[BusyWait, ALU=0]; * Branch if queue empty or hit tail
T← MD, XferFlags← xf.invalidContext; * Set up for subsequent Xfer
T← LDF[T, 3, 14], RTemp2← MD; * T← link.priority
RTemp2← T+(PDA.state), * See if StateVector is available
Branch[LoadPreempted, R odd]; * Branch if link.preempted=TRUE
Fetch← RTemp2, RTemp2← T← B← MD;
T← (IndexMask) AND T; * T← next PSB
PD← MD;
PD← (RTemp0)-Q, * See if PSB = queue.tail
DblBranch[LoadNonPreempted, FindRunnableProcess, ALU#0];
* Ready queue is empty, or there are no runnable processes.
* The only way out of this state is to get a naked notify (or a timeout)
* on a CV that some process is waiting on. Therefore, spin here until
* an interrupt request is raised. (This is our implementation of setting
* the "running" flag to FALSE and returning.)
BusyWait:
RBase← RBase[MesaRegsAlt];
PD← WDC, RBase← RBase[MesaRegsMain];
T← sRescheduleError, Branch[.+2, ALU=0];
Branch[MTrap]; * It's an error to be idle with WDC#0
Call[InterruptLongRunningOpcode]; * Does not return if an interrupt occurs
Branch[.-1];
* Reschedule (cont'd)
*-----------------------------------------------------------
LoadPreempted: * Run preempted process.
* PSB = process to run; RTemp2 = @PDA.state[link.priority].
*-----------------------------------------------------------
* This is part of LoadProcess:
* state: StateHandle ← Fetch[@PDA.block[PSB].context]↑
* LoadStack[state]; LF ← Fetch[@state.frame]; FreeState[link.priority, state];
T← (PSB)+(PSB.context);
RTemp1← (Fetch← T)+1; * PSB.context = StateVector; RTemp1← @PSB.mds
RTemp0← MD, Call[LoadStack]; * Load stack, StkP, Break
T← (RTemp0)+(SV.frame); * DLink← state.frame
Fetch← T, T← RTemp2;
* FreeState: PROCEDURE [priority: Priority, state: StateHandle] = {
* Store[state]↑ ← Fetch[@PDA.state[priority]]↑; Store[@PDA.state[priority]]↑ ← state};
* RTemp0 = state; RTemp2 = T = @PDA.state[link.priority].
Fetch← T, DLink← MD;
Store← T, DBuf← RTemp0, T← MD;
Store← RTemp0, DBuf← T, Branch[XferToNewProcess];
*-----------------------------------------------------------
LoadNonPreempted: * Run non-preempted process.
* PSB = Q = process to run; RTemp2 = PSB.link.
*-----------------------------------------------------------
* This is part of LoadProcess:
* LF ← Fetch[@PDA.block[PSB].context];
* IF link.failed THEN {
* Push[FALSE]; link.failed ← FALSE; Store[@PDA.block[psb].link]↑ ← link};
T← (PSB)+(PSB.context);
RTemp1← (Fetch← T)+1; * PSB.context = frame; RTemp1← @PSB.mds
DLink← MD, T← RTemp2, Branch[XferToNewProcess, R>=0];
T← T AND NOT (PSBL.failed), StkP+1;
Store← Q, DBuf← T, Stack← A0; * Store updated link; Push[FALSE]
*-----------------------------------------------------------
* Preempted and non-preempted cases together here.
* mds ← Fetch[@PDA.block[PSB].mds]↑; Xfer[dst: LF, src: NIL];
* DLink = new local frame; RTemp1 = @PSB.mds
* Set the new local frame now so that if a fault occurs during the
* subsequent Xfer, the correct context is saved.
*-----------------------------------------------------------
XferToNewProcess:
Fetch← RTemp1;
T← MD, MemBase← GF, Call[BRHiGetsT];
T← DLink, MemBase← LF;
LFShadow← BRLo← T, T← MD, Call[BRHiGetsT];
SLink← A0, MemBase← MDS;
BRHi← T, Branch[Xfer];
*-----------------------------------------------------------
Pop2MinimalStack: * Prepare 2 long pointer arguments
* Pop two long pointers, load base registers, and check for minimal stack.
* Enter: MemBase, MemBase xor 1 = first and second BRs to be loaded
* TIOA=0
* Exit: MemBase = entering MemBase xor 1
* Both BRs loaded
* T = ALU = 0 iff second pointer is NIL
* DQBRReg >= 0 (i.e., Requeue flag initialized to 0, if relevant)
*-----------------------------------------------------------
Subroutine;
BRHi← Stack&-1;
BRLo← Stack&-3;
DQBRReg← T← TIOA&StkP;
PD← T, StkP+2, FlipMemBase, Branch[Pop1Tail];
*-----------------------------------------------------------
Pop1MinimalStack: * Prepare 1 long pointer argument
* Pop one long pointer, load base register, and check for minimal stack.
* Enter: MemBase = BR to be loaded
* TIOA=0
* Exit: MemBase unchanged
* BR loaded
* T = ALU = 0 iff pointer is NIL
* DQBRReg >= 0 (i.e., Requeue flag initialized to 0, if relevant)
*-----------------------------------------------------------
Subroutine;
T← TIOA&StkP, StkP-2; * Reads StkP after modification
DQBRReg← T, StkP+2;
Pop1Tail:
T← BRHi← Stack&-1, Branch[MinimalStackErr, ALU#0];
T← (BRLo← Stack&-1) OR T, Return;
* Opcode was not called with minimal stack; generate stack error trap.
TopLevel;
MinimalStackErr:
Branch[StackError];
*-----------------------------------------------------------
FetchCPFlags: * Fetch current process's flags.
* Enter: MemBase = PDA
* Exit: RTemp1 = PSB.flags
* T = pointer to PSB.flags
* Process = PSB
*-----------------------------------------------------------
Subroutine;
T← (PSB)+1; * Know PSB.flags is word 1
Process← (Fetch← T)-1, Branch[.+2];
*-----------------------------------------------------------
FetchCPLink: * Fetch current process's link
* Enter: MemBase = PDA
* Exit: RTemp1 = PSB.link
* T = pointer to PSB.link
* Process = PSB
*-----------------------------------------------------------
Subroutine;
T← Process← Fetch← PSB; * Know that link is word 0
RTemp1← MD, Return;
*-----------------------------------------------------------
TestMonitorLock: * Test and set monitor lock
* Enter: current BR = @monitor
* MD = monitor
* Exit: if monitor is locked, goes to EnterFailed; otherwise:
* RTemp1 = Q = monitor value, with ML.locked = TRUE.
* StkP incremented (in preparation for pushing TRUE result)
* Clobbers T
*-----------------------------------------------------------
Subroutine;
T← A0, RTemp1← MD;
T← RTemp1← (Store← T)+(DBuf← RTemp1)+1, * Dirty monitor, set ML.locked
Branch[EnterFailed, R odd]; * Branch if already locked
Q← T, StkP+1, Return;
*-----------------------------------------------------------
EnterFailed: * Handle failure to enter monitor
* EnterFailed: PROCEDURE [m: LONG POINTER TO monitor] = {
* link: PsbLink ← Fetch[@PDA.block[PSB].link]↑; link.failed ← TRUE;
* Store[@PDA.block[PSB].link]↑ ← link;
* Requeue[src: @PDA.ready, dst: m, psb: PSB]; Reschedule[]};
* Enter: MLBR points to monitor lock
* Exit: Does not return but rather goes directly to MesaReschedule
*-----------------------------------------------------------
TopLevel;
MemBase← PDA, Call[FetchCPLink]; * RTemp1← PSB.link, T← @PSB.link
RTemp1← (RTemp1) OR (PSBL.failed);
Store← T, DBuf← RTemp1;
DQBRReg← BRConst[MLBR]; * dst = ML
SQBRReg← BRConst[RQBR], * src = ReadyQ, Process = PSB
Branch[Requeue&Resched];
*-----------------------------------------------------------
ExitMonitor: * Exit from monitor
* Unlocks monitor, and moves process at head of monitor lock queue to
* ready queue, if there is one.
* ExitMonitor: PROCEDURE [m: LONG POINTER TO Monitor] RETURNS [requeue: BOOLEAN] = {
* mon: Monitor ← Fetch[m]↑; mon.locked ← FALSE; Store[m]↑ ← mon;
* IF requeue ← (mon.tail # PsbNull) THEN {
* link: PsbLink ← Fetch[@PDA.block[mon.tail].link]↑;
* Requeue[src: m, dst: @PDA.ready, psb: link.next]}};
* Enter: MLBR = long pointer to monitor
* MemBase = MLBR
* MD = monitor
* Clobbers T, RTemp0, RTemp1, RTemp2, Process, MemBase
*-----------------------------------------------------------
Subroutine;
RTemp1← MD, T← (IndexMask) AND MD;
RTemp1← (RTemp1) AND NOT (ML.locked), Branch[.+2, ALU#0];
Store← 0S, DBuf← RTemp1, Return; * Queue is empty
* Move head process to ready queue.
Store← 0S, DBuf← RTemp1;
MemBase← PDA;
Fetch← T, DQBRReg← BRConst[RQBR]; * Fetch link of tail PSB; dst = ReadyQ
SQBRReg← BRConst[MLBR]; * src = ML
T← (IndexMask) AND MD;
Process← Fetch← T, Branch[Requeue1]; * Requeue and return
*-----------------------------------------------------------
NotifyWakeup: * Perform naked notify
* Wakes the process at the head of the CV queue if there is one;
* sets the wakeup waiting bit in the CV if there isn't.
* NotifyWakeup: PROCEDURE [c: LONG POINTER TO Condition] RETURNS [requeue: BOOLEAN] = {
* cond: Condition; requeue: BOOLEAN ← FALSE;
* CleanupCondition[c];
* IF (cond ← Fetch[c]↑).tail = PsbNull THEN {cond.wakeup ← TRUE; Store[c]↑ ← cond}
* ELSE {WakeHead[c]; requeue ← TRUE}};
* Enter: CVBR = pointer to CV
* Exit: ALU#0 (for the benefit of MesaInterrupt)
* Clobbers T, RTemp0, RTemp1, RTemp2, Process, SQBRReg, DQBRReg, MemBase
*-----------------------------------------------------------
Subroutine;
RTemp2← Link, Global;
TopLevel;
T← A0, MemBase← CVBR, Call[CleanUpCVQueue];
T← (RTemp0) OR (CV.wakeup), Branch[.+2, ALU=0];
Link← RTemp2, Branch[WakeHead]; * CV queue non-empty, awaken head and return
Link← RTemp2; * CV queue empty, set wakeup waiting bit
Subroutine;
Store← 0S, PD← DBuf← T, Return;
*-----------------------------------------------------------
WakeHead: * Awaken head process on CV queue
* Wakes the process at the head of the CV queue (there must be one).
* WakeHead: PROCEDURE [c: LONG POINTER TO Condition] = {
* vector: POINTER TO TimeoutVector ← Fetch[@PDA.timeout]↑;
* cond: Condition ← Fetch[c]↑; link ← Fetch[@PDA.block[cond.tail].link]↑;
* flags ← Fetch[@PDA.block[link.next].flags]↑; flags.waiting ← FALSE;
* Store[@PDA.block[link.next].flags]↑ ← flags;
* Store[@vector[link.next]]↑ ← 0;
* Requeue[src: c, dst: @PDA.ready, psb: link.next]};
* Enter: CVBR = pointer to CV
* Process = CV.tail
* Exit: MemBase = PDA
* ALU#0 (for the benefit of MesaInterrupt)
* Clobbers T, RTemp0, RTemp1, RTemp2, Process, SQBRReg, DQBRReg
*-----------------------------------------------------------
Subroutine;
T← Process, MemBase← PDA;
Fetch← T, * PSB.link is word 0
DQBRReg← BRConst[RQBR]; * dst = ReadyQ
Fetch← PDA.timeout, T← MD;
Process← (IndexMask) AND T; * Process← successor of tail
T← RSH[Process, 2]; * Convert to PsbIndex
RTemp0← T+MD; * RTemp0← @vector[psb]
T← (Process)+1; * Know PSB.flags=1
Fetch← T,
SQBRReg← BRConst[CVBR]; * src = CV
Store← RTemp0, DBuf← 0C, RTemp0← MD; * vector[psb] ← 0; RTemp0← flags
RTemp0← (RTemp0) AND NOT (PSBF.waiting);
Store← T, DBuf← RTemp0;
Fetch← Process, Branch[Requeue1]; * Call Requeue and return
*-----------------------------------------------------------
Requeue: * Move process from one queue to another
* Enter: SQBRReg = MemBase value for BR containing source QueueHandle;
* bit 15 = 1 iff source QueueHandle is NIL, meaning the caller
* doesn't know what queue the process is on.
* DQBRReg = MemBase value for BR containing destination QueueHandle
* Process = PSB to be requeued
* MemBase = PDA
* Exit: MemBase = PDA
* ALU#0 (for benefit of MesaInterrupt)
* Clobbers T, RTemp0, RTemp1, RTemp2; resets ShC to StdShC
*-----------------------------------------------------------
Subroutine;
* Here we compute "prev", the predecessor of process, and put it in RTemp1.
* If psb.link points to itself, queue will be empty after psb is removed.
* IF src#NIL THEN queue ← Fetch[src]↑;
* link ← Fetch[@PDA.block[psb].link]↑;
* IF link.next = psb THEN prev ← PsbNull ...
Fetch← Process, Global;
Requeue1:
RTemp1← shcQ.tail; * Set shifter for Q.tail masking
RTemp0← T← (IndexMask) AND MD;
RTemp2← MD, PD← (Process)#T; * RTemp2 = link, will be used later
RTemp1← A0, ShC← RTemp1, Branch[RequeueGotPrev, ALU=0];
* Search for predecessor. Start at psb if sq is NIL, else at sq.tail.
* ELSE {
* prev ← IF sq=NIL THEN psb ELSE queue.tail;
* DO temp ← Fetch[@PDA.block[prev].link]↑; IF temp.next = psb THEN EXIT;
* prev ← temp.next; ENDLOOP;
* temp.next ← link.next; Store[@PDA.block[prev].link]↑ ← temp};
MemBase← SQBRReg, Branch[.+2, R odd]; * Branch if src=NIL
Fetch← 0S; * queue ← Fetch[src]↑
T← (IndexMask) AND MD, MemBase← PDA; * T = psb.next or queue.tail
RequeueSearchSQ:
RTemp1← Fetch← T; * T = potential predecessor
T← (IndexMask) AND MD;
PD← (Process)#T;
Branch[RequeueSearchSQ, ALU#0];
* Now RTemp1 has predecessor of process, and MD has its link word.
* Bypass process in queue structure.
T← ShMDBothMasks[RTemp0]; * Insert RTemp0 = psb↑.link.next
Store← RTemp1, DBuf← T;
* RTemp1 = predecessor of process, or 0 if there wasn't one.
* RTemp0 = psb↑.link.next.
* IF src=NIL THEN {
* flags ← Fetch[@PDA.block[psb].flags]↑; flags.cleanup ← link.next;
* Store[@PDA.block[psb].flags]↑ ← flags}
* ELSE IF queue.tail = psb THEN{queue.tail ← prev; Store[src]↑ ← queue};
RequeueGotPrev:
T← A0, MemBase← SQBRReg, Branch[.+3, R even]; * Branch if src#NIL
T← (Process)+1, MemBase← PDA; * Know flags is word 1
RTemp1← Fetch← T, Branch[StoreQueueOrCleanup];
Fetch← T, RTemp0← RTemp1; * Fetch[src]↑; RTemp0← prev
T← (IndexMask) AND (MD);
PD← (Process)#T;
RTemp1← A0, Branch[BeginInsertDQ, ALU#0];
* In the following multi-purpose code, either:
* MemBase = PDA, RTemp1 = @psb.flags, MD = psb.flags, and RTemp0 = link.next;
* or: MemBase = SQBR, RTemp1 = 0, MD = src↑, and RTemp0 = prev.
StoreQueueOrCleanup:
T← ShMDBothMasks[RTemp0]; * Insert into Q.tail or flags.next
Store← RTemp1, DBuf← T;
* Requeue (cont'd)
* Now begin to insert process into dst queue. First, test for the easy case
* in which the dst queue is initially empty. RTemp2 still contains psb↑.link.
* queue ← Fetch[dst]↑; link ← Fetch[@PDA.block[psb].link]↑;
* IF queue.tail = PsbNull THEN {
* link.next ← psb; Store[@PDA.block[psb].link]↑ ← link;
* queue.tail ← psb; Store[dst]↑ ← queue} ...
BeginInsertDQ:
T← A0, MemBase← DQBRReg;
RTemp0← Fetch← T; * Fetch[dst]↑
RTemp1← (IndexMask) AND MD;
T← ShMDBothMasks[Process], Branch[CheckDQTail, ALU#0];
Store← RTemp0, DBuf← T; * Queue empty, make it point to psb
T← Process, MemBase← PDA, * Link psb to itself
Branch[RequeueStorePSBLink];
* dst is non-empty. Begin by testing whether process's priority is <=
* the priority of the current tail process, and if so just append process.
* RTemp1 points to current tail process; RTemp2 = psb↑.link.
* ELSE {
* prev ← queue.tail; temp ← Fetch[@PDA.block[prev].link]↑;
* IF temp.priority >= link.priority THEN {queue.tail ← psb; Store[dst]↑ ← queue} ...
CheckDQTail:
RTemp0← T, MemBase← PDA; * In case psb becomes new tail (below)
Fetch← RTemp1, T← PSBL.priority;
RTemp2← (RTemp2) AND T; * Extract psb↑.link.priority
T← T AND MD; * Extract prev↑.link.priority
PD← T-(RTemp2);
T← (IndexMask) AND MD, Branch[SearchDQLoop, ALU<0];
* Process priority <= tail priority. Just make process be new tail.
T← A0, MemBase← DQBRReg;
Store← T, DBuf← RTemp0; * Make queue point to psb
MemBase← PDA, Branch[RequeueStorePrevLink]; * Link it into the queue
* Must search queue to find proper place to insert process.
* Find prev = last process whose priority is >= that of psb.
* At this point, RTemp1 points to tail process, and MD = its link word,
* which is a pointer to the head process. T = temp.next.
* ELSE DO next ← Fetch[@PDA.block[temp.next].link]↑;
* IF link.priority > next.priority THEN EXIT;
* prev ← temp.next; temp ← next; ENDLOOP; ...
SearchDQLoop:
RTemp0← Fetch← T;
T← PSBL.priority;
T← T AND MD;
PD← (RTemp2)-T-1;
T← (IndexMask) AND MD, Branch[RequeueStorePrevLink, ALU>=0];
RTemp1← RTemp0, Branch[SearchDQLoop];
* Now RTemp1 = prev = the process after which we are to insert.
* link.next ← temp.next; Store[@PDA.block[psb].link]↑ ← link;
* temp.next ← psb; Store[@PDA.block[prev].link]↑ ← temp};
RequeueStorePrevLink:
Fetch← RTemp1; * Insert Process into prev↑.link.next
T← ShMDBothMasks[Process];
Store← RTemp1, DBuf← T, T← MD; * T← former prev↑.link
* Insert T into psb↑.link.next and return.
RequeueStorePSBLink:
RTemp0← T, Fetch← Process; * Know link is word 0
T← StdShC;
T← ShMDBothMasks[RTemp0], ShC← T;
PD← Store← Process, DBuf← T, Return; * ALU#0
*-----------------------------------------------------------
CleanUpCVQueue: * Clean up condition queue
* Cleans up CV queue that may have been left in a mess by Requeue.
* Enter: MemBase = CVBR
* CVBR points to condition variable c
* T = 0
* IndexMask initialized
* Exit: MemBase = CVBR
* ALU = Process = c↑.tail (as modified by subroutine, if necessary)
* RTemp0 = c↑ (modified, if necessary; tail field may not be valid)
* Clobbers T, RTemp0, RTemp1
*-----------------------------------------------------------
Subroutine;
* If CV queue is empty then do nothing.
* cond ← Fetch[c]↑; psb ← cond.tail; IF psb # PsbNull THEN { ...
T← IndexMask, Fetch← T, Global;
* Force write-protect fault to occur here if it's going to occur at all.
Store← 0S, Process← DBuf← MD;
Process← T← (Process) AND T, MemBase← PDA;
T← T+1, RTemp0← MD, Branch[.+2, ALU#0]; * RTemp0← cond
CleanupCVReturn:
PD← Process, MemBase← CVBR, Return; * Queue is empty, nothing to do
* If head PSB's cleanup link is nil then do nothing.
* flags ← Fetch[@PDA.block[psb].flags]↑;
* IF flags.cleanup # PsbNull THEN { ...
T← IndexMask, Fetch← T; * psb↑.flags -- know flags are word 1
RTemp0← (RTemp0) AND NOT T; * cond.tail ← PsbNull (for later)
PD← (IndexMask) AND MD;
SearchForCVQHead:
T← (IndexMask) AND MD, Branch[.+2, ALU#0]; * T← psb↑.flags.cleanup
PD← Process, MemBase← CVBR, Return; * No cleanup queue, nothing to do
* Process has a psb to check, and ALU = T = psb↑.flags.cleanup.
* Follow cleanup links until we either hit NIL or
* find a PSB with a cleanup link pointing to itself.
* DO IF flags.cleanup = psb THEN {
* cond.wakeup ← FALSE; cond.tail ← PsbNull; Store[c]↑ ← cond; RETURN};
* psb ← flags.cleanup; flags ← Fetch[@PDA.block[psb].flags]↑;
* IF flags.cleanup = PsbNull THEN EXIT;
* ENDLOOP;
PD← (Process)#T, Branch[FoundCVQHead, ALU=0];
T← T+1, Branch[MakeCVQEmpty, ALU=0];
Process← (Fetch← T)-1, Branch[SearchForCVQHead]; * ALU#0 guaranteed
* Found a PSB with a cleanup link pointing to itself. This can happen
* if a PSB is Requeued when it is the only PSB on the CV queue.
* Reset the CV queue to empty.
MakeCVQEmpty:
RTemp0← (RTemp0) AND NOT (CV.wakeup);
Process← T← A0, Branch[StoreCVQueue];
* Found a PSB with a NIL cleanUp link, and not the first in the cleanUp queue.
* Put it at the head of the CV queue. Since queues are circular and rooted
* through their tail, this requires chasing down the queue to find the tail.
* head ← psb;
* DO link ← Fetch[@PDA.block[psb].link]↑; IF link.next = head THEN EXIT;
* psb ← link.next; ENDLOOP;
FoundCVQHead:
RTemp1← T← Fetch← Process; * Remember head, fetch psb↑.link
SearchForCVQTail:
Process← T;
T← (IndexMask) AND MD; * T← psb↑.link.next
PD← (RTemp1)#T;
Fetch← T, Branch[SearchForCVQTail, ALU#0];
* Process = new tail PSB; RTemp0 = cond with tail field zeroed out.
* cond.tail ← psb; Store[c]↑ ← cond}};
T← Process;
StoreCVQueue:
RTemp0← (RTemp0) OR T, MemBase← CVBR;
Store← 0S, DBuf← RTemp0, Branch[CleanupCVReturn];