Multithreading: classical Producer Consumer algorithm

Question

Hi all,

Something I don't get about the classical algorithm for the Producer-Consumer problem (from Wikipedia:)

semaphore mutex = 1
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE

procedure producer() {
    while (true) {
        item = produceItem()
        down(emptyCount)
            down(mutex)
                putItemIntoBuffer(item)
            up(mutex)
        up(fillCount)
    }
    up(fillCount) //the consumer may not finish before the producer.
}

procedure consumer() {
    while (true) {
        down(fillCount)
            down(mutex)
                item = removeItemFromBuffer()
            up(mutex)
        up(emptyCount)
        consumeItem(item)
    }
}

I note that both producers and consumers lock 'mutex' prior to messing with the buffer, and unlock it thereafter. If that is the case, i.e. only a single thread is accessing the buffer at any given moment, I don't really see how the above algo differs from a simple solution that entails only putting a guarding mutex over the buffer:

semaphore mutex = 1

procedure producer() {
    while (true) {
        item = produceItem()
        flag = true
        while (flag) {
            down(mutex)
            if (bufferNotFull()) {
                putItemIntoBuffer(item)
                flag = false
            }
            up(mutex)
        }
    }
}


procedure consumer() {
    while (true) {
        flag = true
        while (flag) {
            down(mutex)
            if (bufferNotEmpty()) {
                item = removeItemFromBuffer()
                flag = false
            }
            up(mutex)
        }
        consumeItem(item)
    }
}

Only thing I can think of that necessitates using the 'fillCount' and 'emptyCount' semaphores is scheduling.

Maybe the first algo is for making sure that in a state where 5 consumers are waiting on an empty buffer (zero 'fillCount'), it is assured that when a new producer comes along, it will go past its "down(emptyCount)" statement quickly and get the 'mutex' quickly.

(whereas in the other solution the consumers will needlessly get the 'mutex' only to relinquish it until the new producer gets it and inserts an item).

Am I right? Am I missing something?

Answer 1

If there are no messages in the buffer, the consumer will down the mutex, check the buffer, find that it's empty, up the mutex, loop back around and immediately repeat the process. In simple terms, consumers and producers are stuck in busy loops that chew up 100% of a CPU core. This is not just a theoretical problem, either. You may well find that your computer's fan starts to spin every time you run your program.

Answer 2

There is a starving issue if more than one consumer is involved. In the latter example consumer checks for an item in a loop. But by the time he get's to try again some other consumer may "steal" his item. And next time again, and again. That is not nice.

Answer 3

There's more than just the locking of the buffer going on.

The fillCount semaphore in the first program is to pause the consumer(s) when there's nothing left to consume. Without it, you're constantly polling the buffer to see if there's anything to get, and that's quite wasteful.

Likewise, the emptyCount semaphore pauses the producer when the buffer is full.

Answer 4

The hole concept of the producer/consumer pattern is that the shared resource (buffer) is only accessed if certain criteria are met. And to not utilize unnecessary CPU cycles in order to make sure they are met.

Consumer:

• Wait if there is nothing to consume (=> empty buffer).

Producer:

• Wait if there is not enough space in the buffer.

And for both its very important to note:

• Wait != Spin wait