Code where the XXX are placed

#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) */ 

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 
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 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 */ /* if deadlock detected return 1; */ /* else */ 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 */ printf("Cycle found involving these processes: "); q = p; for (;;) { printf(" %d ", q); q = rg[q].e; q = rg[q].e; if (p == q) break; } } /*---------------------------------------------------------*/ /* Display IDs of resources in cycle starting with node i. */ /*---------------------------------------------------------*/ void putrcycle(int i) { /* XXX - TO BE WRITTEN */ printf("Resources involved: "); } /*----------------------------------------------------------------*/ /* 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... */ /*----------------------------------------------------------------*/ 
 
nt 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 
/*-----------------*/ /* 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 
/*-------------------------------------------*/ 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(' '); } }