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

[Claus Reinke]

> 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