FastForkImpl.mesa
Copyright Ó 1989, 1990, 1991, 1992, 1993 by Xerox Corporation. All rights reserved.
Created by Christian Jacobi, February 27, 1989 12:18:47 pm PST
Christian Jacobi, April 1, 1993 12:24 pm PST
DIRECTORY FastFork, Process;
FastForkImpl:
CEDAR
MONITOR
IMPORTS Process
EXPORTS FastFork =
Implementation Idea:
There is a small ready-pool
Every process in the ready-pool can jump immediately when a job is ready.
There is also small number of processes hanging around on leave sleeping.
The processes hanging around on leave (sleep) may disappear completely, or may go back to the ready-pool; Processes on leave time out or be notified and decide then where to go.
When a process is needed the ready-pool is checked; either a process is removed from the ready-pool or a new one forked. When the ready-pool is nearly empty a process from leave might fill a vacancy to reduce the probability of a fork.
When a job is done, the process might go either in the ready-pool [if there is space], or hanging around on leave.
longTime: Process.Ticks = Process.SecondsToTicks[120];
ForkProcType: TYPE = PROC [REF];
readyMax: INT = 7; --size of ready pool
readyCnt: INT ¬ 0;
readyPool:
ARRAY [0..readyMax]
OF ForkerRef;
--invariants:
--Every entry on the readyPool has a process waiting for its reCheck.
--While entry is on the readyPool its proc is NIL.
--order does not matter; lifo is advantagoues
sleepingMax: INT = 8; --limit on how many processes may enter sleeping mode
wakeSleeperCnt: INT = 3; --wake a sleeper if less processes are ready [small for hysteresis]
sleeping: CONDITION; --time-out is essential
sleepingCount: INT ¬ 0;
ForkerRef: TYPE = REF ForkerRec;
ForkerRec:
TYPE =
RECORD [
proc: ForkProcType, --#NIL means job to do
data: REF,
priority: CARD32,
reCheck: CONDITION --time-out just in case notification goes lost
];
Dequeue:
INTERNAL
PROC []
RETURNS [fr: ForkerRef] =
INLINE {
readyCnt ¬ readyCnt-1; fr ¬ readyPool[readyCnt];
};
Enqueue:
INTERNAL
PROC [fr: ForkerRef] =
INLINE {
readyPool[readyCnt] ¬ fr; readyCnt ¬ readyCnt+1;
};
Fork:
PUBLIC
PROC [proc: ForkProcType, data:
REF, priority:
CARD32] = {
EntryFork:
ENTRY
PROC [proc: ForkProcType, data:
REF]
RETURNS [done:
BOOL] = {
<<doesn't raise errors.. ENABLE UNWIND => NULL;>>
IF done ← readyCnt>0
THEN {
fr: ForkerRef ~ Dequeue[]; --invariant: process is waiting on fr.reCheck
fr.data ← data; fr.proc ← proc; fr.priority ← priority;
NOTIFY fr.reCheck;
};
IF readyCnt<wakeSleeperCnt AND sleepingCount>0 THEN NOTIFY sleeping; --don't BROADCAST!
};
copy: ForkProcType ← proc; --might raise SafeStorage.UnsafeProcAssignment
IF ~EntryFork[copy, data].done
THEN {
Process.Yield[]; --hope this might help a running process to finish so we can avoid the fork
IF ~EntryFork[copy, data].done
THEN {
fr: ForkerRef ~ NEW[ForkerRec];
fr.data ← data; fr.proc ← copy; fr.priority ← priority;
TRUSTED {
Process.InitializeCondition[@fr.reCheck, longTime];
Process.Detach[FORK ForkedProcess[fr]]
};
};
};
};
ForkedProcess:
PROC [fr: ForkerRef] = {
DO
proc: ForkProcType ~ fr.proc;
data: REF ~ fr.data;
IF proc = NIL THEN RETURN;
IF Process.GetPriority[]#fr.priority
THEN {
Process.SetPriority[fr.priority]; --Todays version of Process.SetPriority does a yield which I want to avoid here
};
proc[data];
<<Process.SetPriority[Process.priorityRealTime];>> -- put it back when it wouldn't yield anymore. Actually I don't mind if this loop gets one yield. I'm afraid of YieldSecondBest and of two yields. ChJ December 22, 1992 12:49:47 pm PST
WaitForNextJob[fr];
ENDLOOP;
};
WaitForNextJob:
ENTRY
PROC [fr: ForkerRef] = {
<<doesn't raise errors.. ENABLE UNWIND => NULL;>>
fr.proc ¬ NIL; fr.data ¬ NIL;
IF readyCnt>=readyMax
THEN {
--The ready-pool is full
--Sleep for some time and check again
IF sleepingCount>=sleepingMax THEN RETURN; --die
sleepingCount ¬ sleepingCount+1;
WAIT sleeping;
sleepingCount ¬ sleepingCount-1;
IF readyCnt>=readyMax THEN RETURN; --die
};
--Enter ready queue
Enqueue[fr];
WHILE fr.proc=NIL DO WAIT fr.reCheck ENDLOOP;
};
TRUSTED {
Process.InitializeCondition[@sleeping, Process.MsecToTicks[1000]];
};
END.