Semaphores are an "old school" synchronization primitive that you still encounter from time to time. The Linux kernel, for example, frequently uses semaphores for managing concurrency.
A semaphore represents a thread-safe integer with methods for incrementing and decrementing its value (up and down, respectively). In addition, any attempt to decrement the semaphore below zero will cause the decrementing thread to block. Incrementing the semaphore causes a single sleeping thread to awaken. You can read more about semaphores in Silbershatz section 6.5 (note that the author refers to "up" and "down" as "signal" and "wait"). Also, Java has a built-in semaphore, and the documentation has a useful example (again, with different method names; everybody has to be different...). Note that a semaphore initilized to 1 behaves much like a lock; Linux frequently uses such degenerate semaphores instead of a special lock type.
Semaphores and condition variables have some similarities: they both provide a way to block and unblock threads subject to certain conditions. In this assignment, you first implement a semaphore using a condition variable. Then, you will reverese the process by replacing a condition variable with a semaphore.
For this homework, we do not care if your code has perfect syntax. For example, you can omit declarations such as "throws InterruptedException". The crucial thing is to get the synchronization right: your code must grab the right looks, and use condition variables as appropriate.
The following code snippet provides the interface for a semaphore. Your task is to implement the constructor, the down method, and the up method. You can (and should) use a condition variable to implement thread blocking and wakeup. Clearly, your implementation should be thread-safe. It should also be starvation free: all threads should make progress, assuming that up is called more often than down. This page contains a link to this code and a simple test routine.
public class Semaphore {
public Semaphore (int initialValue) {
// TODO: Implement this
}
// initialize a sempahore with value zero
public Semaphore () {
this(0);
}
public void down () {
// TODO: Implement this!
}
public void up () {
// TODO: Implement this!
}
}
In class, we looked at a BufferPool, which provides a thread-safe repository for a set of data buffers. When the pool is empty, any attempt to acquire a buffer will block. This blocking is implemented using a condition variable. When a buffer is returned to the pool, a single blocked thread is awoken. The source code for the BufferPool is provided here.
Your task is to re-write the BufferPool to use semaphore(s) instead of a condition variable. Your new version should behave the same as the current version. You can assume the existence of a Semaphore class, with the same interface as above. The Semaphore is correctly written (i.e., it uses sufficient synchronization to ensure thread-safety). Your new implementation cannot directly use a condition variable. In other words, the words “wait” and “notify” should not appear in your solution.
(Of course, the Semaphore might be implemented with a condition variable. The implementation details of the Semaphore do not matter for this problem).
From the textbook, Do Silbershatz 5.4 and 5.10