deadlock
교착상태란 어떤 다른 프로세스에 의해서 발생된 이벤트에 의해서 모든 프로세스가 대기하는 현상
요청한 자원을 다른 대기중인 쓰레드가 점유하고 있기 때문에 자원을 요청한 대기중인 쓰레드(또는 프로세스)는 다시는 쓰레드 상태를 변경할 수 없다.
waiting 스레드가 계속 대기만하고 자기 상태를 못바꿈, 어떤 리소스가 다른 waiting하는 스레드에 의해 점유됨
자원의 종류는 몇가지 동일한 인스턴스로 구성된다.
예를 들어 CPU 싸이클, 파일, 입출력 기기(프린터, 드라이브 등)
동일한 자원 유형의 인스턴스를 요청한다면 어떤 인스턴스의 할당이 요청을 만족해야함
어떤 한 쓰레드는 자원이 필요할때 "Request – Use – Release"와 같은 순서로 사용할 수 있다. 이 부분이 critical section
deadlock occur
어떤 한 프로세스가 A라는 자원을 점유한 상태에서 B라는 자원을 점유하고자 할때 B 자원을 가지고 있는 프로세스가 A 자원을 점유하고자 할때 발생
first_mutex, second_mutex 선언
어떤 스레드는 first mutex, second_mutex를 획득하여 진입한다.
pthread_mutex_lock(&first_mutes);
pthread_mutex_lock(&second_mutes);일이 끝난 후 mutex second, first unlock 한다.
다른 스레드는 second부터 얻고 first를 얻는다. first , second 순으로 릴리즈한다.
pthread_mutex_lock(&second_mutes);
pthread_mutex_lock(&first_mutes);
상황 발생:
첫번째 스레드가 first_mutex를 점유하고 second를 점유하려고 하는데, 다른스레드가 second를 점유한다. 각각 first와 second를 갖고있어서 첫번째스레드는 second를 받지 못한다. 두번 째 스레드는 first를 갖지 못한다.
deadlock 네가지 조건
4가지 조건이 만족해야 한다.
-
Mutual Exclusion 상호배제: 적어도 한 개의 리소스가 non-sharable 할때, 한개의 파일을 여러 스레드들이 읽기(read)만 하면 아무문제 없음, write 하면 race condition 하겠지
최소 한개의 자원이 임계 영역에서 점유된다. -
Hold and Wait 점유대기: 적어도 한 개의 리소스를 점유하고 waiting 해야 문제생김
어떤 한 쓰레드가 최소 한개의 자원을 점유하고 다른 쓰레드가 가지고 있는 추가적인 자원을 얻고자 대기할때 -
No preemption 선점불가: cpu 등 자원 선점 불가할때
-
Circular Wait 원형대기: 원형으로 서로 기다림, dependency graph circular.
종속적인 대기 그래프가 원형이 존재할때
Resource-Allocation Graph
자원 할당 그래프
deadlock을 쉽고 정확하게 이해하위한 directed graph 방향성그래프
V: vertex 집합
E: Edge 집합 으로 구성되어 있다.
T: active threads 스레드 집합
R: resource 집합
request edge : (Ti -> Rj) Ti(스레드)가 Rj(리소스)를 요구했다.
assignment dege : (Rj -> Ti) Rj(리소스)를 Ti(스레드)에 할당했다.
first_mutex를 thread_one에 할당 thread_one은 second_mutex 요청,
근데 second_mutex는 이미 thread_two가 가지고 있다. thread_two가 first_mutex request함
R1, R3는 인스턴스가 한개
R2 인스턴스 2개, R4는 3개
쓰레드 T3은 작업을 언젠가 마치고 T2->T1순으로 자원을 할당받게 되어서 수행을 마친다.
↓사이클이 없음 deadlock (x)
2개의 사이클 존재,
R2가 T1과 T2에 할당되어있기 때문에 원형대기가 발생
서로서로 물고물린다. deadlock(o)
한개의 사이클 존재
T2와 T4가 작업을 마치고 R1, R2 자원을 반환하면서 T3, T1도 작업을 마칠 수 있다.
예를들어 T4가 쓰다가 반납해줘서 T3이 받을 수 있다. deadlock(x)
=>
resource-allocation graph 가 사이클이 없으면 deadlock에 절대 들어갈 일이 없다.
사이클이 있으면 daedlock이 있을 수도 있고 없을 수도 있다.
deadlock 처리 방법
1. 무시 : 일어나지 않을 거라고 생각함
2. prevent 또는 avoid(회피) : 어떤 방법을 써서 완전히 방지 -> 거의 불가능
교착 상태 회피: Banker's Algorithm
3. detect, recover : deadlock 내버려두고 발생시 회복시키기
탐색(Detect)하고 회복(Recover)하는 절차
교착상태 탐색 : 교착상태가 발생하는지 탐색
교착상태 회복 : 교착상태가 발생하기 이전으로 되돌리기
Deadlock Prevention
4가지 necessary conditions 중 한가지만 막자
교착상태가 발생하는 조건 4가지(상호배제, 점유와 대기, 선점 불가, 원형 대기)중 하나가 발생하는 것을 막는 방법
-
Mutual Exclusion :
상호배제 조건은 적어도 한 개의 resource는 non-sharable(공유불가능) 해야한다. 모든 resource를 공유가능하게 하면 이런일 발생하지 않는다.
-> 상호배제 조건이 없는 문제는 고려대상이 아니다.
mutex lock 같은 애들은 공유되면 안됨
-> 불가능 -
Hold and Wait
어떤 한 쓰레드가 자원을 요청할때 이미 점유하고 있는 자원을 해제한 다음 요청하는 방식
스레드가 어떤 자원 요청할때 자기 갖고 있는거 다 내려놓고 요청하게 하기
10개파일 오픈 해놓고 새 파일 오픈할때, 기존 파일 다 꺼야됨..
-> 실용적이지 않음 -
No Preemption
preemption 되게 하자, 어떤 자원을 holding하고 있는데, 다른 프로세스가 갖고 있다면 뺏어버리자. 뺏긴애는 문제일으킴
-> 일반적으로 쓸 수가 없다. -
Circular Wait
그나마 현실적임
resource type들에 순서를 부여한다. -
파일, 2.메모리, 3.sdd, 4.모니터 등..
요청할때 내가 점유하고 있는 resource 보다 번호가 더 높은것만 요청한다.
내가 점유하고 있는 자원보다 높은 자원 유형들만 요청한다. 다른 말로 말하면 내가 점유하고 있는 자원보다 순서가 낮은 자원들을 요청하는 것을 막는다.
circular wait 조건이 발생할 수 없다
-> 적어도 deadlock 발생안함, starvation 위험
transaction
원자적 operation 원자적 오퍼레이션
예) 계좌이체 트랜잭션
Account 'from' 에서 'to'로 amount (만원)을 보낸다.
mutex lock1, lock2를 가지고
acuire(lock1); : 내 계좌에 lock을 건다.
acuire(lock2); : 아들 계좌에 lock을 건다.
그 후
withdraw : 돈빼기
deposit : 입금
-> atomic 해야하므로 반드시 lock두개를 획득해야한다.
그러나 아빠->아들 , 아들-> 아빠 동시에 돈을 보내면 문제 발생
transaction(checking_account, savings_account, 25.0)
transaction(savings_account, checking_account, 25.0)
