What are the practical uses of semaphores?

Question

Nonbinary ones..
I have never encountered a problem that required me to use a semaphore instead of mutex. So is this mostly theoretical construct, or real sw like Office, Firefox have places where they use it? If so what are the common use patterns for semaphores?

Solution 1

I think you already know what a semaphore is and you are just wondering how it is used on "real software".

"real sw like Office, Firefox have places where they use it?"

Yes, "real software" use semaphores a lot, it is not just theoretical, e.g. Chromium source, windows semaphore handling code and the same code used by Virtual Box.

"What are the practical uses of semaphores" / "What are the common use patterns for semaphores?"

They are more suitable for producer-consumer synchronization problems. Situations that you have the number of producers and consumers both > 1.

The Fuhrmanator's reference of typical use of semaphores are good ones.

Solution 2

Non-binary semaphores are used in resource allocation. A semaphore might hold the count of the number of a particular resource.

If you have a pool of connections, such as a web browser might use, then an individual thread might reserve a member of the pool by waiting on the semaphore to get a connection, uses the connection, then releases the connection by releasing the semaphore.

You can emulate a semaphore by creating a counter and then establishing a mutual exclusion region around the counter. However, waiting for a resource such as above, requires a two-level mutex and is not quite so elegant as using the semaphore.

Solution 3

A semaphore can count. Counting is fundamentally thread-unsafe, it is a read-modify-write operation on the processor and therefore not atomic. There are lesser primitives available to count safely, Interlocked.Increment() is atomic. But atomicity is a pretty weak threading primitive, in many cases you also have to block code when the count is at a critical value.

With 0 being "critical", all resources have been used. A standard example is counting down processor cores to run threads, once you've used them all then you should not start another thread until one of them completes and doesn't need a processor core anymore. As basic as it gets.

Binary semaphores often appear in literature about threading. A standard text-book entry and closely tied to a fellow Dutchman called Edsger Dijkstra. A pioneer in computer science that first started to think in the 1960s about what you'd do to get a processor to run multiple programs. His P and V annotation only makes sense to a Dutch speaker like me. Parkeer and Vrij are terms you use when you try to put your car somewhere :) This was long before everybody started to think about having different kinds of threading primitives, like mutex and monitor. Primitives that only require having support for a semaphore, once you got a binary semaphore then you do everything else. Building abstractions on top of a basic facility, the way composition works in software.

Noodling on a bit, I'm on a roll, one thing that makes Semaphore quite different from other primitives like Mutex and Monitor and lock is that it doesn't have thread affinity. That's a rather big deal when you write threaded code, the usual contract you try to implement is that only one thread can access a resource at the same time. All of the other .NET synchronization objects are re-entrant, you cannot deadlock yourself by taking a lock more than once on the same thread. They are very friendly and simply increment a counter when you acquire the lock. And count down again when you release. And only give up on the lock when the count reaches 0. Semaphore doesn't work that way at all, it counts when you acquire regardless of which thread acquired it. In some cases that really matters, like the count-down-the-thread-resources example I quoted earlier.

Which is really what is useful for. Not exactly very common. A monitor is the Swiss army-knife of threading, which is why it got its own keyword. The lock keyword in C#, SyncLock in VB.NET

Solution 4

Quoting Doug Schmidt in http://www.cs.wustl.edu/~schmidt/win32-cv-1.html section 2.2:

Counting semaphores are a synchronization mechanism commonly used to serialize or coordinate multiple threads of control. Conceptually, counting semaphores are non-negative integers that can be incremented and decremented atomically. If a thread tries to decrement a semaphore whose value equals 0 this thread is suspended waiting for another thread to increment the semaphore count above 0.

Counting semaphores are often used to keep track of changes in the state of objects shared by multiple threads in a process. For instance, they can record the occurrence of a particular event. Unlike condition variables, semaphores maintain state. Therefore, they allow threads to make decisions based upon this state, even if the event has occurred in the past.

As for patterns, there are two as per http://www.freertos.org/Real-time-embedded-RTOS-Counting-Semaphores.html

Counting semaphores are typically used for two things:

1. Counting events. In this usage scenario an event handler will 'give' a semaphore each time an event occurs (incrementing the semaphore count value), and a handler task will 'take' a semaphore each time it processes an event (decrementing the semaphore count value). The count value is therefore the difference between the number of events that have occurred and the number that have been processed. In this case it is desirable for the count value to be zero when the semaphore is created.

2. Resource management. In this usage scenario the count value indicates the number of resources available. To obtain control of a resource a task must first obtain a semaphore - decrementing the semaphore count value. When the count value reaches zero there are no free resources. When a task finishes with the resource it 'gives' the semaphore back - incrementing the semaphore count value. In this case it is desirable for the count value to be equal the maximum count value when the semaphore is created.

Solution 5

A possible practical example could be a fixed Thread pool: you don't want to waste all your system resources so you allow only a certain number of Threads to execute at a certain time; all remaining Threads will wait in a queue.

Now, I doubt that for instance Java Thread Pool are implemented using a bare resource like a semaphore, but whatever synchronization construct is used, it is theoretically equivalent. You can get a full explanation on Java Thread Pools (and Fixed Thread Pools) here: http://docs.oracle.com/javase/tutorial/essential/concurrency/pools.html

View more solutions