<> <> <> <<>> <> <<>> DIRECTORY Basics USING [ BITSHIFT ], BasicTime USING [ MicrosecondsToPulses, PulsesToMicroseconds ], IntervalTimer USING [ Microseconds, Now, NowInPulses, Pulses ], IntervalTimerFace USING [ exists, SetExpirationTime, Wait ], Loader USING [ MakeProcedureResident, MakeGlobalFrameResident ], <> <<(This implementation borrows the insertion/removal algorithm from the PQ package)>> PrincOpsUtils USING [ ReadPSB ], Process USING [ Detach, Priority, priorityClient3, SetPriority ], <> VM USING [ AddressForPageNumber, Allocate, Interval, Pin, wordsPerPage ] ; IntervalTimerImpl: CEDAR MONITOR IMPORTS Basics, BasicTime, IntervalTimer, IntervalTimerFace, Loader, PrincOpsUtils, Process, -- RTOS, -- VM EXPORTS IntervalTimer = { TooManyWaiters: PUBLIC ERROR = CODE; IntervalItem: TYPE = POINTER TO IntervalRec; IntervalRec: TYPE = RECORD [ time: IntervalTimer.Pulses, wakeup: CONDITION, timedOut: BOOLEAN ]; QIndex: TYPE = NAT; maxQueueLength: QIndex = VM.wordsPerPage - 5; -- max # processes is 1024 these days PSeq: TYPE = LONG POINTER TO PSequ; PSequ: TYPE = RECORD [ queueLength: QIndex, elements: ARRAY [0..maxQueueLength) OF IntervalItem ]; spaceHandle: VM.Interval; intervalQ: PSeq _ NIL; timerIdle: CONDITION; <> <<>> SoftNow: PROC RETURNS [now: IntervalTimer.Microseconds] = { RETURN[IntervalTimer.Now[]]; }; SoftNowInPulses: PROC RETURNS [now: IntervalTimer.Pulses] = { RETURN[IntervalTimer.NowInPulses[]]; }; WaitForExpirationTimeInPulses: PUBLIC ENTRY PROCEDURE[time: IntervalTimer.Pulses] = TRUSTED { item: IntervalRec; IF ~IntervalTimerFace.exists THEN RETURN; item.time _ time; item.timedOut_FALSE; IF ~PQInsert[@item] THEN ERROR TooManyWaiters; <> IntervalTimerFace.SetExpirationTime[PQTop[].time]; NOTIFY timerIdle; <> UNTIL item.timedOut DO WAIT item.wakeup; ENDLOOP }; WaitForExpirationTime: PUBLIC PROCEDURE[time: IntervalTimer.Microseconds] = TRUSTED { nowInPulses: IntervalTimer.Pulses; timeToWait: IntervalTimer.Microseconds; IF ~IntervalTimerFace.exists THEN RETURN; nowInPulses _ IntervalTimer.NowInPulses[]; timeToWait _ time - BasicTime.PulsesToMicroseconds[nowInPulses]; IF LOOPHOLE[timeToWait, INT] <= 0 THEN RETURN; -- in the past already WaitForExpirationTimeInPulses[nowInPulses + BasicTime.MicrosecondsToPulses[timeToWait]]; }; WaitForExpirationInterval: PUBLIC PROCEDURE[microseconds: INT] = TRUSTED { WaitForExpirationTimeInPulses[IntervalTimer.NowInPulses[] + BasicTime.MicrosecondsToPulses[microseconds]]; }; WaitForExpirationIntervalInPulses: PUBLIC PROCEDURE[pulses: INT] = TRUSTED { WaitForExpirationTimeInPulses[IntervalTimer.NowInPulses[] + pulses]; }; IntervalTimerMultiplexor: PROC = TRUSTED { Notifier: ENTRY PROC = TRUSTED INLINE { PQTop[].timedOut _ TRUE; NOTIFY PQTop[].wakeup; PQRemove[]; }; WaitForWork: ENTRY PROC = TRUSTED INLINE { WHILE PQEmpty[] DO WAIT timerIdle; ENDLOOP; IntervalTimerFace.SetExpirationTime[PQTop[].time]; }; Loader.MakeProcedureResident[IntervalTimerMultiplexor]; Loader.MakeGlobalFrameResident[IntervalTimerMultiplexor]; <> Process.SetPriority[Process.priorityClient3]; DO WaitForWork[]; IntervalTimerFace.Wait[]; Notifier[]; ENDLOOP; }; InitializeIntervalTimer: PROC = TRUSTED { spaceHandle _ VM.Allocate[count: 1]; VM.Pin[spaceHandle]; intervalQ _ VM.AddressForPageNumber[spaceHandle.page]; intervalQ.queueLength _ 0; Process.Detach[FORK IntervalTimerMultiplexor[]]; }; <> <<>> <> PQTop: PROC RETURNS [IntervalItem] = TRUSTED INLINE { RETURN[intervalQ.elements[1]]; }; PQEmpty: PROC RETURNS [BOOL] = TRUSTED INLINE { RETURN[intervalQ.queueLength = 0]; }; PQInsert: INTERNAL PROC [item: IntervalItem] RETURNS [ok: BOOL _ TRUE] = TRUSTED INLINE { size, son: QIndex _ intervalQ.queueLength + 1; dad: QIndex _ Basics.BITSHIFT[son, -1]; IF size > maxQueueLength THEN RETURN[FALSE]; WHILE dad > 0 AND LOOPHOLE[intervalQ.elements[dad].time - item.time, INT] > 0 DO <> intervalQ.elements[son] _ intervalQ.elements[dad]; son_dad; dad _ Basics.BITSHIFT[son, -1]; ENDLOOP; intervalQ.elements[son] _ item; -- insert the new item and intervalQ.queueLength _ size; -- update the size. }; <> PQRemove: INTERNAL PROC = TRUSTED INLINE { size: QIndex _ intervalQ.queueLength; item: IntervalItem _ NIL; dad, maxDad: QIndex; IF size = 0 THEN ERROR; -- Paranoid: assert that PQRemove is only called when non-empty item _ intervalQ.elements[size]; intervalQ.elements[size] _ NIL; intervalQ.queueLength _ (size _ size - 1); IF size = 0 THEN RETURN; dad _ 1; maxDad _ Basics.BITSHIFT[size, -1]; WHILE dad <= maxDad DO son: QIndex _ dad + dad; IF son < size THEN IF LOOPHOLE[intervalQ.elements[son].time - intervalQ.elements[son + 1].time, INT] > 0 THEN son _ son + 1; IF LOOPHOLE[intervalQ.elements[son].time - item.time, INT] > 0 THEN EXIT; intervalQ.elements[dad] _ intervalQ.elements[son]; dad _ son; ENDLOOP; intervalQ.elements[dad] _ item; }; InitializeIntervalTimer[]; }. December 27, 1983 3:26 pm, Stewart, Cedar 5