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

[Malcolm Wallace]

"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.

> The Concurrent Haskell paper [1] gives two requirements.  These are:
> 
>   No runnable process will be indefinitely delayed
> 
>   No thread can be blocked indefinitely on an MVar unless
>   another thread holds the MVar indefinitely.
> 
> So I propose for the purposes of the standard/addendum, we adopt the
> above definitions of fairness,

Fair enough. :-)

> The spec also needs to say something about non-blocking foreign calls
> and concurrent I/O.

Another piece of terminology to clear up.  By "non-blocking foreign
call", you actually mean a foreign call that *can* block.  As a
consequence of the fairness policy, you wish to place the requirement on
implementations that such a blocking foreign call _should_not_
block progress of other Haskell threads.  The thread-nature of the
foreign call is "blocking".  The Haskell-API nature is desired to be
"non-blocking".

> That would mean that Hugs doesn't currently comply.  My guess is that
> it could be made a lot closer than it currently is - eg. the IO
> monad's bind could be made to 'yield' occasionally,

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.

Arguably, Hugs has made the wrong choice from a fairness point of view,
but moving the position of the yield, or inserting them more frequently,
should not be a big deal.

> non-blocking foreign calls could be implemented,

This is probably going to be the biggest stumbling block for Hugs.  It
requires to maintain at least two OS-threads, one for the mutator and
one for the foreign call, which I understand makes things difficult.  Is
this where JohnM's suggestion of a minimal poll/select interface comes
in?  Would someone like to set out for discussion what this would mean?

> and the I/O library could be made to use them.

Do you mean some internal I/O library, or the standard Haskell I/O
library?  I would hope the implementation of the latter could be largely
shared.

> But this is all real work.

Indeed.  So are type system extensions, syntax changes, and the overhaul
of the library interfaces.  Perhaps for Hugs, there is currently no
obvious person who feels confident they can implement non-blocking
behaviour for blocking foreign calls.  Well, for nhc98/yhc, we don't
currently have anyone able to re-implement the type system to permit
MPTC+FDs.  That's just the way it is, but these are not insurmountable
technical problems, they are social, organisational, and financial.

Regards,
    Malcolm