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.

«

»

Comments on "Semaphores Using Java"

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

  2. Ashok says:

    nice explanation.

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

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

  5. Sagar says:

    Nice explanation….

  6. Goutam says:

    Very clearly and simply explained. Thanks Joe.

  7. eswaramoorthy.s says:

    sir can you please explain this program

  8. M.fathima sanjas says:

    it was really helpful..
    thank u sir…

  9. Swapnil Phatkar says:

    nice explained.

  10. kalai says:

    Explantions are So Good…

  11. kalai says:

    Great explanations for wonderful concepts….

  12. Amel says:

    nice really helpful ,thank you.

  13. Rudhin says:

    Oh thats a nice tutorial.

    Good job sir.

    Thank you so much.

  14. ravi krishnarpan says:

    Sublime article

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

  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. E.Prakash says:

    Hi Joe ,

    Really Execellant Information , Thanks a lots for crating Blogs

  18. RAHUL DEB BARMAN says:

    SO GOOD THANKS JOE SIR

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

  20. rama says:

    i want explanation about barber shop problem using semaphore

  21. Anonymous says:

    Hi joe,
    Nicely Explained.

  22. cndhu says:

    Hi Joe,

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

  23. harish says:

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

  24. jerry says:

    Very nice blog,
    Congratulation Joe!

  25. VckReddy says:

    Nice explannation on Semaphore with Example.

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

  27. Tarsi says:

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

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

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

    • Concerned says:

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

  30. igor says:

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

  31. Chetan Jadhav says:

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

Your Comment