OS) Deadlock

👀 Deadlock(교착상태)란?

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• 예) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  • Request -> Allocate -> Use -> Release

데드락이 발생하는 예

• 시스템에 2개의 tape drive가 있고 프로세스 P1, P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있는 경우
  
  

P0          P1
P(A);       P(B);
P(B);       P(A);

• 두 세마포어가 필요한 자원을 서로 자원을 하나씩 가진 상태에서 상대가 내놓기를 기다리는 경우

데드락 발생의 4가지 조건

Mutual exclusion (상호 배제)

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

No preemption (비선점)

• 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

Hold and wait (보유 대기)

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

Circular wait (순환 대기)

• 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
• 프로세스 1, 2, 3, 4가 있을 때
  • 1은 2가 가진 자원을 기다림
  • 2는 3이 가진 자원을 기다림
  • 3은 4가 가진 자원을 기다림
  • 4는 1이 가진 자원을 기다림
    
    

데드락 처리 방법

Deadlock Prevention

• 자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

Deadlock Detection and recovery

• 데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발견시 recover

Deadlock Ingorance

• 데드락을 시스템이 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택
• 데드락 자체가 자주 발생하는 일이 아니기 때문에 데드락에 대비한다고 시스템의 자원 분배를 조절하는 것은 비효율적이기 때문에 사용자가 알아서 처리하도록 한다.
  
  

데드락 방지

Mutual exclusion

• 공유해서는 안 되는 자원의 경우 반드시 성립해야 함
• 즉 이 조건이 반드시 성립한다면 데드락이 발생할 수 없다.

Hold and Wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
• 방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
• 방법 2 : 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

No Preemption

• 프로세스가 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
• 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨
• 즉 자원을 선점할 수 있게 하는 것
• state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (예: CPU, memory)

Circular Wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• 예를 들어 순서가 3인 자원을 보유 중인 프로세스가 순서가 1인 자원을 할당받기 위해서는 우선 순서 3을 release해야 한다.

• 자원 요청 사이클이 생성되지 않게 하는 것
  

• 하지만 위 기법들을 적용하면 Utilization(이용률) 저하, Throughput(성능) 감소, Starvation 문제가 생겨서 굉장히 비효율적이다.
  
  

Deadlock Avoidance

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 데드락으로부터 안전한지 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

Resource Allocation Graph algorithm

• 자원당 하나의 인스턴스만 있을 때 사용하는 방법
• 자원들과 프로세스들 간을 실선과 점선으로 잇는 그래프를 그려 할당과 요청된 자원은 실선으로 표시하고 어떤 프로세스가 미래에 한 번은 사용할 수 있는 자원은 점선으로 표시하는 것이다.
• 새로운 자원 요청이 들어오면 실선을 점선으로 바꿨을 때 사이클이 생기지 않을 때에만 요청 자원을 할당한다.
• 사이클 생성 여부 조사시 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다.

Banker’s Algorithm

• 가정
  • 모든 프로세스는 자원의 최대 사용량을 미리 명시
  • 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
• 방법
  • 기본 개념 : 자원 요청 시 safe 상태를 유지할 경우에만 할당
  • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 unsafe 상태)
  • 위의 경우에 부합하는 프로세스가 있으면 그 프로세스에게 자원 할당
  • 할당받은 프로세스가 종료되면 모든 자원 반납
  • 모든 프로세스가 종료될 때까지 이러한 과정 반복

Deadlock Detection and Recovery

Detection

• Banker's Algorithm과 유사한 방법으로 사이클의 존재 여부를 주기적으로 검사하여 자원을 할당하는 방법이 있다.

Recovery

Process termination

• 데드락 된 모든 프로세스 종료
• 데드락이 해결될 때 까지 데드락에 갇혀 있는 프로세스를 하나씩 종료

Resource preemption

• 비용을 최소화 할 victim 선정
• safe state로 rollback하여 프로세스 재시작
• Starvation 문제
  • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
  • cost factor에 rollback 횟수도 같이 고려
    
    

Deadlock Ignorance

• 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
• 데드락은 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있다.
• 만약, 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처
• UNIX, Windows 등 대부분의 범용 OS가 채택
  
  
  

출처

• 운영체제 - 이화여자대학교 KOCW 공개강의