Deadlock is a state when a set of blocked processes each holding a resource are waiting to acquire a resource held by another process in the set.

Deadlock can arise if the following four conditions hold simultaneously:

Mutual exclusion: only one process at a time can use a resource.

Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.

No pre-emption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.

Circular wait: there exists a set {P1, P2, ..., Pn} of waiting processes such that P1 is waiting for a resource that is held by P2, P2 is waiting for a resource that is held by P3, ..., Pn1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P1.

There are 4 choices for handling deadlocks:

Choice #1: Ensure that the system will never enter a deadlock state

1. Deadlock Prevention - ensure that the system will never enter a deadlock state
2. Deadlock Avoidance maintain the safe state by having the information about the maximum number of resources of each type it may need

Choice #2: Allow the system to enter a deadlock state and then recover

1. Deadlock Detection
2. Deadlock Recovery
   1. Process Termination -Abort all deadlocked processes, or abort one deadlocked process at a time until every deadlock cycle is eliminated. May depend upon the priority of the process or process age and remaining time or resources the process has used or resources the process needs to complete or number of processes will need to terminated or the process are interactive or batch?
   2. Resource Pre-emption by selecting a victim or Rollback by return to some safe state, i.e. restart the current process

Choice #3: Ignore and dont care

Resources may be a single instance or multiple instances. Resource allocation and wait for graph occurs for single instances generally and bankers algorithm works for multiple instances.

Q4. We have the following scheme at the current time. Check if there is any safe sequence?

requested allocated

r1 r2 r3 r4 r1 r2 r3 r4

process 1 2 5 3 2 1 0 3 2

process 2 1 5 1 1 1 1 0 0

process 3 3 3 3 3 3 3 3 3

and suppose that the total of available resources is

r1 r2 r3 r4

12 12 7 9

Is this a safe state? Why or why not?

Q5. Given five memory partitions of 100Kb, 500Kb, 200Kb, 300Kb, 600Kb (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of 212 Kb, 417 Kb, 112 Kb, and 426 Kb (in order)? Which algorithm makes the most efficient use of memory?

Q1. Given below is the wait-for graph for the processes. It is built from resource allocation graph. The graph only shows the processes as nodes. Shows pl is waiting for p2 to finish and so on. Wait for graph is used for deadlock detection. R. A R. RE R (a) Resource Allocation Graph (b) Corresponding wait-for graph To do: build a wait for graph for the following and check if it is in a safe state or not? P1 R1 R1 P1 P2 -R2 R2 P2 P3 R3 R3 P3 FRA Q2. Using bankers algorithm, generate the safe sequence for the following data: U 3 Available V W 4 0 X 0 B Allocation U V W 1 1 0 0 1 2 5 4 001 10 2 X 2 3 4 1 U 1 1 5 5 4 Max V W 0 2 4 5 9 0 1 3 2 3 5 5 1 Need U ] | W 0 0 0 1 1 2 0 4 5 5 0 0 3 3 0 2 1 0 0 D E Check if it is in the safe state? Q3. Consider a system with 12 magnetic tapes and 3 processes (PO, P1, P2) available = 3 Process PO 10 Maximum Needs Holding Needs 5 5 4 2 2 9 2 7 P1 P2 Is the system in safe state? What will be the change if available are 2 tapes only i.e. total of 11 tapes in the system