Understanding Operating Systems Sixth EditionLearning ObjectivesLearning Objectives (cont’d.)DeadlockDeadlock (cont’d)Deadlock (cont'd.)Slide 7Seven Cases of DeadlockCase 1: Deadlocks on File RequestsCase 1: Deadlocks on File Requests (cont'd.)Case 2: Deadlocks in DatabasesCase 2: Deadlocks in Databases (cont’d)Slide 13Case 2: Deadlocks in Databases (cont'd.)Slide 15Case 3: Deadlocks in Dedicated Device AllocationCase 4: Deadlocks in Multiple Device AllocationCase 4: Deadlocks in Multiple Device Allocation (cont'd.)Case 5: Deadlocks in SpoolingCase 5: Deadlocks in Spooling (cont'd.)Case 6: Deadlocks in a NetworkCase 6: Deadlocks in a Network (cont'd.)Case 7: Deadlocks in Disk SharingCase 7: Deadlocks in Disk Sharing (cont’d)Slide 25Slide 26Slide 27Case 7: Deadlocks in Disk Sharing (cont'd.)Conditions for DeadlockConditions for Deadlock (cont’d)Conditions for Deadlock (cont'd.)Slide 32Modeling DeadlocksModeling Deadlocks (cont'd.)Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Strategies for Handling DeadlocksStrategies for Handling Deadlocks (cont'd.)Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76StarvationSlide 78Starvation (cont'd.)Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85SummarySummary (cont’d)Slide 88Understanding Operating SystemsSixth EditionChapter 5Process ManagementUnderstanding Operating Systems, Sixth EditionLearning ObjectivesAfter 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 deadlocks2Understanding Operating Systems, Sixth EditionLearning 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 race3Understanding Operating Systems, Sixth EditionDeadlock•In early OS, deadlock was known by the more descriptive phrase - “deadly embrace”.–Happens when the system freezes.•A system-wide tangle of resource requests that begins when two or more jobs are put on HOLD, each waiting for a vital resource to become available.•The problem builds when the resources needed by those jobs are the resources held by other jobs that are also waiting to run but cannot because they’re waiting for other unavailable resources.•The tangled jobs come to a standstill.4Understanding Operating Systems, Sixth EditionDeadlock (cont’d)•The deadlock is complete if the remainder of the system comes to a standstill as well.•When the situation can’t be resolved by the OS, intervention is required.•Deadlock affects more than one job.•Because resources are being tied up, the entire system, not just a few programs, is affected.•Deadlocks became prevalent with the introduction of interactive systems, which generally improve the use of resources through dynamic resource sharing, but this capability also increases the possibility of deadlocks.5Understanding Operating Systems, Sixth EditionDeadlock (cont'd.)6Understanding Operating Systems, Sixth EditionDeadlock (cont'd.)•In some computer systems, deadlocks are regarded as a mere inconvenience that causes delays.•But for real-time systems, deadlocks cause critical situations.•Regardless of the environment, the OS must either prevent deadlocks or resolve them when they happen.7Understanding Operating Systems, Sixth EditionSeven Cases of Deadlock•A deadlock usually occurs when nonshareable, nonpreemptable resources, such as files, printers or scanners are allocated to jobs that eventually require other nonshareable nonpreemptive, resources that have been locked by other jobs.•Deadlocks can also occur on shareable resources that are locked, such as disks and databases.8Understanding Operating Systems, Sixth EditionCase 1: Deadlocks on File Requests•If jobs are allowed to request and hold files for the duration of their execution, a deadlock can occur.•Example (Figure 5.2)–Two programs (P1, P2) and two files (F1, F2)–Deadlock sequence•P1 has access to F1 and also requires F2•P2 has access to F2 and also requires F1 –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 situation9Understanding Operating Systems, Sixth EditionCase 1: Deadlocks on File Requests (cont'd.)10Understanding Operating Systems, Sixth EditionCase 2: Deadlocks in Databases•A deadlock can occur if two processes access and lock records in a database.•Database queries and transactions are often relatively brief processes that either search or modify parts of a database.•Requests usually arrive at random and may be interleaved arbitrarily.• Locking is a technique used to guarantee the integrity of the data through which the user locks out all other users while working with the database.11Understanding Operating Systems, Sixth EditionCase 2: Deadlocks in Databases (cont’d)•Locking can be done at three different levels:–The entire database can be locked for the duration of the request;•The most extreme and most successful solution.•Prevents a deadlock from occurring but it restricts access to the database to one user at a time.•In a multiuser environment, response times are significantly slowed.•Normally an unacceptable solution.12Understanding Operating Systems, Sixth EditionCase 2: Deadlocks in Databases (cont’d)–A subsection of the database can be locked:•When the locking is performed on only one part of the database, access time is improved but the possibility of a deadlock is increased because different processes sometimes need to work with several parts of the data base at the same time.–The individual record can be locked until the request is completed.•Same as above.13Understanding Operating Systems, Sixth EditionCase 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:–An alternative is to avoid the use of locks•If locks are