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

// 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