Monday, February 09, 2009

Java synchronizers - Semaphore

Picture courtesy of matthewblack@flickr
In this part I will present good-old semaphore that was finally introduced in Java 5. Semaphores are applicable in many different cases. One of them is the case when you have limited number of resources that can be accessed at the same time (imagine that you have 5 printers and 100 employees who print their documents - possibly all at the same time). Users have to wait for their turn - however order in which they requested the resource is not important (someone can wait couple of turns while someone else can get the resource many times turn after turn).

The code below shows this "metaphor" with 3 printers and 5 employees:

public class SemaphoreTest {
public static void main(String[] args) throws InterruptedException {
Semaphore sem = new Semaphore(3);
Thread[] t = new Thread[5];

for (int i = 0; i < t.length; i++) {
t[i] = new Thread(new Task(sem));
t[i].start();
}

Thread.sleep(10000);

for (int i = 0; i < t.length; i++) {
t[i].interrupt();
}
}

private static final class Task implements Runnable {
private final Semaphore sem;

private Task(Semaphore sem) {
this.sem = sem;
}

@Override
public void run() {
try {
while (true) {
if (sem.tryAcquire() == true) {
System.out.printf("%s acquired semafore - %d\n", Thread.currentThread().getName(), sem.availablePermits());
sem.release();
} else {
System.out.printf("%s could not acquire semafore\n", Thread.currentThread().getName());
}
Thread.sleep(1000);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
}

The program above terminates automatically after about 10 seconds from start.

Results (one of the infinite number of possible results) on my machine:

Thread-0 acquired semafore - 1
Thread-3 could not acquire semafore
Thread-4 could not acquire semafore
Thread-2 could not acquire semafore
Thread-1 acquired semafore - 0
Thread-3 acquired semafore - 1
Thread-0 acquired semafore - 1
Thread-4 acquired semafore - 0
Thread-2 could not acquire semafore
Thread-1 acquired semafore - 0
Thread-0 acquired semafore - 1
Thread-3 acquired semafore - 0
Thread-2 acquired semafore - 1
...

As you can see each thread at some point acquires the semaphore and accesses requested resources. Be careful though because when the number of consumers/producers vastly outnumbers semaphore's permits starvation is very likely (i.e. some of the threads will never have an opportunity to enter the critical section). You can even spot it on the presented listing where Thread-2 cannot acquire semaphore twice while Thread-0 is "lucky" and always gets it.

2 comments:

Tiago Fernandez said...
This comment has been removed by the author.
Tiago Fernandez said...

For the starvation problem, maybe you could use the fairness feature:

Semaphore sem = new Semaphore(3, true);

But you would need to change the way you're acquiring the lock:

sem.tryAcquire(0, TimeUnit.SECONDS);

I didn't run your code, but according to Javadoc it should work :)