[운영체제] Deadlock

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

교차상태(deadlock)

Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태

Resource: 하드웨어 자원과 소프트웨어 자원을 모두 포함

프로세스가 자원을 사용하는 절차

1) 자원을 요청

2) 자원을 획득

3) 자원을 사용

4) 자원을 반납

---

Mutual exclusion(상호배제): 자원을 한 번 얻으면 독자적으로 사용함. 가지고 있는 동안 공유하지 않음

No preemptoin(비선점): 자원을 가지고 있는 동안 자원을 빼앗기지 않음

Hold and wait(보유대기): 자원을 놓지 않고 기다림

Circular wait(순환대기): 서로가 가진 자원을 기다리면서 사이클을 형성

---

자원 -> 프로세스 : 자원이 프로세스에 속해있음.

프로세스 -> 자원 : 프로세스가 자원을 요청하고 있지만, 아직 획득하지 못한 상태

사각형 안의 점 : 자원 안의 인스턴스

---

그래프 속에 싸이클이사이클이 없으면 데드락이 아님. 화살표가 계속 이어져서 시작점으로 돌아오면 사이클이 존재

사이클이 존재하는 데 만약 자원 당 인스턴스가 하나밖에 없으면(점이 하나씩밖에 없다면) 사이클의 존재가 곧 deadlock을 의미함

하지만 만약 자원에 인스턴스가 여러 개 있다면 데드락일 수도 있고 아닐 수도 있음

 

오른쪽 그림은 R1과 R2가 모두 인스턴스가 두 개이고 P2와 P4는 싸이클에 포함되지 않기 때문에 자신들의 작업이 끝나면 자원 리소스를 반납하고 데드락이 해결됨. 즉 사이클이 존재하지만 데드락은 아닌 상태

---

위의 두 개는 데드락을 미연에 방지.

하지만 데드락은 빈번히 발생하는 이벤트가 아니기 때문에 데드락을 막기 위해 평소에도 데드락을 막기 위해 오버헤드를 두는 것이 그리 효율적이지 않기 때문에 많은 OS가 Deadlock Ignorance, 즉 데드락 이벤트를 책임지지 않는 방식을 채택함

---

- Deadlock Prevention: 데드락이 발생하는 4가지 원인 중 하나를 원천적으로 차단

1) Mutual Exclusion: 한 번에 하나의 프로세스만 사용할 수 있는 자원에 대해 발생하기 때문에 차단 불가능

2) Hold and wait: 자원을 기다려야하는 상황에서는 자원을 보유하고 있지 않으면 됨. 

방법 1_ 프로세스가 시작될 때, 프로세스가 평생에 필요한 모든 자원을 할당받게 만들어줌. 그리고 작업이 끝나면 그때 자원을 반납. 하지만 매 시점마다 필요로 하는 자원이 다른데 그걸 모두 잡고 있으면 자원 활용의 비효율성

방법 2_ 자원이 필요할 때 그때마다. 자원을 Hold 한 상태에서 다른 자원을 기다려야 해서 wait 한다면 이미 hold 하고 있는 자원도 뱉어낸 다음 기다리는 방식. 이러면 누군가는 필요한 자원을 얻고 데드락을 해소

3) No Preemption: 필요한 자원을 가져올 수 없기 때문에 데드락 발생. 프로세스가 한 번 가져가면 중간에 빼앗아올 수 없기 때문에 deadlock 발생. CPU, 메모리 등등은 타이머 등의 interruption을 통해 preemption이 가능하기 때문에 데드락 발생 x(state를 쉽게 save 하고 restore 할 수 있기 때문). 하지만 어떤 자원은 중간에 빼앗아오면 완전 엉망이 되어서 preemtion을 허용하지 않는 경우도 발생.

 4) Circular wait: 자원에 할당 순서를 정해놓고 정해진 순서대로만 자원을 할당

 

하지만 생기지도 않을 수 있는 deadlock을 prevention하기 위해 자원을 낭비하는 결과를 초래하기도 함

---

프로세스를 시작할 때, 그 프로세스가 평생에 쓸 자원을 모두 알고있다고 가정. 때문에 deadlock의 가능성이 조금이라도 있다면 프로세스가 요청한 자원에 여분이 있더라도 자원을 할당해주지 않음.

항상 SAFE한 상태를 유지. Safe 하다는 건, 여분 자원만 가지고도 작업을 끝낼 수 있는 프로세스만 해당.

자원의 인스턴스가 단 하나일 때

점선을 포함한 사이클이 형성되더라도 애초에 받아들이지 않음. 이렇게 하면 적어도 데드락은 생기지 않음. 여기서는 P2에게 R2를 주지 않음

Max: 프로세스가 평생에 걸쳐 필요한 자원

Need: 추가로 요청해야하는 양

 

Need가 Available로 처리가 가능할 때에만 자원을 할당해줌

만약 P0이 A자원 1개를 요청한다면 현재 여분이 있어서 줄 수는 있지만, 혹시 그다음에 A자원을 최대로 요청하면 가용 자원으로 그걸 충족시킬 수 없게 됨. 그 사이에 다른 프로세스들이 자원을 반납해서 P0이 필요한 자원을 모두 줄 수도 있지만, 이건 최선의 경우이고 최악의 경우로 데드락이 발생할 수 있기 때문에 P0에게 자원을 주지 않음. 최악의 경우로 데드락이 발생할 수 있다면 아예 원척적으로 자원을 할당하지 않는 방법이 Banker's algorithm

 

반면 P1의 경우에는 가용 자원을 전부 주는 최악의 상황에도 데드락이 걸리지 않기 때문에 자원 요청을 받아들임

 

이렇게 하면 데드락은 발생하지 않지만, 자원 활용에서 굉장히 비효율적임

---

 

Deadlock Detection and Recovery: 일단 데드락이 발생할 때 까지 기다린 다음, 데드락이 발생하면 그걸 찾아내서 recovery

Wait-for graph에서 싸이클을 찾는 데 걸리는 시간 -> n^2

사이클이 있는지 찾으려면 화살표를 따라가야 하는데, n개의 데이터라고 하면 최대 n-1개의 화살표가 존재. 모든 n개의 데이터들이 n-1개의 화살표를 가지고 있다면 n * (n-1) 개의 화살. 점근적으로 보면 n^2

자원의 instance가 하나일 때

역시 싸이클이 존재하면 데드락 발생. 

자원의 instance가 여러 개 일때

detection은 프로세스가 자원을 요청하면 그냥 주기 때문에 banker's처럼 데드락 각을 재지는 않음.

현재 Available한 자원이  0 0 0 이더라도, 자원을 요청하고 있지 않은 프로세스 P0과 P2이 각각 가지고 있는 자원을 반납할 것이라고 낙관적으로 가정해서(3 1 3) 자원을 요청하는 P1의 요청을 받고 자원을 할당. 그럼 P1도 자원을 받아 작업을 하고 반납할 것이라고 가정. 이렇게 프로세스들에게 받은 요청을 받아들이는 sequence가 존재한다면 데드락이 발생하지 않는다고 가정. 이 낙관적 sequence를 만족시키지 못한다면 데드락이 발생한 것으로 간주하고 detection

Recovery

1. 프로세스들을 없애는 방법

방법 1) 데드락관 연루된 프로세스들을 모두 사살

방법 2) 데드락에 연루된 프로세스들을 데드락이 없어질 때까지 하나씩 죽이면서 확인

 

2. 프로세스로부터 자원을 빼앗는 방법

프로세스 중 희생양을 찾아서 그 친구로부터 자원을 뺏어서 데드락을 해결함

문제 -> 특정 프로세스에게 자원을 빼앗았는데, 그 프로세스가 다시 자원을 요청해서 같은 패턴의 데드락이 반복되는 문제.  때문에 자원을 뺏는 패턴을 바꿔줌. 

Starvation: 비용 최소화를 위해 계속 자원을 빼앗기는 victim 프로세스가 반복될 경우 영영 자원을 할당받지 못함. 이 경우 프로세스가 자원을 몇 번 빼앗겼는지 cost factor에 rollback 횟수를 고려

---

데드락을 막는 과정도, 데드락 detection도 오버헤드가 발생하기 때문에 자원의 효율적 활용을 위해 데드락을 그냥 방치함. 데드락이 발생하면 사용자가 알아서 대처하는 방법