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.

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