7 장교착상태 (Deadlocks) Questions of the day 1. 아래의예는안전한가? ( 예 ) 12 MT 최대수요 현재할당 사용가능 P0 10 5 3 (2) P1 4 2 P2 9 2 (3) 2. 그림 7.6( 자료 p22) 상황에서 R2 를어느프로세스에할당해야할까요? 그이유는? 3. 교재 p293 7.5.3.3 Banker s Algorithm 예시 ( 자료 p27) 에서 Request 0 = (0, 2, 0) 요청을들어줄수있는지요? 그이유는? 7.1
교착상태 (Deadlocks) 시스템모델 (System Model) 프로세스는자원을 요구 사용 해제 Request Use Release 요구와해제 1 system calls 로 ( 예 ) open & close file 2 wait&signal 로 ( 예 ) printer 등 allocate & free memory 같은종류자원에의한 deadlock 다른종류자원에의한 deadlock 7.2
교착상태문제 블록된프로세스집합의각프로세스가하나의자원을소유 (holding) 하면서그집합에있는다른프로세스가소유하고있는자원의획득을요구함 Example» 2개 CD RW drives 가진시스템에서» P 1 과P 2 가각기하나의 CD RW drive를소유하고있으면서나머지 CD RW drive 를소유하기를원함 Example» 1 로초기화된세미포어 A 와 B 가아래의연산수행 P 0 P 1 wait (A); wait(b) wait (B); wait(a) 7.3
다리건너기예 (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
교착상태의특징 (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 자원할당그래프 (Recource-Allocation Graph)» 시스템자원할당그래프 (System resoure-allocation graph) : 방향그래프 (directed graph) p227 그림 7.1 정점 (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.5
자원할당그래프 (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 R j P i R j 7.6
Example of a Resource Allocation Graph 7.7
Resource Allocation Graph With A Deadlock 7.8
Resource Allocation Graph With A Cycle But No Deadlock 7.9
교착상태처리방법 (Methods for Handling Deadlocks) 접근 1. 교착상태생기지않게 : 예방또는회피 접근 2. 교착상태생기면복구 : 탐지와회복 접근 3. 무시 : 교착상태발생않는것으로간주» Unix: 1년에한번수동으로시스템재시작 (manual restart)» JVM: 응용개발자에게맡김 cf. Frosen state» 제어를절대 OS로넘겨주지않는상태 (never returning control to OS) ( 예 ) 높은우선순위의실시간프로세스또는비선점스케줄러에의해스케줄되는프로세스가제어를절대 OS로넘겨주지않는상태 7.10
Deadlock example class Mutex { class A extends Thread { private Mutex first, second; public A(Mutex f, Mutex s) { first = f; second = s; public void run() { synchronized (first) { // do something try { Thread.sleep( ((int)(3*math.random()))*1000); catch (InterruptedException e) { System.out.println("threadA got first mutex"); synchronized (second) { // do something System.out.println("threadA got second mutex"); 7.11 class B extends Thread { private Mutex first, second; public B(Mutex f, Mutex s) { first = f; second = s; public void run() { synchronized (second) { // do something try { Thread.sleep( ((int)(3*math.random()))*1000); catch (InterruptedException e) { System.out.println("threadB got second mutex"); synchronized (first) { // do something System.out.println("threadB got first mutex");
Creating the threads public class DeadlockExample { public static void main(string arg[]) { Mutex mutexx = new Mutex(); Mutex mutexy = new Mutex(); A threada = new A(mutexX,mutexY); B threadb = new B(mutexX,mutexY); threada.start(); threadb.start(); 7.12
뮤텍스락사용시의교착상태실습 교재 7장 p278 코딩 숙제입니다 Tips void *do_work_one(); void *do_work_two(); pthread_mutex_t t t first_mutex; t pthread_mutex_t second_mutex; main() { pthread_t tid; int return val;» 락요청시메시지출력» 락획득시메시지출력» 락해제시메시지출력 int return_val; pthread_mutex_init(&first_mutex, NULL); pthread_mutex_init(&second_mutex, NULL); pthread_create(&tid, (pthread_attr_t *)NULL, (void *(*)())do )())do_work_one, one, (void *)NULL); /* * Wait for the thread to finish executing, then... */ pthread_join(tid, (void **)NULL); printf( Mission Completed!\n"); void *do_work_one(void *param) { printf("thread_one wants the first_mutex\n"); pthread_mutex_lock(&first_mutex); printf("thread_one wants the second_mutex\n"); pthread_mutex_lock(&second_mutex); sleep(1000); pthread_mutex_unlock(&second_mutex); pthread_mutex_unlock(&first_mutex); t t t pthread_exit(0); 7.13
JVM 과교착상태 JVM does nothing to manage deadlocks» Java 2 deadlock 방지위해 suspend(), resume() 제외»suspend() 호출한스레드는 lock holding 한채 suspend 되므로 resume() 하는스레드가 resume() 하기전에 suspend된스레드가가지고있는 lock을요구할경우 deadlock 가능 deprecated methods 데이터일관성 (data consistency) 위해 stop() 제외» stop() 은 lock을 release 하므로스레드가공유데이터수정중 stop() 호출하게되면공유데이터상호배제위반가능 (1) acquire the lock (2) access a shared data structure (3) release the lock 7.14
날짜와시간을출력하는 ClockApplet (4 장스레드 ) import java.applet.* ; import java.awt.* ; public class ClockApplet extends Applet implements Runnable { public void run() { while(true) { try { Thread.sleep(1000); catch(interruptedexception e) { repaint(); public void start() { if(clockthread == null) { clockthread = new Thread(this); clockthread.start() ; else clockthread.resume(); public void stop() { if(clockthread!= null) clockthread.suspend() ; public void destroy() { if(clockthread!= null) { clockthread.stop() ; clockthread = null ; public void paint(graphics g) { g.drawstring(new java.util.date().tostring(), 10, 30) ; private Thread clockthread; <applet code = ClockApplet width = 250 height = 50> </applet> 7.15
날짜와시간을출력하는 ClockApplet2 4장스레드 ppt 자료 p26 날짜와시간출력하는 ClockApplet의 deprecated 메소드» suspend(): 락가진채멈춤» resume()» stop(): 모든락방출 deprecated 메소드제거 import java.applet.*; import java.awt.*; public class ClockApplet extends Applet implements Runnable { public void run() { Thread me = Thread.currentThread(); while (clockthread == me) { try { Thread.sleep(1000); eep( repaint(); synchronized (mutex) { while (ok == false) mutex.wait(); catch (InterruptedException e) { <applet code = ClockApplet l width = 250 height = 50> </applet> 7.16 public void start() { if (clockthread == null) { ok = true; clockthread = new Thread(this); clockthread.start(); else { synchronized(mutex) { ok = true; mutex.notify(); public void stop() { if (clockthread!= null) { synchronized(mutex) { ok = false; public void destroy() { clockthread = null; public void paint(graphics g) { g.drawstring(new java.util.date().tostring(), 10,30); private volatile Thread clockthread; private boolean ok = false; private Object mutex = new Object();
교착상태예방 (Deadlock Prevention) : 필요조건의성립을방지 상호배제 (Mutual Exclusion)» 비공유자원 (nonsharable resources) : ( 예 ) printer nonsharable인자원들에대해서는상호배제성립방지로예방할수없음» 공유자원 (sharable ab resources) : ( 예 ) read-only files no deadlock Ok 점유와대기 (Hold and Wait)» 자원요청시다른자원점유않게함» 2 프로토콜 1 실행전모든사용자원요구하여할당받음 2 자원을점유하지않고있는프로세스만자원요청 ( 자원요청전모든점유자원해제 )» 단점 1. 자원이용율낮음 2. 기아상태가능 비선점 (No Preemption) 1 어떤프로세스가요구한자원이사용가능하지않아대기상태로갈때그프로세스가점유하고있던모든자원을선점하여 : 자원리스트에추가 ( 암시적해제 ) 2 어떤프로세스가요청한자원을점유하고있는프로세스가현재자원대기상태이면요청했던자원을선점함 ( 필요자원을선점해옴 ) ( 예 ) CPU registers, memory space ( 반대로 printer, tape driver 는불가 ) 7.17
교착상태예방 (Deadlock Prevention) 환형대기 (Circular Wait)» 자원종류순서대로요청하게함 F : R N 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.18
교착상태회피 (Deadlock Avoidance) 교착상태예방의단점 : 자원요구방식의제한으로장치사용률, 시스템처리율낮아짐 대안 : 부가적정보로부터현재의자원요청이안전한지를결정자원할당상태 ( 사용가능한자원, 할당된자원 ) 미래의자원요청과자원해제 사용할최대자원의개수이용 동적으로자원할당상태조사하여교착상태를피해감 안전한상태 (Safe State)» 일련의순서대로자원할당해도교착상태없는상태» safe sequence 가있는상태 <P1, P2,... Pn> : Pi요구자원 < 사용가능자원 + j<i인 Pj의자원» deadlock 상태 = unsafe state : safe sequence가없는상태» ( 예 ) 12 MT 최대수요 현재할당 사용가능 P0 10 5 3 2 P1 4 2 P2 9 2 3 deadlock 안전한순서 <P1, P0, P2> 시스템의안전상태를유지할수있는자원요구만들어줌 단점 : 사용가능자원이있어도안전하기위해기다리는경우가있어자원이용율낮아짐 7.19
Safe, unsafe, deadlock state spaces 7.20
교착상태회피 (Deadlock Avoidance) 자원할당그래프알고리즘 (Resource-Allocation Graph Algorithm)» 종류별자원이한개인경우자원종류마다한개의자원요청가능» 자원할당그래프 + 예약간선 (claim edge)» 프로세스가자원요청하면예약간선 (claim edge) 은요청간선 (request edge) 으로변환 cycle 있으면 deadlock» cycle-detection algorithm O(n 2 ) 7.21
Resource-Allocation Graph For Deadlock Avoidance R2 를어느프로세스에할당해야할까요? 그이유는? 7.22
Unsafe State In A Resource-Allocation Graph 7.23
교착상태회피 (Deadlock Avoidance) 은행원알고리즘 (Banker s algorithm)» 종류별자원이여러개인경우» 자료구조 Available : 사용가능한각자원의수 ( 길이 m 인 vector)» Available[j] = k : 자원종류 r j 중 k 개사용가능 Max : 각프로세스의최대요구 (nxm 행렬 )» Max[i,j] = k : P i 는자원종류 r j 중최대k개요청 Need : 각프로세스의남은요구 (nxm행렬)» Need[i,j] = Max[i,j] - Allocation[i,j] = k : P i 는자원종류 r j 를 k개더요구함 Allocation : 각프로세스에할당된자원의수 (nxm 행렬 )» Allocation[i,j] = k : P i 는현재자원종류 r j 를k개할당받고있음 Note : X[i] <= Y[i] for all i=1,2,..n 이면 X<=Y ( 예 ) (1,7,3,2) > (0,3,2,1) 7.24
교착상태회피 (Deadlock Avoidance) 안전알고리즘 (Safety Algorithm) 1 work : 길이 m 인 vector Finish : 길이 n인 vector work := Available Finish[i] := false for i=1,2,...,n 2 다음과같은 i를찾는다. a. Finish[i] = false; b. Need i work 없으면 goto step4 3 Work i := Work i + Allocation i ; Finish[i] := true; goto step2 4 만일모든 i에대해 Finish[i] = true이면안전한상태이다» O(mxn 2 ) : 모든 P i 에대해 i = 1,..,n 7.25
교착상태회피 (Deadlock Avoidance) 자원요청알고리즘 (Resource-Request Algorithm) Request i : P i 의요청 vector Request i [j] = k : 프로세스 P i 가자원종류 r i 중 k개를원함 1 Request i Need i 이면 2 그렇지않으면오류 ( 최대로정의된자원보다더많이요구하므로 ) 2 Requesti Available이면 goto3 그렇지않으면 Pi는기다림 ( 자원이사용가능하지않으므로 ) 3 할당을위해상태수정 Available := Available - Request i ; Allovation i = Allocation i + Request i ; Need i = Need i - Request i ;» 상태수정결과가안전한상태이면 (call safety algorithm) P i 에게요구한자원할당» 그렇지않으면이전상태로복귀하고 P i 는기다림 ( 예 ) 자원 : (A, B, C) = (10, 5, 7) Request 1 = (1, 0, 2)? Request 4 = (3, 3, 0)? Request 0 = (0, 2, 0)? 7.26
Example of Banker s Algorithm 5 processes P 0 through P 4 3 resource: types A (10 instances), B (5instances, and C (7 instances). Snapshot at time T 0 : Allocation Max Available A B C A B C A B C P 0 0 1 0 7 5 3 3 3 2 10 5 7 P 1 2 0 0 3 2 2 5 3 2 P 2 3 0 2 9 0 2 10 4 7 P 3 211 1 222 2 2 743 P 4 0 0 2 4 3 3 7 4 5 The content of the matrix. Need is defined to be Max Allocation. Need A B C P 0 7 4 3 P 1 1 2 2 P 2 6 0 0 P 3 0 1 1 P 4 4 3 1 safe sequence < P 1, P 3, P 4, P 2, P 0 > 있으므로 safe state 임 7.27
Example (Cont.): P 1 request (1,0,2), Request 1 = (1, 0, 2)? Request 1 Available 인지조사 : (1,0,2) (3,3,2) true 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 302 020 0 532 P 2 3 0 2 6 0 0 P 3 2 1 1 0 1 1 3 7 4 3 7 5 5 10 5 7 P 4 0 0 2 4 3 1 7 4 5 safety algorithm 실행하면 safe sequence <P 1, P 3, P 4, P 0, P 2 > 있으므로요구들어줌 P 4 의요구 (3,3,0) 를들어줄수있나? P 0 의요구 (0,2,0) 를들어줄수있나? 0 7.28
교착상태탐지 (Deadlock Detection) 접근 2. 교착상태생기면복구» 교착상태탐지알고리즘과» 교착상태로부터회복알고리즘필요 자원종류별로한개의자원 (Single Instance of a Resource Type)» 대기그래프 (wait-for graph) 로해결» 자원종류정점없애고간선합침 cycle 있으면 deadlock OS 가할일 대기그래프유지 주기적으로 cycle detection algorithm 수행» 모든정점이선행자를가지면 cycle : C 로쓴자료구조론 p310 7.29
Resource-Allocation Graph And Wait-for Graph Resource-Allocation Graph Corresponding wait-for graph 7.30
교착상태탐지 (Deadlock Detection) 자원종류별로여러개자원 : banker s algorithm과유사» 자료구조 Available : 길이 m vector Allocation : n x m 행령 Pn Rm Request : n x m 행렬 Pn Rm 1 Work : 길이 m vector Finish : 길이 n vector Work := Available Allocation i 0 이면 Finish[i] [] = false; 그렇지않으면 Finish[i] := true; 2 다음과같은 i을찾는다. a. Finish[i] = false; b. Request i Work; 없으면 goto 4 3 Work := Work + Allocation i Finish[i] []:= true goto 2 4 1 i n인 i에대해 Finish[i] = false인것이있으면교착상태이때 finish[i] = false인프로세스 Pi는 deadlocked» O(mxn 2 )» ( 예 ) (A, B, C) = (7, 2, 6) 7.31
Example of Detection Algorithm Five processes P 0 through P 4 ; three resource types A (7 instances), B (2 instances), and C (6 instances). Snapshot at time T 0 : Allocation Request Available A B C A B C A B C P 0 010 0 000 0 0 000 0 0 010 0 P 1 2 0 0 2 0 2 7 2 4 P 2 3 0 3 0 0 0 3 1 3 P 3 2 1 1 1 0 0 5 2 4 P 4 002 0 002 0 726 Sequence <P 0, P 2, P 3, P 1, P 4 > will result in Finish[i] = true for all i. P 2 requests an additional instance of type C. Request A B C P 0 0 0 0 0 1 0 P 1 2 0 2 P 2 001 0 P 3 1 0 0 P 4 0 0 2 시스템의상태는?» P 0 의자원을회수하여도다른프로세스들의자원요청을들어줄수 없으므로교착상태존재하며, P 1, P 2, P 3, and P 4 이교착상태에연루됨 7.32
교착상태탐지 (Deadlock Detection) 탐지알고리즘의사용 (Detection-Algorithm Usage) 관점 1 교착상태가얼마나자주일어나는가?(How often is a deadlock likely to occur?) 2 몇개의프로세스들이교착상태에연루되는가?(How many processes will be affected by deadlock when it happens?) 탐지알고리즘호출간격결정 ( 예 ) 요구가즉시허락되지않을때마다조사 원인프로세스탐지가능 CPU 이용율이 40% 이하일때탐지알고리즘수행 원인프로세스탐지 불가능 7.33
교착상태로부터의회복 (Recovery from Deadlock) 수동 : Operator 가처리 자동 1 circular wait하는프로세스를 abort all( 모두 ) - great expense one at a time( 하나씩 ) : overhead 2 자원을선점 고려사항 : 1 희생자선택 (selecting a victim) 2 어디까지 rollback : 자원선점당한프로세스를꺼꾸로돌림 total rollback partial rollback 3starvation 없게 7.34