데드락

데드락이란?

한 스레드가 자원을 요청했을때 그 자원이 이미 다른 스레드에서 점유 중이라면 요청 스레드는 대기상태에 들어간다. 이런식으로 모든 스레드가 대기상태에 들어가게 되어 어떠한 자원도 반납이나 점유가 이루어지지 못하는 상태를 데드락이라 한다.

가장 중요한 핵심은 자원의 획득과 반납에 있다. 데드락을 유발하는 자원은 뮤텍스나 세마포, 파일시스템이 있다. 더 나아가 네트워크 통신 및 IPC간 통신 등 여러 유형의 이벤트에서도 발생할 수 있다.

다중 스레드 환경에서 데드락 발생 예

void *do_work_one(void *param)
{
	pthread_mutex_lock(&first_mutex);
	pthread_mutex_lock(&second_mutex); 
	// Do some work
	pthread_mutex_unlock(&second_mutex); 
	pthread_mutex_unlock(&first_mutex);
	pthread_exit(0);
}

void *do_work_two(void *param)
{
	pthread_mutex_lock(&second_mutex); 
	pthread_mutex_lock(&first_mutex);
	// Do some work
	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutex); 
	pthread_exit(0);
}

두개의 스레드가 있다고 가정하고 스레드1번이 work_one, 스레드 2번이 work_two를 수행한다고 하자.
1. 운이 안좋게도 스레드 1번이 first_mutex를 획득하고 이후에 스레드2번이 second_mutex를 획득 했다.
2. 다시 스레드 1번이 second_mutex를 요청하지만 스레드 2번이 점유하고 있기에 대기 상태가 된다.
3. 이후 스레드 2번이 실행되며 스레드 2번 또한 first_mutex를 요청하고 대기상태가 될 것이다.

두 스레드 모두 자원을 반납하지 못하였고 점유하지도 못하는 무한 대기 상태인 데드락이 발생한다.

라이브락

우리는 위와 같은 문제를 해결하기 위해 자원 요청시 해당 자원이 이미 점유 중이라면 대기 상태로 블락되지 않고 락을 반납후 다시 락을 얻기로 구현하였다. 이 구현은 posix에서는 pthread_mutex_trylock로 구현해놓았다.

우리는 위 코드를 아래와 같이 변경 후 실행한다고 가정하자.

void *do_work_one(void *param)
{
	int done = 0;
	while(!done){    
		pthread_mutex_lock(&first_mutex);
		if (pthread_mutex_lock(&second_mutex)){
			// Do some work
			pthread_mutex_unlock(&second_mutex); 
			pthread_mutex_unlock(&first_mutex);    
			done = 1;
		}else{
			pthread_mutex_unlock(&first_mutex);    
		}
	}
	pthread_exit(0);
}

void *do_work_two(void *param)
{
	int done = 0;
	while(!done){
		pthread_mutex_lock(&second_mutex);
		if (pthread_mutex_lock(&first_mutex)){
			// Do some work
			pthread_mutex_unlock(&first_mutex);    
			pthread_mutex_unlock(&second_mutex); 

			done = 1;
		}else{
			pthread_mutex_unlock(&second_mutex);    
		}
	}
	pthread_exit(0);
}

1. 운이 안좋게도 스레드 1번이 first_mutex를 획득하고 이후에 스레드2번이 second_mutex를 획득 했다.
2. 다시 스레드 1번이 second_mutex를 요청하지만 스레드 2번이 점유하고 있기에 현재 내가 가진first_mutex락을 반납할것이다.
3. 스레드 2번은 first_mutex 락이 반납 되기 이전에 실행되며 스레드 2번은 first_mutex를 요청하게된다. 하지만 스레드 1번이 아직 first_mutex 락을 가지고 있기에 2번은 내가 가진 second_mutex를 반납하게 될것이다.

위와 같이 두 스레드가 순차적으로 반납하고 가져가는것이 아닌 동시에 요청하고 동시에 반납하는 과정을 반복하게 된다.

이 같은 문제는 재시도 시간을 무작위로 지정하였을때 발생하게 되며 서로 충돌이 발생한 이후 임의 시간 동안 대기하도록하여 해결한다.