Overview

Semaphores are one of the two tradtional ways of synchronizing multiple processes (threads) -- the other is monitors. Java intrinsically includes monitors which restrict critical sections of code to only one thread at a time. However, there are many more complex problems, some of which can be better solved with semaphores. A semaphore is a method for signalling threads and is often used for acquiring and releasing access to resources. A thread waits on access to a resource or for a signal and releases a resource by signaling completion.

Benefits

Iviz semaphores, in particular, implement counting semaphores that ensure that requests are granted in the order received. Key functionality includes:

Queue waiting processes in order to guarantee they are served first-come first-served.
Count waits and signals to enable flexible control of resources.
Are timed to prevent endless waiting.
Are interruptable to create sophisticated asynchronous control.
Have extensive API methods to provide programming easy and power.

iViz Semaphores are available as binary semaphore.jar and source code that is provided under the GPL. All the code, source and documentation is in the downloadable archive. The package is "com.iviz.semaphore". The code and documentation does not come with any guarantee or warranty for any purpose.

Operation

Counting semaphores define a count of the number of "free passes" and a queue for waiting threads. If a thread attempts to wait on the semaphore, and there are free counts, the count is decremented and the thread proceeds. If the count reaches zero, further threads will block until it is signalled.

Alternatively, when a thread signals a semaphore, the next waiting thread proceeds. If no threads are waiting, the count is incremented, which will allow some future thread to proceed.

When semaphores are used as a lock to guard a critical section, the initial count is set to "1" to permit only one thread access at any time. The critical section is wrapped with a guard.wait (); and guard.signal ();. The first "wait" will succeed and others will block until the thread reaches the second, which lets the next one go. If no thread is waiting, the semaphore remains open until the next one comes through. This use of a semaphore is a bit simple, and better implemented by a plain Java monitor.

Some excellent descriptions of semaphores and how they are used are available at: Java World, Oswego Univ, and Developer Central. Of course, if you're working with threads there are some great books: Java Thread Programming and O'Reilly's Java Threads

Basic API

The semaphore API provides the following basic operations (plus more advaced ones--see the javadocs.)

semaphore.swaitNoInterrupt () -- Ordinary wait for signal. Ignore all interrupts and wait indefinately
semaphore.swaitNoInterrupt (long ms) -- Wait for signal, ignoring all interrupts, but throw an exception after ms milleseconds.
semaphore.swait () -- Wait indefinately for signal, but throw exception on interrupt.
semaphore.swait (long ms) -- wait ms milleseconds for a signal. Throw exception on timeout or on interrupt
semaphore.signal () -- Alert next waiting thread to start
semaphore.interrupt () -- Throw an exception on all interruptible waiting threads

Example--Reader Writer

The reader-writer synchronization problem describes typical database access in which there are many threads attempting to read and write to the database and the constraints that must be enforced are:

Only K readers may read at the same time
Only 1 writer may write at any time
No readers may read when a writer is writing
Writers must not be wait endlessly for an opportunity.

The example code includes a solution to the reader-writer problem solved with semaphores. In addition, it can be used to test the semaphore code to be correct.

The algorithm used is:

    Reader                     Writer
Wait on QueueSem            Wait on QueueSem       <- Enables fairness
Wait on ReadSem             Wait on WriteSem       <- Enforces rule 1 & 2
  if first reader,                                 <- Rule 3
    wait on WriteSem                    
Signal QueueSem             Signal QueueSem        <- Maximise throughput          
 
  Critical Section          Critical Section

  if last reader,
    signal WriteSem                                <- Enables fairness
Signal ReadSem              Signal WriteSem        <- Signal done

The example takes a number of command-line parameters

	-nreaders #	Number of threads trying to read.
	-nwriters #	Number of threads.
	-nreads #	Number of times each thread should read.
	-nwrites #	Number of times each thread should write.
	-maxreaders #	Max number of simultaneous reads.
	-readms #	Number of milleseconds to wait for read. Used for testing JVM behavior
	-writems #	Number of milleseconds to wait for write. Used for testing JVM behavior
	-showtrace	When present, show trace of semaphores. Used to trace deadlock.
	-showcriticals	When present, show threads in critical sections. Used to ensure reading and writing interwoven.
	-yield	Make threads yield after critical section. Used for testing JVM behavior.

The first parameters control how many threads and how many reads (or writes) each thread does. This enables the semaphores to be stress tested for hundreds of threads and for special combinations, such as only readers, single reader, many writers, etc.

The readms, writems, yield parameters are used to determine how the JVM behaves. Some JVM are greedy and do not let some threads start (to even wait) before others have a big time slice. By inserting yields and delays it is possible to produce different JVM behavior.

Caveat

Although the basic signal/wait mechanism has been heavily tested with SUn's JVM 1.3.1_01a and 1.2.2., there is no guarantee that it will function correctly with whichever version of the JVM you happen to be using. Furthermore, the underlying operating system may exhibit perverse synchronization behavior. It is virtually impossible to test real-time synchronization code. If you have problems with this module, let us know, although there is no expectation that we will be able to diagnose or repair the code.

There is a known bug in the non-interruptable wait methods during which a signal may be missed in the time between when an interrupt occurs and a succeeding signal.