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

[Benjamin Franksen]

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.

Ben
-- 
There are three kinds of programmers: those who make off by one errors, 
and those who don't.