Code examples in c c++ for deadlock detection

CSci 430: Programming Project #3

Deadlock Detection

Summer I 2019

Dates: Assigned: Monday June 17, 2019 Due: Friday June 21, 2019 (before Midnight)

Objectives:

• Learn more about Deadlock algorithms.

• Better understand how we can algorithmically detect deadlocks on a system.

• Use C/C++ to implement vector and matrix data structures, get prac- tice in creating and using such data structures in C/C++.

Description:

Our textbook gives the following algorithm (pg. 276) for algorithmically detecting if a deadlock is present or not in a system. It requires that the system keep an Allocation matrix A, listing which resources are currently allocated to which processes, and the available vector V, which gives the amount of each resource currently available in the system. In addition, the deadlock detection algorithm requies a request matrix Q, which keeps track of the amount of each resource each process is currently requesting from the system. The algorithm is:

1. Mark each process that has a row in the Allocation matrix of all zeros.

2. Initialize a temporary vector W to equal the Available vector A.

1

3. Find an index i such that process i is currently unmarked and the i th row of Q is less than or equal to W. That is, Qik ≤ Wk, for 1 ≤ k ≤ m. If no such row is found, terminate the algorithm.

4. If such a row is found, mark process i and add the corresponding row of the allocation matrix to W. That is, set Wk = Wk+Aik, for 1 ≤ k ≤ m. Return to step 3.

A deadlock exists if and only if there are unmarked processes at the end of the algorithm. Each unmarked process is deadlocked.

In this assignment we will implement the deadlock detection algorithm. Your program will be given a file that describes the A allocation matrix and the Q request matrix, representing the current state of all allocations and requested allocations in the system. Your program will implement the deadlock detection algorithm described above. The result of your program will be one of 2 outputs:

1. If no deadlock exists, the program will display No Deadlock on stan- dard output.

2. If a deadlock does exist, the program will display Deadlock: P0, P1, P2 on standard output, where P0, P1, P2 are the processes that the algorithm determined to be deadlocked in the system.

State simulation file formats

I have provided a p3-start.cpp template that can open up and read in the process/resource state simulation files used for this assignment. Here we discuss a bit more the format of these file. I have provided 2 or 3 exam- ple simulations, with expected correct answers, for you to use to test your implementations with.

The input files needed for this assignment need to contain the information found in the V available vector and the A allocation and Q request matrices. In the following I use r as the number of resources and p as the number of processes. Thus the general format of the input file is:

r p V1 V2 V3 ... Vr A11 A12 ... A1r ... Ap1 Ap2 ... Apr

2

Q11 Q12 ... Q1r ... Qp1 Qp2 ... Qpr

For example, the example of the deadlock detection algorithm given on page 277 has a system with r=5 resources and p=4 processes. The V, A and Q vector/matrices are shown on that page. The input file for the current state of the system shown on page 277 would be

5 4 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1

The function named readSystemState() in your template p2-start.cpp code expects a file of this format, and reads it into a State structure for you.

Running Simulations

The following is a discussion of the expected output of your program. Your program must work from the command line, and expect a single parameter, the name of the state simulation input file, as its input. Your program should display only a single line to standard output as a result of running it. If the system, described in the state input file is not deadlocked, the program should simply state there was no deadlock to standard output:

$ p3.exe state-02.sim No Deadlock

On the other hand, if your program is deadlocked, it should say that it detected a deadlock, and it should print out the processes that are deadloked to standard output:

$ p3.exe state-01.sim Deadlock: P0, P1,

3

I have provided 2 or 3 example input state files, named state-01.sim, state-02.sim, etc. I have also provided the correct and expected output for these simulations, named state-01.res, state-02.out, etc.