Deadlock 교착상태
무엇인가?
사거리가 완전히 막혀있는 상태에 해당한다.
위의 그림은 더이상 이동할수 있는 방법이 없는 상태이다.
누군가가 희생을 하게 되면 교착상태가 발생하지 않지만, 자원을 가지고 있으면서 다른 자원을 요청하기 때문에 교착상태가 발생한다.
문제
위의 자원은 하드웨어 자원일 수도 있고, 소프트웨어 자원일 수도 있다.
프로세스가 자원을 사용하는 절차는 크게 4가지에 따른다.
자원의 요청, 자원의 획득, 자원의 사용, 자원의 반납
발생조건
- 상호배재
- 비선점
- 보유대기
- 순환대기
위의 4가지 조건을 모두 만족해야지 교착상태가 발생한다.
자원할당그래프로 보는 DeadLock
동그라미는 프로세스를 나타내며 사각형은 자원을 나타낸다.
화살표는 자원에서 프로세스로 가는 화살표와 프로세스에서 자원으로 가는 화살표 두가지가 있다.
자원의 인스턴스가 하나 뿐이고, 사이클이 생기게 되면 데드락이 된다.
자원의 인스턴스가 여러개이고, 사이클이 생기게 되면, 데드락이 될수도 있고, 아닐 수도 있다.
첫번째 그림은 데드락이지만, 두번째 그림은 데드락이 아니다.
Deadlock 해결방법
데드락은 빈번히 발생하는 문제가 아니기 때문에 미연에 방지하는 것은 오버헤드라고 판단하여, 그래도 나두고 사람이 데드락이 발생시 프로세스를 킬하는 방법으로 하는게 활용된다. (Deadlock Ignorance)
Deadlock Prevention
Deadlock Avoidance
프로세스가 실행될때 프로세스가 최대로 사용할 자원을 정의해서, 그 정의한 자원으로 데드락의 가능성을 확인해서 자원의 할당이 진행된다.
자원의 인스턴스가 하나인 경우는 그래프로
자원의 인스턴스가 여러개인 경우는 뱅커스 알고리즘으로 확인
뱅커스 알고리즘은 프로세스가 시작될 때 자원을 최대 얼마나 쓰는지 정의한다
max가 정의된 값이다.
추가로 요청가능한 양이 need가 될수 있다.
need가 available 범위 안에 있다면 자원을 할당하지만, 그렇지 않다면 자원을 할당하지 않는다.
자원의 요청을 받아 들일지 받아들이지 않을 지를 결정하는 알고리즘이 뱅커스 알고리즘이다.
p0의 경우는 자원을 할당하지 않는다.
알고리즘은 최악의 경우를 상정하지 때문에 7,5,3을 요청할 수 있기 때문에 available에서 만족하지 못하기 때문에 할당하지 않는다.
최대요청을 가정하고서 판단하기 때문에 p0의 경우는 할당을 거절한다.
p1의 경우는 가용자원으로 need를 충족하기 때문에 알고리즘으로 판단시 가능하기 때문에 자원을 할당한다.
available로 추가요청을 모두 받아들일 수 있다면 받아들이고 그렇지 않다면 받아들이지 않는다.
자원이 남아도 데드락이 생길지 모른다는 걱정에 자원을 주지 않기 때문에 비효율적이라고 할 수 있다.
Deadlock Detection and Recovery
밑의 두가지 방법은 데드락이 생기든지 말던지 상관없이 하는 것이다.
1.데드락에 연류된 프로세스를 모두 죽이는 방법이다.
2.데드락에 연류된 프로세스를 하나씩 죽여보는 방법이다.
Deadlock Ignorance
데드락이 생기든 말든 가만히 나두는 것이다.
만약 데드락이 생겼을때 시스템이 느려지고, 프로세스가 정지되면, 사용자가 프로세스를 끝내든지 하는 방법으로 운영체제는 관여하지 않는 방법이다.
