운영체제 - 병행제어(10)
OS를 공부하면서 정리를 한 내용들 입니다.
데드락의 처리방법 네 가지중 디텍션 앤 리커버리, 이그노란스에 대해 알아봅니다.
앞서 배웠던 Deadlock Prevention과 Deadlock Avoidance는 Deadlock이 안 생기게 하는 방법이었습니다.
Deadlock Detection and Recovery
- Deadlock이 발생은 허용하되, 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
Deadlock이 자주 생기는 상황도 아니고, 굳이 자원이 여유가 있는데도 막음으로써 여유있는 자원을 안쓰는 것은
비효율적으로 동작하기 때문에, 여유자원이 있으면 무조건 요청을 받아들여서 자원을 할당합니다.
대신, 이렇게 동작했을 때 언젠가는 Deadlock이 생길 수 있습니다.
발생시 시스템이 느려지거나 특정 프로세스가 동작을 안하거나 할때 detection을하고, recovery합니다.
Deadlock Detection
Resource type 당 single instance인 경우
* 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미합니다.
Resoucre type 당 multiple instance인 경우
* Banker's algorithm과 유사한 방법을 활용합니다.
Wait for graph 알고리즘
Resource type 당 single instance인 경우
Wait for graph<
* 자원 할당 그래프의 변형
* 프로세스만으로 node 구성
* Pi가 가지고 있는 자원을 Pk가 기다리는 경우
Algorithm
* Wait for graph에 사이클이 존재하는지를 주기적으로 조사
Resource type 당 single instance인 경우
(a) 그림을 보았을 때 왼쪽 하단의 삼각형에 사이클이 있습니다.
Deadlock이 발생하게 됩니다.
또 찌그러진 사각형? 의 모양으로도 사이클이 있어서 Deadlock이 발생합니다.
(b)는 (a)를 조금 더 간단하게 만든 것입니다.
(a)에서 프로세스와 자원이 있을 때, 자원을 빼버리고 프로세스에서 프로세스로 가는 그래프로 만들 수 있습니다.
이것을 Wait for graph라고 합니다.
이러한 그래프를 찾아서 사이클을 찾으면 조금 더 빨리 찾을 수 있기 때문에
Deadlock이 발생하는지를 빠르게 확인 할 수 있습니다.
Resoucre type 당 multiple instance인 경우
이렇게 Deadlock이 있는 것을 확인했으면 Recovery를 합니다.
Recovery
Process termination
* Abort all deadlocked processes(데드락이 연루된 모든 프로세스를 죽이는 법)
* Abort one process at a time until the deadlock cycle is eliminated(데드락이 연루된 사라질 때 까지 하나씩 프로세스를 죽이는 법)
Recourse Preemption
* 비용을 최소화할 victim의 선정
* safe state로 rollback하여 process를 restart
* starvation 문제
Deadlock Ignorance
Deadlock이 일어나지 않는다고 생각하고 조치를 하지 않습니다.
- 매우 드물게 발생하는 현상이므로, 조치 자체가 더 큰 overhead일 수 있습니다.
- 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후
직접 process를 죽이는 등의 방법으로 대처합니다. - UNIX, Windows 등 대부분의 범용 OS가 채택됩니다.
Deadlock은 운영체제에서 아주 고전적인 문제 중 하나입니다.
아이러니하게도 현대의 범용 OS들은 이 방법을 채택하고 있습니다.
Deadlock이 발생하면 동작을 안하거나, 시스템이 정지된 느낌이 들거나 사용자가 답답한 경우가 발생할 수 있습니다.
이 경우 사용자가 알아서 프로세스를 죽이던지, 전원을 끄던지 하는 방식으로 처리를 하는 겁니다.
-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의