|
|
|
# Concurrency
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
## References
|
|
|
|
|
|
|
|
|
| ... | ... | @@ -26,7 +23,6 @@ Papers and other docs: |
|
|
|
- [ Concurrent Haskell](http://www.haskell.org/ghc/docs/papers/concurrent-haskell.ps.gz) (the original paper, including a semantics)
|
|
|
|
- [ Extending the Haskell FFI with Concurrency](http://www.haskell.org/~simonmar/papers/conc-ffi.pdf) (a specification of the interaction between concurrency and the FFI, with a semantics)
|
|
|
|
- [ A Draft report addendum](http://www.haskell.org/ghc/docs/papers/threads.ps.gz) (a shorter version of the above paper).
|
|
|
|
- [ A Poor Man's Concurrency Monad](http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps) (Hugs' implementation of Concurrency)
|
|
|
|
- [ Software Transactional Memory](http://research.microsoft.com/~simonpj/papers/stm/)
|
|
|
|
|
|
|
|
## Pros
|
| ... | ... | @@ -42,159 +38,146 @@ Papers and other docs: |
|
|
|
- Providing a 'select' and non-blocking IO would be enough to allow people to implement something like it themselves in haskell and are provided by most systems as primitives.
|
|
|
|
- Things like the 'poor man's concurrency monad' can achieve some of the benefits
|
|
|
|
|
|
|
|
---
|
|
|
|
|
|
|
|
|
|
|
|
# Proposals
|
|
|
|
|
|
|
|
## Proposal
|
|
|
|
|
|
|
|
## Proposal 1
|
|
|
|
|
|
|
|
- Standardise on Concurrent Haskell without STM. It is our view that even in the presence of STM, `MVar`s offer
|
|
|
|
functionality that is distinct from STM and separately useful, so this leaves room for growth.
|
|
|
|
|
|
|
|
- The Haskell' standard does not include concurrency, but includes enough to allow portable thread-safe
|
|
|
|
libraries to be written. (see "thread safe", below).
|
|
|
|
|
|
|
|
- A separate addendum specifies concurrency according to the *fairness* requirements (see below).
|
|
|
|
|
|
|
|
|
|
|
|
## Proposal 2
|
|
|
|
|
|
|
|
- Use the semantics from [ Extending the Haskell FFI with Concurrency](http://www.haskell.org/~simonmar/papers/conc-ffi.pdf)
|
|
|
|
|
|
|
|
- The Haskell' standard includes concurrency with the *fairness* requirements.
|
|
|
|
|
|
|
|
- A separate addendum specifies how implementations that do not provide concurrency behave: at the least,
|
|
|
|
it should include enough to allow portable thread-safe libraries.
|
|
|
|
Questions:
|
|
|
|
|
|
|
|
## Proposal 3
|
|
|
|
|
|
|
|
- Decide how much pre-emption is acceptable, and figure out how to specify this.
|
|
|
|
|
|
|
|
- The Haskell' standard includes concurrency with a weaker version of *fairness*, that is enough
|
|
|
|
to admit implementations with *cooperative scheduling*.
|
|
|
|
|
|
|
|
- A separate addendum specifies concurrency with the full *fairness* requirements.
|
|
|
|
|
|
|
|
## Open questions
|
|
|
|
|
|
|
|
- Should we specify what an implementation that doesn't provide concurrency should do? (e.g. provide an implementation
|
|
|
|
of MVars in terms of IORefs, so that concurrency-safe libraries can be written portably).
|
|
|
|
|
|
|
|
- Require bound thread support, or make it optional? (YHC has concurrency with non-blocking foreign calls, but doesn't
|
|
|
|
have bound threads as yet.)
|
|
|
|
|
|
|
|
- Do we require [ForeignBlocking](foreign-blocking)?
|
|
|
|
|
|
|
|
## Thread-safety
|
|
|
|
---
|
|
|
|
|
|
|
|
|
|
|
|
# Proposal
|
|
|
|
|
|
|
|
In order to write library code that is thread-safe when run in a multi-threaded environment, two things are needed:
|
|
|
|
|
|
|
|
## what is provided
|
|
|
|
|
|
|
|
1. a way to protect mutable state against race conditions
|
|
|
|
1. a way to declare that foreign calls are blocking
|
|
|
|
|
|
|
|
|
|
|
|
For (1), we have two choices:
|
|
|
|
At least the following interface will be provided
|
|
|
|
|
|
|
|
|
|
|
|
- Provide `MVar`s. A non-concurrent implementation might implement them in terms of `IORef`,
|
|
|
|
for example.
|
|
|
|
- Control.Concurrent.MVar - everything except addMVarFinalizer
|
|
|
|
- Control.Concurrent - ThreadId?,myThreadId,forkIO,yield,threadWaitRead\[1\],threadWaitWrite\[1\],threadDelay,threadSetPriority\[2\],threadGetPriority\[2\]
|
|
|
|
|
|
|
|
- Provide STM. Not entirely trivial to implement, even in a single-threaded implementation, because
|
|
|
|
exceptions have to abort a transaction. Ross Paterson provided an [ implementation](http://www.haskell.org//pipermail/haskell-prime/2006-March/001108.html).
|
|
|
|
|
|
|
|
the FFI must be able to handle 'concurrent nonrentrant' imports, but not
|
|
|
|
necessarily 'concurrent reentrant' ones.
|
|
|
|
|
|
|
|
For (2), one option is [ForeignBlocking](foreign-blocking).
|
|
|
|
|
|
|
|
## Progress Guarentee
|
|
|
|
|
|
|
|
---
|
|
|
|
|
|
|
|
- if any haskell thread is runnable then at least one thread will be running.
|
|
|
|
- foreign calls marked 'concurrent' will not interfere will the above rule.
|
|
|
|
|
|
|
|
# Terminology
|
|
|
|
## MVar Guarentees
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**Pre-emption** means that (1) threads have priority levels, and (2) that a
|
|
|
|
higher priority thread can steal the processor from a currently-running
|
|
|
|
lower priority thread, and (3) it can do so "immediately" it needs to,
|
|
|
|
without waiting for some "safe" synchronisation point.
|
|
|
|
By these criteria, none of the current Haskell implementations are
|
|
|
|
pre-emptive, because no API assigns priorities to threads. So let's try
|
|
|
|
to avoid using the term.
|
|
|
|
initial proposal is here:
|
|
|
|
|
|
|
|
|
|
|
|
>
|
|
|
|
>
|
|
|
|
> [ http://www.haskell.org//pipermail/haskell-prime/2006-March/001168.html](http://www.haskell.org//pipermail/haskell-prime/2006-March/001168.html)
|
|
|
|
>
|
|
|
|
>
|
|
|
|
|
|
|
|
**Fairness** can be defined by two main criteria:
|
|
|
|
## Misc library stuff
|
|
|
|
|
|
|
|
|
|
|
|
- No runnable process will be indefinitely delayed.
|
|
|
|
- No thread can be blocked indefinitely on an MVar unless another thread holds the MVar indefinitely.
|
|
|
|
|
|
|
|
yield is guarenteed to choose an alternate thread if another one exists and is
|
|
|
|
runnable.
|
|
|
|
|
|
|
|
**Cooperative scheduling** describes an implementation in which it is the programmer's responsibility to insert context switch points in the code. An implementation that only provides cooperative scheduling cannot satisfy the fairness properties given above. A programmer who has access to all the code *may* be able to insert enough context switch points to satisfy fairness, but this isn't always possible.
|
|
|
|
|
|
|
|
|
|
|
|
\[2\] priorities are advisory, but higher priority threads should be run in
|
|
|
|
preference to lower priority ones.
|
|
|
|
|
|
|
|
**Concurrent foreign call** means a foreign call that should run concurrently with other Haskell threads. It is a requirement of "fairness" (above) that a foreign call should not prevent other threads from making progress indefinitely. Note that we used to use the term **non-blocking foreign call** here, but that lead to confusion with "foreign calls that block", which are foreign calls that may wait indefinitely for some resource, such as reading data from a socket. "foreign calls that block" are the main reason for wanting support for concurrent foreign calls.
|
|
|
|
|
|
|
|
|
|
|
|
threadDelay guarentees the thread will wait as long as its argument at a
|
|
|
|
minimum. it may be blocked for longer.
|
|
|
|
|
|
|
|
**Scheduling.**
|
|
|
|
Most current implementations of
|
|
|
|
concurrency in Haskell use non-preemptive scheduling. That is, there are
|
|
|
|
explicit time points at which any one thread can *yield*, allowing other threads to run.
|
|
|
|
The only differences between implementations are in the granularity and positioning of the yield.
|
|
|
|
|
|
|
|
## notes
|
|
|
|
|
|
|
|
- For Hugs, yield is inserted at certain I/O actions.
|
|
|
|
- For ghc in non-SMP mode, yield is inserted after some count of allocations.
|
|
|
|
- For yhc, yield is inserted after some count of bytecode instructions.
|
|
|
|
|
|
|
|
|
|
|
|
Arguably, Hugs has made the wrong choice from a fairness point of view. It would be possible to make Hugs yield more often, such as in IO-monad's bind operator, but even this wouldn't be quite enough for fairness, because a thread might hang indefinitely performing a non-IO computation. Yielding outside of the IO monad in Hugs doesn't seem possible without overhauling the concurrency implementation completely.
|
|
|
|
\[1\] may be moved to another module, routines working on Handles should be
|
|
|
|
added too.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The notable exception to the above is GHC in SMP mode, which can run multiple Haskell threads simultaneously in separate OS threads, and hence simultaneously on multiple CPUs if available. This implementation is truly preemptive.
|
|
|
|
\[2\] possibly, if we decide to go with priorities
|
|
|
|
|
|
|
|
|
|
|
|
---
|
|
|
|
# Optional extensions to basic standard
|
|
|
|
|
|
|
|
|
|
|
|
# Levels
|
|
|
|
|
|
|
|
These are optional extensions a compiler may implement. In some
|
|
|
|
implementations they may entail a run-time cost to non-concurrent code or a
|
|
|
|
compiler might need a special option to enable them. However, A compiler is
|
|
|
|
not required to provide more than one concurrency model as long as it can meet
|
|
|
|
the requirements of the standard and any options it claims to support.
|
|
|
|
|
|
|
|
|
|
|
|
There are several levels of concurrency support which require sucessivly more
|
|
|
|
implementation support and imply more implementation overhead.
|
|
|
|
|
|
|
|
If a compiler documents that it supports one of the following options, then it
|
|
|
|
must adhere to the rules of that option as well.
|
|
|
|
|
|
|
|
## No Concurrency
|
|
|
|
|
|
|
|
## Optional Feature 1 - Preemption
|
|
|
|
|
|
|
|
|
|
|
|
The report says nothing about concurrency at all
|
|
|
|
|
|
|
|
The standard only requires a progress guarentee, that a thread is always
|
|
|
|
running, making progress. If an implementation supports context switching
|
|
|
|
during arbitrary, perhaps even pure, computations and meets the stronger
|
|
|
|
fairness guarentees, then it can be said to support the 'Preemption' option.
|
|
|
|
|
|
|
|
## Concurrent Friendly
|
|
|
|
|
|
|
|
|
|
|
|
Fairness Guarentee
|
|
|
|
|
|
|
|
Enough is specified to allow people to write completley portable programs and
|
|
|
|
libraries that while they may not depend on concurrency, will not break in the
|
|
|
|
presence of it. See "Thread-safety" above.
|
|
|
|
|
|
|
|
- no starvation
|
|
|
|
|
|
|
|
## Concurrent Capabale
|
|
|
|
|
|
|
|
new library calls provided
|
|
|
|
|
|
|
|
|
|
|
|
This would allow concurrency needing programs to be written, but perhaps not
|
|
|
|
as transparently as it curently is with GHC. This would include everything
|
|
|
|
needed to write concurrent programs without anything that would imply a
|
|
|
|
run-time or implementation overhead in the non-concurrent case.
|
|
|
|
- mergeIO, nmergeIO
|
|
|
|
|
|
|
|
## Optional Feature 2 - OS threads
|
|
|
|
|
|
|
|
## Concurrent Built-in
|
|
|
|
|
|
|
|
|
|
|
|
## Concurrent Preemptive/SMP
|
|
|
|
The implementation allows multiple haskell threads to run at once via the
|
|
|
|
operating systems threading service. May take advantange of SMP architectures.
|
|
|
|
|
|
|
|
|
|
|
|
- forkOS,isCurrentThreadBound,runInBoundThread,runInUnboundThread
|
|
|
|
- bound threads
|
|
|
|
- concurrent reentrant supported |
