Semaphores explained -- A Java approch

Semaphore can be considered as a variable or Data Structure that can be used to archive mutual exclusion in a Parallel Programming environment.

One good real life example to explain this is the tablet mechanism that is used in old railway system. Where when a train enters a Train Station it need to get a tablet from the Station master to proceed to the next station. When the train get the tablet that means there will be no other train in the railway track till it reaches the next station. When The train arrived to the next station it must give back the tablet to the station master so that he can signal the station that train has come from that line is cleared now (line is clear )

So getting a tablet is like acquiring a lock in the train line so that other trains that are in need of acquiring the line need to wait till the train reaches the next station and release the lock ( give the tablet back).

This signal system still in use in Sri Lanken Railway line in some parts where there is only one rail track between two stations.

Above explained situation is an example for the Binary Semaphore. where it supports two operations up() and down() . A binary semaphore can have only two values 0 and 1 .(NOTE that up() , down() operations are atomic operations )

when someone call a up on semaphore if its value is 0 then it increment it to one and return so that execution can proceed. But if its value is 1 then that up call block the process execution till some one make the semaphore value to 0 (wait till a down call);

In a down call if semaphore value is 1 it decrement it can return. If its 0 then the down call will block the process execution till the semaphore value set to one (wait till a up call).

This little idea is extended to an idea called Counting Semaphores there we can have more than two values for the semaphore. So that process can call multiple up s /down s till it get blocked.Which means more that one thread can pass the through before it blocked.

Now its time to look in to how this going help to solve a mutual exclusion problem.

Following is a famous problem in Concurrent programming text books lets see how we can solve it.

Bill and Ben work in a cafe that specialises in a soup and sandwich combination.

Bill makes two rounds of sandwiches while, at the same time, Ben makes two bowls of soup. When the sandwiches and soup are ready Bill and Ben each, they serve a soup and sandwich combination to a customer. These actions are repeated throughout the day.

[Note: Bill cannot serve until Ben has made the soup and Ben cannot serve until Bill has made the sandwiches.]

So as the Problem explained Before Serving sandwiches and soup Bill and Ben need to sync up.

Which means there can be no two customers in the shop at any time that has only served one item.(soup/sandwich)

If we model Bill and Ben as two processes that executes parallely it must be like follows

process Bill {

while (true) {

// Bill makes sandwiches //

SYNCH 1;

// Bill delivers //

}

}

process Ben {

while (true) {

// Ben makes soup //

SYNCH 2;

// Ben delivers //

}

}

To implement this Processes I'll be using the Java Language. Java has inbuilt semaphore implementation in java.util.concurrent.Semaphore

Its a counting Semaphore implementation. For this case since we only need a binery semaphore I'll will use it with permit value 1. which means only 1 thread is permitted to acquire it at a time.

I'll use the operations acquire and release operations which are smiler to up and down operations .

First lets look in to the code.

import java.util.concurrent.Semaphore;

public class Cafe {
private  final Semaphore bill = new Semaphore(1);
private  final Semaphore ben = new Semaphore(1);


public static void main(String[] args) throws InterruptedException {
  //Cafe opening
  new Cafe().openCafe();
 // Cant keep it open for long time.... :D
 Thread.sleep(1000);
 System.exit(0);
}


private void openCafe () throws InterruptedException {
  // allocating them to the work
  bill.acquire();
  ben.acquire();


  Thread benProcess = new Thread(new Ben());
  Thread billProcess = new Thread(new Bill());
  //work started
  benProcess.start();
  billProcess.start();


}
class Bill implements Runnable {

  public void run() {
      int i=0;
      while(true) {
          System.out.println("[Bill] finished making 1 sandwitch");
          System.out.println("[Bill] finished making 2 sandwitchs");

          try {

              //bill says i m done
              bill.release();
              // bill wait till ben done
              ben.acquire();
          } catch (InterruptedException e) {
              System.out.println("Process interrupted....");
          }

          System.out.println("[Bill Serves...Sandwitch to customer "+ ++i+" ]");
      }
  }
}

class Ben implements Runnable {

  public void run() {
      int i=0;
      while(true) {
          System.out.println("[Ben] finished making 1 Soup");
          System.out.println("[Ben] finished making 2 Soup");

          try {

              // ben says i m done
              ben.release();
              // ben waits till bill done
              bill.acquire();
          } catch (InterruptedException e) {
              System.out.println("Process interrupted....");
          }

          System.out.println("[Ben Serves... Soup to Customer "+ ++i+"]");
      }
  }
}
}

So if we looked in to the code Bill and Ben are implemented as two runnable s . At the start We create a Cafe allocate Ben and Bob work and tell them to start work.

If we look in to Bill Process what it does is it creates two Sandwiches and tell that I, m done by releasing bill semaphore and waits till Ben finished by trying to acquire the ben semaphore.

And Ben does other way around.

So it guarantees that Ben cant serve till Bill finish and Bill cant till Ben finishes.

So at the end when the processors executing parallely the condition of there can be no two customers in the shop at any time that has only served one item.(soup/sandwich) is satisfied.

Following is sample console out put I got

[Ben] finished making 1 Soup
[Ben] finished making 2 Soup
[Bill] finished making 1 sandwitch
[Bill] finished making 2 sandwitchs
[Ben Serves... Soup to Customer 1]
[Ben] finished making 1 Soup
[Ben] finished making 2 Soup
[Bill Serves...Sandwitch to customer 1 ]
[Bill] finished making 1 sandwitch
[Bill] finished making 2 sandwitchs
[Ben Serves... Soup to Customer 2]
[Ben] finished making 1 Soup
[Ben] finished making 2 Soup
[Bill Serves...Sandwitch to customer 2 ]
[Bill] finished making 1 sandwitch
[Bill] finished making 2 sandwitchs
[Ben Serves... Soup to Customer 3]
[Ben] finished making 1 Soup
[Ben] finished making 2 Soup
[Bill Serves...Sandwitch to customer 3 ]

......... goes on


You can see the condition is satisfied.
Hope this helps to improve your understanding on Semaphores...