교착 상태(DeadLock)

교착 상태란 시스템 자원을 두고 경쟁하거나 서로 통신하는 프로세스 집합의 영구 차단을 말한다.

프로세스 집합의 각 프로세스가 다른 차단된 프로세스에 의해서만 트리거될 수 있는 이벤트를 대기하면서 차단되면, 일련의 프로세스가 교착된다.

즉, 이벤트가 트리거 되지 않아 2개 이상의 프로세스를 진행할 수 없는 상황을 말한다.

Example.

시스템이 2개의 tape 드라이브를 갖고 있다고 하자.

P1과 P2는 각각 하나의 테이프 드라이브를 가지며, 각각 다른 테이프 드라이브가 필요하다.

Semaphore A와 B가 1로 초기화 되어 있다.

    P1                                      P2

semWait(A);                   semWait(B);

semWait(B);                   semWait(A);

 

모든 교착 상태는 2개 이상의 프로세스로 인한 자원 요구 충돌과 관련됨.

 

Resources

비선점 자원

- 제거된다면 프로세스가 실패함.

- 일반적으로 교착상태는 비선점 자원을 수반한다.

- 자원의 두 가지 일반적인 범주는 재사용 가능성 및 소모성

 

재사용 가능 자원

- 한 번에 하나의 프로세스만 안전하게 사용할 수 있고, 그 사용으로 고갈되지 않는 재사용 가능한 자원을 말함.

- 프로세스는 나중에 다른 프로세스에서 재사용 할 수 있도록 release하는 리소스를 확보한다.

Request -> Lock(Allocate) -> Use -> Unlock(Release)

예) 프로세서, 메모리, 디바이스, 테이프 드라이브, 프린터, 파일, 데이터베이스 및 세마포어와 같은 데이터 구조

 

소모성 자원

- 소모성 자원은 생성(생산) 및 파괴(소비)할 수 있는 자원을 말한다.

예) 인터럽트, 신호, 메세지, 입출력 버퍼의 정보

 

자원 할당 그래프

- 자원을 프로세스에 할당하는 것을 구체화하는 유용한 도구

- 시스템 자원 및 프로세스들의 상태를 묘사한다.

정점 V의 집합과 간선 E의 집합으로 구성됨.

정점 V는 두 종류

1. 시스템 안에 프로세스들을 구성하는 집합.

2. 시스템 안에 자원 타입을 구성하는 집합.

간선 E는 두 종류

1. request edge : 방향이 있는 간선

2. Assignment edge : 방향이 있는 간선

만약 그래프가 사이클을 포함하지 않으면 교착 상태가 없는것이고 그래프가 사이클을 포함한다면,

자원 종류당 오직 한 인스턴스는 교착 상태이고, 자원 종류당 여러개의 인스턴스들은 교착상태가 아닌것이다.

리소스 할당 그래프 알고리즘은 각 리소스 유형의 인스턴스가 여러 개인 리소스 할당 시스템에 적용할 수 없음.

 

Dining Philosophers Problem

디익스트라에 의해 소개된 문제로, 5명의 철학자와 5개의 포크가 있음.

철학자들은 먹기 위해 2개의 포크가 필요함. ( 어떤 두 철학자도 동시에 같은 포크를 사용할 수 없음. )

교착 상태를 막는 것이 목표이다.

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM 5
sem_t forks[NUM]; // forks
void pickup(int philosopher_num){
	sem_wait(&forks[philosopher_num % NUM]);
}
void putdown(int philosopher_num){
	sem_post(&forks[philosopher_num % NUM]);
}
void thinking(int philosopher_num){
    printf("philosopher %d is thinking\n", philosopher_num);
    return;
}
void eating(int philosopher_num){
    printf("philosopher %d is eating\n", philosopher_num);
    return;
}
void *philosopher(void *arg){
    int philosopher_num;
    philosopher_num = (unsigned long int) arg;
    while(1){
        pickup(philosopher_num);
        printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);
        pickup(philosopher_num + 1);
        printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
        eating(philosopher_num);
        putdown(philosopher_num + 1);
        printf("philosopher %d puts down the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
        putdown(philosopher_num);
        printf("philosopher %d puts down the fork %d.\n", philosopher_num, philosopher_num);
        thinking(philosopher_num);
	}
	return NULL;
}
int main(){
    pthread_t threads[NUM];
    for(int i=0; i<NUM; i++){
    	sem_init(&forks[i], 0, 1);
    }
    for(unsigned long int i=0; i<NUM; i++){
    	pthread_create(&threads[i], NULL, philosopher, (void*)i);
    }
    for(int i=0; i<NUM; i++){
    	pthread_join(threads[i], NULL);
    }
    printf("NO DEADLOCK\n");
	return 0;
}

 

첫 번째 해결 방법

세마포어를 사용하여 세마포어 변수 sem_t room을 만들고, wait()과 post()를 사용하는 것이다.

#define NUM 5
sem_t forks[NUM]; // forks
sem_t room;
void pickup(int philosopher_num){
	sem_wait(&forks[philosopher_num % NUM]);
}
void putdown(int philosopher_num){
	sem_post(&forks[philosopher_num % NUM]);
}
void thinking(int philosopher_num){
    printf("philosopher %d is thinking\n", philosopher_num);
    return;
}
void eating(int philosopher_num){
    printf("philosopher %d is eating\n", philosopher_num);
    return;
}
void *philosopher(void *arg){
    int philosopher_num;
    philosopher_num = (unsigned long int) arg;
    while(1){
    sem_wait(&room);
    pickup(philosopher_num);
    printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);
    pickup(philosopher_num + 1);
    printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
    eating(philosopher_num);
    putdown(philosopher_num + 1);
    printf("philosopher %d puts down the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
    putdown(philosopher_num);
    printf("philosopher %d puts down the fork %d.\n", philosopher_num, philosopher_num);
    sem_post(&room);
    thinking(philosopher_num);
	}
	return NULL;
}
int main(){
    pthread_t threads[NUM];
    for(int i=0; i<NUM; i++){
    	sem_init(&forks[i], 0, 1);
    }
    sem_init(&room, 0, 4);
    for(unsigned long int i=0; i<NUM; i++){
    	pthread_create(&threads[i], NULL, philosopher, (void*)i);
    }
    for(int i=0; i<NUM; i++){
   		pthread_join(threads[i], NULL);
    }
    printf("NO DEADLOCK\n");
    return 0;
}

 

교착 상태 Handling

1. 교착 상태를 예방

- 조건 중 하나를 없애는 정책을 채택하여 교착 상태를 방지.

- 3가지 필수 정책 중 하나 (상호 배제, 선점 불가, hold & wait)를 방지하거나 순환 대기 방지

단점 : 이로 인해 utilization이 낮아지고, 동시성이 떨어지거나 자원 사용이 어려워진다.

2. 교착 상태를 회피

- 필요한 세 가지 조건을 허용하지만, 현재 자원 할당 조건에 따라 요청을 승인 또는 승인하지 않음.

단점 : 교착 상태를 방지하려면 향후 프로세스 자원 요청에 대한 지식이 필요하다.

3. 교착 상태를 감지 및 복구

- 교착 상태가 발생할 수 있다고 가정하고, 주기적으로 교착 상태를 확인한다.

- 교착 상태에 빠진 프로세스를 제거하거나 리소스를 해제하여 복구한다.

4. 문제를 그냥 무시하는 것

- 예방 , 회피 및 감지/복구는 비용이 많이 든다.

- 교착 상태가 드문 경우에 오버헤드를 감수 할 가치가 있는 문제인가? 에 대해 고민하는 것.

 

교착 상태 예방(Deadlock Prevention)

- 조건 중 하나를 제거하는 정책(상호 배제, 선점 불가, hold & wait, 순환 대기)

hold & wait - 프로세스가 필요한 모든 리소스를 한 번에 요청하고, 모든 요청을 동시에 부여할 수 있을 때 까지 프로세스를 차단한다. 비효율적 일 수 있으며, 프로세스를 느리게 하고 불필요하게 리소스 엑세스를 거부할 수 있음

Circular wait - Resource Ordering. 즉 리소스 유형의 선형 순서를 정의하는 것. 각 프로세스의 자원 요청을 오름차순으로 열거함. 불편하고, 복잡하며 제한된 자원 요청

 

교착 상태 회피(Deadlock Avoidance)

교착 상태를 해결하기 위한 접근

- 교착 상태 방지 알고리즘은 요청을 만드는 방법을 제한하여 교착 상태를 방지한다.

- 이로 인해 utilization이 낮아지고 동시성이 떨어지거나 자원 사용이 어려울 수 있다.

- 교착 상태를 방지하기 위한 다른 방법은 자원 요청 방법에 대한 추가 정보를 요구하는 것이다.

- 현재 자원 할당 요청이 승인될 경우, 교착 상태로 이어질 수 있는지에 대한 여부를 동적으로 결정한다.

- 교착 상태에 절대 도달하지 않도록 안전한 상태를 만듦. ( 향후 프로세스 요청에 대한 지식이 필요함, 모든 안전하지 않은 상태가 교착 상태는 아님.)

 

Process Initiation Denial

- 리소스 요구 사항으로 인해 교착 상태가 발생할 수 있는 경우, 새 프로세스의 시작을 거부하는 교착 상태 방지 정책을 정의할 수 있다.

- 즉, 모든 현재 프로세스와 새 프로세스의 클레임을 모두 충족할 수 있는 경우에만 프로세스가 시작된다.

- 모든 프로세스가 함께 최대 클레임을 제기하기 때문에 최악의 경우를 가정할 수 있음.

 

Resource Allocation Denial

새 스레드가 시스템에 들어오면 각 리소스 유형의 최대 인스턴스 수를 선언해야 한다.

- 사용자가 리소스 집합을 요청할 때, 시스템은 이러한 리소스 할당이 시스템을 안전한 상태로 유지하는 지 여부를 결정해야 한다.

- 필요한 경우 리소스가 할당된다. 그렇지 않은 경우 스레드는 다른 스레드가 충분한 리소스를 릴리즈할때까지 기다려야 한다.

- Banker's Algorithm으로 알려져 있음.