교착상태(Deadlock)
태그 :
- 개념
- Multi processing 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태 교착상태에 있는 프로세스들은 결코 실행을 끝낼 수 없으며 시스템 자원이 묶여있어서 다른 작업을 시작하는 것도 불가능
I. 교착상태(Deadlock)의 개요
가. 교착상태(Deadlock)의 정의
- Multi processing 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태
- 교착상태에 있는 프로세스들은 결코 실행을 끝낼 수 없으며 시스템 자원이 묶여있어서 다른 작업을 시작하는 것도 불가능
나. 교착상태와 무한대기의 비교
구분 |
Deadlock(교착상태) |
Starvation(무한대기) |
정의 |
다수의 프로세스가 아무 일도 못하고 특정사건 무한대기 |
특정 프로세스가 자원을 할당 받기 위한 무한정 대기 상태 |
발생원인 |
상호배제, 점유와 대기, 비선점, 환형대기 |
자원의 편중된 분배정책 |
해결방안 |
예방, 회피, 발견, 회복 |
Aging 기법 |
II. 교착상태의 개념도 및 발생 조건
가. 교착상태의 개념도
나. 교착상태의 발생원인
- 교착상태는 한 시스템에서 다음 네 가지 조건이 동시 성립 시 발생
원인 |
상세 내역 |
상호배제 (Mutual Exclusion) |
프로세스들이 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용하지 못함 |
점유와 대기 (Block & Wait) |
프로세스가 어떤 자원을 할당 받아 점유하고 있으면서 다른 자원을 요구 |
비선점 (Non Preemption) |
프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없으며, 점유하고 있는 프로세스 자신만이 해제 가능 |
환형 대기 (Circular wait) |
프로세스간 자원 요구가 하나의 원형을 구성 |
III. 교착상태의 해결 방안
가. 교착상태의 예방(Prevention)
- 상호배제 예방 : 상호배제 사용하지 않음(동시액세스 허락)
- 부분할당 예방: 프로세스가 필요로 하는 자원을 일시에 요구/할당
- 비선점 예방 : 자원임시 할당해제 및 원상복구(다루기가 힘듦)
- 환형대기 예방 : 모든 자원 고유번호 지정하여 환형대기 예방
나. 회피(Avoidance)-Banker’s Algorithm(은행가 알고리즘)
- 운영체제(OS)는 자원의 상태를 감시
- 프로세스는 사전에 자기 작업에서 필요한 자원의 수를 제시
- OS는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태인지 면밀하게 분석
- OS는 안전한 상태를 유지할 수 있는 요구만을 수락, 그 외의 요구는 만족될 때 까지 계속 거절
다. 교착상태의 발견(Detection)
- 시스템의 상태를 감시하는 알고리즘을 통하여 교착상태를 검사하는 알고리즘
- 시스템의 자원할당 그래프로 교착상태검출(Graph reduction, cycle Detection, Knot detection)
- 교착상태 발생 시 자원할당 소거
라. 교착상태의 회복(Recovery)
- Deadlock이 없어질 때까지 프로세스를 순차적으로 Kill하여 제거
- 프로세스 종료비용 최소화 : 우선순위, 진행비용, 복귀비용 등
- 자원의 우선순위 할당 : 희생자 선택, 복귀, 기아상태
IV. Wait-die와 Wound-wait 기법 비교
비고 |
Wait-die |
Wound-wait |
정의 |
오래된 트랜잭션 기다리고, 새로운 트랜잭션이 Rollback 되고 다시 계획 |
오래된 트랜잭션이 새로운 트랜잭션을 rollback 시키고 이를 다시 계획 |
트랜잭션 양 |
lock을 요청하는 단계 중에 abort되어 재시작되므로, abort되는 트랜잭션의 처리된 양이 적음 |
처리도중 높은 우선 순위 트랜잭션에 의해 abort되므로, 그 동안 처리된 일이 모두 무시되어 불필요한 작업 수행 |
공통점 |
- 두 방법 모두 우선 순위가 높은 트랜잭션이 낮은 트랜잭션을 abort 시킴 - 중지된 트랜잭션은 기존 타임스탬프를 가지고 재시작 - 결국 시스템에서 가장 높은 우선 순위를 갖게 되어 완료됨 - 구현이나 관리가 waits-for graph보다 쉬움 |
V. 교착상태 해결을 위한 전체 시스템 설계
가. 내부 시스템 자원을 순서화
- PCB, 버퍼, Semaphore 등의 자원 순서화
나. 사용자 작업에 대한 주기억 장치 선점
- 선점은 Paging, Segmentation, Swapping 시스템에서 가장 효율적인 접근법
- 선점이 불가능 하면 주기억장치를 작업 자원의 부류에 포함시킴
다. 작업이나 작업단계의 자원필요량 산정
라. 교체 가능 공간 사전 할당
- 요구된 기억장치를 사전에 할당
[ 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문이 실행.