Semaphores Using Java

Last modified on October 17th, 2014 by Joe.

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.

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.

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”.

Comments on "Semaphores Using Java"

  1. Chetan Jadhav says:

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

  2. igor says:

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

  3. Tena says:

    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

  4. Joe says:

    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. Tarsi says:

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

  6. Deepak Kumar Shrivastava says:

    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. VckReddy says:

    Nice explannation on Semaphore with Example.

  8. jerry says:

    Very nice blog,
    Congratulation Joe!

  9. harish says:

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

  10. cndhu says:

    Hi Joe,

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

  11. Anonymous says:

    Hi joe,
    Nicely Explained.

  12. rama says:

    i want explanation about barber shop problem using semaphore

  13. vidyasagar says:

    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).

  14. RAHUL DEB BARMAN says:

    SO GOOD THANKS JOE SIR

  15. E.Prakash says:

    Hi Joe ,

    Really Execellant Information , Thanks a lots for crating Blogs

  16. Asraful says:

    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.

  17. karthik says:

    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.

  18. ravi krishnarpan says:

    Sublime article

  19. Amel says:

    nice really helpful ,thank you.

  20. kalai says:

    Great explanations for wonderful concepts….

  21. kalai says:

    Explantions are So Good…

  22. Swapnil Phatkar says:

    nice explained.

  23. M.fathima sanjas says:

    it was really helpful..
    thank u sir…

  24. eswaramoorthy.s says:

    sir can you please explain this program

  25. Goutam says:

    Very clearly and simply explained. Thanks Joe.

  26. Concerned says:

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

  27. Sagar says:

    Nice explanation….

  28. J says:

    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.

  29. Candice says:

    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.

  30. Ashok says:

    nice explanation.

  31. Prabhu R Babu says:

    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

  32. alok says:

    I didnt understood this program. Can Anyone please give step by step explaination for this

Comments are closed for "Semaphores Using Java".