Semaphore uses two atomic operations: wait and signal to solve critical section problems.

Scope

This article explains semaphore, mutex, and binary semaphore in detail.

Definition 

Lock-based synchronization is simple to lock(mutex) where a critical section is used. We acquire the lock, enter into the critical section then release the lock. Let’s consider the lock solution in terms of restroom analogy. The restroom has a gate and lock, if you want to use the restroom you just need to have the key to enter the locked restroom. You use this key, unlock the restroom, use it, then once you come out, you leave the key outside the restroom. So if there’s another process who wants to or another person who wants to use this restroom, he sees the key is available, he unlocks and uses the restroom and again comes out and puts the key outside, that is the simple lock base solution. The problem here is there are people who are waiting outside this restroom and these people need to stand there. These people need to stand there to see if somebody has come out and locked the restroom and put the key outside. So you need to have to continuously wait if you want to use the restroom, this is called busy waiting. In lock synchronization, we use a loop that waits for the lock to become false. 

Another problem is there is no queueing among the people. So there is one person who takes the key, uses the restroom, and comes out then again takes the key, uses the restroom, and comes out, the other people keep building in the queue. There is no bound waiting. 

This lock-based solution cannot be used in complex situations of the operating system. The only complex situation is there is a process P1 which has the statement S1 and another process P2 which has the statement S2. You want to ensure that S1 of the process executes S2 of the process. For example, if you want to see processes then you want to see how many times chrome appeared in the output. You want to do grab chrome and then you want to count how many times chrome appears. So there are three processes Ps, grab and wc.Ps will acquire the lock and produce something in the buffer. The grab will acquire the lock will take something from the buffer i.e take the produce thing by the ps. This is basically producer-consumer problem variation. Then we will come and take things from the buffer. They are running one after the other because they need to acquire the lock. You can use this CPU better. You can use some other mechanism in a way that whenever Ps has produced something, it tells the other process grab who is waiting to get an item to take this item and run a statement which takes an item.

Last but not the least issue is what if there are multiple instances of a device that is non-shareable. So there are three printers in your system. But one process can use a printer at a time. So you need to access the lock of this printer to use this printer but they’re three printers. If this printer is not available then you can use the other printer. So if you go and implement this solution of the critical section using lock it becomes a really complex solution.

Semaphore is going to simplify it a lot. Let’s understand in terms of restroom analogy.  It becomes really complex to use locks outside the restrooms and have keys outside the restrooms and then check them one by one. A semaphore is simply a count variable and the queue. Initially, this count variable represents the number of resources available. If there are three restrooms and no person is there, the count is 3 and the queue is empty. Whenever a person uses a restroom count is decreased and if the count becomes less than 0 after decrementing, it means no restrooms are available and the remaining persons are added to the queue. The person waits in the queue before acquiring the restroom.

There are two processes with semaphore. Wait and Signal. Before acquiring a resource you call the waiting process and after using the resource or critical section you call the signal process. The wait process simply decreases and the count signal process simply increases the count.

Now imagine the count becomes zero. All the restrooms are occupied three people came took the restrooms and there are more people coming so the count will become negative because they will all call wait and wait for the restrooms. So what this semaphore solution is when all the three restrooms are occupied, it asks them to wait but does not ask them to stand outside the restroom, it asks them to go and sleep and not stand outside. In terms of processes, do not run in a loop to wait for some critical section or some resource to become free, go and sleep and the semaphore says I’ll wake you up when a person leaves the restroom, the semaphore is going to call signal and if there are people in the queue it’ll wait, it will wake up one of these processes and ask them to use the restroom. 

So the analogy in terms of restrooms is there is a security guard who is a semaphore who is standing outside these restrooms and there is a queue of people who want to use this restroom. When all the restrooms are occupied security guard takes the phone number of the person and asks them to go and rest and when the restroom will be available he will call. 

The pseudocode of wait and signal are:

Struct sem{
                Int count;
                 Queue q;
                }

Sem S(3,empty)

void wait()
{
S.count - -;
  if(s.count <0) {
Add the caller process P to Q
Sleep(P)
}
}

void signal()
{
  S.count + +;
if (s.count<=0)
{
Remove a process P from q;
Wakeup (P)
}
}

Binary Semaphore

A binary semaphore has values only true and false. We can use binary semaphore as mutex also but additional functionalities like wake up and sleep and queue so that’s can be used in place of a mutex it provides additional functionalities like it has a queue and it has the sleep call whenever a process is already acquired a critical section if more process come they go to sleep.

Implementation of a binary semaphore:

Struct BinSem
{
 bool val;
Queue q;
}
void wait()
{
if(s val==1)
   s val = 0;
else{
Put this process P in q
Sleep(P)
}
}

Boolean S(true,empty)
Global

void signal()
{
  if(q is empty)
 S val = 1;
  else{
Pick a process P from q.
Wake up(P)
}
}

Semaphores are some variables and they are implemented by the operating system, the kernel has to implement them. Wait and the signal must be atomic. Atomicity is required in these two operations it should not happen that part of these operations executes and part does not execute. Atomicity is achieved using a lock your operating system that provides the semaphore service internally uses a lock to ensure that these operations are atomic.

Summary

• Semaphore is provided by the operating system because of its shared memory.
• They are implemented using locks, and some facilities are implemented on top of locks.
• The two operations wait and signal both have to be atomic. Either the complete operation happens or nothing happens in this operation. 

Special thanks to Avaneet Kaur Saluja for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article