Synchronization primitives: Mutex and Semaphore (Explanation for Semaphore) - Article 5

Hi Folks,

In the previous article, we saw what is Mutex or Mutual Exclusion. If critical section code is thought of as a single resource, only one thread will be allowed to use that resource.

In this article, we shall see what is a semaphore and the solutions to few synchronization problems using the semaphore.

A semaphore is very simple and easy to understand but it can solve complex synchronization problems. It is just a integer variable that can be initialized to any integer value (Usually non-negative: >= 0). After that, it is shared by the threads (Or processes).

After initialization, only two operations can be performed on the semaphore: Decrement and Increment.

The pseudo code of usage is as below:

Semaphore MySem;
MySem = 3;

// Share MySem between n threads say 10 threads

Thread 1:

// Some code here
MySem.Increment(); // MySem++
// Some more code here
MySem.Decrement(); // MySem--

Thread 2:

// Some code here
MySem.Decrement(); // MySem --
// Some more code here

For example: You have 3 printers and you want to synchronize access to it. Hence, initialize MySem to number of resources which is 3. Such a semaphore is called a counting semaphore, which keeps track of or counts the number of resources. If you have only 1 resource, initialize semaphore to 1. It's as simple as this (Such a semaphore is called binary semaphore).

NOTE 1: In the perspective of Linux and POSIX standards, Mutex and Binary semaphore are entirely different concepts.

NOTE 2: The distinction between Binary semaphore and Counting semaphore is made for human understanding purpose only. Internally, there is no difference from the perspective of implementation with in computers.

NOTE 3: There are many operating systems, RTOSes, etc out there in the market which may implement Mutex and Binary semaphore using same code or some hardware specific optimized CPU instructions. Hence, they may say Mutex and Binary semaphore are same.

NOTE 4: The increment and decrement operations on Semaphore variable are guaranteed to be atomic and race conditions will not occur, else synchronization of synchronization of synchronization of... may go infinitely.

To summarize, Semaphore is just a integer initialized to the number of resources and later controlled using increment and decrement.

So far so good? Now what does increment and decrement actually mean? What do threads (Or processes) actually do with that?

DECREMENT: Thread 1 says "I want to use 1 of the available 3 printer resources and I am taking 1 of them. Hence, now the number of available printers is 2".

Psuedo code:

Thread 1:

Semaphore Printers = 3;

Semaphore.Decrement() {
    while Printers <= 0, wait for at least one printer to be available; // DO NOTHING
    // Some other thread might have released one
    Printers--; // TAKE ONE
}

WAIT is same as DECREMENT. WAIT is also called as DECREMENT. i.e., a thread may have to WAIT for one of the resources to be free and then DECREMENT the number of resources and then use it.

INCREMENT: Thread 2 says "I am done with using the printer already acquired before. Hence, I am incrementing and informing that at least 1 resource is available now".

Psuedo code:

Thread 2:

Semaphore.Increment() {
    Printers++; // No need to wait for giving away
}

Let me end this article with a real world example: Similar things happen with humans. Whenever you go to a very famous restaurant and the number of tables are limited, you have to WAIT for atleast one of the tables.

After taking that table, you have your favorite meal, enjoy it slowly, and then you just leave (INCREMENT) for others to take it.

For taking something precious, you have to WAIT, but you can give something immediately, there will be takers.