운영체제 6장 Concurrency : Deadlock and Starvation




데드락 - 여러 프로세스가 지속적으로 기다려야 하는 상황
시스템 리소스에 대한 경쟁이나 통신중에 발생

여러 프로세스가 데드락이 된다는것은
다른 blocked process에 의해 triggered되는 이벤트를 기다리는 경우에 의해 데드락이 발생되었다고 함 (다른 프로세스가 뭔가 해주길 기다리는 상태)

parmanent 한 결과, 효율적인 해결책이 없다.


누군가 양보를 해서 차례대로 지나가는 것이 해결책




프로세스간에 충돌을 발생시키는 리소스는 크게 2가지
재사용 가능한 리소스 - 공유할수 없고 한번에 하나의 프로세스만 쓸수 있는 프로세서, IO, 메인메모리, 각종 디바이스, 통신장치, 세마포어 ...
소모하는 리소스 - 생성된다음 소모되는것, interrupt, 시그널, 메시지, information, IO 버퍼



서로 받기를 기다리는 상태 (상대가 해주길 기다림)




자원을 요구하는것을 화살표로 표시
할당된것은 반대방향으로 표시
점은 리소스의 instance




사이클을 이루고 있다면 deadlock 발생
 - 가장 간단한 해결법은 사이클을 끊는것



# deadlock의 발생 필요충분조건 (암기)

하나의 프로세스만이 리소스를 사용할수 있어야 한다(mutual exclusion)
프로세스는 resource allocation을 잡고 새로운 할당을 기다려야 한다
한번 자원이 할당되면, 잡고있는 프로세스로부터 뺏을수 없다
닫힌 체인이 만들어져서 한 프로세스가 잡고있는 자원을 다른 프로세스가 요구한다면 

이 경우 데드락이 발생할수 있다.
첫번째 경우는 당연하다(상호배제를 하다보니까 문제가 생긴것)



# deadlock 해결법
1. 앞에서 본 deadlock의 발생조건을 하나 막는것 - 가장 보수적 방법, 자원을 비효율적으로 쓰게
2. 새 자원을 할당시 데드락이 발생한다면 할당하지 않는것
3. 할당해놓고 데드락이 발생시 확인해서 제거하기 




데드락의 가능을 완전히 없애는것
간접적 방법 - 앞에서 본 3가지중 하나를 없애는것
직접적 방법 - circular wait를 없애는것



mututal exclusion을 없애는것은 불가능하다. 리소스의 consistency를 보장할수 없음 
hold and wait - 프로세스가 리소스를 잡고, 다른 리소스를 요구하는 상황이다. 이건 없앨수 있다.(reuseable 한 경우)


no preemption - preemption 하도록 할수 있다, 이제까지 하고 있던 것을 다시 돌려놓고(롤백해서) 다른 프로세스가 자원을 먼저 쓰게 해서
circular wait - 자원할당에 순서를 정해서 할당되도록 한다




avoidance - 조금 더 자유로운 방법, 데드락이 발생할지 확인하여 발생한다면 할당하지 않느것
미래의 어떤 자원을 요구할지 알고있어야 따져볼수 있다.



deadlock avoidance에는 두가지 방법이 있다
리소스를 할당을 거부하는
프로세스 자체를 시작 안하는



리소스 할당을 거부하는 것은, bankers algorithm 이라고 부른다
현재 시스템 자원할당 상태를 state라고 하고
safe state 에 머물도록 하는것 - 데드락을 발생시키지 않는 경우가 한가지라도 존재한다면
unsafe state는 그런 경우가 존재하지 않는 경우를 말함, 반드시 데드락이 발생한다는것




이 상태는 safe state임을 알수 있다







이 방법의 장점은
preemption이나 롤백이 필요없이 문제가 생길지 확인해보고 문제가 생길것 같다면 할당하지 않는 것이므로, 처음부터 할당하지 않는 deadlock prevention보다는 자유롭다 




제약점은
미리 자원을 몇개 쓸지 알아야 한다
자원에 한정되어 데드락을 피하기 위한 알고리즘이 돌기 때문에 프로세스간 synchronization 이나 communication이 없어야 하고 독립적으로 실행되는 프로세스여야 한다
자원의 개수가 고정되어 있어야 하고
어떤 프로세스도 자원을 잡고 종료되지 않아야 한다.



prevention 은 가장 보수적이고 리소스 접근에 있어서 제약이 많다, 효율 떨어짐
detection은 보다 자유로운 방법이다


deadlock detection
bankers 알고리즘을 실시간으로 돌려서 확인
장점 - 일단 자원을 할당하기 때문에 알고리즘이 간단
단점 - 데드락이 발생했는지 주기적으로 검토해야 한다, 발생시 recovery가 쉽지 않다, 다시 돌리는것도 비용이 들어간다



데드락 발견시 복구방법
모든 데드락된 프로세스 종료
중간중간에 체크포인트에 저장해야할 상태를 저장하다가 데드락 발생시 돌아가도록 하는것
해결될때까지 하나씩 프로세스를 없애는
데드락이 발생하지 않을때까지 자원을 빼앗는






디스크나 swap-space에는 데드락을 해결하는 해결책이 있다




# 식사하는 철학자 문제


프로세스는 철학자가 된다
식사를 위해서는 두개의 포크를 들어야 한다
어느 철학자도 deadlock, starvation 없이 식사하는 법은??


세마포어를 사용한것
이것은 데드락이 발생할수 있다
각자 왼쪽의것을 잡고 오른쪽것을 집으려고 하면... circular wait


다른 방법
아예 자리를 넷으로 제한한다
한명은 식사를 끝낼수 있고, 나머지 사람도 차례대로 식사가 가능하다
그러나 한 자리가 비워지기 때문에 자원이 낭비된다.



모니터를 이용해서 해결하는 방법
각 철학자가 생각하다가 잡는데 하나의 atomic한 operation을 만든것
집으려면 둘다 집고 아니면 둘다 못잡도록