An implementation of integer buffer that creates deadlock

Question

Let’s consider the following pseudocode:

class OneBuf{
    Mutex m;
    CondVar cv;
    int buffer;
    bool full;

    void put(int data){
        m.lock();
        while(full){
            cv.wait(m);
        }
        buffer = data;
        full = true;
        cv.signal();
        m.unlock();
    }

    int get(){
        int data;
        m.lock();
        while(!full){
            cv.wait(m);
        }
        full = false;
        data = buffer;
        cv.signal();
        m.unlock();
        return data;
    }
} 

I was told that the above code is a wrong implementation of a buffer with capacity of one integer and that the lines 14 and 26 should execute cv.broadcast() instead of cv.signal(). Can you help me prove that this correction is necessary by showing an execution of the initial code with 3 threads (e.g. 1 producer and 2 consumers) that creates deadlock (i.e. all 3 of the threads end up sleeping)?

I don’t know if I need graph theory to prove this.

Answer 1

If the application is in the state where one consumer is in the monitor and the other two threads are waiting for it, just signalling one thread risks waking up the other consumer which will get blocked as the buffer now is empty.

And since that blocked consumer does not signal, the producer will not wake up. With the buffer empty the first consumer will eventually be blocked.

One path there starts with an empty buffer(both consumers waiting) and the producer having two items to put in the buffer. Then, on the second put it will be blocked and one of the consumers will enter.