Section 3.5 - 교착 상태 ( Deadlock )
- 숫자가 의미하는 것 = 리소스
- 차 = 프로세스
그림에서 차가 직진을해서 지나가려고 하면 반드시 2개의 리소스를 확보해야하지만, 마음급한 차들이 서로 빨리 지나가려고 함
각 차들은 한개의 리소스들을 선점하는데 성공했으나 다른 리소스들은 다른 차들이 가지고 있기때문에 더이상 진행해 나갈 수 없음
1. 교착상태 ( Deadlock )
( 이하 교착상태와 데드락은 같은 뜻으로 사용함 )
두 개 이상의 프로세스 혹은 스레드가 서로가 가진 리소스를 기다리는 상태
교착상태의 4가지 조건
교착상태에 빠지려면 아래 4가지 조건을 만족해야함
- Mutual exclusion
- Hold and Wait
- No Preemption
- Circular Wait
그림으로 예시를 들어가면서 알아보자
-
Mutual exclusion
리소스를 공유해서 사용할 수 없다
그림에서 리소스를 공유하면 교통사로에 해당
-
Hold and Wait
프로세스가 이미 하나 이상의 리소스를 취득(Hold)한 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다림 (Wait)
그림에서 2번 리소스를 확보한 차가 3번 리소스를 기다리지만 3번리소스는 이미 다른차가 선점하고 있음
-
No preemption
리소스 반환은 오직 그 리소스를 취득한 프로세스만 가능
그림에서 2번 리소스를 확보한 차가 3번 리소스를 기다릴 때 3번 리소스를 이미 다른차가 선점하고 있다고 해서 빼앗아 올 수 없고 3번 리소스는 3번 리소스를 가진 차만이 반환할 수 있음
-
Circular wait
순환하는 형식으로 리소스를 기다림
2. 교착상태 방지 ( Deadlock Prevention )
데드락에 빠지지 않게 하기위해 어떻게 할까? 당연히 위 4가지 조건이 동시에 만족하지 않게하면 된다.
데드락 4조건 시스템중 하나가 충족되지 않게 시스템을 디자인
=> 데드락 방지
-
# 1. Mutual Exclusion 만족 x
리소스를 공유가능하게 함 -> 현실적으로 어려울 수 있음
-
# 2. Hold and Wait 만족 x
2가지 제약이 있음
- 리소스들을 모두 확보한 뒤에 시작
- 리소스를 전혀가지지 않은 상태에서만 리소스 요청
그림을 보면 2번 3번 리소스 둘다 확보하고 있어야 시작이 가능하게 하거나 / 2번을확보하는데 성공을 하고 3번을 확보하고싶을때는 2번을 비우고 2번 3번 둘다 확보할 수 있을때 시작가능 하게 함
-
# 3. No preemption
추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 함
그림을 보면 2번 리소스를 확보한 차량이 3번 리소스를 기다리고 있고 2번 리소스를 양보가 가능할때 양보하는 방식
-
# 4. Circular wait
모든 리소스에 순서체계를 부여해서 오름차순으로 리소스 요청 ( 제일 많이 사용됨 )
그림을 보면 4번리소스 근처의 차가 4번을 먼저 확보하는것이 아닌 1번을 먼저 확보하도록 하는것
대부분의 경우에서 자원 낭비가 발생하고 Hold and Wait를 부정할 경우 기아상태 ( starvation )가 될 수 있음
아래 내용 부터는 이런게 있구나 하는 정도로 알고 넘어 가자
교착상태 회피 ( Deadlock Avoidance )
실행 환경에서 추가적인 정보를 활용하여 데드락이 발생할것 같은 상황 회피
=> 자원을 신중하게 할당하면 교착상태를 회피 할 수 있음
여기서 말하는 추가적인 정보는 실행환경에서 운영체제가 동작할때 현재 사용가능한 리소스, 할당된 리소스, 미래에 있을 리소스 요청들 등을 의미
- Banker algorithm ( 데드락 회피 알고리즘들 중 하나 )
리소스 요청을 허락해 줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때 까지 계속 요청을 거절하는 알고리즘
교착상태 회피는 여러 가정들이 필요하기 때문에 현실성이 부족하고 자원 요청이 있을 때마다 회피 알고리즘을 사용하는 것은 상당한 오버헤드
교착상태 감지와 복구
데드락을 허용하고 데드락이 발생하면 복구하는 전략
# 1. 프로세스 종료
데드락에 빠진 모든 차를 견인해버림, or 한대씩 견인시키면서 해결되는지 확인
지금까지 진행된 작업을 잃을 수 있기 때문에 리스크가 큼
( 최후의 카드 )
# 2. 리소스의 일시적인 선점을 허용
희생자 선택, 롤백, 기아상태 등등... 여러 사항들을 고려
교착상태 무시
아몰랑 데드락 무시할래 ( 이방법을 근데 많이 쓴다고함..)
오버헤드보다 교착상태를 무시할 때 더 이득이 큰 경우에 사용
프로그래밍 레벨에서의 데드락 예시 ( java )
public class Main {
public static void main(String[]args) {
Object lock1 = new Object(); // 리소스1
Object lock2 = new Object(); // 리소스2
Thread t1 = new Thread(() -> {...}); // 쓰레드 t1 동작
Thread t2 = new Thread(() -> {...}); // 쓰레드 t2 동작
t1.start();
t2.start();
}
}Thread t1 = new Thread(()->{
synchronized(lock1){
System.out.println("[t1]get lock1");
synchronized(lock2){
System.out.println("[t1] get lock2");
}
}
});
Thread t2 = new Thread(()->{
synchronized(lock2){
System.out.println("[t2]get lock2");
synchronized(lock1){
System.out.println("[t2] get lock1");
}
}
});쓰레드 1에서는 lock1을 쥐고 Critical Section으로 들어가게하고 t1이 lock1을 확보했다고 메시지를 띄우고나서 두번째 Critical Section으로 들어가기위해 lock2를 확보하려고 하고 있음
쓰레드 2에서도 위와같은 과정과 같으나 lock2를 먼저 확보하려고 시도
동시에 함수가 실행되면 처음에 t1이 lock1을 가지고 있게 되고 t2가 lock2를 가지고 있는데 두번째 Critical Section으로 들어갈때 t2는 lock1이 필요하지만 lock1은 t1이 가지고 있고 반대로 t1은 lock2가 필요하지만 t2가 lock2를 가지고 있어 데드락이 발생
위 내용을 이해 했다면 해결 방법도 쉽게 생각할 수 있을것이다. 아마?..
