Deadlocks
Q:데드락이 걸릴거를 예측할 수 있느냐? 그걸 예상하고 막을 수 있을까?
Resource Allocation Graph
요청과 할당을 그래프로 표현한 것!
이 요청과 할당의 그래프가 circular가 될 때가 있으면, 데드락이 발생한다.
이 때, 할당에서 가능한 자원이 없는 상태, 그러니까 무조건 Circular라고 다 되는건 아니고, 가능한 자원이 없는 원이 만들어질 때, 그리고 서로가 서로를 들고 있을 때, 데드락이 발생함.
가운데꺼는 데드락, 오른쪽 꺼는 데드락이 안 생긴다.
해결책
1.
proactive : ensure system will never enter a deadlock state
2.
reactive : allow system to enter a deadlock state and then recover
3.
No handling : ignore the problem and pretend that deadlocks never occur in the system.
8.3 데드락 특성
데드락이 어떻게 발생하나요?
1.
Mutual exclusion
a.
오직 하나의 프로세스만 리소스를 쓸 수 있다.
2.
No preemption
a.
프로세스가 자기 작업이 다 끝나고, 스스로가 리소스를 놓아준다.
b.
사실 누군가가 강제로 리소스를 뺏으면 없을 것
3.
Hold and wait
a.
한 프로세스가 최소 한 개의 리소스를 잡고 있고, 다른 프로세스에 의해 잡혀있는 추가적인 리소스를 요구한다.
4.
Circular wait
a.
결국 서로사 서로를 물고 있어야한다.
자원 할당 그래프
시스템 자원 할당 그래프라고 하는 그래프로 더욱 정확하게 기술할 수 있다.
정점 V의 집합과 간선 E의 집합으로 구성됨.
스레드 Ti에서 자원 Rj로 가는 선은 요청 간선
자원 Ri에서 스레드 Tj로 가는 간선은 할당 간선
교착상태를 갖는 cyclic Vs 교착 상태 없는 cyclic
왼쪽이 교착 상태가 있고, 오른쪽이 교착상태가 없는 순환 고리이다.
자원 할당 그래프에서 사이클이 없다면 교착 상태가 아니고, 사이클이 있다면 교착 상태일 수도 있고 아닐 수도 있다.
8.4 교착 상태 처리 방법
•
교착 상태 예방
◦
필요 조건 중 적어도 하나가 성립하지 않도록 보장하는 일련의 방법. 자원이 어떻게 요청될 수 있는지를 제한 함으로써 교착 상태를 예방한다.
•
교착 상태 회피
◦
스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 ㅇ ㅛ구
◦
추가적인 지식을 가지고 운영체제는 스레드가 기다려야할지 않을지를 결정할 수 있다.
•
그냥 무시하기
◦
시스템이 교착 상태인지 탐지할 수 있어야한다.
◦
교착 상태를 무시하는 것이 비용이 적게 든다.
8.5 Deadlock Prevention
•
Limited Resource
◦
Sharing을 허용한다.
◦
기본적으로 virtualizing을 함으로써 공유를 허용한다.
◦
예를 들어 프린터
◦
프린터 스풀링, 물리적으로는 공유하지 않지만 가상으로는 공유하고, 각각은 모두 독립적으로 사용한다고 생각. 그리고 이런 요청을 타임 쉐어링으로 처리한다.
•
No Preemption
◦
선점을 허용하자!
◦
프로세스에서는 CPU 선점을 허용하는데, 컨텍스트 스위칭을 사용해서 상태를 저장하고 복구한다.
•
Hold and wait
◦
프로세스가 리소스를 하나씩 요청하기 때문인데, 모든 걸 한 번에 요청해버리면 문제가 해결된다.
▪
자원 요청의 동적 특성으로 인해 대부분의 응용 프로그램에는 실용적이지 않다.
◦
스레드가 자원을 전혀 갖고 있지 않을 대만 자원을 요청할 수 있도록 허용
▪
스레드가 추가 자원을 요청할 수 잇으려면, 자신에게 할당된 모든 자원을 반드시 먼저 방출해야함.
▪
단점이 있다.
•
자원이 할당되었지만 장기간 사용되지 않을 수 있기에 자원 이용률이 낮을 수 있고,
•
인기 있는 여러 개의 자원이 필요한 스레드는 필요한 자원 중 적어도 하나는 항상 다른 스레드에 할당되므로 무한정 대기해야할 수 있다.
•
Circular wait
◦
리소스의 전체 순서를 매기고, 프로세스는 오름차순으로 리퀘스트를 요청한다.
◦
순환 대기 조건에 연루된 스레드들을 {T0,T1...Tn}이라 부르고 Ti는 Ri를 기다리고 Ri는 Ti+1이 차지하고 있을 때. Ti+1이 Ri를 가지고 Ri+1을 요청하므로 F(Ri) < F(Ri+1)이다. 하지만 이는 결국 F(R0) < F(R0)이므로 순환 대기가 성립하지 않는다.
◦
하지만 락이 동적으로 획득될 수 있다면 락 순서를 부여한다고 교착 상태 예방을 보장하지는 않는다.
◦
void transaction(Account from, Account to, double amount){
mutex lock1, lock2;
lock1 = get_lock(from);
lock2 = get_lock(to);
acquire(lock1);
acquire(lock2);
withdraw(from,amount);
deposit(to,amount);
release(lock2);
release(lock1);
}
transaction(checking_account, savings_account, 25,0);
transaction(savings_account, checking_account, 50,0);
동시에 일어나면 데드락이 걸린다.
JavaScript
복사
8.6 교착 상태 회피
교착 상태를 예방하면 장치의 이용률이 저하되고 시스템 총처리율이 감소한다.
Safe State
•
deadlock safe에서 insafe한지 안한지를 리퀘스트가 올 때 확인해야한다.
안전하다는 말은 시스템이 교착 상태를 야기시키지 않고 차레대로 모두 할당해줄 수 있다는 것을 의미.
즉, 안전 순서를 찾을 수 있다면 시스템은 안전하다고 말한다.
하지만 이런 순서를 찾을 수 없다면 불안전하다. → 앞으로 교착 상태로 가게 될 수도 있다는 뜻이다.
Avoidance algorithms
•
Single instance of a resource type
◦
User a resource-allocation graph
•
Multiple instances of a resource type
◦
banker’s algorithm
자원 할당 그래프 알고리즘
요청과 할당 간선에 추가하여, 예약 간선을 도입한다.
미래에 자원을 요청할 것이라는 의미의 간선
스레드 Ti가 실행되기 전에, 스레드의 모든 예약 간선이 자원할당 그래프에 표시되어야한다.
그래프에서 사이클을 탐지하는 알고리즘은 n^2 차수의 연산이 필요하다. 모든 노드로 시작해서 그래프를 따라가라야하기 대문이다.
왼쪽이어도 오른쪽으로 할당할 수는 없다.
왜냐하면 사이클이 생기기 때문이다.
Banker’s algorithm
•
Available: 각 종류별로 가용한 자원의 개수를 나타내는 벡터로 크기는 m
◦
Available[j] = k라면 현재 Rj를 k개 사용할 수 있다는 뜻
•
Max: 각 스레드가 최대로 필요로하는 자원의 개수를 나타내는 행렬, nxm이다.
◦
Max[i][j] = k라면 현재 스레드 Ti가 Rj를 최대 k개까지 요청한다.
•
Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 nxm이다.
•
Need: 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬
◦
Need = Max - Allocation
안정성 알고리즘
1.
Work와 Finish는 크기가 m과 n인 벡터. Work = Available로 초기 값을 준다.
a.
Finish[i] = false를 초기 값으로 준다.
2.
아래 두 조건을 만족시키는 i값
a.
Finish[i] = false → 스레드에 대해 종료 여부
b.
Need ≤ Work → 필요한게 Available보다 작을 때
c.
없으면 step 4로
3.
Work = Work + Allocation → 필요한게 가용한거보다 작아서 다 사용하고 해제한다.
a.
Finish[i] = true
b.
2번으로
4.
모든 i값에 대해 Finish[i] = true이면 안전 상태
자원 요청 알고리즘
1.
Reqeust≤ Need이면 2번으로, 아니면 시스템에 있는 것보다 많이 요청했으므로 오류 처리
2.
Request ≤ Available이면 3번으로 간다. 아니면 요청한 자원이 당장 없으므로 Pi는 기다림
3.
마치 시스템이 Ti에게 자원을 할당한 것처럼 시스템 상태 정보를 변경
a.
Available = Available - Request
b.
Allocation = Allocation + Request
c.
Need = Need - Request
바뀐 상태가 안전하다면 반영된 정보대로 자원을 할당.
불안전하다면 복원한다.
8.7 교착 상태 탐지
Detect algorithm → Banker’s 알고리즘을 하거나, Resource Allocation Graph를 이용해서 지금 데드락인지 아닌지 확인한다.
언제 이 Detection Algorithm을 사용하냐?
•
데드락이 자주 발생하는 상황이면?
◦
거의 모든 타임에 리소스 요청이 허가 되지 않을거다. 아무리 CPU utilization이 낮더라도 말이다
•
일단 하고 Recovery를 하자
◦
프로세스를 종료하고, 자원을 회수한다.
◦
데드락된 모든 프로세스를 종료할 수도 있고, 데드락된 사이클이 종료될 때까지 한 개만 종료해볼 수도 있다.
Detection Algorithm
1.
자원 유형당 한 개인 경우
a.
자원할당 그래프를 그린다.
2.
여러 개인 경우
a.
Banker’s 알고리즘의 변형
b.
다른 점
i.
Allocation이 없으면 Finish[i] = true이다.
ii.
Request ≤ Work이면 Work = Work + Allocation을 한다.
iii.
왜 시스템이 바로 스레드 T의 자원을 회수하냐?
1.
교착 상태에 빠져있지 않다. 따라서 낙관적으로 볼 때, 작업을 마치기까지 더 이상의 추가적인 자원을 필요로 하지 않는다고 생각해볼 수 있다.
2.
결국 지금 당장 자원을 뺏어서 줄 수 있을지를 판단했을 때, 없으면 교착 상태이기 때문이다.
8.8 교착 상태 회복
프로세스와 스레드의 종료
•
교착 상태 프로세스를 모두 중지
•
교착 상태가 제거될 때까지 한 프로세스씩 중지
◦
프로세스의 우선순위가 무엇인지
◦
지금까지 프로세스가 수행된 시간과 지정된 일을
자원 선점
•
어떻게 리커버리를 함?
◦
victim을 정하자
▪
비용을 최대한 줄이자.
◦
Rollback
▪
아예 safe state 상태로 돌리자. 거기서부터 시작
◦
Starvation
▪
계속 victim으로 지정되면, 기아상태가 생길 수 있다. 따라서 cost factor에 롤백 숫자를 넣어야한다.