*-----------------------------------------------------------
Title[AltoMesaProcess.mc...January 22, 1982 6:04 PM...Taft];
* Process/monitor opcodes, interrupt handler, and process scheduler.
IfE[AltoMode, 0, ER[Alto-only.module--will.not.work.with.Pilot, 1]];
*-----------------------------------------------------------
%
CONTENTS, by order of occurence
MEMonitor Enter
MREMonitor Reenter
MXDMonitor Exit and Depart
MXWMonitor Exit and Wait
NOTIFYNotify
BCASTBroadcast
REQUEUERequeue
Pop2ShortOrLongPop 2 short or long pointers and load base registers
Pop1ShortOrLongPop 1 short or long pointer and load base register
FetchCP&CPFFetch current process and current process’s flags
SetReadyQBRSet up RQBR to point to the Ready Queue
EnterFailedPut current process on ML queue
ExitMonitorUnlock monitor and awaken process at head of ML queue
WakeHeadAwaken process at head of CV queue
RequeueMove a process from a source queue to a destination queue
CleanUpCVQueueClean up CV queue that may have been left in a mess by Requeue
IWDCIncrement WDC, disable interrupts
DWDCDecrement WDC, reenable interrupts as appropriate
MesaIFUMapFault (etc.) IFU exception traps
MesaReschedTrapMesa Reschedule trap
MesaInterruptNotify naked CVs according to wakeups pending in NWW
CheckForTimeouts Scan PSBs and awaken any that have timed out
MesaRescheduleSuspend current process and begin new one from Ready Queue
%
TopLevel;
KnowRBase[RTemp0];
* Base registers.
* Following two registers must be IFU-addressable and mutually xor 1.
BR[MLBR, 34];* Monitor lock
BR[CVBR, 35];* Condition variable
BR[RQBR, IP[ScratchBR]];* Ready queue
* R register usage.
* RTemp0-3 are used for general scratch purposes.
* The remaining RTemps are 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];
* Ticks: TYPE = CARDINAL;
* ProcessHandle: TYPE = LONG POINTER [0..77777B] TO PSB;
* Queue: TYPE = LONG POINTER [0..77777B] TO PSB;
* QueueHandle: TYPE = LONG POINTER TO Queue;
* Note that the process/monitor opcodes actually accept either short or long
* QueueHandles, and must distinguish among them by testing the stack depth.
* PSB: TYPE = MACHINE DEPENDENT RECORD [
MSC[PSB.link, 0];* Link: ProcessHandle,
MSC[PSB.cleanUp, 1];* cleanUp: ProcessHandle,
MSC[PSB.timeout, 2];* timeout: Ticks,
MSC[PSB.flags, 3];* flags: PsbFlags,
MSC[PSB.frame, 4];* frame: LocalFrameHandle ];
MC[SizePSB, 5];
* PsbFlags: TYPE = MACHINE DEPENDENT RECORD [
MC[PSBF.enterFailed, 100000];* enterFailed: BOOLEAN,
MC[PSBF.detached, 40000];* detached: BOOLEAN,
* fill: [0..37B],
MC[PSBF.state, 600];* state: {ready, taken, dead, alive},
* unused: BOOLEAN,
MC[PSBF.abortPending, 40];* abortPending: BOOLEAN,
* unused: BOOLEAN,
MC[PSBF.waitingOnCV, 10];* waitingOnCV: BOOLEAN,
MC[PSBF.priority, 7];* priority: Priority ]
* Condition: TYPE = MACHINE DEPENDENT RECORD [
*wakeupWaiting: {no, yes},
*queue: Queue ]
* MonitorLock: TYPE = MACHINE DEPENDENT RECORD [
*lock: {locked, unlocked},
*queue: Queue ]
* StateVector: TYPE = MACHINE DEPENDENT RECORD [
MC[SV.stack, 0];* stack: ARRAY[0..7] OF UNSPECIFIED,
MC[SV.stkp, 10];* breakbyte, stkp: BYTE,
MC[SV.dst, 11];* dst: ControlLink,
MC[SV.src, 12];* src: ControlLink ];
* Microcode knows that SIZE[StateVector] = 13B !!
* Fixed memory locations
MC[CurrentPSB, 21];
MC[ReadyList, 22];
* MC[CurrentState, 23];* Defined in DMesaDefs.mc
MC[NakedCVArray, 40];* Array of naked CVs (thru 57)
Set[FirstPSBLoc, 1075];* Pointer to first PSB
Set[LastPSBLoc, 1076];* Pointer to last PSB
Set[FirstSVLoc, 1077];* Pointer to first StateVector
* Other constants -- unpublished but apparently widely known!!
MC[TimerLoc, 344];* Address of process timer cell
* TimerLoc+1 counts timer interrupts per tick
MC[TimerChanMask, 20];* Timer interrupt channel
*-----------------------------------------------------------
IFUR[ME, 1, MLBR, N[2]];* MonitorEnter[pMonitorLock];
*-----------------------------------------------------------
:IfMEP;
StkP-1, Branch[.+2];
Stack&-1← MD, Branch[.+1];
StkP+1, Call[Pop1ShortOrLong];* MLBR← pMonitorLock
:Else;
Call[Pop1ShortOrLong];* MLBR← pMonitorLock
:EndIf;
* ml ← Fetch[m]↑;
* IF ml.lock = unlocked THEN
* BEGIN ml.lock ← locked; Store[m]↑ ← ml; Push[TRUE]; END
* ELSE BEGIN EnterFailed[m]; ReSchedule[TRUE]; END;
T← Fetch← RTemp0, Call[TestMonitorLock]; * RTemp0 = 0 here
Stack+1← (Store← T)+1, DBuf← Q, IFUNext0;
*-----------------------------------------------------------
IFUR[MRE, 1, CVBR, N[4]];* MonitorReEnter[pMonitorLock, pCondition];
*-----------------------------------------------------------
:IfMEP;
StkP-1, Branch[.+2];
Stack&-1← MD, Branch[.+1];
StkP+1, Call[Pop2ShortOrLong];* CVBR← pCondition, MLBR← pMonitorLock
:Else;
Call[Pop2ShortOrLong];* CVBR← pCondition, MLBR← pMonitorLock
:EndIf;
* ml ← Fetch[m]↑;
* IF ml.lock = unlocked THEN BEGIN ... <unlocked case> ... END
* ELSE EnterFailed[m]; ReSchedule[TRUE];
Fetch← RTemp0, Call[TestMonitorLock]; * RTemp0 = 0 here
* <unlocked case>:
* CleanUpCVQueue[c]; ml.lock ← locked; Store[m]↑ ← ml;
T← A0, MemBase← CVBR, Call[CleanUpCVQueue];
T← A0, MemBase← MLBR;
Store← T, DBuf← Q;
* Store[@cp.cleanUp]↑ ← NIL; cpf ← Fetch[@cp.flags];
* if cpf.abortPending THEN Trap[sProcessTrap] ELSE Push[TRUE];
RTemp0← A0, MemBase← PDA, Call[FetchCP&CPF];
T← (Process)+1;* @cp.cleanUp
PD← (RTemp1) AND (PSBF.abortPending);
Store← T, T← DBuf← RTemp0, Branch[.+2, ALU#0];
Stack+1← T+1, IFUNext0;* Push[TRUE] and exit
T← sProcessTrap, Branch[SavePCAndTrap];
*-----------------------------------------------------------
TestMonitorLock:
* Test and set monitor lock; shared by ME and MRE.
* Enter: monitor lock fetched
* Exit: if monitor is locked, goes to EnterFailed; otherwise:
*RTemp1 = Q = monitor lock value, with lock changed to "locked".
*-----------------------------------------------------------
Subroutine;
RTemp1← MD;
RTemp1← (RTemp1) AND (77777C), Branch[EnterFailed, R>=0];
Q← RTemp1, Return;
TopLevel;
*-----------------------------------------------------------
IFUR[MXD, 1, MLBR, N[2]];* MonitorExitAndDepart[pMonitorLock];
*-----------------------------------------------------------
:IfMEP;
StkP-1, Branch[.+2];
Stack&-1← MD, Branch[.+1];
StkP+1, Call[Pop1ShortOrLong];* MLBR← pMonitorLock
:Else;
Call[Pop1ShortOrLong];* MLBR← pMonitorLock
:EndIf;
* ExitMonitor[m]; Reschedule[TRUE];
T← A0, Call[ExitMonitor];* Returns with T=0, RTemp1=ml
RTemp1← (Store← T)+1, DBuf← RTemp1, Branch[MesaReschedule1]; * IL=1
*-----------------------------------------------------------
IFUR[MXW, 1, CVBR, N[4]];* MonitorExitAndWait
* [pMonitorLock, pCondition, ticks];
*-----------------------------------------------------------
T← Stack&-1, Branch[MXWM2];
:IfMEP;
T← Stack&-1← MD, Branch[.+1];
:EndIf;
MXWM2:RTemp3← T, Call[Pop2ShortOrLong]; * RTemp3← ticks,
* CVBR← pCondition, MLBR← pMonitorLock
* [] ← Fetch[m]↑; CleanUpCVQueue[c]; ExitMonitor[m];
T← Fetch← RTemp0, FlipMemBase, Call[CleanUpCVQueue];
T← A0, MemBase← MLBR, Call[ExitMonitor];
Store← T, DBuf← RTemp1;
* cp ← Fetch[currentPSB]↑; cpf ← Fetch[@cp.flags]↑;
* IF ~cpf.abortPending THEN ...
MemBase← PDA, Call[FetchCP&CPF];
PD← (RTemp1) AND (PSBF.abortPending);
RTemp0← A0, MemBase← CVBR, Branch[.+2, ALU=0];
RTemp1← ID, Branch[MesaReschedule1];
* BEGIN cv ← Fetch[c]↑;
* IF cv.wakeupWaiting = yes THEN
* BEGIN cv.wakeupWaiting ← no; Store[c]↑ ← cv; END ...
Fetch← RTemp0, RTemp0← T;* RTemp0← @cp.flags
RTemp2← MD, T← PSBF.waitingOnCV;
RTemp2← (RTemp2) AND (77777C), Branch[.+2, R>=0];
Store← 0S, DBuf← RTemp2, Branch[MesaReschedule];
* ... ELSE BEGIN
* cpf.waitingOnCV ← TRUE; Store[@cp.flags]↑ ← cpf;
* IF ticks#0 THEN
* BEGIN ticks ← currentTime+ticks; IF ticks=0 THEN ticks←1; END;
* Store[@cp.timeout]↑ ← ticks;
* Requeue[src: ready, dst: c, process: cp];
* END;
T← (RTemp1) OR T, MemBase← PDA;
Store← RTemp0, DBuf← T;
SQBRReg← BRConst[RQBR], Call[SetReadyQBR]; * src = ReadyQ
MemBase← PDA;
DQBRReg← BRConst[CVBR], Call[Requeue]; * dst = CV
T← TimerLoc;
Fetch← T, PD← RTemp3;
RTemp3← (RTemp3)+MD, Branch[ZeroTimeout, ALU=0];
T← (PSB.timeout)+(Process), Branch[.+2, ALU#0];
RTemp3← (RTemp3)+1;
Store← T, DBuf← RTemp3;
* If supplied ticks = 0, don’t need to store timeout at all, since
* Requeue zeroed it.
ZeroTimeout:
RTemp1← ID, Branch[MesaReschedule1];
*-----------------------------------------------------------
IFUR[NOTIFY, 1, CVBR, N[2]];* Notify[pCondition];
*-----------------------------------------------------------
:IfMEP;
StkP-1, Branch[.+2];
Stack&-1← MD, Branch[.+1];
:EndIf;
RTemp3← A0, Branch[BCASTM1];
*-----------------------------------------------------------
IFUR[BCAST, 1, CVBR, N[2]];* Broadcast[pCondition];
*-----------------------------------------------------------
:IfMEP;
StkP-1, Branch[.+2];
Stack&-1← MD, Branch[.+1];
:EndIf;
RTemp3← 77777C, Branch[BCASTM1];
:IfMEP;
BCASTM1:
StkP+1, Call[Pop1ShortOrLong];* CVBR← pCondition
:Else;
BCASTM1:
Call[Pop1ShortOrLong];* CVBR← pCondition
:EndIf;
* This code is shared by NOTIFY and BCAST.
* RTemp3 has the appropriate mask for testing whether to follow the chain
* past the first PSB: 0 if NOTIFY, 77777 if BCAST.
* CleanUpCVQueue[c];
* DO cv ← Fetch[c]↑; IF cv.queue=NIL THEN EXIT; WakeHead[c]; ENDLOOP;
* Reschedule[TRUE];
T← A0, Call[CleanUpCVQueue];* Returns ALU = CV.queue
BroadcastLoop:
Branch[.+2, ALU#0];
RTemp1← ID, Branch[MesaReschedule1];
Nop;* Placement
Call[WakeHead];
T← A0, MemBase← CVBR;
Fetch← T, T← RTemp3;
Process← T AND MD, Branch[BroadcastLoop];
*-----------------------------------------------------------
IFUR[REQUEUE, 1, CVBR, N[4]];* Requeue
*[sourceQueueHandle, destQueueHandle, processHandle];
*-----------------------------------------------------------
T← Stack&-1, Branch[REQUEUEM2];* PSB handle
:IfMEP;
T← Stack&-1← MD, Branch[.+1];
:EndIf;
REQUEUEM2: Process← T, Call[Pop2ShortOrLong]; * CVBR← destQ, MLBR← sourceQ
SQBRReg← T-T-1, Branch[.+2, ALU=0]; * Branch if sq=NIL
SQBRReg← BRConst[MLBR];* sourceQueueHandle in MLBR
DQBRReg← BRConst[CVBR];* destQueueHandle in CVBR
Branch[Requeue&Resched];
*-----------------------------------------------------------
Pop2ShortOrLong:
* Pop two short or long pointers and load base registers.
* Enter: MemBase, MemBase xor 1 = first and second BRs to be loaded
*ID = 4
* Exit:RTemp0 = 0
*MemBase = entering MemBase xor 1
*Both BRs loaded
*ID advanced
*T = ALU = 0 iff second pointer is NIL
*DQBRReg >= 0 (i.e., Requeue flag initialized to 0, if relevant)
* Clobbers RTemp0, RTemp1, DQBRReg
*-----------------------------------------------------------
RTemp1← Link, Call[Pop1ShortOrLong];
Link← RTemp1;
Subroutine;
PD← DQBRReg, FlipMemBase, Branch[Pop1Tail];
*-----------------------------------------------------------
Pop1ShortOrLong:
* Pop one short or long pointer and load base register.
* Enter: MemBase = BR to be loaded
*ID = 2
* Exit:RTemp0 = 0
*MemBase unchanged
*BR loaded
*ID advanced
*T = ALU = 0 iff pointer is NIL
*DQBRReg >= 0 (i.e., Requeue flag initialized to 0, if relevant)
* Clobbers RTemp0, DQBRReg
*-----------------------------------------------------------
Subroutine;
DQBRReg← TIOA&StkP;
DQBRReg← (ID) AND (DQBRReg);
Pop1Tail:
RTemp0← T← A0, Branch[.+2, ALU#0];
* Short pointer, lengthen it with high part of MDS.
BRHi← MDSHi, Branch[.+2];
* Long pointer, pop high part off stack.
T← BRHi← Stack&-1;
T← (BRLo← Stack&-1) OR T, Return;
*-----------------------------------------------------------
FetchCP&CPF:
* Fetches current process and current process’s flags.
* Enter: MemBase = PDA
* Exit:Process = processHandle for current PSB
*RTemp1 = processHandle↑.flags
*T = pointer to processHandle↑.flags
*-----------------------------------------------------------
Subroutine;
T← CurrentPSB;
Fetch← T;
Process← MD, T← (PSB.flags)+MD;
Fetch← T;
RTemp1← MD, Return;
*-----------------------------------------------------------
SetReadyQBR:
* Sets up RQBR to point to the Ready queue
* Exit:MemBase = RQBR
*BR loaded
*RTemp0 = -1
*-----------------------------------------------------------
Subroutine;
MemBase← RQBR;
BRHi← PDAHi;
RTemp0← ReadyList;
RTemp0← (BRLo← RTemp0)-(RTemp0)-1, Return;
*-----------------------------------------------------------
EnterFailed:
* Enter: MLBR points to monitor lock
* Exit: Does not return but rather goes directly to MesaReschedule
*-----------------------------------------------------------
TopLevel;
DQBRReg← BRConst[MLBR];* dst = ML
SQBRReg← BRConst[RQBR], Call[SetReadyQBR]; * src = ReadyQ
* cp ← Fetch[currentPSB]↑; cpf ← Fetch[@cp.flags]↑;
MemBase← PDA, Call[FetchCP&CPF];
* cpf.enterFailed ← TRUE; Store[@cp.flags]↑ ← cpf;
* Requeue[src: ready, dst: m, process: cp];
* Here RTemp1 has cpf and T has @cp.flags.
RTemp1← (RTemp1) OR (PSBF.enterFailed);
Store← T, DBuf← RTemp1, Branch[Requeue&Resched];
*-----------------------------------------------------------
ExitMonitor:
* Unlocks monitor, and moves process at head of monitor lock queue to
* ready queue, if there is one.
* Enter: T = 0
*MemBase = MLBR
*MLBR = QueueHandle for MonitorLock
* Exit:MemBase = MLBR
*T = 0
*RTemp1 = adjusted MonitorLock value (lock = unlocked)
*Clobbers T, Q, RTemp0, RTemp1, RTemp2, Process
*-----------------------------------------------------------
Subroutine;
* ml ← Fetch[m]↑; p ← ml.queue;
* IF p#NIL THEN ...
Fetch← T, SQBRReg← BRConst[MLBR];* src = ML
T← Process← PD← MD;
Q← Link, Branch[.+2, ALU#0];
RTemp1← 100000C, Return;* Queue empty, exit quickly
* BEGIN p ← Fetch[@p.link]↑; Requeue[src: m, dst: ready, process: p]; END;
TopLevel;
MemBase← PDA;
Fetch← T, DQBRReg← BRConst[RQBR], Call[SetReadyQBR]; * dst = ReadyQ
Process← MD, MemBase← PDA, Call[Requeue];
* ml ← Fetch[m]↑; ml.lock ← unlocked; Store[m]↑ ← ml;
T← A0, MemBase← MLBR;
RTemp1← 100000C, Fetch← T;
Link← Q;
Subroutine;
RTemp1← (RTemp1) OR MD, Return;
*-----------------------------------------------------------
WakeHead:
* Wakes the process at the head of the CV queue (there must be one).
* Enter: CVBR = QueueHandle for CV
*Process = CV.queue (note that WW bit must be stripped off)
* Exit:MemBase = PDA
*Clobbers T, RTemp0, RTemp1, RTemp2, Process, SQBRReg, DQBRReg
*-----------------------------------------------------------
Subroutine;
RTemp1← Link;
TopLevel;
DQBRReg← BRConst[RQBR], Call[SetReadyQBR]; * dst = ReadyQ
T← Process, MemBase← PDA;
* p ← Fetch[@p.link]↑; pf ← Fetch[@p.flags]↑;
Fetch← T, SQBRReg← BRConst[CVBR]; * src = CV
Process← MD, T← (PSB.flags)+MD;
Fetch← T, RTemp0← Not[PSBF.waitingOnCV!]C;
* pf.waitingOnCV ← FALSE; Store[@p.flags]↑ ← pf;
RTemp0← (RTemp0) AND MD;
RTemp0← Store← T, DBuf← RTemp0;* RTemp0#0 for Requeue
* Requeue[src: c, dst: ready, process: p];
Link← RTemp1, Branch[Requeue];* Link← overrides implied Call
*-----------------------------------------------------------
Requeue:
* Moves a process from a source queue to a destination queue.
* 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 = ProcessHandle
*MemBase = PDA
* Exit:MemBase = PDA
*Clobbers T, RTemp0, RTemp1, RTemp2
*-----------------------------------------------------------
Subroutine;
* Here we compute "pp", the predecessor of process, and put it in RTemp1.
* IF Fetch[@process.link]↑ = process THEN pp ← NIL ...
T← Fetch← Process, Global;
RTemp1← T#MD;
RTemp0← T+1, T← MD, Branch[RequeueGotPP, ALU=0];
* ... ELSE BEGIN pp ← IF sq=NIL THEN process ELSE Fetch[sq]↑;
* Keep pp in MD for a while, and save process.link in T.
* Note that we actually start with Fetch[@process.link]↑ rather than process,
* but that’s ok since we already checked for Fetch[@process.link]↑ = process.
MemBase← SQBRReg, Branch[.+2, R odd]; * Branch if sq=NIL
Fetch← 0S;
* Search for predecessor of Process in ring. MD is where to start.
* WHILE Fetch[@pp.link]↑ # process DO pp ← Fetch[@pp.link]↑; ENDLOOP;
MemBase← PDA;
RTemp1← Fetch← MD;
PD← (Process)#MD;
Branch[.-2, ALU#0];
* Now RTemp1 has predecessor of process. Bypass process in queue structure.
* Store[@pp.link]↑ ← Fetch[@process.link]↑; END;
Store← RTemp1, DBuf← T;
* RTemp1 = predecessor of process, or 0 if wasn’t one. T = process.link.
* RTemp0 = @process.cleanUp.
* IF sq=NIL THEN Store[@process.cleanUp]↑ ← Fetch[@process.link]↑
* ELSE IF Fetch[sq]↑ = process THEN Store[sq]↑ ← pp;
RequeueGotPP:
MemBase← SQBRReg, Branch[.+2, R even]; * Branch if sq#NIL
MemBase← PDA, Branch[StorePPOrCleanUp];
RTemp0← Fetch← 0S;* Fetch[sq]
PD← (Process)#MD;
T← RTemp1, Branch[.+2, ALU#0];
StorePPOrCleanUp:
Store← RTemp0, DBuf← T;* Store[sq]↑ ← pp
* Requeue (cont’d)
* Now begin to insert process into dq. First, test for the easy case
* in which dq is initially empty.
* While we are at it, zero process.timer so as to disable timeouts.
* (This is logically a part of WakeHead, but it’s easier to do here.)
* Store[@process.timeout]↑ ← Ticks[0];
* pp ← Fetch[dq]↑; IF pp=NIL THEN ...
T← A0, MemBase← DQBRReg;
RTemp0← Fetch← T;* Fetch[dq]↑
T← (PSB.timeout)+(Process);
RTemp1← PD← MD, MemBase← PDA;
T← (Store← T)+1, DBuf← RTemp0,* Know @PSB.flags = @PSB.timeout+1
Branch[CheckDQTail, ALU#0];
* dq is empty. Simply put process onto dq and link it to itself.
* ... BEGIN Store[@process.link]↑ ← process; Store[dq]↑ ← process; END
T← A0, MemBase← DQBRReg;
Store← T, T← DBuf← Process;
RTemp0← T, MemBase← PDA, Branch[RequeueFinish];
* dq 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; T points to process↑.flags.
* ... ELSE BEGIN pri ← Fetch[@process.flags]↑.priority;
* IF pri <= Fetch[@pp.flags]↑.priority THEN ...
CheckDQTail:
Fetch← T;
T← (PSB.flags)+(RTemp1);
Fetch← T, RTemp2← MD, T← PSBF.priority;
RTemp2← (RTemp2) AND T;* RTemp2← process’s priority
T← T AND MD;* T← pp’s priority
PD← (RTemp2)-T-1;
* Top of search loop; RTemp1 = pp; ALU<0 if process↑.priority <= pp↑.priority.
* ALU>=0 here always if came from SearchDQ (below).
SearchDQLoop:
RTemp0← Fetch← RTemp1, Branch[SearchDQ, ALU>=0];
* Process lower priority than tail. Just make process be new tail.
* ... Store[dq]↑ ← process ...
T← A0, MemBase← DQBRReg;
Store← T, DBuf← Process, T← MD;
MemBase← PDA, Branch[RequeueLinkDQ];
* Have to search dq to find proper place to insert process.
* Insert after last process whose priority is >= that of process.
* ... ELSE DO tp ← Fetch[@pp.link]↑;
* IF pri <= Fetch[@tp.flags]↑.priority then pp ← tp ELSE EXIT;
* ENDLOOP;
SearchDQ:
RTemp1← MD, T← (PSB.flags)+MD;
Fetch← T;
T← (Add[PSBF.priority!]S) AND MD;
PD← (RTemp2)-T-1;
* Note: set ALU>=0 here -- know ProcessHandles are IN [0..77777B].
T← RTemp1, Branch[SearchDQLoop, ALU<0];
* Now RTemp0 = pp = the process after which we are to insert;
* T = tp = that process’s successor.
* Store[@process.link]↑ ← Fetch[@pp.link]↑;
* Store[@pp.link]↑ ← process;
RequeueLinkDQ:
T← Store← Process, DBuf← T;
RequeueFinish:
Store← RTemp0, DBuf← T, Return;
*-----------------------------------------------------------
CleanUpCVQueue:
* Cleans up CV queue that may have been left in a mess by Requeue.
* Enter: MemBase = CVBR
*CVBR points to condition variable
*T = 0
* Exit:MemBase = CVBR
*ALU = Process = CV.queue (as modified by subroutine, if necessary)
*Clobbers T, RTemp0
*-----------------------------------------------------------
Subroutine;
T← 77777C, Fetch← T;* Fetch pCondition↑
Process← T AND MD, MemBase← PDA; * RTemp0← pCondition↑.queue
T← (Process)+1, Branch[.+2, ALU#0];
PD← Process, MemBase← CVBR, Return; * Queue is empty, nothing to do
Fetch← T;* Fetch process↑.cleanUp
PD← MD;
SearchForCVQHead:
PD← MD, Branch[.+2, ALU#0];* Always branches 2nd time and after
PD← Process, MemBase← CVBR, Return; * No cleanup queue, nothing to do
* Process has a processHandle to check, and ALU = MD = process↑.cleanUp.
* Follow process↑.cleanUp links until we either hit NIL or
* find a PSB with a cleanUp link pointing to itself.
Process← MD, PD← (Process)#MD, Branch[FoundCVQHead, ALU=0];
T← (Process)+1, Branch[CVQEmpty, ALU=0];
PD← (Fetch← T)-T-1, Branch[SearchForCVQHead]; * Fetch cleanUp link
* 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.
CVQEmpty:
T← Process← A0, MemBase← CVBR, 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.
* T = new head process +1 here.
FoundCVQHead:
RTemp0← T← T-1;* RTemp0← tail
SearchForCVQTail:
Process← Fetch← T;* Fetch process↑.link
T← MD, PD← (RTemp0)#MD;
Branch[SearchForCVQTail, ALU#0];
* Process now points to the predecessor of RTemp0.
T← A0, MemBase← CVBR;
StoreCVQueue:
Store← T, PD← DBuf← Process, Return; * pCondition↑ ← Process
*-----------------------------------------------------------
IFUR[IWDC, 1, L];* Increment Wakeup Disable Counter: wdc ← wdc+1;
*-----------------------------------------------------------
WDC← (WDC)+1, RBase← RBase[NWW], Branch[IWDCM1];
:IfMEP;
Stack← MD, Branch[.-1];
StkP+1, Branch[.-2];
:EndIf;
IWDCM1:
NWW ← (NWW) OR (100000C), IFUNext0;
*-----------------------------------------------------------
IFUR[DWDC, 1, L];* Decrement Wakeup Disable Counter: wdc ← wdc-1;
* Note: one instruction must be executed after DWDC before an
* interrupt is permitted to occur. (This is accomplished by the
* NoReschedule .. Reschedule in UpdateNWW.)
*-----------------------------------------------------------
:IfMEP;
Branch[DWDCM1];
Stack← MD, Branch[DWDCM1];
StkP+1, Branch[DWDCM1];
:EndIf;
DWDCM1: * Also get here from WRM
WDC← (WDC)-1, RBase← RBase[NWW], Call[UpdateNWW];
IFUNext0;
*-----------------------------------------------------------
UpdateNWW:
* Subroutine to update NWW to reflect new state of WDC and initiate
* a Reschedule request if an interrupt is pending.
* Entry conditions: ALU=WDC, RBase=RBase[NWW]
* Exit conditions: RBase=RBase[NWW].
*-----------------------------------------------------------
Subroutine;
KnowRBase[NWW];
NWW← (NWW) AND NOT (100000C), Branch[DisableNWW, ALU#0];
PD← NWW, NoReschedule, Branch[.+3, Reschedule’];
* If a Reschedule was already pending, we must restart the IFU in order to
* prevent a reschedule trap from occurring on the next IFUJump, even though
* we have already done a NoReschedule.
T← (ID)-(PCX’)-1;
PD← NWW, PCF← T;
* Actually, should Reschedule only if WDC=0 now, but incrementing WDC
* more than once is uncommon, and MesaReschedTrap will sort this out anyway.
* Note that Reschedule doesn’t take effect until the second successful IFUJump.
Branch[.+2, ALU=0];
Reschedule;
Return;
* Unnecessary to worry about possibility of Reschedule trap when disabling
* interrupts, since MesaReschedTrap ignores traps when interrupts are disabled.
DisableNWW:
NWW← (NWW) OR (100000C), Return;
TopLevel;
*-----------------------------------------------------------
* These are exception entries for the Mesa instruction set
*-----------------------------------------------------------
Set[MesaTrapBase, Sub[300, LShift[MesaInsSet, 6]]];
DontKnowRBase;
TopLevel;
MesaIFUNotReady:
At[MesaTrapBase, 34], IFUNext0;
:IfMEP;
At[MesaTrapBase, 35], T← Stack&-1← MD, IFUNext2;
At[MesaTrapBase, 36], IFUNext2;
:EndIf;
*-----------------------------------------------------------
* Reschedule trap and interrupt processing
*-----------------------------------------------------------
MesaReschedTrap:
At[MesaTrapBase, 14], RBase← RBase[NWW], Branch[MesaResc1];
:IfMEP;
At[MesaTrapBase, 15], Stack← MD, RBase← RBase[NWW], Branch[MesaResc1];
At[MesaTrapBase, 16], StkP+1, RBase← RBase[NWW], Branch[MesaResc1];
:EndIf;
* 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 an IFUNext0.
* Invariant: NWW<0 iff WDC#0; therefore, need not check WDC explicitly.
MesaResc1:
NoReschedule;
T← NOT (Q← PCX’);* Q#0 => normal emulation
T← NWW, PCF← T;* NWW>0 means interrupt can take
Branch[MesaInterrupt, ALU>0];
* No interrupt is pending. Just resume execution.
IFUNext0;
*-----------------------------------------------------------
MesaInterrupt:
* Enter: RBase=AEmRegs
*T=NWW>0 (i.e., interrupts enabled and at least one request pending)
*Q#0 if interrupted from normal emulation; Q=0 if from idle loop.
*WDC=0
*-----------------------------------------------------------
* Turn off the wakeups pending on channels we are about to process.
* Make a special test for an interrupt occurring on the timer channel
* (60 hz), and do CheckForTimeouts when one occurs.
* As a side-effect, reset the "requeue performed" flag in DQBRReg.
NWW← (NWW) AND NOT T, RBase← RBase[RTemp0];
DQBRReg← T AND (TimerChanMask);
WDC← T, MemBase← PDA, Branch[CheckForTimeouts, ALU#0];
* For each interrupt that is pending, check the naked CV pointed to by
* the appropriate entry in NakedCVArray (these are PDA-relative pointers).
* Discard any interrupt directed to a NakedCVArray entry that is NIL.
* RTemp3 keeps the NakedCVArray pointer, and WDC is used to shift the
* interrupt request bits.
CheckNakedCVs:
RTemp3← NakedCVArray;
CheckNakedCVLoop:
PD← WDC, MemBase← PDA;
RTemp3← (Fetch← RTemp3)+1, Branch[NoMoreInts, ALU=0];
WDC← (WDC) RSH 1, Branch[.-1, R even];
T← PD← MD, MemBase← CVBR;
BRLo← T, Branch[CheckNakedCVLoop, ALU=0];
* Have an interrupt for a non-NIL NakedCVArray entry.
* If a process is waiting on the CV pointed to by the entry, wake it up;
* if no process is waiting, set the wakeupWaiting bit in the CV.
BRHi← PDAhi;
T← A0, Call[CleanUpCVQueue];
T← A0, Branch[.+2, ALU#0];
Store← T, DBuf← 100000C, Branch[CheckNakedCVLoop];
Nop;* Placement
Call[WakeHead];
Branch[CheckNakedCVLoop];
* All interrupt requests have been processed, and WDC=0 again.
* If we were interrupted from normal emulation (Q#0), do a Reschedule iff
* the interrupt actually caused any processes to be requeued.
* If we were interrupted from the idle loop (Q=0), go reconsider the ReadyQ.
NoMoreInts:
PD← Q;
RTemp1← A0, DblBranch[MesaReschedule1, IdleReschedule, ALU#0];
*-----------------------------------------------------------
CheckForTimeouts:
* This is invoked every time an interrupt is requested on the
* 60 hz timer channel. This microcode "knows" which channel the
* Mesa system enables for that purpose!
* Enter: MemBase = PDA
* Exit:MemBase = PDA
*Clobbers T, RTemp0-3, Process, DQBRReg, SQBRReg
*-----------------------------------------------------------
* Scan PSBs only every third tick
T← Add[TimerLoc!, 1]C;* Count up timer interrupts/tick
Fetch← T, Process← And[FirstPSBLoc, 177400]C;
RTemp0← MD+1;
Process← (Process) OR (And[FirstPSBLoc, 377]C), Branch[.+2, ALU>=0];
Store← T, DBuf← RTemp0, Branch[CheckNakedCVs]; * Not this time
* Fetch PSB array bounds and update timer
T← (Store← T)-1, DBuf← -3C;* Reset interrupts/tick count
Fetch← T;
RTemp0← MD+1;* RTemp0← updated current time
Store← T, DBuf← RTemp0;
T← (Fetch← Process)+1;
Process← MD, Fetch← T;* Process← first PSB
RTemp3← MD;* RTemp3← last PSB
* For each process, if PSB.timeout#0 (i.e., enabled to timeout) and
* PSB.timeout=currentTime, then put the process back on the readyQ.
* FOR p ← Fetch[firstPSB]↑, p+SIZE[PSB] UNTIL p=Fetch[lastPSB]↑ DO
* time ← Fetch[@p.timeout]↑;
* IF time#Ticks[0] AND time=currentTime THEN ...
CheckTimerLoop:
T← (PSB.timeout)+(Process);
T← (Fetch← T)+(Sub[SizePSB!, PSB.timeout!]C); * T← next process
PD← MD;
PD← (RTemp0)-MD, Branch[CanTimeout, ALU#0];
PD← (RTemp3)-T;* Beyond last PSB?
NoTimeout:
Process← T, Branch[CheckTimerLoop, ALU>=0];
Branch[CheckNakedCVs];
CanTimeout:
PD← (RTemp3)-T, Branch[NoTimeout, ALU#0];
* pf ← Fetch[@process.flags]↑; pf.waitingOnCV ← FALSE;
* Store[@process.flags]↑ ← pf;
* Requeue[src: NIL, dst: ready, process: process];
DQBRReg← BRConst[RQBR], Call[SetReadyQBR]; * dst = ReadyQ
SQBRReg← T-T-1, MemBase← PDA, Call[Requeue]; * src = NIL
T← (PSB.flags)+(Process);
Fetch← T, RTemp0← Not[PSBF.waitingOnCV!]C;
RTemp0← (RTemp0) AND MD;
* Will check the current process’s timer again, but Requeue zeroed it
* so no matter.
RTemp1← TimerLoc;* Re-fetch currentTime
Fetch← RTemp1;
Store← T, DBuf← RTemp0, RTemp0← MD, Branch[CheckTimerLoop];
*-----------------------------------------------------------
Requeue&Resched:
* Do a Requeue followed by a Reschedule.
* Arguments as for Requeue.
*-----------------------------------------------------------
MemBase← PDA, Call[Requeue];
*-----------------------------------------------------------
MesaReschedule:
* 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.
*-----------------------------------------------------------
TopLevel;
RTemp1← ID;* RTemp1← IL
* Here RTemp1 = 0 if came from MesaInterrupt; = IL if came from
* process/monitor opcode.
* IF ~reschedulePending THEN RETURN;
MesaReschedule1:
MemBase← PDA, DQBRReg, Branch[.+2, R<0];
IFUNext0;* No Requeue, resume normal execution
* Save state of current process.
* cs ← Fetch[currentState]↑; SaveState[cs];
* StoreMDS[@LocalBase[L].pc]↑ ← PC;
* cp ← Fetch[currentPSB]↑; Store[@cp.frame]↑ ← L;
T← CurrentState;
Fetch← T, RTemp2← CurrentPSB;
RTemp1← (RTemp1)-(PCX’)-1, Call[SavePCInFrame]; * PCX or PCX+IL
DLink← T, MemBase← PDA;* DLink← L
RTemp0← MD, Call[SaveState];* RTemp0 = where to save the state
Fetch← RTemp2;* CurrentPSB↑
Store← T, DBuf← SLink, T← MD;* Finish saving state
T← (PSB.frame)+T;
Store← T, DBuf← DLink;* CurrentPSB↑.frame ← L
* Check ready queue for new process to run
* IF Fetch[ready]↑ = NIL THEN ...
IdleReschedule:
T← ReadyList;
Fetch← T, RTemp0← And[FirstSVLoc, 177400]C;
Process← PD← Q← MD;
PD← WDC, Branch[SetupNewProcess, ALU#0];
* Ready queue is empty.
* 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.
* ... BEGIN IF wdc#0 THEN WakeError[];
* DO IF wp#0 THEN RETURN; ENDLOOP; END
* Note that RETURN with wp#0 implies that CheckForInterrupts will happen
* before any additional instructions can be executed. But we can’t implement
* it that way on the Dorado; therefore, branch directly to MesaInterrupt.
T← sWakeupError, Branch[.+2, ALU=0];
Branch[MTrap];* It’s an error to be idle with WDC#0
PD← A0, RBase← RBase[NWW];
PD← NWW, NoReschedule, Branch[., ALU=0];
T← NWW, Branch[MesaInterrupt];* Q=0 => will return to IdleReschedule
* MesaReschedule (cont’d)
KnowRBase[RTemp0];
* Have a process ready to run.
* Process = tail of ready list. Set up to run head process.
* np ← Fetch[@np.link]↑; pf ← Fetch[@np.flags]↑;
SetupNewProcess:
Fetch← Process;
Process← MD, T← (PSB.flags)+MD;
RTemp2← Fetch← T;
* state ← Fetch[FirstSV]↑ + SIZE[StateVector]*pf.priority.
* This code knows that SIZE[StateVector] = 13B, and does the multiply
* by the shift-and-add method.
RTemp0← (RTemp0) OR (And[FirstSVLoc, 377]C);
RTemp1← MD, T← (Add[PSBF.priority!]S) AND MD;
Fetch← RTemp0, Q← T;
T← LSH[T, 3];
T← T+Q, Q LSH 1;
T← T+Q;
RTemp0← T+MD;
* If we are resuming a process waiting on a monitor lock, store FALSE
* on its stack before resuming it.
* Process = np, RTemp1 = flags, RTemp0 = state, RTemp2 = @np.flags.
* IF pf.enterFailed THEN BEGIN
* Store[@state.stkp]↑ ← 1; Store[@state.stack[0]]↑ ← FALSE;
* pf.enterFailed ← FALSE; Store[@np.flags]↑ ← pf; END;
T← (RTemp1) AND (77777C), Branch[NotWaitingML, R>=0];
Store← RTemp2, DBuf← T, T← A0;* Store flags
Store← RTemp0, DBuf← T;* Store stack[0]
T← (RTemp0)+(SV.stkp);
Store← T, DBuf← 1C;* Store stkp
* Now set up the state for the new process.
* Process = np, RTemp0 = state.
* Store[@state.dst]↑ ← Fetch[@np.frame]↑;
* Store[currentPSB]↑ ← np; Store[currentState]↑ ← state;
* LoadState[state];
NotWaitingML:
T← (PSB.frame)+(Process);
Fetch← T, T← CurrentPSB;
Store← T, DBuf← Process;* Store currentPSB
T← (RTemp0)+(SV.dst);
Store← T, DBuf← MD, XferFlags← A0; * Store state.dst
T← CurrentState;
Store← T, DBuf← RTemp0, Branch[LoadState]; * Store currentState