Chapter 7: Deadlocks, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Chapter 7: Deadlocks The Deadlock Problem System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from Deadlock 7.2 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
The Deadlock Problem Deadlock ( 교착상태 ): 블록된프로세스집합의각프로세스가하나의자원을소유 (holding) 하면서그집합에있는다른프로세스가소유하고있는자원의획득을기다리고있는상태 Example 2 개 CD RW drives 가진시스템에서 P 1 과 P 2 가각기하나의 CD RW drive 를소유하고있으면서나머지 CD RW drive 를소유하기를원함 CD1 P1 P2 Example CD1 1 로초기화된세미포어 A 와 B 가아래의연산수행 P 0 P 1 wait (A); wait(b) wait (B); wait(a) 7.3 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
다리교행예 (Bridge Crossing Example) 한차선에서차량통행은한방향으로만가능 다리는자원 교착상태생기면, 차량한대가후진하여해결 ( 자원선점후되돌림 ) 여러차량이후진해야할수도있음 기아상태발생가능 Traffic only in one direction Each section of a bridge can be viewed as a resource If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback) Several cars may have to be backed up if a deadlock occurs Starvation is possible 7.4 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Fig. 7.1 deadlock Example class Program { Mutex first_mutex = new Mutex(); Mutex second_mutex = new Mutex(); static int sleep = 0; static void Main(string[] args) { Program p=new Program(); Thread t1=new Thread(new ThreadStart(p.work_one)); Thread t2 = new Thread(new ThreadStart(p.work_two)); t1.start(); t2.start(); t1.join(); t2.join(); } public void work_one() { Console.WriteLine("T1 1st mutex.wait0"); } first_mutex.waitone(); Console.WriteLine("T1 1st mutex.wait1"); Console.WriteLine("T1 2nd mutex.wait0"); second_mutex.waitone(); Console.WriteLine("T1 2nd mutex.wait1"); for (int i = 0; i < 5; i++) Console.WriteLine("Thread One {0,2}", i); Console.WriteLine("T1 2nd mutex.release0"); second_mutex.releasemutex(); Console.WriteLine("T1 2nd mutex.release1"); Console.WriteLine("T1 1st mutex.release0"); first_mutex.releasemutex(); Console.WriteLine("T1 1st mutex.release1"); public void work_two() { } Console.WriteLine(" T2 2nd mutex.wait0"); second_mutex.waitone(); Console.WriteLine(" T2 2nd mutex.wait1"); Console.WriteLine(" T2 1st mutex.wait0"); first_mutex.waitone(); Console.WriteLine(" T2 1st mutex.wait1"); for (int i = 0; i < 5; i++) Console.WriteLine(" Thread Two {0,2}", i); Console.WriteLine(" T2 1st mutex.release0"); first_mutex.releasemutex(); Console.WriteLine(" T2 1st mutex.release1"); Console.WriteLine(" T2 2nd mutex.release0"); second_mutex.releasemutex(); Console.WriteLine(" T2 2nd mutex.release1"); } 7.5 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
7.6 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
1.System Model 프로세스는자원의사용방법요구 사용 해제 Request Use Release 요구와해제 1 system calls로 ( 예 ) open & close file allocate & free memory 2 wait&signal로 ( 예 ) printer 등 같은종류자원에의한 deadlock 다른종류자원에의한 deadlock 7.7 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
2.Deadlock Characterization 동시에아래의조건모두만족하면 deadlock 발생가능 ( 필요조건 ) 1. 상호배제 (Mutual exclusion) 2. 점유와대기 (Hold and wait) 자원점유하면서다른자원대기 3. 비선점 (No preemption) 배정된자원은선점되지않는다. released only voluntarily by the process 4. 순환대기 (Circular wait) {P0, P1,... Pn, P0} 자원할당그래프 (Recource-Allocation Graph) 시스템자원할당그래프 (System resource-allocation graph) : 방향그래프 (directed graph) 정점 (Vertices) : P = {P1, P2,.. Pn} 시스템의모든processes의집합 R = {R1, R2,.. Rn} 시스템의모든 resource types의집합 방향간선 (directed edges) : Pi Rj 요청간선 ( request edge) Rj Pi 할당간선 (assignment edge) Deadlock이면 (p), 자원할당그래프에 cycle있음 (q) 각자원종류마다 1 자원 : cycle (q) 은필요충분조건 (p q) 각자원종류마다여러자원 : cycle (q) 은필요조건일뿐 (p q) 7.8 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Example of a Resource Allocation Graph Process 그래프에주기가존재하지않으면시스템내어느프로세스도교착상태가아니다 Resource Type with 4 instances P i requests instance of R j P i P i is holding an instance of R j P i 자원할당그래프 7.9 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Resource Allocation Graph With A Deadlock 교착상태를갖는자원할당그래프 7.10 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Resource Allocation Graph With A Cycle But No Deadlock 그래프에주기가있더라도교착상태가아닐수있다 사이클이있으면서교착상태가아닌자원할당그래프 7.11 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Basic Facts 만일그래프가사이클을가지고있지않으면 = 교착상태인가?. 만일그래프가사이클을가지고있을때 하나의자원형 ( 예프린터들 ) 에하나의인스턴스만있으면 => 교착상태 하나의자원형 ( 예프린터들 ) 에여러개의인스턴스가있으면 => 교착상태일가능성이있다. If graph contains no cycles no deadlock If graph contains a cycle if only one instance per resource type, then deadlock if several instances per resource type, possibility of deadlock 7.12 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
3. 교착상태처리방법 (Methods for Handling Deadlocks) 접근 1. 교착상태생기지않게 : 예방또는회피 Prevention : deadlock 발생필요조건을점검 Avoidance : 안전상태, 자원할당그래프 Resource Allocation Graph Algorithm : 자원할당그래프 + 예약간선 for one instance per resource type Baker s Algorithm for multiple instances per resource type 접근 2. 교착상태생기면복구 : 탐지와회복 Deadlock detection Wait-for Graph Approach : for one instance per resource type Deadlock Detection Algorithm for multiple instances per resource type Deadlock recovery : process termination, preemtion 접근 3. 무시 : 교착상태발생않는것으로간주 Unix: 1 년에한번수동으로시스템재시작 (manual restart) JVM: 응용개발자에게맡김 cf. Frosen state 제어를절대 OS 로넘겨주지않는상태 (never returning control to OS) ( 예 ) 높은우선순위의실시간프로세스또는비선점스케줄러에의해스케줄되는프로세스가제어를절대 OS로넘겨주지않는상태 7.13 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
4. 교착상태예방 (Deadlock Prevention) 접근 1. deadlock 발생의필요조건성립을예방 1. 상호배제 (Mutual Exclusion) 비공유자원 ( nonsharable resources) : ex. Printers 비공유자원 ( 한순간한프로세스만사용가능 )=> 항상상호배제성립 =>deadlock 공유자원 (sharable resources) : ex. Read-only files-> no deadlock 항상공유가능 => 상호배제미성립 => no deadlock 2. 점유와대기 (Hold and Wait) 자원요청시마다다른자원점유않게보증하여야한다. 두가지방법 실행전모든사용자원요구하여할당받고실행시작 자원을점유하지않고있는프로세스만자원요청 ( 자원요청전모든점유자원해제 ) 단점 1. 자원이용율낮음 2. 기아상태가능 3. 비선점 (No Preemption) 어떤프로세스가요구한자원이사용가능하지않아대기상태로갈때이프로세스가점유하고있던모든자원을선점하여자원리스트에추가 ( 암시적해제 ) 프로세스 A 가자원 b 를요청한경우그자원 b 가다른프로세스 B 에의하여점유되어있고 B 가대기상태에있으면 b 의자원 b 를선점하여프로세스 A 가사용 ( 필요자원을선점해옴 ) ( 예 ) CPU registers, memory space ( 반대로 printer, tape driver 는불가 ) 7.14 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
4. 교착상태예방 (Deadlock Prevention)(Cont.) 4. 환형대기 (Circular Wait) 자원종류별로순서번호를할당하고증가번호순서대로요청하게하여순환대기조건을방지함 단점 F : R N F( R ) = N F(tape driver)=1, F(disk drive)=5, F(printer)=12, 초기에 Ri 를요청점유후 Rj 를요청하는경우 (1) F(Rj) > F(Ri) 인자원만요청 (2) F(Ri) >= F(Rj) 인모든자원해제된상태에서자원요청 (1 의대안 ) 사실 : 1 또는 2 방법으로자원요청하면환형대기발생않음 모순에의한증명 1 또는 2 방법으로자원요청했으나 {P0, P1,... Pn} 환형대기발생을가정 Pi 는 Pi+1 이점유하고있는 Ri 대기, Pn 은 P0 가점유하고있는 Rn 대기 F(R0) < F(R1) < < F(Rn) < F(R0) : F(Rn) < F(R0) 는모순 고로, 자원종류순서대로요청하면환형대기없음 자원요구방식의제한으로장치사용율, 시스템처리율이낮아짐 P0 P1 P2 R0 R1 R2 7.15 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5 교착상태회피 (Deadlock Avoidance) 교착상태예방의단점 : 장치의이용률이저하되고시스템처리율이감소된다 교착상태회피 (Deadlock Avoidance) 의경우시스템이다음과같은사전정보를인지가요구된다. 실행전에프로세스는필요로하는각형별자원의최대수 (maxmum number) 를제공하여야한다. 교착상태회피알고리즘은순환대기 (circular-wait) 조건이존재하지않는것을보증하기위하여동적으로자원할당상태를조사한다. 프로세스의유용한자원수 (available resources), 할당된자원수 (allocated resources), 최대요구수 (maximum demands) 로정의된다 7.16 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5 교착상태회피 (Deadlock Avoidance) 5.1 안전상태 (Safe State) 안전상태 : 시스템이어떤순서로든프로세스들이요청하는모든자원을교착상태를야기시키지않고차례로모두할당해줄수있는상태 안전순서가존재하는상태 Unsafe state : 안전순서가존재하진않는경우, deadlock 상태 안전순서 (Safe sequence) : <P 1, P 2,, P n > : Pi 의요구자원수 >=Pj 의유용자원수 + Pi 의점유 ( 할당 ) 자원수, 0<j < I 의조건을만족하는프로세스의순서열 Pj 의유용자원수 : Pj 에할당 ( 해제될수있는 ) 된수와 j 이전의유용한수 예 12 magnetic tapes Max. Demands Current Needs Available t=0 t=1 t=2 t=3 3 =12-9 5=4+1 10=10+0 12=9+3 P0 10 5 10-5>3 10-5<=5+0 P1 4 2 4-2<2+1 P2 9 2 9-2>3 9-2>5 9-2<=7+3 안전순서 <P1,P0,P2> 시스템은안전상태를유지할수있는요구만들어준다. 단점 : 사용가능자원이있어도안전하기위해기다리는경우가있어자원이용율낮아짐 t=0 에서 P1 에 2 할당하고 1 이남는다 1 은 P0 나 P1 에할당할수있지만. 7.17 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5 교착상태회피 (Deadlock Avoidance) 안전상태 (Safe State) If a system is in safe state no deadlocks If a system is in unsafe state possibility of deadlock Avoidance ensure that a system will never enter an unsafe state. 7.18 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5 교착상태회피 (Deadlock Avoidance) 시스템은안전상태에서불안전상태로갈수있다 t0 에 12 개의자기테이프를 3 개의프로세스 P0, P1, P2 가다음과같이사용중일때시스템은안전한가? 최대수요 현재사용량 (Max) (allocation) available t=1 t=2 t=3 t=4 3 =12-9 5=4+1 10=10+0 12=9+3 P0 10 5 10-5>3 10-5<=5+0 P1 4 2 4-2<2+1 P2 9 2 9-2>3 9-2>5 9-2<=7+3 Safe state sequence <P1,P0,P2> at time t0- system is in safe state. t1 에서 P2 가 tape 를하나더요구하고할당받았다면안전한가? 2 4=4+0 P0 10 5 10-5>2 10-2<4 P1 4 2 4-2>=2+0 P2 9 3 9-3>2 9-3<4 So system is in unsafe state. 7.19 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5 교착상태회피 (Deadlock Avoidance) 교착상태회피알고리즘 시스템이불안정상태가아님을보장하는것 안정상태로부터시스템이불안정상태로가지않도록한다 프로세스가가용한자원을요청할때마다할당될수있는지대기해야하는지를결정한다 현재가용한자원을요청하더라도만일할당후시스템이불안정상태가되면대기해야한다 Two type Deadlock Avoidance appreach Single instance of a resource type 5.2 Use a resource-allocation graph Multiple instances of a resource type 5.3 Use the banker s algorithm 7.20 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5.2 자원할당그래프알고리즘 ( Resource-Allocation Graph Algorithm) 종류별자원이한개인경우자원종류마다한개의자원요청가능 자원할당그래프 + 예약간선 (claim edge) 프로세스가실행되기전에프로세스의모든예약간선들을자원할당그래프에표시 예약간선 (Claim edge) P i R j : 프로세스 P j 가자원 R j 를요구할수있음을의미한다. 예약간선은프로세스가자원을요구하면요구간선 (request edge) 으로변환된다. 요구간선은자원이프로세스에할당되면할당간선 (assignment edge) 으로변화된다. 할당간선은다원이해제되면예약간선으로변환된다. cycle 있으면 deadlock cycle-detection algorithm O(n 2 ) 모든정점이선행자를가지면 cycle 7.21 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Resource-Allocation Graph Resource-Allocation Graph for deadlock avoidance 사이클이없다면자원을할당해도안전상태이고, Unsafe State In Resource-Allocation Graph 사이클이발견되면할당은시스템을불안전상태로만든다 Assignment edge request edge claim edge P2 requests R2 If we grant it, A cycle is formed (unsafe) No cycle safe -grant Cycle - unsafe - deny 교착상태회피를위한자원할당그래프 불안전한상태의자원할당그래프 7.22 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5.3 Banker s Algorithm 은행원알고리즘 (Banker s algorithm) Is applicable to a resource allocation system with multiple instances of each resource type. Due to the fact that bank system doesn t allocate all cash required by all customers 새로운프로세스의생성시각자원종류에대해총자원수를넘지않는한도내에서최대수요를정의 기존프로세스의추가적인자원요구시이할당으로시스템의상태가안정상태로유지되는지를결정 Yes -> 할당됨 No -> 기다림 7.23 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5.3 Banker s Algorithm 은행원알고리즘의자료구조 (Data Structures for the Banker s Algorithm ) Available: 길이 m 인벡터 만일 available [j] = k:, 자원종류 R j 는 k 개의자원이유용함을의미 Max: n x m matrix. Ex. Max [i,j] = k: 프로세스 P i 는최대 k 개의인스턴스를요청할수있음 Allocation: n x m matrix. Ex. Allocation[i,j] = k : 프로세스 P i 에현재할당된자원종류 R j 의인스턴스개수 k Need: n x m matrix. 각프로세스의남은요구량 Ex. Need[i,j] = k, 프로세스 P i 는작업을완성하기위하여 R j 의 k 개를더요구할수있다. Need [i,j] = Max[i,j] Allocation [i,j] 7.24 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
안전알고리즘 (safety Algorithm) 5.3 Banker s Algorithm 1. Initially Work[0..m-1]=Available[0..m-1] //for each resource type Finish[0..n-1]=false //for each process 2. find an index i such that both: (a) Finish [i] = false (b) Need[i] Work[i] If no such i exists, go to step 4 3. Work[i] = Work[i] + Allocation[i] Finish[i] = true go to step 2 4. if Finish [i] == true for all i, then the system is in a safe state 7.25 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
5.3 Banker s Algorithm 자원요청알고리즘 (Resource-Request Algorithm for Process P i ) Request[0..n-1] for process P i. If Request i [j] = k then process P i wants k instances of resource type R j 1. If Request i Need i go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim 2. If Request i Available, go to step 3. Otherwise P i must wait, since resources are not available 3. Pretend to allocate requested resources to P i by modifying the state as follows: 4. Call safety algorithm Available = Available Request; Allocation i = Allocation i + Request i ; Need i = Need i Request i ; If safe the resources are allocated to Pi If unsafe Pi must wait, and the old resource-allocation state is restored 7.26 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Deadlock Avoidance(2) Resource-Request Algorithm for Process P i Request = request vector for process P i. If Request i [j] = k then process P i wants k instances of resource type R j 1. If Request i Need i go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim 2. If Request i Available, go to step 3. Otherwise P i must wait, since resources are not available 3. Pretend to allocate requested resources to P i by modifying the state as follows: 4. Call safety algorithm Available = Available Request; Allocation i = Allocation i + Request i ; Need i = Need i Request i ; If safe the resources are allocated to Pi If unsafe Pi must wait, and the old resource-allocation state is restored ( 예 ) 자원 : (A, B, C) = (10, 5, 7) Request1 = (1, 0, 2)? Request4 = (3 3 0)? Request0 = (0 2 0)? 7.27 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Example of Banker s Algorithm Is system safe? 시스템의상태 5 processes P0 through P4 3 resource: types (A,B,C)= (10,5,7). Allocation[n,m],Max[n,m] Snapshot at time T 0 : Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 10 5 7 P1 2 0 0 3 2 2 5 3 2(332+200) P2 3 0 2 9 0 2 10 4 7 P3 2 1 1 2 2 2 7 4 3(532+211) P4 0 0 2 4 3 3 7 4 5 ------- 7 2 5 The content of the matrix. Need is defined to be Max Allocation. safe <P1 P3 P4 P2 P0 > 있으므로 safe 임 W(3,3,2) N1(1,2,2) A1(2,0,0) W(5,3,2) N3(0,1,1) A3(2,1,1) W(7,4,3) N4(4,3,1) A4(0,0,2) W(7,4,5) N2(6,0,0) A2(3,0,2) W(10,4,7) N0(7,4,5) A0(0,1,0) W(10,5,7) Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 7.28 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
For the request (1,0,2) for P 1, safe? Example: P 1 Request (1,0,2) Check Need and Available Request(1,0,2)<Need[1](1,2,2) true Request(1,0,2) Available(3,3,2) true Modify state Available -=Request (3,3,2)-(1,0,2) =>(2,3,0) Allocation[1,..] +=Request (2,0,0)+(1,0,2) =>(3,0,2) Need[1,..] -= Request (1,2,2)-(1,0,2)=>(0,2,0) Snapshot Allocation Need Available A B C A B C A B C P 0 0 1 0 7 4 3 2 3 0 P 1 3 0 2 0 2 0 P 2 3 0 2 6 0 0 P 3 2 1 1 0 1 1 P 4 0 0 2 4 3 1 Executing safety algorithm shows that sequence < P 1, P 3, P 4, P 0, P 2 > satisfies safety requirement. So we can allocate the request(1,0,2) for P1. Can request for (3,3,0) by P 4 be granted? Can request for (0,2,0) by P 0 be granted? 5 3 2 7 4 3 7 5 5 7 4 5 10 5 7 7.29 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
6 교착상태탐지 (Deadlock Detection) 접근 2 : 교착상태진입을허용하고교착상태가생기면복구 교착상태탐지알고리즘 (Detection algorithm) 교착상태로부터회복알고리즘 (Recovery scheme) 2 cases A: single instance per resource type: cycle deadlock B: multiple instance per resource type:? irreducible deadlock 7.30 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
6 교착상태탐지 (Deadlock Detection) 접근 2 : 교착상태가생기면복구 교착상태탐지알고리즘 (Detection algorithm) 교착상태로부터회복알고리즘 (Recovery scheme) 6.1 대기그래프를유지관리 (Maintain wait-for graph) 자원종류별로한개인자원 (Single Instance of Each Resource Type) 의경우 그래프의사이클을점검하여교착상태탐지 교착상태복구 : 자원종류정점을없애고간선을합침 Cycle 이있으면 deadlock Os가할일 대기그래프유지 주기적으로주기탐지알고리즘 (cycle detection algorithm, O(n)=n 2 ) 가동 모든정점이선행자를가지면 cycle이다. Cycle은모든정점이선행자를가질때 7.31 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Resource-Allocation Graph and Wait-for Graph Reduction: (Request? Grant Release) Reduction by P 5 only Not completely reducible deadlock! (cycle) each resource type single unit (eg DB) Resource-Allocation Graph Corresponding wait-for graph 7.32 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
6.3 Deadlock Detection Algorithm 6.2 교착상태탐지알고리즘 - 자원종류별로여러개의자원 Cf. banker s algothim - 자료구조 Available [0..m-1] 유용자원수 Allocation[0..n-1,0..m-1] 프로세스별자원별활당된수량 Request[0..n-1,0..m-1] 프로세스별자원별요구량 1. Let Work and Finish be vectors of length m and n, respectively Initialize: (a) Work = Available (b) if Allocation[i] 0 then Finish[i]= fasle else Finish[i] = true for i = 1,2,, n, 2.Find an index i such that both: (a) Finish[i] == false (b) Request i Work If no such i exists, go to step 4 3. Work = Work + Allocation i Finish[i] = true go to step 2 // n // 자원이할당되어있는프로세스 // m 4. If Finish[i] == false, for some i, 1 i n, then the system is in deadlock state. Moreover, if Finish[i] == false, then P i is deadlocked Algorithm requires an order of O(m x n 2) operations to detect whether the system is in deadlocked state 7.33 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Example of deadlock Detection Algorithm Five processes P 0 through P 4 ; three resource types A (7 instances), B (2 instances), and C (6 instances) (7,2,6) Snapshot at time T 0 : Allocation Request Available A B C A B C A B C P 0 0 1 0 0 0 0 0 0 0 P 1 2 0 0 2 0 2 P 2 3 0 3 0 0 0 P 3 2 1 1 1 0 0 P 4 0 0 2 0 0 2 Sequence <P 0, P 2, P 3, P 1, P 4 > will result in Finish[i] = true for all i => no deadlock Work 0 0 0 0 1 0 7 2 4 3 1 3 5 2 4 7 2 6 7.34 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
Example (Cont.) P 2 requests an additional instance of type C. For R2=(0,0,1), will the system got to safe state? Allocation Request Available A B C A B C A B C P 0 0 1 0 0 0 0 0 0 0 P 1 2 0 0 2 0 2 P 2 3 0 3 0 0 1 P 3 2 1 1 1 0 0 P 4 0 0 2 0 0 2 Work 0 0 0 0 1 0 (001)!<(010) State of system? Can reclaim resources held by process P 0, but insufficient resources to fulfill other processes; requests There does not exist any Ri<(010) therefore Deadlock exists, consisting of processes P 1, P 2, P 3, and P 4 7.35 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
6.3 Detection-Algorithm Usage 탐지알고리즘관련문제 How often a deadlock is likely to occur? How many processes will need to be rolled back? 얼마나자주알고리즘을호출해야하나? 요구가있을때마다 요구가즉시할당 ( 허락 ) 되지않을때마다조사 원인프로세스탐지가능 주기적으로 ( 교착상태의가능성이매우적다면 ) CPU 이용율이 40% 이하일때탐지알고리즘수행 원인프로세스탐지불가능 7.36 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
7 교착상태로부터회복 (Recovery from Deadlock) 강제종료 (Process Tremination) 모든교착상태의프로세스를종료 (abort) 교착상태의사이클이제거될때까지프로세스를하나씩종료한다. 종료를위한프로세스의선택순서는? 프로세스의우선순위 프로세스의실행 (computation) 시간에따라, 완료 (completion) 시간이의길이에따라 프로세스가사용했던자원에따라 종료에필요한프로세스의수에따라 프로세스의 Interactive 또는 batch 인지에따라선점 (preemption) 희생자선정 minized cost Rollback 안전상태까지뒤로후진하고다시그프로세스부터실행 Starvation 같은프로세스가계속해서희생자로선택될때 롤백시 cost factor를사용해서제거해야 7.37 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
summary Deadlock 의개념 Deadlock 의충분조건 : Mutual exclusion, Hold and wait, No emption, Circular wait, Deadlock 의처리방법 예방및회피 Prevention : 상호배제, 점유및대기, no preemption, 순환대기 Avoidance : resource allocation graph, banker s algorithm 탐지및복구 (detection and recovery) 무시 Wait-for for one instance per one resource type Deadlock detection algorithm for multiple instance per one resource type 7.38 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
연습문제 다음연습문제풀어보세요. 7.1 교토의교착상태 7. 11 은행원알고리즘문제, 7.14 다리교착상태문제 7.15 기아현상제거문제 7.39 / 38 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2011
End of Chapter 7, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010