DIRECTORY Basics USING [ BITSHIFT ], BasicTime USING [ MicrosecondsToPulses, PulsesToMicroseconds ], IntervalTimer USING [ Microseconds, Now, NowInPulses, Pulses ], IntervalTimerFace USING [ exists, SetExpirationTime, Wait ], Loader USING [ MakeProcedureResident, MakeGlobalFrameResident ], 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 –IntervalTimerImpl.mesa Last Edited by: Swinehart, March 4, 1983 10:15 am Last Edited by: L. Stewart, December 27, 1983 3:26 pm Compile this module /-c PriorityQueue USING [ Create, Empty, Insert, Ref, Remove, SortPred, Top ], (This implementation borrows the insertion/removal algorithm from the PQ package) RTOS USING [ UnregisterCedarProcess ], Operations for debugging Assert queue cannot be empty here, since Remove[] holds the same monitor. Note: WAIT cannot be aborted. Process will not proceed until the timeout occurs! RTOS.UnregisterCedarProcess[PrincOpsUtils.PsbHandleToIndex[PrincOpsUtils.ReadPSB[]]]; Priority Queue implementation. Unsafe if Wait procedure can be aborted or otherwise terminated while a wait is in progress!!! Is that OK? Call only when it is known that PQEmpty[] is FALSE Item is better than q[dad], so shuffle q[dad] down Call only when it is known that PQEmpty[] is FALSE Êp˜J™J™1J™5J™J™J™šÏk ˜ Jšœœœ˜Jšœ œ0˜?Jšœœ,˜?Jšœœ%˜J™2J˜2J˜Jšœ œ œ˜(—Jšœ ž˜:Jšœž˜1J˜J˜—J™2š Ÿœœœœœ˜*Jšœ%˜%Jšœœ˜Jšœ˜Jšœ œœž?œ˜XJ˜ Jšœœ˜J˜*Jšœ œœ˜Jšœœ ˜,šœ˜Jšœ˜šœ ˜JšœœBœœ˜i—Jš œœ+œœœ˜IJ˜2J˜ Jšœ˜—J˜J˜J˜—Jšœ˜J˜—J˜+—…— ¦