Deadlock
교착상태에 빠지다
두개 이상의 프로세스가 서로 상대방의 작업이 끝나기를 기다리고 있어
결과적으로 아무것도 완료되지 못하는 상태
Blocked/Asleep state
프로세스가 특정 이벤트를 기다리는 상태
프로세스가 필요한 자원을 기다리는 상태
Deadlock state
프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우를 프로세스가 deadlock상태에 있다고 하며
시스템 내에 deadlock상태에 빠진 프로세스가 있는 경우 시스템이 deadlock상태에 있다고 한다
프로세스가 일을 못하고 계속 기다린다는 점에서 Starvation과 유사하지만,
Starvation은 프로세스를 기다리는 단계인 ready상태에서의 대기현상이고,
deadlock은 자원이나 이벤트를 기다리는 asleep상태에서의 대기현상이다
또한 Starvation은 영원한 기다림은 아니지만, deadlock은 발생 가능성이 zero이다.
자원의 분류
Deadlock과 자원은 밀접한 관련이 있다.
일반적 분류
HW resources vs SW resources
다른 분류법
1. 선점 가능 여부에 따른 분류
2. 할당 단위에 따른 분류
3. 동시 사용 가능 여부에 따른 분류
4. 재사용 가능 여부에 따른 분류
선점 가능 여부에 따른 분류
Preemptible resources
선점 당한 후 돌아와도 문제가 발생하지 않는 자원(프로세서, 메모리 등)
Non Preemptible resources
선점당하면 이후 진행에 문제가 발생하는 작업.
Rollback, restart 등 특별한 동작이 필요
(disk drive등)
할당 단위에 따른 분류
Total allocation resources
자원 전체를 프로세스에게 할당(프로세서, disk drive 등)
Partioned allocation resources
하나의 자원을 여러 조각으로 나누어 여러 프로세스에게 할당(메모리 등)
동시 사용 가능 여부에 따른 분류
Exclusive allocation resources
한 순간에 한 프로세스만 사용 가능한 자원(프로세서, 메모리, disk drive등)
*메모리는 partioned라 공유가능하다고 생각할 수 있지만, 한 프로세스에게
할당된 메모리 공간은 한 프로세스만 접근 가능하므로 Exclusive가 맞다
Shared allocation resources
여러 프로세스가 동시에 사용 가능한 자원
(한개의 프로그램으로 여러개의 창을 사용가능한 SW, shared data 등)
재사용 가능 여부에 따른 분류
SR(Serially-reusable Resources)
시스템 내에 항상 존재하는 자원
사용이 끝나면 다른 프로세스가 사용 가능
ex) 프로세서, 메모리, 디스크, 프로그램 등
CR(Consumable Resources)
한 프로세스가 사용한 후에 사라지는 자원
ex) signal, message
Deadlock과 자원의 종류
Deadlock을 발생시킬 수 있는 자원의 형태
Non-preemptible resources - 비선점 자원
Exclusive allocation resources - 한순간에 한 프로세스만 사용가능한 자원
Serially resuable resources - 시스템 내에 항상 존재하는 자원
//할당 단위는 영향을 미치지 않음
//CR을 대상으로 하는 Deadlock model은 너무 복잡하므로 제외한다
