Solution of CS604 Assignment no 3:
Question:
a. Consider a system with five processes: P1, P2, P3, P4, P5and four resource types: R1, R2, R3, R4 with single instance. From the given below information, you are required to determine whether the deadlock exists in the system though deadlock detection strategy for resources with single instance.
P = {P1, P2, P3, P4, P5}
R = {R1, R2, R3, R4}

E = {P1®R1, R1®P2, P2®R2, R2®P3, P3®R3, R3®P4, P4®R4, R4®P5, P5®R5, R5®P1}
b. Consider a system with five processes: P1, P2, P3, P4, P5 and four resource types: R1, R2, R3 and R4 with multiple instances. From the given below information, you are required to determine whether the deadlock occurs in a system though deadlock detection strategy for resources with multiple instances.
P = {P1, P2, P3, P4, P5}
R = {R1, R2, R3, R4}
R1: 5 instances
R2: 3 instances
R3: 2 instances
R4: 4 instances
Consider the system in following state:
 Processes Allocation Request Work R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 P1 0 0 0 0 0 1 0 0 0 0 1 1 P2 0 1 0 1 0 0 1 1 P3 2 0 0 2 0 0 1 1 P4 1 1 0 0 2 1 2 0 P5 2 1 1 0 1 0 0 1
Note: There can be many sequences so you are required to start from top to bottom for “Processes” column. i.e. P1 to P5.
Solution:
a)
P = {P1, P2, P3, P4, P5}
R = {R1, R2, R3, R4}
E = {P1®R1, R1®P2, P2®R2, R2®P3, P3®R3, R3®P4, P4®R4, R4®P5, P5®R5, R5®P1}

****Image is in File below****

Single instance of each resource type
A deadlock exists in the system if and only if the wait for graph contains a cycle. To detect deadlocks the system needs to maintain the wait-for graph and periodically to invoke algorithm that searches for a cycle in the graph.

b)
R1:5 instances, R2:3instances, R3:2instances, R4:4instances

 Processes Allocation Request Work R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 P1 0 0 0 0 0 1 0 0 0 0 1 1 P2 0 1 0 1 0 0 1 1 0 1 1 2 P3 2 0 0 2 0 0 1 1 2 1 1 4 P4 1 1 0 0 2 1 2 0 P5 2 1 1 0 1 0 0 1 4 2 2 4

After execution in system:

 Processes Allocation Request Work R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 P1 0 0 0 0 0 1 0 0 4 2 2 4 P2 0 1 0 1 0 0 1 1 0 1 1 2 P3 2 0 0 2 0 0 1 1 2 1 1 4 P4 1 1 0 0 2 1 2 0 5 3 2 4 P5 2 1 1 0 1 0 0 1 4 2 2 4
Possible Processes are:

< P2, P3, P5, P1, P4 >