자원을 요청한 스레드도 대기하고, 자원을 점유한 스레드도 대기해
결코 그 상태를 변경시킬 수 없는 상황을 deadlocks이라고 부른다.
- 모든 프로세스가 다른 프로세스에 의해서만 일어나는 이벤트를 기다리는 상황이라고도 정리할 수 있다.
보통 운영체제들은 교착 상태 예방을 제공하지 않는다.
따라서 프로그래머가 잘 설계해야 한다.
1. System Model
시스템은 스레드들 사이에 분배되어야 할 자원들로 구성된다.
Mutex lock과 semaphore와 같은 다양한 동기화 도구들도 시스템 자원이며,
이들은 가장 일반적인 교착 상태의 발원지이다.
락은 보통 특정 자료구조와 연관되어 있다.
따라서 락의 각 인스턴스에는 일반적으로 고유한 자원 클래스가 할당된다.
프로세스는 요청, 사용, 방출 순으로만 자원을 사용할 수 있다.
자원의 요청과 방출은 시스템 콜이다.
(파일의 open()과 close() / malloc()과 free()도 이의 예다)
운영체제는 매번 스레드가 자원을 요청했는지와 할당받았는지를 확인한다.
시스템 테이블이 각 자원이 가용 상태인지, 어느 스레드에 할당 되었는지 기록한다.
어떤 스레드가 다른 스레드에 할당된 자원을 요청하면, 그 자원을 기다리는 스레드 큐에 입력될 수 있다.
다중 스레드 응용 개발자는 동기화 도구를 사용할 때, 반드시 교착 상태의 가능성을 염두에 두어야 한다.
2. Deadlock in Multithreaded Applications
어떤 특정 스케줄링 상황에서만 발생할 수 있는 교착 상태를 식별하고 검사하는 작업은 어렵다.
2.1 Livelock
livelock은 또 다른 형태의 liveness 장애이다.
교착 상태와 유사하게 두 개 이상의 스레드가 진행되는 것을 방해하지만 그 원인이 다르다.
라이브락은 스레드가 실패한 행동을 계속 시도할 때 발생한다.
복도에서 사람을 마주쳐 계속 서로 같은 방향으로 피해주는 상황과 같다.
봉쇄되지는 않았지만 앞으로 진행할 수 없다.
라이브락은 pthread_mutex_trylock() 함수로 설명할 수 있다.
각 스레드는 trylock()을 호출하여 실패하고, 각자의 락을 해제한 후 동일한 행동을 무한 반복한다.
라이브락은 일반적으로 스레드가 실패한 작업을 동시에 재시도할 때 발생한다.
따라서 재시도하는 시간을 무작위로 정하면 회피할 수 있다.
교착상태만큼 흔히 일어나지는 않지만 어려운 문제이며,
교착상태와 같이 특정 스케줄링 상황에서만 발생할 수 있다.
3. Deadlock 특성
교착 상태를 특징 짓는 조건을 알아보자.
3.1 필요조건들
교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.
- 상호 배제(mutual exclusion) : 최소한 하나의 자원이 비공유 모드로 점유된다.
- hold and wait : 하나 이상의 자원을 점유한 채, 다른 스레드에 의해 점유된 자원을 얻기 위해 대기한다.
- 비선점(no preemption) : 자원들을 선점할 수 없다.
- circular wait : 요청의 간선이 하나의 고리를 만든다.
3.2 자원 할당 그래프
교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있다.
자원 할당 그래프가 cycle을 포함하면 교착 상태가 존재할 수 있다.
각 자원 유형이 여러 인스턴스를 가지면, 사이클이 있다고 해서 반드시 교착상태가 발생했음을 의미하지는 않는다.
4. 교착 상태 처리 방법
원칙적으로 교착 상태 문제를 처리하는 데는 다음 세 가지 방법이 있다.
- 무시
- 교착 상태를 예방하거나 회피하는 프로토콜 사용
- 복구
첫 번째 해결안이 Linux와 Windows를 포함해 대부분의 운영체제가 사용하는 방법이다.
데이터베이스와 같은 일부 시스템은 세 번째 해결안을 채택한다.
교착 상태를 예방하기 위해 예방 혹은 회피 기법의 하나를 사용한다.
교착 상태 예방은 교착 상태 필요 조건 중 하나 이상이 성립하지 않도록 보장하는 일련의 방법이다.
교착 상태 회피는 자원에 대한 추가적인 정보를 통해 교착 상태를 예측한다.
시스템은 교착 상태가 발생했는지 확인하기 위해
시스템의 상태를 조사하는 알고리즘과,
교착 상태 복구 알고리즘을 제공할 수 있다.
교착 상태를 탐지하고 복구하는 알고리즘이 없다면,
교착 상태가 일어났을 때, 시스템이 정지하고 수작업으로 재시동해야 할 수도 있다.
이 방법은 실제로 여러 운영체제에서 사용되고 있고,
이는 교착상태는 드물게 발생하고,
따라서 무시하는것이 더 효율적일 수 있기 때문이다.
시스템은 교착상태가 아닌 라이브니스 상황을 위해서라도
반드시 수동 복구 방법을 가지고 있어야 하며,
이를 교착상태의 복구에도 동일하게 사용할 수 있다.
5. 교착 상태 예방
데드락의 4가지 필요조건을 각각 별도로 검토해보자
5.1 상호 배제
mutex락과 같은 어떠한 자원들은 근본적으로 공유가 불가능하므로
일반적으로 상호배제를 거부함으로써 교착상태를 예방하는 것은 불가능하다.
5.2 Hold and wait
이를 막으려면 스레드가 자원을 요청할 때 다른 자원을 보유하지 않도록 보장해야 한다.
한가지 방법으로 각 스레드가 실행 전에 모든 자원을 요청하고 할당하는 프로토콜을 제공하는 것이다.
이는 자원 요청의 동적 특성으로 인해 실용적이지 않다.
대안으로 스레드가 자원을 갖고 있지 않을 때만 자원을 요청할 수 있도록 한다.
이 두 프로토콜은 두 가지 주요 단점이 있다.
첫째, 자원이 할당되었지만 장기간 사용하지 않아 자원 이용률이 낮을 수 있다.
둘째, 기아가 발생할 수 있다.
인기 있는 자원을 여러개 원하면 얻지 못해 무한정 대기해야 할 수 있다.
5.3 비선점
비선점이 성립되지 않을 것을 보장하기 위해,
만일 어떤 자원을 점유하고 있는 스레드가 대기해야 하는 자원을 요청하면,
현재 가지고 있는 자원을 묵시적으로 방출한다. (=가지고는 있으나 언제든 선점 당할 수 있다)
대안으로 한 스레드가 요청한 자원이 가용하면 할당하고,
아니면 그 자원을 점유한 스레드가 또 다른 자원을 위해 대기중인거였다면
선점해서 뺏는다.
이렇게 해도 안되면 대기해야 한다.
대기하는 동안 이 스레드가 가진 자원은 마찬가지로 선점될 수 있다.
스레드가 자원을 할당받고 대기중에 빼앗긴 모든 자원을 회복하면 다시 시작할 수 있다.
이 프로토콜은 cpu 레지스터나 데이터베이스 트랜잭션처럼
그 상태가 쉽게 저장되고 복원될 수 있는 자원에 종종 적용된다.
일반적으로 교착 상태가 가장 흔하게 발생하는 mutex나 세마포어에는 적용될 수 없다.
5.2 순환 대기
앞의 세 가지 방법은 사실 별로 실용적이지 않다.
순환대기를 와해할 한 가지 방법은
모든 자원 유형에 전체적인 순서를 부여하여 순서대로 자원을 요청하도록 하는 것이다.
대안으로, 스레드가 자원 유형 i의 인스턴스를 요청할 때마다,
F(i) >= F(j)인 모든 자원 i를 방출하도록 요구하는 방법이 있다.
이 때 동일한 유형의 자원을 여러 개 요청할 때, 한번에 모든 자원을 할당받아야 하는 점을 주의해야 한다.
이 두 가지 프로토콜을 사용하면 순환 대기 조건이 발생하지 않는다.
순서나 계층 구조를 정하는 것 자체만으로는 교착 상태를 예방할 수 없다.
수백 수천개의 락의 순서를 정하는 것은 어렵다.
개발자들은 그래서 해시함수를 이용해서 순서를 정했다.
락 순서를 부여한다고 해서 교착상태의 예방을 보장하지는 않는다.
6. 교착 상태 회피
교착 상태를 예방할 때 발생 가능한 부수적인 문제는
장치의 이용률이 저하되고 시스템 총처리율이 감소한다는 것이다.
다른 대안은 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것이다.
각 스레드의 요청과 방출에 대한 순서를 파악하고 있다면 스케줄 조율을 할 수 있다.
이를 위해 현재 가용 자원, 할당된 자원, 앞으로 요청할 혹은 방출할 자원등을 고려해야 한다.
교착상태 회피 알고리즘은 시스템에 순환 대기가 발생하지 않도록 자원 할당 상태를 검사한다.
6.1 안전 상태
시스템 상태가 안전하다는건
모든 프로세스나 스레드가 종료될 수 있는 순서가 존재하는 상태를 뜻한다.
즉, 시스템이 안전 순서를 찾을 수 있다는 것이다.
그렇다고 시스템이 불안전 상태라고 해서 반드시 교착 상태가 일어난다는 건 아니다.
시스템은 안전상태에 있다가도 불안전 상태로 전이할 수 있다.
회피 알고리즘의 기본 원칙은
시스템의 상태가 항상 안전 상태이도록 고수하는 것이다.
항상 자원을 즉시 할당해줄지 기다리게 할지 체크한다.
따라서 회피를 안쓸때보다 자원 이용률은 떨어진다.
6.2 자원 할당 그래프 알고리즘
만약 각 자원유형마다 하나의 인스턴스만 갖는다면 예약 간선을 추가 도입해 나타낸다.
예약 간선은 미래에 자원을 요청할 것이라는 걸 나타낸다.
사이클 탐지 알고리즘(O(n^2))을 이용해 안전성을 검사한다.
만약 사이클이 발견되지 않으면 자원을 할당해도 시스템은 안전하다.
사이클이 발견되면 요청을 대기해야 한다.
6.3 Banker's Algorithm
자원할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있으면 사용할 수 없다.
은행원 알고리즘은 이러한 상황에서도 쓸 수 있지만 효율은 보다 떨어진다.
은행원 알고리즘은 이 알고리즘을 은행에 적용하면
고객들이 현금을 찾으러 와도 일정한 순서에 의해 모든 요청을 다 들어줄 수 있게 되기 때문이다.
이 시스템에서는 스레드가 시작할 때
스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고해야 한다.
시스템은 이를 보고 요청을 들어주었을 때도 계속 시스템이 안전할 수 있을지 판단한다.
만약 안전하지 않다면 그 스레드는 다른 스레드가 끝날 때까지 기다리게 된다.
이를 구현하려면 몇 가지 자료구조가 필요하다.
n이 스레드의 수, m이 자원의 종류 수이다.
- Available: 각 종류별로 가용한 자원의 수를 나타내는 벡터
- Max : 각 스레드가 최대로 필요로 하는 자원의 개수를 나타내는 행렬.
Max[i][j] = k면 스레드i가 j자원을 k개 - Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬.
- Need : 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬
6.3.1 안전성 알고리즘
현재 가용한 자원의 수로 실행 가능한 스레드를 찾고,
있으면 끝내고 가용한 자원 +
없으면 모든 스레드가 끝난 상태인지 체크하고, 다 끝났으면 안전상태라고 판단
이는 자원의 종류 x (스레드 수)^2개의 연산이 필요하다.
6.3.2 자원 요청 알고리즘
자원 요청이 안전하게 들어줄 수 있는지 검사하는 알고리즘.
먼저 요청 개수랑 Need랑 비교해서 더 적어야 한다.
그 다음 요청 개수랑 Available을 비교해 더 적으면 다음 스텝으로 간다. 더 많으면 기다려야 한다.
이제 자원을 할당해준 것처럼 Available, Need등의 값들을 바꿔보고
바뀐 상태가 안전하면 할당해준다.
그게 아니면 원상태로 복원하고 해당 스레드는 대기해야 한다.
7. 교착 상태 탐지
만일 시스템이 교착 상태 예방이나 방지 알고리즘을 안쓰면 교착상태가 발생할 수 있다.
이러한 환경에선 반드시 다음 알고리즘들을 지원해야 한다.
- 시스템의 상태를 검사하는 알고리즘
- 교착 상태로부터 회복하는 알고리즘
