Why does “producers and consumers check availability before getting the mutex” avoid deadlock?

Question

In Little Book of Semaphores:

4.1.6 Finite buffer producer-consumer solution

Finite buffer consumer solution

1 items.wait ()
2 mutex.wait ()
3 event = buffer .get ()
4 mutex. signal ()
5 spaces . signal ()
6
7 event. process ()

Finite buffer producer solution

1 event = waitForEvent ()
2
3 spaces .wait ()
4 mutex.wait ()
5 buffer .add(event)
6 mutex. signal ()
7 items. signal ()

In order to avoid deadlock, producers and consumers check availability before getting the mutex.

Why does "producers and consumers check availability before getting the mutex" avoid deadlock?

I have learned some methods preventing deadlock by making one of the four necessary conditions of deadlock not hold (mutual exclusion, hold and wait, nonpreemtible, circular waiting. c.f. Section 7.3 in Operating Systems Concepts), and some methods avoiding deadlock (c.f. Section 7.4). I was wondering what condition the solution in the quote makes not hold, or what deadlock avoidance method it uses?

Thanks.

Answer 1

This solution to producer-consumer is preventing both circular waiting and holding while waiting from occurring.

Basically, if there are no items in the queue for the consumer to grab, then there are definitely spaces available for the producer to fill. And both processes know about these, because of the semaphores in use (provided you correctly set the semaphore counts up before starting the program):

a) if no items:

• items semaphore is empty and consumer is waiting for it to go up without taking the hold of the queue;
• spaces semaphore is up and producer is not waiting on anything (other producers excluded) before grabbing the queue and putting the new item into it, after which it will signal on the items semaphore and that will release one of the consumers, who are waiting on it;

b) if no spaces:

• spaces semaphore is empty and producer is waiting for it to go up without taking the hold of the queue;
• items semaphore is up and consumer is not waiting on anything (other consumers excluded) before grabbing the queue and taking an item out of it, after which it will signal on the spaces semaphore and that will release one of the producers, who are waiting on it.

c) if both items and spaces:

• items semaphore is up and consumer is not waiting on anything (except for the mutex) before grabbing the queue and taking an item out of it;
• spaces semaphore is up and producer is not waiting on anything (except for the mutex) before grabbing the queue and putting the new item into it;

d) if no items and no spaces—can only happen if the consumer has just grabbed an item and is about to refill spaces semaphore or the producer has just put a new item in and is about to refill items semaphore.

Also, this use of semaphores makes sure that if the item is spoken for, the next consumer to reach the semaphore will not try grabbing it, even if it is still in the queue and same goes for spaces.