Synchronizing Access to Shared Objects - Operating Systems: Principles and Practice - page 212

Exercises

5. Assuming Hansen semantics for condition variables, our implementation
of the blocking bounded queue in Figure 5.10 does not guarantee free-
dom from starvation: if a continuous stream of threads makes insert() (or
remove()) calls, it is possible for a waiting thread to wait forever. For
example, a thread may call insert() and wait in the while(isFull())
loop; then, every time another thread calls remove() and signals on the
itemRemoved condition variable, a different thread might call insert() ,
see that the queue is not full, and insert an item before the waiting
thread resumes. Then, when the waiting thread resumes, it will retest
the isFull() predicate, see that the queue is full, and wait() .
Prove that under Hoare semantics and assuming that when a signal occurs,
it is the longest-waiting thread that is resumed, our implementation of
BBQ ensures freedom from starvation. That is, that if a thread waits in
insert() , then it is guaranteed to proceed after a bounded number of
remove() calls complete, and vice versa.

6. As noted in the previous problem, our implementation of the blocking
bounded queue in Figure 5.10 does not guarantee freedom from starvation.
Modify the code to ensure freedom from starvation so that if a thread waits
in insert() , then it is guaranteed to proceed after a bounded number of
remove() calls complete, and vice versa. Note: Your implementation
must work under Hansen/Mesa semantics for condition variables.

5.5 Implementing synchronization objects

We have described two types of synchronization variables, locks and condition
variables. Given these synchronization variables, we can implement shared ob-
jects to coordinate access to shared state. In this section, we describe how to
implement these important building blocks.
Recall from Chapter 4 that threads can be implemented for the kernel or
for user-level processes. We will initially describe how to implement locks for
in-kernel threads; at the end of this section we discuss the changes needed to
support these abstractions for threads in user-level processes.

5.5.1 Implementing locks

Recall from Section 5.3 that a lock allows us to group an arbitrary sequence
of operations on shared state into an atomic unit by calling Lock::acquire()