[운영체제] Deadlock

사거리가 완전히 막혀버린 상황

 

프로세스들이 서로가 가진 자원을 기다리면 block 된 상태다

 

데드락이 발생하는 4가지 조건

1. 상호배재 - 하나의 프로세스만 자원을 사용할 수 있다.

2. 비선점 - 자원을 빼앗기지 않는다.

3. 보유대기 - 다른 자원을 기다릴때 보유 자원을 놓지 않는다.

4. 순환대기 - 내가 필요한 자원은 다른 프로세스가 가지고 있고 , 또 그 프로세스도 다른 프로세스의 자원을 기다리고

하는 싸이클

 

데드락을 처리하는 방법

위에 2가지는 데드락이 생기지 않게 미연에 방지하는 방법

위로갈수록 더 강력한 방법.

밑에 2가지는 생기게 두는데 ,

3번 방법이 데드락이 있으면 recover 시키고 , 4번째는 데드락이 생겨도 시스템이 책임지지 않는방법

대부분 ignorance를 채택하고있다. 데드락이 생겨도 관여하지 않는다.

 

ignorance - 운영체제가 관여하지 않고 사람이 알아서 프로세스를 죽이던지 해결을 해야한다.

 

데드락은 자주 발생하는 상황이 아니기 때문에 이걸 방지하기 위해 오버헤드를 들이는게 

비효율적이기 때문이다.

 

Deadlock Prevention

 

데드락이 발생하는 4가지 조건 중 1개를 원천 차단해버린다

1. 자원이 필요할 경우 보유 자원은 모두 내려놓고 요청을 한다.

2. 어떤 자원을 기다리는 상황이면 , 이미 보유한 자원은 선점 할 수 있게 한다.

 

 

Deadlock Avoidance

프로세스가 시작될때 이 프로세스가 평생 쓸 자원을 미리 알고있다고 가정을 하고,

안전한 경우에만 할당을 해서 데드락을 피하는 방법

자원이 하나 밖에 없는 경우 데드락을 피해가는 방법

프로세스가 2개가 있고, 자원이 2개가 있는 상황

자원에서 프로세스로 가는 화살표는 , 자원이 프로세스에 할당된 상황

프로세스에서 자원으로 가는 화살표는 자원을 요청한 상태

 

점선은 이 프로세스가 적어도 한번은 이 자원을 사용할 것이다. 라는 뜻

 

cycle (데드락)이 생기지 않는 경우에만 자원을 할당한다.

 

항상 최악의 상황을 가정하고 데드락을 회피한다.

자원이 여러개인 경우 - 은행원 알고리즘

프로세스 5개,

자원이 3종류가 있다. 

인스턴스가 각각 10개 5개 7개 있다.

 

그림의 Max 가 예측을 한거다 이 프로세스는 평생 이 정도의 자원을 쓸 것이다.

전체 자원 인스턴스에서 현재 할당된 자원을 빼면 Available 만큼 나온다

이때 자원을 요청하면 

프로세스 1번으로 예를들면 추가 요청할 수 있는자원은 1 2 2 개 다

이게 현재 가용 (available) 에서 모두 충족할 수 있는지 본다.

그게 모두 충족이 가능하니까 요청하면 바로 주는 것 

, 근데 현재 available 로 need 가 충족하지 않으면 

줄 자원이 있더라도 자원을 주지 않는다. 

예를들어 프로세스 0 이 B 자원 2개를 요청했다면, available 에는 분명 2개의 자원을 줄 수 있게 남아있지만

Need 가 available 로 충족이 안되므로 자원을 할당하지 않는다.

 

avoidance 알고리즘은 프로세스가 자원을 최대한 쓸 양을 예측하게된다 

 

Deadlock Detection and Recovery

 

자원의 최대 사용량을 미리 알 필요 없다.

 

데드락이 있는지 확인방법

추가 요청하는게 없는 프로세스는 반납할거라고 낙관적으로 예측한다.

그럼 A 3 B 1 C 3 개 만큼의 가용용량이 있다고 가정한다.

이렇게 되면 프로세스1의 A 2 개 C 2개 를 이용할 수 있게된다.

데드락이 발생하지 않음 .! 이런식으로 예측을 한다.

 

만약 데드락이 발견되면?

 

크게 2가지 방법이 있다.

1. 데드락의 연류된 프로세스를 죽인다.

2. 데드락의 연류된 프로세스를 1개씩 죽여본다.

 

Deadlock Ignorance

 

데드락이 일어나든 말든 아무 일 안한다.

대부분의 운영체제가 이 방법을 사용