chp-2.0.0: An implementation of concurrency ideas from Communicating Sequential Processes

Control.Concurrent.CHP.Clocks

Description

Clocks, based on an idea by Adam Sampson.

A clock is similar to a timer, but it is entirely concerned with logical time, rather than any relation to actual time, and all clocks are entirely independent. A clock has the concept of enrollment, so at any time there are N processes enrolled on the clock. Each process may wait on the clock for a specific time. Once all N enrolled processes are waiting for a time (giving a list of times Ts), the clock moves forward to the next time in Ts.

Let's consider an example. Three processes are enrolled on an Int clock. The current time of the clock is 0. One process asks to wait for time 3, and blocks. A second process asks to wait for time 5, and blocks. Finally, the third process waits for time 3. At this point, the first and third process are free to proceed, and the new clock time is 3. The second process (waiting for time 5) stays waiting until the two processes have returned and waited again.

There is also the option to wait for the next available time. If our two enrolled processes wait again, with the first waiting for time 7, and the third waiting for the next available time, the second and third will wake up, with the new time on the clock being 5 (the first stays waiting for time 7).

There is also the ability for time to wrap around. If all processes are waiting for a time that is before the current time (using less-than from the Ord instance) or just the next available time, the earliest time of those will be taken. So if the current time is 26, and the processes are waiting for 11, 21 and next available time, the first and third will wake up and the new time will be 11. This is particularly useful for using your own algebraic type (data Phase = PhaseA | PhaseB | PhaseC deriving (Eq, Ord)). If you want to, you can use Integer and never use the time wrapping ability (see waitUnbounded).

What the units of a clock mean is entirely up to you. The only requirement is an Ord instance for comparing two times, to use the above rules. The item in a clock may be an Int, a Double, an Integer, or even types like Bool or Either, your own types or newtypes, or things like lists!

The following rules apply to clocks:

  • If there are no processes enrolled, the time never changes.
  • Time never advances (and processes are never woken up) until all processes enrolled on the clock have waited for a time (either the next available, or a specific time).
  • If all processes enrolled wait for the next available time, they will not wake up (until another process enrolls and asks for a specific time). To make sure that time advances, use the Control.Concurrent.CHP.Common.advanceTime process.
  • The clock always advances to the earliest (minimum) specific offer that is stricly after the current time, unless:
  • If all processes that are waiting for specific times, ask for times that are before the current time, the earliest (minimum) of these is taken, and thus time effectively moves backwards (wraps around). In this case, all processes waiting for the next time will also be woken up.
  • As a consequence of all of the above, if you wait and return being told the current time, that time cannot change until you next wait, or if you resign from the clock (temporarily or permanently).
  • Note that waiting for clocks cannot be used as part of a choice (Control.Concurrent.CHP.Alt.alt and Control.Concurrent.CHP.Alt.every). The semantics of allowing this are unclear. If a clock waits for time 5, but later backs out, should it be possible for two other processes to advance the time to 3 in the mean-time? Due to this, clocks cannot be used in a choice. If you want to have a choice involving a time change, have a process that waits for the next available time, then sends it down a channel to the process making the choice.

Clocks are similar to phased barriers (indeed, both have an instance of Waitable). The fundamental differences are:

  • A barrier can only move one phase at a time. If you use barriers to skip past several phases at once, this will be much less efficient than using a clock. This is also true if not every process enrolled on a barrier wants to take action every phase -- a clock allows those processes to remain sleeping, rather than wake up only to sleep again,
  • Barriers support choice, but clocks do not. This means clocks are both less powerful, but also faster than barriers.
  • Barriers choose their next phase using their incrementing function. Clocks are more flexible, in that their next phase is chosen solely by looking at the requests from the various processes. Hence why Double is a suitable type for a Clock time, but not for a PhasedBarrier phase.

This whole module was first added in version 1.2.0.

Synopsis

Documentation

data Ord time => Clock time Source

A clock that measures time using the given type. Only Ord is required on the type, so it can be all sorts. Obvious possibilities are numeric types such as Int and Double -- if you want monotonically-increasing time, see waitUnbounded. Other possibilities include your own algebraic types, if you want a clock that cycles around a given set of phases. If every process enrolled on the clock always just waits for the next time, you may want to consider using a PhasedBarrier. If you want a clock that works in reverse or anything else strange, you can always wrap your type in a newtype to give a custom Ord instance.

See the documentation at the beginning of this module for more information on clocks.

Instances

Waitable Clock 
Ord time => Enrollable Clock time 
Ord time => Poisonable (Enrolled Clock time) 

class Waitable c whereSource

A type-class for things that you can on for a specific time/phase. The instance for PhasedBarrier repeatedly syncs until the specific phase is reached. Clock waits until the time is reached.

Methods

wait :: Ord t => Enrolled c t -> Maybe t -> CHP tSource

Given an enrolled item, waits for the specific time/phase (if you pass a Just value) or the next available time/phase. (if you pass Nothing). The value returned is the new current time. Note that waiting for the current time/phase or a past time/phase on a clock/barrier will not return immediately -- see the rules at the top of this module, and see waitUnbounded.

getCurrentTime :: Ord t => Enrolled c t -> CHP tSource

Gets the current time/phase.

waitUnbounded :: (Waitable c, Ord t) => Enrolled c t -> Maybe t -> CHP tSource

Normally, when waiting on a clock, if you wait for a time equal to (or earlier than) the current time, you will block until the clock wraps around. Sometimes, however, you may want your clock to never wrap around (and use Integer as the inner type, usually), and want to make sure that if a process waits for the current time or earlier, it returns instantly. That is what this function achieves.

Calling this function with Nothing has indentical behaviour to calling wait with Nothing. If you wait for the current time or earlier, all of the other processes waiting on the clock will remain blocked. Processes who have asked to wait for the current time will remain blocked -- it is generally not useful to mix waitUnbounded and wait on the same clock.

newClock :: (Ord time, Show time) => time -> CHP (Clock time)Source

Creates a clock that starts at the given time. The Show instance is needed to display times in traces.

newClockWithLabel :: (Ord time, Show time) => time -> String -> CHP (Clock time)Source

Creates a clock that starts at the given time, and gives it the given label in traces. The Show instance is needed to display times in traces.