Deadlock이란? (교착상태)

같은 열의 차들은 일련의 프로세스라고 할 때, 서로 상대의 차로를 내어놓으라고 대치중인 상태

• 문제 : 자원을 아무도 사용하지 못한 채, 진행이 안되는 상태
• 이 때의 자원 : HW, SW를 포괄 (I/O device, CPU cycle, memory 공간, 세마포어)
• 자원 사용 절차 : 요청()

Deadlock은 언제 생길까?

1. 상호배제 :
2. 비선점 : 이미 할당된 자원을 다른 프로세스가 뺏을 수 없음
3. 점유대기 : 자원을 점유한 채로 waiting
4. 순환대기 : cycle 형성된 상태

자원할당 그래프

Deadlock 예방과 해결

1. Deadlock Prevention (방지)
2. Deadlock Avoidance (방지)
3. Deadlock Detection and Recovery (처리)
4. Deadlock Ignorance (처리)

1. Deadlock Prevention

1-1. 상호배제 방지
1-2. 점유대기 방지
: 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 합니다.
1-3. 비선점 조건 방지
1-4. 순환대기 방지

위 네가지 만족 못 하게 함

2. Deadlock Avoidance

자원 요청의 부가적인 정보를 이용해
프로세스가 시작할 때 프로세스가 최대로 필요한 자원의 양을 declare.

프로세스가 자원 요청을 할 때 데드락 가능성이 있으면 요청을 받아들이지 않고, safe면 요청을 받아들임.

자원 개수에 따라

2-1 .자원당 인스턴스가 하나인 경우에는 그래프를 이용해 deadlock avoidance

2-2. 여러개라면 뱅커스 알고리즘을 이용

• 첫 번째 네모 : 현재 할당된 양
• 두 번째 네모 : 평생에 자원을 최대로 쓸 때 사용하는 양, (declare)
• 세 번째 네모 : 현재 가용 자원
• 네 번째 네모 : (2네모-1네모) 두 개의 차, 앞으로 최악의 경우 이만큼 더 필요할 수 있다.
  프로세스가 딱 들어올 때, 네번째 네모의 정보를 확인하고 가용 자원이랑 비교해서 수용할 지 말 지 결정

끝까지 어떤 sequence가 현재의 가용자원으로 처리가 된다면, safe로 판단한다. deadlock avoidance는 safe를 항상 유지하도록 한다.

• sequence : P1 P2 , , , Pn
• unsafe != deadlock

3. Deadlock Detection and Recovery

3-1. Deadlock Detection

상황이 이상하다? => deadlock detection
detection : 그래프로 사이클 찾거나, 알고리즘으로 하거나 (후자가 더 좋음)

• single => cycle 찾는 그래프
  

  • 오른쪽은 왼쪽을 간결하게 표현한 것 : 자원을 빼버리고, 프로세스 간의 관계만 남김

• multiple instance의 경우
  (single에서도 쓸 수 있긴 함)

  

3-2. Deadlock Recovery

1. process terminaion 종료
   • 연루된 모든 프로세스를 kill
   • 한 번에 하나씩 kill, cycle이 깨질 때까지
2. resource preemption 자원 선점
   • 비용 최소화할 victom 선정
   • 다만, 비용 뿐 아니라 프로세스별로 rollback 횟수도 고려해서 기아현상이 일어나지 않도록 해야 함

4. Deadlock Ignorance (처리)

Deadlock이 일어나거나~ 말거나~

일어나면, 사용자가 알아서 대처하고 OS는 🐶무시

Quiz

문제 출처

```
1. 2개 이상의 프로세스가 서로 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 무엇이라 하는가?

2. 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 나타내는 방향성이 있는 그래프를 무엇이라 하는가?  

3. 네 가지 교착 상태 필요조건에 대해 설명하시오.

4. 교착 상태 해결 방법 중, 교착 상태를 유발하는 네 가지 조건을 무력화하는 방법은 무엇인가?

5. 교착 상태 해결 방법 중, 교착 상태가 발생하지 않는 수준으로 자원을 할당하는 방법은 무엇인가? 

6. 교착 상태 해결 방법 중, 자원 할당 그래프를 사용하여 교착 상태를 발견하는 방법은 무엇인가? 

7. 교착 상태 해결 방법 중, 타임아웃을 이용하여 해결하는 방법은 무엇인가? 

8. 교착 상태 해결 방법 중, 은행원 알고리즘을 사용하여 해결하는 방법은 무엇인가?

9. 교착 상태 해결 방법 중, 모든 자원에 번호를 부여하고 낮은 번호의 자원을 사용할 수 없도록 하는 방법은 무엇인가?

10. 교착상태 해결 방법 중, 프로세스가 시작 초기에 자신을 이용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납하는 방법은 무엇인가?

11. 교착 상태 해결 방법 중, 교착상태가 검출되면 교착상태를 일으킨 모든 프로세스를 종료하는 방법은 무엇인가?

12. 자원 할당 그래프에서 무엇이 발견되면 교착상태라고 판단할 수 있는가?

___

1. 교착 상태 해결 방법 중 프로세스가 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납하는 방법이 있다. 이 방법의 단점을 설명하시오.

  필요한 모든 자원을 미리 파악하기 어렵다.
  자원 사용 효율성이 떨어진다.
  나중에 필요한 자원까지 한 번에 점유해야하기 때문에 당장 필요한 프로세스가 자원을 활용하지 못하는 일이 발생한다.
  배치 시스템 처럼 동작하게 된다.

  필요한 자원을 모두 점유한 프로세스가 작업을 끝내야 그 다음 작업이 실행될 수 있다.
  필요 자원이 많은 프로세스가 필요 자원이 적은 프로세스에 비해 불리하다. 이는 자원 사용의 공평성에 위배된다.



2. 교착 상태 회피 방법인 은행원 알고리즘의 단점을 설명하시오.

	실제로 교착 상태가 발생하지 않는데도 교착 상태가 발생할 것으로 판단해 자원 사용을 제약한다. 모든 프로세스가 자신이 사용할 자원을 미리 선언해야 한다.


3. 교착 상태 검출 시 타임아웃을 이용하는 방법의 장단점을 설명하시오.

	자원 할당 그래프보다 가볍다.
  	자원 할당 그래프를 사용하려면 자원을 요구하고 할당할 때 마다 갱신해야 하고 이를 유지하는데 드는 추가적인 오버헤드가 존재한다. 분산 시스템의 경우 네트워크 문제인지, 일반적인 처리의 지연인지, 교착 상태인지 판단하기 어렵다.

	따라서 교착 상태가 아닌데도 프로세스를 강제 종료할 위험이 있다.
```

참고
https://chanhuiseok.github.io/posts/cs-2/
https://sangminlog.tistory.com/entry/process-synchronization