Semaphores

For the java.util class see Semaphore
Wikipedia [1] defines semaphore as a protected variable that is used for restricting access to shared resources in a multiprogramming environment.

First we will define a general interface for the Semaphore classes.

public interface Semaphore
{
    /*
     * Dijkstra used P and V original (in dutch) to describe semaphores
     * P: prolaag (try-and-decrease)
     * V : verhoog (increase) 
     */
    public  void P(); //down 
    public  void V(); // up 
}

Three different implementations of Semaphores.

  • Semaphore1
//A simplified version of the semaphore implementation
class Semaphore1 implements Semaphore
{

    protected int value = 0;

    public Semaphore1()
    {
        value = 0;
    }

    public Semaphore1(int initial)
    {
        value = initial;
    }

    public synchronized void P()
    {
        value--;
        if (value < 0)
            try
            {
                wait();
            } catch (InterruptedException e)
            {
            }
    }

    public synchronized void V()
    {
        value++;
        if (value <= 0)
            notify();
    }

}
  • Semaphore2
/*
 * Version using wait and notify for suspending and reawaking threads
 */
class Semaphore2 implements Semaphore
{
 
    private int value;
 
    private int waiting = 0; // number of threads waiting
 
    public Semaphore2()
    {
        value = 0;
    }
 
    public Semaphore2(int initial)
    {
        value = initial;
    }
 
    public synchronized void P()
    {
        if(value > 0) value--;
        else
        {
            waiting++;
            try
            {
                wait();
            }
            catch(InterruptedException e)
            {
 
            }
            waiting--;
        }
 
    }
 
    public synchronized void V()
    {
        if(waiting == 0) value++;
        else notify();
    }
 
}
  • Semaphore3
/*
 * An implementation of a general semaphore.
 * a while(condition) { ... wait() ...} loop is used 
 * to suspend the process invoking a P(). 
 */
class Semaphore3 implements Semaphore
{
 
    protected int value;
 
    public Semaphore3(int initial)
    {
        value = initial;
    }
 
    public synchronized void P()
    {
        while (value <= 0)
        {
            try
            {
                wait();
            } catch (InterruptedException ex)
            {
 
            }
            value--;
        }
    }
 
    public synchronized void V()
    {
        value++;
        notify();
    }
 
}

Lastly, the Process class for testing the three different implementations of semaphores

//Solving the mutual exclusion problem using a semaphore
 
class Process extends Thread
{
 
    private int id;
 
    private Semaphore sem;
 
    public Process(int i, Semaphore s)
    {
        id = i;
        sem = s;
    }
 
    private int random(int n)
    {
        return (int) Math.round(n * Math.random() - 0.5);
    }
 
    private void busy()
    {
        try
        {
            sleep(random(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void noncritical()
    {
        System.out.println("Thread " + id + " is NON critical");
        busy();
    }
 
    private void critical()
    {
        System.out.println("Thread " + id + " entering critical section");
        busy();
        System.out.println("Thread " + id + " leaving critical section");
    }
 
    public void run()
    {
        for (int i = 0; i < 2; ++i)
        {
            noncritical();
            sem.P();
            critical();
            sem.V();
        } 
    }
 
    public static void main(String[] args)
    {
        final int N = 4;
 
        System.out.println("Busy waiting...");
 
        Semaphore sem = new Semaphore1(1);
        //Semaphore sem = new Semaphore2(1);
        //Semaphore sem = new Semaphore3(1);
        Process p[] = new Process[N];
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Process(i, sem);
            p[i].start();
        }
    }
}
Bibliography
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.