💀 Deadlock

교착상태

2개 이상의 프로세스가 서로의 작업이 끝나기를 기다려 영원히 기다리게 되는 현상

---

💣 발생 조건

상호 배제

한 번에 하나의 프로세스만이 공유자원을 사용할 수 있음

점유와 대기

프로세스가 공유자원을 가진 상태로 다른 공유자원을 원하여 기다리는 상태

비선점

공유자원이 할당된 프로세스를 다른 프로세스가 가로챌 수 없음

순환 대기

2개 이상의 프로세스들이 원형을 이루면서 대기하는 상태

---

💉 예방

상호 배제 부정

여러 프로세스가 동시에 공유자원을 사용

점유 대기 부정

실행 전에 필요한 모든 자원을 할당
자원이 점유되지 않은 상태에서 자원 요청을 받도록 함

비선점 부정

자원에 대한 선점을 허용

순환 대기 부정

자원 요구가 선형으로 요구되게 함

---

🏃‍♂ 회피

프로세스 수 고정
자원의 종류와 수 고정
프로세스가 요구하는 최대 자원 수 파악
프로세스가 자원 사용 후 반드시 반납

💰️ 은행원 알고리즘

CPU는 최소한 하나의 프로세스에게 할당해줄 자원을 항상 보유하고 있어야 한다.

수많은 연산이 수행되기에 사용하지 않는다.

데드락을 처리하지 않고 데드락 발생 시 종료 후 다시 수행한다.

---

🔍️ 탐지

탐지 알고리즘 활용

지속적인 확인으로
오버헤드 발생 가능

---

💊 회복

🧑 사용자 처리

교착상태에 속한 하나의 프로세스를 사용자가 강제 종료

🖥️ 시스템 처리

• 프로세스 중지
  교착상태에 속한 모든 프로세스 중지
  교착상태가 해결될 때까지 하나씩 중지

• 자원 선점
  교착상태가 해결될 때까지 자원 할당을 해제

---

🛣️ Non-blocking Algorithms

🚧 블로킹 동시성 알고리즘

요청된 동작이 수행될 수 없는 경우
스레드가 동작을 수행할 수 있을 때까지 대기

🛣️ 논-블로킹 동시성 알고리즘

요청된 동작이 수행될 수 없는 경우
스레드가 이를 요청 스레드에 통지

📌 Lock-free

시스템 전체 진행이 보장

다른 스레드의 작업에 관계없이 하나 이상의 스레드가 유한한 단계로 진행할 수 있음을 보장

기아현상 발생 가능

📌 Wait-free

Lock-Free 상태에서 스레드 진행도 보장

모든 스레드에 대해 제한된 대기 시간과 공정성을 보장

	독립적 논 블로킹	의존적 논-블로킹	의존적 블로킹
모든 메소드가 진행을 담당	Wait-free	Obstruction-free	Starvation-free
몇몇 메소드가 진행을 담당	Lock-free	?	Deadlock-free

Maurice Herlihy and Nir Shavit