preemptive vs cooperative: attempt at formalization

[John Meacham]

I'd like to be a bit more formal when it comes to the distinction
between cooperative and preemptive implementations of concurrency, here
is a first attempt.

1. termination,

In a concurrent implementation, a thread performing an infinite loop
with no IO or interaction with the outside world can potentially stall
switching to another thread forever, in FP, we usually denote an
infinite loop by _|_. so I think the first difference would be:

[Rule 1]
* in a cooperative implementation of threading, any thread with value
  _|_ may cause the whole program to have value _|_. In a preemtive one,
  this is not true.

I am using _|_ in the stronger sense of non-termination, not including
things like exceptions which should have a well defined behavior.

2. fairness

Assuming no thread has value _|_ now, what can both models guarentee
when it comes to fairness?

both can guarentee every runnable thread will eventually run with a
round-robin type scheduler.

both can fairly allocate CPU time at the limit, if a thread is taking
too much CPU in either model, it can be allocated less timeslices in the
future. the same scheduling algorithms work for both with minor
modifications.

the thing that pre-emptive implementations can do that cooperative ones
cannot is provide latency fairness. as in, the time before a given
thread is scheduled once it becomes runnable can be bound independently
of what other threads are doing.

so perhaps the following

[Rule 2]
* A cooperative system cannot necessarily guarentee or provide for
  latency requirements when it comes to scheduling a thread once it
  becomes runnable. A pre-emptive system can provide such guarentees
  (discounting foreign nonconcurrent calls)


I think these two rules are enough to distinguish when you can say you
meet the pre-emptive option without delving into implementation details.

What do y'all think?


        John





-- 
John Meacham - ⑆repetae.net⑆john⑈