[OS] Deadlock

데드락 (Deadlock)

데드락은 교착 상태라고도 부르며 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 무한히 기다리는 상태이다. 

 

데드락의 발생조건

1. 상호 배제

- 한 순간에 한 프로세스만이 해당 자원을 사용할 수 있다.

2. 점유 대기

- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기해야 한다.

 

3. 비선점

- 이미 할당된 자원을 강제로 빼앗을 수 없다.

 

4. 환형 대기

- 자원 할당 그래프에서 환형(cycle)이 만들어진 경우 즉, 서로 다른 프로세스의 행동을 기다리는 상황이다.

 

1 ~ 3의 조건은 데드락의 필요 조건이다. 즉 어느 하나라도 충족하지 않으면 데드락은 발생하지 않으며 모든 조건이 충족되었다고 하더라도 무조건 데드락이 발생하는 것은 아니다. 여기에 4번 조건까지 만족되면 데드락이 발생한다. 즉 1 ~ 4번 조건은 데드락의 필요충분조건이다.

---

데드락 발생 시나리오

P와 Q라는 두 개의 프로세스가 A와 B라는 자원을 경쟁적으로 사용하며 수행하는 과정이다.

각 프로세스는 일정 기간 동안 두 개의 자원을 동시에 배타적으로 사용해야 한다.

1. Q가 B를 획득하고, A를 획득한다. Q는 모든 작업을 수행하고 B와 A를 순서대로 반납한다. 이후 P로 전환되면 두 자원을 사용할 수 있게 된다.

 

2. Q가 B를 획득하고, A를 획득한다. 이 때 P로 전환되지만 A의 획득에 실패하므로 블락된다. Q가 수행을 완료하고 자원을 반납하면 P가 깨어나서 자원을 사용할 수 있게 된다.

 

3. Q가 B를 획득하고 P가 A를 획득한다. 이후 Q는 A의 획득에 실패하여 블락되고, P는 B의 획득에 실패하여 블락된다.

=> 데드락 발생

 

4. P가 A를 획득하고 Q가 B를 획득한다. 이후 P는 B의 획득에 실패하여 블락되고, Q는 A의 획득에 실패하여 블락된다.

=> 데드락 발생

 

5. P가 A를 획득하고, B를 획득한다. 이 때 Q로 전환되지만 B의 획득에 실패하므로 블락된다. P가 수행을 완료하고 자원을 반납하면 Q가 깨어나서 자원을 사용할 수 있게 된다.

 

6. P가 A를 획득하고, B를 획득한다. P는 모든 작업을 수행하고 A와 B를 순서대로 반납한다. 이후 Q로 전환되면 두 자원을 사용할 수 있게 된다.

---

데드락 해결 방법

1. 데드락이 발생하지 않도록 예방(Prevention)

2. 데드락 발생 가능성을 인정하면서도 적절하게 회피(Avoidance)

3. 데드락 발생을 허용하지만 발견(Detection)하여 회복

 

데드락 예방 (Prevention)

데드락 발생 조건 4가지를 방지하여 데드락 발생 가능성을 차단하는 방법

 

데드락 회피 (Avoidance)

데드락 발생 조건 중 1 ~ 3은 허용하지만 4번 조건인 환형 대기가 발생하지 않도록 방지하는 것으로 예방에 비해 더 많은 병행성을 제공한다. 데드락 회피로는 다음과 같은 방법들이 있다.

 

1. 프로세스 시작 거부

프로세스가 시작하려 할 때 요구하는 자원 할당이 데드락 발생의 가능성이 있으면, 프로세스를 시작시키지 않는 방법으로 자원에 대한 벡터와 행렬을 이용하여 데드락 발생 가능성을 판단한다. 

2. 자원 할당 거부 (은행원 알고리즘)

자원 할당 거부를 통한 데드락 회피 기법에는 은행원 알고리즘을 사용한다.

 

※ 은행원 알고리즘

• 시스템에 고정된 수의 프로세스와 자원이 존재한다고 가정
• 시스템의 상태를 safe state와 unsafe state로 구분
• safe state란 데드락이 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 경로가 존재하는 상태
• unsafe state란 해당 경로가 존재하지 않는 상태
• safe state를 유지할 수 있는 요청에만 자원 할당을 허락

C - A는 추가적으로 할당해야 할 자원들의 행렬이다. V를 C - A의 한 프로세스에게 할당할 때 수행이 끝나는 프로세스를 찾아 할당하면 해당 프로세스의 수행을 종료시킬 수 있다. 이후 A에서 해당 프로세스의 값들을 반환하여  V에 더하고 해당 프로세스의 값들은 C와 C - A에서 모두 0이 된다.

 

 

다음은 unsafe state에 대한 예시로 실행할 수 있는 프로세스가 없는 경우이다.

 

데드락 발견 (Detection)

데드락 발견은 프로세스의 시작이나 자원 접근에 대해 제약을 가하지 않고, 요청이 들어오면 항상 할당을 한다. 대신 주기적으로 시스템에 환형 대기조건이 발생했는지 검사하고 발생한 경우 이를 해결하게 된다.

 

데드락 발견 알고리즘

현재 V를 할당하여 수행이 완료될 수 있는 프로세스를 Q에서 찾아서 있다면 해당 프로세스가 종료된 이후 반납할 자원을  V에 추가한다. 이 과정을 반복하여 알고리즘이 종료되었을 때 모든 프로세스가 완료되면 데드락이 발생하지 않은 것이고 그렇지 않다면 데드락 상태가 존재하는 것이다. 이 알고리즘의 단점으로는 현재 데드락의 존재 여부만 파악할 뿐, 이후에 데드락이 생길지 여부는 파악하지 못한다는 점이다.

 

※ 데드락 회복 방법

데드락을 발견했다면 다음과 같은 방법으로 데드락 상태에서 회복할 수 있다.

• 데드락에 포함된 모든 프로세스를 중지 -> 대부분의 OS에서 채택하는 방식
• 데드락에 포함된 각 프로세스의 수행을 모두 롤백 후 재수행
• 데드락이 없어질 때까지 포함된 프로세스를 하나씩 종료
• 데드락이 없어질 때까지 포함된 자원을 하나씩 선점시킴

---

식사하는 철학자 문제 (Dinning Philosopher Problem)

식사하는 철학자 문제는 데드락의 대표적인 예시로 다음과 같은 조건을 따른다.

• 여러 철학자가 원형 테이블에 앉아 식사를 하는 상황
• 철학자는 포크 2개를 모두 가진 상태에서만 식사를 할 수 있음
• 철학자는 왼쪽에 있는 포크를 먼저 집고, 그 이후에 오른쪽에 있는 포크를 집음
• 식사를 마치면 두 포크를 테이블에 내려놓음
• 위 상황에서 철학자의 인원과 동일하게 포크가 배치되어있다면 데드락이 발생

#define N 5       //number of philosopher

semaphore fork[N];

void philosopher(int i)
{
	while(1){
		think();
		semWait(fork[i]);
		semWait(fork[(i+1) mod N];
		eat();
		semSignal(fork[(i+1) mod N]);
		semSignal(fork[i]);
	}
	return;
}

int main(void)a
{
	for(int i = 0; i < N; i++)  //semaphore 모두 로 초기화
		semInit(fork[i], 1);

	for(int i = 0; i < N; i++)
		philosopher(i);

	return 0;
}

 

세마포어를 사용하여 문제를 해결하는 방법

해당 방법은 room이라는 세마포어를 추가로 두어 한 번에 최대 4명까지 앉을 수 있도록 제한하는 방법이다.

#define N 5       //number of philosopher

semaphore fork[N];
semaphore room;

void philosopher(int i)
{
	while(1){
		think();
		semWait(room);
		semWait(fork[i]);
		semWait(fork[(i+1) mod N];
		eat();
		semSignal(fork[(i+1) mod N]);
		semSignal(fork[i]);
		semSignal(room);
	}
	return;
}

int main(void)
{
	for(int i = 0; i < N; i++)  //semaphore 모두 로 초기화
		semInit(fork[i], 1);

	semInit(room, N-1);

	for(int i = 0; i < N; i++)
		philosopher(i);

	return 0;
}

---