DeadLock-교착상태
일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
deadlock이 발생하는 조건 4가지
- Mutual Exclusion - 상호배재
매순간 하나의 프로세스만이 자우너을 사용할 수 있음, 내가 가지고 있는 동안에는 다른 누구도 내가 쓰고 있는 자원을 같이 쓸 수 없음. - No Preemption
비선점 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음 - Hold and Wait - 보유대기
자원을 가진 프로세스가 다른 자원을 기다릴때 보유 자원을 놓지 않고 계속 가지고 있음 - Circular Wait 순환 대기
자원을 기다리는 프로세스간에 사이클이 형성됨,
예를 들어, 프로세스 P0,P1,,,,Pn이 있을때
P0는 P1이 가진 자원을 기다리고
P1은 P2가 가진 자원을 기다리고
...
Pn은 P0가 가진 자원을 기다릴때
이런경우 자원 할당 그래프를 그려서 확인한다.
- 동그라미: 프로세스 자원
- 자원-> 프로세스 화살표 : 이 프로세스가 이 자원을 가지고 있다.
- 프로세스 -> 자원으로 화살표 : 이프로세스가 이 자원을 요청했다.
- 사각형 안에 점: 자원의 수
판단방법
그래프에 cycle이 없으면 deadlock이 아니다.
위 그림은 deadlock아님
cycle이 있으면
만약 자원당 instance가 1개밖에 없으면 deadlock
만약 많은 instance가 있으면 deadlock일수도 아닐 수 도 있다.
이그림은 cycle이 있고, deadlock이다.
왜냐하면 R2자원에 사이클이 2개 있으므로, R2에서 자원 2개가 이미 P1,P2한테 가있는데 P3가 요청을 하므로 deadlock이다.
이건 데드락이 아니다. 왜냐하면 사이클이 존재하지만, P2,P4가 자원을 release한다면 다시 P1이 R1,R2를 가져갈 수도 있기 때문이다.
Deadlock의 처리방법
- Deadlock Prevention
- Deadlock Avoidance
- Deadlock Detection and Recovery
- Deadlock Ignorance
Deadlock Precention, Deadlock Avoidance는 Deadlock을 미연에 방지한다.
나머지 2가지는 일단 Deadlock이 생기게 두는데 3번째는 시스템이 느려진 상태에서 혹시 Deadlock이 있나 detection을 하고, 그다음에 만약 deadlock이 발생한 상태에서 Recovery를 한다.
4번째 방식은 아무일도 안한다.
근데 OS에서는 의외로 4번째 방식을 채택하고있다.
우리가 데드락에 대해서 열심히 배우지만 의외로 데드락을 무시하는 상태
왜냐하면, 데드락이 애초에 발생할 확률이 희박하고, 그다음에 만약에 발생하더라도 그냥 껏다 키는게 더 비용이 데드락을 발생시키지 않게 구현하는것보다 비용이 낮기 떄문이다.
Deadlock Prevention
deadlock의 4가지 조건중 하나를 원천적으로 차단해서 안생기게 하는것이다.
- Mutual Exclusion: 애초에 공유자원에서 문제가 생기므로, 해결 방법 x
- Hold and Wait
방법 1: 프로세스 시작시 모든 필요한 자원을 할당 받게 하는방법 -> 프로세스가 종료 될때 까지 어떤 자원이 필요한지 모르는데, 처음부터 다 할당하면 자원 비효율성 증가.
방법 2: 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청 - No preemption
자원을 기다려야하는 경우 자원을 놓지 않는게 아니라, 뺏어올 수 있게 하기
state를 쉽게 save하고 restore 할 수 있는 cpu,memory에서 주로 사용
왜냐하면 cpu를 빼앗더라도 PCB에 저장해 놨다가, 바로 고 다음부터 다시 또 실행이 가능하기 때문에 - Circular wait
모든 자원에 할당 순서를 정해서 정해진 순서대로만 자원 할당
예를 들어, 내가 4번 자원을 가지고 싶으면 1,2,3번 자원을 가져야만 4번 자원을 요청 할 수 있는 상태
그러면 내가 1,2를 가지고 있고 3을 요청하려면,
나머지 모든 프로세스들은 3을 요청할 수 없다. 1,2를 이미 내가 가지고 있기 때문에
DeadLock Avoidance
이것 또한 DeadLock을 미연에 방지하는것이다.
프로세스가 시작될 때 프로세스가 시작해서 종료될때까지 최대 사용량을 이미 알고 있다고 가정하에 DeadLock을 방지하는 방법이다.
2가지 경우 Avoidance알고리즘이 있다.
1. 자원이 한가지 있는경우, 앞에서 사용했던 Resource Allocation Graph Algorithm을 사용한다.
2. 자원이 여러개 있다면, Banker's Algorithm을 사용한다.
자원이 1개 있는경우
Cycle을 그려서 확인해본다.
Deadlock Avoidance는 프로세스가 최대로 사용할 자원을 이미 알고 있으므로, 미리 자원을 할당하기 전에 점선을 추가한다.
process에서 자원으로 가는 경우 밖에 없고, 지금 당장 이 자원을 요청한 건 아니지만, 평생 1번 자원을 요청할 수 있다. 이말이다.
만약 자원이 할당되면 실선으로 바뀐다. 만약 P2가 자원 R2를 요청하고 자원이 할당되면 Deadlock이 아니다 왜? 지금 당장 P1이 R2를 요청한게 아니기 때문이다.
그래서 만약 나중에 R2를 요청하더라도 P2가 반납했더라면 DeadLock이 안생기고 P2가 점선으로 바뀐다.
결국 ReqeustEdge가 AssignmentEdge로 바뀔때 Cycle이 생기지 않는 경우에만 요청자원을 할당하는 것이다.
자원이 여러개 있는경우
Banker's Algorithm을 사용한다.
프로세스가 현재 5개 있고 자원이 3개 자원에 해당하는 Instance들이 A는 10개 B는 5개 C는 7개가 존재한다고 하자.
Allocation은 이미 프로세스에 자원이 할당된것이고,
Avoidance는 평생 이용할 최대치의 자원을 미리 알고 있다고 하였으므로, A,B,C의 최대 자원을 확인 할 수 있다.
그러면 Max-Allocation을 하면 Need가 나오는데
자원을 프로세스가 요청을 하면 일단, 현재 Available자원을 가지고 Need의 자원을 전부 줄 수 있는지 확인하고 주는것이다.
예를 들자면, P1이 A 1개 C 2개를 요청했다고 치자. 현재 가용자원이 3,2,2에서 1,0,2를 줄 수 있는지를 확인하는게 아니라,
먼저 Need에서 확인을 해야하는것이다. Need인 1,2,2를 Available인 3,3,2가 줄수 있는지 말이다. 만약 줄수 있으면 그뒤에 요청을 허가하는것이다.
만약에 P0가 1,3,2를 요청하면 Available은 가능할지 몰라도 Need에서 필요한게 7,4,3이므로 Available로 애초에 처리가 안된다. 그러므로 만약 P0가 최대 요청을 해버리면 가용자원만으로는 1,3,2 요청이 안되므로,
자원 할당 요청을 처리하는게 아니라 무시하고,
다른 프로세스들이 종료되어서 Allocation이 줄어들어서 그 자원들이 P0한테 할당이 되면 Need가 줄어들고 Available로 처리가 가능하면, 그때되면 자원요청 처리를 해준다.
고로, P0는 A를 1개만 달라고 요청을 하더라도 무시한다. 왜? 최대 요청을 처리할 수 있을만큼의 Available자원이 없기 때문이다.
즉 Deadlock Avoidance는 safe state를 만족시켜야한다.
- safe state
시스템 내의 프로세스들에 대한 safe sequence가 존재하는상태 - safe sequence
프로세스의 sequence<P1,P2,,,Pn>이 safe하려면 Pi의 자원요청이 가용자원 + Pi의 보유자원에 의해 충족되어야한다.
만약에 Pi의 자원요청이 즉시 충족될 수 없으면, Pj(j<i)인 모든 프로세스가 종료될때 까지 기다리다가 Pj 프로세스들이 모든 작업을 완료하고 Allocation된 자원들을 반납하고 종료하면, Pi의 Allocation이 늘어나므로 자원요청이 성공 할 수 있다.
Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.
Deadlock Detection and recovery
Deadlock Detection
1. 자원이 1개있는경우
자원이 1개있는경우는 앞에서 처럼 자원할당 그래프를 통해 사이클 생성 유무로 Deadlock을 Detection할 수 있다.
그림처럼 자원당 인스턴스가 하나 있는경우는 자원을 빼고 그래프를 프로세스만으로 그릴 수 있다.
그래서 프로세스의 갯수가 n개라고 가정하면 이 n개에서 모두 화살표가 뻗어나간다면, n-1개가 생기고 이러면 n^2-n개를 확인해야하므로 O(n^2)만큼 시간 복잡도가 걸린다.
- 자원이 여러개 있는 경우
Banker's알고리즘과 비슷하게, Allocation, Request, Available Table을 그려서 Deadlock 여부를 판단해야한다.
그런데 이전 Avoidace의 Banker알고리즘과 다르게 우리는 현재 Deadlock이 생기면 그냥 생기게 놔두는 전략이므로, 프로세스의 최대 요처어 자원의 갯수를 미리 알필요가 없다.
그러므로, 그림과같이
P1,P3,P4가 요청을 보내도(Request Table에서) 현재 Available이 전부 0,0,0이기 때문에 당연히 자원을 당장 주지는 못한다.
다만 이게 Deadlock이냐 아니냐를 판단할때는 우리는 Deadlock이 생기면 그냥 생기게 냅둔다고 하였으므로, 낙관적 접근으로, 지금 자원을 요청하지 않은 P0,P2 프로세스는 자원을 반납을 할 것이라고 가정을 한다.
그러면 available은 3,1,3으로 늘어나게 되고, 그러면 P1요청을 받아 들이고 또 P1이 자원을 다 쓰고 나서 반납하면, Available이 늘어나니까 나머지 요청도 동일한 방식으로 처리해주면된다.
만약에 근데 아래 그림처럼
P2가 갑자기 C를 1개 요청한다면, 지금 P0만 B를 1개 내어놓는다고 가정하기 때문에,
P1,P2,P3,P4의 모든 요청을 받아 들일 수 없으므로, Deadlock이 걸린다.
그러므로, Deadlock을 Detection하기위해서는 현재 Available을 통해서 Request를 처리 할 수 있는지 확인하고, 만약 그렇지 않다면, Request를 하지 않은 프로세스들의 Allocation을 반납하여 추가된 Available에서 request를 처리할 수 있는것이 있는지 판단한다.
만약 그래도 그 어떠한 request도 처리를 하지 못한다면, Deadlock이 발생한다.
Recovery
- 모든 DeadlockProcess를 전부 죽인다.
- 하나씩 Deadlock Process를 죽여보면서 Deadlock이 풀리는지 안풀리는지 확인한다.
- 자원을 뺏는 방법
비용을 최소화 할 victim을 선정하고, 그 친구로부터 자원을 뺏어서 deadlock을 푼다.
그후에 safe state로 rollback하여 process를 다시 시작한다.
근데 만약에 동일한 프로세스가 반복해서 victim으로 선정되는경우 starvation이 발생하므로, rollback 횟수도 고려해서 이제 새로운 victim을 설정하는 방식을 사용해야한다.
Deadlock Ignorance
Deadlock자체가 애초에 드물게 발생하므로, Deadlock에 대한 조치, 예방이 더 큰 OverHead일 수 있다.
그래서 Deadlock이 일어나지 않는다고 생각하고 아무런 조치를 취하지 않는다.
그런데 만약 실제 시스템에서 deadlock이 발생하면 시스템이 비정상적으로 작동하는것을 사람이 직접 느낀후에 process를 직접 킬하는 방식으로 대처한다.
대부분의 OS가 채택하는 방식이다.
