데드락(Deadlock)

데드락이란 일련의 프로세스들이 서로가 가진 자원을 기다리며 벽돌처럼 block되어 더 이상 진행이 될 수 없는 상태를 말한다. 

그림처럼 각각의 자동차가 모두 자기 앞에 있는 자동차가 지나가기를 기다리는 상황이 되어 모든 차가 더 이상 움직일 수 없는 상태를 말한다. 

예를 들어 세마포어 변수 A, B가 있고 프로세스 P1이 P(A), P(B)을 순서대로 호출하고 P2가 P(B), P(A)를 호출한다고 가정해보자.
그러면 P1과 P2가 서로 각각 B와 A를 영원히 기다리는 상태가 되어버린다. 이런 상태가 Deadlock이다. 

즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말한다.

프로세스 자원 사용 절차

프로세스가 자원을 사용하는 절차에는 Request, Allocate, Use, Release가 있다. 

• Request :  자원을 요청하고, 만약 다른 프로세스가 자원을 사용하고 있어 받을 수 없다면 대기한다. 
• Allocate : 자원을 받는다.
• Use : 프로세스가 받은 자원을 사용한다.
• Release : 프로세스가 자원을 놓아준다. 

Deadlock은 모든 프로세스가 Request 상태가 되어있는 상황을 의미한다.

데드락 발생조건(Deadlock Characterization)

Deadlock이 발생하기 위해선 다음 4가지 조건을 만족해야 한다. 

1. Mutual exclusion (상호 배제)
- 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 

2. Hold and wait (점유 대기)
- 자원을 최소한 하나 보유하고 있고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

3. No preemption (비선점)
- 이미 할당된 자원을 빼앗을 수 없다.

4. Circular wait (순환 대기)
- 자원을 대기하는 프로세스들은 순환 형태(사이클)로 자원을 대기해야 한다.

프로세스 간의 관계를 그래프로 도식화해 보면 데드락이 발생할지 예상할 수 있다. 이 그래프를 Resource-Allocation Graph(자원 할당 그래프)라고 한다.
만약 그래프에 사이클(Cycle)이 없다면 Deadlock이 아니다. 반면, 사이클이 있다면 Deadlock이 발생할 가능성이 있다. 
정확히 말하면, 자원당 하나의 인스턴스만 있는 경우엔 Deadlock이고, 여러 인스턴스가 존재하는 경우엔 Deadlock일 수도 있고 아닐 수도 있다. 

데드락 예방(Deadlock Prevention)

데드락을 미리 예방하려면 자원을 할당할 때 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 방식이다. 

1. Mutual Exclusion 
Critical Section Problem을 해결하기 위해서는 이 조건은 반드시 만족해야 하므로 공유자원이 존재한다면 이 조건은 만족시킬 수밖에 없다.
만약 공유자원이 없다면 한 번에 여러 프로세스가 공유 자원을 사용할 수 없게하면 된다.

2. Hold and Wait
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록 해야 한다.
따라서 프로세스를 시작할 때 모든 필요한 자원을 할당받게 하거나, 자원이 필요한 경우 보유하고 있던 자원을 모두 반납하고 다시 요청하는 방식을 이용할 수 있다. 

3. No preemption
프로세스가 어떤 자원을 기다려야 하는 경우 보유하고 있던 자원이 선점된다. 그리고 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다. 

4. Circular wait
자원의 타입에 따라 프로세스마다 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다. 

데드락 회피(Deadlock Avoidance)

데드락 예방은 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있다.
반면 데드락 회피법은 예방법보다는 조금 덜 제한적인 방법으로 예방법의 단점을 일부 해결할 수 있습니다.

Deadlock Avoidance는 Deadlock이 발생할 가능성이 있는 경우엔 아예 자원을 할당하지 않는 방식이다. 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다. 

Safe state, Safe sequence

시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태(Safe state)에 있다고 말한다.

그리고 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(Safe sequence)라고 부른다.

만약 시스템이 Safe state에 있으면 Deadlock이 발생하지 않는다. 하지만 Unsafe state에 있으면 Deadlock이 발생할 수 있다. 따라서, Deadlock Avoidance는 시스템이 Unsafe state에 들어가지 않는 것을 보장하는 것이다.

두 가지의 Avoidance 알고리즘이 있는데, 각 자원 타입마다 하나의 인스턴스가 존재하는 경우 자원 할당 그래프 알고리즘을 사용한다.
반면 여러 인스턴스가 존재하는 경우 Banker's 알고리즘을 사용한다. 

두 알고리즘은 어려워서 설명은 패스하겠다.

데드락 탐지, 회복(Deadlock Detection and Recovery)

Deadlock이 발생했는지는 Deadlock을 미리 회피하는 방법과 유사하게 확인할 수 있다.
그래프를 통해서 사이클이 생겼는지를 확인하거나, 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스가 존재하지 않는다는 것을 이용하여 확인할 수 있다.

Deadlock을 회복하는 방법으로는
1. 프로세스를 종료시키거나 자원을 선점하는 방법
2. 프로세스를 종료시킬 땐 Deadlock에 빠진 모든 프로세스를 종료하거나, Deadlock이 해결될 때까지 한 번에 한 프로세스씩 종료

자원을 선점할 땐 어떤 프로세스를 종료시킬지 결정(Selecting a victim)하고, Deadlock이 발생하기 전 상태로 돌아가(Rollback) 프로세스를 재시작한다. 이때 동일한 프로세스가 계속해서 victim으로 선정되는 경우 Starvation이 발생할 수도 있다. 이는 Rollback 된 횟수를 저장함으로써 해결할 수 있다. 

데드락 무시(Deadlock Ignorance)

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식이다. 
그 이유는, Deadlock이 매우 드물게 발생하기 때문에 Deadlock에 대한 조치 자체가 더 큰 오버헤드일 수 있기 때문이다. 따라서 만약 시스템에 Deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느끼면 직접 프로세스를 죽이는 등의 방법으로 대처한다. 
이 방식은 UNIX, Windows 등 대부분의 운영체제가 채택하는 방식이다.

동기화

동기화란 프로세스, 스레드들이 수행되는 시점을 조절하여 서로가 알고 있는 정보가 일치하도록 하는 것을 의미한다.

Mutex, Monitor, Semaphore

Mutex, Monitor, Semaphore 이 세 개의 공통점은 모두 OS 동기화 기법이라는 것이다.

Mutex, Monitor vs Semaphore

우선 뮤텍스, 모니터 / 세마포어의 차이점은 개념적으로 뮤텍스, 모니터는 상호배재를 함으로서 임계구역에 하나의 스레드만 들어갈 수 있다는 것이고, 세마포어는 하나의 스레드만 들어가게도 할 수 있고(binary semaphore) 여러개의 스레드가 들어가게 할 수도 있다(counting semaphore).

임계구역 (Critical Section)

• 하나의 프로세스만 사용 할 수 있는 구역
• 공유되는 자원에서 문제가 발생하지 않도록 독점을 보장해 줌
• 임계영역에선 한 순간에 반드시 하나의 프로세스나 스레드만 진입이 가능하다.

상호 배제

• 한 프로세스가 공유 자원을 사용 할 때, 다른 프로세스가 접근 하는 것을 막는 것

Mutex vs Monitor

뮤텍스와 모니터의 가장 큰 차이는 뮤텍스는 다른 프로세스(애플리케이션)간에 동기화할 때 사용할 수 있다는 것이고 모니터는 하나의 프로세스(애플리케이션)내에 다른 스레드 간에 동기화할 때 사용된다는 것이다.
또한, 뮤텍스는 보통 운영체제 커널,프레임워크,라이브러리에 의해서 제공되는 반면에 모니터는 프레임워크나 라이브러리 그 자체에서 제공된다. 따라서 뮤텍스는 무겁고 느리며 모니터는 가볍고 빠르다.

Monitor vs Semaphore

앞에서 세마포어는 binary semaphore 아니라 counting semaphore를 제공하는 반면 모니터는 개념적으로 binary semaphore만 가능하다고 했다.둘은 이 차이점만 있는 것이 아니다. Java에서는 모니터를 모든 객체에게 기본적으로 제공하고 있는 반면 C에서는 모니터를 사용할 수 없다. 또한, 세마포어는 실제로는 카운터라는 변수값으로 프로그래머가 상호배제나 오더링의 목적으로 사용시 매번 값을 따로 지정해줘야하는 등 조금 번거롭다. 반면,모니터는 이러한 일들이 캡슐화되어있어서(encapsulation) 개발자는 카운터값을 1로 주냐 0으로 주냐 고민할 필요 없이 synchronized, wait(), notify() 등의 키워드를 이용해 좀 더 편하게 동기화할 수 있다.

정리

Mutex

• 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막음, 하나의 스레드만 접근 가능
• 한 스레드가 임계 영역에 들어 갈 때 lock을 하고, 나올 때 unlock
• 다른 프로세스 간 동기화 할 때 사용 (모니터와의 차이점)
• 운영체제, 커널, 프레임워크, 라이브러리에 의해 제공되므로 무겁고 느림

Monitor

• 하나의 프로세스 내에서 다른 스레드 간 동기화에 사용 됨 (뮤텍스와의 차이점)
• 세마포어는 임계구역 앞에 wait, signal을 설정해야 함, But 모니터는 함수 앞에 synchronized를 붙여주기만 하면 알아서 상호배제 하여 함수의 작업을 수행 함
• 프레임워크, 라이브러리 그 자체에서 제공되므로 가볍고 빠름
• JAVA에서 사용가능. C에선 사용 불가능 (세마포어와의 차이점)

Semaphore

= 임계 영역에 들어 갈 수 있는 스레드가 1개 이상 (뮤텍스와의 차이점)

• wait, signal 함수 사용 (wait() -> 임계영역 -> signal())
• wait() : 임계 영역에 들어 갈 수 있는지 확인
• signal() : 임계 영역에서 빠져나왔음을 알림