Pre-emptive or co-operative concurrency (was: Concurrency)
claus.reinke at talk21.com
Wed Mar 29 11:21:17 EST 2006
> 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.
More information about the Haskell-prime