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.