DeadLock
정의
프로세스들이 더 이상 진행하지 못하고 영구적으로 block된 상태
예를들면
- 꽉 막힌 4거리 교차로
- 서로 멱살을 잡으면서 놓으라고 함
데드락 발생 4조건
- 상호배제(Mutual exclusion)
- 잠금과 대기(Hold & Wait)
- 선점 불가(No preemption)
- 순환 대기(Circular wait)
위 4가지 조건을 모두 만족해야 데드락이 발생한다. 즉 4가지 중 하나라도 만족하지 못하면 데드락은 발생하지 않는다.
데드락 발생조건 상세
각 조건별로 상세 내역을 알아보자.
상호 배제(Mutual exclusion)
한 번에 오직 한 개의 프로세스만이 자원에 접근 가능
예를들면 데이터베이스 연결 풀, 쓰기용 파일 열기, 레코드 락, 세마포어
만약 프로세스의 수보다 자원의 수가 더 많으면 실질적으로 상호 배제가 깨진다고 볼 수 있다. 자원을 접근함에 있어서 제약이 없기 때문이다.
하지만 대부분의 경우 접근할 자원이 부족한 경우가 많다.
잠금과 대기(Hold & Wait)
한 개 이상의 자원을 가진(Hold) 프로세스가 다른 프로세스 소유의 자원을 기다리는 것(Wait)
선점 불가(No preemption)
한 프로세스가 다른 프로세스로 부터 자원을 빼앗지 못하는 것
순환 대기(Circular wait)
프로세스 연쇄적(환형)으로 자원을 대기하는 상태
예를 들면
P1, P2 : 프로세스
R1, R2 : 자원
P1은 R1을 점유하고 있고 P2는 R2을 점유하고 있는 상태에서 P1은 R2가 필요하고, P2는 R1이 필요한 상태
출처 http://beginnersbook.com/2015/04/deadlock-in-dbms/
이것이 환형이기 때문에 프로세서와 리소스의 수는 각각 N개 이상일 수 있다.
데드락을 깨자
데드락 무시
이 방법은 해당 어플리케이션이 데드락이 발생하지 않는다고 가정하 하는 것이다. 즉, 실제로는 데드락은 무시하면 안된다. 데드락 발생을 정상적인 동작이 아니라고 판단하는 것이고 최후의 수단으로 두는 방식
Ostrich algorithm : 데드락이 발생하면 시스템 재시작
데드락 회피
순환 대기가 발생하지 않도록 자원의 할당 상태를 검사한다.
은행원 알고리즘(Dijkstra)
프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는 지를 사전에 검사하여 교착상태의 발생을 회피하는 기법
- 대출 : 자원할당
- 은행의 잔고 : 자원
- 대출상환 : 자원해제
- 안전상태(safe) : 대출 후 잔고가 있음
- 불안전상태(unsafe) : 대출 후 잔고가 마이너스가 됨
비교
은행원 알고리즘 기준
- 고객이 은행에 대출을 신청한다.
- 은행원은 대출이 가능한지 심사한다.
- 대출이 가능하면 대출해준다.(safe)
- 대출이 불가능하면 대출해주지 않는다.(unsafe)
어플리케이션 기준
- 프로세스가 자신에게 필요한 자원들의 선점을 요청
- 알고리즘이 자원들 선점이 가능한지 검증
- 자원들 선점이 가능하면(safe) 자원을 할당한다.
- 자원들 선점이 불가능하면(unsafe) 하면 요청을 거절한다. - 데드락의 위험이 있으므로
잠금과 대기 조건 깨기 와 일부 비슷해 보인다.
데드락 감지
프로세스를 모니터링해서 데드락을 유발하는 프로세스를 감지한다. 그 후
- 해당 프로세스를 죽인다.
- 데드락 상태였던 프로세스가 죽고난 자원을 풀어서 다른 프로세스에서 선점할 수 있게 열어둔다.
단점
CPU 사용율이 높아서 성능 하락
데드락 예방
상호 배제 조건 깨기
상호 배제 조건 자체를 비켜가기
- 자원을 동시 사용가능하게 만듬 : ex)
AtomicInteger - 프로세스 수보다 자원의 수를 더 늘림 : 상호 배제할 필요가 없어짐
하지만 대부분의 경우 자원은 제한적이다. 상호 배제 조건을 깨기는 매우 힘든 경우가 많음
잠금과 대기 조건 깨기
대기가 발생하지 않도록 해서 비켜가기
각 자원을 점유하기 전에 필요한 자원들이 다 확보 가능한지 확인한다. 만약 단 하나의 자원이라도 점유하지 못한다면 지금까지 점유한 자원을 몽땅 내놓고 처음부터 다시 시작한다.
단점
- 기아(Starvation) : 한 프로세스가 계속해서 필요한 자원을 점유하지 못함
- 라이브락(Livelock) : 여러 프로세스가 한꺼번에 잠금 단계로 진입하는 바람에 계속해서 자원을 점유했다 풀었다를 반복한다.
- 예를 들면 길을 가다 사람 2명이 서로 마주쳤는데 서로 똑같이 왼쪽 오른쪽 피하면서 갈 길을 못가는 상태
- Deadlock는 프로세스가 대기상태인데, Livelock는 프로세스가 계속 활성화된 상태에서 잠금상태에 빠짐.
- Deadlock를 회피하기 위해서 프로그램을 잘못 만들게 되면 Livelock에 빠지는 경우가 많다.
- 프로세스가 모든 자원을 할당받기 위해 오랜시간 대기상태에 있게 됨
- CPU 사용율이 높아짐
선점 불가 조건 깨기
다른 프로세스로 부터 자원을 뺏어올 수 있게 한다. 하지만 모든 요청 관리의 난이도가 높음
순환 대기 조건 깨기
모든 프로세스가 일정 우선순위 를 가지고 그 순서로 자원을 할당하면 데드락을 예방할 수 있음
단점
- 자원을 할당하는 순서와 자원을 사용하는 순서가 다를 수 있다. 그래서 대기시간이 길어질 수 있음
- 때로는 순서에 따라 자원 할당하기가 어렵다.
참고
