Test.DejaFu.Deterministic.Schedule

Deterministic scheduling for concurrent computations.

Documentation

type Scheduler s = s -> Maybe (ThreadId, ThreadAction) -> NonEmpty (ThreadId, NonEmpty Lookahead) -> (ThreadId, s)

A Scheduler maintains some internal state, s, takes the ThreadId of the last thread scheduled, or Nothing if this is the first decision, and the list of runnable threads along with what each will do in the next steps (as far as can be determined). It produces a ThreadId to schedule, and a new state.

Note: In order to prevent computation from hanging, the runtime will assume that a deadlock situation has arisen if the scheduler attempts to (a) schedule a blocked thread, or (b) schedule a nonexistent thread. In either of those cases, the computation will be halted.

type ThreadId = Int

Every live thread has a unique identitifer.

data NonEmpty a

The type of non-empty lists.

Constructors

a :| [a]

Instances

Functor NonEmpty

Foldable NonEmpty

Traversable NonEmpty

Eq a => Eq (NonEmpty a)

Ord a => Ord (NonEmpty a)

Read a => Read (NonEmpty a)

Show a => Show (NonEmpty a)

NFData a => NFData (NonEmpty a)

Pre-emptive

randomSched :: RandomGen g => Scheduler g

A simple random scheduler which, at every step, picks a random thread to run.

roundRobinSched :: Scheduler ()

A round-robin scheduler which, at every step, schedules the thread with the next ThreadId.

Non pre-emptive

randomSchedNP :: RandomGen g => Scheduler g

A random scheduler which doesn't pre-empt the running thread. That is, if the last thread scheduled is still runnable, run that, otherwise schedule randomly.

roundRobinSchedNP :: Scheduler ()

A round-robin scheduler which doesn't pre-empt the running thread.

Utilities

makeNP :: Scheduler s -> Scheduler s

Turn a potentially pre-emptive scheduler into a non-preemptive one.

toList :: NonEmpty a -> [a]

Convert a NonEmpty to a regular non-empty list.