반응형

데드락은 모든 프로세스가 그 집합내의 다른 프로세스에 의해서만 발생될 사건을 기다리고 있는 상태를 의미한다. 


반면에 기아 상태는 시스템은 교착상태는 아니지만 적어도 하나의 프로세스는 막연히 연기되는 상황을 의미한다.


즉, 교착 상태는 자원을 자유롭게 할당한 결과에 대한 자원 부족이라면 


기아 상태는 절대 사용 할 수 없는 자원을 계속해서 기다리는 결과(데드락)를 예방하기 위해 자원을 할당할 때 발생(기다림)하는 결과이다.



Deadlock


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


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


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

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

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

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


즉, 공유된 자원속에서 자원을 소유한 상태로 비동기적으로 요청 할 수 있고, 한번 소유한 자원은 반납전까지 뺏을 수 없으며 내가 아닌 다른 프로세스가 자원을 가지고 있다면 데드락이다.


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


1. 상호배제 제거

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


2. 점유대기 제거

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


3. 비선점 제거

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


4. 순환대기 제거

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


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



아이템 1,2,3이 존재하고 유저 3명중 한명이 각 아이템 1,2,3을 모두 먹으면 모든 아이템을 다시 반납하는 시스템이다.


이때 한사람이 3개를 다 가져가지 않고 다른 사람이 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 <iostream>
#include <thread>
#include <mutex>
 
using namespace std;
 
mutex myMutex1, myMutex2;
 
int item[3] = { 1,2,3 };
int user[3][3];
int deadlockCnt;
void func0(int id) {
    while (1) {
        if (deadlockCnt >= 5)
            return;
        for (int i = 0; i < 3; i++){
            myMutex1.lock();
            printf("id :: %d 잠금\n",id);
            if (user[id][i] == 0 && item[i]) {
                user[id][i] = i+1;
                item[i] = 0;
                printf("id :: %d이(가) 아이템 %d을(를) 가져감\n", id, i);
                deadlockCnt = 0;
            }
            printf("id :: %d 잠금해제\n", id);
            deadlockCnt++;
            myMutex1.unlock();
        }
 
        myMutex1.lock();
        if (user[id][0] && user[id][1] && user[id][2]) {
            printf("id :: %d 아이템 모두 반납\n", id);
            user[id][0] = user[id][1] = user[id][2] = 0;
            item[0] = 1, item[1] = 2, item[2] = 3;
            deadlockCnt = 0;
        }
        myMutex1.unlock();
    }
}
 
int main() {
    thread t0(func0, 0);
    thread t1(func0, 1);
    thread t2(func0, 2);
    t0.join();
    t1.join();
    t2.join();
    printf("데드락 발생\n");
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus







Starvation


(아래 코드로 starvation(기아 상태)가 제대로 이해 되지 않을 수 있다.

이것만 알아두자.

기아 상태는 우선순위가 밀려 교착상태가 없어도 자신이 자원을 할당받지 못하는 경우이다.)


대표적인 식사하는 철학자 문제이다.

모든 사용자가 왼손에 포크를 다 쥐게 되면 starvation 현상이 일어나게 된다.

(오른손에 다같이 쥐고 있어도 마찬가지)


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
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <thread>
#include <mutex>
 
using namespace std;
 
struct userInfo {
    int left;
    int right;
};
 
int fork[5] = { 1,1,1,1,1 };
userInfo user[5] = { -1, };
 
mutex myMutex;
 
void func(int id) {
    while (1) {
        myMutex.lock();
        if (fork[id] && user[id].left == -1) {
            printf("id :: %d이(가) 왼손에 포크 :: %d 잡음\n", id, id);
            fork[id] = 0;
            user[id].left = id;
        }
        myMutex.unlock();
        myMutex.lock();
        if (fork[(id + 1) % 5] && user[id].right == -1) {
            printf("id :: %d이(가) 오른손에 포크 :: %d 잡음\n", id, (id + 1) % 5);
            fork[(id + 1) % 5] = 0;
            user[id].right = (id + 1) % 5;
            if (user[id].left >= 0 && user[id].right >= 0) {
                printf("id :: %d이(가) 포크 %d, %d 반납\n", id, user[id].left, user[id].right);
                fork[user[id].left] = 1;
                fork[user[id].right] = 1;
                user[id].left = user[id].right = -1;
            }
        }
        myMutex.unlock();
    }
}
 
int main() {
    for (int i = 0; i < 5; i++)
        user[i].left = user[i].right = -1;
 
    thread t1(func, 0);
    thread t2(func, 1);
    thread t3(func, 2);
    thread t4(func, 3);
    thread t5(func, 4);
    t1.join();
    t2.join();
    t3.join();
    t4.join();
    t5.join();
    printf("데드락 발생\n");
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus











반응형
저작자표시 비영리 변경금지

'Applied > Operating System(OS)' 카테고리의 다른 글

스케줄링 알고리즘(Scheduling Algorithm)  (0) 2018.10.05
스케줄링(Scheduling) 개념 및 이해  (0) 2018.10.04
피터슨(Peterson's algorithm) 알고리즘  (0) 2018.10.04
데커 알고리즘(Dekker's algorithm)  (0) 2018.10.03
프로세스(Process) 개념 및 상태 천이  (0) 2018.10.03

티스토리툴바