What is a semaphore

Question

A semaphore is a programming concept that is frequently used to solve multi-threading problems   My question to the community    What is a semaphore and how do you use it

User · Answer

Mutex  exclusive-member access to a resource  Semaphore  n-member access to a resource  That is  a mutex can be used to syncronize access to a counter  file  database  etc   A sempahore can do the same thing but supports a fixed number of simultaneous callers  For example  I can wrap my database calls in a semaphore 3  so that my multithreaded app will hit the database with at most 3 simultaneous connections  All attempts will block until one of the three slots opens up  They make things like doing naive throttling really  really easy

User · Answer

Craig      A semaphore is a way to lock a   resource so that it is guaranteed that   while a piece of code is executed    only this piece of code has access to   that resource  This keeps two threads   from concurrently accesing a resource    which can cause problems    This is not restricted to only one thread  A semaphore can be configured to allow a fixed number of threads to access a resource

User · Answer

I ve created the visualization which should help to understand the idea  Semaphore controls access to a common resource in a multithreading environment    ExecutorService executor   Executors newFixedThreadPool 7    Semaphore semaphore   new Semaphore 4    Runnable longRunningTask      - gt        boolean permit   false      try           permit   semaphore tryAcquire 1  TimeUnit SECONDS           if  permit                System out println  Semaphore acquired                Thread sleep 5             else               System out println  Could not acquire semaphore                    catch  InterruptedException e            throw new IllegalStateException e         finally           if  permit                semaphore release                           execute tasks for  int j   0  j  lt  10  j          executor submit longRunningTask     executor shutdown      Output  Semaphore acquired Semaphore acquired Semaphore acquired Semaphore acquired Could not acquire semaphore Could not acquire semaphore Could not acquire semaphore   Sample code from the article

User · Answer

There are two essential concepts to building concurrent programs - synchronization and mutual exclusion  We will see how these two types of locks  semaphores are more generally a kind of locking mechanism  help us achieve synchronization and mutual exclusion   A semaphore is a programming construct that helps us achieve concurrency  by implementing both synchronization and mutual exclusion  Semaphores are of two types  Binary and Counting   A semaphore has two parts   a counter  and a list of tasks waiting to access a particular resource  A semaphore performs two operations   wait  P   this is like acquiring a lock   and release  V   similar to releasing a lock  - these are the only two operations that one can perform on a semaphore  In a binary semaphore  the counter logically goes between 0 and 1  You can think of it as being similar to a lock with two values   open closed  A counting semaphore has multiple values for count   What is important to understand is that the semaphore counter keeps track of the number of tasks that do not have to block  i e   they can make progress  Tasks block  and add themselves to the semaphore s list only when the counter is zero  Therefore  a task gets added to the list in the P   routine if it cannot progress  and  freed  using the V   routine   Now  it is fairly obvious to see how binary semaphores can be used to solve synchronization and mutual exclusion - they are essentially locks   ex  Synchronization   thread A  semaphore  amp s    locks semaphores are passed by reference  think about why this is so  A semaphore  amp s   s s      constructor foo        s P        some block of code B2          thread B  semaphore  amp s  B semaphore  amp s   s s      constructor foo               some block of code B1 s V          main    semaphore s 0      we start the semaphore at 0  closed  A a s   B b s       In the above example  B2 can only execute after B1 has finished execution  Let s say thread A comes executes first - gets to sem P    and waits  since the counter is 0  closed   Thread B comes along  finishes B1  and then frees thread A - which then completes B2  So we achieve synchronization   Now let s look at mutual exclusion with a binary semaphore   thread mutual ex  semaphore  amp s  mutual ex semaphore  amp s   s s      constructor foo        s P      critical section s V            s P      critical section s V            main    semaphore s 1   mutual ex m1 s   mutual ex m2 s       The mutual exclusion is quite simple as well - m1 and m2 cannot enter the critical section at the same time  So each thread is using the same semaphore to provide mutual exclusion for its two critical sections  Now  is it possible to have greater concurrency  Depends on the critical sections   Think about how else one could use semaphores to achieve mutual exclusion   hint hint   do i necessarily only need to use one semaphore    Counting semaphore  A semaphore with more than one value  Let s look at what this is implying - a lock with more than one value   So open  closed  and    hmm  Of what use is a multi-stage-lock in mutual exclusion or synchronization   Let s take the easier of the two   Synchronization using a counting semaphore  Let s say you have 3 tasks -  1 and 2 you want executed after 3  How would you design your synchronization   thread t1      s P      block of code B1  thread t2      s P      block of code B2  thread t3        block of code B3 s V    s V        So if your semaphore starts off closed  you ensure that t1 and t2 block  get added to the semaphore s list  Then along comes all important t3  finishes its business and frees t1 and t2  What order are they freed in  Depends on the implementation of the semaphore s list  Could be FIFO  could be based some particular priority etc   Note   think about how you would arrange your P s and V s if you wanted t1 and t2 to be executed in some particular order  and if you weren t aware of the implementation of the semaphore    Find out   What happens if the number of V s is greater than the number of P s    Mutual Exclusion Using counting semaphores  I d like you to construct your own pseudocode for this  makes you understand things better   - but the fundamental concept is this   a counting semaphore of counter   N allows N tasks to enter the critical section freely  What this means is you have N tasks  or threads  if you like  enter the critical section  but the N 1th task gets blocked  goes on our favorite blocked-task list   and only is let through when somebody V s the semaphore at least once  So the semaphore counter  instead of swinging between 0 and 1  now goes between 0 and N  allowing N tasks to freely enter and exit  blocking nobody   Now gosh  why would you need such a stupid thing  Isn t the whole point of mutual exclusion to not let more than one guy access a resource    Hint Hint   You don t always only have one drive in your computer  do you       To think about   Is mutual exclusion achieved by having a counting semaphore alone  What if you have 10 instances of a resource  and 10 threads come in  through the counting semaphore  and try to use the first instance

User · Answer

Consider  a taxi that can accommodate a total of 3 rear  2 front  persons including the driver  So  a semaphore allows only 5 persons inside a car at a time  And a mutex allows only 1 person on a single seat of the car   Therefore  Mutex is to allow exclusive access for a resource  like an OS thread  while a Semaphore is to allow access for n number of resources at a time

User · Answer

Semaphore can also be used as a     semaphore  For example if you have multiple process enqueuing data to a queue  and only one task consuming data from the queue  If you don t want your consuming task to constantly poll the queue for available data  you can use semaphore   Here the semaphore is not used as an exclusion mechanism  but as a signaling mechanism  The consuming task is waiting on the semaphore The producing task are posting on the semaphore   This way the consuming task is running when and only when there is data to be dequeued

User · Answer

This is an old question but one of the most interesting uses of semaphore is a read write lock and it has not been explicitly mentioned   The r w locks works in simple fashion  consume one permit for a reader and all permits for writers  Indeed  a trivial implementation of a r w lock but requires metadata modification on read  actually twice  that can become a bottle neck  still significantly better than a mutex or lock   Another downside is that writers can be started rather easily as well unless the semaphore is a fair one or the writes acquire permits in multiple requests  in such case they need an explicit mutex between themselves   Further read

User · Answer

A semaphore is a way to lock a resource so that it is guaranteed that while a piece of code is executed  only this piece of code has access to that resource   This keeps two threads from concurrently accesing a resource  which can cause problems

User · Answer

A semaphore is an object containing a natural number  i e  a integer greater or equal to zero  on which two modifying operations are defined  One operation  V  adds 1 to the natural  The other operation  P  decreases the natural number by 1  Both activities are atomic  i e  no other operation can be executed at the same time as a V or a P    Because the natural number 0 cannot be decreased  calling P on a semaphore containing a 0 will block the execution of the calling process  thread  until some moment at which the number is no longer 0 and P can be successfully  and atomically  executed   As mentioned in other answers  semaphores can be used to restrict access to a certain resource to a maximum  but variable  number of processes

User · Answer

Think of semaphores as bouncers at a nightclub  There are a dedicated number of people that are allowed in the club at once  If the club is full no one is allowed to enter  but as soon as one person leaves another person might enter   It s simply a way to limit the number of consumers for a specific resource  For example  to limit the number of simultaneous calls to a database in an application   Here is a very pedagogic example in C   -   using System  using System Collections Generic  using System Text  using System Threading   namespace TheNightclub       public class Program               public static Semaphore Bouncer   get  set             public static void Main string   args                           Create the semaphore with 3 slots  where 3 are available              Bouncer   new Semaphore 3  3                   Open the nightclub              OpenNightclub                       public static void OpenNightclub                         for  int i   1  i  lt   50  i                                     Let each guest enter on an own thread                  Thread thread   new Thread new ParameterizedThreadStart Guest                    thread Start i                                    public static void Guest object args                           Wait to enter the nightclub  a semaphore to be released               Console WriteLine  Guest  0  is waiting to entering nightclub    args               Bouncer WaitOne                              Do some dancing              Console WriteLine  Guest  0  is doing some dancing    args               Thread Sleep 500                   Let one guest out  release one semaphore               Console WriteLine  Guest  0  is leaving the nightclub    args               Bouncer Release 1

User · Answer

So imagine everyone is trying to go to the bathroom and there s only a certain number of keys to the bathroom  Now if there s not enough keys left  that person needs to wait  So think of semaphore as representing those set of keys available for bathrooms  the system resources  that different processes  bathroom goers  can request access to   Now imagine two processes trying to go to the bathroom at the same time  That s not a good situation and semaphores are used to prevent this  Unfortunately  the semaphore is a voluntary mechanism and processes  our bathroom goers  can ignore it  i e  even if there are keys  someone can still just kick the door open    There are also differences between binary mutex  amp  counting semaphores    Check out the lecture notes at http   www cs columbia edu  jae 4118 lect L05-ipc html

User · Answer

A hardware or software flag  In multi tasking systems   a semaphore is as variable with a value that indicates the status of a common resource A process needing the resource checks the semaphore to determine the resources status and then decides how to proceed

User · Answer

Semaphores are act like thread limiters    Example  If you have a pool of 100 threads and you want to perform some DB operation  If 100 threads access the DB at a given time  then there may be locking issue in DB so we can use semaphore which allow only limited thread at a time Below Example allow only one thread at a time  When a thread call the acquire   method  it will then get the access and after calling the release   method  it will release the acccess so that next thread will get the access       package practice      import java util concurrent Semaphore       public class SemaphoreExample           public static void main String   args                Semaphore s   new Semaphore 1               semaphoreTask s1   new semaphoreTask s               semaphoreTask s2   new semaphoreTask s               semaphoreTask s3   new semaphoreTask s               semaphoreTask s4   new semaphoreTask s               semaphoreTask s5   new semaphoreTask s               s1 start                s2 start                s3 start                s4 start                s5 start                         class semaphoreTask extends Thread           Semaphore s          public semaphoreTask Semaphore s                this s   s                     Override         public void run                 try                   s acquire                    Thread sleep 1000                   System out println Thread currentThread   getName     Going to perform some operation                    s release                  catch  InterruptedException e                    e printStackTrace

User · Answer

The article Mutexes and Semaphores Demystified by Michael Barr is a great short introduction into what makes mutexes and semaphores different  and when they should and should not be used  I ve excerpted several key paragraphs here  The key point is that mutexes should be used to protect shared resources  while semaphores should be used for signaling  You should generally not use semaphores to protect shared resources  nor mutexes for signaling  There are issues  for instance  with the bouncer analogy in terms of using semaphores to protect shared resources - you can use them that way  but it may cause hard to diagnose bugs   While mutexes and semaphores have some similarities in their implementation  they should always be used differently  The most common  but nonetheless incorrect  answer to the question posed at the top is that mutexes and semaphores are very similar  with the only significant difference being that semaphores can count higher than one  Nearly all engineers seem to properly understand that a mutex is a binary flag used to protect a shared resource by ensuring mutual exclusion inside critical sections of code  But when asked to expand on how to use a  quot counting semaphore  quot  most engineers   varying only in their degree of confidence   express some flavor of the textbook opinion that these are used to protect several equivalent resources       At this point an interesting analogy is made using the idea of bathroom keys as protecting shared resources - the bathroom   If a shop has a single bathroom  then a single key will be sufficient to protect that resource and prevent multiple people from using it simultaneously  If there are multiple bathrooms  one might be tempted to key them alike and make multiple keys - this is similar to a semaphore being mis-used   Once you have a key you don t actually know which bathroom is available  and if you go down this path you re probably going to end up using mutexes to provide that information and make sure you don t take a bathroom that s already occupied  A semaphore is the wrong tool to protect several of the essentially same resource  but this is how many people think of it and use it  The bouncer analogy is distinctly different - there aren t several of the same type of resource  instead there is one resource which can accept multiple simultaneous users   I suppose a semaphore can be used in such situations  but rarely are there real-world situations where the analogy actually holds - it s more often that there are several of the same type  but still individual resources  like the bathrooms  which cannot be used this way       The correct use of a semaphore is for signaling from one task to another  A mutex is meant to be taken and released  always in that order  by each task that uses the shared resource it protects  By contrast  tasks that use semaphores either signal or wait   not both  For example  Task 1 may contain code to post  i e   signal or increment  a particular semaphore when the  quot power quot  button is pressed and Task 2  which wakes the display  pends on that same semaphore  In this scenario  one task is the producer of the event signal  the other the consumer       Here an important point is made that mutexes interfere with real time operating systems in a bad way  causing priority inversion where a less important task may be executed before a more important task because of resource sharing   In short  this happens when a lower priority task uses a mutex to grab a resource  A  then tries to grab B  but is paused because B is unavailable   While it s waiting  a higher priority task comes along and needs A  but it s already tied up  and by a process that isn t even running because it s waiting for B   There are many ways to resolve this  but it most often is fixed by altering the mutex and task manager   The mutex is much more complex in these cases than a binary semaphore  and using a semaphore in such an instance will cause priority inversions because the task manager is unaware of the priority inversion and cannot act to correct it       The cause of the widespread modern confusion between mutexes and semaphores is historical  as it dates all the way back to the 1974 invention of the Semaphore  capital  quot S quot   in this article  by Djikstra  Prior to that date  none of the interrupt-safe task synchronization and signaling mechanisms known to computer scientists was efficiently scalable for use by more than two tasks  Dijkstra s revolutionary  safe-and-scalable Semaphore was applied in both critical section protection and signaling  And thus the confusion began  However  it later became obvious to operating system developers  after the appearance of the priority-based preemptive RTOS  e g   VRTX  ca  1980   publication of academic papers establishing RMA and the problems caused by priority inversion  and a paper on priority inheritance protocols in 1990  3 it became apparent that mutexes must be more than just semaphores with a binary counter   Mutex  resource sharing Semaphore  signaling Don t use one for the other without careful consideration of the side effects

[multithreading] What is a semaphore?

Examples related to multithreading

Examples related to concurrency

Examples related to semaphore