데드락

컨커런시 버그 (타이밍 버그)

발생할 수도 있고 아닐 수도 있음

 

종류

논 데드락 버그

원자성 위배

- 스레드들이 동시에 동작할 경우 문제가 됨

- 락으로 해결

 

오더링 문제

- 특정 스레드 이후에 실행되는게 보장되어야 문제가 없는 경우

- 조건변수나 세마포 사용

---

데드락 (교착 상태)

2개 이상의 스레드가 발생하지 않을 사건을 기다리게 되는 사건

 

4가지 조건을 모두 만족해야 발생

1. Mutual exclusion

2. Hold-and-Wait

3. No preemption for resource

4. Circular wait

 

데드락의 대처

1. 데드락 예방

2. 데드락 회피

3. 데드락 발견 및 회복

 

데드락 예방

1. Hold-and-Wait 없애기

모든 락을 한번에, 원자적으로 잡아야 함

-> 큰 락을 잡고 락1, 락2.. 를 잡을 수 있게하기

 

2. Preemption 하기

락을 못잡으면 다시 놔주기

* 트라이락: 못잡으면 놔줌

 

문제: 라이브락 발생 가능

 

3. 환형 대기 없애기

락을 잡는 순서를 적절하게 맞춰서 환형으로 대기하는 현상이 발생하지 않도록 해야 함

 

4. 상호 배제를 아예 안쓰기

락 프리 어프로치

원자성을 보장하면서 락을 안쓰는 방법..

-> 하드웨어 명령어를 사용

 

보통 Compare and Swap을 사용

 

단점: 쓸 수 있는 때가 제한적.. 락, 언락이 제네럴한 방법

 

데드락 회피

스케줄링을 잘 해서 데드락이 발생하지 않도록 함

 

	Thread 1	Thread 2	Thread 3	Thread 4
Lock 1	yes	yes	no	no
Lock 2	yes	yes	yes	no

홀드-앤-웨이트는 두 개 이상의 락을 잡아야 해당되는 문제

Thread1과 Thread2를 같은 CPU에 올리면 둘이 동시에 실행되지 않으니 회피 가능

 

** 그래도 스케줄링이 선점형이면 데드락은 발생 가능, 회피할 뿐이고 데드락이 아예 안되는게 아님

 

Banker's algorithm

은행원이 돈을 빌려주는 것과 비슷하게 동작

프리한 상태의 리소스를 가지고 모든 스레드를 종료시킬 수 있으면 세이프, 아니면 언세이프

 

갚을 수 있는 애한테 자원을 빌려주는 방식

 

데드락 발견 및 회복

데드락의 발생은 허용하나 발생하면 탐지하고 리커버리

 

자원 할당 그래프를 사용

자원          ->   프로세스 : 가짐

프로세스   ->           자원: 가지고 싶음

 

프로세스가 종료 가능하면 엣지를 지움

계속해서 엣지를 지우고 다 지우면 데드락이 없는 것

반면, 지울 수 없는 엣지가 있으면 데드락 탐지

 

보통 수행한 지 얼마 안된 걸 죽임(언두)

가장 최근이 언두할게 적을 것임

 

혹은 락을 가장 적게 가지고 있는 걸 죽임

undo 오버헤드가 가장 적을 만할 걸 골라서 죽임

---

데이터베이스는 기록자, 판독자 문제.. 여러가지 상황에서 컨커런시 문제는 고려됨

 

세가지 팁

1. 가능하면 심플

2. 문제가 안되면 내버려 두는 것이 맞다

3. 맵 리듀스 처럼 공유자원을 안쓰면 락도 안써도 됨 (OS는 어쩔 수 없이 해야되긴 한다)