오퍼레이팅 시스템

[OS] DeadLocks

유승혁 2022. 9. 20. 15:25

0. 정의

 프로세스의 집합이 영원히 block 되어 있는 상태를 의미한다. 그렇게 되는 이유는 해당 집합 내에서 누군가가 어떠한 event를 발생 시켜야만 다른 프로세스가 움직일 수 있지만 서로 그 상태에 머물러 있기 때문이다.

 이때의 event라는 것은 자원을 할당 받는 다는 것이다. 아래 그림을 보면 직진할 수 있는 길을 할당 받기 위해 서로 기다리면서 길을 막고 있는 것처럼.

 

1. 자원 할당 그래프

 오른쪽 그림과 같이 자원은 R, 프로세서는 P로 나타낸다. 각 P1과 P2 모두 R1, R2를 둘 다 요청하고 있다. 이때 R1은 P1에게 할당 되었고 R2는 P2에게 할당 되었다. 하지만 P1은 R2가 필요하고 P2도 R1이 필요하다. 이렇게 되면 P1,P2 둘다 자원을 할당 받기를 기다리게 되고 이것이 deadlock이다. 그래프의 특징을 보면 cycle이 존재한다는 것이다.

 

 

 

 

2. 식사하는 철학자 문제

 다익스트라가 만들어낸 문제이다. 5명의 철학자가 있고 하나의 테이블에 5개의 포크와 5개의 접시가 있다. 철학자는 밥 -> 생각 -> 밥 -> 생각... 이 과정을 돈다. 이때 밥을 먹으려면 한번에 2개의 포크가 필요하다. 만약 모든 철학자가 동시에 자신의 오른쪽의 포크를 들고 왼쪽 포크가 생겨나길 기다린다면.. deadlock이다. 그 누구도 밥을 먹지 못한다.

 우리의 목표는 이 상황을 해결하고자 한다.

 

 

 

 

 

 

2.1 4명씩 앉히기

semaphore room = {4};//방의 자원
semaphore fork[5] = {1};//포크 자원
int i;

void philosopher (int i){
    while(true){
    	think();
        wait(room);
        wait(fork[i]);
        wait(fork[(i+1)%mod5]);
        eat();
        signal(fork[(i+1)%mod5);
        signal(fork[i]);
        signal(room);
    }
}
void main(){
	parbegin(philosopher(0),philosopher(1),
    	philosopher(2),philosopher(3),philosopher(4)); 
}

 위 처럼 room 이라는 semaphore의 값을 4로 설정을 하여 한번에 4명만 room mutex에 접근 가능하게끔 하였다. 하지만 이럴 경우 한번에 5명이 있을 수 있는 방에서 4명만 들어가기에 동시성이 굉장히 떨어진다. 즉 좋지 않은 방법!

 

3. DeadLock 발생 조건 & 해결 법

 - mutual exclusion: 오직 한번에 하나의 프로세스만 자원에 접근 가능

 - No preemtion: 선점 불가

 - Hold and wait: 프로세스가 최소 하나의 자원을 잡은 상태에서 추가적인 다른 자원을 얻기 위해 기다리고 있음.

 위 3가지는 deadlock에 대한 필요 조건이지 충분 조건은 아니다. 이때 만약

 - Circular wait: 프로세스 집합{P0,P1..Pn}이 존재하고 P0가 P1이 필요로 하는 자원을 P1이 Pn이 필요로 하는 자원을 P0가 Pn이 필요로 하는 자원을 잡고 있는 경우를 말한다.

 이 4가지가 모두 존재한다면 deadlock에 대한 필요충분 조건이 된다.

 그렇다면 해결법으로는 4가지 중 한 가지를 없애거나 다른 조건을 추가하면 된다. 해결 컨셉들을 알아보자

 - DeadLock Prevention: 데드락이 일어날 경우를 사전에 방지한다. 4가지 중 하나를 성립하지 못하게 한다. 하지만 device utilization이 낮아지고 동시성이 안좋아 진다. 

 - DeadLock Avoidance: 3가지 필요 조건은 신경 쓰지 않고 자원을 할당하기 전에 자원 할당 그래프를 그려 할당할지 말지를 결정한다.

 - DeadLock dectection and recovery: 데드락이 발생하게 끔 내비 두고 발생 할 때 이를 해결한다. 주기적으로 데드락이 발생했는지 검사 해야한다.

 - just ignore : 데드락이 자주 발생하는 일이 아닌데 자꾸 신경 쓰기에는 cost도 크니깐 그냥 내비 두는게 어떨까? 사용자가 이상하다 싶으면 알아서 중단 시키지 않을까? 

 

4.1 DeadLock Prevention

 위에서 소개되었던 4가지 조건 중 하나를 제거하는 것이다. 소개할 첫 번째 방법은 Hold and Wait을 없애는 것이다.

void *philosopher(void* arg){
	int philosopher_num;
	philosopher_num = (unsigned long int) arg;
	for(unsigned int iter=0;iter<ITER;iter++){
		sem_wait(&once);
		pickup(philosopher_num);
		pickup(philosopher_num+1);
		sem_post(&once);
		eating(philosopher_num);
		putdown(philosopher_num+1);
		putdown(philosopher_num);
	   thinking(philosopher_num);
   }
   return NULL;
}

 컨셉은 한번에 포크를 두 개씩 드는 것이다. 하지만 이럴 경우 1번째 철학자와 3번째 철학자의 포크는 전혀 겹치지 않는데 굳이 once로 경쟁할 필요가 없다. 즉, 불필요한 제한이 생겨나는 것이고 이에 따라 효율성 측면에서 좋지 못하다.

 

 두 번째 해결 방식은 Circular wait을 없애는 것이다.

void *philosopher(void* arg){
    int philosopher_num;
    philosopher_num = (unsigned long int) arg;
    for(unsigned int iter=0;iter<ITER;iter++){
    	if(philosopher_num < 4){
    		pickup(philosopher_num);
		    pickup(philosopher_num+1);
	    }
        else{
            pickup(philosopher_num+1);
            pickup(philosopher_num);
        }
        eating(philosopher_num);
        putdown(philosopher_num+1);
        putdown(philosopher_num);
        thinking(philosopher_num);
    }
    return NULL;
}

 위의 방식은 4명은 왼쪽 포크를 잡고 오른쪽 포크를 잡지만 마지막 한명은 오른쪽을 잡고 왼쪽을 잡게끔 하는 것이다. 이렇게 하면 마지막 사람은 오른쪽(0번 포크)를 먼저 집어야 하지만 0번이 이미 잡고 있기에 sleep에 들어간다.

 이처럼 circular 모양이 나오지 않게 끔한다. 이 경우 굉장히 효율은 좋지만, 단점으로는 확장성에 약하다. 이렇게 단순하고 명확한 예시에서는 circular를 피할 수 있지만 굉장히 복잡한 현대의 os에는 적용할 곳이 많지 않아 보인다. 또한 만약 마지막 철학자가 오른쪽이 아닌 반드시 왼쪽을 먼저 잡아야 한다면,, 위 해결책은 쓸모가 없다.

 

4.2 DeadLock Avoidance

  deadlock prevention 방식들은 request에 대해 제한을 두어 deadlock을 피했다. 이런 방식은 자원 사용을 어렵게 하거나 동시성을 떨어뜨린다. 이번에는 그러지 말고 자원 요청이 들어오면 자원을 주어도 되는지? 판단하자는 것이다. 대게 자원할당 그래프를 그려서 해결한다. 해당 그래프를 그리기 위해서는 각 프로세스가 요청하는 자원의 종류에 대해 알아야 하고 자원이 어느 프로세스에 할당 되어있는지 알고 있어야만 한다. 자원 할당 그래프는 모든 자원이 하나씩 존재할때 적합하고 만약 자원이 여러개일 경우 다른 방식을 사용한다.

 이 방식은 두 가지로 나뉘는데, 겹치겠다 싶으면 프로세스 시작을 거부해 버리는 Process Initiation Denial과 프로세스는 일단 진행 시키고 자원을 요청하는 시점에 검사하는 Resource Allocation Denial (Banker's algorithm) 방식이 있다.

 Process Initiation Denial: n개의 프로세스가 존재하고 m개의 자원이 있을 때 새로운 프로세스를 시작하려면 해당 프로세스가 요구하는 모든 자원에 해당하는 만큼 가져오게 되면 남아있는 자원들 보다 더 가져오는 것이 아닐 지 검사한다.

 정리해보자면,

 R = {자원의 수}, V = {할당 되지 않은 자원의 수}, C = {i번째 process가 j 번째 재원 몇개를 요구하는지 정리해 놓은 행렬}, A = {i 번째 process에 할당된 j 번째 자원의 수} 라고 한다면  모든 R의 값이 n+1번째 C + (지금까지 요청 받아진 자원의 수) 보다 크거나 같으면 된다.

 이러한 방식은 만약 프로세스가 필요로 하는 자원이 아주 잠깐인데 이 잠깐 때문에 실행을 못해버리면 굉장히 비효율 적이게 된다. 그래서 

Resource Allocation Denial, Banker's algorithm을 대게 사용한다.

 

4.3 Resource Allocation Denial (Banker's algorithm)

 정말 간단한 개념이다. 내가 자원을 관리하는 은행이라고 생각하고, 갚을 능력이 되는 프로세스에게만 자원을 할당한다. 아래와 같은 예시가 있다고 하자.

 3개의 프로세스와 1가지 종류의 자원이 있다. 이 자원은 총 12개가 있었다.

Process Claim(C) Allocation(A) C-A
P1 10 5 5
P2 4 2 2
P3 9 2 7

 이때 현재 3개가 남게 된다. 우리는 이 자원을 만약 P1이나 P3에게 먼저 주면 P1은 추가로 2개가 더 필요하고 P3은 4개가 더 필요하다. 즉 deadlock이 발생한다. 그렇다면 P2에게 먼저 할당하고 반환 받으면 5개가 되고 P1에게 할당하고 리턴 받으면 10개가 되고 P3에게 주어 P3도 끝내면 된다. 이처럼 내가 빌려주면 반환할 수 있는 (P2처럼) 프로세스에게 할당 하는 것이다.

 즉 남은 현재 자원의 수 >= Ci - Vi 인 i 번째 프로세스에게 할당하면 된다. 자원이 여러 종류일 때도 충분히 확장 가능하다는 것이 느껴진다.

 

 

5. 식사하는 철학자를 bankers로 해결하기

 식사하는 철학자 문제의 경우 5종류의 프로세스와 5종류의 자원이 있고 각 자원은 한 개씩 존재한다. 각 프로세스 별 필요로 하는 자원 또한 알고 있다. 그러하니 deadlock prevention이 아닌 deadlock avoidance인 bankers로 해결해보자.

bool getNext(int i){
     int left, right;
     bool flag = false;
     sem_wait(&forks[i]);
     sem_wait(&forks[(i+1)%NUM]);

     if(C[i][i]-A[i] > 0 && C[i][(i+1)%NUM]-A[(i+1)%NUM] > 0){
        A[i] += 1;
        A[(i+1)%NUM] += 1;
        flag = true;
     }
     return flag;
}

void done(int i){
    A[i] = 0;
    A[(i+1)%NUM] = 0;

    sem_post(&forks[i]);
    sem_post(&forks[(i+1)%NUM]);
}

void *philosopher(void* arg){
   int philosopher_num;
   philosopher_num = (unsigned long int) arg;
   for(unsigned int iter=0;iter<ITER;iter++){
       if(!getNext(philosopher_num)){done(philosopher_num);continue;}
       
       pickup(philosopher_num);
       pickup(philosopher_num+1);
       
       eating(philosopher_num);
       done(philosopher_num);
       
       putdown(philosopher_num+1);
       putdown(philosopher_num);
       
       thinking(philosopher_num);
   }
   return NULL;
}

 C 배열은 몇 번째 철학자가 몇 번째 포크를 필요로 하는 지 나타냈고 A 배열은 각 포크의 남은 자원의 수를 의미한다. A배열은 포크와 마찬가지로 공유 자원이 되므로 mutex lock이 필요하다. 아무튼 이제 코드를 보자.

 위와 같이 getNext()를 통해 현재 철학자가 원하는 포크를 할당 할 수 있는 지 bankers algorithm을 적용한 if문을 통해 검사한다. 가능하다면 true를 리턴받아 eating을 한 후 done()을 통해 현재 포크자원을 리턴한다. 만약 getNext()를 했을 때 false를 리턴한다면 바로 자원을 semaphore 자원을 바로 내려 놓아야만 한다.

 

6. 수행시간 비교

 ITER의 값을 5000으로 했을 때 수행시간은 다음과 같았다. clock() 함수를 통해 비교해보았다.

 NO CIRCULAR WAIT: 40000~50000 / NO HOLD&WAIT: 130000~150000 / BANKERS: 70000~90000

 당연하게도 no circular wait이 가장 효율 적이었다. 사실상 철학자 간에 포크 집는 것에 대한 제한이 없기 때문에 가능했던 일이 아닌가 싶다. 조금 놀랐던 점은 bankers가 no hold&wait 보다 효율적이라는 사실! 아무래도 no hold & wait은 동시에 1,3 / 2,4 이런 식으로 동시에 먹을 수 있는 철학자의 수가 제한되다 보니 효율이 많이 떨어지는 듯 싶다.. 과잉 보호랄까?? ㅎㅎ