교착상태(Deadlocks) 시스템 모델(System Model) 프로세스는 자원을 요구 -> 사용 -> 해제 요구 -> 사용 -> 해제 Request Use Release 요구와 해제 ① system calls로 (예) open & close file allocate & free memory ② wait&signal로 (예) printer 등 같은 종류 자원에 의한 deadlock 다른 종류 자원에 의한 deadlock 2000 운영체제

교착상태의 특징(Deadlock Characterization) 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이면 자원할당 그래프에 cycle있음 ※ 각 자원 종류 마다 1 자원 : cycle은 필요충분조건 ″ 여러 자원 : cycle은 필요조건일 뿐 2000 운영체제

자원할당 그래프(Recource-Allocation Graph) Process Resource Type with 4 instances Pi requests instance of Rj Pi is holding an instance of Rj Pi Rj Pi Rj 2000 운영체제

Example of a Resource Allocation Graph 2000 운영체제

Resource Allocation Graph With A Deadlock 2000 운영체제

Resource Allocation Graph With A Cycle But No Deadlock 2000 운영체제

교착상태 처리방법(Methods for Handling Deadlocks) 접근 1. 교착상태 생기지 않게 : 예방 또는 회피 접근 2. 교착상태 생기면 복구 : 탐지와 회복 접근 3. 무시 : 교착상태 발생 않는 것으로 간주 Unix: 1년에 한번 수동으로 시스템 재시작(manual restart) JVM: 응용 개발자에게 맡김 cf. Frosen state 제어를 절대 OS로 넘겨주지 않는 상태(never returning control to OS) (예) 높은 우선순위의 실시간 프로세스 또는 비선점 스케줄러에 의해 스케줄 되는 프로세스가 제어를 절대 OS로 넘겨주지 않는 상태 2000 운영체제

교착상태 처리방법(Methods for Handling Deadlocks) JVM does nothing to manage deadlocks. Java 2 deadlock 방지위해 suspend(), resume() 제외 suspend() 호출한 스레드는 lock holding 한 채 suspend 되므로 resume()하는 스레드가 suspend된 스레드가 가지고 있는 lock을 요구할 경우 deadlock 가능 데이터 일관성(data consistency) 위해 stop() 제외 stop()은 lock을 release 하므로 스레드가 공유 데이터 수정 중 stop() 호출하게 되면 공유 데이터 상호배제 위반 가능 (1) acquire the lock (2) access a shared data structure (3) release the lock 2000 운영체제

Deadlock example class Mutex { } class B extends Thread class A extends Thread { public A(Mutex f, Mutex s) { first = f; second = s; } public void run() { synchronized (first) { //do something synchronized (second) { // do something else private Mutex first, second; class B extends Thread { public B(Mutex f, Mutex s) { first = f; second = s; } public void run() { synchronized (second) { //do something synchronized (first) { // do something else private Mutex first, second; public class DeadlockExample // Figure 8.5 2000 운영체제

Creating the threads 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(); } 2000 운영체제

Applet that displays the date and time of day p127 Fig.5.9에서 스레드 stop(), resume(), stop() 제거 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); repaint(); synchronized (mutex) { while (ok == false) mutex.wait(); } catch (InterruptedException e) { } public void start() { // Figure 8.7 } public void stop() { 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(); 2000 운영체제

start() and stop() methods for the applet // this method is called when the applet is // started or we return to the applet public void start() { if (clockThread == null) { ok = true; clockThread = new Thread(this); clockThread.start(); } else { synchronized(mutex) { mutex.notify(); // this method is called when we // leave the page the applet is on public void stop() { if (clockThread != null) { synchronized(mutex) { ok = false; } clockThread = null; 2000 운영체제

교착상태 예방(Deadlock Prevention) ~ 필요 조건의 성립을 방지 상호배제(Mutual Exclusion) 비공유 자원(nonsharable resources) : (예) printer nonsharable인 자원들에 대해서는 상호배제 성립 방지로 예방할 수 없음 공유 자원(sharable resources) : (예) read-only files -> no deadlock Ok 점유와 대기(Hold and Wait) 자원 요청시 다른 자원점유 않게 함 2 프로토콜 ① 실행전 모든 사용자원 요구하여 할당 받음 ② 자원을 점유하지 않고 있는 프로세스만 자원 요청(자원요청 전 모든 점유자원 해제) 단점 1. 자원 이용율 낮음 2. 기아상태 가능 2000 운영체제

교착상태 예방(Deadlock Prevention) ~ 비선점(No Preemption) ① 어떤 프로세스가 요구한 자원이 사용가능하지 않아 대기상태로 갈 때 그 프로세스가 점유하고 있던 모든 자원을 선점하여 :자원리스트에 추가(암시적 해제) ② 어떤 프로세스가 요청한 자원을 점유하고 있는 프로세스가 현재 자원대기상태이면 요청했던 자원을 선점함(필요자원을 선점해 옴) (예) CPU registers, memory space (반대로 printer, tape driver는 불가) 환형 대기(Circular Wait) 자원종류 순서대로 요청하게 함 F : R -> N ① F(Rj) > F(Ri) 인 자원만 요청 ② F(Ri) >= F(Rj) 인 모든 자원 해제된 상태에서 자원요청 모순에 의한 증명 {P0, P1,... Pn} 환형대기 상태 가정 Pi+1은 Ri를 점유 Ri+1 waiting, Pi는 Pi+1이 점유하고 있는 Ri 대기 F(R0) < F(R1) < … < F(Rn) < F(R0) : F(Rn) < F(R0)는 모순 고로, 자원종류 순서대로 요청하면 환형대기 없음 단점 자원요구방식의 제한으로 장치 사용율, 시스템 처리율이 낮아짐 2000 운영체제

교착상태 회피(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> 시스템의 안전상태를 유지할 수 있는 자원 요구만 들어줌 단점 : 사용가능 자원이 있어도 안전하기 위해 기다리는 경우가 있어 자원 이용율 낮아짐 2000 운영체제

교착상태 회피(Deadlock Avoidance) ~ 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm) 종류별 자원이 한 개인 경우 자원 종류마다 한 개의 자원 요청가능 자원할당 그래프 + 요청가능 간선(claim edge) cycle 있으면 deadlock cycle-detection algorithm O(n2) 은행가 알고리즘(Banker’s algorithm) 종류별 자원이 여러 개인 경우 자료구조 Available : 사용가능한 각 자원의 수(길이 m인 vector) Available[j] = k : 자원종류 rj중 k개 사용가능 Max : 각 프로세스의 최대 요구(nxm 행렬) Max[i,j] = k : Pi는 자원종류 rj중 최대 k개 요청 Need : 각 프로세스의 남은 요구(nxm행렬) Need[i,j] = Max[i,j] - Allocation[i,j] = k : Pi는 자원종류 rj를 k개 더 요구함 Allocation : 각 프로세스에 할당된 자원의 수(nxm 행렬) Allocation[i,j] = k : Pi는 현재 자원종류 rj를 k개 할당 받고 있음 Note : X[i] <= Y[i] for all i=1,2,..n 이면 X<=Y (예) (1,7,3,2) > (0,3,2,1) 2000 운영체제

교착상태 회피(Deadlock Avoidance) ~ 안전 알고리즘(Safety Algorithm) ① work : 길이 m인 vector Finish : 길이 n인 vector work := Available Finish[i] := false for i=1,2,...,n ② 다음과 같은 i를 찾는다. a. Finish[i] = false; b. Need i <= work 없으면 goto step④ ③ Work := Work + Allocation; Finish[i] := true; goto step② ④ 만일 모든 i에 대해 Finish[i] = true이면 안전한 상태이다 O(mxn2) : 모든 Pi에 대해 i = 1,..,n 2000 운영체제

교착상태 회피(Deadlock Avoidance) 자원요청 알고리즘(Resource-Request Algorithm) Requesti : Pi의 요청 vector Requesti[j] = k : 프로세스 Pi가 자원종류 ri중 k개를 원함 ① Requesti <= Needi 이면 ② 그렇지 않으면 오류(최대로 정의된 자원보다 더 많이 요구하므로) ② Requesti <= Available이면 goto③ 그렇지 않으면 Pi는 기다림(자원이 사용가능하지 않으므로) ③ 할당을 위해 상태 수정 Available := Available - Requesti; Allovationi = Allocationi + Requesti; Needi = Needi - Requesti; 상태 수정 결과가 안전한 상태이면(call safety algorithm) Pi에게 요구한 자원할당 그렇지 않으면 이전 상태로 복귀하고 Pi는 기다림 (예) 자원 : (A, B, C) = (10, 5, 7) Request1 = (1, 0, 2) ? Request4 = (3, 3, 0) ? Request0 = (0, 2, 0) ? 2000 운영체제

Safe, unsafe , deadlock state spaces 2000 운영체제

Resource-Allocation Graph For Deadlock Avoidance 2000 운영체제

Unsafe State In A Resource-Allocation Graph 2000 운영체제

교착상태 탐지(Deadlock Detection) ~ 접근 2. 교착상태 생기면 복구 교착 상태 탐지 알고리즘과 교착 상태로 부터 회복 알고리즘 필요 자원종류별로 한 개의 자원(Single Instance of a Resource Type) 대기 그래프(wait-for graph)로 해결 자원종류 정점 없애고 간선 합침 cycle 있으면 deadlock OS가 할 일 대기 그래프 유지 주기적으로 cycle detection algorithm 수행 모든 정점이 선행자를 가지면 cycle : C로 쓴 자료구조론 p310 2000 운영체제

Resource-Allocation Graph And Wait-for Graph Corresponding wait-for graph 2000 운영체제

교착상태 탐지(Deadlock Detection) ~ 자원종류별로 여러 개 자원 : banker’s algorithm과 유사 자료구조 Available : 길이 m vector Allocation : n x m 행령 Pn Rm Request : n x m 행렬 Pn Rm ① Work : 길이 m vector Finish : 길이 n vector Work := Available -> Allocationi /= 0 이면 Finish[i] = false; 그렇지 않으면 Finish[i] := true; ② 다음과 같은 i을 찾는다. a. Finish[i] = false; b. Requesti <= Work; 없으면 goto ④ ③ Work := Work + Allocationi Finish[i] := true goto ② ④ 1 <= i <= n인 i에 대해 Finish[i] = false인 것이 있으면 교착상태 이때 finish[i] = false인 프로세스 Pi는 deadlocked O (m x n2) (예) (A, B, C) = (7, 2, 6) 2000 운영체제

교착상태 탐지(Deadlock Detection) 탐지 알고리즘의 사용(Detection-Algorithm Usage) ① How often is a deadlock likely to occur? ② How many processes will be affected by deadlock when it happens? 탐지 알고리즘 호출간격 결정 (예) 요구가 즉시 허락되지 않을 때마다 조사 -> 원인 프로세스 탐지 가능 CPU 이용율이 40%이하일 때 탐지 알고리즘 수행 -> 원인 프로세스 탐지 불가능 2000 운영체제

교착상태로 부터의 회복(Recovery from Deadlock) 수동 : Operator가 처리 자동 ① circular wait하는 프로세스를 abort all(모두) - great expense one at a time(하나씩) : overhead ② 자원을 선점 고려사항 : ① 희생자 선택(selecting a victim) ② 어디까지 rollback : 자원 선점 당한 프로세스를 꺼꾸로 돌림 total rollback partial rollback ③ starvation없게 2000 운영체제