Solved–Assignment 4 –Solution

Description

Q1 – Written question (5 marks)

Provide a simple example of a system in an unsafe state, where the processes could finish without entering a deadlock. Show the state, and two sequences of execution: one leading to a deadlock and the other leading to the completion of all processes.

Hint: you should not need more than 3 processes and one resource type (with multiple instances).

Q2 – Written question (5 marks)

In a system consisting of four processes and five resource types, the current allocation and maximum needs are as follows:

Process Allocation Maximum Available
P0 10211 11213 0 0 x 1 2
P1 20110 22210
P2 11010 21310
P3 11110 11221

What is the smallest value of ‘x’ that can keep the system in a safe state? Once you find the ‘x’ value, find a safe execution order using the Safety Algorithm we discussed in the lecture. Include a step-by-step walk-through of the Safety Algorithm.

Q3 – Programming question (20 marks)

Write a program that implements the Banker’s Algorithm. Your program will determine whether there is a safe execution sequence for a given set of processes, and a request. The process information will be provided in a configuration file, specified as a command-line argument. The configuration file will contain the number of processes (numProc), the number of resource types (numResourceTypes), currently available resources (available), current resource allocation for all processes, the maximum resources required by each process, and a request (request) by process ‘i’. For instance, the example we discussed during lectures, can be translated into the following configuration file (config1.txt):

numProc = 5

numResourceTypes = 3
available = <3 3 2>
P0<010><753>

P1<200><322>
P2<302><902>

P3<211><222>

CPSC 457: Assignment 4 1

P4<002><433>

request 1 = <1 0 2>

The last line represents a request by process #1 for resources (1,0,2). If you run your program on the above configuration file, the output should look as follows:

$ ./banker config1.txt

Grant request <1 0 2> from P1.
Sequence: P1, P3, P0, P2, P4.

If the request can be granted, your program needs to output a possible execution sequence, as above. If the request cannot be granted, the output of your program should look like this:

$ ./banker config2.txt

Reject request <1 0 2> from P1.

Reason: request would result in unsafe state.

If the request cannot be granted, the program should output the reason for rejection. Possible reasons for rejecting a request include:

request would result in an unsafe state,

request is invalid (exceeding declared max for process), not enough resources available.

You are free to use the banker.cpp code in the Appendix 1 as a starting point. If you do, all you have to do is implement the Banker::isSafe() method.

Submission

You should submit 3 files for this assignment:

Answers to the written questions combined into a single file, called either report.txt or report.pdf. Do not use any other file formats.

Your solutions to Q3 in files called banker.c or banker.cpp.

Since D2L will be configured to accept only a single file, you will need to submit an archive, eg.
assignment4.tgz. To create such an archive, you could use a command similar to this:

$ tar czvf assignment4.tgz report.pdf banker.cpp

General information about all assignments:

All assignments must be submitted before the due date listed on the assignment. Late assignments or components of assignments will not be accepted for marking without approval for an extension beforehand. What you have submitted in D2L as of the due date is what will be marked.

Extensions may be granted for reasonable cases, but only by the course instructor, and only with the receipt of the appropriate documentation (e.g. a doctor’s note). Typical examples of reasonable cases for an extension include: illness or a death in the family. Cases where extensions will not be granted include situations that are typical of student

CPSC 457: Assignment 4 2

life, such as having multiple due dates, work commitments, etc. Forgetting to hand in your assignment on time is not a valid reason for getting an extension.

After you submit your work to D2L, make sure that you check the content of your submission. It’s your responsibility to do this, so make sure that you submit your assignment with enough time before it is due so that you can double-check your upload, and possibly re-upload the assignment.

All assignments should include contact information, including full name, student ID and tutorial section, at the very top of each file submitted.

Assignments must reflect individual work. Group work is not allowed in this class nor can you copy the work of others. For further information on plagiarism, cheating and other academic misconduct, check the information at this link: http://www.ucalgary.ca/pubs/calendar/current/k-5.html.

You can and should submit many times before the due date. D2L will simply overwrite previous submissions with newer ones. It’s better to submit incomplete work for a chance of getting partial marks, than not to submit anything.

Only one file can be submitted per assignment. If you need to submit multiple files, you can put them into a single container. The container types supported will be ZIP and TAR. No other formats will be accepted.

Assignments will be marked by your TAs. If you have questions about assignment marking, contact your TA first. If you still have questions after you have talked to your TA then you can contact your instructor.

Appendix 1 – banker.cpp for Q9

/*

* banker.cpp

*
* Student Name:
* Student Number:

*
* Class: CPSC 457 Fall 2017
* Instructor: Pavol Federl

*
* Copyright 2017 University of Calgary. All rights reserved.
*/

#include

#include
#include
#include
#include

using namespace std;

class Banker
{
private:

int numProc; // the number of processes

CPSC 457: Assignment 4 3

int numResources; // the number of resources
int * available; // number of available instances of each resource
int ** max; // the max demand of each process, e.g., max[i][j] = k
// means process i needs at most k instances
// of resource j
int ** allocation;// number of resource instances already allocated
int ** need; // number of resource instances needed by each process

public:

/* Initializing the vectors and matrixes for the Banker’s Algorithm.
* Takes ownership of all arrays.

*
* @param avail The available vector
* @param mThe max demand matrix
* @param alloc The allocation matrix
* @param pThe number of processes
* @param rThe number of resources

*/

Banker (int * avail, int ** m, int ** alloc, int p, int r) { numProc = p;
numResources = r;
/ Setup the available vector, the max matrix, and the
/ allocation matrix
available = avail;
max = m;
allocation = alloc;

/ Initialize the need matrix need = new int*[numProc];

for (int i = 0; i < numProc; i++) need[i] = new int[numResources];
}

/* Destroy the vectors and matrixes
*/
~Banker() {
numProc = 0;
numResources = 0;

/ Free all allocated memory space delete[] available;

for (int i = 0; i < numProc; i++)
{

delete[] need[i]; delete[] max[i]; delete[] allocation[i];
}

delete[] need; delete[] max; delete[] allocation;
}
/* Check whether it is safe to grant the request
* @param pid The process that is making the request
* @param req The request
* @param sequenceOrReason The safe execution sequence returned
* by the algorithm or reason for rejection

CPSC 457: Assignment 4 4

* @return Whether granting the request will lead to a safe state.

*/

bool isSafe (int pid, int * req, string & sequenceOrReason) { sequenceOrReason = “Not implemented yet.”;
return false;

}
};

int main (int argc, char * const argv[]) {
ifstream config; // Configuration file
string conffile; // The configuration file name
int numProc; // The number of processes
int numResources; // The number of resources
string sequenceOrReason; // The execution sequence returned by
// the Banker’s Algorithm
int i, j, index; // Indices for the vectors and matrixes
int pid; // The ID of the process that is making the
// request
string reqStr; // The request vector in string format

/ Read in the config file name from the commanda-line arguments if (argc < 2) {

cout << “Usage: banker \n”; return 0;

}
else {
conffile = argv[1];
}

/ Open the file

config.open(conffile.c_str());

// Get the number of process and the number of resources
string line, var, equal; // strings for parsing lines in cfg. file
getline(config, line);
istringstream iss(line);
iss >> var >> equal >> numProc; // Get the number of processes
iss.clear();

getline(config, line);

iss.str(line);

iss >> var >> equal >> numResources; // Get the number of resources iss.clear();

/ Create the available vector, the max matrix, and the allocation

/ matrix according to the number of processes and the number of
/ resources

int * available = new int[numResources]; int ** max = new int*[numProc];

int ** allocation = new int*[numProc];

for (int i = 0; i < numProc; i++)
{
max[i] = new int[numResources];

allocation[i] = new int[numResources];
}

// Get the available vector

CPSC 457: Assignment 4 5

getline(config, line);

replace(line.begin(), line.end(), ‘<‘, ‘ ‘); // Remove “<” and “>” replace(line.begin(), line.end(), ‘>’, ‘ ‘); iss.str(line);

iss >> var >> equal;

for (j = 0; j < numResources; j++) // Read in the “available” vector iss >> available[j];
iss.clear();

/ Get the max matrix and the allocation matrix for (i = 0; i < numProc; i++)

{
getline(config, line);

replace(line.begin(), line.end(), ‘<‘, ‘ ‘); replace(line.begin(), line.end(), ‘>’, ‘ ‘);

iss.str(line);
iss >> var;
index = atoi(&var.at(1)); // Get the process ID

if (index < 0 || index >= numProc)
{

cerr << “Invalid process ID: ” << var << endl; return 0;
}

/ Get the number of resources allocated to process “index”. for (j = 0; j < numResources; j++) iss >> allocation[index][j];

/ Get the max allocation to process “index”.

for (j = 0; j < numResources; j++) iss >> max[index][j];
iss.clear();
}

// Get the request vector
int * request = new int[numResources];
getline(config, line);
reqStr = line.substr(line.find(‘<‘), line.find(‘>’) – line.find(‘<‘) + 1);

replace(line.begin(), line.end(), ‘<‘, ‘ ‘); replace(line.begin(), line.end(), ‘>’, ‘ ‘); iss.str(line);
iss >> var >> pid >> equal;

for (j = 0; j < numResources; j++) // Read in the “request” vector iss >> request[j];
iss.clear();

/ Check the request using the Banker’s algorithm. Banker * banker = new Banker(

available, max, allocation, numProc, numResources); if (banker -> isSafe(pid, request, sequenceOrReason))

cout << “Grant request ” << reqStr << ” from P” << pid << “.\n” << “Sequence: ” << sequenceOrReason << “.\n”;
else

cout << “Reject request ” << reqStr << ” from P” << pid << “.\n” << “Reason: ” << sequenceOrReason << “\n”;

}

CPSC 457: Assignment 4 6