contents
Deadlock
교착상태 : 각자 일부 자원은 가진 상태에서 상대방이 가진 자원을 요구하고 상대방도 자신의 자원을 내놓지 않고 상대방의 자원을 요구하는 상황
•
일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
자원(Resource)
•
교착 상태가 발생하는 근본적인 원인
시스템이 가지고 있는 한정적인 자원보다 사용하고자 하는 프로세스들의 요청이 더 많기 때문
→ 그렇다면 자원을 더 많이 준비해두자
거의 사용되지 못할 것이 뻔한데도 필요 이상의 비용을 들여 많은 자원을 구비해 놓는 시스템이 과연 가격 대비 효과 면에서 권장할 일일까?
Deadlock의 문제
무한대기(Infinite Postponement)와 Deadlock의 차이점
실행 중인 프로세스가 자원에 대해 취할 수 있는 행동
Deadlock이 발생하는 조건
1.
Mutual Exclusion(상호 배제)
: 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
•
자원을 얻으면 독점적으로 사용한다.
2.
No Preemption(비선점)
: 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.
3.
Hold and wait
: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
4.
Circular wait
: 자원을 기다리는 프로세스 간에 사이클이 형성된다.
•
필요한 자원들이 꼬리에 꼬리를 물고 사이클을 형성
Resource-Allocation Graph(자원 할당 그래프)
→ : 프로세스가 이 자원을 가지고 있다
← : 프로세스가 이 자원을 요청했다(아직 획득하지 못함)
Resource 1 | Resource 2 | Resource 3 | |
Process 1 | 요청 | 획득 | x |
Process 2 | 획득 | 획득 | 요청 |
Process 3 | x | x | 획득 |
Deadlock인지 아닌지 그래프에서 구분하는 방법
•
그래프에 Cycle이 없다면 Deadlock이 아님
•
Cycle이 있으면
◦
자원당 instance가 하나씩 밖에 없다면 사이클은 deadlock를 의미한다.
◦
instance가 여러개인 상황이라면 deadlock일 수도 아닐 수도 있다.
Deadlock 처리 방법
1.
Deadlock Prevention(미연에 방지)
: 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
2.
Deadlock Avoidance(미연에 방지)
: 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원 할당
•
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
3.
Deadlock Detection and recovery(생기는 걸 놔둠)
: Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
4.
Deadlock Ignoreance(생기는 걸 놔둠)
: Deadlock을 시스템이 책임지지 않음
•
UNIX를 포함한 대부분의 OS가 채택
•
Deadlock에 대해서 아무것도 하지 않음
•
사람이 알아서 Deadlock를 해결하도록 함
Deadlock Prevention
1.
Mutual Exclusion(상호 배제)
•
공유해서는 안되는 자원의 경우 반드시 성립해야 함
2.
No Preemption(비선점)
•
Process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
•
모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
•
State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, Memory)
◦
아무거나 막 빼앗아오면 안된다.
3.
Hold and wait
•
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.(기다릴때는 아무런 자원을 가지지 말자)
1.
프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
2.
자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
4.
Circular wait
•
모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
•
자원을 보유 중인 프로세스가 다른 자원을 할당받기 위해서는 우선 보유 중인 프로세스를 release해야 한다.
ex. 1, 3, 5번 자원이 있을 때 1번 자원부터 얻어야지만 순서대로 자원 획득이 가능
Utilization(자원이용률) 저하, throughput(전체 시스템 성능) 감소, starvation 문제→ 생기지도 않을 Deadlock를 고려해서 제약조건을 많이 달아두기 때문에 상당히 비효율적
Deadlock Avoidance
•
자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
◦
프로세스가 시작됐을 때, 해당 프로세스가 평생에 쓸 자원의 최대량을 알고 있다고 가정하고 deadlock를 피해간다.
◦
내가 자원을 줬을 때 deadlock이 생길 거 같다면 여분이 있는데도 불구하고 안준다.
•
가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
•
Safe state : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
•
Safe sequence : 프로세스의 sequence가 safe하려면 Process의 자원 요청이 가용 자원 + 모든 프로세스의 보유 자원에 의해 충족되어야 함
•
조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
◦
Process i의 자원 요청이 즉시 충족될 수 없으면 모든 Process j(j < i)가 종료될 때까지 기다린다.
◦
Process i-1이 종료되면 Process i의 자원요청을 만족시켜 수행한다.
1.
자원의 인스턴스가 1개씩 밖에 없다면 → Resource Allocation Graph algoritnm 사용
2.
자원의 인스턴스가 여러개가 있다면 → Banker’s Algorithm 사용
두 가지를 사용해서 효율적으로 deadlock를 피해간다.Resource Allocation Graph Algorithm(1 instance)
•
점선 : 이 프로세스가 평생에 적어도 한 번은 해당 자원을 사용(요청)할 일이 있다.
•
점선을 포함해서 Cycle를 생성된다면(가능성) 그대로 놔둔다.
•
Cycle이 생성될 가능성이 없다면 자원을 준다.
Banker’s Algorithm(N instance)
•
전체 자원 instance에서 할당된 자원을 빼면 Available이 나옴
•
추가 요청 가능량 → Need
할당된 자원 | 최대 자원(끝날때까지 사용하는 자원의 양) | 사용 가능한 자원의 양(가용자원) | 추가 요청 가능한 양 |
평생에 이만큼을 요청할 수가 있다. |
•
사용자는 최악의 경우에 추가 요청 가능한 양을 요청할 수 있다.
◦
P0는 최악의 경우에 (7, 4, 3)를 한 번에 요청할 수 있다.
◦
현재 (3, 3, 2)를 가지고 있기 때문에 가용 자원의 수를 넘기는 (7, 4, 3)는 불가능하다.
◦
다른 프로세스들이 resource를 돌려준다면 프로세스 0이 추가 요청 가능한 양을 모두 진행할 수 있긴하지만 Banker’s Algorithm은 보수적이기 때문에 최대 자원(추가 요청할 수 있는 자원)이 가용 자원을 넘는지 확인한다.
◦
충족이 되면 보내주고, 안되면 그 요청은 받아들이지 않는다.
•
P1의 경우에는 가용자원으로 충분히 커버를 할 수 있기 때문에 요청을 받아들인다.
◦
P1은 최대 요청을 다 받았기 때문에 요청하기 보다는 반납할 일만 남았다.
가용 자원을 가지고 커버할 수 있는 양이라면 요청을 들어주고 아니면 받아들이지 않는다. 각 프로세스의 요청 자원을 다 충족하는 시퀀스가 존재한다면 → safe한 상태(절대 Deadlock이 걸리지 않는)
추가로 들어야할 자원이 Available를 모두 충족하는 지 확인한다.
•
가용 자원만 가지고도 Max가 처리되니깐 준다 = deadlock으로부터 안전
빈번한 이벤트가 아니니깐 그냥 그대로 사용하다가 갑자기 시스템 문제가 생기면 Deadlock Detection를 하고 Deadlock이 발견된다면 recovery를 하자.
Deadlock Detection and recovery
•
Resource type 당 single instance인 경우
◦
자원 할당 그래프에서의 cycle이 곧 deadlock를 의미한다.
▪
wait-for graph에서 overhead
•
프로세스가 N개 있다고 할 때, wait-for graph에서 cycle를 찾아내는데 O(N^2)의 시간이 걸린다.
•
너비 우선 탐색, 깊이 우선 탐색 → 모든 점을 다 탐색, Cycle를 찾아낼 수 있다.
•
Resource type 당 multiple instance인 경우
◦
Banker’s algorithm과 유사한 방법 사용
◦
프로세스가 자원을 요청하면 다 준다.(낙관적으로 접근)
할당된 자원 | 요청한 자원 | 사용 가능한 자원 |
◦
P0, P2는 요청한 자원이 없으니깐 반납할 것이라고 보기
◦
아무 요청이 없는 것들을 쌓고 쌓고 쌓아서 요청된 것들을 다 허용을 하고, 다른 프로세스들도 요청된 게 없는 상태에서 또 반납을 하게 된다.
요청을 받아들이는 시퀀스가 있다면 데드락이 없다.만약, P2가 자원 C를 더 요청하는 경우가 오면 어떡하나?
Deadlock이 있는지 확인하려면,
1.
가용 자원이 있는지 확인
2.
가용 자원으로 처리 가능한 프로세스가 있는지 확인
3.
요청한 게 없는 프로세스는 가용자원으로 합친다.
4.
처리 가능한 프로세스가 있는지 확인
5.
위의 프로세스를 반복하면서 결론적으로 모든 프로세스가 처리되는지 본다.
6.
Deadlock이 발견된다면, Recovery 진행
Recovery 진행
1.
Process termination
a.
Deadlock에 연루된 모든 프로세스들을 한꺼번에 사살
b.
Deadlock에 연루된 프로세스들을 하나씩 사살한다.
•
하나를 죽이고 문제가 해결되지 않는다면 다른 애를 또 죽이고 하는 식으로 진행 → Deadlock이 없어질 때까지
2.
Resource Preemption
프로세스로부터 자원을 뺏는 방식
a.
희생양을 찾는다.
b.
희생양으로부터 자원을 뺏어서 Deadlock를 없앤다.
c.
다시 safe state로 rollback하여 process를 restart를 하면 데드락이 없어진다.
•
자원을 뺏었는데, 다른 프로세스가 갖기 전에 해당 자원을 다시 요청해서 가져가고 하는 식의 문제 존재
⇒ Starvation 문제
◦
자원을 빼앗는 패턴을 조금씩 다르게 한다.
◦
계속 특정 프로세스만 자원을 뺏긴다면 비용을 최소화하는데는 성공했지만 해당 프로세스는 앞 부분으로 rollback해야하기 때문에 희생이 크다.
◦
비용말고도 어떤 프로세스가 rollback를 몇 번 했는지도 중요한 요소
Deadlock Ignoreance
Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다.
•
드물게 발생하는 Deadlock를 위해서 따로 조치를 취하는 것 자체가 더 큰 overhead라고 생각해서 아무 조치도 취하지 않는 것.
•
시스템에 deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처한다.
•
대부분의 운영체제가 채택하고 있는 방식