Deadlock
태그 :
- 개념
- - Multi processing 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태 - 교착상태에 있는 프로세스들은 결코 실행을 끝낼 수 없으며 시스템 자원이 묶여있어서 다른 작업을 시작하는 것도 불가능
1. 교착상태(Deadlock)의 개요
가. 교착상태(Deadlock)의 정의
- Multi processing 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태
- 교착상태에 있는 프로세스들은 결코 실행을 끝낼 수 없으며 시스템 자원이 묶여있어서 다른 작업을 시작하는 것도 불가능
나. 교착상태와 무한대기의 비교
구분 |
Deadlock(교착상태) |
Starvation(무한대기) |
정의 |
다수의 프로세스가 아무 일도 못하고 특정사건 무한대기 |
특정 프로세스가 자원을 할당 받기 위한 무한정 대기 상태 |
발생원인 |
상호배제, 점유와 대기, 비선점, 환형대기 |
자원의 편중된 분배정책 |
해결방안 |
예방, 회피, 발견, 회복 |
Aging 기법 |
2. 교착상태의 개념도 및 발생 조건
가. 교착상태의 개념도
나. 교착상태의 발생원인
- 교착상태는 한 시스템에서 다음 네 가지 조건이 동시 성립 시 발생
원인 |
상세 내역 |
상호배제 (Mutual Exclusion) |
프로세스들이 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용하지 못함 |
점유와 대기 (Block & Wait) |
프로세스가 어떤 자원을 할당 받아 점유하고 있으면서 다른 자원을 요구 |
비선점 (Non Preemption) |
프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없으며, 점유하고 있는 프로세스 자신만이 해제 가능 |
환형 대기 (Circular wait) |
프로세스간 자원 요구가 하나의 원형을 구성 |
- 프로세스들이 서로 남의 프로세스가 자원 내어주기를 기다리면서 영원히 block되어 있는 상태
- 모든 트랜잭션들이 실행을 전혀 진전시키지 못하고 무한정 기다리고 있는 상태
ㆍT1은 T2가 데이터 아이템 x를 unlock하기 기다림
ㆍ T2는 데이터 아이템 x를 locking하고 있는 상태
ㆍ T2는 T1d이 데이터 아이템 y를 unlock하기 기다림
ㆍ T1는 데이터 아이템 y를 locking하고 있는 상태
3. 교착상태의 해결 방안
가. 교착상태의 예방(Prevention)
- 상호배제 예방 : 상호배제 사용하지 않음(동시액세스 허락)
- 부분할당 예방: 프로세스가 필요로 하는 자원을 일시에 요구/할당
- 비선점 예방 : 자원임시 할당해제 및 원상복구(다루기가 힘듦)
- 환형대기 예방 : 모든 자원 고유번호 지정하여 환형대기 예방
나. 회피(Avoidance)-Banker’s Algorithm(은행가 알고리즘)
- 운영체제(OS)는 자원의 상태를 감시
- 프로세스는 사전에 자기 작업에서 필요한 자원의 수를 제시
- OS는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태인지 면밀하게 분석
- OS는 안전한 상태를 유지할 수 있는 요구만을 수락, 그 외의 요구는 만족될 때 까지 계속 거절
다. 교착상태의 발견(Detection)
- 시스템의 상태를 감시하는 알고리즘을 통하여 교착상태를 검사하는 알고리즘
- 시스템의 자원할당 그래프로 교착상태검출(Graph reduction, cycle Detection, Knot detection)
- 교착상태 발생 시 자원할당 소거
라. 교착상태의 회복(Recovery)
- Deadlock이 없어질 때까지 프로세스를 순차적으로 Kill하여 제거
- 프로세스 종료비용 최소화 : 우선순위,진행비용,복귀비용 등
- 자원의 우선순위 할당 : 희생자 선택,복귀,기아상태
4. 교착상태 회피기법- 타임스탬프의 Wait-die와 Wound-wait 기법 비교
가. 내용 : 트랜잭션을 유일하게 식별할 수 있는 식별자(identifier)를 타임스탬프라 하며, 이는 트랜잭션이 실행을 시작하는 순서에 기초한다. 따라서 타임스탬프를 이용하여 트랜잭션이 기다려야 할 지, 복귀해야 할 지를 결정
나. Wait-die와 wound-wait비교
비고 |
Wait-die |
Wound-wait |
정의 |
오래된 트랜잭션 기다리고, 새로운 트랜잭션이 Rollback 되고 다시 계획 |
오래된 트랜잭션이 새로운 트랜잭션을 rollback 시키고 이를 다시 계획 |
트랜잭션 양 |
lock을 요청하는 단계 중에 abort되어 재시작되므로, abort되는 트랜잭션의 처리된 양이 적음 |
처리도중 높은 우선 순위 트랜잭션에 의해 abort되므로, 그 동안 처리된 일이 모두 무시되어 불필요한 작업 수행 |
공통점 |
- 두 방법 모두 우선 순위가 높은 트랜잭션이 낮은 우선순위의 트랜잭션을 abort 시킴 - 중지된 트랜잭션은 기존 타임스탬프를 가지고 재시작 - 결국 시스템에서 가장 높은 우선 순위를 갖게 되어 완료됨 - 구현이나 관리가 waits-for graph보다 쉬움 |
5. RULE
가. WAIT-DIE Rule:
If Ti requests a lock on a data item which is already locked by Tj, then Ti is permitted to wait if ts(Ti)<ts(Tj).
If ts(Ti)>ts(Tj), then Ti is aborted and restarted with the same timestamp.
➠if ts(Ti)<ts(Tj) then Ti waits else Ti dies
➠non-preemptive:Ti never preempts Tj
➠prefers younger transactions
나. WOUND-WAIT Rule:
If Ti requests a lock on a data item which is already locked by Tj, then Ti is permitted to wait if ts(Ti)>ts(Tj).
If ts(Ti)<ts(Tj), then Tj is aborted and the lock is granted to Ti.
➠if ts(Ti)<ts(Tj) then Tj is wounded else Ti waits
➠ preemptive:Ti preempts Tj if it is younger
➠prefers older transactions
종류 |
설명 |
비고 |
wait-die 기법 |
트랜잭션 Ti가 이미 Tj가 로크한 데이타 아이템을 요청할 때 만일 Ti의 타임스탬프가 Tj의 것보다 작은 경우(즉 TS(Ti) < TS(Tj)가 되어 Ti가 고참인 경우)에는 Ti는 기다린다. 그렇지 않으면 Ti는 복귀(즉 die)하고 다시 시작한다 (비선점 기법) |
-고참 트랜잭션이 신참 트랜잭션을 기다림 -고참 트랜잭션이 가지고 있는 데이타를 신참 트랜잭션이 요구하면 복귀 후 재실행 => 불필요한 복귀가 자주 일어날 가능성 |
wound-wait 기법 |
트랜잭션 Ti가 이미 트랜잭션 Tj가 로크한 데이타 아이템을 요청할 때 Ti의 타임스탬프가 Tj의 것보다 클 경우 (즉 TS(Ti) > TS(Tj)가 되어 Tj가 고참인 경우)에는 기다린다. 그렇지 않으면 Tj는 복귀해서 (즉 Ti는 Tj를 상처 입힌다) 다시 시작한다 (선점 기법) |
-고참 트랜잭션은 신참 트랜잭션을 기다리지 않음 -신참 트랜잭션이 가지고 있는 데이타를 고참 트랜잭션이 요구하면 신참 트랜잭션은 복귀 후 재실행 -신참 트랜잭션은 기다리기만 하면 됨 => 불필요한 복귀가 비교적 덜 일어남 |
6. 교착상태 탐지기법- 대기 그래프 (wait for graph)
가. 교착상태의 필요충분조건 중 하나인 환형대기 조건을 탐지하여 발견되면 트랜잭션 하나를 취소시키는 방법
구분 |
설명 |
환형대기 탐지방법 |
-실행 중인 각 트랜잭션에 대해 노드를 만든다 -트랜잭션 Tj가 로크한 데이터 아이템 x에 대해서 Ti가 로크하기 위해 기다리고 있으면 방향간선 Ti -> Tj를 첨가한다 -이런 방식으로 구축된 대기 그래프에 사이클이 생성되면 교착상태로 판단함 |
복구방법 |
-교착상태와 관련있는 트랜잭션 하나를 선정하여 취소시키고 그 트랙잭션에 의해 변경된 데이터 아이템들은 원상태로 회복시킨다 -일반적으로 취소되는 트랙잭션은 작업이 가장 적게 수행된 (비용 요인) 트랜잭션을 선정하는 것이 효율적이다 (기아문제를 해결하기 위해서는 희생자로 선택되는 횟수를 제한할 필요가 있다) |
[참고] Livelock
- Lock : 잠금이 발생한 상황
- Blocking : 잠금을 발생시킨 프로세스간 차단행위
- Deadlock: 두 개 이상의 프로세스가 블록 된 채로 상대방이 보유한 자원을 해재하기를 기다리는 상태로 두 개 이상의 프로세스가 경계구역에 동시에 들어가지 못하게 하는 상호 배재 때문에 발생
- Livelock: 데드락은 프로세스 집합 내의 프로세스들이 요구하는 자원을 할당 받지 못해서 블록된 상태로 계속 대기하는 반면 라이브 락은 자원을 할당 받기 위해 상태를 계속 바꾸지만 더 이상 진행되지 못한다.
외나무 다리에서 서로 비키지 않고 대기하는 것이 데드락, 서로 비켰다가 다시 전진하는 것이 라이브 락.
예를 들면 좁은 길을 걷고 있다가 대면한 보행자 2명이 서로 상대가 피하려고 한 방향으로 움직여 버려 피할 수 없는 경우가 있다. 다음에 반대의 방향으로 피할 려고 하지만 피할 수 없다. 이러한 상황이 계속 되어 몇 시간이 지나도 엇갈릴 수 없게 되는 상황에 해당한다.
그림1 의 상황에서 서로 양보하려다 보니 그림 2의 상황이 되고, 또 서로 양보하려다 보니 그림 3이 되고 이것이 계속 반복 되어 A와B는 서로 지나가지 못하는 상태.
Sql Query 실행기에서의 Live Lock
Sql Query 실행기를 두 개 띄우고, 첫번째 Sql Query 실행기에서 특정 테이블에 대하여 Update문을 실행하고 Commit이나 RollBack은 실행하지 않는다.
두번째 Sql Query 실행기에서 똑같은 update문을 실행하면 첫번째 Sql이 종료되지 않았으므로 두번째 Sql은 Livelock 상태.
첫번째 Sql이 Commit이나 RollBack으로 명령이 종료되면 두번째 Sql은 Livelock상태가 종료되고 Update문이 실행.