Session 30: Semaphores

We tried everything. We looked and software based solutions that were working for just 2 processes. We tried extending them to n processes using some hardware based mechanisms. We tried to optimise the waiting using blocking. But we did not get a single tools that could

• Eliminate Busy Waiting
• Be a software based solution
• Provide mutual exclusion
• Provide progress
• Provide bounded waiting.

That is until Dijkastra came along with the concept of Semaphores while working on THE Multiprogramming System.

Dijkastra borrowed the term Semaphore from railway signalling!

It is a physical mechanism with arms that can be raised or lowered to tell a train if it can proceed or stop. Why he borrowed this name we will see shortly!

Forget about TSL, Peterson, Locks etc. If you had to tackle this problem and create an abstract tool that can satisfy all these requirements. What would you do? Let us see how Edger Dijkastra might have come up with a solution.

Binary Semaphore

The previous ideas failed because the availability check and blocking were two different operations causing the Lost Wakeup Problem. So it would be better to have this step indivisible or atomic in nature so there is not window for preemption.

class Semaphore
{
private:
    int value;
    Queue waitingProcesses;

public:

    Semaphore(int initialValue)
    {
        value = initialValue;
    }

    P(Process P)
    {
        atomically
        {
            if (value > 0)
            {
                value--;
            }
            else
            {
                waitingProcesses.push(P);
                BLOCK(P);
            }
        }
    }

    V()
    {
        atomically
        {
            if (!waitingProcesses.empty())
            {
                Process P = waitingProcesses.pop();
                WAKEUP(P);
            } else {
                value++;
            }
        }
    }
};

So what is going on here? This is the smart part, to solve the problem of concurrency, Dijkastra said, we have 1 critical section and we can symbolise its availability by an integer value , i.e. value = 1 means critical section is available and value = 0 means it is not available.

That sounds a lot like locks, so how is it better? The entire step of updation/blocking/wakeup happens atomically with no preemption. Every process is allowed to do 2 things:

• P(process): try (proberen) to take critical section by decreasing value
• V(): Increase (vergogen) value to show availability of the critical section.

This version of the Semaphore is called a Binary Semaphore the value can only hold 2 stated, 0 means critical section is occupied, 1 means critical section is free.

Counting Semaphore

But hold on, Dijkastra just created something more than an mechanism for the critical section problem!

He said that there is only 1 critical section so the value can only be 0 or 1 denoting the availability of the critical section. But why stop at one? Unbeknownst to him he created something much more powerful, something that can help control the access of multiple resources simultaneously while maintaining synchronisation.

Get Abhinit Tripathi’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Dijkastra’s colleague, Carel Scholten suggested an interesting use case of Dijkastra’s semaphores that can help processes utilise the availability of multiple resources.

Imagine you got 5 printers in an office and 100 documents waiting for you to print them. Will you go and print each document on a single printer? If 1 page takes 1 minutes you will be sitting there for 100 mintes while the other 4 printers are getting dust. No you would not want that!

You would want to utilise the 5 printers, printing 5 documents in one minute. So you only need to wait for 20 minutes….or u can write a program to do that using counting semaphores!

Instead of have value = 0 we can have value = 5 . this will tell us how many resources do we have left for allocation. since the tasks are independent we don’t really need mutual exclusion here, 5 printers can separately print their documents.

When one printer is taken we try and decrease the value using P() , similarly when a printer is free we can increase the value using V() .

Now value no longer represents if the critical section is free or not, it represents how many units of a particular resource are available.

value = 5

the first 5 processes can get the printer
P1 : value = 4
P2 : value = 3
P3 : value = 2
P4 : value = 2
P5 : value = 0

But P6 sees 0 printers available so it gets blocked in the waiting queue.

When a process runs V() then P6 is popped out of the queue andit takes
a printer.

Isn’t this awesome! Now maybe you can imagine using counting semaphores to model a pool of CPU cores! Modern operating systems don’t literally use counting semaphores to perform CPU scheduling but I hope you can see & appreciate the engineering intuition behind it.

In summary Binary Semaphores can be used when u want to handle race conditions and critical section or you have a single shared resource. On the contrary, if u have multiple resources that can be used independently by a finite number of processes us can manage them by using Counting Semaphores. The underlying idea remains the same, we are trying to control access to a finite number of resources.

Finally let us check if Semaphores are a solution or a mechanism, we will be considering Binary Semaphores as they are the one working on the critical section problem.

Semaphore S(1);

process()
{
    S.P();

    // CRITICAL SECTION

    S.V();
}

Mutual Exclusion
Say 2 processes want to enter the critical section P1 & P2. value = 1 . P1 gets to execute P() which will atomically reduce value tp 0 . Then P2 execute P() but now value == 0 so P2 will go in the waiting queue and will be blocked. So only a single process can enter the critical section.

Mutual Exclusion is satisfier

Progress
Suppose P1 finishes and executes V() , which again runs atomically and increases value to 1 and wakes up P1, now P1 resumes into the critical section.

Progress is satisfied

Bounded Waiting
In the above sample code, if a P1 is too interested it will execute the exit section by running V() so that will bring a waiting process right inside the critical section without incrementing the count. If P1 runs P() again, it will get blocked since value == 0 .

But does it prevent deadlocks? I will it for you to ponder.

Bounded Waiting is satisfied

Just like that…WE FINALLY HAVE IT!
We tried software solutions, brought in hardware, worked on generalisation, tried removing busy waiting using blocking.

Every solution fixed something….and broke something along the lines. But we finally arrived at semaphores!

An elegant abstract data type that can leverage blocking, scaler beyond two processes, coordinate and synchronise access to shared resources, and ensures mutual exclusion, progress and bounded waiting.

And that is the nature of engineering, here failiure is more important than success. One success comes from tons of failiures, they are an engineers best friend…doesn’t matter software or hardware.

Let us see what happens when use semaphores against the most famous synchronisation problems in OS.

EXXXCCEELLSSIIOOORR!!