wiki:Concurrency/DraftReportText

Version 1 (modified by simonmar@…, 7 years ago) (diff)

First draft of text for the report, many omissions

Draft Chapter: Concurrency

Haskell supports concurrency, in the sense that a program can contain multiple threads of execution interacting non-deterministically. Precisely what we mean by this, and what guarantees the programmer is given, are described in the following chapter. The material here is to be read concurrently with the description of the Control.Concurrent library, in Chapter ??.

Threads

New threads are created by the forkIO operation from the module Control.Concurrent:

   forkIO :: IO a -> IO ThreadId

The forkIO operation creates a new thread to execute the supplied IO action, and returns immediately to the caller with a value of type ThreadId that can be used to identify the new thread (see 'The ThreadId type', below).

Operations performed by multiple threads may be interleaved arbitrarily by the implementation, with the following restriction:

  • A thread that is not blocked on a resource will not be indefinitely delayed by the implementation.

This is called the fairness guarantee. An implementation technique that is often used to provide this fairness guarnatee is pre-emption: running threads are periodically pre-empted in software in order to let other threads proceed. There are other implementation techniques that also work; for example, hardware concurrency. (ToDo?: move this text to a footnote or separate section?)

The ThreadId type

The ThreadId type is abstract, and supports Eq, Ord, and Show, with the following meanings:

  • Eq: two ThreadId values compare equal if and only if they were returned by the same forkIO call.
  • Ord: the implementation provides an arbitrary total ordering on ThreadIds. For example, the ordering may be used to contruct a

mapping with ThreadId as the domain. There are no guarantees other than that the ordering is total; the particular ordering might be different from run to run of the program.

  • Show: the results are implementation-defined, this is mainly for debugging.

Communication

ToDo?: MVars or STM.

MVars have important properties that can't be simulated in STM: fairness and single-wakeup. (only the first is important from a semantics perspective, the second has significant practical importance though).

Concurrency and the FFI

Foreign calls (see Chapter ??) can be made as usual by concurrent threads. The fairness guarantee requires that a foreign call must not hold up the other threads in the system; this implies that the Haskell implementation must be able to make use of the operating system's native threads ("OS threads" from now on) in order to run a foreign call concurrently with other Haskell threads, and concurrently with other foreign calls.

However, it is not required that the Haskell implementation maintain a one-to-one mapping between native operating system threads and Haskell threads [cite: Conc/FFI paper]: indeed there are more efficient imlementations that multiplex many Haskell threads on to a few operating system threads. On such systems, it can be relatively expensive to make a foreign call that must be able to run concurrently with the other threads, and for this reason we allow a small exception to the fairness guarantee:

  • A foreign import declaration annotated as nonconcurrent (ToDo?: pick syntax) is not subject to the fairness guarantee. It may prevent progress of other threads until it returns.

In some implementations, nonconcurrent foreign calls can be implemented much more efficiently.

Foreign calls may also invoke further Haskell functions by calling foreign exported functions. Allowing for this possibilty may also be expensive: a function exposed by foreign export may be invoked at any time by an arbitrary OS thread, and the implementation must be ready to receive the call. However, if the implementation knows that a given foreign call cannot result in a callback (a call to a function exposed by foreign export), then it can sometimes use a more efficient calling sequence for the foreign call. For this reason, we have another annotation:

  • A foreign import declaration annotated as nonreentrant (ToDo?: pick syntax) can be assumed by the implementation to refer to a foreign function that will never call a Haskell function, or any function in the C API described in Chapter ??.

Memory model

ToDo?.

  • MVar operations can never be observed out-of-order
  • Maybe: IORef operations also strongly ordered
  • STM, if we have it: also strong ordering between transactions

Bound threads (optional)

ToDo?.

Bound threads allow a Haskell program more control over the mapping between Haskell threads and OS threads. Such control is required for interacting with foreign code that is either single-threaded or makes use of thread-local state in the native OS threading model.