Write a C program to execute a deadlock detection program

One technique for dealing with deadlock is called detect and recover. In this scheme, some procedure is used to identify when a deadlock occurs, and then another procedure is used to deal with the blocked processes. One technique to identify a deadlock is to maintain a resource graph that identifies all processes, all resources, and the relationships between them (that is, which processes exclusively own which resources, and which processes are blocked waiting for which resources), and check for cycles in the resource graph. For this assignment, you will write a program that simulates the execution of multiple processes with respect to their resource allocation and resource release requests, and detect when (or if) deadlock occurs. If deadlock occurs, your program will then display a list of the processes and resources involved in the deadlock. To simulate the behavior of the processes in the system, your program will use input that describes the sequence of actions each process takes to lock, release (unlock), and use resources. Each such action consists of a capital letter L, U or C respectively, immediately followed by a non-negative integer n; the interpretation of n depends on the particular action. The various actions permitted are as follows.

If the action is L, the process (call it p) that performs the action requests exclusive use of the resource identified by n. The nr resources in the system are identified by integers in the range 1 to nr. If the resource is available (that is, not currently locked by any other process) when process p requests its use, then process p is given exclusive use of the resource and is allowed to continue. If the resource is not available, process p is blocked and placed at the end of the firstin-first-out queue of processes waiting on the resource. Process p remains on the queue until the resource becomes available and it (process p) is at the head of the queue of waiting processes. Thus the first process to block while requesting use of a resource is the process that is moved to the ready state when the resource again becomes available.

If the action is U, process p relinquishes its exclusive use of the resource identified by n. This action will also move a single blocked process (say process q) from the head of the queue of processes waiting on this resource to the end of the systems ready queue. Note that immediately after this waiting process (q) moves to the end of the ready queue, the process that just released the resource (p) will be moved to the end of the ready queue, just after the process that was at the head of the waiting queue (q).

If the action is C, then the process computes for n units of time, maintaining exclusive use of any resources it may have previously obtained but not yet released. n will never be smaller than 1; that is, there will never be any vacuous compute actions in a process. Of course, the computation is really fictional, and will just cause the simulated system time to increase by n. A process terminates after it has successfully executed each of the actions specified for it in the input data. Note that we make the (unusual) assumption that if a process terminates still having exclusive use of one or more resources, then those resources are forever unavailable (at least until the next simulation)!

For example, suppose a process is described by the following sequence of actions:

L1 L2 C10 U1 U2

This process will first request exclusive use of resource 1, then exclusive use of resource 2. Next it will compute for 10 units of time (maintaining exclusive use of resources 1 and 2), after which it will relinquish its use of resources 1 and 2 (in that order).

There will be no more than 50 processes in the system in any simulation, and we will assume there is just a single CPU. Each process will have its own sequence of actions describing its execution, and there will be no more than 50 actions for any process. There will be no more than 50 resources in any simulation.

Each successful request for the exclusive use (L) or release (U) of a resource by a process requires one time unit to complete, and a compute action (C) requires the number of time units specified by n for that action. The example shown above will require a total of 14 time units to complete. Since all processes are assumed to be in the ready queue (in increasing process number order: 1, 2, , np) at the beginning of a simulation, and the first time unit is numbered 0, the process in the example above will terminate at time 14.

The execution of the sequences describing each process is done in a round-robin manner. One unit of time is given to each process, in turn, starting with process 1, then process 2, , and then process np. Execution then continues with process 1 again (assuming it didnt block or terminate during its previous execution). Of course, when a process completes, it is no longer given any units of execution time. If a process becomes blocked, it does not receive any units of execution time until it is unblocked. If a process p requests a resource r, but is not able to immediately obtain exclusive use of r (because another process q is using it), then process p is blocked while waiting for the resource r to become available. When process q releases resource r, the first process waiting for the resource (that is, the first process in the queue of processes waiting for resource r) is moved to the end of the queue of ready processes. Note that this does not guarantee that process p will successfully obtain the resource when it next runs, since another ready process (ahead of p in the ready queue) may run and request exclusive use of the resource before p is selected for execution.

Lets look at a complete example. Suppose we have three processes with execution action sequences as follows:

Process 1: L1 L2 C2 U1 U2

Process 2: L1 L2 C2 U1 U2

Process 3: L3 C5 U3 C2

Simulation 2 in the sample input and output (below) shows the sequence in which these process actions would occur, and the time (starting at 0) when they would occur.

The set of processes in simulation 2 does not deadlock, but obviously other sequences can (see the samples for several such sequences). To detect deadlock, your program must build a resource graph (with nodes for processes and resources, and directed edges indicating resource ownership and pending resource requests), and test the graph for the existence of a cycle after each resource allocation request is made by a process. This test must be performed after each successful or unsuccessful allocation.

The input data will consist of a sequence of simulation test cases identified by sequential numbers starting with 1. The first line of input for each test case will contain two integers that specify the number of processes (1 np 50) and the number of resources (1 nr 50). The remaining np lines in the test case specify the actions for each of the np processes, with line i + 1 of the test case input containing the action specifications for process i. Each action specification line contains an integer na (1 na 50) that specifies the number of actions for the process and then na action specifications, each consisting of an action type (L, U, or C) followed immediately by an integer. The last test case will be followed by a line containing two integer zeroes. Sample input and output appears below, and illustrates the input format.

Sample Input

1 2

5 L1 L2 C10 U1 U2

3 3

5 L1 L2 C2 U1 U2 5 L1 L2 C2 U1 U2

4 L3 C5 U3 C2 2 2 5 L1 L2 C2 U1 U2

5 L2 L1 C2 U2 U1

3 3

6 L1 C3 L2 C3 U1 U2

6 L2 C3 L3 C3 U2 U3

6 L3 C3 L1 C3 U3 U1

7 6

7 L1 C5 L2 C5 U1 U2 C3

4 C3 L3 C5 U3

5 C3 L2 C2 U2 C3

6 L4 C6 L3 U4 C2 U3

6 L3 C5 L5 U3 U5 C2

7 L6 C5 L2 C2 U2 U6 C3

7 L5 C2 L4 C5 U5 C2 U4

0 0

Expected Output for the Sample Input (without trace)

Simulation 1

All processes successfully terminated.

Process 1: run time = 14, ended at 14

Simulation 2

All processes successfully terminated.

Process 1: run time = 6, ended at 12

Process 2: run time = 6, ended at 21

Process 3: run time = 9, ended at 19

Simulation 3

Deadlock detected at time 2 involving...

Processes 1, 2

Resources 2, 1

Simulation 4

Deadlock detected at time 12 involving...

Processes 1, 2, 3

Resources 2, 3, 1

Simulation 5

Deadlock detected at time 40 involving...

Processes 4, 5, 7

Resources 3, 5, 4

Provided template code:

#include

#include

#include

#define MAXSTEP 50 /* max action steps for any process */

#define MAXPROC 50 /* max processes in any simulation */

#define MAXRSRC 50 /* max resources in any simulation */

FILE *f; /* input stream */

/*----------------------------------------------------------------*/

/* There are several arrays used to record information about the */

/* processes and the resources. Since process IDs and resoure IDs */

/* start with 1, the 0th entry in each array is unused. That is, */

/* the arrays are treated as if they are 1-origin arrays, and not */

/* 0-origin arrays. This makes the code easier to understand at */

/* the cost of one array entry. */

/*----------------------------------------------------------------*/

/*------------------------------------------------------------------*/

/* This is an array of structures with one entry for every process. */

/* Each entry contains the "program" that will be executed by the */

/* process (ns, a, and n), the index in the a and n arrays of the */

/* next action to be taken, the state of the process, the total */

/* time used by the process, and the time when it ended. */

/*------------------------------------------------------------------*/

struct process {

int ns; /* # of actions for this process */

char a[MAXSTEP]; /* actions */

int n[MAXSTEP]; /* parameters (resource ID or time) */

int ip; /* index to next action */

int state; /* process state */

/* -1 = finished */

/* 0 = ready (or running) */

/* 1..nr = blocked, waiting on resource */

int runtime; /* time used */

int endtime; /* time process ended */

} proc[MAXPROC+1];

int trace; /* trace option value */

int simno; /* simulation number */

int t; /* simulation time */

int np; /* total # of processes (1..MAXPROC) */

int nr; /* total # of resources (1..MAXRSRC) */

/*--------------------------------------------------------------------*/

/* The following two items represent a very simple queue that records */

/* the "ready" processes (actually, the indices in the "proc" array */

/* of the ready processes). The number of entries in the queue is */

/* nready. If nready > 0, then the first entry in the queue is in */

/* ready[0], and the last entry is in ready[nready-1]. This could be */

/* made a lot "swifter" with dynamic allocation (i.e. using a linked */

/* list for the queue), but in this case, we're not so concerned with */

/* speed. */

/*--------------------------------------------------------------------*/

int nready; /* # of ready processes (0..np) */

int ready[MAXPROC]; /* the ready queue (each in 1..np) */

int running; /* ID of the running process (1..np) */

/*------------------------------------------------------------------*/

/* The next three arrays are used to record information about the */

/* resources. rstate[r] is 0 if resource r is not being used. If */

/* resource r is being used by process p, then rstate[r] = p. */

/* If there are any processes waiting for the resource, then their */

/* process IDs will appear on a queue associated with the resource */

/* being awaited. For example, suppose process 3 "owns" resource 4, */

/* and processes 1 and 2 (in that order) have attempted to gain */

/* mutually-exclusive access to the resource. We'd then have this: */

/* rstate[4] = 3 process 3 owns resource 4 */

/* nrw[4] = 2 2 procs are waiting for resource 4 */

/* rw[4][0] = 1 process 1 is first waiting proc */

/* rw[4][1] = 2 process 2 is second waiting proc */

/*------------------------------------------------------------------*/

int rstate[MAXRSRC+1]; /* resource state */

/* 0 = unused */

/* 1..np = owned by process */

int rw[MAXRSRC+1][MAXPROC+1]; /* queues of waiting processes */

int nrw[MAXRSRC+1]; /* # of procs on each queue */

/*---------------------------------------------------------------*/

/* Node of the resource graph. There is an edge from a resource */

/* node to a process node to indicate the process "owns" the */

/* resource. An edge from a process to a resource indicates the */

/* process is awaiting the resource. Thus there is at most one */

/* outgoing edge from each node. */

/*---------------------------------------------------------------*/

/* Subscripts 0 to np-1 correspond to processes 0 to np-1. */

/* Subscripts np to np+nr-1 correspond to resources 0 to nr-1. */

/*---------------------------------------------------------------*/

struct node { /* process/resource node */

int e; /* in a process node, e = index of awaited resource */

/* in a resource node, e = index of owning process */

/* if no edge exists, then e = -1. */

int v; /* has node been visited yet? */

} prn[MAXPROC+MAXRSRC];

/*-----------------------------------------------*/

/* Display the state of processes and resources. */

/* This function is optional, and is used for */

/* insight into the data structures and the */

/* diagnosis of flawed code. */

/*-----------------------------------------------*/

void statedump(void)

{

int i, j;

printf("State at time %d: ", t);

printf("Processes: ");

for(i=1;i<=np;i++) {

printf(" Process %d: ", i);

switch(proc[i].state) {

case -1: printf("finished "); break;

case 0: printf("ready/running "); break;

default: printf("waiting on resource %d ", proc[i].state); break;

}

}

printf(" Resources: ");

for(i=1;i<=nr;i++) {

printf(" Resource %d: ", i);

if (rstate[i] == 0)

printf("unused ");

else {

printf("owned by process %d; ", rstate[i]);

if (nrw[i] == 0)

printf("awaited by no processes. ");

else if (nrw[i] == 1)

printf("awaited for by process %d ", rw[i][0]);

else {

printf("awaited for by processes %d", rw[i][0]);

for(j=1;j

printf(", %d", rw[i][j]);

putchar(' ');

}

}

}

printf("-------------------------------- ");

}

/*---------------------------------------------------------------------------*/

/* Get the next simulation and return 1; return 0 at end of file, -1 on err. */

/*---------------------------------------------------------------------------*/

/* This input function is very agressive in its attempt to detect bad input. */

/* As the input data is guaranteed to be correct, student solutions could */

/* have substantially less code here. But, since this works, and is provided */

/* for your use, there probably isn't much reason to change it. Obviously, */

/* you should verify you understand what it's doing! */

/*---------------------------------------------------------------------------*/

int getinput(void)

{

int i, j;

int r; /* fscanf result */

int c; /* an action letter (L, U, or C) */

int v; /* value for the action */

int oldv; /* used for overflow test */

int got1; /* did we get at least one digit? */

r = fscanf(f,"%d%d",&np,&nr); /* # processes, # resources */

if (r != 2) {

fprintf(stderr,"Error reading np and nr. ");

return -1;

}

if (np == 0 && nr== 0) return 0; /* end of input? */

for (i=1;i<=np;i++) { /* get data for processes 1 ... np */

r = fscanf(f,"%d",&proc[i].ns); /* # of steps for process i */

if (r != 1) {

fprintf(stderr,"Error reading number of actions for process %d ",

i);

return -1;

}

c = fgetc(f);

for (j=0;j

while (c == ' ' || c == '\t') /* skip blanks and tabs */

c = fgetc(f);

if (c != 'L' && c != 'U' && c != 'C') {

fprintf(stderr,"Bad action for process %d step %d. ", i, j);

return -1;

}

proc[i].a[j] = c; /* save action for step j */

got1 = 0; /* we've got no digits yet */

v = 0;

c = fgetc(f);

while(isdigit(c)) {

got1 = 1;

oldv = v;

v = v * 10 + c - '0';

if ((v - c + '0') / 10 != oldv) {

fprintf(stderr,

"Overflow reading n for process %d step %d. ",

i, j);

return -1;

}

c = fgetc(f);

}

if (!got1) {

fprintf(stderr,"Missing value for process %d step %d ", i, j);

return -1;

}

proc[i].n[j] = v;

switch(proc[i].a[j]) {

case 'L':

case 'U':

if (proc[i].n[j] < 1 || proc[i].n[j] > nr) {

fprintf(stderr,"Bad value for process %d "

"step %d. ", i, j);

return -1;

}

break;

case 'C':

if (proc[i].n[j] < 1) {

fprintf(stderr,"Bad value for process %d "

"step %d. ", i, j);

return -1;

}

break;

default: /* this should not be possible */

fprintf(stderr,"Unrecognized action character for "

"process %d step %d. ", i, j);

return -1;

}

}

while (c == ' ' || c == '\t') /* skip trailing blanks, tabs */

c = fgetc(f);

if (c != ' ') {

fprintf(stderr,"Unrecognized input after actions for "

"process %d. ", i);

return -1;

}

}

return 1;

}

/*-------------------------------------------------------------------*/

/* Deadlock detection algorithm. */

/* See if deadlock exists in the current state. */

/* */

/* If deadlock is detected, display the appropriate information (the */

/* identity of the processes and resources involved) and return 1. */

/* */

/* If deadlock is not detected, return 0. */

/*-------------------------------------------------------------------*/

/* The argument s is the subscript of the node in the resource graph */

/* with which the cycle detection algorithm begins. */

/*-------------------------------------------------------------------*/

/* HIGHLY RECOMMENDED: READ THE FILE NAMED 'cycle.txt' in the */

/* csci4500 directory on Loki. Make certain you understand how the */

/* algorithm works before attempting to implement it! */

/*-------------------------------------------------------------------*/

int cycle(int s)

{

/* XXX - TO BE WRITTEN */

return 0; /* DUMMY FUNCTION -- ALWAYS RETURNS 0 */

}

/*---------------------------------------------------------*/

/* Display IDs of processes in cycle starting with node i. */

/*---------------------------------------------------------*/

void putpcycle(int i)

{

/* XXX - TO BE WRITTEN */

}

/*---------------------------------------------------------*/

/* Display IDs of resources in cycle starting with node i. */

/*---------------------------------------------------------*/

void putrcycle(int i)

{

/* XXX - TO BE WRITTEN */

}

/*----------------------------------------------------------------*/

/* Build a resource graph representing the current system state. */

/* Then check for a deadlock starting with each process node. */

/* */

/* If a deadlock is detected, display the processes and resources */

/* involved in the deadlock and return any non-zero value. */

/* */

/* If *NO* deadlock is detected, return 0. */

/*----------------------------------------------------------------*/

/* Note that a solution might choose to keep the resource graph */

/* "up to date" as the simulation of the processes continues. */

/* That approach would likely be faster than rebuilding the graph */

/* after each action, but we're not concerned with speed here. */

/* And this approach is less likely to have errors... */

/*----------------------------------------------------------------*/

int deadlock(void)

{

int i;

int dproc[MAXPROC]; /* IDs of processes involved in a deadlock */

int ndproc;

int drsrc[MAXRSRC]; /* IDs of resources involved in a deadlock */

int ndrsrc;

/*-------------------------------*/

/* Construct the resource graph. */

/*-------------------------------*/

/* XXX - TO BE WRITTEN */

/*-----------------------------------------------------------------*/

/* Check for a cycle starting at every possible node in the graph. */

/*-----------------------------------------------------------------*/

for(i=0;i

if (cycle(i)) { /* Display the cycle */

printf("Deadlock detected at time %d involving... ", t);

putpcycle(i);

putrcycle(i);

return 1; /* report deadlock detected */

}

return 0; /* report no deadlock detected */

}

/*-----------------------------------------------------*/

/* Add process p (1..np) to the end of the ready queue */

/*-----------------------------------------------------*/

void makeready(int p)

{

ready[nready++] = p;

}

/*--------------------------------------------------*/

/* Add process p (1..np) to the end of the queue of */

/* processes waiting on resource r (1..nr) */

/*--------------------------------------------------*/

void makewait(int p, int r)

{

rw[r][nrw[r]] = p;

nrw[r]++;

}

/*---------------------------------------------------------------*/

/* Process options. Then read input data, simulate and check for */

/* deadlock, and then repeat until end of input. */

/*---------------------------------------------------------------*/

int main(int argc, char *argv[])

{

int i, ip, n;

int dd; /* non-zero if deadlock detected */

char a;

/*-----------------*/

/* Handle options. */

/*-----------------*/

while (argc > 1 && argv[1][0] == '-') {

if (!strcmp(argv[1],"-v")) {

trace++;

argc--;

argv++;

continue;

}

fprintf(stderr,"Unknown option %s ", argv[1]);

exit(1);

}

/*------------------------------------*/

/* Setup stream f for the input data. */

/*------------------------------------*/

if (argc > 2) {

fprintf(stderr,"Usage: prog2 [-v] [inputfilename] ");

exit(1);

}

if (argc == 2) {

f = fopen(argv[1],"r");

if (f == NULL) {

fprintf(stderr,"Cannot open %s for input. ", argv[1]);

exit(1);

}

} else

f = stdin;

for (simno=1;;simno++) {

/*---------------------------------*/

/* Get the next set of input data. */

/*---------------------------------*/

if (getinput() != 1)

break;

t = 0; /* set simulation time */

/*---------------------------------*/

/* Initialize the data structures. */

/*---------------------------------*/

for (i=1;i<=np;i++) { /* initialize each process */

proc[i].ip = 0; /* first action index */

proc[i].state = 0; /* process state is ready */

proc[i].runtime = 0; /* no time used yet */

ready[i-1] = i; /* setup initial ready queue */

}

nready = np;

for (i=1;i<=nr;i++) { /* initialize each resource */

rstate[i] = 0; /* unused */

nrw[i] = 0; /* no waiting processes */

}

printf("Simulation %d ", simno);

/*-----------------------------------------------------------*/

/* Perform deadlock detection and simulate a process action. */

/*-----------------------------------------------------------*/

for(;;) {

dd = deadlock(); /* check for deadlock */

if (dd) /* if it was detected */

break;

/*---------------------------------------------*/

/* Get a process from the ready queue to run. */

/* If there are no ready processes, we must be */

/* done or deadlocked. */

/*---------------------------------------------*/

if (nready == 0) break; /* no ready processes */

running = ready[0]; /* first ready process */

for (i=1;i

ready[i-1] = ready[i]; /* but who cares? */

nready--;

/*--------------------------------------*/

/* Get ip, a, and n for running process */

/*--------------------------------------*/

ip = proc[running].ip;

a = proc[running].a[ip];

n = proc[running].n[ip];

if (trace) {

printf("%d: ", t);

printf("process %d: ", running);

printf("%c%d ", a, n);

}

/*--------------------------------------------*/

/* If the process is requesting a resource... */

/*--------------------------------------------*/

if (a == 'L') {

/*------------------------------*/

/* If the resource is available */

/*------------------------------*/

if (rstate[n] == 0) {

/* XXX - TO BE WRITTEN */

/*-----------------------------------*/

/* If the resource is not available. */

/* Time does NOT increase here! */

/*-----------------------------------*/

} else {

if (trace) printf("\t(resource %d unavailable) ", n);

makewait(running,n); /* add to waiters */

proc[running].state = n; /* mark proc blocked */

}

}

/*-------------------------------------------*/

/* If the process is releasing a resource... */

/*-------------------------------------------*/

else if (a == 'U') {

rstate[n] = 0; /* resource unused now */

if (trace) printf("\t(resource %d released) ", n);

/*---------------------------------------------*/

/* If any processes are waiting on the reource */

/*---------------------------------------------*/

if (nrw[n] > 0) {

/*--------------------------------------*/

/* Make the first waiting process ready */

/*--------------------------------------*/

if (trace) printf("\t(process %d unblocked) ", rw[n][0]);

/* XXX - TO BE WRITTEN */

}

/*----------------------------------------*/

/* The currently running process advances */

/*----------------------------------------*/

if (ip+1 == proc[running].ns) {

proc[running].state = -1; /* done */

proc[running].endtime = t+1; /* end time */

if (trace) printf("\t(process %d terminated) ", running);

} else {

proc[running].ip++;

makeready(running);

}

proc[running].runtime++;

t++;

}

/*-------------------------------*/

/* If the process is "computing" */

/*-------------------------------*/

else if (a == 'C') {

n--; /* reduce remaining computation time */

/* XXX - TO BE WRITTEN */

}

/*----------------------------------------------------------*/

/* This point should never be reached if the data is valid. */

/*----------------------------------------------------------*/

else {

fprintf(stderr,"Bad action (%d) ", a);

exit(1);

}

}

if (!dd) {

/*----------------*/

/* If no deadlock */

/*----------------*/

printf("All processes successfully terminated. ");

for (i=1;i<=np;i++) {

printf("Process %d: run time = %d, ended at %d ",

i, proc[i].runtime, proc[i].endtime);

}

}

putchar(' ');

}

}