Pre-emptive or co-operative concurrency (was: Concurrency)
benjamin.franksen at bessy.de
Sat Apr 1 15:04:43 EST 2006
On Wednesday 29 March 2006 13:35, John Meacham wrote:
> I am not sure what the MVar guarentee means, if it is blocked on an
> MVar, then it becomes runnable when the MVar is filled, so the
> runnable rule seems to take care of it.
Unfortunately not. Suppose threads A, B, and C compete for taking the
same MVar. Now, without the MVar related fairness condition, threads A
and B could be scheduled so that both alternately get the MVar but
thread C still can't make any progess since it never gets the MVar.
Note that this problem is related to so called priority inversion in
priority scheduled systems. Priority inversion happens when a high
priority thread waits for a resource held by a low priority process,
but the latter can't make progress because it gets crowded out by a
medium priority thread. In this case the medium priority thread
effectively runs with a priority higher than the high priority thread,
contrary to what the programmer has specified. The standard solution is
to adopt a priority inheritance protocol, that is, temporarily raise
the priority of any process that has claimed a resource to the maximum
priority of all threads waiting for this resource.
There are three kinds of programmers: those who make off by one errors,
and those who don't.
More information about the Haskell-prime