[Operating System Concepts] Chapter8 Deadlocks

곤뇽

1. Deadlock?
2. Deadlock Conditions
3. Deadlock Prevention
4. Deadlok Avoidance
5. Deadlok Detection / Recovery

 

---

Deadlock?

자기상태를 바꾸지 못하고, (프로세스/스레드 간) 대기만 하게되는 경우를 의미한다.

https://namu.wiki/w/%EB%8D%B0%EB%93%9C%EB%9D%BD

• 시스템에 유한개의 자원이 있다고 가정했을 때, 경쟁하는 스레드 끼리 자원이 잘 분배될 수 있도록 나누어야 한다.
• 자원의 종류(CPU cycle, files, I/O device)에 따른 동등한 자원들 끼리의 경쟁이 일어난다.
  • 리소스타입이 중요하지, 리소스 개수가 몇개인지는 중요하지 않다.
  • Request - Use - Release 의 과정으로 자원이 사용되는데 'Use' 상태일 때 임계영역에 들어간것으로 이해할 수 있다.

Deadlock Conditions

데드락이 발생하는 상황과 조건들에 대해 알아보자

/* thread one runs in this function */
void *do_work_one(void *param)
{
	pthread_mutex_lock(&first_mutex);
	pthread_mutex_lock(&second_mutex);
    
    /* do something */
    
	pthread_mutex_unlock(&second_mutex);
	pthread_mutex_unlock(&first_mutex);
    
    pthread_exit(0);
}

/* thread two runs in this function */
void *do_work_two(void *param)
{
	pthread_mutex_lock(&second_mutex);
	pthread_mutex_lock(&first_mutex);

    /* do something */

	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutex);

    pthread_exit(0);
}

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

• first_mutex → wait, second_mutex→wait : 굉장히 데드락 발생하기 쉬운 경우라고 할 수 있다.

#데드락 발생의 4가지 필요 조건

1. Mutual Exclusion (상호배제) → 상호배제가 필요없으면 데드락 할 이유가 없다. 
2. Hold and Wait (점유대기) → 하나의 리소스를 점유하고, 대기해야 데드락이 생긴다.
3. No preemption (선점불가) → 자원들이 선점이 불가할 때만 데드락이 발생한다.
4. Circular Wait (원형대기) → 의존성 그래프를(dependency graph) 그려보면 circular 함을 알 수 있다.

 

#자원할당 그래프 RAG(Resource-Allocation Graph)

위의 그래프는 데드락이 발생할까? R2 의 인스턴스가 하나하나 서로 물고 물리고 있기 때문에, 데드락이 발생한다.

• 방향이 있는 그래프로서 데드락을 정확하고 쉽게 이해하기 위한 그래프이다.
• first_mutex → thread_one (assign) → second_mutex(request) → thread_two → first_mutex(assign)… : 데드락 발생되는 전형적인 그래프

#Three ways of dealing with the Deadlock Problem

1. Ignore(무시하기)
2. Prevent (방지하기) → 비용이 비싸다.
   Avoid (피하자) → 여전히 비용이 비싸다. (Banker’s Algorithm)
3. Detect (탐지하자) (w/ 빠른 리커버리)

 

Deadlock Prevention

데드락을 방지하기 위해서는 발생조건 중 적어도 하나이상 막아주면 된다.

1. Mutual Exclusion (상호배제) → 상호배제가 필요없으면 데드락 할 이유가 없다. 
2. Hold and Wait (점유대기) → 하나의 리소스를 점유하고, 대기해야 데드락이 생긴다.
3. No preemption (선점불가) → 자원들이 선점이 불가할 때만 데드락이 발생한다.
4. Circular Wait (원형대기) → 의존성 그래프를(dependency graph) 그려보면 circular 함을 알 수 있다.

 

#How to prevent deadlock?

1. 적어도 하나의 리소스는 ‘non-sharable’ 이어야 하지 않을까? → 본질적으로 non-sharable하다. → 상호배제조건 자체가 안되는 문제는 deadlock 자체가 발생하지 않기 때문에 고려하지 않는다.
2. 자원을 점유할 때 모든 자원을 모두 내려놓고 자원을 가져가는것? → 실용적이지 않다.
3. 어떤 리소스를 점유하고 있고, 리소스를 요청했을 때 뺏어 버린다고 하는 경우에 문제가 발생할 수 있다. → 유용하지 않음
4. 순환점유를 막는방법이 위의 발생조건을 막는것 보다 그나마 실용적이다. 
   → 자원 점유에 대한 순번을 부여한다. 하나가 안되면 내려놓기 순서대로 진행한다면, deadlock은 발생하지 않겠지만 starvation의 가능성은 커진다. → 라킹이 동적으로 발생한다면 lock ordering 방법은 데드락 방지를 보장할 수 없다.

Deadlock Avoidance

미래에 생길 데드락을 방지하기 위해, 시스템에게 스레드의 요청을 사전에 맞기는 방식

• 해당 방법을 사용하기 위해서는 어떠한 방식으로 리소스가 요청되는지를 알아야 한다.
• 최대 할당되는 리소스의 갯수를 사전에 알고 있으면 좋음
• 안전한 상태에 있다는 것은 어떤 스레드에 맥시멈까지 리소스를 할당할 수 있다는 것을 의미한다.
• 그러한 순서를 찾아낸다면 데드락을 방지할 수 있다.

→ Safe Sequence 찾는게 중요한 개념이다.

unsafe한 상태에서 deadlock 발생할 수 있는 가능성이 존재한다. 그러나 safe 하기만 하면 데드락 발생 안한다.

 

#safe state

• 안전 상태 라는 것은 어떤 스레드의 최대 사용량 까지 리소스를 할당할 수 있는 것을 의미한다.
• 리소스의 최대 갯수를 파악하고 있으면 사용하기 편한 방법이다.
• 스레드의 'Safe Sequence' 순서를 알아낸다면 데드락을 방지할 수 있다.

• Safe State : Deadlock state에 진입하지 못하도록 safe state로 둘 수 있다.
• 시스템은 초기화 된 상태에서 안전 상태에 있다고 판단할 수 있다. → 이후로 데드락 발생여부를 체크한다.
• 새로운 자원을 할당 시켜줄 수 있는지 여부를 결정하고 시스템에서 가능하다고 판단되면 request (ok)

Deadlock Detection / Recovery

#overview

1. Prevention : 효과적이지 않음
2. Avoidance : banker 알고리즘은 요청이 들어갈 때 마다 돌아간다.
   → 시스템에게 큰 부담이 간다. 매우 중요한 프로그램에만 적용하자
3. Detection
   
   • 데드락이 자주 발생할수록 자주 체킹해준다.
   • 스레드 갯수가 많아질수록 데드락 detection 주기짧게 설정하는것이 유효하다.

 

#Recovery Method1 - Process and Thread Termination

데드락을 방지하기 위해서 프로세스를 죽여가면서 데드락이 발생하지 않도록 만들어준다.

• abort all detected process : 모두 죽이기
• abort one process at a time until deadlock cycle is eliminated : 한 프로세스만 죽이기 (해소될 때 까지 연속적으로 죽이기)

#Recover Method2 - Resource preemption

리소스 점유를 방지해주기 위해서 다음과 같은 절차를 가져간다.

• select victim : 희생양을 하나 선정(가장 최근의 스레드)해서, 리소스 선정해서 뺏고 request에 할당한다.
• rollback : 프로세스를 safe state로 두고 재시작한다.
• starvation : 한 프로세스가, 계속 재수없게 걸릴 수도 있는 상황이 발생할 수 있기 때문에 starvation 발생함