데드락(Deadlocks)

프로세스에서 할 일이 많다면...
일을 쪼개서,
의존성(dependency)를 정의하고,
스레드에 작업을 할당,
스레드 간 실행을 동기화해야 할 것

• 이 과정에서 데드락이라는 치명적인 문제 발생 가능

데드락이란?

데드락: 프로세스들이 서로 시스템 자원을 경쟁하거나, 서로 소통하는 과정에서 영구적으로 block되는 상태

• 서로 다른 프로세스의 이벤트를 기다리고 있음
• 영구적임
• 효과적인 해결책이 없음

예시) 식사하는 철학자들 문제(The Dining Philosophers)

가정)
1. 철학자는 생각을 하고 식사를 함
2. 식사를 하기 위해서는 포크가 양 손에 있어야 함

• 주의: 여기서 말하는 fork는 명령어 fork와 다름.
  식사를 위해 필요한 자원인 포크를 의미
  

semaphore_t
fork[NUM_PHILOSOPHERS];

void init(){
	for(i=0; i<NUM_PHILOSOPHERS; i++)
    		fork[i].value=1;
}

Deadlock 발생

philosopher(int i){
	while(TRUE){
    	// Think
        // Eat
        P(fork[i]); //  if 각 프로세스마다 fork 
        // 포크 두 개 드는 것 불가능 (데드락)
        	P(fork[(i+1) % 5]);
            eat();
           	V(fork[(i+1) % 5]);
        V(fork[i]);
    }
}

semaphore fork[5]=(1,1,1,1,1);
fork(philosopher, 1, 0);
fork(philosopher, 1, 1);
fork(philosopher, 1, 2);
fork(philosopher, 1, 3);
fork(philosopher, 1, 4);

가능한 해결책

philosopher(int i){
	while(TRUE){
    	// Think
        // Eat
        j=i%2; // j는 0(i가 짝수),1(i가 홀수) 가능 
        // j를 도입해 모두 1개씩 포크 드는 상황을 방지
        P(fork[(i+j) % 5]);
        	P(fork[(i+1-j) % 5]);
            eat();
           	V(fork[(i+1-j) % 5]);
        V(fork[(i+j) % 5]);
    }
}

semaphore fork[5]=(1,1,1,1,1);
fork(philosopher, 1, 0);
fork(philosopher, 1, 1);
fork(philosopher, 1, 2);
fork(philosopher, 1, 3);
fork(philosopher, 1, 4);

Nesting Semaphore: 구현 방법 2가지

P(flag1);
	P(flag2);
    	< access R1 >;
    	< access R2 >;
   	V(flag2);
V(flag1);

P(flag2);
	P(flag1);
   	 < access R1 >;
    < access R2 >;
   	V(flag1);
		V(flag2);

• flag1, flag2는 세마포어를 사용하기 위한 플래그를 의미
• 1번, 2번 관계없이 P 연산의 역순으로 V를 수행해야 함
  - 두 개의 플래그(flag1, flag2)에 대해서 flag1의 P를 먼저 수행했다면 V는 flag2보다 나중에 수행해야

데드락 발생 조건

데드락은 아래 4가지 상황이 동시에 발생해야 일어날 수 있음

• 네 가지 조건 중 하나라도 만족 안 하면 데드락 X, 모두 만족해도 데드락 안 발생할 수도 있음(필요조건)

1. Mutual Exclusion: mutex 등을 사용해 하나의 스레드만이 lock을 얻을 수 있게 만듦
2. Hold and Wait: mutex1을 가지고 있는데, mutex2를 얻지 못해 wait을 하더라도, 가지고 있는 mutex1을 계속 hold하고 있어야 함
3. Circular Waiting: 스레드들이 서로의 자원을 기다리는 circular wait이 필요

4. No Preemption: 스레드 간에 선점(preemption)이 일어나지 않아, 다른 lock을 얻지 못하더라도 가지고 있는 lock을 놓아주지 않음. 각 프로세스가 unlock을 통해 lock을 해제해야 함.

어떻게 대처?

1. 데드락을 예방(Prevention)
- deadlock의 4가지 조건 중 하나를 제거하는 정책 도입
- ex) 한 번에 모든 자원을 요청, 선점(preemption), 자원에 순서 부여(increasing/decreasing하는 방식으로만 사용)
2. 데드락을 피함(Avoidance)
- ex) 다른 mutex lock을 얻을 수 없다면, 가진 mutex hold하지 않고 내어줌
- 앞의 철학자 예시에서, 본인이 mutex lock(포크)을 모두 얻지 하면 가진 lock을 내어줌(가진 포크를 내려놓음)
3. 데드락을 파악(Detection)
- 데드락이 있는지 주기적으로 파악, 해결 시도

References.

1. 강순주 교수님 PPT 09
2. Operating Systems Concepts 10ed. Abraham-Silberschatz
3. https://jhnyang.tistory.com/3