Dead Lock의 개념과 조건

개념

• 교착상태
• 둘 이상의 프로세스, 심하면 운영체제 자체도 함께 멈추는 현상

조건

4가지 조건을 모두 만족하면 교착상태 발생
1. 상호 배제 Mutual exclusion
2. 점유 상태로 대기 Hold and wait
3. 선점 불가 No preemption
4. 순환성 대기 Circular wait

상호 배제 Mutual exclusion

• 자원 자체는 여러 프로그램이 동시에 사용(점유)할 수 없다.
• 상호 배체 자체를 없애기는 불가능
• ex. 연산 결과를 저장하는 변수를 동시에 건드리면 위험

점유 상태로 대기 Hold and wait

• 자원을 점유한 상태로 다른 자원 기다림.
• 여러 자원을 동시에 점유하도록 하거나, 기다려야하는 자원을 할당받으려면 다른 자원을 반환하도록 하기
• ex. skype는 마이크와 카메라를 사용해야 함. 마이크는 점유했지만, 다른 카메라 앱이 카메라를 점유하고 있어서 대기. -> 녹음기는 마이크를 못 쓰게 되니 skype 와 마이크 모두 사용 불가

선점 불가 No preemption

• 다른 프로세스가 자원을 뺏어올 방법이 없음.
• 우선 순위 선점을 가능하게 하면 해결
  • 녹음기의 우선순위를 높게 해서 마이크를 뺏어가거나, skype의 우선순위를 높게해서 카메라 앱으로부터 카메라를 뺏어가거나

순환성 대기 Circular wait

• 대기가 꼬리를 물어서 순환하게 되는 경우. 대기하는 연결 고리를 타고 올라가면 자신이 나오므로 해결하지 못하게 됨.
• 자원에 우선순위를 매기는 등 방식으로 해결

벗어나는 방법

예방 Prevention

• 교착이 일어날 상황 자체를 방지

회피 Avoidance

은행원 알고리즘

• OS가 데드락에 빠질 가능성을 판단하고, 데드락 가능성이 없다고 판단하면 자원 할당

Wait-Die 기법

• 프로세스 A가 보유한 자원을 프로세스 B가 요청하는 경우
  • 프로세스 B가 프로세스 A보다 적은 타임스탬프를 가지는 경우에만 자원 점유를 위한 대기만 허용.
  • 그렇지 않으면 프로세스 B는 롤백
  • 대기하는 프로세스가 작은 타임스탬프 보유

Wound-Wait 기법

• 프로세스 A가 보유한 자원을 프로세스 B가 요청하는 경우
  • 프로세스 B가 프로세스 A보다 큰 타임스탬프를 가지는 경우에만 자원 점유를 위한 대기가 허용
  • 그렇지 않으면 프로세스 B는 롤백
  • 대기하는 프로세스가 큰 타임스탬프 보유

타임스탬프 : 프로세스가 시작되고 종료되는 시간

탐지 Detection

• 자원할당 그래프 알고리즘 ( 그래프를 통해 교착상태 발생 가능성 탐지 )

복구 Recovery

• 교착 상태인 프로세스 종료