시스템 프로그래밍 실습 14주차 : Synchronization 2

시스템 프로그래밍 실습 14주차 : Synchronization 2

 

 

 

[목차]

- Deadlock 

- Deadlock Prevention 

 

 

 

 

1. Deadlock이란? 

: 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황 / 교착 상태라고도 한다 

 

 

- P1과 P2가 리소스 A, B 둘 다를 얻어야 한다고 가정할 때, t1에 P1이 리소를 A를 얻고 P2가 리소스 B를 얻었다면 t2때 P1은 리소스 B를, P2는 리소스 A를 기다리게 됨. 하지만 서로 원하는 리소스가 상대방에게 할당되어 있기 때문에 이 두 프로세스는 무한정 기다리게 됨. 

 

 

 

Deadlock 발생 조건

 

 

1) Mutal Exclusion (상호배제)

   : 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다리는 상태 

 

2) Hold and wait (점유 대기)

   : 현재 프로세스에서 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 상태

 

3) No preemption (비선점)

   : 다른 프로세스에 이미 할당된 자원을 강제로 빼앗을 수 없다 / 선점이 시간 상의 선점이 아니라 우선권을 우선한다는 의미의 선점이다! 

 

4) Circular wait (순환대기)

   : 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있는 상태

 

 

 

 

=> Deadlock 해결방안! 

1) 데드락이 발생하지 않도록 예방(prevention) 하기

2) 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기

3) 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기

 

 

 

2.  Deadlock Prevention

 

   => 데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것!!

 

 

1) Mutal Exclusion (상호배제) [사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다]

      : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 함

          -> 그러나 추후 동기화 관련 문제가 발생할 수 있다

 

 

2) Hold and wait (점유 대기) [현재 프로세스에서 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 상태]

    : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 함 

 

 

3) No preemption (비선점) [다른 프로세스에 이미 할당된 자원을 강제로 빼앗을 수 없다]

   : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 함 / 

 

 

4) Circular wait (순환대기) [ 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있는 상태]

   : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 함 / 자원에 고유한 번호를 할당하고, 번호 오름차순대로 자원을 요구하도록 한다

 

 

 

 

 

 

예시 1) 

 

- Deadlock 발생되는 코드 

#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");

}

 

- 자원은 뮤텍스인 lock1과 lock2

- 각각 critical section을 pthread_mutex_lock을 통해 보호

 

- 메인 스레드가 우선 lock1을 점유하고, 이후 생성된 스레드는 lock2를 점유

- 바로 메인 스레드는 lock2를 점유하여 임계 영역에 진입하여야하는데 이미 생성된 스레드가 가지고 있다 

    -> lock2가 해제될때까지 기다린다 

- 생성된 스레드는 lock2는 점유했고 lock1을 얻은 후에 임계 영역을 진입하려합니다. 하지만 lock1은 이미 메인 스레드에 의해 점유됨 

    ->  lock1이 해제될때까지 기다려야 한다 

 

 

Deadlock의 네 가지 조건에 해당! 

 

1) Mutal Exclusion (상호배제) [사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다]

    - critical section으로 특정 한 스레드만 임계 영역에 진입할 수 있다 / 여기서 임계 영역이 중첩되어있다

 

 

2) Hold and wait (점유 대기) [현재 프로세스에서 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 상태]

    - 메인 스레드는 lock1을 점유하고 lock2가 해제되기를 기다리고 있고 생성된 스레드는 lock2를 점유하고 메인 스레드에 의해 lock1이 해제될때까지 기다리고 있다

 

 

3)  No preemption (비선점) [다른 프로세스에 이미 할당된 자원을 강제로 빼앗을 수 없다]

    - 서로 강제로 lock1, lock2를 가져올 수 없다 

 

 

4)  Circular wait (순환대기) [ 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있는 상태]

    - 다음과 같은 순환이 된다 

 

-> 실행결과 : 끝나지 않게 된다 

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

 

 

 

 

- Deadlock 해결 코드 

#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

 

 

 

예시 2) 

 

 

 

 

 

 

 

 

 

https://chanhuiseok.github.io/posts/cs-2/

[운영체제] 데드락(Deadlock, 교착 상태)이란?

https://jwprogramming.tistory.com/12

Deadlock 개념이란? 그에 대한 해결책/회피책

https://reakwon.tistory.com/120

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

 

 

https://yunmorning.tistory.com/51

[Operating System] Condition Variable

https://velog.io/@kmin-283/Condition-Variables#the-correct-producerconsumer-solution

Condition Variables

http://csi.skku.edu/wp-content/uploads/10-pthreads_2.pdf

http://www.lifl.fr/~marquet/ens/pp/td-mt.html

TD : Introduction au multithreading

 

 

 

 

@ 드디어 14주차 끝, 종강! 월요일 실시간 당일 과제 지옥 같았지만 재밌었당 그래도 다신 보지 말자