Semaphore: Mutual Exclusion in Single System

29 Mar 2011 by

Semaphore

Semaphore

Mutual Exclusion is required both in single system and distributed systems to protecting the shared resource from being modified concurrently. In this article, we will discuss the mutual exclusion in single system by using Semaphore. Finally we will follow by giving Java example. Before reading this article, it is highly recommended you read the Principle of Mutual Exclusion.

Semaphore

Semaphore is a flag that railroad engineers would use when trains enter a shared track. Semaphore here refers to a mechanism to ensure only one thread or process to access a shared resource. To implement semaphore in Java, synchronized(this) keyword should be used to surround critical section. The code from previous article will look like this.

Global variables

int x = 6;
int y = 0;

FooThread

void foo(){
  synchronized(this){
    x++;
    y = x;
  }
}

BarThread

void bar(){
  synchronized(this){
    y++;
    x += 3;
  }
}

Problem in Semaphore

The results from this example have only 2 options:

  • x = 10 and y = 8 if foo() runs first
  • x = 10 and y = 10 if bar() runs first

Semaphore can ensure only one thread can access a resource at the same time. However, it cannot guarantee there is only single flow that can modify variable x and y. It means that we are not sure whether foo() runs first or bar() otherwise.

Condition Variable

To solve the problem above, Condition Variable must be used. In general conditional variables are known as event. A condition variable notifies threads that a particular condition has been met. It is used to signify from one thread to another that some events are taken place.

In Java, there are wait(), notify() and notifyAll() to help condition variable.

By using condition variable we can design a specific flow. For example, we want foo() runs before bar().

Global variables

int x = 6;
int y = 0;
boolean fooDone = false;

FooThread

  public void foo(){
    synchronized(this){
      x++;
      y=x;
      fooDone = true;
      notify();
    }
  }

BarThread

  public void bar(){
    synchronized(this){
      if(!fooDone){
        try{
          wait();
        }catch(InterruptedException ie){
          ie.printStackTrace();
        }
      }
      y++;
      x+=3;
    }
  }

After applying condition variable and assuming foo() runs before bar(). So the result is only one choice. x = 10 and y = 8;
So now you are clear how semaphore and condition variable help to achieve mutual exclusion.

For the full Java source code and detail in using monitor will be posted in the next article.

2 responses so far

Leave a Reply