Assuming Mesa semantics for condition variables, our implementation of the blocking bounded queue in Figure 5.8 does not guarantee freedom from starvation: if a continuous stream of threads makes insert (or remove) calls, a waiting thread could wait forever. For example, a thread may call insert and wait in the while loop because the queue is full. Starvation would occur if every time another thread removes an item from the queue and signals the waiting thread, a different thread calls insert, sees that the queue is not full, and inserts an item before the waiting thread resumes. Prove that under Hoare semantics and assuming that signal wakes the longest-waiting thread, our implementation of BBQ ensures freedom from starvation. More precisely, prove that if a thread waits in insert, then it is guaranteed to proceed after a bounded number of remove calls complete, and vice versa.

// Thread-safe blocking queue. const int MAX10 class BBQ // Synchronization variables Lock lock; CV itemAdded; CV item Removed; // State variables int items [MAX]; int front; int nextEmpty; public: BBQ ) -BBQ ) t; void insert(int item); int remove) // Initialize the queue to empty, // the lock to free, and the /1 condition variables to empty BBQ: :BBQ ) front nextEmpty 0; Wait until there is room and // then insert an item void BBQ: :insert(int item) lock.acquire(); while ((nextEmpty - frontMAX) item Removed.wait(&lock); item s [ nextEmpty % MAX] nextEmpty++ itemAdded.signal); lock.release( item ; // Wait until there is an item and // then remove an item. int BBQ: :remove() int item; lock.acquire () while (front nextEmpty) itemAdded.wait (&lock); item = items [front % MAX]; frontt; item Removed.signal() lock.release(); return item; Figure 5.8: Athread-safe blocking // Thread-safe blocking queue. const int MAX10 class BBQ // Synchronization variables Lock lock; CV itemAdded; CV item Removed; // State variables int items [MAX]; int front; int nextEmpty; public: BBQ ) -BBQ ) t; void insert(int item); int remove) // Initialize the queue to empty, // the lock to free, and the /1 condition variables to empty BBQ: :BBQ ) front nextEmpty 0; Wait until there is room and // then insert an item void BBQ: :insert(int item) lock.acquire(); while ((nextEmpty - frontMAX) item Removed.wait(&lock); item s [ nextEmpty % MAX] nextEmpty++ itemAdded.signal); lock.release( item ; // Wait until there is an item and // then remove an item. int BBQ: :remove() int item; lock.acquire () while (front nextEmpty) itemAdded.wait (&lock); item = items [front % MAX]; frontt; item Removed.signal() lock.release(); return item; Figure 5.8: Athread-safe blocking