Deadlock(1)

Deadlocks

7강 학습목표

• 데드락이 무엇인지 알고 데드락에 빠지는 상황과 조건을 안다.
• 데드락을 예방, 회피하는 방법을 안다.

DeadLock

두개 이상의 Process들이 각각의 자원을 Hold한 상태에서 다른 Process의 자원을 받길 기다리는 상태.

Ex ) Semaphore A와 B가 1로 초기화 된 후

P0 -> Wait(A); Wait(B); / P1 -> Wait(B); Wait(A);

Bridge Crossing Example

차량이 하나밖에 통과할 수 없는 다리를 생각했을 때,

다리 = 자원

차량 = 프로세스

다리의 중간에서 차량이 만난 상황이 데드락 상황이다.

차를 뒤로 뺄 수 없는 상황이다 = 한번 할당된 자원은 반환되지 않는다(No preempt)

Starvation이 일어날 수 있다.

Deadlock Characterization

데드락은 다음과 같은 네가지 조건을 동시에 만족시켜야 발생한다.

1.Mutual Exclusion : 한 순간에 한 프로세스만 자원에 접근할 수 있다.

2.Hold and Wait : 프로세스가 하나의 자원을 갖고 있고, 다른 자원을 필요로 한다.

3.No preemption : No Interruptable, 자원은 그 자원을 사용하는 프로세스가 자발적으로 반납하기 전까지 접근이 불가능하다.

4.Circular Wait : 프로세스들이 서로 필요로 하는 자원과 갖고있는 자원이 꼬리를 물고 Closed Loop가 생성되어야 한다.

네가지 조건을 전부 만족해야 Deadlock이 발생 가능하다.

System Model

R = 자원 ex) CPU, 메모리 공간, I/O 디바이스 등…

W = 인스턴스, 자원 R은 한개 이상의 인스턴스W 를 갖는다.

프로세스는 자원을 사용하기 위해 다음과 같은 과정을 거친다.

요청(request) -> 사용(use) -> 반환(release)

Resource-Allocation Graph

프로세스와 자원간의 관계를 한눈에 표현하기 위한 그래프

Process = 동그라미로 표현

Resoures = 큰 네모로 표현

Instance = Resource안에 작은 네모로 표현

Request Edge = 동그라미(Process)에서 자원(Resource)로 화살표

Assignment Edge = 자원(Resource)에서 동그라미(Process)로 화살표

Resource Allocation Graph with A Deadlock

프로세스와 자원의 관계를 나타낸 자원 할당 그래프에서 Closed Loop가 생성될 경우 Deadlock의 가능성이 있다.

Closed Loop가 생성된 상황에서 다음과 같은 네 조건을 만족하면 Deadlock상황에 빠진 것이다.

• Mutual exclusion / Hold and Wait / No Preemption / Circular Wait

이 중 한가지라도 만족하지 않으면 Deadlock상황이 아니게 된다. EX) 강의에서는 Hold and Wait를 만족하지 않는 자원 할당 그래프를 보여준다.

Deadlock Example

 

No Deadlock Example

정리

Closed Loop가 없다 -> No Deadlock

Closed Loop가 있다 -> 자원당 인스턴스가 하나밖에 없다 -> Deadlock

Closed Loop가 있다 -> 자원당 인스턴스가 여러개다 -> Deadlock의 가능성이 있다.

네가지 조건을 만족해야만 한다.

Deadlock을 처리하는 방식

1. 절대 Deadlock에 빠지지 않도록 하는 방식.
2. Prevention : 원천봉쇄, Avoidance : 회피, 가까이 가지만 Deadlock 직전에 빠져나온다.
3. Deadlock탐지와 복구
4. Deadlock상태를 점검하고 Deadlock상태에 빠지면 복구한다.
5. Deadlock 무시많은 운영체제들이 채택하는 방식이다.
6. 위의 두 방법은 Overhead가 너무 크기 때문에 그냥 Deadlock을 무시하는 방법도 있다.

Deadlock Prevention

데드락에 빠지기 위한 네가지 조건 중 하나라도 만족시키지 않도록 하는 방법으로 Deadlock을 예방할 수 있다.

1.Mutual Exclusion 만족 X -> 공유하는 자원은 Hold하지 않는다. 공유하지 않는 자원만 Hold하도록 한다. Ex) 읽기 전용 파일같은 경우에는 상호배제 조건을 만족하지 않는다.

2.Hold and Wait 만족 X -> Hold하고 있는 자원이 없을때 만 요청할 수 있도록 한다.

• 프로세스 실행전에 필요한 모든 자원을 준비해주거나, 아무것도 없을 때에만 자원을 요청할 수 있도록 한다 -> 자원의 활용률이 낮아지고 기아의 가능성이 있다.

3.No Preemption 만족 X -> 모든 자원이 시작할 때 할당되지 않으면 자발적으로 갖고있는 자원을 전부 반환한다.

Preemptive한 자원은 프로세스가 기다리는 동안 List에 올라가고, 모든 자원이 할당되지 않으면 다시 처음부터 자원을 모으기 시작한다.

4.Circular Wait 만족 X -> 모든 자원에 번호를 부여하고 번호가 증가하는 자원만 요청할 수 있도록 한다.

Ex) 15번 자원을 가진 프로세스는 1번 자원을 요청할 수 없고, 15번 이상의 자원만 요청할 수 있다.

Deadlock Avoidance

Deadlock을 회피하기 위해서는 사전에 추가적인 정보가 있어야 한다.

가장 간단하고 효율적인 방법 : 미리 사용할 자원을 알고 있다. 주기적으로 자원 할당 상태를 확인한 뒤 결코 Circular-Wait 상태에 빠지지 않도록 한다.

자원 할당 상태는 사용가능한 자원, 할당된 자원, 그리고 프로세스의 최대 요구 자원의 수로 정의된다.

Safe State = Deadlock과 무관한 상태

프로세스에게 자원을 할당할 때, 시스템은 할당해도 시스템이 Safe State에 있는지 확인해야만 한다.

모든 프로세스의 Safe한 Sequence가 존재한다면 시스템이 Safe State에 있다는 것을 의미한다.

시스템이 Safe한 상태에 있으면 Deadlock이 발생할 수 없고

시스템이 Unsafe한 상태에 있으면 Deadlock이 발생할 가능성이 있다.

Avoidance는 시스템이 절대 Unsafe한 상태에 빠지지 않도록 하는 것이다.

자원 할당 그래프 알고리즘.

Claim Edge는 프로세스에서 자원으로 그어지는 점선의 화살표이며 프로세스가 자원을 필요로 할 수 있다는 것을 의미한다.

Claim Edge는 자원을 요청하게 되면 실선으로 바뀐다.

할당받게 되면 화살표의 방향이 바뀌고, 자원이 반환되면 다시 Claim Edge로 변하게 된다.

Claim Edge로 구성된 Closed Loop도 Unsafe한 상태이다.