P0가 먼저 수행됐다면 wait 시스템 콜을 통해 S라는 세마포어를 -1 하고 0이 된다. 근데 여기서 interrupt가 걸리고 P0의 상태가 ready가 되고 P1이 스케줄링되면 wait 통해서 Q 세마포어를 -1 하고 0이 된다. 그리고 wait S를 하려고 했으나 값이 0이기 때문에 여기서 wait 함 그러면서 P1의 상태가 waiting 된다. P0가 스케줄 되어서 실행되는데 wait Q를 하려고 했으나 0이기 때문에 wait을 한다. 그러면 깨어날 수가 없다. 서로 계속 기다림
P0와 P1은 deadlock 상태에 빠졌다.
Deadlock Characterization
데드락이 발생될 필요조건 4가지
A->B : A는 B의 충분조건, B는 A의 필요조건
위 4가지 조건이 만족이 되면 데드락에 빠질 가능성이 있다.(필요조건)
데드락이 발생되었다면 이 4가지 조건이 다 참이다.(충분조건)
M.E이 없으면 동기화 문제도 없고 데드락 문제도 발생하지 않는다.
hold and wait: 하나의 shared resource를 홀드한 상태에서 또 다른 shared resource 기다리는 일이 발생하면 데드락에 빠질 가능성이 있다. (밥 먹는 철학자에서 왼쪽 젓가락을 가지고 오른쪽 젓가락을 또 가지려고 기다리는 상태, 항상 데드락에 빠지는 것은 아니고 특정 타이밍에 의해서 발생) (자원이 2개가 필요할 때 왼쪽 젓가락을 홀드한 상태에서 오른쪽 젓가락을 wait 하는 상황이 존재하면 그게 hold and wait 조건을 만족하는 것)
No preemption: 왼쪽 젓가락을 집고 오른쪽 젓가락을 집으려고 봤더니 누가 쓰고 있음 그러면 들고 있는 상태로 기다리는 게 아니라 왼쪽 젓가락을 다시 내려놓을 수도 있음. 왼쪽 젓가락을 내려놓는다면 데드락이 발생하지 않는다. 근데 계속 들고 있으면 데드락에 빠질 가능성이 있다.(반납하는 게 preemption, 반납 안 하는 게 no preemption) (내가 뭔가를 홀드 했는데 실제로 그걸 쓰기 전에 다시 반납하는 것=preemption, 이렇게 되면 데드락이 발생하지 않는다.)
circular wait: 밥 먹는 철학자 원탁에서 서로가 서로를 기다리는 조건인 경우 데드락이 발생될 수 있다.
데드락을 발생시킬 4가지 필요조건 중에 어느 하나라도 만족하지 않으면 데드락이 발생하지 않는다.
4가지 조건 모두 만족 <= 데드락이면 (참)
4가지 조건중 하나라도 만족하지 않으면 => not 데드락 (참)
M.E가 아니게 알고리즘을 만들 수 없음, M.E가 이루어져야 synchronization 문제를 해결하는 건데 M.E가 없다는 것은 race condition이 없다고 하는 것과 똑같은 이야기니까 아예 문제가 발생하지 않는다. 이건 우리가 없앨 수 없는 문제임.
circular wait도 문제가 그렇게 주어지는 것이기 때문에 우리가 해결할 수 없다.
결국 세마포어를 한번 가졌다가 더 사용할 수 없으면 다시 반납하는 알고리즘을 만들거나(no preemption) 아니면 hold and wait(하나를 갖고 그다음 또 하나를 요청하도록 하지 말고 필요한 공유 자원이 여러 개라면 여러 개를 한 번에 갖게 끔)이 없도록 알고리즘을 만든다.
결국 hold and wait 조건을 만족하지 않도록 알고리즘을 만들면 데드락에 빠지지 않는다는 것이 보장된다. 그 방법이 deadlock prevention
Handling Deadlocks
데드락 처리방안 크게 4가지
deadlock prevention: 개발자가 하는 것. 데드락이 발생될 가능성을 원천 봉쇄, 이건 개발자가 알고리즘을 만들어야 함.
deadlock avoidance: 회피, 운영체제가 하는 것. shared resource를 프로세스나 스레드가 달라고 요청한다면 그때 주게 된다면 데드락에 빠질 수 있는지 알고리즘을 돌려서 확인을 한다. 그걸 알고 나서 운영체제가 shared resource를 스레드나 프로세스한테 할당하는 방식. 엄청난 오버헤드.
deadlock detection and recovery: 운영체제가 하는 것. 공유 자원을 달라고 하면 일단 준다. 그런데 주기적으로 받은 스레드나 프로세스가 데드락에 빠졌는지 안 빠졌는지 검사를 한다. 그리고 빠졌다면 빠지기 이전 상태로 복구를 한다. 엄청난 오버헤드
deadlock ignorance: 현재 운영체제가 사용하고 있는 방법. 아무것도 안 하는 것.
Ostrich: 낙타, 자기가 해결할 수 없는 상황이 오면 머리를 모래 속에 묻고 잊으려고 함
결국 할 수 있는 것은 deadlock prevention, 어떻게 원천적으로 봉쇄하냐면 데드락을 발생시킬 4가지 필요조건 중에 어느 하나라도 만족하지 않도록, 그 4가지 조건 중에 hold and wait이나 no preemption 이 안되도록 알고리즘을 만든다. 주로 hold and wait가 만족하지 않도록 해줘야 한다. (필요한 자원이 여러 개라면 그 여러 개를 한꺼번에 가지고 한꺼번에 반납하는 알고리즘을 만들면 데드락이 발생하지 않는다.)
