In concurrent computing, a deadlock is a state in which each member of a group waits for another member, including itself, to take action, such as sending a message or more commonly releasing a lock.Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, where software and hardware locks are used to arbitrate shared resources and implement process synchronization. In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process. If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock.
교착상태를 설명할 때 자주 사용되는 사진이죠?!
교착 상태(DeadLock)란 운영체제에서 시스템 자원에 대한 요구가 뒤엉킨 상태입니다.
즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 끝이 없는 대기에 빠지는 상황을 의미합니다.
프로세스 A와 B 모두 리소스 A,B를 얻어야 한다고 가정할 경우, T 시점에 프로세스 A가 리소스 A를 얻고 , 프로세스 B가 리소스 B를 얻었다면 T 시점 이후에 프로세스 A와 B는 아직 점유하고 있지 않은 리소스를 기다리게 됩니다.
하지만, 앞서 언급한 것 처럼, 프로세스 A와 B가 각각 하나의 리소스를 가지고 있기 때문에 두 프로세스는 계속 기다릴 수 밖에 없는 것이죠.
동기화 기법을 사용할 때 발생하게 되는 이슈 중 하나가 쓰레드간의 교착 상태현상입니다. 공유 객체인 A와 B가 존재한다고 할 때, 상호 교차 참조하는 연산을 수행하는 동기화된 블록을 수행할 경우교착 상태가 발생합니다. 이러한 교착 상태를 방지하기 위해 연산 수행 범위를 최소화하거나 혹은 두 객체의 참조 순서가 같게 합니다.(아래 예제의 방식입니다.) 또한 A,B 객체를 참조하는 별도의 객체를 생성하여 사용하는 방식으로 로직의 수정이 필요합니다.
[교착 상태가 발생하는 경우]
public class DeadLockEx {
public static void main(String[] args) {
final String resource1 = "Programmers";
final String resource2 = "DevCourse";
Thread t1 = new Thread() {
public void run() {
synchronized (resource1) {
System.out.println("Thread 1: locked resource1");
System.out.println("Thread 1: Waiting for resource2");
synchronized (resource2) {
System.out.println("Thread 1: locked resource2");
}
}
}
};
Thread t2 = new Thread() {
public void run() {
synchronized (resource2) {
System.out.println("Thread 2: locked resource2");
System.out.println("Thread 2: Waiting for resource1");
synchronized (resource1) {
System.out.println("Thread 2: locked resource1");
}
}
}
};
t1.start();
t2.start();
}
}
출력 결과
[교착 상태를 해결하는 방법 - 자원 순서 변경]
public class DeadLockEx {
public static void main(String[] args) {
final String resource1 = "Programmers";
final String resource2 = "DevCourse";
Thread t1 = new Thread() {
public void run() {
synchronized (resource1) {
System.out.println("Thread 1: locked resource1");
System.out.println("Thread 1: Waiting for resource2");
synchronized (resource2) {
System.out.println("Thread 1: locked resource2");
}
}
}
};
Thread t2 = new Thread() {
public void run() {
synchronized (resource1) {
System.out.println("Thread 2: locked resource1");
System.out.println("Thread 2: Waiting for resource1");
synchronized (resource2) {
System.out.println("Thread 2: locked resource2");
}
}
}
};
t1.start();
t2.start();
}
}
출력 결과
| 교착 상태가 발생하는 조건
상호 배제 조건(Mutual exclusion condition) - 하나의 리소스는 한 번에 한 프로세스 만이 사용할 수 있습니다. 이미 사용중인 리소스를 점유 및 사용하려면 요청한 자원이 해제될때까지 대기해야 합니다.
점유 대기 조건(Hold-and-wait condition) - 하나 이상의 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 추가적으로 점유하기 위해 대기하는 프로세스가 존재해야 합니다.
비선점 조건(No-preemption condition) - 다른 프로세스에게 할당 및 점유되고 있는 자원은 사용이 끝날 때까지 다른 프로세스가 강제로 뺏을 수 없습니다.
순환 대기 조건(Circular wait condition) - 앞서 확인한 그림처럼, 프로세스 A가 프로세스 B가 가지고 있는 자원을 점유하기위해 대기하고, 프로세스 B가 프로세스 A가 가지고 있는 자원을 점유하기 위해 대기하는 것을 의미합니다.
이 4가지 조건을 모두 만족하게 될 경우, 교착 상태에 빠지게 되는 것입니다.
| 교착 상태를 해결하는 방법
교착 상태 무시
교착 상태 무시방법에서는, 교착 상태가 거의 발생하지 않거나 혹은 발생하지 않을 것이라고 가정을 하는 것입니다. 이러한 방법은 우리가 흔히 사용하고 있는 윈도우와 유닉스등 운영체제에서 이러한 기법을 사용하고 있습니다.
성능이 저하되거나 교착 상태가 발생해 문제가 생긴다면 사용자가 인위적으로 프로세스를 종료하거나 시스템을 재부팅하는 식으로 해결합니다.
교착 상태 회피
회피 기법은 교착 상태가 발생할 가능성을 배제하지 않고 교착 상태가 발생할지 않을지를 예상하여 안전 상태(safe state)일때만 자원 요청을 허용하는 방법입니다.
안전 상태(safe state) - 교착 상태를 발생하지 않으면서 차례로 모든 프로세스에게 자원을 할당해 줄 수 있는 상태를 의미합니다.
안전 순서(safe sequence) - 프로세스에게 자원을 할당 등의 작업을 할 때 교착 상태를 발생하지 않은 순서를 찾을 경우 그 순서를 안전 순서라고 부릅니다.
불안전상태(unsafe sequence) - 안전 상태가 아닌 상황을 의미하며 교착 상태가 발생할 수 있는 상황입니다. 불안전 상태일 경우에는 안전상태가 될때까지 기다려야 하죠. - 교착 상태는 불안전 상태일 경우 일때 발생할 수 있는 것이므로 아래 그림처럼 표현할 수 있습니다. Safe state vs Unsafe state (And DeadLock)
은행원 알고리즘(Banker's Algorithm)
교착 상태 회피방법의 대표적인 기법으로 자원의 할당에 관한 여부를 결정하기 이전에 자원들에 대한 할당량을 판단 및 시뮬레이션을 하여 Safe state가 될 수 있을지 없을지를 판단합니다.
즉, 곧 대기중인 다른 프로세스들도 교착 상태가 발생하는지 안하는지를 확인하는 것입니다.
알고리즘의 예제를 살펴보기 이전에, 은행원 알고리즘을 적용하려면 자원의 양과 프로세스의 수가 일정해야 합니다.
은행원 알고리즘 예제
- 현재 가용 가능한 자원의 양은 4라고 가정하겠습니다.
- Max : 프로세스들이 작업을 완료하기 위해 필요한 최종 자원 - Allocation : 현재 시점에 프로세스에 할당 되어있는 자원 - Need : 프로세스가 작업을 완료하기 위해 필요한 추가 자원
프로세스
Max
Allocation
Need
Available
P1
8
2
6
P2
7
4
4
P3
4
3
5
1. P1 프로세스는 현재 할당된 자원은 2, 작업을 완료하기 위해 필요한 자원은 6입니다.
2. 하지만, 가지고 있는 자원은 4이므로 작업을 완료할 수 없습니다.
3. 반면, P2 프로세스는 할당된 자원이 4,필요한 자원이 4 그리고, 현재 가용 가능한 자원이 4이므로 작업을 완료할 수 있습니다. 그러므로, 현재 가용가능한 자원을 P2 프로세스에 할당합니다.
4. P2 프로세스의 작업이 완료된다면, 이전 가용 가능했던 자원(4) - 필요한 자원(4) + 프로세스의 작업을 최종적으로 완료하는데 필요한 자원(7) 을 계산한 7이 가용가능한 자원으로 생겼을 것입니다.
이와 같이, 프로세스들을 순회하며 , 프로세스들 간의 필요한 자원과 가용가능한 자원들을 비교하며 자원을 할당하는 것이 은행원 알고리즘입니다.
아무래도, 프로세스의 수와 자원이 고정되어 있다보니, 동적인 환경에 적합하지 않습니다.
교착 상태 탐지 및 회복
탐지 기법은 교착상태가 발생했는지 여부를 탐색하는 것입니다.
현재 시스템의 자원 할당 상태를 가지고 파악하는 것입니다. 대표적으로 자원 할당 그래프를 통해 탐지할 수 있습니다. https://blog.kakaocdn.net/dn/LLO72/btqENZv5gbB/sddKLOkvTXJdmwJoEDGClK/img.png
- 프로세스로부터 자원에 대한 간선은 자원에 대한 요청을 의미하며 프로세스가 기다리는 상태입니다.
- 자원에서부터 프로세스에 대한 간선은 자원이 해당 프로세스에 할당된 것을 의미합니다.
- 자원을 요청할 때마다 탐지 알고리즘이 호출될 경우 오버헤드가 발생할 수 있습니다.
여기서 잠깐! 오버헤드란?!
오버헤드는 프로그램의 실행흐름에서 나타나는 현상입니다. 이는 예상하지 못한 추가적인 메모리, 자원, 시간 등이 사용되는 것을 일컫습니다.
탐지 기법을 통해 데드락을 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하는 방법을 사용해야 합니다.
회복 방법으로는 크게 2가지를 이야기 할 수 있습니다.
1. 프로세스 중단시키는 방법
1-1. 교착 상태가 발생한 모든 프로세스를 중단시키는 방법
1-2. 프로세스를 하나씩 중단시키며 매번 탐지 기법을 사용하여 확인하는 방법 -> 1-1번 방법의 경우에는 작업중이던 다른 프로세스마저 중단시킬 수 있다는 단점이 있습니다. -> 1-2번 방법의 경우에는 매번 탐지 알고리즘을 호출해야하므로 그에 따른 부담이 생길 수 있습니다.
2. 자원 선점하는 방법
2-1. 교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하는 것입니 다. 이때, 우선순위, 수행된 정도 등 다양한 사항을 고려하여 자원을 선점합니다.
교착 상태 예방
교착 상태가 발생하는 경우는 4가지 조건이 모두 성립될 때입니다. 그러므로, 교착 상태 예방에서는 4가지 조건에 대한 부정하는 방식으로 교착 상태를 해결하고자 합니다.
상호 배제 부정 - 한 번에 여러개의 프로세스가 공유 자원을 접근 및 사용할 수 있게 합니다. - 하지만, 추후 동기화와 관련한 문제가 발생할 수 있습니다.
점유 대기 부정 - 프로세스가 작업을 하는데 필요한 자원을 모두 한번에 필요하고, 모든 자원을 점유할 때까지 작업을 보류하는 방법입니다.
비선점 부정 - 높은 우선순위를 가지고 있는 프로세스가 작업에 필요한 자원(다른 프로세스가 점유하고 있는 자원)을 점유할 수 있도록 합니다.
순환 대기 부정 - 기존의 순환 형태가 아닌 일정한 방향으로만 자원을 요구할 수 있도록 합니다.
| Conclusion
교착 상태는 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 끝이 없는 대기에 빠지는 상황을 의미합니다.
교착 상태가 발생하는 조건은 1. 상호 배제 2. 점유 대기 3. 비선점 4. 순환 대기 이며 이 모두를 만족해야지 교착 상태가 발생합니다.
교착 상태를 해결하는 방법은 1. 교착 상태 무시 2. 교착 상태 탐지 및 회복 3. 교착 상태 예방 4. 교착 상태 회피가 있습니다.
문자열(String, StringBuffer, StringBuilder) 포스팅을 한 이후로, 동기화와 관련하여 이어지는 부분이라고 생각합니다. 물론 Java에서의 Lock Interface나 동기화, 락과 관련한 부분에 대한 추가적인 공부를 더 해야할 것 같습니다.
개념과 예제를 접하긴 했지만, 조금 더 실제 업무에서 접하는 경우의 예시를 더 알아봐야할 것 같다는 생각이 들었습니다.
