Deadlocks
Operating Systems Lab Class 7
In this lab session we will look at the problem of deadlocks. Deadlock describes a situation where two or more threads are blocked forever, waiting for each other. Deadlock occurs when multiple threads need the same locks but obtain them in different order. A Java multithreaded program may suffer from the deadlock condition because the synchronized keyword causes the executing thread to block while waiting for the lock associated with the specified object.
Figure 1: Deadlocks
1 Avoiding Deadlocks
We will write a monitor solution to the north-south railway tunnel problem. Suppose a two- way (north-south), two-lane railway contains a long one-lane tunnel. A southbound (or north- bound) train can only use the tunnel if there are no oncoming trains in the tunnel from the other side. Because of accidents, a signalling system has been installed at the entrances to the tunnel. When a train approaches the tunnel, a sensor notifies the controller computer by calling the function enterTunnelSouthBound when a train arrives at southbound, and it calls the function enterTunnelNorthBound when a train arrives at northbound. When a train ex- its the tunnel, the sensor notifies the controller computer by calling exitTunnelNorthBound or exitTunnelSouthBound .
The railway can become deadlocked if both a northbound and a southbound train enter the tunnel at the same time (the trains are unable to back up). We are going to write a program that prevents deadlock using Java synchronization.
In this lab, we are going to have two threads classes, one representing a northbound train and the other representing a train traveling southbound. Once a train is on the tunnel, each will sleep for a random period of time to simulate traveling in the tunnel.
2 Getting Started
1. Download the os-lab7.zip archive from Canvas and unzip it into your workspace. 1
2. Start NetBeans and open the project. The project should contain four files in the src di- rectory: Tunnel.java (contains the main method), TimesGenerator.java, SouthBound.java, NorthBound.java and TunnelManager.java.
3. Before you begin, read through the code and then compile and run it before making any modifications. This should work without problems.
2.1 Implementation 1
4. The program will work as follows:
• The program takes four arguments: northTrains, southTrains, maxTravelTime and mea-
nArrivalTime. For example, this input 4 3 5 10 means that the number of north trains is 4, the number of south trains is 3, the maximum travel time is 5 seconds and the mean of the exponential distribution that is used to generate the arrival times is 10. Running this example, java Tunnel 4 3 5 10 should output
• In the first step, complete Tunnel.java to parse the command line arguments and create the threads that run the tasks SouthBound and NorthBound; also implement SouthBound.java and NorthBound.java; but do not yet implement TunnelManager.java.
• Complete the newTrainArrivalTime() method from TimesGenerator class. This method aims to return the arrival time value from the exponential distribution that has a mean of meanArrivalTime (see the Appendix page).
2.2 Reflection
5. Run this program several times with different inputs and observe the output. What do you observe? Explain what is happening and why.
2.3 Implementation 2
6. Now complete the remaining classes:
• Fill in the gaps in TunnelManager.java.
You find hints about the possible algorithm in the comment blocks of the locking func- tions. Your implementation will require the use of the wait() and notify() (respectively notifyAll()) methods as defined in the java.lang.Object class. Look at the Java API to understand what they are doing. Also read about synchronized methods.
• Test your program with different inputs.
7. Extra question: Explain how semaphores can be used to design an algorithm that prevents
deadlock.
3 Java API References
https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html
https://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html
http://docs.oracle.com/javase/8/docs/api/java/lang/Runnable.html
http://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Semaphore.html
http://docs.oracle.com/javase/7/docs/api/java/util/Random.html
Appendix
Exponential Distribution
• The Probability Density Function(PDF) of the exponential random variable t is given by:
• Mean= 1/λ
• The Cumulative Distribution Function(CDF) : F(t)=f(T ≤t)=1−e−λt
t≥0
f(t) = λe−λt, t ≥ 0
• Inverse transform sampling is a basic method for generating sample numbers at random from any probability distribution given its cumulative distribution function. This means by knowing the value of F(t) we can find the value of t as follows:
t = −1ln(1 − F(t)) λ
In Jave, the value of F(t) can be generated using nextDouble() function which returns the next pseudorandom, uniformly distributed value between 0 and 1 from this random number generator’s sequence.
• Example
Generate an arrival time from an exponential distribution of mean 3, if nextDouble() returns 0.811. Sol. the arrival time value t can be found by substituting t=0.811 in the above equation:
t = − 1 ln(1 − F (t)) = − 1 ln(1 − 0.811) = 5 λ3