This is in C. The partial solution "template" for the assignment is provided below which is well commented. NO OTHER LANGUAGES WILL BE ACCEPTED.

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. In 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, and use resources. Each such action consists of a capital letter (L, U or C) 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, then the process that performs the action (say process p) requests exclusive use of the resource identified by the associated value of 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 first-in-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 Instructors Solution

The instructors solution (in executable form) is available in the default directory. By default, the program will read its input data from the standard input. Alternately, the name of an input file may be specified on the command line. The solution also provides a trace facility that may help you understand the sequence of events in a simulation. This trace is turned on if the v option is specified on the command line. Thus the program invocation has this syntax:

./prog2 [-v] [inputfilename]

The trace output contains two types of information. Each time an action is attempted, the trace output will display the simulation time, the process, and the action involved. As you can see from the sample output (below), the computation time parameter will continually be reduced as the process makes progress toward completion.

The second type of information shown in parentheses in the sample output indicates when a resource is allocated, when an allocation was unsuccessful, when a resource was deallocated (released), when a process was unblocked (awakened) because a resource on which it was waiting was deallocated, and finally when a process terminated. This should all be obvious from examination of the sample output.

The Input Data

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.

The Assignment

Write and test a program in C to carry out the simulation of multiple processes executing the sequences of resource requests and computation specified by the input data, checking after each resource allocation request for the existence of deadlock by attempting to find a cycle in the resource graph. If no deadlocks occur during execution, then for each process indicate the total run time and the time when the process completed. If a deadlock does occur, indicate that fact, the time when the deadlock was detected, and the identification of the processes and resources involved in the circular wait. The samples shown below illustrate the desired output format. No extraneous output (e.g. debugging information) should appear in your output, and tracing information should not appear in the output from your solution.

The program must read from the standard input and write to the standard output. To submit the source code for your solution (which should be named prog2 with a suitable suffix), place it and a suitable makefile in a directory named csci4500-172-prog2 located just below your home directory on loki. (If your submission requires special consideration you may add a README file to the submission directory.) You will need to create this directory yourself. Do not put other files in this directory, and do not alter the contents of the directory after the due date! In particular, there should be no object or executable files, or input or output data files in the directory.

You may use any cycle detection algorithm you wish to detect deadlock. A reasonably explicit description of a cycle detection algorithm that is appropriate for this problem is provided on Loki in the file named cycle.txt in the csci4500 directory.

All processes will have at least one action item.

No invalid execution sequences will appear in the input. In particular, no process will attempt to release a resource it does not already possess, and no process will attempt to obtain a resource it already possesses. (There is only one unit of each resource available.)

The template solution provided below is not a complete solution, but the parts of the template that require additional development have been appropriately marked.

Note that you are not required to work in a group. But even if you work by yourself, it is still appropriate to include your name as the author in the source code.

Sample Input and Output

The sample input shown below is in the file prog2.input on loki. It includes five test cases. The output was produced from the instructors solution for this assignment. Although the samples are representative of the input that will be used to test your solution, you should certainly create additional test cases yourself.

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

Expected Output for the Sample Input (with trace enabled)

Simulation 1

0: process 1: L1

(resource 1 allocated to process 1)

1: process 1: L2

(resource 2 allocated to process 1)

2: process 1: C10

3: process 1: C9

4: process 1: C8

5: process 1: C7

6: process 1: C6

7: process 1: C5

8: process 1: C4

9: process 1: C3

10: process 1: C2

11: process 1: C1

12: process 1: U1

(resource 1 released)

13: process 1: U2

(resource 2 released)

(process 1 terminated)

All processes successfully terminated.

Process 1: run time = 14, ended at 14

Simulation 2

0: process 1: L1

(resource 1 allocated to process 1)

1: process 2: L1

(resource 1 unavailable)

1: process 3: L3

(resource 3 allocated to process 3)

2: process 1: L2

(resource 2 allocated to process 1)

3: process 3: C5

4: process 1: C2

5: process 3: C4

6: process 1: C1

7: process 3: C3

8: process 1: U1

(resource 1 released) (process 2 unblocked)

9: process 3: C2

10: process 2: L1

(resource 1 allocated to process 2)

11: process 1: U2

(resource 2 released)

(process 1 terminated)

12: process 3: C1

13: process 2: L2

(resource 2 allocated to process 2)

14: process 3: U3

(resource 3 released)

15: process 2: C2

16: process 3: C2

17: process 2: C1

18: process 3: C1

(process 3 terminated)

19: process 2: U1

(resource 1 released)

20: process 2: U2

(resource 2 released)

(process 2 terminated)

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

0: process 1: L1

(resource 1 allocated to process 1)

1: process 2: L2

(resource 2 allocated to process 2)

2: process 1: L2

(resource 2 unavailable)

2: process 2: L1

(resource 1 unavailable)

Deadlock detected at time 2 involving...

Processes 1, 2

Resources 2, 1

Simulation 4

0: process 1: L1

(resource 1 allocated to process 1)

1: process 2: L2

(resource 2 allocated to process 2)

2: process 3: L3

(resource 3 allocated to process 3)

3: process 1: C3

4: process 2: C3

5: process 3: C3

6: process 1: C2

7: process 2: C2

8: process 3: C2

9: process 1: C1

10: process 2: C1

11: process 3: C1

12: process 1: L2

(resource 2 unavailable)

12: process 2: L3

(resource 3 unavailable)

12: process 3: L1

(resource 1 unavailable)

Deadlock detected at time 12 involving...

Processes 1, 2, 3

Resources 2, 3, 1

Simulation 5

0: process 1: L1

(resource 1 allocated to process 1)

1: process 2: C3

2: process 3: C3

3: process 4: L4

(resource 4 allocated to process 4)

4: process 5: L3

(resource 3 allocated to process 5)

5: process 6: L6

(resource 6 allocated to process 6)

6: process 7: L5

(resource 5 allocated to process 7)

7: process 1: C5

8: process 2: C2

9: process 3: C2

10: process 4: C6

11: process 5: C5

12: process 6: C5

13: process 7: C2

14: process 1: C4

15: process 2: C1

16: process 3: C1

17: process 4: C5

18: process 5: C4

19: process 6: C4

20: process 7: C1

21: process 1: C3

22: process 2: L3

(resource 3 unavailable)

22: process 3: L2

(resource 2 allocated to process 3)

23: process 4: C4

24: process 5: C3

25: process 6: C3

26: process 7: L4

(resource 4 unavailable)

26: process 1: C2

27: process 3: C2

28: process 4: C3

29: process 5: C2

30: process 6: C2

31: process 1: C1

32: process 3: C1

33: process 4: C2

34: process 5: C1

35: process 6: C1

36: process 1: L2

(resource 2 unavailable)

36: process 3: U2

(resource 2 released)

(process 1 unblocked)

37: process 4: C1

38: process 5: L5

(resource 5 unavailable)

38: process 6: L2

(resource 2 allocated to process 6)

39: process 1: L2

(resource 2 unavailable)

39: process 3: C3

40: process 4: L3

(resource 3 unavailable)

Deadlock detected at time 40 involving...

Processes 4, 5, 7

Resources 3, 5, 4

File cycle.txt

A Simple Cycle Detection Algorithm

==================================

Assume we've got a set of processes and single-use resources, as is the case

with the deadlock detection problem. Here's a simple way to determine if there

is a cycle in the resource graph, and how to identify the processes and

resources involved with the cycle.

Step 1 -- Build the resource graph.

===================================

Assume we've got an array of nodes, each of which has the following

components:

e - integer (subscript) of the "pointed-to" node (to which there

is an edge in the resource graph).

In a process node, e is the subscript of the node for the

resource being awaited (if any).

In a resource node, e is the subscript of the node for the

owner process (if any).

If there is no edge from the node, then set e to -1 (which

is interpreted by the algorithm as indicating no edge exists).

v - zero if a node hasn't yet been visited in a depth-first search,

and non-zero if the node has been visited.

Note that there is at most a single edge FROM a process to a resource, and

a single edge FROM a resource to a process. But there may be multiple edges

pointing TO a process or a resource. This is why we only need a single entry

in each node (namely 'e') that identifies the "pointed-to" node.

If we've got a maximum of MAXPROC processes and MAXRSRC resources, then the

array that represents the nodes in the resource graph will need no more than

MAXPROC + MAXRSRC entries. So you could write this:

struct node {

int e;

int v;

} rg[MAXPROC+MAXRSRC];

("rg" is used as the name to suggest this is a resource graph.)

Assume in a specific case that we have np processes and nr resources.

Associate subscripts 0 through np - 1 with processes.

Associate subscripts MAXPROC through MAXPROC + nr - 1 with resources.

That is, the element of rg that will be associated with resource 4

if there are a maximum of 10 processes (MAXPROC=10) will be 13.

Using the current state of processes and resources, set up the appropriate

entries in the rg array.

EXAMPLE. Suppose MAXPROC = 10 and MAXRSRC = 20, as it does in the deadlock

problem. If we have 2 processes and 2 resources, then we'd use the following

array entries:

rg[0] - process 0

rg[1] - process 1

rg[10] - resource 0

rg[11] - resource 1

Assume process 0 owns resource 0 and is waiting for resource 1.

Assume process 1 owns resource 1 and is waiting for resource 0.

We'd then have rg[0].e = 11, rg[1].e = 10, rg[10].e = 0, and rg[11].e = 1.

Naturally we don't care about the other entries.

END OF EXAMPLE.

Step 2 -- Search for a cycle in the graph, starting from each process node.

===========================================================================

We assume the resource graph has been properly constructed, and that np and

nr indicate the number of processes and resources, respectfully.

The search is basically a depth-first search, with pseudo-code that looks

like this (Q and P are integer subscripts):

A: for each process node P (that is, for P = 0, 1, ..., np-1):

Set v = 0 in all nodes (all process and resource nodes)

Set rg[P].v to 1 (mark node P as having been visited).

Set Q = P.

B: Set Q = rg[Q].e

If Q is -1 (no edge from the previous node), then repeat the

search starting at the next process node (that is, continue

the for loop at A with the next value of P).

If Q is NOT -1 (there is an edge from the node being visited):

If Q = P (that is, we're returned to the starting node),

then we have found a cycle starting with process P.

So stop the depth-first search and go to step 3 (below).

If Q is marked (that is, if rg[Q].v is non-zero), we have

detected a cycle, but it didn't begin with P. Go back to

the loop A and repeat for the next valid value of P.

Otherwise mark node Q as having been visited (rg[Q].v = 1),

and repeat from B.

If we reach this point (we did a depth-first search starting with each

process and didn't find any cycles), then there is no deadlock.

Step 3 -- Display the processes and resources involved in the cycle.

====================================================================

We now know there is a cycle beginning with process P. So we can easily display

the IDs of the processes involved by just following the edges in the graph

starting with process P:

Set Q = P

X: Print process Q's identification

Set Q = rg[Q].e (follow edge to resource wanted by Q)

Set Q = rg[Q].e (follow edge to process owning resource Q)

If Q is not P, repeat from X.

We can do almost the same thing for resources; just skip the first node (P).

Set R = rg[P].e

Set Q = R

Y: Print resource Q's identification

Set Q = rg[Q].e (follow edge to process owning resource Q)

Set Q = rg[Q].e (follow edge to resource wanted by process Q)

If Q is not R, repeat from Y.

/*Template solution*/

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

/* prog2_temp.c - This is a partial solution, or template, for the */

/* second programming assignment. It is */

/* reasonably well-commented, and those places in which additional */

/* code must be provided are mared with comments like this: */

/* XXX - TO BE WRITTEN */

/* Of course there may be additional places in the code that may be */

/* modified, deleted, or additional code added. The decision of what */

/* to keep, toss, or modify is left to the user. */

/* */

/* REMEMBER THAT THIS IS *NOT* A COMPLETE SOLUTION, NOR WILL IT YIELD */

/* REASONABLE RESULTS IF COMPILED AND EXECUTED. */

/* */

/* Usage: prog2 [-v] [inputfilename] */

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

#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(' ');

}

}