Producer consumer using only 1 additional semaphore

user_10302682 0
Viewed 1090

Solution traditional to producer-consumer

In Operating-Systems, as you see in the link above for producer consumer, two semaphores full and empty are used, why is it not possible to do this using only one quantity semaphore fullEmpty.

What I mean is, we have a binary semaphore mutex and another semaphore fullEmpty, which is initially 0 because there are no items in the buffer, so why do we need 2 semaphores (full, empty)?

The only thing is the order of wait and signal need to be changed so that the updating of fullEmpty is within the critical section.

Any thoughts or reasons?

operating-system mutex multithreading semaphore
2 Answers

The key statement in the description that relates to your answer is "We have a buffer of fixed size."

For the sake of answering your question, let's first assume that the buffer can expand to fit as many items as needed, or in other words the buffer can grow to an unlimited size. In this case, the only synchronization that would need to occur between producers and consumers (apart from locking the mutex to ensure that you don't corrupt items in the critical section) would be ensuring that consumers only consume items after they have been produced by a producer. You could solve this problem with just a mutex and one semaphore. Here is some code, which I borrowed and changed from the link you shared:

Producer

do {
    //produce an item

    wait(mutex);

    //place in buffer

    signal(mutex);
    signal(full);

} while (true);

Consumer

do {
    wait(full);
    wait(mutex);

    //remove item from buffer

    signal(mutex);

    //consume item

} while (true);

As you can see above, the producer is always able to add things to the queue (apart from when the mutex is being held) and doesn't need to wait for consumers to consume anything because the buffer will never fill, even if the consumers don't consume items. On the other hand, consumers can't consume anything until producers have produced items.

To answer your question, you need to focus on the statement, "We have a buffer of fixed size." This changes the problem. Since the buffer is no longer able to grow to an unlimited size, you need to get producers to wait when the buffer is full before they can add more things to the buffer. This is why you need a second semaphore. Not only do consumers need to wait for producers, but now producers need to wait for consumers. You get producers to wait for consumers by getting them to call wait on a semaphore that only consumers call signal on.

You can't do this with only one semaphore because the conditions when a producer has to wait are different from the conditions when a consumer has to wait. Since they should be able to decrement and advance past the semaphore in different conditions, you can't use the same semaphore for both.

user_7756240

This is because there 2 conditions you have to wait for: the queue is empty and the queue is full. But classic semaphore allows you to wait only for one condition - wait until semaphore is not 0.

You can solve this problem using a single synchronization object, but such object needs to be more feature-full than a semaphore. "Bounded semaphore" - semaphore that has a maximum value should be enough as it allows you to block waiting for both conditions.

How to get one is another question:

I suggest you to get familiar with futex interface - with it you can build more powerful and more efficient synchronization objects than regulars ones. Today most OSes provide an equivalent interface and even C++ might introduce something similar in the future (see std::synchronic<T>).

Few notes:

Linux has eventfd which can act as a semaphore when created with EFD_SEMAPHORE flag, but it has maximum value of 0xfffffffffffffffe and it cannot be changed. Maybe some day this syscall will be extended to support maximum value too.

user_11436340
Related