Pre-emptive or co-operative concurrency (was: Concurrency)

[Simon Marlow]

On 28 March 2006 15:26, Malcolm Wallace wrote:

> "Simon Marlow" <simonmar at microsoft.com> wrote:
> 
>> Ok, I'll try to nail down what we should require in terms of fairness
>> (which is the same as pre-emption).
> 
> The terms are not entirely synonymous.
> 
> 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 those criteria, none of the current Haskell implementations are
> pre-emptive, because no API assigns priorities to threads.  So let's
> not use the term pre-emption; instead let's agree to talk only about
> fairness, since that is the real topic here.

Ok, I won't argue this point.  It depends which definition you read -
I'm using the term preemption to mean that threads can be preempted by
the execution engine.  I won't use the term any more to avoid confusion.

> As I see it, all current (and likely future) implementations of
> concurrency in Haskell use co-operative scheduling.  The only
> differences are in the granularity and positioning of the 'yield'
> calls. 
> 
>   * For Hugs, yield is inserted at certain I/O actions.
>   * For ghc,  yield is inserted after some count of allocations.
>   * For yhc,  yield is inserted after some count of bytecode
> instructions. 

That list is a useful implementation reference, but I think it misses
the point.  It's much more useful to reserve the term "cooperative" for
when the burden is on the programmer to insert context-switch points, as
is the case in Hugs.  This is a significant difference from the
programmer's point of view, whereas the difference in imlementation
between GHC and YHC is to a very close approximation invisible.

Let's stick to fairness.  These are the requirements I think the
standard should include:

   No runnable process will be indefinitely delayed.

   No thread can be blocked indefinitely on an MVar unless another
   thread holds the MVar indefinitely.

   Suitably annotated foreign calls run concurrently
   with other Haskell threads.

That does preclude a cooperative implementation, and for good reasons.
Manuel made the point that if a cooperative implementation is admitted
by the standard, that makes it much harder to write portable concurrent
code.  Code written using GHC wouldn't neceessarily run properly on a
cooperative implementation, despite the fact that both implementations
would be conforming.  I think Haskell' should avoid this pitfall.

Cheers,
	Simon