×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,045,665명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형



데드락(Deadlock)이란?


교착 상태라고도 말한다.


이 데드락이 발생하는 원인은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을


기다리고 있기 때문에 서로가 아무것도 완료하지 못하는 상태를 가리킨다.



결국, 프로그램 상에서 교착 상태는 동기화과정에서 일어나는 것이며, 


동기화를 해주는 코드를 잘못짜게 된다면 프로세스는 멈추어 버리게 된다.


즉, 세마포어, 뮤텍스 등 동기화를 하려고 제작한 코드에서 프로그래머의 실수로


코드를 동기화가 제대로 진행되지 않도록 만든다면, 어느순간부터 프로세스가 멈추어 있게 된다.



예를들어보자


1. A, B사람이 하나의 사다리를 이용중인데 한명은 올라가있는 상태이고, 한명은 내려가있는 상태이다.


A가 내려가려 하고, B가 올라가려고하니 서로가 위 아래에 사람이 있기에 내려갈 수 없는 상태가 된다.


이러한 것을 데드락 이라고한다.


2. 어느 교차로에서 차량 4대가 서로 자기가 가야할 방향으로 가야하는데, 그 위치에 모두 차가 있어서


4대 모두다 이러지도 못하지도 하는 상황이 교착 상태 즉, 데드락이 걸리는 상태이다.



데드락(Deadlock) 발생 조건 및 회피 방법


데드락이 생길 수 있는 조건은 다음 4가지를 모두 만족할 때 생긴다.


1. 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다. 

2. 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

3. 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다. 

4. 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.


회피방법은 위의 4가지중 하나라도 해결한다면 데드락을 면할 수 있다.


1. 상호배제 제거

데드락은 공유 불가능한 자원을 사용하며 발생하는 것이므로 공유하도록 만들면 된다.


2. 점유대기 제거

한 프로세스가 실행되기 전 모든 자원을 할당해준다.


3. 비선점 제거

자원을 점유하고 있는 프로세스가 다른 자원을 요구 할 때 점유하고 있던 모든 자원을 반납하고 요구 자원을 사용하기 위해 기다린다.


4. 순환대기 제거

각 자원에 고유 번호를 할당하여 순서대로 자원을 요구하도록 한다.


하지만 이 방법은 자원 낭비가 심함을 알고 있어야 한다.






소스 코드를 통해 데드락에 대해 생각해보자.


데드락(Deadlock) 소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
 
sem_t semaphore[3];
 
void *threadRoutine(void *argumentPointer)
{
    long id = (long)argumentPointer;
    int i;
    for(i = 0; i < 10000; i ++)
    {
        printf("sem_wait_%ld를 시도중입니다.\n", id); 
        sem_wait(&semaphore[id]);
        printf("sem_wait_%ld 성공.\n", id);
 
        printf("sem_wait_%ld를 시도중입니다.\n"1-id); 
        sem_wait(&semaphore[1-id]);
        printf("sem_wait_%ld 성공.\n"1-id);
 
 
        printf("sem_post_%ld를 시도중입니다.\n",id); 
        sem_post(&semaphore[id]);
        printf("sem_post_%ld 성공.\n", id);
 
        printf("sem_post_%ld를 시도중입니다.\n",1-id); 
        sem_post(&semaphore[1-id]);
        printf("sem_post_%ld 성공.\n",1-id);
    }
 
    return NULL;
}
 
int main()
{
    pthread_t threadDs[3];
 
    // 두개의 세마포어를 형성하여 각 세마포어에 1개의 입장권을 부여
    sem_init(&semaphore[0], 01);
    sem_init(&semaphore[1], 01);
 
    pthread_create(&threadDs[0], NULL, threadRoutine, (void*)0);
    pthread_create(&threadDs[1], NULL, threadRoutine, (void*)1);
 
    // 스레드 조인
    pthread_join(threadDs[0], NULL);
    pthread_join(threadDs[1], NULL);
 
    printf("No Deadlock !! \n");
    return 0;
}
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


이 코드에서


No Deadlock !! 이 출력되면 데드락이 걸리지 않은 것이다.


물론 for문에서 0번 스레드와 1번 스레드가 서로 10000번씩 딱 돌게되면 위의 내용이 출력될 것이다.


하지만, 컴퓨터 OS는 스케줄러가 프로세스에게 할당 시간을 주어 돌아가게 한 후, 


모두 Concurrent하게 돌듯이 프로그램을 만들어야 하기에 Context Switching이 일어난다.


결국 Deadlock이 한번도 안 일어나야 동기화를 제대로 한 소스 코드 및 프로그램이지만, 한번이라도 일어나면


그 코드는 데드락이 일어나는 동기화가 좋지 못한 코드인 것이다.

 

거두절미하고 결과를 확인해보자.


모든 내용은 그림속에 text를 통해 해설을 해 두었다.











최종적으로 printf("No Deadlock !! \n");이 실행되지 않았다는 것은


메인 thread는 자식 thread join상태로 이미 슬립중이고.


그 자식 thread 2개가 서로 return NULL;을 하지 못하고 있다는 것을 의미한다.


즉, 이러한 것이 데드락이다.





그렇다면 이 코드에서 데드락을 푸는 방법은 어떻게 해야할까?


다음과 같이 2개만 바꾸어 주면 모든것이 해결된다.



데드락(Deadlock)을 피하는 소스 코드



threadRoutine 함수부분에

sem_wait(&semaphore[id]); 부분을 sem_wait(&semaphore[0]); 로


sem_wait(&semaphore[1-id]); 부분을 sem_wait(&semaphore[1]);로 바꾸면 모든것이 해결된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
 
sem_t semaphore[3];
 
void *threadRoutine(void *argumentPointer)
{
    long id = (long)argumentPointer;
    int i;
    for(i = 0; i < 10000; i ++)
    {
        printf("sem_wait_%ld를 시도중입니다.\n", id); 
        sem_wait(&semaphore[0]);
        printf("sem_wait_%ld 성공.\n", id);
 
        printf("sem_wait_%ld를 시도중입니다.\n"1-id); 
        sem_wait(&semaphore[1]);
        printf("sem_wait_%ld 성공.\n"1-id);
 
 
        printf("sem_post_%ld를 시도중입니다.\n",id); 
        sem_post(&semaphore[id]);
        printf("sem_post_%ld 성공.\n", id);
 
        printf("sem_post_%ld를 시도중입니다.\n",1-id); 
        sem_post(&semaphore[1-id]);
        printf("sem_post_%ld 성공.\n",1-id);
    }
 
    return NULL;
}
 
int main()
{
    pthread_t threadDs[3];
 
    // 두개의 세마포어를 형성하여 각 세마포어에 1개의 입장권을 부여
    sem_init(&semaphore[0], 01);
    sem_init(&semaphore[1], 01);
 
    pthread_create(&threadDs[0], NULL, threadRoutine, (void*)0);
    pthread_create(&threadDs[1], NULL, threadRoutine, (void*)1);
 
    // 스레드 조인
     pthread_join(threadDs[0], NULL);
       pthread_join(threadDs[1], NULL);
 
    printf("No Deadlock !! \n");
    return 0;
}
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



왜 이게 데드락을 피할수 있는것일까?


결국 어느 스레드간에 sem_wait(&semaphore[0]); 를 하고 sem_wait(&semaphore[1]);을 순차적으로 하게되면,


그 다음 스레드가 sem_wait(&semaphore[0]); 혹은 sem_wait(&semaphore[1]);를 할 때, 앞선 스레드가 이미 wait을 하였기에


자연스럽게 기다리게 된다.


그리고 나서 앞선 스레드가 post :: (V)를 해주면, 다음 스레드가 wait을 다시 할 수 있게 되어 데드락을 피할 수 있다.




동영상을 통해 Deadlock 및 Avoiding Deadlock을 확인해 보자.




반응형