Algorithm.

Q2. Define Algorithm.

Ans. A formal set of instructions that can be followed to perform a specific task such as solving a logical or a mathematical problem.

Fit Algorithm.

Q19. Define Fit Algorithm.

Ans. They are the methods used for allocation of the newly created process holes.

Algorithm.

Q5. Define Algorithm.

Ans. Logical sequence of discrete steps that describe a complete solution to a given problem.

Q1. Explain abort one process at a time until the deadlock cycle is eliminated method of Deadlock Recovery of Process Termination.

Ans. This method incurs considerable overhead, since after each process is aborted, a deadlock detection algorithm must be invoked to determine whether any processes are still deadlocked.

Many factors may affect which process is chosen to abort:

1. What the priority of the process is.
2. How long the process has computed and how much longer the process will compute before completing its designated task.
3. How many and what type of resources the process has used (For example: Whether the resources are simple to preempt).
4. How many more resources the process needs in order to complete.
5. How many processes will need to be terminated?
6. Whether the process is interactive or batch.

Q1. What are the processes of recovering from deadlock?

Ans. When a detection algorithm determines that a deadlock exists, several alternative. One is simplyto abort one or more processes to break the circular wait. The other is to preempt some resources from one or more of the deadlocked processes.

1. Process Termination

2. Resource Preemption

Numerical Solved with Deadlock Detection Algorithm

Q3. Use deadlock algorithm, there are five processes and 3 resource type

A -> 7 instances

B -> 2 instances

C -> 6 instances

Process Allocation Request Available
 P0 P1 P2 P3 P4
 A B C 0 1 0 2 0 0 3 0 3 2 1 1 0 0 2
 A B C 0 0 0 2 0 2 0 0 0 1 0 0 0 0 2
 A B C 0 0 0

Solu:

Step 1:

For process P0

request0 available

(0, 0, 0) ≤ (0, 0, 0)

Process P0 will execute.

Available = Available + Allocation

request1 ≤ available

(2, 0, 2) ≤ (0, 1, 0)

P1 must wait.

Step 3:

For process P2

request2 ≤ available

(0, 0, 0) ≤ (0, 1, 0)

P2 will execute.

Available = Available + Allocation

= (0, 1, 0) + (3, 0, 3)

= (3, 1, 3)

Step 4:

For process P3

request3 ≤ available

(1, 0, 0) ≤ (3, 1, 3)

P3 will execute.

Available = Available + Allocation

= (3, 1, 3) + (2, 1, 1)

= (5, 2, 4)

Step 5:

For process P4

request4 ≤ available

(0, 0, 2) ≤ (5, 2, 4)

P4 will execute.

Available = Available + Allocation

= (5, 2, 4) + (0, 0, 2)

= (5, 2, 6)

Step 6:

For process P1

request1 ≤ available

(2, 0, 1) ≤ (5, 2, 6)

P1 will execute.

Available = Available + Allocation

= (5, 2, 6) + (2, 0, 0)

= (7, 2, 6)

Safety sequence = <P0, P2, P3, P4, P1>

Numerical Solved by Deadlock Detection Algorithm

Q2. Apply deadlock detection algorithm to the following an show the result

Available = [ 2 1 0 0]

Allocation = [0 0 1 0]

[2 0 0 1]

[0 1 2 0]

Request = [2 0 0 1]

[1 0 1 0]

[2 1 0 0]

Solu:

Process Allocation Request Available
 P0 P1 P2
 A B C D 0 0 1 0 2 0 0 1 0 1 2 0
 A B C D 2 0 0 1 1 0 1 0 2 1 0 0
 A B C D 2 1 0 0

Step 1:

For process P0

request0 ≤ available

(2, 0, 0, 1) ≤ (2, 1, 0, 0)

Process P0 must wait.

Step 2:

For process P1

request1 ≤ available

(1, 0, 1, 0) ≤ (2, 1, 0, 0)

Process P1 must wait.

Step 3:

For process P2

request2 ≤ available

(2, 1, 0, 0) ≤ (2, 1, 0, 0)

Process P2 will execute.

Available = Available + Allocation

Available = (2, 1, 0, 0) + (0, 1, 2, 0)

= (2, 2, 2, 0)

Step 4:

For process P0

request0 ≤ available

(2, 0, 0, 1) ≤ (2, 2, 2, 0)

P0 must wait.

Step 5:

For process P1

request1 ≤ available

(1, 0, 1, 0) ≤ (2, 2, 2, 0)

P1 will execute.

Available = Available + Allocation

= (2, 2, 2, 0) + (2, 0, 0, 1)

= (4, 2, 2, 1)

Step 6:

For process P0

request0 ≤ available

(2, 0, 0, 1) ≤(4, 2, 2, 1)

P0 will execute.

Available = Available + Allocation

= (4, 2, 2, 1) + (0, 0, 1, 0)

= (4, 2, 3, 1)

Safety sequence = < P2, P1, P0>

Ans. Following are the step of Deadlock Detection Algorithm:

Step 1:

Let work and finish the vectors of length ‘m’ and ‘n’.

Initialize work = available

for i=1 … N

if Allocationi ≠ 0

then

Finish[i] = False

else

Finish[i] = True

Step2:

Find an index ‘i’, such that both

a)    Finish[i] = False.

b)    Requesti ≤ Work //Requesti ≤ Available

If no such ‘i’ exit go to step 4.

Step 3:

Work = Work + Available

//Available = Available + Allocation

Finish[i] = True

Go to step 2.

Step 4:

If Finish[i] = False

for some i, i ≤ n

then

Q2. Apply deadlock detection algorithm to the following an show the result

Available = [ 2 1 0 0]

Allocation = [0 0 1 0]

[2 0 0 1]

[0 1 2 0]

Request = [2 0 0 1]

[1 0 1 0]

[2 1 0 0]

Q3. Use deadlock algorithm, there are five processes and 3 resource type

A -> 7 instances

B -> 2 instances

C -> 6 instances

Process Allocation Request Available
 P0 P1 P2 P3 P4
 A B C 0 1 0 2 0 0 3 0 3 2 1 1 0 0 2
 A B C 0 0 0 2 0 2 0 0 0 1 0 0 0 0 2
 A B C 0 0 0

Single Instance of Each Resource Type

Q2. What happens when a Single Instance of Each Resource Type is present?

Ans.

Maintain wait for graph

Node are processes

Pi → Pj,

if Pi is waiting for Pj.

Invoke an algorithm that searches for cycle in the graph. If there is a cycle, there exists a deadlock.

An algorithm to detect a cycle in the graph requires an order of n2 operations, where n=number of vertices or processes in the graph.

Figure: Resource Allocation Graph

Note:

• Process(P) to Resource(R) is a Request.
• Request (R) to Process (P) is a Assignment.

Figure: Wait for Graph