LNU: 1DV512 Operating Systems (H18) Page 1 of 3 Practical Task 2
Aim: Practical experience with synchronization concepts Begin Date: November 15, 2018
End Date: November 25, 2018
Submission: an archive file (zip) that includes all files relevant to execute and test your program should be submitted through MyMoodle; if the submitted program does not run (execute) using the instructions provided in the ReadMe.txt file, your solution is not accepted.
Instructions: you are allowed and encouraged to use the literature recommended in the course; use of other literature is also encouraged; assignment must be completed independently and without the help of other colleagues or the teacher.
Problem definition
Philosopher_1
Develop a Java application that simulates the Dining Philosophers problem (see Chapter 6 of the book1). Five philosophers sit around a table (see Figure 1) and in front of each philosopher there is a bowl of food. There are five chopsticks available. A philosopher can be in three states: EATING, THINKING, or HUNGRY. A hungry philosopher needs two chopsticks (his left and right chopstick) for eating. If a chopstick is used by a neighbor, then the philosopher must wait until the chopstick is released. The philosopher first picks up the left chopstick, and then the right chopstick.
Initially all five philosophers are in THINKING state. Time for THINKING and EATING is generated pseudo-randomly from a discrete uniform distribution [0, 1000]. Basically, a philosopher is in THINKING or EATING state for 0-1000 time units (milliseconds); one of these values is selected in pseudo-random2 manner to simulate thinking or eating time.
Philosopher_5
Philosopher_4
Philosopher_2
Philosopher_3
Figure 1. Dining Philosophers
We will provide four classes for you: DiningPhilosopher, Philosopher, Chopstick, and DiningPhilosopherTest. Details for each class are listed below:
1. The DiningPhilosopher class contains:
- Variables: philosophers (list), chopsticks (list), DEBUG (boolean),
NUMBER_OF_PHILOSOPHERS (int), SIMULATION_TIME (int), SEED (int),
executorService
- Methods: printTable (that prints the average eating/thinking/hungry times for each
philosopher); initialize (used to set the simulation time, which indicates for how many
1 Operating System Concepts, 9th Edition, by Abraham Silberschatz, Peter B. Galvin, Greg Gagne 2 http://docs.oracle.com/javase/7/docs/api/java/util/Random.html
Chopstick_1
Chopstick_2
Chopstick_3
Chopstick_5
Chopstick_4
LNU: 1DV512 Operating Systems (H18) Page 2 of 3
milliseconds the simulation will run; the seed for the random generator); start (that
starts the simulation process).
- The Philosopher class implements the runnable interface, which means that each philosopher
will be running in a separate thread. This class contains:
- Variables: Left and right chopstick objects.
- Methods: getAverageThinkingTime, getAverageEatingTime, getAverageHungryTime
(to retrieve the average thinking, eating, and hungry times); getTotalThinkingTime, getTotalEatingTime, getTotalHungryTime (to retrieve the total thinking, eating, and hungry times); getNumberOfThinkingTurns, getNumberOfEatingTurns, getNumberOfHungryTurns (to retrieve the number of thinking, eating, and hungry turns); run() (that basically simulates the think, eat, and hungry process for the corresponding philosopher).
- The Chopstick class is used by the Philosopher class. It contains:
a. Variables: id (the chopstick id) b. Methods:
4. The DiningPhilosopherTest is a class that test the correctness of your implementation a. Methods: test1, test2, and test3 (test different scenarios)
You should:
- Import these four classes.
- Complete the start() method in the DiningPhilosopher class. You need to provide means to
interrupt the philosophers when the simulation time is over.
- Complete the initialize(…) method in the DiningPhilosopher class. You should create the
chopsticks, and philosophers, and assign chopsticks to philosophers.
- Implement the run() method in the Philosopher class.
- Calculate the average3 EATING, THINKING, and HUNGRY times. When the start() method
has finished the average eating, thinking, and hungry times for each philosopher should be
known.
- If DEBUG is set to true, your implementation should print in the console the major events that
occur during the simulation (for instance, Philosopher_1 is THINKING, Philosopher_4 is EATING, Philosopher_3 is HUNGRY, Philosoper_2 released Chopstick_3, Philosopher_1 picked-up Chopstick_1, Deadlock detected …)
- Detect and report the deadlock (that is a state where all philosophers hold the left chopstick and wait for the right chopstick). Alternatively, prevent deadlocks from happening and explain how you prevented it from happening.
- Add comprehensive comments (in the code) to explain your implementation.
Folder structure
- Create a new project and name it 1dv512.userid (e.g. 1dv512.sm222bt)
- Put all your files in one package (default)
- Pack the whole project directory (src) into zip archive. Your zip should contain some root
directory (e.g. sm222bt), not just list of files. Example of the folder structure:
− sm222bt
− src
3 http://mathworld.wolfram.com/ArithmeticMean.html
LNU: 1DV512 Operating Systems (H18)
Page 3 of 3
− Chopstick.java,
− DiningPhilosopherTest.java, − DiningPhilosopher.java
− Main.java
− Philosopher.java,
− ReadMe.txt,
Instructions for running and testing the application
Provide any information that is relevant for running your application in the ReadMe.txt file. Expect that we test your solution using a method like this:
public static void main(String args[]) {
DiningPhilosopher dp = new DiningPhilosopher(); dp.DEBUG = true;
int simulationTime = 10000;
int seed = 100;
dp.initialize(simulationTime, seed);
dp.start();
dp.printTable();
}