Multi-threaded programming - Producer Consumer

Question

The pseudocode for a 'Inadequate implementation' of a producer consumer problem mentioned in wikipedia is as below. This solution is said to have a race condition which could cause deadlock.

My question is : Wouldn't just modifying the conditions of wakeing up the other thread as below solve the possible deadlock issue. That way there is not just one wakeup which could be lost, but subsequent multiple ones, or am I missing something. Trying to understand here.

int itemCount = 0;

procedure producer() {
    while (true) {
        item = produceItem();

        if (itemCount == BUFFER_SIZE) {
            sleep();
        }

        putItemIntoBuffer(item);
        itemCount = itemCount + 1;

        //if (itemCount == 1) <<<<<<<< change this to below condition
        if(itemCount > 0)
        {
            wakeup(consumer);
        }
    }
}

procedure consumer() {
    while (true) {

        if (itemCount == 0) {
            sleep();
        }

        item = removeItemFromBuffer();
        itemCount = itemCount - 1;

        //if (itemCount == BUFFER_SIZE - 1) <<<<<<< Change this to below
        if(itermCount < BUFFER_SIZE)
        {
            wakeup(producer);
        }

        consumeItem(item);
    }
}

Answer 1

Wouldn't just modifying the conditions of wakeing up the other thread as below solve the possible deadlock issue.

No, the race condition still exists. The problem is that there are multiple threads doing the consuming and/or producing. When a consumer (for example) is awoken and told that there are items to be processed, it might go remove the item but some other thread (or threads) has gotten there before it.

The solution is to do the following:

lock() {
   while (itemCount == 0) {
       sleep();
   }

   item = removeItemFromBuffer();
   itemCount = itemCount - 1;
}

So even if the consumer is awoken, it immediately checks again that the itemCount is not 0 with a while loop. Even though the itemCount was incremented, another thread might have removed that element and decremented itemCount before the thread that got the signal had a chance to act. That is the race.

It is the same for the producer side although the race is to stop the producer from over-filling the buffer. A producer may be awoken because there is space available but by the time it goes to put items into buffer, other threads have beaten it and re-filled the buffer. It has to test again to make sure after it was awoken that there is space.

I go into line by line detail about this race on this page from my website entitled Producer Consumer Thread Race Conditions. There also is a little test program there that demonstrates the issue.

The important point to realize is that in most locking implementations, there is a queue of threads waiting to gain access to a lock. When a signal is sent to a thread, it first has to reacquire the lock, before it can continue. When a thread is signaled it then goes to the end of the BLOCK queue. If there are additional threads that are waiting for the lock but not waiting, they will run ahead of the awoken thread and steal the items.

This is very similar to this question about while loops in similar code. Unfortunately the accepted answer does not address this race condition. Please consider upvoting my answer to a similar question here. Spurious wakeups are an issue but the real problem here is the race condition wikipedia is talking about.