Semaphores Using Java

Semaphore is an interesting topic in operating systems and it can be used in a variety of ways to solve challenging problems.

In this article I will explain,

  1. what is a semaphore
  2. how to implement a semaphore in java
  3. an example problem and solution implementation using semaphore.

Following is a challenging programming problem we have in computers masters degree.

Example Problem

Assume there are three processes: Pa, Pb, and Pc. Only Pa can output the letter A, Pb B, and Pc C.
Utilizing only semaphores (and no other variables) the processes are synchronized so that the output satisfies the following conditions:

a) A B must be output before any C’s can be output.
b) B’s and C’s must alternate in the output string, that is, after the first B is output, another B cannot be output until a C is output. Similarly, once a C is output, another C cannot be output until a B is output.
c) The total number of B’s and C’s which have been output at any given point in the output string cannot exceed the number of A’s which have been output up to that point.

Now, just close your eyes and imagine of a solution to this problem. There are different solutions available, just using a constraint solver this can be solved.

This difficult problem can be solved very easily using semaphore’s locking mechanism. Before diving into the solution,

What is a Semaphore

Semaphore is a word coined from ancient Greek words (sêma, phoros) meaning ‘sign, bearing/bearer’.

Semaphore is a technique used to control access to common resource for competeing multiple processes. Semaphore maintains a counter which keeps track of the number of resources available. When a process requests access to resource, semaphore checks the variable count and if it is less than total count then grants access and subsequently reduces the available count.

Semaphore is just a gatekeeper guarding the resources. If available grants access and otherwise asks the processes to wait.

Ads by Google

  • When the resource count is arbitrary then this is called counting semaphore.
  • If resource count is only one and the state value is restricted to on/off, then it is called binary semaphore. This is slightly different from mutex.

Counting Semaphore Implementation in Java

package com.javapapers.thread;

public class CountingSemaphore {
	private int value = 0;
	private int waitCount = 0;
	private int notifyCount = 0;

	public CountingSemaphore(int initial) {
		if (initial > 0) {
			value = initial;
		}
	}

	public synchronized void waitForNotify() {
		if (value <= waitCount) {
			waitCount++;
			try {
				do {
					wait();
				} while (notifyCount == 0);
			} catch (InterruptedException e) {
				notify();
			} finally {
				waitCount--;
			}
			notifyCount--;
		}
		value--;
	}

	public synchronized void notifyToWakeup() {
		value++;
		if (waitCount > notifyCount) {
			notifyCount++;
			notify();
		}
	}
}

This is an implementation of a counting semaphore. It maintains counter variables ‘value’, ‘waitCount’ and ‘notifyCount’. This makes the thread to wait if value is lesser than waitCount and notifyCount is empty.

Binary Semaphore Implementation in Java

package com.javapapers.thread;

public class BinarySemaphore {
	private boolean locked = false;

	BinarySemaphore(int initial) {
		locked = (initial == 0);
	}

	public synchronized void waitForNotify() throws InterruptedException {
		while (locked) {
			wait();
		}
		locked = true;
	}

	public synchronized void notifyToWakeup() {
		if (locked) {
			notify();
		}
		locked = false;
	}
}

Binary semaphore just acts as an on or off switch. It maintains a boolean lock and on state of the lock it waits or notifies.

Solution to the Problem

package com.javapapers.thread;

import java.util.Random;

public class SemaphoreABC {
	protected static final BinarySemaphore binarySemaphore0 = new BinarySemaphore(
			0);
	protected static final BinarySemaphore binarySemaphore1 = new BinarySemaphore(
			1);
	protected static final CountingSemaphore countingSemaphore = new CountingSemaphore(
			0);

	protected static final Random random = new Random();

	public static void main(String args[]) throws InterruptedException {
		new Thread(new ProcessA()).start();
		new Thread(new ProcessB()).start();
		new Thread(new ProcessC()).start();
		Thread.sleep(9000);
		System.exit(0);
	}
}
package com.javapapers.thread;

public class ProcessA extends SemaphoreABC implements Runnable {
	public void run() {
		while (true) {
			try {
				Thread.sleep(1 + (int) (random.nextDouble() * 500));
			} catch (InterruptedException e1) {
				e1.printStackTrace();
			}
			System.out.print("A");
			countingSemaphore.notifyToWakeup();
		}
	}
}
package com.javapapers.thread;

public class ProcessB extends SemaphoreABC implements Runnable {
	public void run() {
		while (true) {
			try {
				Thread.sleep(1 + (int) (random.nextDouble() * 800));
				binarySemaphore1.waitForNotify();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			countingSemaphore.waitForNotify();
			System.out.print("B");
			binarySemaphore0.notifyToWakeup();
		}
	}
}
package com.javapapers.thread;

public class ProcessC extends SemaphoreABC implements Runnable {
	public void run() {
		while (true) {
			try {
				Thread.sleep(1 + (int) (random.nextDouble() * 800));
				binarySemaphore0.waitForNotify();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			countingSemaphore.waitForNotify();
			System.out.print("C");
			binarySemaphore1.notifyToWakeup();
		}
	}
}
Output: AABCABACAABCAABCAAABCABCABACAABCABACABACABACABAC

In solution to the problem, we have used both counting semaphore and binary semaphore.

  • Condition b) is met with using the binary semaphore binarySemaphore0 and binarySemaphore1. These two act as alternate switches to the thread and allows for printing.
  • Condition c) is met with using the counting semaphore. Both processB and processC calls waitForNotify and processA calls notifyToWakeup indicating that it has printed ‘A’, thus ensuring the total count of ‘A’ to be always larger than ‘B’,’C’ together.
  • We have used a random number generator in three processes to create requests at random interval. Thread.sleep(6000) allows the overall program to run for 6 secs. If you want to see this run for longer duration, increase this number accordingly.

Java has its own implementation of counting semaphore refer API java.util.concurrent.Semaphore

Thank you, hope you have enjoyed reading this article.


This is a guest article from Vincy. She was a software engineer and left her fulltime job to pursue higher studies. Presently a student of masters computer science (ME Computer Science) and loves programming using php. You can reach her at giftvincy@gmail.com


I have been getting requests for contribution to javapapers for quite sometime now. Sure I want to give authors chance to share their knowledge using javapapers as a platform but didn’t want to compromise on the style and quality I have built over a period. Vincy is my wife and happy to have her article as first guest article for javapapers.

Get in touch with me if you wish to publish an article but there are two conditions,

  1. I have a style of writing and its presenting technology in its simplest form and my readers love it. I will be editing your article ‘heavily’ to bring it to my own style.
  2. Your article will be licensed under “creative commons cc-share with required attribution”.

This Core Java tutorial was added on 26/02/2012.

previous post: Eclipse Shortcuts

next post: Soap Web Service – Introduction

33 comments on “Semaphores Using Java

  1. Semaphores Concept explained in Plain and Simple way..!!!

  2. What’s the point in re-inventing the weel? What’s wrong with standard java.util.concurrent.Semaphore?

  3. Igor, I think that Joe is just explaining the way semaphores work, not re-implementing the standard at all by 2 simple classes.

    Very well explained Joe, another way to do it is by an example of few instances using the same object concurrently. And just for adding my 2 cents, another way to solve this kind of problems is by using monitors or messages!

    congrats

    • Yes, but he could explain using standard classes. Creating your own is very much reinventing the wheel – and confusing for new learners.

  4. Igor, just trying to explain what a semaphore is. At the end of the article I have even referred java’s semaphore class.

    Tena, thanks. I haven’t tried using monitors/messages, thats a nice idea. Let me try that out.

  5. Nicely Explained.
    I love to read your articles.
    Can you please explain annotations as well?

  6. Hi Joe.

    I am PG student. I really get benifited by your Papers.

    I need your help.
    Please help me.

    I what brief difference between throw,throws and throwable.

    please help any one, if good difference u have.

  7. My e-mail id is Deepakmkumca10@gmail.com

    I love java blogs and like to read about more and more about java.

    Please any one help me! about

    Difference between throw, throws and throwable?

  8. Nice explannation on Semaphore with Example.

  9. it is not clear for me, can u please explore in detail

  10. Hi Joe,

    Thank you.
    Please explain difference between cohesion and coupling in your way. This is my third request

  11. i want explanation about barber shop problem using semaphore

  12. Hi Joe,
    Thanks for nice explanation. I wish someday you will write on Data structures in java. It will be a lot helpful for lots of people. Some of those you have already covered.If possible please write on creation of a data structure without importing any libraries(except java.lang.* which is default).

  13. Hi Joe ,

    Really Execellant Information , Thanks a lots for crating Blogs

  14. I already read 6-7 article from this site. Will go through to others. Subscribed already via e-mail. The way of writing is too simple but highly easy to understand complex concept like this one and JVM hook. Keep on.

  15. Hi Joe,

    I want use this semaphore in my jsp to limit how many users can see registration page (Like 10 users ) …and after that users will get in a Queue ..so that my website performance is not hit.

  16. Oh thats a nice tutorial.

    Good job sir.

    Thank you so much.

  17. it was really helpful..
    thank u sir…

  18. sir can you please explain this program

  19. Very clearly and simply explained. Thanks Joe.

  20. Sorry, I’m looking for an explanation of java.util.concurrent.Semaphore. I’ve got enough to learn without trying to get my head around a 3rd party reinvention of the wheel.

  21. Thank you so much for this! Everything else I find is for using the built in Semaphore, and that isn’t allowed in my assignment. I love the full code, it’s so helpful when you are brand new to java. I look forward to viewing the rest of your tutorials.

  22. Hi Joe,

    Its a very good article. but why in the method WaitForNotify(), we call notify() in the catch block of InterruptedException. Also, when interruptedException happens, we should not decrement notifyCount. I think we should replace “notify()” with notifyCount++. Let me know what you think

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>