<> <> <> <> DIRECTORY FastFork, Process; FastForkImpl: CEDAR MONITOR IMPORTS Process EXPORTS FastFork = BEGIN <> <> <> <> <> <> <> 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] = { < 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 readyCnt0 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]; <<<> -- 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] = { < 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.