ProcessImpl.mesa
last edited by Levin on August 8, 1983 11:03 am
Last edited by Andrew Birrell on April 20, 1983 6:34 pm
DIRECTORY
Basics USING [BITSHIFT, LongNumber],
MesaRuntimeInit USING [StateVectorCounts],
PrincOps USING [
Condition, ConditionVariable, ControlLink, FaultIndex, Frame, FrameHandle, FrameSizeIndex, InterruptItem, NoTimeout, NullFrame, NullLink, NullPsbHandle, NullStateVectorHandle, PDA, PDABase, Priority, ProcessDataArea, ProcessState, ProcessStateBlock, PsbHandle, PsbIndex, PsbLink, PsbNull, Queue, SD, sFork, sJoin, sProcessTrap, StartPsb, StateVector, StateVectorHandle, Ticks],
Process USING [
DisableTimeout, EnableAborts, Milliseconds, Priority, priorityFaultHandlers, SetPriority, SetTimeout, Ticks],
PrincOpsUtils USING [
Alloc, Broadcast, COPY, DisableInterrupts, EnableAndRequeue, EnableInterrupts, Enter, Exit, FrameSize, Free, GetReturnFrame, MyLocalFrame, Notify, PsbHandleToIndex, PsbIndexToHandle, ReadPSB, ReEnter, Requeue, Wait, WritePSB, WriteWDC];
ProcessImpl: MONITOR [
pdaWords: CARDINAL, svCounts: MesaRuntimeInit.StateVectorCounts, wordsPerSV: CARDINAL,
reservedNakedNotifyMask: WORD, millisecondsPerTick: CARDINAL]
LOCKS processLock
IMPORTS Basics, PrincOpsUtils, Process
EXPORTS MesaRuntimeInit, PrincOpsUtils, Process =
BEGIN
OPEN PrincOps, Basics;
Types and Related Declarations
FsiFrame: TYPE = MACHINE DEPENDENT RECORD [
fsi (0): FrameSizeIndex, -- must be at 3 MOD 4 boundary.
frame (1): local Frame];
NakedNotifyLevel: TYPE = [0..--VM.bitsPerWord--16);
DyingFrameHandle: TYPE = POINTER TO dying Frame;
Global Variables (protected by processLock)
processLock: MONITORLOCK;
rebirth: CONDITION; -- queue of unused processes.
frameReady: CONDITION; -- queue of parents waiting to rejoin their child.
frameTaken: CONDITION; -- queue of children waiting to rejoin their parent.
dead: CONDITION; -- queue of parents waiting for their child to clean up.
deadFrame: DyingFrameHandle ← NIL; -- the top-level frame of a detached process which needs to be freed.
busyLevels: PACKED ARRAY NakedNotifyLevel OF BOOL;
This really should be protected by a completely separate monitor from the above, but it isn't worth the trouble.
Exported to Process
Initializing monitors and condition variables
MsecToTicks: PUBLIC SAFE PROC [ms: Process.Milliseconds] RETURNS [Process.Ticks] = TRUSTED {
RETURN[
(IF ms >= Process.Milliseconds.LAST-(millisecondsPerTick-1) THEN
Process.Milliseconds.LAST -- (avoid overflow)
ELSE ms + millisecondsPerTick-1)
/ millisecondsPerTick
]
};
SecondsToTicks: PUBLIC SAFE PROC [sec: CARDINAL] RETURNS [Process.Ticks] = TRUSTED {
ticks: LongNumber = [lc[(sec.LONG*1000 + millisecondsPerTick-1) / millisecondsPerTick]];
RETURN[IF ticks.highbits ~= 0 THEN Ticks.LAST ELSE ticks.lowbits]
};
TicksToMsec: PUBLIC SAFE PROC [ticks: Ticks] RETURNS [Process.Milliseconds] = TRUSTED {
RETURN[
IF ticks > Process.Milliseconds.LAST/millisecondsPerTick THEN
Process.Milliseconds.LAST
ELSE ticks*millisecondsPerTick
]
};
Detaching processes
Detach: PUBLIC ENTRY PROCEDURE [process: PROCESS] =
BEGIN
h: PsbHandle;
IF (h ← ValidProcess[process]) = NullPsbHandle THEN
RETURN WITH ERROR InvalidProcess[LOOPHOLE[process, UNSPECIFIED]];
PDA[h].flags.processState.detached ← TRUE;
BROADCAST frameTaken; -- wake child if waiting to JOIN.
END;
Aborting a process
Abort: PUBLIC ENTRY PROCEDURE [process: PsbIndex] = {
h: PsbHandle;
IF (h ← ValidProcess[process]) = NullPsbHandle THEN
RETURN WITH ERROR InvalidProcess[process];
PrincOpsUtils.DisableInterrupts[]; -- (also stops ProcessTimeoutCounter from ticking.)
IF ProcState[h].state = alive THEN {
PDA[h].flags.abort ← TRUE;
IF PDA[h].flags.waiting THEN {
Wake the victim up.
PDA[h].flags.waiting ← FALSE;
PDA[PDA.timeout][PrincOpsUtils.PsbHandleToIndex[h]] ← NoTimeout;
TEMP until microcode uses timeout vector:
PDA[h].--timeout--mds ← NoTimeout;
PrincOpsUtils.Requeue[NIL, @PDA.ready, h];
};
};
PrincOpsUtils.EnableInterrupts[];
};
Control of Scheduling
Pause: PUBLIC ENTRY SAFE PROC [ticks: Process.Ticks] = TRUSTED {
ENABLE ABORTED => GO TO Aborted;
c: CONDITION;
Process.SetTimeout[@c, ticks];
Process.EnableAborts[@c];
WAIT c;
EXITS
Aborted => RETURN WITH ERROR ABORTED;
};
SetTimeSlice: PUBLIC ENTRY SAFE PROC [ticks: Process.Ticks] = TRUSTED {
IF pSchedulingInterval = NIL THEN RETURN;
pSchedulingInterval^.timeout ← ticks;
NOTIFY pSchedulingInterval^;
};
Process validation
ValidateProcess: PUBLIC ENTRY PROC [p: PsbIndex] = {
IF ValidProcess[p] = NullPsbHandle THEN RETURN WITH ERROR InvalidProcess[p];
};
InvalidProcess: PUBLIC ERROR [process: PsbIndex] = CODE;
Exported to PrincOpsUtils
AllocateNakedCondition: PUBLIC ENTRY PROC
RETURNS [cv: LONG POINTER TO CONDITION, mask: WORD] =
BEGIN
FOR level: NakedNotifyLevel IN NakedNotifyLevel DO
IF ~busyLevels[level] THEN {
busyLevels[level] ← TRUE;
RETURN[
cv: LOOPHOLE[@PDA.interrupt[level]],
mask: Basics.BITSHIFT[1, NakedNotifyLevel.LAST - level]
];
};
ENDLOOP;
ERROR
END;
DeallocateNakedCondition: PUBLIC ENTRY PROC [cv: LONG POINTER TO CONDITION] = {
FOR level: NakedNotifyLevel IN NakedNotifyLevel DO
IF busyLevels[level] AND
cv = LOOPHOLE[@PDA.interrupt[level], LONG POINTER TO CONDITION] THEN {
busyLevels[level] ← FALSE;
PDA.interrupt[level].condition.tail ← PsbNull;
RETURN;
};
ENDLOOP;
ERROR;
};
Internal Procedures
ProcState: PROC [psbh: PsbHandle] RETURNS [ProcessState] = INLINE {
RETURN[PDA[psbh].flags.processState]
};
ProcessTrap: PROC RETURNS [BOOL] =
This procedure is invoked by microcode when an aborted process attempts to reenter its monitor.
BEGIN
OPEN PrincOpsUtils;
Enter: PROC [a: POINTER TO MONITORLOCK] RETURNS [BOOL] = LOOPHOLE[Enter];
LongEnter: PROC [a,b: --LONG POINTER TO MONITORLOCK--UNSPECIFIED]
RETURNS [BOOLEAN] = LOOPHOLE[Enter];
abortee: FrameHandle;
state: RECORD [filler: UNSPECIFIED, v: StateVector];
state.v ← STATE;
Acquire abortee's monitor lock:
UNTIL
(IF state.v.stkptr = 4 THEN LongEnter[state.v.stk[0], state.v.stk[1]]
ELSE Enter[LOOPHOLE[state.v.stk[0], POINTER TO MONITORLOCK]])
DO ENDLOOP;
abortee ← GetReturnFrame[];
abortee.pc ← [abortee.pc + 1]; -- step past ME(L) instruction.
PDA[ReadPSB[]].flags.abort ← FALSE;
ERROR ABORTED;
if ABORTED is made resumable, we should return [monitorEntered: TRUE]
as the result of the MonitorEnter instruction that got us here.
END;
ValidProcess: INTERNAL PROC [p: --PsbIndex--UNSPECIFIED] RETURNS [h: PsbHandle] = INLINE {
This procedure returns NullPsbHandle if "p" is invalid.
RETURN[
IF ~(LOOPHOLE[p, PsbIndex] IN [StartPsb..StartPsb+PDA.count)) OR
ProcState[h ← PrincOpsUtils.PsbIndexToHandle[LOOPHOLE[p, PsbIndex]]].state IN [frameTaken..dead]
THEN NullPsbHandle ELSE h
]
};
Implementation of Language Constructs (FORK and JOIN)
Fork: PROC [--argsForRoot,-- root: ControlLink] RETURNS [childPsb: PsbIndex] = {
PForkFrame: TYPE = POINTER TO FRAME[Fork];
ChildBuilder: PROC [--parent's locals--] RETURNS [--MUST BE NULL!--] = {
pChild: LONG POINTER TO ProcessStateBlock ← @PDA.block[childPsb];
parentFrame: PForkFrame = LOOPHOLE[PrincOpsUtils.GetReturnFrame[]];
fsi: FrameSizeIndex = LOOPHOLE[parentFrame-1, POINTER TO FsiFrame].fsi;
childFrame: PForkFrame = PrincOpsUtils.Alloc[fsi];
PrincOpsUtils.COPY[
from: parentFrame, to: childFrame, nwords: PrincOpsUtils.FrameSize[fsi]];
childFrame.identity ← child;
pChild.link.failed ← FALSE;
pChild.link.priority ← PDA[PrincOpsUtils.ReadPSB[]].link.priority;
pChild.flags ← [
processState: [state: alive, detached: FALSE],
cleanup: PsbNull, waiting: FALSE, abort: FALSE
];
pChild.context ← [frame[LOOPHOLE[childFrame, FrameHandle]]];
TEMP until microcode uses timeout vector:
pChild.mds ← Inline.HighHalf[LONG[LOOPHOLE[1, POINTER]]];
pChild.mds ← NoTimeout;
PDA[PDA.timeout][childPsb] ← NoTimeout;
The following starts the new process executing. Its PC is set to begin execution at the instruction after the call to ChildBuilder. Its stack is empty. Therefore, ChildBuilder MUST NOT RETURN ANY RESULTS!
PrincOpsUtils.Notify[@rebirth];
};
identity: {parent, child};
argsForChild: StateVector;
argsForChild ← STATE; -- must be first! ("root" is automatically popped off the stack first.)
identity ← parent;
UNTIL PrincOpsUtils.Enter[@processLock] DO NULL ENDLOOP;
WHILE LOOPHOLE[rebirth, ConditionVariable].condition.tail = PsbNull DO
PrincOpsUtils.Wait[@processLock, @dead, LOOPHOLE[dead, ConditionVariable].timeout];
UNTIL PrincOpsUtils.ReEnter[@processLock, @dead] DO NULL ENDLOOP;
ENDLOOP;
childPsb ← PDA.block[LOOPHOLE[rebirth, ConditionVariable].condition.tail].link.next; -- walk to tail, then to head.
[] ← ChildBuilder[--my local vars--];
Both parent and child processes will execute the following code:
SELECT identity FROM
parent => {PrincOpsUtils.Exit[@processLock]; RETURN[childPsb]}; -- return child handle to FORKing parent.
child => {
To simulate a procedure call, we must also store dest and source links *above* the stack since ReturnWithState doesn't. (stack pointer is *not* incremented.)
argsForChild.stk[argsForChild.stkptr] ← root;
argsForChild.dest ← root;
Set child's top context to call End when it returns:
argsForChild.stk[argsForChild.stkptr+1] ← End;
argsForChild.source ← LOOPHOLE[End, ControlLink];
RETURN WITH argsForChild; -- "call" root procedure of child.
};
ENDCASE;
};
End: PROC = {
When the top context of a process "returns", it Xfers to this procedure with its results on the stack.
sv: RECORD [filler: UNSPECIFIED, results: StateVector];
frame: DyingFrameHandle;
h: PsbHandle;
sv.results ← STATE; -- save stack containing returned results.
UNTIL PrincOpsUtils.Enter[@processLock] DO NULL ENDLOOP;
frame ← LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
frame.state ← alive;
h ← PrincOpsUtils.ReadPSB[];
PDA[h].flags.processState.state ← frameReady;
PDA[h].flags.abort ← FALSE; -- too late for Aborts: they no-op
PrincOpsUtils.Broadcast[@frameReady]; -- wake any parent process waiting to Join.
Wait till this process is Detached or Joined:
UNTIL ProcState[h].state = frameTaken OR ProcState[h].detached DO
PrincOpsUtils.Wait[@processLock, @frameTaken, LOOPHOLE[frameTaken, ConditionVariable].timeout];
WHILE ~PrincOpsUtils.ReEnter[@processLock, @frameTaken] DO ENDLOOP;
ENDLOOP;
Free any frame left over from a previous dead detached process:
IF deadFrame ~= NIL THEN {PrincOpsUtils.Free[deadFrame]; deadFrame ← NIL};
IF ProcState[h].detached THEN deadFrame ← frame; -- If detached, leave our frame for freeing.
frame.state ← dead; -- tell Joiner that we're done.
PDA[h].flags.processState.state ← dead;
PrincOpsUtils.Broadcast[@dead]; -- tell parent our frame has been left for freeing.
PrincOpsUtils.Wait[@processLock, @rebirth, LOOPHOLE[rebirth, ConditionVariable].timeout];
This process is dead. Its PSB sits in the rebirth queue until it is recycled into a new process by Fork. Our current frame however, has one of two fates:
(a) If this process was detached, the frame will simply be freed by the next process that finishes ("deadFrame").
(b) if this process is being Joined, the parent process will have acquired a pointer to our frame. The JOIN code will Xfer to our frame and the code below will be executed BY THE PARENT PROCESS. The parent process therefore MUST BE RUNNING IN THE SAME MDS as the child process!
UNTIL PrincOpsUtils.ReEnter[@processLock, @rebirth] DO ENDLOOP;
sv.results.dest ← LOOPHOLE[frame.returnlink, ControlLink]; -- (frame.returnlink was set by Join[] to point to the context of JOIN.)
sv.results.source ← NullLink;
PrincOpsUtils.Exit[@processLock];
Reload returned results into stack, return to parent:
RETURN WITH sv.results
};
Join: ENTRY PROC [process: PsbIndex] RETURNS [loadResults: FrameHandle] = {
h: PsbHandle;
frame: DyingFrameHandle;
self: FrameHandle = PrincOpsUtils.MyLocalFrame[];
IF (h ← ValidProcess[process]) = NullPsbHandle THEN
RETURN WITH ERROR InvalidProcess[process];
Wait till process ready to be joined:
WHILE ProcState[h].state ~= frameReady DO WAIT frameReady ENDLOOP;
Guaranteed to be a dying frame by the time we get here.
frame ← LOOPHOLE[PDA[h].context.frame, DyingFrameHandle];
PDA[h].flags.processState.state ← frameTaken;
BROADCAST frameTaken; -- tell child process we've got his frame.
Wait till he has finished cleaning up:
WHILE frame.state ~= dead DO WAIT dead ENDLOOP;
At this point, we (the parent process) have acquired responsibility for the child's frame. IT MUST BE IN THE SAME MDS AS THE PARENT. We use the child frame's return link as a mailbox to pass to the child's frame the address of the JOINer's frame, which the child should return to.
frame.returnlink ← self.returnlink;
RETURN[frame] -- JOINer will next Xfer to "frame", which will reload the results into the stack and return them to the JOINer.
};
Time Slicer
defaultInterval: Process.Milliseconds = 100;
schedulerPriority: Process.Priority = Process.priorityFaultHandlers;
pSchedulingInterval: LONG POINTER TO CONDITION ← NIL;
Schedule: ENTRY PROCEDURE = {
OPEN PrincOps;
QueueToPsbHandle: PROCEDURE [queue: Queue] RETURNS [PsbHandle] = INLINE
{RETURN[PrincOpsUtils.PsbIndexToHandle[queue.tail]]};
The following is intended to be altered only by the debugger.
schedulingLevels: PACKED ARRAY Process.Priority OF BOOLEAN ←
[FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE];
schedulingInterval: CONDITION ← [timeout: MsecToTicks[defaultInterval]];
pSchedulingInterval ← @schedulingInterval; -- enable use of SetTimeSlice
Note: this procedure only touches resident structures and does not call any procedures. It therefore can never consume a state vector and consequently does not need a reserved one, even though it is executing at the reserved priority level.
Process.SetPriority[schedulerPriority];
DO
WAIT schedulingInterval;
FOR priority: Process.Priority DECREASING IN [FIRST[Process.Priority]..schedulerPriority) DO
IF schedulingLevels[priority] THEN {
psb: PsbHandle;
PrincOpsUtils.DisableInterrupts[];
Note that readyList can't be empty, since we are running!
psb ← PrincOpsUtils.PsbIndexToHandle[PDA[QueueToPsbHandle[PDA.ready]].link.next];
DO
SELECT PDA[psb].link.priority FROM
= priority => {PrincOpsUtils.Requeue[@PDA.ready, @PDA.ready, psb]; EXIT};
< priority => EXIT;
ENDCASE => IF psb = QueueToPsbHandle[PDA.ready] THEN EXIT;
psb ← PrincOpsUtils.PsbIndexToHandle[PDA[psb].link.next];
ENDLOOP;
PrincOpsUtils.EnableInterrupts[];
};
ENDLOOP;
ENDLOOP;
};
Initialization
Initialize: PROC = {
This procedure is implicitly parameterized by the module parameters.
AlignUp: PROC [unaligned, modulus: UNSPECIFIED] RETURNS [aligned: UNSPECIFIED] =
INLINE {RETURN[ ((unaligned + modulus-1) / modulus) * modulus]};
AlignDown: PROC [unaligned, modulus: UNSPECIFIED] RETURNS [aligned: UNSPECIFIED] =
INLINE {RETURN[unaligned - unaligned MOD modulus]};
rAlloc: PDABase RELATIVE POINTER TO UNSPECIFIED ← LOOPHOLE[pdaWords]; -- allocation pointer.
Initialize monitored variables and SD
Process.DisableTimeout[@dead];
Process.DisableTimeout[@frameReady];
Process.DisableTimeout[@frameTaken];
Process.DisableTimeout[@rebirth];
SD[sProcessTrap] ← ProcessTrap;
SD[sFork] ← Fork;
SD[--sCedarFork-- 153B] ← Fork; -- temporary until Compiler is fixed
SD[sJoin] ← Join;
Allocate StateVector pool:
{
alignmentStateVector: CARDINAL = 4; -- (a D0 requirement)
sizeStateVector: CARDINAL =
AlignUp[MAX[SIZE[StateVector], wordsPerSV], alignmentStateVector];
rState: StateVectorHandle ← AlignDown[rAlloc, alignmentStateVector];
FOR pri: Priority IN Priority DO
PDA.state[pri] ← NullStateVectorHandle;
FOR k: CARDINAL IN [0..svCounts[pri]) DO
IF LOOPHOLE[rState, CARDINAL] < sizeStateVector THEN ERROR;
rState ← rState - sizeStateVector;
PDA[rState].stk[0] ← PDA.state[pri]; -- chain onto list.
PDA.state[pri] ← rState;
ENDLOOP;
ENDLOOP;
rAlloc ← rState;
};
{
Find number of {PSB, timeout words} that will fit in space remaining, considering TimeoutVector alignment and unused TimeoutVector positions.
sizePSBTimeout: CARDINAL = SIZE[ProcessStateBlock] + SIZE[Ticks];
alignmentTimeoutVector: CARDINAL = 16; -- (PrincOps requirement)
rStartPsb: PDABase RELATIVE POINTER TO UNSPECIFIED =
LOOPHOLE[PrincOpsUtils.PsbIndexToHandle[StartPsb]];
totalPsbs: CARDINAL;
PDA.count ← 0;
FOR nUseful: CARDINAL DECREASING IN [0..(rAlloc - rStartPsb)/sizePSBTimeout] DO
totalPsbs ← StartPsb + nUseful;
PDA.timeout ← AlignDown[rAlloc - totalPsbs, alignmentTimeoutVector];
IF (LOOPHOLE[PDA.timeout, CARDINAL] + StartPsb -- (first used word of timeout vector)
- LOOPHOLE[rStartPsb, CARDINAL]) / SIZE[ProcessStateBlock] >= nUseful THEN
{PDA.count ← nUseful; EXIT}; -- that many Psbs fit in available space.
REPEAT
FINISHED => ERROR;
ENDLOOP;
IF PDA.count <= 1 THEN ERROR;
};
Initialize TimeoutVector: (Note: TimeoutVector unused portions overlay Psbs)
FOR psb: PsbIndex IN [StartPsb..StartPsb+PDA.count) DO
PDA[PDA.timeout][psb] ← NoTimeout;
ENDLOOP;
Set up the executing context as a legitimate process (detached) in the first Psb:
PDA.block[StartPsb] ← ProcessStateBlock[
link: [failed: FALSE, priority: FIRST[Priority], next: StartPsb, vector: NULL],
flags: [
processState: [state: alive, detached: TRUE],
cleanup: PsbNull, waiting: FALSE, abort: FALSE],
context: NULL,
TEMP until microcode uses timeout vector:
mds: Inline.HighHalf[LONG[LOOPHOLE[1, POINTER]]] ];
mds: NoTimeout
];
Note: the following assumes that someone has previously set the return link of the topmost frame to NullFrame.
FOR root: FrameHandle ← PrincOpsUtils.MyLocalFrame[], root.returnlink.frame DO
IF root.returnlink.frame = NullFrame THEN
{root.returnlink ← LOOPHOLE[End, procedure ControlLink]; EXIT};
ENDLOOP;
PrincOpsUtils.WritePSB[PrincOpsUtils.PsbIndexToHandle[StartPsb]]; -- tell the processor.
Initialize the ready list
PDA.ready ← Queue[tail: StartPsb];
Put rest of PSBs into free pool: (chained off "rebirth" condition)
{
firstFree: PsbIndex ← StartPsb+1;
lastFree: PsbIndex ← StartPsb+PDA.count-1;
LOOPHOLE[rebirth, ConditionVariable].condition.tail ← PsbNull;
FOR psb: PsbIndex IN [firstFree..lastFree] DO
PDA.block[psb].link.next ← IF psb=firstFree THEN lastFree ELSE psb-1;
PDA.block[psb].flags.processState.state ← dead;
TEMP until microcode uses timeout vector:
PDA.block[psb].mds ← NoTimeout;
REPEAT
FINISHED => LOOPHOLE[rebirth, ConditionVariable].condition.tail ← firstFree;
ENDLOOP;
};
Initialize FaultVector:
FOR fi: FaultIndex IN FaultIndex DO
PDA.fault[fi] ← [
queue: [tail: PsbNull], condition: [tail: PsbNull, abortable: FALSE, wakeup: FALSE]];
ENDLOOP;
Initialize naked-notify allocator:
busyLevels ← LOOPHOLE[reservedNakedNotifyMask];
PrincOpsUtils.WriteWDC[0]; -- start interrupts.
Start the time slicer
Detach[FORK Schedule[]];
};
Initialize[];
END.