데드락 (deadlock, 교착상태)

DeadLock

두개 이상의 프로세스가 각 자원을 점유하고 있는 상태에서 서로의 자원을 요구하며, 상대 작업이 끝나기를 영원히 기다리는 상태

 

발생 필수 조건

1. 한번에 하나의 프로세스만 공유자원을 쓴다. (  일반 lock )

2. 자원하나를 가지고 있는 상태에서 또 다른 자원을 요구한다.

3. 내가 원한 또 다른 자원을 이미 선점한 프로세스가 나의 자원을 요구한다. (순환형태)

4. 강제 선점할 수 없다.

 

 

 

해결방법

예방

1. 공유를 허용하던가
2. 자원을 한번에 할당하던가. 또는 자원 점유가 없을 때만 자원 요청하던가
3. 선형 적인 자원 점유상태를 유지하던가
4. 강제 선점을 허용하던가

자원사용을 효율성을 떨어트림.

 

 

회피

안전한지 확인하고 자원을 할당한다.

*회피 시 요구조건

• 프로세스 수가 고정되어 있어야 한다.
• 자원의 종류와 수가 고정되어 있어야 한다.
• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

이러한 조건때문에 회피는 현실성이 부족하고, 자원 요청이 있을 때마다 회피 알고리즘을 사용하려면 성능저하가 크다.

 

사용하는 알고리즘은 2개가 있다.

 

1. 은행원 알고리즘

*자원 할당 결정전에 예상되는 모든 자원의 최대 할당량을 가지고 시뮬레이션을 하여 safe state에 들 수 있는지 여부를 검사하여 교착상태의 가능성을 미리 조사하는 알고리즘.

 

"적어도 하나의 프로세스에게 필요한 자원을 넘겨줄 만큼의 양을 보유하고 있어야 한다."

 

프로세스	최대 자원 요청	가지고 있는 자원	필요한 자원
P0	10	5	5
P1	4	2	2
P2	9	2	7

*시스템 자원은 총 12개 가정

1. 현재 남은 자원 12 - 9 = 3
2. (P1에 할당 가능) P1에 자원을 할당 3 - 2 = 1
3. P1 작업이 끝나 자원을 반납 1 + 4 = 5
4. (P0에 할당 가능) P0에 자원을 할당 5 - 5 = 0
5. P0 작업이 끝나 자원을 반납 0 + 10 = 10
6. (P2에 할당 가능) P2에 자원을 할당 10 - 7 = 3
7. P2 작업이 끝나 자원을 반납 3 + 9 = 12

P0 -> P0 -> P2 순으로 자원 할당 시 안전함.  <safe sequence : 교착 상태를 발생 시키지 않고 자원을 할당하는 순서>

 

 

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

*순환을 확인하여 회피하게 함. 

*예약 간선(점선) 으로 설정한 자원에 대해서만 자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당받는 방법

*프로세스가 어떤 자원을 사용 중이고 향후 어떤 자원을 사용 예정인지 그린 방향성 그래프

• 프로세스 시작 전에 모든 예약 간선들을 자원할당 그래프에 표시합니다.
• 프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 주기가 형성되지 않을 때에만 자원을 할당 받습니다.

할당 실패

 

 

 

 

상호 배제 : R1, R2
점유 대기 : P1, P3
비선점 : O
순환 대기 : O
=> 교착상태 X (P4가 R2를 해제하면 해결)

 

 

탐지 - 회복

교착상태가 탐지되었다면 회복 기법을 통해 교착상태를 복구.

지속적으로 교착 상태를 확인하므로 성능저하 발생. 호출빈도 조절 해야함.

1. 은행원 알고리즘으로 unsafe state 확인
2. 자원 할당 그래프로 순환 확인

호출주기 예)

• 자원을 요청했는데 즉시 할당되지 못하는 시점에 호출
• 주기적으로 일정 시간마다 호출
• cpu 이용률이 특정 값 이하로 떨어지는 시점에 호출

 

 

-회복-

교착상태에서 회복하는 방식

1. [프로세스 종료] <교착상태 프로세스 모두 종료, 교착상태 해결까지 하나씩 종료> - 재시작
2. [자원 선점] 교착상태 프로세스의 자원을 강제 빼앗아 다른 프로세스에게 할당.

자원 선점시 고려 사항)

1. 희생자 선택 (selection of a victim)
   • 최소의 피해를 줄 수 있는 프로세스를 선택합니다.
2. 롤백(rollback)
   • 희생자 선택된 프로세스를 문제 없던 이전 상태로 롤백해야 합니다.
   • 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작하는 것입니다.
3. 기아 상태(starvation)
   • 한 프로세스가 계속 희생하여 기아상태가 되는 것을 방지해야 합니다.
   • 한 가지 방법은 우선 순위를 사용하여 선점 될때마다 프로세스 우선순위를 높이는 것입니다.

 

 

출처

교착상태(Dead Lock) 해결 방법 (tistory.com)

[OS] 교착상태(Deadlock, 데드락)의 정의, 발생 조건, 해결 방법 :: 코딩 공부 일지 (tistory.com)