Pre-emptive or co-operative concurrency (was: Concurrency)
On 28 March 2006 11:14, Malcolm Wallace wrote:
There are certainly technical questions. If Hugs's implementation of concurrency is not concurrency after all, on what basis do we make that determination? Why is a definition of concurrency that encompasses both ghc and Hugs models unacceptable?
Ok, I'll try to nail down what we should require in terms of fairness (which is the same as pre-emption). 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. The spec also needs to say something about non-blocking foreign calls and concurrent I/O. Both are important, because one of the main uses of concurrency is as a way of structuring a program that interacts with asynchronous external agents. So I propose for the purposes of the standard/addendum, we adopt the above definitions of fairness, together with the requirement that "safe" (and maybe "blockable") foreign calls and I/O operations do not block other threads. 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, non-blocking foreign calls could be implemented, and the I/O library could be made to use them. But this is all real work. If you want to be really picky, GHC doesn't comply either, because a thread can avoid pre-emption by not doing any allocation (we consider this a bug). Cheers, Simon [1] http://www.haskell.org/ghc/docs/papers/concurrent-haskell.ps.gz
On Tue, Mar 28, 2006 at 02:43:09PM +0100, Simon Marlow wrote:
So I propose for the purposes of the standard/addendum, we adopt the above definitions of fairness, together with the requirement that "safe" (and maybe "blockable") foreign calls and I/O operations do not block other threads.
this is exactly the purpose of the blockable flag. exactly those FFI routines that are guarenteed to not block are those that have the blockable flag. it happens by accident that this means the same thing as 'safe' in ghc, but that is quite specific to ghcs concurrency implementation. it is quite important to separate the concept of blockable from safe. it is unlikely a cooperative system will ever be able to support 'blockable safe' calls, but with some finagling can support 'blockable unsafe' ones. I have a whole lot to say on these issues but have been sick lately so have been MIA. I hope to catch up soon though. John -- John Meacham - ⑆repetae.net⑆john⑈
"Simon Marlow"
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
On 2006-03-28, Malcolm Wallace
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".
*glyph of enlightenment*. Ah, no wonder a lot of the discussion and docs didn't seem to make sense. -- Aaron Denney -><-
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.
obviously, cs-concepts are still taught differently around the globe.. I was taught that non-preemptive scheduling simply means that threads will never be preempted, so they complete whatever they want to do, then voluntarily return control. the opposite, preemptive scheduling, allocates schedule resources to threads independent of their needs, solely based on meta-level properties (time slices, number of reductions, ..), so threads may be preempted by a context switch in whatever they are doing. there is no implication of priorities, nor is there an implication of re-scheduling not happening at "safe" synchronisation points. it is just that "safety" is from the scheduler's point of view (a reduction step has completed), not from the thread's point of view (all the steps needed for a certain task have been completed). so (at least in my background;-), non-preemptive scheduling implies cooperative concurrency (if any of the threads does not play fair with yields, the whole scheduling arrangement may break down), and preemptive scheduling implies careful programming for another reason (none of the threads may assume that it won't be interrupted and resumed in the middle of some complex activity; which is why atomic actions, transactions, STM, and the like are so important). all of the concurrency implementations discussed so far seem to be based on a mixture of preemptive and non-premptive scheduling. context-switches happen only on specific events, which every thread will usually engage in, although it need not always do so: 1 only calls to yield 2 any calls to concurrency library api 3 any allocation these differ merely in the level of cooperation required from threads in order to achieve the appearance of pre-emptive scheduling. each of them can be defeated by non-cooperative thread code, so none of them is entirely preemptive. however, the more possible thread events are permitted as context-switch points, the closer we come to a preemptive scheduler, as there is less and less potential for threads to be non-cooperative. cheers, claus
Hi,
context-switches happen only on specific events, which every thread will usually engage in, although it need not always do so:
1 only calls to yield 2 any calls to concurrency library api 3 any allocation
The Yhc concurrency switches every n instructions, and therefore even an "evil" thread cannot lock up the system. Of course, even with fully pre-emptive scheduling, you've still got deadlocks... Thanks Neil
participants (6)
-
Aaron Denney -
Claus Reinke -
John Meacham -
Malcolm Wallace -
Neil Mitchell -
Simon Marlow