Skip to main content

Threads in Java - Semaphores (Part 11)

Semaphore is nothing but a variable which is used to achieve synchronization in processes. Let us understand the concept of semaphores with an example -
A(Semaphore s) {
        while (s == 0) ;
        s = s - 1;
    }

B(Semaphore s) {
        s = s + 1;
    }
Here, there are two operations A and B. Now these operations surround the critical section as below -

// Non-critical section
A(s);
// CRITICAL SECTION
B(s);
// Non-critical section

Let there are two processes X and Y and s is initialized to 1. Now, if X enters the critical section, A(s) will be called before this which will update the s to 0. Due to this, Y cannot enter the critical section unless s > 0 (The process will be stuck at while loop). The value of s will be 1 only if X completes its critical section and calls B(s). That way mutex is achieved. This is an example of Binary Semaphore as it can store only two values 0 and 1.

In case there are multiple instances of a resource, then we can initialize the semaphore to the value equal to the number of instances. For e.g., let's say a resource has three instances then we will initialize s = 3; Now, if there are three processes X, Y and Z, they will get each instance and value of s is decremented by 1 each time. Suppose if fourth process W comes, then it has to wait until one of the processes does not complete its execution of critical section. This is an example of Counting Semaphore.

Optimized approach

Whenever any process waits, it continuously checks the value of semaphore (in the while loop) which wastes a CPU cycle. To avoid this, we can use the below approach - 
A(Semaphore s) {
        s = s - 1;
        if (s < 0) {
            // Pushing process in the queue
            block();
        }
    }

B(Semaphore s) {
        s = s + 1;
        if (s >= 0) {
            // Popping process from the queue
            wakeup(p);
        }
    } 
Here, whenever a process waits, we put it in a queue (push). Once one process is completed, we signal the queue so that the next process can be executed (pop).

Semaphore in Java

As discussed in the previous sections, a Semaphore controls access to a shared resource using counter. 
  • If counter > 0 - Access is permitted
  • If counter = 0 - Access is denied.
The counter is counting the permits to access a shared resource. In short, in order to access a shared resource, a thread should have a permit.
  • If counter > 0, then the thread can have the permit to access the shared resource. Once, the permit is acquired, the count is decremented.
  • If counter = 0, the thread has to wait until a permit is acquired. 
  • Once the thread completes its execution, it releases the permit and the counter is incremented.
  • Now, the other thread can acquire the permit and performs its execution.

Code example

Java provides Semaphore class in java.util.concurrent package, so we do not have to implement our own semaphores.

We can use a semaphore to lock access to a resource. Thus, each thread that wants to access this resource must first call acquire() to acquire the lock and calls release() to release the lock. See below code (source: GeeksforGeeks)

Output

Executing: ThreadB
Executing: ThreadA
ThreadA is waiting for a permit.
ThreadA gets a permit.
ThreadB is waiting for a permit.
ThreadA: 1
ThreadA: 2
ThreadA: 3
ThreadA: 4
ThreadA: 5
ThreadA releases the permit.
ThreadB gets a permit.
ThreadB: 6
ThreadB: 7
ThreadB: 8
ThreadB: 9
ThreadB: 10
ThreadB releases the permit.
Final value of the shared resource: 10
Let us understand this program in steps -

  • We have two threads TheadA and ThreadB which are incrementing the value of the shared variable count. 
  • As you can see that, ThreadA acquires the lock and increments count by one in each for loop iteration. ThreadB has to wait until ThreadA releases the lock. 
  • Note that we are also calling Thread.sleep() just to prove that semaphore is providing synchronization. In normal scenarios, the call to sleep() will make the other thread to run. This doesn't happen in this case as the thread acquiring the permit has not released it yet causing the other thread to wait.

Conclusion

Congratulations!! 🙋 Semaphores and their applications with code example. You can see the API documentation of this class here. I hope you enjoyed this post.

You can find the complete code of this project on my GitHub in this commit. Feel free to fork or open issues, if any.

I would love to hear your thoughts on this and would like have suggestions from you to make it better. 

Feel free to befriend me on FacebookTwitter or Linked In or say Hi by email.

Happy Coding 😊

Comments

Popular posts from this blog

Threads in Java - Masterclass (Part 0)

Multithreading is a way to introduce concurrency in a program. In any case, if there are parallel paths in our program (parts which do not depend on the result from another part), we can make use of multithreading.
One should exploit this feature, especially with all these multiple core machines nowadays.

Below are a few reasons why we should use multithreading -
1. Keep a process responsive There was once a time when you would print a document in MS Word and the application would freeze for an annoyingly long amount of time until the job finished. Eventually, Microsoft solved this problem by running a printing job parallel to the main thread/ GUI thread.  To be clear though, not only GUI apps but Network services have to keep an ear to the ground for new clients, dropped connections and cancellation requests. In either case, it is critical to do the heavy lifting on a secondary thread to keep the user satisfied. 2. Keep a processor busy Keeping a processor busy can be a tough task e…

Parsing XML using Retrofit

Developing our own type-safe HTTP library to interface with a REST API can be a real pain as we have to handle many aspects -
making connectionscachingretrying failed requeststhreadingresponse parsingerror handling, and more.  Retrofit, on the other hand, is a well-planned, documented and tested library that will save you a lot of precious time and headaches. In this tutorial, we are going to discuss how we can parse the XML response returned from https://timesofindia.indiatimes.com/rssfeedstopstories.cms using the Retrofit library.

To work with Retrofit, we need three classes -  Model class to map the JSON dataInterfaces which defines the possible HTTP operationsRetrofit.Builder class - Instance which uses the interface and the Builder API which allows defining the URL endpoint for the HTTP operation. Every method of the above interface represents on possible API call. The request type is specified by using appropriate annotations (GET, POST). The response is returned as a Call object…

Material design profile page in Android

Hey everyone, some days back I was working on one my personal Android project. In that project, I was supposed to create a simple profile page for a user. This profile page was supposed to show some basic details of a user.

The output of this UI will be like this -
I created the profile page using material design and in this post, I am going to discuss a step by step tutorial to create a simple yet elegant profile page. Without further ado, let's get started.
Creating a new project Click on File ➤ New Project ➤ Empty Activity and fill the necessary details. Change styles.xml fileNavigate to app\src\main\res\values\styles.xmlChange the style value from DarkActionBar to NoActionBar as below<resources><!-- Base application theme. --><stylename="AppTheme"parent="Theme.AppCompat.Light.NoActionBar"><!-- Customize your theme here. --><itemname="colorPrimary">@color/colorPrimary</item><itemname="colorPrimaryDark&qu…