Scheduling Resources in a Threaded Environment

Marc Horowitz

Section 4: Prof. Peter Elias Luis Rodriguez February 26, 1991

In Hoare’s model, wait and signal are direct commands to the scheduler. When shared data needs to be protected against being modified by multiple threads concurrently, the critical code is placed inside a monitor function. At the beginning of the monitor function, a condition variable is waited on. If no other thread is waiting on the condition, execution continues, otherwise execution is blocked. At the end of the monitor, the function signals the condition. At this point, exactly one blocked thread is allowed to begin execution again. If there are no blocked threads, the signal is ignored.

In contrast, in Birrell’s model, the signal does not guarantee that exactly one blocked thread will be started. It is possible for more than one thread to be started, and it is possible to broadcast on a condition, which will cause all threads to continue.

The most important way in which these models differ is that after a wait unblocks in the Hoare model, the thread knows that it has exclusive access, and that no other thread has interposed since the most recent thread signalled the condition. Under the Birrell model, this is not guaranteed, and the thread must check that the condition it was waiting for is really in the state the thread wants it in.

Because of the above difference, the Hoare model makes it easier to reason about multi-threaded programs. As long as all operations which need to be atomic are protected inside monitor functions, there will be no problems of timing-related data corruption. With the Birrell model, the programmer needs to be more careful about keeping his data intact, as he must remember to check the state of his data before and after the wait on the condition variable. Most of the other issues of correctness, such as deadlocking and efficiency, are essentially the same in both models.