Question

1. Assume we have the following resources: • 4 graphic displays • 3 printers • 1 disks Consider we have already allocated these resources among four processes as demonstrated by the following matrix named Allocation. Process Name Graphics Printers Disk Drives Process A 0 1 0 Process B 0 0 1 Process C 0 1 0 Process D 1 0 0 The following is the matrix to show the number of each resources requested; we call this matrix Request. Process Name Graphics Printers Disk Drives Process A 2 0 0 Process B 2 2 0 Process C 1 0 1 Process D 0 2 1 a. Apply Deadlock Detection Algorithm and check whether any deadlock exists. b. Suppose now the Process B requests one additional instance of Graphics, and Process C requests two additional instances of Graphics and one additional instance of Disk Drives, whether this can be granted?

Answer 1

a.

The allocation matrix :

Process	Graphic Display	Printer	Disk
A	0	1	0
B	0	0	1
C	0	1	0
D	1	0	0

Total number of resources in the system :

4 Graphic Displays, 3 Printers and 1 disks.

The available vector is obtained by subtracting the sum of all instances of a device from the total number of instances present for that device.

So, the available vector is :

Graphic Display	Printer	Disk
3	1	0

The need matrix is :

Process	Graphic Display	Printer	Disk
A	2	0	0
B	2	2	0
C	1	0	1
D	0	2	1

The deadlock detection algorithm refers to the safety algorithm as follows :

Step 1 :

Initialize a variable Work = Available = 3 1 0  

Initialize a boolean array variable flag[i] = false for all processes i = A, B. C and D.

Step 2 :

Find a process such that the need value of the process is less than the work vector and flag value is false.

The process selected is process A.

Update the value of Work as Work = Old value of Work + Allocation value of process A

= 3 1 0 + 0 1 0 = 3 2 0

Assign flag value for process A as true.

Step 3 :

Find a process such that the need value of the process is less than the work vector and flag value is false.

The process selected is process B.

Update the value of Work as Work = Old value of Work + Allocation value of process B

= 3 2 0 + 0 0 1

= 3 2 1

Assign flag value for process B as true.

Step 4 :

Find a process such that the need value of the process is less than the work vector and flag value is false.

The process selected is process C.

Update the value of Work as Work = Old value of Work + Allocation value of process C

= 3 2 1 + 0 1 0

= 3 3 1

Assign flag value for process C as true.

Step 5 :

Find a process such that the need value of the process is less than the work vector and flag value is false.

The process selected is process D.

Update the value of Work as Work = Old value of Work + Allocation value of process D

= 3 3 1 + 1 0 0

= 4 3 1

Assign flag value for process D as true.

Since the values of all processes are true, the resultant safe sequence is A, B, C and D and hence, there is no deadlock.

b.

Process B has requested for 1 instance of Graphic Display. Process C has requested 2 instances of Graphic Displays and one instance of Disk.

Applying Banker's algorithm :

For process B,

• Request vector which is 1 0 0 is less than or equal to Need vector which is 2 2 0.
• Request vector as of now for process B will be 1 0 0 and it is less than or equal to value of available which is 3 1 0. So, proceed to the next step.
• Available vector = Available vector old value - Request vector of process B that is 3 1 0 - 1 0 0 = 2 1 0.
• Allocation value of process B = Old allocation value + Request vector of process B that is 0 0 1 + 1 0 0 = 1 0 1.
• Need value of process B = Old value of Need - Request vector of process B that is 2 2 0 - 1 0 0 = 1 2 0.

For process C,

• Request vector which is 2 0 1 is more than the Need vector which is 1 0 1. So, this results in an error and the algorithm cannot proceed.

Hence, collectively if process B and process C requests for the given resources, then the request cannot be granted.