tailieunhanh - Lecture Operating system concepts - Lecture 27

This chapter examines two problems that plague all efforts to support concurrent processing: deadlock and starvation. We begin with a discussion of the underlying principles of deadlock and the related problem of starvation. Then we examine the three common approaches to dealing with deadlock: prevention, detection, and avoidance. | CSC 322 Operating Systems Concepts Lecture - 29: by Ahmed Mumtaz Mustehsan Special Thanks To: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. (Chapter-6) Silberschatz, Galvin and Gagne 2002, Operating System Concepts, Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad 1 Chapter 6 Deadlock Lecture-29 2 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Ways of Handling Deadlock Deadlock Detection (studied) Deadlock Recovery (studied) Deadlock Avoidance (Today) Deadlock Prevention (Today) Lecture-29 3 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Deadlock Avoidance Allow the chance of deadlock to occur, but avoid it happening when it is going to happen!!! Check whether the next state (change in system) may end up in a deadlock situation; avoid it. Plotting of Graph (Next Slide) Explains the idea!!! Lecture-29 4 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Two process resource trajectories. Deadlock Avoidance . | CSC 322 Operating Systems Concepts Lecture - 29: by Ahmed Mumtaz Mustehsan Special Thanks To: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. (Chapter-6) Silberschatz, Galvin and Gagne 2002, Operating System Concepts, Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad 1 Chapter 6 Deadlock Lecture-29 2 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Ways of Handling Deadlock Deadlock Detection (studied) Deadlock Recovery (studied) Deadlock Avoidance (Today) Deadlock Prevention (Today) Lecture-29 3 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Deadlock Avoidance Allow the chance of deadlock to occur, but avoid it happening when it is going to happen!!! Check whether the next state (change in system) may end up in a deadlock situation; avoid it. Plotting of Graph (Next Slide) Explains the idea!!! Lecture-29 4 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Two process resource trajectories. Deadlock Avoidance Lecture-29 5 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Deadlock avoidance Safe state = NO deadlock! there exists some scheduling order in which every process can run to completion even if all of them suddenly request their max number of resources immediately Unsafe != deadlocked Lecture-29 6 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Safe states Lecture-29 7 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Unsafe states With only 4 free, neither A nor C can be completely satisfied. Lecture-29 8 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Banker’s algorithm for single resource (SR) type Lecture-29 9 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Dijkstra's Banker's Algorithm Definitions Each process has a LOAN, MAXIMUM NEED, CLAIM LOAN: current number of resources held MAXIMUM NEED: total number resources needed to complete CLAIM: = (MAXIMUM - LOAN) Lecture-29 10 Ahmed Mumtaz Mustehsan, GM-IT, CIIT, Islamabad Assumptions Establish a LOAN ceiling (MAXIMUM NEED) for each process