Dining Philosophers

Comments Off on Dining Philosophers

Dining Philosophers is one of those classical problems to understand (and resolve) deadlocks in software. Lets look at examples were we cause deadlocks, come up with a solution to avoid deadlocks and finally come up with a solution to avoid starvation. Also, here is a great link describing many more ways to solving the Dining Philosophers problem.

Here is a simple class to represent a fork on the table.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Fork {
 int forkid;
 Semaphore mutex=new Semaphore(1, true);
 public Fork(int forkid) {
    this.forkid = forkid;
  }
  public String toString() {
    return String.valueOf(forkid);
  }
  public void pickUpFork() throws InterruptedException {
    mutex.acquire();
  }
  public void putDownFork() {
    mutex.release();
  }
}

Deadlock Philosopher
This guy blindly picks up the left fork and then the right fork. We create a circular wait condition. Imagine scenario where all philosophers have a left fork and waiting for the right fork.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class DeadlockPhilosopher implements Philosopher {
 String philosopher;
 Fork left;
 Fork right;
 public DeadlockPhilosopher(String philosopher, Fork left, Fork right) {
  this.philosopher = philosopher;
  this.left = left;
  this.right = right;
 }
 @Override
 public void run() {  
  while( true ) {   
   try {    
    left.pickUpFork();
    System.out.println(philosopher + " picked up " + left);
    Thread.sleep(5000); // this will just cause the deadlock quicker!  
    right.pickUpFork();
    System.out.println(philosopher + " picked up " + right);
    System.out.println(philosopher + " is eating...");
    right.putDownFork();
    System.out.println(philosopher + " put down " + right);
    left.putDownFork();
    System.out.println(philosopher + " put down " + left);   
    System.out.println(philosopher + " is thinking...");
    Thread.sleep(5000); // think!   
   } catch (InterruptedException e1) {
    // TODO Auto-generated catch block
    e1.printStackTrace();
   }   
  }
 }
 @Override
 public String getPhilosopher() {
  return philosopher;
 }
}

2. Sensible Philosopher (No deadlocks)
Ok how do we break deadlocks? We get rid of the circular wait condition. We give forks (or resources) numbers. We make sure that philosophers access lowered numbered resources over higher numbered resources. In this solution all philosophers are right handed except E who is left handed. That’s enough to break the circular wait. Another solution could also be to make two adjacent philosophers request forks in different orders (i.e. make them right handed and left handed). The 5th and the 1st philosopher will be same handed however other philosopher being different handed, the circular wait will be broken.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class OrderlyPhilosopher implements Philosopher {
 
  String philosopher;
  Fork left;
  Fork right;
 
  public OrderlyPhilosopher(String philosopher, Fork left, Fork right) {
    this.philosopher = philosopher;
    this.left = left;
    this.right = right;
  }
 
  @Override
  public void run() {
 
    while( true ) {
 
      try {
 
        Fork pickUpFirst = null;
        Fork pickUpSecond = null;
 
        if ( left.forkid < right.forkid ) {
          pickUpFirst = left;
          pickUpSecond = right;
        } else {
          pickUpFirst = right;
          pickUpSecond = left;
        }
 
        pickUpFirst.pickUpFork();
        System.out.println(philosopher + " picked up " + pickUpFirst);
        Thread.sleep(5000);  // this will just cause the deadlock quicker!
        pickUpSecond.pickUpFork();
        System.out.println(philosopher + " picked up " + pickUpSecond);
        System.out.println(philosopher + " is eating...");
        pickUpSecond.putDownFork();
        System.out.println(philosopher + " put down " + pickUpSecond);
        pickUpFirst.putDownFork();
        System.out.println(philosopher + " put down " + pickUpFirst);      
        System.out.println(philosopher + " is thinking...");
        Thread.sleep(5000);  // think!
 
      } catch (InterruptedException e1) {
        // TODO Auto-generated catch block
        e1.printStackTrace();
      }
 
    }
 
  }
 
  @Override
  public String getPhilosopher() {
    return philosopher;
  }
}

3. Fair Philosopher (No deadlocks, No Starvation, Average Performance)
Ok, so in all these cases there are chances that starvation might occur, i.e. some philosopher might not get a chance to eat as often. How do we tackle this? Well instead of having semaphores on the forks, why not have semaphores on philosophers themselves Check if both forks are empty at any point of time, if not wait, else use. Make sure neighbors are not eating. Look at Solution #7: Preventing Starvation A Little Better to know what i am talking about.

1. Ok, we know in order to avoid spurious wake ups we should put wait() in a while loop but what happens when you wake a philosoper up and its a spurious wake up? He waits() again and goes back to end of waiting list. That’s not good, instead lets 1.) make sure we don’t have spurious wake ups and 2.) Output an error (and return from function) if he wakes up but cannot eat so that we know we are causing spurious wakeup’s in the code.

2. So you MUST wait if people are waiting (even if you can eat). You will only be awakened, by a thread if you can eat. So when you are awakened, as a safety measure check if you can eat, output error message (and return) if you can’t and go ahead and eat!

3. Check most waiting thread when a philosopher finished eating or starts eating. In both scenarios, there is a possibility of the most waiting thread to start eating. Remember, until the most waiting thread cant eat, nobody behind him can eat too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
class Conductor {
 
  Philosopher philosophers[];
  List<String> eating;
  List<String> waiting;
  Lock lock=new ReentrantLock(true);
  Condition con=lock.newCondition();
 
  public Conductor(Philosopher philosophers[]) {
    this.philosophers = philosophers;
    this.eating = new ArrayList<String>();
    this.waiting = new ArrayList<String>();
  }
 
  public void eat(String philisopher) throws InterruptedException {
    if ( !validPhilosopher(philisopher) )
      return;
    //System.out.println(philisopher + " wants to eat...");
    //System.out.println(eating.size() + " people eating...");
    lock.lock();
    try {
      if ( waiting.size() > 0 || eating.contains(philisopher) || eating.contains(getLeftNeighbhor(philisopher)) || eating.contains(getRightNeighbhor(philisopher)) ) {
        System.out.println(philisopher + " blocked...");
        waiting.add(philisopher);
        con.await();
        //System.out.println(philisopher + " awakened...");
        waiting.remove(philisopher);
 
        if ( eating.contains(philisopher) || eating.contains(getLeftNeighbhor(philisopher)) || eating.contains(getRightNeighbhor(philisopher)) ) {
          System.out.println(philisopher + " awakened however he cant eat! Problem!!!");
          return;
        } 
      }
      System.out.println(philisopher + " eating...");
      eating.add(philisopher);
 
      // CHECK for WAITING threads Q, and signal last waiting thread, if you can handle it!
      if ( waiting.size() > 0 ) {
        String waitingPhil = waiting.get(0);
        if ( !eating.contains(waitingPhil) && !eating.contains(getLeftNeighbhor(waitingPhil)) && !eating.contains(getRightNeighbhor(waitingPhil)) ) {
          //System.out.println(philisopher + " eat signalling awake to " + waitingPhil);
          con.signal();
        }
      }
    } catch ( Exception e ) {
 
    } finally {
      lock.unlock();
    }
  }
 
  public void finisheat(String philisopher) throws InterruptedException {
    lock.lock();
    if ( !validPhilosopher(philisopher) || !eating.contains(philisopher) )
      return;
    eating.remove(philisopher);
 
    // CHECK for WAITING threads Q, and signal last waiting thread, if you can handle it!
    if ( waiting.size() > 0 ) {
      String waitingPhil = waiting.get(0);
      if ( !eating.contains(waitingPhil) && !eating.contains(getLeftNeighbhor(waitingPhil)) && !eating.contains(getRightNeighbhor(waitingPhil)) ) {
        //System.out.println(philisopher + " finisheat signalling awake to " + waitingPhil);
        con.signal();
      }
    }
    lock.unlock();
  }
 
  public boolean validPhilosopher(String philisopher) {
    for ( int i = 0 ; i < philosophers.length ; i++ )
      if ( philosophers[i].getPhilosopher().equals(philisopher) )
        return true;
    return false;
  }
 
  public String getLeftNeighbhor(String philisopher) {
    int i = 0;
    for ( ; i < philosophers.length ; i++ ) {
      if ( philosophers[i].getPhilosopher().equals(philisopher) )
        break;
    }
 
    if ( i == 0 )
      return philosophers[philosophers.length-1].getPhilosopher();
    else
      return philosophers[i-1].getPhilosopher();    
  }
 
  public String getRightNeighbhor(String philisopher) {
    int i = 0;
    for ( ; i < philosophers.length ; i++ ) {
      if ( philosophers[i].getPhilosopher().equals(philisopher) )
        break;
    }
 
    if ( i == philosophers.length-1 )
      return philosophers[0].getPhilosopher();
    else
      return philosophers[i+1].getPhilosopher();      
  }
}
 
class ConductorPhilosopher implements Philosopher {
  String philosopher;
  Conductor c;
  public ConductorPhilosopher(String philosopher, Conductor c) {
    this.philosopher = philosopher;
    this.c = c;
  }
 
  @Override
  public String getPhilosopher() {
    return philosopher;
  }
 
  @Override
  public void run() {
    try {  
      while ( true ) {
        //System.out.println(philosopher + " wants to eat...");
        c.eat(philosopher);
        //System.out.println(philosopher + " eating...");
        Thread.sleep(new Random().nextInt(2000));
        c.finisheat(philosopher);
        Thread.sleep(new Random().nextInt(2000));
        //System.out.println(philosopher + " thinking...");
      }
    } catch (InterruptedException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    }    
  }
}

Here is the philosophers table and main method for running the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class PhilosphersTable {
 
  ExecutorService executorService;
  Philosopher philosophers[];
 
  public PhilosphersTable(Philosopher philosophers[]) {    
    this.philosophers = philosophers;
    this.executorService = Executors.newFixedThreadPool(5);
 
    for ( int i = 0 ; i < philosophers.length ; i++ )
      executorService.submit(philosophers[i]);
  }
 
  public static Philosopher[] getConductorPhilosophers() {
 
    ConductorPhilosopher philosophers[]=new ConductorPhilosopher[5];
    Conductor conductor=new Conductor(philosophers);
 
    philosophers[0] = new ConductorPhilosopher("A", conductor);
    philosophers[1] = new ConductorPhilosopher("B", conductor);
    philosophers[2] = new ConductorPhilosopher("C", conductor);
    philosophers[3] = new ConductorPhilosopher("D", conductor);
    philosophers[4] = new ConductorPhilosopher("E", conductor);
 
    return philosophers;
 
  }
 
  public static Philosopher[] getOrderlyPhilosophers() {
 
    Fork forks[]=new Fork[5];
    forks[0]=new Fork(1);
    forks[1]=new Fork(2);
    forks[2]=new Fork(3);
    forks[3]=new Fork(4);
    forks[4]=new Fork(5);
 
    OrderlyPhilosopher philosophers[]=new OrderlyPhilosopher[5];    
    philosophers[0] = new OrderlyPhilosopher("A", forks[0], forks[4]);
    philosophers[1] = new OrderlyPhilosopher("B", forks[1], forks[0]);
    philosophers[2] = new OrderlyPhilosopher("C", forks[2], forks[1]);
    philosophers[3] = new OrderlyPhilosopher("D", forks[3], forks[2]);
    philosophers[4] = new OrderlyPhilosopher("E", forks[4], forks[3]);
 
    return philosophers;
 
  }
 
  public static Philosopher[] getDeadlockPhilosophers() {
 
    Fork forks[]=new Fork[5];
    forks[0]=new Fork(1);
    forks[1]=new Fork(2);
    forks[2]=new Fork(3);
    forks[3]=new Fork(4);
    forks[4]=new Fork(5);
 
    DeadlockPhilosopher philosophers[]=new DeadlockPhilosopher[5];    
    philosophers[0] = new DeadlockPhilosopher("A", forks[0], forks[4]);
    philosophers[1] = new DeadlockPhilosopher("B", forks[1], forks[0]);
    philosophers[2] = new DeadlockPhilosopher("C", forks[2], forks[1]);
    philosophers[3] = new DeadlockPhilosopher("D", forks[3], forks[2]);
    philosophers[4] = new DeadlockPhilosopher("E", forks[4], forks[3]);
 
    return philosophers;
 
  }
 
}
 
public class DiningPhilosphers {
 
  public static void main(String args[]) {
 
    //PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getDeadlockPhilosophers());
    //PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getOrderlyPhilosophers());
    PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getConductorPhilosophers());
  }
 
}

Reentrant vs NonReEntrant locks

Comments Off on Reentrant vs NonReEntrant locks

Java 5 has a ReentrantLock implementation of the Lock interface. Meaning if the same thread tries to acquire the lock again, it will allow that. It does have information about which thread is holding the lock. The following code will not cause a deadlock.

1
2
3
4
5
6
7
8
9
10
11
12
Lock l=new ReentrantLock(true);
public void funcReentrantLock(int level) {
  System.out.println("entered funcReentrantLock: " + Thread.currentThread().getName() + " at level " + level);		
  if ( level == 0 )
    return;
 
  l.lock();
  System.out.println(Thread.currentThread().getName() + " locked at level " + level);
  funcReentrantLock(level-1);
  l.unlock();
  System.out.println(Thread.currentThread().getName() + " unlocked at level " + level);
}

Semaphore’s on the other hand are non-re entrant meaning if the same thread locks and then re-locks it will cause a deadlock. If the same thread tries to acquire the lock again, it wont allow that. It does not have information which thread is holding the lock. The following code will cause a deadlock.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Semaphore available = new Semaphore(1, true);
public void funcNonReentrantLock(int level) {
  System.out.println("entered funcNonReentrantLock: " + Thread.currentThread().getName() + " at level " + level);		
  try {
    if ( level == 0 )
	return;
    available.acquire();
    System.out.println(Thread.currentThread().getName() + " acquire at level " + level);
    funcNonReentrantLock(level-1);
    available.release();
    System.out.println(Thread.currentThread().getName() + " release at level " + level);
  } catch (InterruptedException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
  }
}

The synchronized keyword is a re-entrant lock. Why use one over the other? Well for starters it seems like re-entrant lock performs much better. Also, the lock interface provides some other api methods like trylock() which acquires the lock only if it is free at time of invocation.

Deadlocks in java

Comments Off on Deadlocks in java

Ok, lets start with seeing a simple example of how deadlocks can be created in java. Simple way to achieve this is to try to acquire locks in different order and you will see it happen.

Thread1 – Resource 1, Resource 2
Thread2 – Resource 2, Resource 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Resource1 {
}
 
class Resource2 {
}
 
class DeadlockThread1 implements Runnable {
 
  public void run() {
    while ( true ) {
      synchronized ( Resource1.class ) {
        System.out.println("DeadlockThread1 acquired Resource1");
        synchronized ( Resource2.class ) {
          System.out.println("DeadlockThread1 acquired Resource1 and Resource2");
        }
      }
    }
  } 
 
}
 
class DeadlockThread2 implements Runnable {
 
  public void run() {
    while ( true ) {
      synchronized ( Resource2.class ) {
        System.out.println("DeadlockThread2 acquired Resource2");
        synchronized ( Resource1.class ) {
          System.out.println("DeadlockThread2 acquired Resource2 and Resource1");
        }
      }
    }
  } 
 
}
 
public class Deadlock {
  public static void main(String args[]) {
    Thread dlock1=new Thread(new DeadlockThread1());
    Thread dlock2=new Thread(new DeadlockThread2());
    dlock1.start();
    dlock2.start();
  }
}

Release of Locks:- Ok, say that we acquired resources in the same order, in what order do we release them? In other words, is one of these sequences better than the other?

Sequence 1

  • lock R1
  • lock R2
  • unlock R2
  • unlock R1

Sequence 2

  • lock R1
  • lock R2
  • unlock R1
  • unlock R2

Sequence 1 is recommended. Sequence 2 doesn’t cause issues iff you don’t acquire/unacquire locks between unlock R1 and unlock R2. For e.g.

  • lock R1
  • lock R2
  • unlock R1
  • In the mean time another thread got hold of R1 and is waiting for you to release R2
  • lock R1 <- you are trying to re-lock R1, its a deadlock!

Quartz within Tomcat using XML job descriptions

Comments Off on Quartz within Tomcat using XML job descriptions

Objective is to make a counter using Quartz. Step by step we’ll do the following

  1. Create a custom context listener to initialize a counter,
  2. Create quartz properties file and xml jobs file,
  3. Schedule a job that would keep incrementing the counter,
  4. Create a servlet to view that counter.

1. Create a custom context listener to initialize a counter:- If we need to listen to various events within the servlet container event listeners give us the flexibility to do that. We have Servlet context-level (application-level) events and Session-level events. For more, look at the documentation.

“After the application starts up and before it services the first request, the servlet container creates and registers an instance of each listener class that you have declared. For each event category, listeners are registered in the order in which they are declared. Then, as the application runs, event listeners for each category are invoked in the order of their registration. All listeners remain active until after the last request is serviced for the application.”

We declare all the listeners we need in the xml file. QuartzInitializerListener will create the scheduler (MyScheduler) from the quartz.properties and set scheduler factory instance into the servletContext.

1
2
3
4
5
6
7
8
9
10
11
12
<context-param>
  <param-name>initcounter</param-name>
  <param-value>100</param-value>
</context-param>
<listener>
  <listener-class>
	com.napp.listener.MyServletContextListener
  </listener-class>	
  <listener-class>
	org.quartz.ee.servlet.QuartzInitializerListener
  </listener-class>
</listener>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class MyServletContextListener implements ServletContextListener {
  public static int counter = 0;
  final static Logger logger = LoggerFactory.getLogger(MyServletContextListener.class);
 
  public void contextDestroyed(ServletContextEvent arg0) {
    // TODO Auto-generated method stub
  }
 
  public void contextInitialized(ServletContextEvent arg0) {
    String initCounter = arg0.getServletContext().getInitParameter("initcounter");
    if ( initCounter!= null) {
	counter = Integer.parseInt(initCounter);
	logger.info("Set counter-" + counter);
    } else {
	logger.info("Coulnt read init counter, default is 0");
    }
  }
}

2. Create quartz properties file and xml jobs file:- Quartz.properties that contains information that the Scheduler Factory uses to create a scheduler.

1
2
3
4
5
6
7
8
org.quartz.scheduler.instanceName = MyScheduler
org.quartz.threadPool.threadCount = 3
org.quartz.jobStore.class = org.quartz.simpl.RAMJobStore
org.quartz.plugin.jobInitializer.class = org.quartz.plugins.xml.XMLSchedulingDataProcessorPlugin
org.quartz.plugin.jobInitializer.fileNames = jobs.xml
org.quartz.plugin.jobInitializer.failOnFileNotFound = true
#org.quartz.plugin.jobInitializer.scanInterval = 1
#org.quartz.plugin.jobInitializer.wrapInUserTransaction = false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
<job-scheduling-data
  xmlns="http://www.quartz-scheduler.org/xml/JobSchedulingData"
  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="http://www.quartz-scheduler.org/xml/JobSchedulingData http://www.quartz-scheduler.org/xml/job_scheduling_data_1_8.xsd"
  version="1.8">
  <schedule>	
    <job>
	<name>hello-world-job</name>
	<group>hello-world-group</group>
	<description>Print a welcome message</description>
        <job-class>com.napp.job.HelloWorldScheduledJob</job-class>
        <job-data-map>
          <entry>
	    <key>param1</key>
	    <value>value1</value>
          </entry>
        </job-data-map>
    </job>
    <trigger>	
	<cron>
	  <name>helloworld-trigger</name>
	  <job-name>hello-world-job</job-name>
	  <job-group>hello-world-group</job-group>
	  <!-- It will run every 5 seconds -->
	  <cron-expression>0/5 * * * * ?</cron-expression>
	</cron>	
    </trigger>
  </schedule>
</job-scheduling-data>

3. Schedule a job that would keep incrementing the counter:-

1
2
3
4
5
6
7
public class HelloWorldScheduledJob implements Job {
  final static Logger logger = LoggerFactory.getLogger(HelloWorldScheduledJob.class);
  public void execute(JobExecutionContext arg0) throws JobExecutionException {
    logger.info("Incremening counter.");
    MyServletContextListener.counter = MyServletContextListener.counter+1;
  }
}

4. Create a servlet to view that counter:-

1
2
3
4
5
6
7
8
9
10
11
12
13
public class SimpleServlet extends HttpServlet {
  private static final long serialVersionUID = 1L;
  public void doGet(HttpServletRequest req, HttpServletResponse rsp) throws ServletException, IOException {
    rsp.setContentType("text/html");
    PrintWriter out = rsp.getWriter();
    out.println("<html>");
    out.println("<head><title> Simple Servlet </title></head>");
    out.println("<body>");
    out.println("<p>Counter - " + MyServletContextListener.counter + "</p>");
    out.println("</body></html>");
    out.close();
  }
}

You can download the sample-web-app from here.