COMP 2006J讲解、java编程语言调试、java程序辅导
讲解留学生Processing|讲解R语言编程
Operating Systems
Assignment 01: Deadlocks
COMP 2006J
Autumn, 2020
1 Deadlock Simulator
Please download the deadlock simulator source code from Moodle. The deadlock simulator illustrates
multiple processes competing for one or more resources. This helps us to investigate the nature
and causes of deadlock conditions, and how they can be avoided, detected, and resolved. Users can
define different processes with different resource requirements using the configuration files used in the
simulator and experiment.
2 Overview of the simulator
• It creates a specified number of simulated processes.
• For each process, it reads a command file of actions to be performed by that process. Each
action is one of the following:
– Compute for a specified length of time
– Request an instance of a specified resource
– Free an instance of a specified resource
– End or halt the process
• It creates a specified number of instances for each of several resources.
• It runs the simulation by considering the commands for each process, one at a time, and either
allowing the process to execute, granting it an instance of a requested resource, blocking the
process until a requested is available, or ending a process.
• When all processes are halted, the simulation stops.
3 Running the simulation
• Compile the java code using following command.
1 $ javac *. java
• To run the program, enter the following command in the terminal.
1 $ java deadlock < file - name - prefix > < initial - number - of - processes > <
initial - available - for - resource > ...
Parameter Description
file-name-prefix
Specifies the name prefix for the process command files. The default command file names are
generated from this prefix, followed by the number of the process, followed by ”.dat”
(e.g, ”a0.dat”, ”a1.dat” if ”a” is the prefix).
initial-number-of-processes Specifies the number of processes to create for the simulation. This should be a non-negative
number, usually greater than one.
initial-available-for-resource...
Specifies the initial number of instances available for each resource. This should be a sequence
of non-negative numbers. For example, ”2 1 2 0” indicates that there are four resources, and
there are initially two instances of resource 0, one instance of resource 1, two instances of
resource 2, and zero instances of resource 3.
Example:
University College Dublin 1
Operating Systems
Assignment 01: Deadlocks
COMP 2006J
Autumn, 2020
1 $ java deadlock aN 2 1 > a . log
• In this example.
– a : is the prefix for the names of the files containing the commands (the actual names of
the files are a0.dat, and a1.dat, so N is the integer that identifies the file)
– 2 : is the number of processes to be created
– 1 : is the number of instances to create for the first resource
– a.log : is the name of the output file
3.1 Sample Process Command Files
The ”a0.dat” input file looks like this:
1 /*
2 a0 . dat
3 The " a " collection of process data files is meant to simulate
4 two processes competing for a single resource . If you run
5 the simulator with one resource available , one of the processes
6 will block until the other is done using the resource .
7 */
8 C 10 // compute for 10 milliseconds
9 R 0 // request resource 0
10 C 10 // compute for 10 milliseconds
11 F 0 // free resource 0
12 H // halt process
3.2 The Output File
The output file is a log of the simulation since the simulation started. It contains one line per cycle
executed. The format of each line is:
1 time = t available = r0 r1 ... rn blocked = n
Where,
• t - is the number of milliseconds since the start of the simulation
• ri - is the number of available instances of each resource
• n - is the number of blocked processes
The output file a.log looks something like this:
1 time = 0 available = 1 blocked = 0
2 time = 1 available = 1 blocked = 0
3 time = 2 available = 1 blocked = 0
4 time = 3 available = 1 blocked = 0
5 time = 4 available = 1 blocked = 0
6 time = 5 available = 1 blocked = 0
University College Dublin 2
Operating Systems
Assignment 01: Deadlocks
COMP 2006J
Autumn, 2020
7 time = 6 available = 1 blocked = 0
8 time = 7 available = 1 blocked = 0
9 time = 8 available = 1 blocked = 0
10 time = 9 available = 1 blocked = 0
11 Process 1 blocked .
12 time = 10 available = 0 blocked = 1
13 time = 11 available = 0 blocked = 1
14 time = 12 available = 0 blocked = 1
15 time = 13 available = 0 blocked = 1
16 time = 14 available = 0 blocked = 1
17 time = 15 available = 0 blocked = 1
18 time = 16 available = 0 blocked = 1
19 time = 17 available = 0 blocked = 1
20 time = 18 available = 0 blocked = 1
21 time = 19 available = 0 blocked = 1
22 Process 1 unblocked .
23 time = 20 available = 0 blocked = 0
24 time = 21 available = 0 blocked = 0
25 time = 22 available = 0 blocked = 0
26 time = 23 available = 0 blocked = 0
27 time = 24 available = 0 blocked = 0
28 time = 25 available = 0 blocked = 0
29 time = 26 available = 0 blocked = 0
30 time = 27 available = 0 blocked = 0
31 time = 28 available = 0 blocked = 0
32 time = 29 available = 0 blocked = 0
33 time = 30 available = 1 blocked = 0
34 All Processes Halted .
In this example, the simulation runs for a total of 30 time units and then halts. During the simulation,
all processes are computable for 10 time units. During the next 10 time units, the single instance of
the resource is allocated to one process, while the other process is blocked. During the final 10 time
units, the first process frees the resource, but the resource is immediately allocated to the second
process, which then continues to compute, unblocked, to the end of the simulation.
4 Tasks
4.1 Task 1
(a) Try running the deadlock simulator using the following command:
1 $ java deadlock a 2 2 > a . log
Explain why a process block does not occur.
4.2 Task 2
(a) Create a simple configuration (by creating two process scripts like a0.dat and a1.dat) which
will end up in a deadlock using the simulator. Name those script files as ex0.dat, ex1.dat, ...,
University College Dublin 3
Operating Systems
Assignment 01: Deadlocks
COMP 2006J
Autumn, 2020
exN.dat.
(b) Briefly explain your configuration, and why it leads to a deadlock.
4.3 Task 3
(a) Implement the deadlocked() method in the DeadlockManager class. You should use the Resource
preemption method you learned in the class here. Your algorithm should consider the process
starvation problem and should not reset the same process every time a deadlock occurs.
4.4 Task 4
(a) Explain the algorithm implemented in Task 3. Specifically, explain how it handles the starvation
problem.
(b) Explain why recovering this way is very hard, or impossible in most real-world scenarios.
5 Submission
Submit a single zip file which includes the following files:
1. DeadlockManager.java
2. a.log
3. Process scripts files and log files for the configuration in Task2. (Rename them as ex0.dat,
ex1.dat, . . . , exN.log)
4. assignment 1.pdffile containing your answers for questions asked in Task1, Task2 and Task4.
Your submission will be tested against input that we have designed.
• Do NOT change any source file other than the DeadlockManager.java.
• Do NOT change the function interfaces of any functions in the DeadlockManager.java.
• If you need more static variables for your implementation you can define them without changing
other data structures.
• Do NOT output anything other than what has been asked for. If you have added any outputs
for your convenience, you should remove/comment them before submission.
University College Dublin 4