Process Management Lecture Notes PDF

Lecture 6: Process Management  Learning Objectives After completing this chapter, you should be able to describe: Several causes of system deadlock and livelock The difference between preventing and avoiding deadlocks How to detect and recover from deadlocks...

Lecture 6: Process Management  Learning Objectives After completing this chapter, you should be able to describe: Several causes of system deadlock and livelock The difference between preventing and avoiding deadlocks How to detect and recover from deadlocks 2  Learning Objectives (cont’d.) The concept of process starvation and how to detect and recover from it The concept of a race and how to prevent it The difference between deadlock, starvation, and race 3  Deadlock Resource sharing – Memory management and processor sharing Many programs competing for limited resources Lack of process synchronization consequences – *Deadlock: “deadly embrace” Two or more jobs placed in HOLD state Jobs waiting for unavailable vital resource Complete when System comes to standstill Resolved via external intervention – *Starvation Infinite (endless) postponement of job First of all, understand what is Process Management, click on https://www.youtube.com/watch?v=1zgSo4_Z-UA Deadlock and Condition of Deadlock:- https://www.youtube.com/watch?v=MYgmmJJfdBg 4  Remember this! Deadlock – two or more jobs waiting for resources that are being held by another job, which in turn is also waiting for resources (1 mark) Starvation – a job that is kept waiting for resources because it is kept getting blocked from the resources and hence prevented from execution (1 mark) 5  Think of Bob and Jack as processes and the ball as the resource. If we assume that only one can play with the ball at a time, Bob has to wait for Jack to finish playing. This is a normal situation where both Bob and Jack (processes) get to play with ball (utilize the resource). ref://durofy.com/the-deadlock-problem/ 6  Deadlock (cont'd.) More serious than starvation (indefinite postponement) Affects entire system – Affects more than one job Not just a few programs – All system resources become unavailable Example: traffic jam (Figure 5.1) More prevalent in interactive systems Real-time systems – Deadlocks quickly become critical situations No simple and immediate solution 7 Deadlock (cont'd.) 8  Seven Cases of Deadlock Nonsharable / nonpreemptable resources – Are Allocated to jobs requiring same type of resources *Resource types locked by competing jobs 1. File requests 2. Databases 3. Dedicated device allocation 4. Multiple device allocation 5. Spooling 6. Network 7. Disk sharing 9  Case 1: Deadlocks on File Requests Jobs request and hold files for execution duration Example (Figure 5.2) – Two programs (P1, P2) and two files (F1, F2) – Deadlock sequence P1 has access to F1 F2 and also requires F2 F1 P2 has access to F2 F1 and also requires F1 F2 – Deadlock remains Until one program withdrawn or Until one program forcibly removed and file released – Other programs requiring F1 or F2 Put on hold for duration of situation 10  Case 1: Deadlocks on File Requests (cont'd.) F1 held by P2 P1 request F1 P2 request F2 F2 held by P1 11  Case 2: Deadlocks in Databases Two processes access and lock database records **Locking – Technique One user locks out all other users Users working with database – Three locking levels Entire database for duration of request Subsection of database Individual record until request completed 12  Case 2: Deadlocks in Databases (cont'd.) Example: two processes (P1 and P2) – Each needs to update two records (R1 and R2) – Deadlock sequence P1 accesses R1 and locks it P2 accesses R2 and locks it P1 requests R2 but locked by P2 P2 requests R1 but locked by P1 Race between processes – Results when locking not used – Causes incorrect final version of data – Depends on process execution order 13 *****Case 2: Deadlocks in Databases (cont'd.) 14  THINK!! 1.What could happen to the record after the updates? 2.What you can do to prevent? 3.If the process handle function update GPA hangs in the middle of updating a GPA value, what could happen? 15 Case 3: Deadlocks in Dedicated Device Allocation Limited number of dedicated devices Example – Two programs (P1, P2) Need two tape drives each Only two tape drives in system – Deadlock sequence P1 requests tape drive 1 and gets it P2 requests tape drive 2 and gets it P1 requests tape drive 2 but blocked P2 requests tape drive 1 but blocked 16 Case 4: Deadlocks in Multiple Device Allocation Several processes request and hold dedicated devices Example (Figure 5.4) – Three programs (P1, P2, P3) – Three dedicated devices (tape drive, printer, plotter) – Deadlock sequence P1 requests and gets tape drive P2 requests and gets printer P3 requests and gets the plotter P1 requests printer but blocked P2 requests plotter but blocked P3 requests tape drive but blocked 17 Case 4: Deadlocks in Multiple Device Allocation (cont'd.) 18  Case 5: Deadlocks in Spooling Virtual device – Dedicated device (printer) made sharable – Example Printer: high-speed disk device between printer and CPU Spooling – Process Disk accepts output from several users Acts as temporary storage for output Output resides in disk until printer accepts job data 19  Case 5: Deadlocks in Spooling (cont'd.) Deadlock sequence – Printer needs all job output before printing begins Spooling system fills disk space area No one job has entire print output in spool area Results in partially completed output for all jobs Results in deadlock 20  Case 6: Deadlocks in a Network No network protocols controlling network message flow Example (Figure 5.5) – Seven computers on network Each on different nodes – Direction of arrows Indicates message flow – Deadlock sequence All available buffer space fills 21 Case 6: Deadlocks in a Network (cont'd.) 22  Case 7: Deadlocks in Disk Sharing Competing processes send conflicting commands – Scenario: disk access Example (Figure 5.6) – Two processes – Each process waiting for I/O request One at cylinder 20 and one at cylinder 310 – Deadlock sequence Neither I/O request satisfied Device puts request on hold while attempting to fulfill other request for each request – Livelock results 23 Case 7: Deadlocks in Disk Sharing (cont'd.) 24  Conditions for Deadlock Four conditions simultaneously occurring prior to deadlock or livelock i. Mutual exclusion ii. Resource holding iii. No preemption iv. Circular wait All needed by operating system – Must recognize simultaneous occurrence of four conditions Resolving deadlock – Removal of one condition 25  Conditions for Deadlock (cont'd.) Mutual exclusion – Allowing only one process access to dedicated resource Resource holding – Holding resource and not releasing it – Waiting for other job to retreat No preemption – Lack of temporary reallocation of resources 26  Conditions for Deadlock (cont'd.) Circular wait – Each process involved in impasse Waiting voluntarily resource release by another so at least one can continue All four required for deadlock occurrence Deadlock remains until one condition removed 27 Mutual Exclusion – Each resource is either available or currently assigned to exactly one process R1 R1 R1 A B A B A B OK OK NOT OK 28 Resource Holding (Hold and wait)– A process holding a resources requests another resource R1 A B OK R2 29  No preemption – Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them 30  Circular wait– There must be circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain. R1 hold requesting A B requesting hold R2 31  *Modeling Deadlocks Directed graphs – Circles represent processes – Squares represent resources – Solid arrow from resource to process Process holding resource – Solid arrow from a process to resource Process waiting for resource – Arrow direction indicates flow – Cycle in graph Deadlock involving processes and resources 32 Modeling Deadlocks (cont'd.) 33  Modeling Deadlocks (cont'd.) Three graph scenarios to help detect deadlocks – System has three processes (P1, P2, P3) – System has three resources (R1, R2, R3) Scenario one: no deadlock – Resources released before next process request Scenario two: deadlock – Processes waiting for resource held by another Scenario three: no deadlock – Resources released before deadlock 34  Modeling Deadlocks (cont'd.) No deadlock – Resources released before next process request 35 Modeling Deadlocks (cont'd.) 36  Modeling Deadlocks (cont'd.) Deadlock – Processes waiting for resource held by another 37 Modeling Deadlocks (cont'd.) 38  Modeling Deadlocks (cont'd.) No deadlock – Resources released before deadlock 39 Modeling Deadlocks (cont'd.) 40  *Strategies for Handling Deadlocks Prevention – Prevent occurrence of one condition Mutual exclusion, resource holding, no preemption, circular wait Avoidance – Avoid deadlock if it becomes probable Detection – Detect deadlock when it occurs – Recover gracefully Recovery – Resume system normalcy quickly and gracefully 41  Deadlock Prevention One way to prevent deadlocks is to ensure that one of the four necessary conditions for deadlock never holds. Mutual Exclusion 1. Ensure that resources are never assigned exclusively to a single process Hold and Wait Condition 1. Require that process request and acquire ALL the resources they need before they start execution 2. Require that a process temporarily release resources being held. 3. Require that if a process requests for a resources that is not available, then it has to release currently held resources. For more additional on “Deadlock Prevention”, click on https://www.youtube.com/watch?v=cTCHLuVGBDI 42  Deadlock Prevention No Preemption 1. Ensure resources can be forcibly taken away from a process if necessary Circular Wait 1. Require that processes are entitled to only one resource 43  Strategies for Handling Deadlocks (cont'd.) Prevention eliminates one of four conditions – Complication: every resource cannot be eliminated from every condition – Mutual exclusion Some resources must allocate exclusively Bypassed if I/O device uses spooling – Resource holding Bypassed if jobs request every necessary resource at creation time Multiprogramming degree significantly decreased Idle peripheral devices 44  Strategies for Handling Deadlocks (cont'd.) Prevention (cont'd.) – No preemption Bypassed if operating system allowed to deallocate resources from jobs Okay if job state easily saved and restored Not accepted to preempt dedicated I/O device or files during modification – Circular wait Bypassed if operating system prevents circle formation Use hierarchical ordering scheme Requires jobs to anticipate resource request order Difficult to satisfy all users 45  Strategies for Handling Deadlocks (cont'd.) Avoidance: use if condition cannot be removed – System knows ahead of time Sequence of requests associated with each active process ***Dijkstra’s Bankers Algorithm – Regulates resources allocation to avoid deadlock No customer granted loan exceeding bank’s total capital All customers given maximum credit limit No customer allowed to borrow over limit Sum of all loans will not exceed bank’s total capital For more additional on “Deadlock Avoidance”, click on https://www.youtube.com/watch?v=AvPjOyeJbBM Banker Algorithm:- https://www.youtube.com/watch?v=2V2FfP_olaA 46 Strategies for Handling Deadlocks (cont'd.) 47  Strategies for Handling Deadlocks (cont'd.) Unsafe State 48  Strategies for Handling Deadlocks (cont'd.) Safe State 49 Strategies for Handling Deadlocks (cont'd.) Unsafe State 50  Strategies for Handling Deadlocks (cont'd.) Operating systems deadlock avoidance assurances – Never satisfy request if job state moves from safe to unsafe Identify job with smallest number of remaining resources Number of available resources => number needed for selected job to complete Block request jeopardizing safe state 51  Strategies for Handling Deadlocks (cont'd.) Problems with the Banker’s Algorithm – Jobs must state maximum number needed resources – Requires constant number of total resources for each class – Number of jobs must remain fixed – Possible high overhead cost incurred – Resources not well utilized Algorithm assumes worst case – Scheduling suffers Result of poor utilization Jobs kept waiting for resource allocation 52  Strategies for Handling Deadlocks (cont'd.) Detection: build directed resource graphs – Look for cycles Algorithm detecting circularity – Executed whenever appropriate Detection algorithm – Remove process using current resource and not waiting for one – Remove process waiting for one resource class Not fully allocated – Go back to step 1 Repeat steps 1 and 2 until all connecting lines removed For more additional on “Deadlock Detection”, click on https://www.youtube.com/watch?v=2St4eKZ_VVQ 53 Strategies for Handling Deadlocks (cont'd.) 54 Strategies for Handling Deadlocks (cont'd.) 55  Strategies for Handling Deadlocks (cont'd.) Recovery – Deadlock untangled once detected – System returns to normal quickly All recovery methods have at least one victim Recovery methods – Terminate every job active in system Restart jobs from beginning – Terminate only jobs involved in deadlock Ask users to resubmit jobs – Identify jobs involved in deadlock Terminate jobs one at a time For more additional on “Deadlock Recovery”, click on https://www.youtube.com/watch?v=KBFrWu_gejE 56  Starvation Job execution prevented – Waiting for resources that never become available – Results from conservative resource allocation Example – “The dining philosophers” by Dijkstra Starvation avoidance – Implement algorithm tracking how long each job waiting for resources (aging) – Block new jobs until starving jobs satisfied 57  Starvation (cont'd.) For more additional on “Dining Philosophers Problem”, click on https://www.youtube.com/watch?v=Nbw bQQB7xNQ 58 Starvation (cont'd.) 59  Summary Operating system – Dynamically allocates resources – Avoids deadlock and starvation Four methods for dealing with deadlocks – Prevention, avoidance, detection, recovery Prevention – Remove simultaneous occurrence of one or more conditions – System will become deadlock-free – Prevention algorithms Complex algorithms and high execution overhead 60  Summary (cont'd.) Avoid deadlocks – Clearly identify safe and unsafe states – Keep reserve resources to guarantee job completion – Disadvantage System not fully utilized No prevention support – System must detect and recover from deadlocks Detection relies on selection of victim 61