[운영체제/리눅스] 교착상태(deadlock)의 원인과 쓰레드를 통한 교착상태 발생 예제와 회피방법(pthread_mutex_timed_lock)

 

 

동기화, 임계 영역 등 더 많은 정보와 예제를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

리눅스 프로그래밍 note 배포

 

교착상태(Deadlock)

deadlock... 이름도 뭣같이 무섭네요. 교착상태라고 하는 것은 다중 프로그래밍 시스템에서 프로세스 혹은 스레드가 결코 일어나지 않을 일을 무한정으로 기다리는 상태를 말합니다. 시스템에서 교착상태는 프로세스가 요구하는 자원이 엉켜서 더 이상 작업을 더 실행할 수 없는 상태를 의미합니다.

 

시스템이라고 생각하면 조금 어려울 수 있는데 인간 세계에서도 똑같아요. 예를 들어볼까요?

 

평화로운 중고 사이트에서 A가 사고 싶은 노트북이 생겨서 B에게 연락을 합니다. 가뜩이나 요즘 중고사기가 판을 치는 시기에 B에게 먼저 노트북을 택배로 보내면 150만원을 입금해주겠다고 합니다. B 역시 A를 의심하여 먼저 입금하면 노트북을 보내겠다고 합니다. A는 B의 노트북을, B는 A의 돈을 요구하는 상황이고 서로 주지않습니다. 이렇게 서로 자원(돈, 노트북)을 점유한 상태에서 막혀 버려 서로 해야할 일(거래)을 하지 못하는 것입니다. 아무 것도 아닌 일 때문에 해야할 일을 못하는 것이지요. 어이가없네

 

교착상태의 발생 조건

아래 설명에서는 프로세스만을 이야기하는데, 스레드도 같습니다. 편의상 프로세스만 예를 들어 이야기하도록 하겠습니다.

 

1. 상호배제 (Mutual Exclusion)

한 번에  한 프로세스만 자원을 사용할 수 있어야합니다. 사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 다 사용되고 난 후 해제될때까지 기다려야합니다. 

 

2. 점유와 대기 (Hold And Wait)

프로세스는 자원을 점유한 동시에 대기해야합니다. 위의 예에서 볼 수 있듯이 A는 돈을 소유하고 있고 B가 노트북을 주기까지 대기하고 있습니다. 

 

3. 비선점 (Non Preemptive)

자원을 선점할 수 없는 조건으로 누군가가 자원을 가지고 있을때 뺏을 수 없습니다. 위의 예에서도 지극히 정상적인 상식에서 A와 B는 물건을 불법적으로 훔칠 수 없죠. 

 

4. 순환(환형) 대기 (Circle wait)

프로세스가 여러개 있을때 자원의 점유와 요청의 관계가 순환되는 조건을 말합니다. 프로세스 3개를 각각 p1, p2, p3라고 할때 p1이 p2의 자원을 요청하고, p2가 p3의 자원을 요청하고, p3가 p1의 자원을 요청하고 그 자원은 요청한 자원을 얻을 수 있을때까지 반환할 수 없습니다. 이 조건은 위의 세 조건이 만족이 되면 자연스레 만족됩니다.

 

아래의 그림은 순환 대기를 나타낸 것인데 R1, R2, R3는 각 P1, P2, P3가 점유한 자원을 의미하고 각 자원은 소유된 프로세스쪽으로 화살표가 나가고 있습니다. 프로세스들의 화살표는 요구하는 자원쪽으로 향하고 있지요. 여기서 이 화살표들의 방향대로 나가면 사이클을 그리며 무한정 순환하게 됩니다.

 

 

 

 

 

교착상태 발생 코드

아래의 코드는 교착상태를 스레드를 이용해서 발생한 예제입니다. 여기서는 간단히 메인 스레드와 메인 스레드에서 생성된 스레드를 고려합니다.

여기서 자원은 뮤텍스인 lock1과 lock2를 말하지요. 

 

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>


pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *function(void* arg){

        sleep(1);       //main thread가 먼저 실행할 여지를 줌
        printf("\t thread start\n");

        pthread_mutex_lock(&lock2);
        pthread_mutex_lock(&lock1);

        printf("\t critical section \n");

        pthread_mutex_unlock(&lock1);
        pthread_mutex_unlock(&lock2);

        printf("\t thread end\n");

}

int main(){
        pthread_t tid;

        printf("main thread start and create thread\n");
        pthread_create(&tid,NULL,function,NULL);

        pthread_mutex_lock(&lock1);
        sleep(5);               //thread가 lock2를 먼저 실행할 여유를 줌
        pthread_mutex_lock(&lock2);

        printf("critical section \n");

        pthread_mutex_unlock(&lock2);
        pthread_mutex_unlock(&lock1);

        pthread_join(tid,NULL);
        printf("main thread end\n");

}

 

(정확히 100% 아래처럼 동작한다고 말할 수는 없지만 위 코드는 대부분 제가 의도한 대로 동작합니다. 왜냐면 스레드 실행 순서의 흐름은 예측할 수 없으니까요.)

 

코드를 보면 각각 critical section을 pthread_mutex_lock을 통해 보호하고 있지요. 이 소스 코드에서 눈 여겨 봐야할 점은 메인 스레드가 우선 lock1을 점유하고, 이후 생성된 스레드는 lock2를 점유하고 있습니다. 

바로 메인 스레드는 lock2를 점유하여 임계 영역에 진입하여야하는데 이미 생성된 스레드가 가지고 있습니다. 그렇기 때문에 lock2가 해제될때까지 기다립니다.

한편 생성된 스레드는 lock2는 점유했고 lock1을 얻은 후에 임계 영역을 진입하려합니다. 하지만 lock1은 이미 메인 스레드에 의해 점유되었습니다. 따라서 lock1이 해제될때까지 기다려야합니다.

 

여기서 위의 네가지 조건이 보이시나요?

첫번째 조건으로 critical section으로 특정 한 스레드만 임계 영역에 진입할 수 있습니다. 여기서 임계 영역이 중첩되어 있네요. lock1을 이용해 잠근 임계영역과 lock2를 통한 임계영역이지요.

두번째 조건으로 점유와 대기를 이루고 있습니다. 메인 스레드는 lock1을 점유하고 lock2가 해제되기를 기다리고 있고 생성된 스레드는 lock2를 점유하고 메인 스레드에 의해 lock1이 해제될때까지 기다리고 있습니다.

세번째 조건은 비선점 조건인데 서로 강제로 lock1, lock2를 가져올 수 없습니다.

네번째 조건은 위의 그림처럼 그려보면 사이클을 이루게 되죠.

 

 

이 프로그램의 실행결과는 어떨까요? 무사히 수행이 될까요? 실행시켜 보도록 하겠습니다.

 

# ./a.out   main thread start and create thread            thread start

네, 사용자가 중지하지 않는 이상 이 프로그램은 영원히 끝나지 않습니다. 아래에서 교착상태를 해결하는 코드를 볼 수 있습니다.

 

 

 

 

교착상태 문제 해결

교착상태가 발생하면 어떻게 해결할 수 있을까요? 크게 세가지 방법이 있는데 간략히 알아보도록 합시다.

 

1) 교착 상태 예방

교착 상태가 발생하기 전에 조치를 취하는 방식으로 위의 4가지 조건 중 하나라도 발생시키지 않으면 됩니다. 

- 자원의 상호배제 조건 방지

- 점유와 대기 조건 방지

- 비선점 조건 방지

- 순환 대기 조건 방지

 

앞서 얘기했듯이 처음 세조건이 만족되면 순환 대기가 발생하므로 결국에는 순환대기를 발생시키지 않으면 됩니다.

교착 상태 예방은 시스템의 처리량을 떨어뜨립니다. 

 

2) 교착 상태 회피

예방처럼 교착 상태의 발생 가능성을 미리 제거하지 않고 교착상태가 일어난다고 보고 이것을 회피하는 것입니다. 예를 들어 몇 초동안 프로세스나 스레드가 임계 구역 전에 대기 중이라면 이 시간이 지난 후 다음 작업을 수행합니다. 위의 예제코드를 아래와 같이 수정할 수 있습니다.

 

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>


pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *function(void* arg){
        struct timespec tout;
        struct tm* t;
        int locked;

        sleep(1);       //main thread가 먼저 실행할 여지를 줌
        printf("\t thread start\n");


        clock_gettime(CLOCK_REALTIME,&tout);
        tout.tv_sec += 5;

        pthread_mutex_lock(&lock2);
        locked = pthread_mutex_timedlock(&lock1,&tout);  //5초간만 lock이 걸림

        printf("\t critical section \n");

        if(locked == 0){
                pthread_mutex_unlock(&lock1);
        }
        pthread_mutex_unlock(&lock2);

        printf("\t thread end\n");

}

int main(){
        pthread_t tid;

        printf("main thread start and create thread\n");
        pthread_create(&tid,NULL,function,NULL);

        pthread_mutex_lock(&lock1);
        sleep(5);               //thread가 lock2를 먼저 실행할 여유를 줌
        pthread_mutex_lock(&lock2);

        printf("critical section \n");

        pthread_mutex_unlock(&lock2);
        pthread_mutex_unlock(&lock1);

        pthread_join(tid,NULL);
        printf("main thread end\n");

}

 

pthread_mutex_timed_lock 함수는 특정 시간동안 lock을 얻을 수 없다면 뮤텍스를 잠그지 않고 ETIMEDOUT이라는 오류 부호를 돌려줍니다. 따라서 스레드가 무한정 차단되지 않게 만듭니다. 이 코드를 실행시켜보면 아래와 같이 끝나기는 합니다.

 

# ./a.out main thread start and create thread          thread start          critical section critical section          thread end main thread end

 

 

3) 교착 상태 회복 

교착 상태를 시스템에서 탐지하여 회복시키는 알고리즘으로 교착상태를 회복합니다.