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, ..., Pn-1 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 a. 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? b. Resource Pre-emption by selecting a victim or Rollback by return to some safe state, ie, restart the current process Choice #3: Ignore and don't care Resources may be a single instance or multiple instances. Resource allocation and wait for graph occurs for single instances generally and banker's algorithm works for multiple instances. Question Num 1 : 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. R RA R R (a) Resource Allocation Graph 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 MORA P1 P2 R2 R2 P2 P3 LOR3 R3 P3 FRA Q2. Using banker's algorithm, generate the safe sequence for the following data: U 1 1 Allocation U 1 1 0 2 B 1 2 3 51 4 4 D 0 0 1 1 E 10 2 1 Available V W X 4 0 0 X 3 5 Max V W 1 0 2 4 5 9 0 1 3 2 XU 1 3 2 ovlo Need W 0 0 1 1 2 0 4 5 50 0 3 3 1 5 5 4 5 1 1 OO 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 Maximum Needs Holding Needs 10 5 5 2 2 P2 9 2 7 PO P1 4 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?