Add deadlock

java-squid · 102092 · Nov 3, 2021 · Oct 10, 2021 · Oct 11, 2021 · Oct 11, 2021
commit 4a3dcee99b1168e2017f86e1c7bc930b70084e8f
diff --git a/operating-system/deadlock/han/README.md b/operating-system/deadlock/han/README.md
@@ -0,0 +1,125 @@
+# Deadlock이란?
+
+- 교착 상태
+- 프로세스나 스레드가, 어떤 특정 이벤트를 기다리고 있는데, 그 이벤트는 발생할 수 없는 상태에 놓여있음.
+  - 즉 쓸 데 없이, 기다리고 있는 상태를 의미하는듯.
+
+
+
+## 실제 시스템에서 교착 상태
+
+- Database (MySQL)
+
+  - **상호 거래 패턴**
+
+  ![image](https://user-images.githubusercontent.com/22140570/136698857-2e340bae-151d-47fa-85a1-c22c007c8f0e.png)
+
+  - 트랜잭션 1 은 A를 점유하고 있음., 트랜잭션 2는 B를 점유하고 있음.
+  - 이 상태에서 트랜잭션1 는 B에게 접근하려 함 (이미 트랜잭션 2가 점유하고 있는 상태)
+  - 그런데 트랜잭션 2은 A에 접근하려 함 (이미 트랜잭션 1이 점유하고 있는 상태임)
+  - 점유가 풀려야, 해당 데이터에 접근할 수 있는데, 현재 상태로 보아서, 점유가 풀릴 수가 없는 상태임. (교착 상태)
+
+
+
+## 교착 상태를 만족하기 위한 4가지 필요조건
+
+- 아래 4가지 조건은 만족하게 되면, 교착 상태에 빠지게 된다.
+
+
+
+### 상호 배제 조건
+
+- mutual exclusion condition
+- 한번에 프로세스 하나만 해당 자원을 사용할 수 있음.
+  - 다른 프로세스가 위 자원을 사용하려 하면, 기다려야 한다.
+
+
+
+### 점유와 대기 조건
+
+- hold and wait condition
+- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 위해 대기하는 프로세스가 존재.
+
+
+
+### 비 선점 조건
+
+- nopremption condition
+- 이미 할당된 자원을 강제로 뻈을수는 없음
+
+
+
+### 순환 대기 조건
+
+- circular wait conditon
+- 대기 프로세스의 집합이 순한 형태로 자원을 대기
+
+
+
+
+
+## 교착 상태 해결 방법
+
+### 예방
+
+- 위 4가지 발생 조건 중에, 하나라도 발생하지 않도록 하는 것.
+- 예를 들면 상호 배제 조건 의 경우, **여러 프로세스** 들이 해당 자원을 사용할 수 있도록 해주는 것.
+
+
+
+### 회피
+
+> *Safe sequence, Safe state*
+
+- 안전 상태?
+  - 프로세스들이 요청하는 모든 자원을, 교착 상태에 빠지지 않으면서 모두에게 자원을 할당해줄 수 있는 상태
+- 안전 순서?
+  - 특정 순서로 프로세스들에게 자원을 할당해줬더니, 교착 상태가 발생하지 않았음. 이러한 순서.
+- 불안전 상태?
+  - 안전 상태가 아닌 상태
+  - 교착 상태 발생 가능성이 있다.
+
+- 은행원 알고리즘
+
+  - 시스템을 안전 / 불안전 상태로 구분
+  - 불안전 상태이면, 할당할 자원을 고정, 프로세스 수도 고정, 제한된 시간안에 자원 반납등의 조건이 전제됨.
+
+- 회피 전략을 즉 자원을 요청할 때마다, 시스템의 안전 상태를 파악해야함 (오버헤드 심함)
+
+  - 이러한 점 때문에, 해당 전략을 사용하는 시스템은 거의 없다.
+
+
+
+### 탐지 및 복구
+
+- 교착 상태가 자주 발생한다면 사용.
+- 교착 상태는 **필요악**
+  - 왜?
+  - 교착 상태는 안 만들어지는게 좋지만, 교착 상태가 발생할 수 없는 환경을 만들어 버린다면, 할당된 자원을 효율적으로 사용하는 것은 불가능한 일이 됨.
+- 탐지
+  - Allocation, Request, Available 
+  - **순환 대기 조건**이 존재하는 지 탐지함 (시스템의 자원 상태를 확인함)
+  - 탐지 알고리즘을 사용..해서 오버헤드 존재
+
+- 복구
+  - 순환 대기를 깨서, 교착 상태로 부터 회복하도록 함.
+  - 순환 대기에 포함된 프로세스의 제어권을 빼고 롤백.. 혹은 순환 대기가 깨질 때까지 프로세스 종료
+  - 어떤 프로세스를 깰까?
+    - 시스템마다 다른 기준으로 우선 순위
+    - MySQL의 경우, 트랜잭션의 크기가 가장 작은..
+
+### 무시
+
+- 교착 상태가 드물게 발생한다면 이 방법을 사용
+- 드물게 발생하는데, 굳이 교착 상태 해결 비용을 미리 지불할 필요는 없을듯.
+- 즉 교착 상태가 발생했다? 그러면 사용자가 원인이 되는 프로세스, 스레드를 죽이는 방법을 택함.
+
+
+
+# 참고
+
+- https://www.youtube.com/watch?v=FXzBRD3CPlQ
+
+- https://chanhuiseok.github.io/posts/cs-2/
+- http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788993712476
+