운영체제7 Deadlock

안녕하세요. 옆집 컴공생입니다. 오늘은 Deadlock 에 대해 배워 볼거에요. 

저번 시간에는 하드웨어와 소프트웨어의 프로세스 동기화에 배워보았습니다. 

 

 

https://com24everyday.tistory.com/205

운영체제6 Process Synchronizaiton

 

자 그럼 오늘도 힘을 내서 배워보도록 하겠습니다. 

주요 내용은 다음과 같습니다. 

 

• System Model
• Deadlock Characterization
• Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance

 

 

---

System Model

 

각 프로세스가 리소스를 사용하기 위해서는 다음과 같은 과정을 거쳐야합니다. 

1. request 요청

2. use 사용

3. release 권한 해제

 

 

 

Deadlock Characterization

Deadlock 은 다음과 같은 네가지 상황을 충족시켜야 발생을 하게 됩니다. 

 

1. Mutual exclusion : 오직 하나의 프로세스가 resource를 사용할 수 있게 해야함
2. Hold and wait : 자원을 점유한 채 다른 프로세스의 자원을 기다림
3. No preemption : 자원을 선점을 할 수 없음. 선점이란 자원을 점유한 프로세스가 있을 때 그 자원을 선점할 수 없음 -> 선점하면 Deadlock이 발생하지 않음 
4. Circular wait : 순환 대기, 대기하고 있는 자원이 P0,P1,..Pn 이 있을 때  P0-> P1, P1 -> P2 ,.... Pn -> P0 의 자원을 원할 때 순환 대기 상태 발생  

즉 Deadlock 상황에서 프로세스는 절대 실행을 끝낼 수가 없습니다. 자원들이 서로 물려있기 때문입니다. 

 

 

 

Resource-Allocation Graph(자원 할당 그래프) 

 

P 집합 - 프로세스

R 집합 - 리소스 

 

request edge(요청 edge) - Pi -> Rj 

프로세스 Pi 가 리소스 Rj 에게 자원 할당 요청 

 

assignment edge(할당 edge) Rj -> Pi 

리소스 Rj 가 프로세스 Pi 에게 리소스 할당  

 

프로세스와 리소스는 각각 다음과 같이 표현 

 

 

Example of a Resource Allocation Graph 

 

예시를 한 번 살펴 보겠습니다.

프로세스 P1 , 현재 R2의 한 인스턴스 점유 중 R1 에 인스터스 요청하며 대기 

프로세스 P2 , R1와 R2 점유중 ,R3 에 인스턴스 하나 기다림

프로세스 P3, R3 점유중

 

 

Example of a Resource Allocation Graph With a Deadlock

 

 

이 상황에서는 딱 봐도 사이클이 존재함을 알 수 있습니다.

P1 ->R1 -> P2 -> R3 ->  P3 -> R2 -> P1

P2 -> R3  -> P3 -> R2 -> P2 

 

- P1,P2,P3 는 교착 상태

- P2 는 P3 이 점유하는 R3 기다리고 P3 는 P2 가 점유하는 R2를 기다리고 있음

 

각 프로세스는 Hold and wait 를 하고 있고 No preemption 이며 사이클 형태로 Circular wait입니다.

 

 

 

 

Graph with a cycle but No Deadlock

위 그림은 사이클이 존재하지만 Deadlock 이 없습니다. 

P1 -> R1 -> P3 -> R2 -> R1

 

이는 P3 가 R2 를 방출 할 수 있기 때문입니다. -> Release 되는 해당 R2는 P3 에게 할당되어 사용하고 CYCLE 이 사라지게 됩니다. 

 

 

 

즉 그래프는 사이클이 없으면 -> 데드락 무조건 없음

사이클 있으면 -> 데드락 일수도 아닐 수도 있음

입니다. 

 

---

Methods for Handling Deadlocks 

 

데드락을 다루는 데는 여러가지 방법이 있습니다. 

• Prevent Deadlock : 처음부터 안 생기도록
• Avoid Deadlock : 데드락을 동적으로 리소스 관리를 잘함으로써
• Detect Deadlock : 데드락을 해결 

그럼 Prevent Deadlock 에 대해 보겠습니다. 

 

 

Deadlock 을 예방할 수 있을까요?

 

다음에 관해 생각을 해 보아야 합니다. 

1. Mutual Exclusion 을 없앨 수 있나
   • 시스템 설계시 사용 안 할 수 없음 ( 공유 변수의 일관성 유지 필수이기 때문)
2. Hold and Wait(점유대기) 에 대한 Deadlock 발생 가능성 없애기
   • 프로세스가 자신이 사용할 모든 자원을 한꺼번에 요청하는 전략 -> 없앨 수 있음 ,But 성능저하, 비효율적
   • 즉 필요한 자원 중 하나라도 할당 받을 수 없는 상호아에서는 다른 자원을 Hold 하지 않음
3. No Preemption(비선점) 에 의한 Deadlock 발생 가능성 없애기
   • 만약 자원을 점유한 프로세스가 다른 자원을 요청 때, 할당 받을 수 없다면 일단 자신이 점유한 자원 반납, 후 반납한 자원과 새로 원하는 자원을 다시 요청
   • 상황에 따라 한 프로세스가 다른 프로세스 점유한 자원 원하면 강제로 그 프로세스의 자원을 강제 반납 시키고 원하는 프로세스에 할당(선점 허용)
4. Circular Wait  
   • linear ordering 하면 됨

 

 

 

좀 현실적인 방안으로는 Deadlock Avoidance 가 있습니다. 이는 위 1,2,3 조건들을 허용하고 자원을 할당할때 Deadlock 상황으로 진행하지 않도록 합니다. 대신 Circular Wait 상황을 피하는 겁니다. 

 

주요 두가지 방법

1. 프로세스 자원할당 거부(Resource Allocation Denial)수행 중인 프로세스의 추가적 자원 할당이 데드락을 발생하면 자원 할당 안함
2. 프로세스 시작 거부(Process Initiation Denial) 
   • 프로세스 시작할때 요구하는 자원 할당이 데드락 발생 가능성 있으면 시작 안함

 

 

프로세스 자원할당 거부(Resource Allocation Denial)

 

이와 관련된 유명한 알고리즘인 'banker's algorithm(은행원 알고리즘)'에 대해 배워보겠습니다.  

 

시스템 상태(System state) : 리소스가 프로세스들에게 자원을 어떻게 할당하고 줄 수 있는지 관계를 의미

안전한 상태(Safe state) : 데드락이 발생하지 않도록 프로세스에게 자원을 할당

 

 

다음을 보겠습니다. Initial state 입니다.

R은 리소스고 P는 프로세스입니다. 할당행렬은 자원이 할당된 상황입니다. C-A 제일 오른쪽 행렬은 Pi에게 더 필요한 자원입니다. P1의 R1은 C 에서 3개를 요구했지만 A에서 1개가 할당되었기 때문에 2개가 더 필요한 것 입니다. 

Available vector V는 더 사용할 수 있는 자원 벡터입니다. 

 

여기서 P1은 C-A 를 봤을 때 각각 (2,2,2)를 요구하고 있습니다. 하지만 현 가용 벡터가 (0 , 1, 1) 이기 때문에 P1은 수행이 완료가 불가능한 것입니다. 

P2는 (0,0,1) 을 요구하는데 이는 (0,1,1) 에서 충족시킬 수 있기 땜누에 실행할 수 있습니다. 이때 P2가 완료가 되면 P2는 자기에게 할당된 모든 리소스를 반납합니다. 이는 (6,1,3)을 반납하기 때문에 가용 자원은 (6,2,3)이 될 겁니다.  

 

 

->P2가 실행이 되고 나면 Safe State 가 될 수 있습니다.

 

 

이제는 P1의 자원 요구도 들어줄 수 있게 되었습니다. 

 

다음은 P1이 실행이 되고 난 뒤의 모습입니다. 

 

이처럼 자원을 할당시 계속 safe state 이 유지가 되면 deadlock 이 발생하지 않습니다. 

이것이 Dijkstra 가 제안한 "자원할당거부방법(Resource Allocation Denial)" 입니다.

 

정리를 하자면 프로세스가 자원 할당 요청시 결과가 시스템의 상태를 계속 안전 상태로 유지할 수 있는지를 먼저 파악하여 할당 여부를 결정하는 겁니다.

 

 

 

또 다른 예시를 확인해보겠습니다.

초기 상태 입니다.

A의 R1을 다음과 같이 바꿔줍니다. 

R1과 R3가 추가되었습니다. 

여기서 V를 보면 C-A 에서 어떤 요구도 들어주지 못합니다. 그러면 수행을 완료하지 못하는 상태가 되는 겁니다. 

Unsafe state 입니다. 

 

 

 

---

챕터 7 Deadlock 이 끝났습니다.