데드락(Deadlock)

: 둘 이상의 프로세스가 서로 각자 필요로하는 자원을 갖고 있고, 서로의 것을 원할 때 무한정 기다리는 현상

데드락 발생 조건

1. 상호 배제: 자원은 한번에 한 프로세스만 사용 할 수 있음
2. 점유 후 대기: 최소한 하나의 자원을 점유하고 있는 상태에서 다른 프로세스의 자원을 추가 점유하려는 프로세스가 존재
3. 비선점: 다른 프로세스의 자원은 강제로 뺏을 수 없음
4. 순환 대기: 순환형태의 자원 대기가 있음

데드락 해결 방법

데드락 예방 : 데드락 발생조건 하나를 제거해 해결

1. 상호 배제 제거: 여러 프로세스가 공유 자원 사용하도록
2. 점유 후 대기 제거 : 프로세스 실행전에 미리 필요한 모든 자원 할당을 마쳐 추가 점유를 제거.
   • 문제: 자원 과다 사용으로 인한 효율성, starvation, 무한 대기 등 문제가 있다.
3. 비선점 제거 : 선점 가능한 프로토콜을 만들어줌
   • 문제: 기존에 사용중이던 프로세스는 작업 내용을 잃을 수도 있다.
4. 순환대기 제거 : 자원에 고유번호 할당 후 오름차순으로 자원 요구하도록

데드락 회피 : 데드락 발생할 것 같으면 피해가기

• 은행원 알고리즘
  • 어떠한 프로세스가 자원 요구 시, 시스템은 자원 할당 후에도 안정 상태로 남아있게 되는지 사전에 검사해서 안정이면 할당, 아니면 자원 해지까지 대기
  • 최소 한 사람이 최대로 요구할 수 있는 자원을 알고, 미리 그것보다 많은 자원을 갖고 있어야 한다.

데드락 탐지 : 자원 할당 그래프를 통해 데드락 감지.

• 자원 요청 때마다 탐지 알고리즘을 실행, 그에 대한 오버헤드 존재
• 순환이 발생하면 데드락 발생하는 것이라고 결정.
  1. Union find
  2. DFS를 통해 visit했는지 탐지
  3. 토끼와 거북이(runner 매커니즘)

데드락 회복 : 데드락 발생한 1. 프로세스 종료하거나 2. 할당된 자원 해제를 통해 회복

• 종료방법
  • 데드락 프로세스 모두 중지 or 데드락 해결때 까지 하나씩 중지
• 자원 선점(해제)방법
  • 데드락 프로세스의 자원을 다른 프로세스에게 할당
  • 우선순위가 낮은 프로세스나 수행횟수 적은 것 부터

식사하는 철학자와 기아(Starvation)

• 데드락 발생조건의 네가지를 전부 만족하는 시나리오.
• 발생조건 중 하나를 제거하면 해결

과정

1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다.
2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 들 수 있을 때까지 생각하며 대기한다.
3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.
4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.
5. 다시 생각하다가 배고프면 1번으로 돌아간다.

Reference)

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/DeadLock.md

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%94

https://gameproyyj.tistory.com/157?category=875111

https://m.blog.naver.com/hirit808/221788147057