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; 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]; WaitForNextJob[fr]; ENDLOOP; }; WaitForNextJob: ENTRY PROC [fr: ForkerRef] = { < NULL;>> fr.proc ¬ NIL; fr.data ¬ NIL; IF readyCnt>=readyMax THEN { IF sleepingCount>=sleepingMax THEN RETURN; --die sleepingCount ¬ sleepingCount+1; WAIT sleeping; sleepingCount ¬ sleepingCount-1; IF readyCnt>=readyMax THEN RETURN; --die }; Enqueue[fr]; WHILE fr.proc=NIL DO WAIT fr.reCheck ENDLOOP; }; TRUSTED { Process.InitializeCondition[@sleeping, Process.MsecToTicks[1000]]; }; END. ͺ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 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. --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 <> -- 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 --The ready-pool is full --Sleep for some time and check again --Enter ready queue Κ:–(cedarcode) style•NewlineDelimiter ˜codešœ™Kšœ ΟeœI™TKšœ>™>K™,—K˜šΟk œ˜K˜—šΟn œžœž˜Kšžœ˜Kšžœ ˜—šž˜K˜—šœ™šœ™K™I—™IK™³—Kšœμ™μKšœr™r—K˜Kšœ6˜6K˜Kšœžœžœžœ˜ K˜Kšœ žœΟc˜'Kšœ žœ˜šœ žœžœ ˜,š ™Kš E™EKš 2™2—K™-—K˜Kšœ žœ 5˜LKšœžœ D˜]Kšœ ž œ ˜-Kšœžœ˜K˜Kšœ žœžœ ˜ šœ žœžœ˜Kšœ ˜+Kšœžœ˜ Kšœ žœ˜Kšœ ž œ /˜CK˜—K˜š Ÿœžœžœžœžœ˜