교착 상태
교착 상태(deadlock)
- 스레드가 자원을 요청했을 때, 그 자원이 그 순간 이용할 수 없다면 스레드는 대기 상태에 들어간다. 때때로 대기 중인 스레드가 다시는 상태를 변경하지 못하는 경우가 발생하는데, 이는 해당 스레드가 요청한 자원이 다른 대기 중인 스레드에 의해 점유되어 있을 때 발생한다. 이러한 상황을 교착상태(deadlock)라고 한다.
시스템 모델
- 시스템은 여러 경쟁 스레드간에 분산 될 한정된 수의 자원으로 구성된다.
- 자원은 여러 유형(또는 클래스)으로 분할될 수 있으며, 각각은 몇 개의 동일한 인스턴스로 구성된다.
- CPU 사이클, 파일 및 IO 장치 등
- 시스템에 4개의 CPU가 있는 경우 자원 유형 CPU에는 4개의 인스턴스가 존재한다.
스레드는 자원을 사용하기 전에 자원를 요청해야하며 자원을 사용한 후에 자원을 해제해야 한다. 스레드는 지정된 작업을 수행하는 데 필요한만을의 자원를 요청할 수 있다.
- 요청된 자원의 수는 시스템에서 사용할 수 있는 총 자원 수를 초과할 수 없다.
일반적인 작동 모드에서 스레드가 자원를 활용하는 순서
- 요청 : 스레드가 자원을 요청한다. 자원을 즉시 할당받을 수 없는 경우 요청 스레드는 자원을 획득할 때 까지 기다려야 한다.
- 사용 : 스레드는 자원에 대해 작업을 수행할 수 있다.
- 해제 : 스레드가 자원을 해제한다.
각 스레드가 커널에서 관리하는 자원을 사용할 때마다, 운영체제는 해당 스레드가 자원을 요청했고 할당받았는지를 확인한다. 시스템 테이블은 각 자원이 사용 가능한지 또는 할당된 상태인지를 기록한다. 할당된 자원에 대해서는 그 자원이 할당된 스레드도 테이블에 기록된다. 만약 스레드가 다른 스레드에게 이미 할당된 자원을 요청하면, 해당 스레드는 그 자원을 기다리는 대기 큐에 추가될 수 있다.
스레드 집합이 교착 상태에 있다는 것은, 해당 집합의 모든 스레드가 자신이 요청한 이벤트가 다른 스레드에 의해 발생해야만 진행할 수 있는 상황을 의미한다.
- 주요 관심사 이벤트는 자원의 획득과 해제이다.
- 자원은 일반적으로 논리적 자원이다.(뮤텍스 잠금, 파일, 세마포어)
- 그 외에도 네트워크 인터페이스에서의 읽기나 IPC(프로세스 간 통신) 기능과 같은 이벤트도 교착 상태를 초래할 수 있다.
멀티스레드 어플리케이션에서의 교착 상태
POSIX 뮤텍스 잠금을 사용하는 다중 스레드 Pthread 프로그램에서 교착 상태가 발생하는 예시
pthread mutex lock : 락을 획득
pthread_mutex_unlock : 락을 해제// thread_one이 수행하는 함수
void *do_work_one(void *param) {
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/* 작업 수행 */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}
// thread_two이 수행하는 함수
void *do_work_two(void *param) {
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/* 작업 수행 */
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
pthread_exit(0);
}thread_one이 first_mutex를 획득하고 thread_two가 second_mutex를 획득할 때 교착 상태가 발생할 수 있다.(자원을 획득 한채 서로의 자원을 획득해야 함)
위 상황은 교착 상태가 항상 발생하는 것은 아니다. thread_two 스레드가 락을 획득하려고 시도하기 전에, thread_one이 first_mutex와 second_mutex를 획득하고 해제하면 교착상태가 일어나지 않을 수도 있다.
Livelock
- 데드락과 유사하지만 다르다.
- 둘 이상의 스레드가 진행이 되는것을 막는것은 같지만 데드락과 다른 이유로 스레드가 진행 할 수 없음
- 지속적으로 실패하는 작업을 재시도할 때 발생한다.
- 길을 걷다가 사람을 마주칠 때, 같은 방향으로 자리를 피해서 앞으로 가지 못하는 상황과 유사하다.
- 라이브락은 동시에 실패한 연산을 재시도 할 때 발생한다.
- 각각의 스레드가 재시도 연산을 랜덤한 시간에 하도록 하면 피할 수 있음
교착 상태 특성
필요 조건
교착 상태가 발생하는 네 가지 조건(동시에 성립할 때 발생)
- 상호 배제(Mutual exclusion) : 적어도 하나의 자원이 공유 불가능한 모드로 유지 되어야 한다. 한번에 하나의 스레드만 자원을 사용할 수 있다.
- 보유 대기(Hold and wait) : 스레드는 적어도 하나의 자원을 보유하고 있어야 하며 현재 다른 스레드가 보유하고 있는 추가 자원을 획득하기 위해 대기해야 한다.
- 비선점(No preemption) : 자원이 선점되지 않는다. 스레드가 작업을 완료한 후 자원을 보유하고 있는 스레드가 자발적으로 자원을 해제한다.
- 순환 대기(Circular wait) : 스레드 T0이 T1이 점유한 자원을 기다리고, T1은 T2의 자원을 기다리고, T2은 T1의 자원을 기다린다.
자원 할당 그래프
자원 할당 그래프(Resource-Allocation Graph)
- 정점들의 집합 V와 엣지들의 집합 E로 이루어짐
- V는 두가지 타입이 존재한다.
- T는 시스템에서 활성화된 스레드
- R은 모든 자원 타입들을 나타낸다.
- Ti → Rj;는 Ti가 Rj의 자원을 요청하는 것을 나타낸다.
- request edge라고 한다.
- Rj → Ti;는 Rj가 Ti에 할당되어 있다는 것을 나타낸다.
- assignment edge라고 한다.
자원할당 그래프 예시
The sets T, R, and E:
T = {T1, T2, T3}
R = {R1, R2, R3, R4}
E = {T1 → R1, T2 → R3, R1 → T2, R2 → T2, R2 → T1, R3 → T3}
점들은 자원을 나타낸다.
그래프에서 순환이 발생하지 않기 때문에 교착 상태에 빠지지 않음
두 개의 사이클 발생
T1 → R1 → T2 → R3 → T3 → R2 → T1
T2 → R3 → T3 → R2 → T2T2는 R3을 기다리고 있고, T3는 T1 또는 T2가 R2를 해제하기를 기다리고 있다. 그리고 T1은 T2가 R1을 해제하기를 기다리고 있다.
T1 → R1 → T3 → R2 → T1순환이 발생하지만 교착 상태에 빠지지 않는다. T4가 R2를 해제하면 T3는 R2를 할당받아 순환이 사라짐
교착 상태를 다루는 방법
- 문제를 완전히 무시하고 시스템에서 교착 상태가 발생하지 않는 것처럼 행동할 수 있다.
- 교착 상태를 방지하거나 피하기 위해 프로토콜을 사용하여 시스템이 교착 상태에 빠지지 않도록 할 수 있다.
- 시스템이 교착 상태에 들어가는 것을 허용하고, 감지한 후 회복할 수 있다.
교착 상태 예방
상호 배제(Mutual exclusion)
일반적으로 일부 자원은 본질적으로 공유할 수 없기 때문에 상호 배제 조건을 거부함으로써 교착 상태를 방지할 수 없다.
보유 대기(Hold and wait)
보유 대기 조건이 발생하지 않기 위해서는 스레드가 자원을 요청할 때 다른 자원을 소유하지 않도록 보장해야 한다.
보유 대기를 방지하기 위해 다음과 같이 할 수 있다.
- 스레드가 실행을 시작하기 전에 필요한 모든 자원을 요청하고 할당받도록 하는 방법
- 스레드가 자원을 전혀 소유하지 않은 상태에서만 자원을 요청할 수 있도록 하는 방법.
- 추가 자원을 요청하기 전에 현재 할당된 자원을 모두 해제 해야한다.
보유 대기 방지 방법의 단점
- 자원 활용도가 낮다.
- 기아 상태가 발생할 수 있다.
- 인기 있는 자원이 계속 다른 스레드들에 할당될 수 있음
비선점(No Preemption)
비선점이 발생하지 않게 하려면 다음과 같이 할수 있다.
- 첫 번째 방법
- 어떤 자원을 점유하고 있는 스레드가 즉시 할당할수 없는 다른 자원을 요청하면
- 현재 점유하고 있는 모든 자원이 선점된다.
- 선점된 자원들은 그 스레드가 기다리고 있는 자원들의 리스트에 추가된다.
- 스레드는 요청 하고 있는 자원과 점유 했었던 자원들을 다시 획득 할 수 있을때만 시작할 수 있다.
- 두 번째 방법
- 스레드가 어떤 자원을 요청하면 그 자원이 사용 가능한지 검사한다.
- 만약 사용 가능하다면 그 자원들을 할당한다.
- 만약 사용이 불가능하다면
- 그 자원들을 보유하면서 추가의 자원을 요구하는 다른 대기중인 스레드에 할당되어있는지 검사한다.
- 할당된 대기 중인 스레드가 있다면 그 스레드로부터 원하는 자원을 선점해 이들을 요청하는 스레드에 할당한다.
- 자원을 이용할 수 없거나 다른 대기 스레드에 점유되어 있지 않다면
- 요청 스레드는 대기해야 한다.
- 대기 하는 동안 보유한 자원들이 선점될 수 있다.
- 스레드는 대기중에 선점된 자원과 요청된 자원을 회복할 때 다시 시작할 수 있다.
- 그 자원들을 보유하면서 추가의 자원을 요구하는 다른 대기중인 스레드에 할당되어있는지 검사한다.
이 방법들은 mutex 락과 세마포 같은 자원에는 일반적으로 적용할 수 없다.
순환 대기(Circular Wait)
상호 배제, 보유 대기, 비선점은 대부분 상황에서 일반적으로 실용적이지 않다. 순환 대기 조건은 필요 조건 중 하나를 무효화하여 실용적인 해결책을 제시할 수 있다.
순환 대기 조건이 성립되지 않도록 하는 방법
- 모든 자원 유형에 전체적인 순서를 부여하여, 각 프로세스가 오름차순으로 자원을 요청하도록 요구한다.
- 스레드는 초기에 Ri의 인스턴스를 요청할 수 있다. 그 후 F(Rj) > F(Ri)일때 Rj의 인스턴스를 요청할 수 있다.
순서를 부여한다고 해서 교착 상태 예방을 보장하지는 않는다.
void transaction(Account from, Account to, double amount) {
mutex lock1, lock2;
lock1 = get lock(from); // 첫 번째 계좌에 대한 락 획득
lock2 = get lock(to); // 두 번째 계좌에 대한 락 획득
acquire(lock1); // 첫 번째 락 잠금
acquire(lock2); // 두 번째 락 잠금
withdraw(from, amount); // 출금
deposit(to, amount); // 입금
release(lock2); // 두 번째 락 해제
release(lock1); // 첫 번째 락 해제
}transaction(checking_accoumt, savings_account, 25.0)
transaction(savings_account, checking_accoumt, 50.0)위 코드에서 서로 자원을 가지고 있는 상태에서 자원을 기다리므로 순환 대기가 발생 한다.
