DIRECTORY Inline USING [ BITSHIFT ], IntervalTimer USING [ Microseconds, Now, NowInPulses, Pulses ], IntervalTimerFace USING [ exists, SetExpirationTime, Wait ], Process USING [ Detach, Priority, priorityInterrupt, SetPriority ], ProcessOperations USING [ HandleToIndex, ReadPSB ], RTOS USING [ UnregisterCedarProcess ], Runtime USING [ GlobalFrame ], Space USING [ Create, Handle, LongPointer, Map, virtualMemory, wordsPerPage ], SpecialSpace USING [ MakeResident, MakeCodeResident, MakeGlobalFrameResident ], System USING [ MicrosecondsToPulses, PulsesToMicroseconds ] ; IntervalTimerImpl: CEDAR MONITOR IMPORTS Inline, IntervalTimer, IntervalTimerFace, Process, ProcessOperations, RTOS, Runtime, Space, SpecialSpace, System 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 = Space.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: Space.Handle; 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 - System.PulsesToMicroseconds[nowInPulses]; IF LOOPHOLE[timeToWait, INT] <= 0 THEN RETURN; -- in the past already WaitForExpirationTimeInPulses[[nowInPulses + System.MicrosecondsToPulses[timeToWait]]]; }; WaitForExpirationInterval: PUBLIC PROCEDURE[microseconds: INT] = TRUSTED { WaitForExpirationTimeInPulses[[IntervalTimer.NowInPulses[] + System.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]; }; SpecialSpace.MakeCodeResident[Runtime.GlobalFrame[IntervalTimerMultiplexor]]; SpecialSpace.MakeGlobalFrameResident[Runtime.GlobalFrame[IntervalTimerMultiplexor]]; RTOS.UnregisterCedarProcess[ProcessOperations.HandleToIndex[ProcessOperations.ReadPSB[]]]; Process.SetPriority[Process.priorityInterrupt]; DO WaitForWork[]; IntervalTimerFace.Wait[]; Notifier[]; ENDLOOP; }; InitializeIntervalTimer: PROC = TRUSTED { spaceHandle _ Space.Create[size: 1, parent: Space.virtualMemory]; Space.Map[spaceHandle]; SpecialSpace.MakeResident[spaceHandle]; intervalQ _ Space.LongPointer[spaceHandle]; 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 _ Inline.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 _ Inline.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 _ Inline.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[]; }. IntervalTimerImpl.mesa Last Edited by: Swinehart, March 4, 1983 10:15 am Last Edited by: L. Stewart, March 31, 1983 2:08 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) 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! 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 ÊU˜J™J™1J™2J™J™J™šÏk ˜ Jšœœœ˜Jšœœ,˜?Jšœœ%˜<šœœ7™JJ™Q—Jšœœ6˜CJšœœ˜3Jšœœ˜&Jšœœ˜JšœœC˜NJšœ œ=˜OJšœœ/˜;J˜J˜—šœœ˜ JšœGœ&˜xJšœ˜J˜Jšœœœœ˜$J˜Jšœœœœ ˜,šœ œœ˜J˜Jšœ œ˜Jšœ ˜Jšœ˜—J˜Jšœœœ˜Jšœ1Ïc%˜VJ˜Jš œœœœœ˜#šœœœ˜Jšœ˜Jšœ œœ ˜3Jšœ˜J˜—J˜Jšœœ˜Jšœ œ˜J˜J™J™šÏnœœœ&˜;Jšœ˜J˜—J˜šŸœœœ ˜=Jšœ˜$J˜J˜J˜—š Ÿœœœ œœ˜]J˜Jšœœœ˜)J˜Jšœœ˜Jšœœœ˜.JšœI™IJšœ2˜2Jšœ ˜JšœQ™QJšœœœ˜0Jšœ˜—J˜šŸœœ œ%œ˜UJšœ"˜"Jšœ'˜'Jšœœœ˜)Jšœ*˜*Jšœ=˜=Jš œœ œœœž˜EJšœW˜WJšœ˜—J˜š Ÿœœ œœœ˜JJšœi˜iJšœ˜J˜—š Ÿ!œœ œ œœ˜LJšœF˜FJšœ˜J˜—šŸœœœ˜*š Ÿœœœœœ˜'Jšœœ˜Jšœ˜Jšœ ˜ Jšœ˜—š Ÿ œœœœœ˜*šœ ˜Jšœ ˜Jšœ˜—Jšœ2˜2Jšœ˜—JšœM˜MJšœT˜TJšœV˜ZJ˜/š˜Jšœ˜Jšœ˜Jšœ ˜ Jšœ˜—Jšœ˜—J˜šŸœœœ˜)J˜BJ˜J˜'Jšœ+˜+J˜Jšœœ˜0Jšœ˜J˜—J™‹J™J™2š Ÿœœœœœ˜5Jšœ˜Jšœ˜—J˜š Ÿœœœœœœ˜/Jšœ˜"Jšœ˜—J˜šŸœœœœœœœœ˜YJšœ.˜.Jšœœ ˜'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˜——…—¸#