운영체제(7) Deadlock

  

1. Define Dependencies

 

[프로세스들이 Lock을 얻기 위해 요청한] 자원들의 의존성 관계.
즉 프로세스가 어떤 자원을 요청할 때 그 자원이 이미 다른 프로세스에 의해 사용 중이라면,
해당 프로세스는 그 자원을 사용하기 위해 먼저 그 자원을 소유한 프로세스가 완료될 때까지 대기한다.
-> 이러한 의존성 관계들이 꼬이게 되면 데드락이 발생할 수 있다. 
-> 프로세스 A, B가 각각 자원 X와 Y를 요청하고 A는 X를, B는 Y를 소유하고 있다면
    서로의 자원을 사용하기 위해 두 프로세스 모두 대기하는 상황이 발생한다. 
-> OS에서는 데드락을 예방하기 위해 Lock을 얻는 순서나 우선순위를 지정, Lock 강제 해제 등을 할 수 있다. 
 
 

2. Deadlock

 
(system resource를 경쟁하거나, 서로 통신하는) 일련의 프로세스를 영구적으로 blocking한다. 
프로세스 집합이 교착 상태가 되는 현상.
-> Permanent, No efficient solution.

윗 그림 (b)의 교착 상태 상황을 나타낸 그림이다. 프로세스와 자원의 순환 체인이 있어 교착 상태가 발생한다.

 
<Dining-Philosophers Problem>
철학자 5명이 원형 식탁에 둘러앉아 고뇌하다가, 밥을 먹는다. 그들의 양쪽엔 젓가락이 한 짝씩 놓여 있다.
1. 왼쪽 젓가락부터 집어든다. 옆자리 사람이 사용 중이라면 그가 내려놓을 때까지 고뇌하며 기다린다.
2. 왼쪽 젓가락을 들었으면, 오른쪽 젓가락도 든다. 들 수 없다면 마찬가지로 기다린다.
3. 두 젓가락을 모두 들었다면 일정 시간 동안 식사를 한다. 
4. 식사를 마쳤으면 오른쪽 젓가락을 먼저 내려놓고, 왼쪽 젓가락을 내려놓는다. 
5. 다시 고뇌하다가 배고프면 이 행동을 반복한다. 

 
Deadlock(교착 상태)의 대표적인 예시이다. 
-> 만일 모든 철학자가 배고픔을 느끼고 왼쪽 젓가락을 동시에 집어든다면? 모두가 영원히 식사 불가.
    2번 상태에서 평생 멈추게 된다. -> Starvation(기아 현상)으로 아사한다. 
 
<Examples of Resource allocation graphs>

(a) : 프로세스에서 자원으로 향하는 Graph edge, 요청하였으나 아직 부여되지 않은 자원을 나타낸다. 
(b) : 재사용 가능한 자원의 node(점)에서 프로세스로 향하는 Graph edge, 프로세스가 생산자임을 나타낸다. 
(c) : 교착 상태의 예시를 보여준다. 
(d) : 각 Resource가 여러 단위를 사용할 수 있기 때문에 교착 상태가 발생하지 않는다. 
 
 

3. Deadlock Conditions

 
(1) Mutual Exclusion : 상호 베타
한 번에 하나의 프로세스만 리소스를 사용할 수 있다. 
각각의 스레드는 뮤텍스에서 lock되어야 한다. 한 번에 하나의 스레드만 잠글 수 있다. 
(ex) Dining-Philosophers Problem : 젓가락은 한 번에 한 철학자만 사용할 수 있다. 
 
(2) Hold and Wait : 보류 및 대기
프로세스는 다른 리소스의 할당을 기다리는 동안, 할당된 리소스를 유지할 수 있다. 
각 스레드가 뮤텍스를 잠그면 두 번째 뮤텍스의 잠금을 시도한다. (첫번째 잠금 먼저)
(ex) Dining-Philosophers Problem : 집어든 젓가락은 계속 집은 채로 반대쪽 젓가락을 기다린다. 
 
(3) Circular Waiting : 순환 대기
각 프로세스가 체인의 다음 프로세스에 필요한 최소 하나의 리소스를 보유. 폐쇄적인 프로세스 체인 존재.
스레드1과 스레드2는 서로 다른 리소스에서 대기하고 있다. 
(ex) Dining-Philosophers Problem : 모든 철학자들이 자기 오른쪽 철학자가 젓가락을 놓기를 기다린다. 
 
(4) No Preemption : 선점없음
리소스를 보유하는 프로세서에서 리소스를 강제로 제거할 수 없다. 
두 번째 Lock 호출이 차단되면 두 스레드 모두 뮤텍스에서 잠금을 해제하지 않는다. 
(ex) Dining-Philosophers Problem : 이미 누군가가 집어든 젓가락은 강제로 뺏을 수 없다. 
 
** 이 4가지 필요조건 중, 1가지만 어겨도 데드락은 발생하지 않는다. 
** Circular Wait는 다른 세 가지 조건으로 인해 생기는 문제로, 해결 불가한 문제다. 
 
 

4. Dealing with Deadlock - 교착상태를 처리하기 위한 접근법

 
<Prevent Deadlock>
위의 4가지 조건 중 하나를 제거하는 정책을 채택한다. 
 
<Avoid Deadlock>
[자원 할당의 현재 상태]에 따라 적절한 dynamic choice를 한다. -> 교착 상태를 피한다. 
 
<Detect Deadlock>
교착 상태의 존재를 감지하고, 복구 작업을 수행할 수 있다.