Conditional Variable vs Semaphore

Question

When to use a semaphore and when to use a conditional variable?

Solution 1

Locks are used for mutual exclusion. When you want to ensure that a piece of code is atomic, put a lock around it. You could theoretically use a binary semaphore to do this, but that's a special case.

Semaphores and condition variables build on top of the mutual exclusion provide by locks and are used for providing synchronized access to shared resources. They can be used for similar purposes.

A condition variable is generally used to avoid busy waiting (looping repeatedly while checking a condition) while waiting for a resource to become available. For instance, if you have a thread (or multiple threads) that can't continue onward until a queue is empty, the busy waiting approach would be to just doing something like:

//pseudocode
while(!queue.empty())
{
   sleep(1);
}

The problem with this is that you're wasting processor time by having this thread repeatedly check the condition. Why not instead have a synchronization variable that can be signaled to tell the thread that the resource is available?

//pseudocode
syncVar.lock.acquire();

while(!queue.empty())
{
   syncVar.wait();
}

//do stuff with queue

syncVar.lock.release();

Presumably, you'll have a thread somewhere else that is pulling things out of the queue. When the queue is empty, it can call syncVar.signal() to wake up a random thread that is sitting asleep on syncVar.wait() (or there's usually also a signalAll() or broadcast() method to wake up all the threads that are waiting).

I generally use synchronization variables like this when I have one or more threads waiting on a single particular condition (e.g. for the queue to be empty).

Semaphores can be used similarly, but I think they're better used when you have a shared resource that can be available and unavailable based on some integer number of available things. Semaphores are good for producer/consumer situations where producers are allocating resources and consumers are consuming them.

Think about if you had a soda vending machine. There's only one soda machine and it's a shared resource. You have one thread that's a vendor (producer) who is responsible for keeping the machine stocked and N threads that are buyers (consumers) who want to get sodas out of the machine. The number of sodas in the machine is the integer value that will drive our semaphore.

Every buyer (consumer) thread that comes to the soda machine calls the semaphore down() method to take a soda. This will grab a soda from the machine and decrement the count of available sodas by 1. If there are sodas available, the code will just keep running past the down() statement without a problem. If no sodas are available, the thread will sleep here waiting to be notified of when soda is made available again (when there are more sodas in the machine).

The vendor (producer) thread would essentially be waiting for the soda machine to be empty. The vendor gets notified when the last soda is taken from the machine (and one or more consumers are potentially waiting to get sodas out). The vendor would restock the soda machine with the semaphore up() method, the available number of sodas would be incremented each time and thereby the waiting consumer threads would get notified that more soda is available.

The wait() and signal() methods of a synchronization variable tend to be hidden within the down() and up() operations of the semaphore.

Certainly there's overlap between the two choices. There are many scenarios where a semaphore or a condition variable (or set of condition variables) could both serve your purposes. Both semaphores and condition variables are associated with a lock object that they use to maintain mutual exclusion, but then they provide extra functionality on top of the lock for synchronizing thread execution. It's mostly up to you to figure out which one makes the most sense for your situation.

That's not necessarily the most technical description, but that's how it makes sense in my head.

Solution 2

Let's reveal what's under the hood.

Conditional variable is essentially a wait-queue, that supports blocking-wait and wakeup operations, i.e. you can put a thread into the wait-queue and set its state to BLOCK, and get a thread out from it and set its state to READY.

Note that to use a conditional variable, two other elements are needed:

• a condition (typically implemented by checking a flag or a counter)
• a mutex that protects the condition

The protocol then becomes,

1. acquire mutex
2. check condition
3. block and release mutex if condition is true, else release mutex

Semaphore is essentially a counter + a mutex + a wait queue. And it can be used as it is without external dependencies. You can use it either as a mutex or as a conditional variable.

Therefore, semaphore can be treated as a more sophisticated structure than conditional variable, while the latter is more lightweight and flexible.

Solution 3

Semaphores can be used to implement exclusive access to variables, however they are meant to be used for synchronization. Mutexes, on the other hand, have a semantics which is strictly related to mutual exclusion: only the process which locked the resource is allowed to unlock it.

Unfortunately you cannot implement synchronization with mutexes, that's why we have condition variables. Also notice that with condition variables you can unlock all the waiting threads in the same instant by using the broadcast unlocking. This cannot be done with semaphores.

Solution 4

semaphore and condition variables are very similar and are used mostly for the same purposes. However, there are minor differences that could make one preferable. For example, to implement barrier synchronization you would not be able to use a semaphore.But a condition variable is ideal.

Barrier synchronization is when you want all of your threads to wait until everyone has arrived at a certain part in the thread function. this can be implemented by having a static variable which is initially the value of total threads decremented by each thread when it reaches that barrier. this would mean we want each thread to sleep until the last one arrives.A semaphore would do the exact opposite! with a semaphore, each thread would keep running and the last thread (which will set semaphore value to 0) will go to sleep.

a condition variable on the other hand, is ideal. when each thread gets to the barrier we check if our static counter is zero. if not, we set the thread to sleep with the condition variable wait function. when the last thread arrives at the barrier, the counter value will be decremented to zero and this last thread will call the condition variable signal function which will wake up all the other threads!

Solution 5

I file condition variables under monitor synchronization. I've generally seen semaphores and monitors as two different synchronization styles. There are differences between the two in terms of how much state data is inherently kept and how you want to model code - but there really isn't any problem that can be solved by one but not the other.

I tend to code towards monitor form; in most languages I work in that comes down to mutexes, condition variables, and some backing state variables. But semaphores would do the job too.

View more solutions

Comments

[Steven Lu]

This would be a better answer if you explained what "monitor form" is.

[berkay]

Great answer, I would like to add from other so answers:Semaphore is used to control the number of threads executing. There will be fixed set of resources. The resource count will gets decremented every time when a thread owns the same. When the semaphore count reaches 0 then no other threads are allowed to acquire the resource. The threads get blocked till other threads owning resource releases. In short, the main difference is how many threads are allowed to acquire the resource at once ? Mutex --its ONE. Semaphore -- its DEFINED_COUNT, ( as many as semaphore count)

[Vladislavs Burakovs]

Just to elaborate on why there's this while loop instead of a simple if: something called spurios wakeup. Quoting this wikipedia article: "One of the reasons for this is a spurious wakeup; that is, a thread might be awoken from its waiting state even though no thread signaled the condition variable"

[Brent Writes Code]

@VladislavsBurakovs Good point! I think it's also helpful for the case where a broadcast wakes up more threads than there are resources available (e.g. broadcast wakes up 3 threads, but there are only 2 items in the queue).

[Jaafar]

I wish I would upvote you answer until the queue is full ;) Perfect Answer. This code could help figuring out semaphores csc.villanova.edu/~mdamian/threads/PC.htm

[max]

@VladislavsBurakovs To clarify a bit, the reason that the condition may still be false to a thread that has just woken up (resulting in a spurious wakeup) is that there might have been a context switch before the thread got a chance to check the condition again, where some other scheduled thread made that condition false. This is one reason that I know for a spurious wakeup, don't know if there are more.

[einpoklum]

I find it is not entirely clear why a syncVar needs an independently-accessible lock, i.e. why would a thread not simply do syncVar.wait() and have that return when the condition is met and the thread has exclusive access. And when it's done it can syncVar().release()

[宏杰李]

mutex can be viewed as a conditions variable, it's condition is whether or not be holded.

[doron]

In the C++ std library they are all district objects, all implemented using platform specific APIs. Certainly a semaphore will unblock the number of times signalled, condition variable might be be signalled multiple times but unblock only once. This is why the wair takes a mutex as a parameter.

[Kai Petzke]

Condition Variables aren't really good for implementing Barriers, either. In particular, there is a race condition between a thread decrementing said counter and putting itself to sleep on the Condition Variable. So one also needs a Mutex. Each thread has to first acquire the Mutex, then decrement and check the counter, then put itself to sleep on the Condition Variable while atomically releasing the Mutex. When later all threads wake up, they all need to reacquire that Mutex, but can only do so one thread at a time. Therefore, if the OS libs provide a Barrier primitive, then use that!

[John]

@Brent Writes Code "Semaphores and condition variables build on top of the mutual exclusion provide by locks and are used for providing synchronized access to shared resources. They can be used for similar purposes." Any reference? What about std::semaphore and std::conditional_variable?

[John]

@BrentWritesCode There are spurious wakeups for both conditional variable and semaphore. Am I right?

[John]

The description about the protocol is wrong!