운영체제 (10) - Deadlock (데드락)

Deadlock(데드락)

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

 

자원(Resource)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• 예 ) I / O devices, CPU cycle, memory space, semaphore 등

Deadlock 발생 조건 4가지

1. Mutual Exclusion (상호 배제)
   • 매 순간 하나의 프로세스만이 자원 사용 가능
2. No preemption (비선점)
   • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
3. Hold and wait (보유 대기)
   • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
4. Circular wait ( 순환 대기)
   • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

위 4가지 조건을 모두 만족해야 한다

 

Deadlock 처리방법

1. Deadlock Prevention
   • 자원할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것,  (단점 :Utilization 저하, throughput 감소, starvation 문제)
2. Deadlock Avoidance
   • 자원요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는경우에만 자원을 할당 ex) Resource Allocation Graph algorithm, Banker's Algorithm
   • 시스템 state가 원래 state로 돌아올 수 있는경우에만 자원 할당
3. Deadlock Detection and recovery
   • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
   • Recovery의 방식에는 2가지가 있다
     1. 프로세스 종료 (Process termination)
        • 연루된 모든 process를 종료하거나, Deadlock이 없어질 때까지 하나씩 종료한다
     2. 자원 선점 (Resource preemption)
        • 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에 할당하고, 기존 점유 중이던 프로세스는 종료
        • 최소 비용이 들도록 희생자를 선택함. 롤백이나 기아상태에 대한 고려가 필요
4. Deadlock Ignorance
   • Deadlock을 시스템이 책임지지 않음
   • UNIX를 포함한 대부분의 OS가 채택
   • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead 일 수 있음
   • 사람이 직접 process를 죽이는 등의 방법으로 대처

 

Resource - Allocation Graph

• Deadlock이 발생하는지 보는, 프로세스와 Resource로 이뤄진 그래프
• 사이클이 있으면 Deadlock (2가지 경우의 수)
  1. Resource 타입마다 한개의 instance만 존재 하면, 데드락
  2. Resource타입마다 몇개의 instance가 존재하면, 데드락의 가능성이 있다
• 사이클이 없으면 Deadlock이 아니다

 

Resource - Allocation Graph

Banker's Algorithm (은행원 알고리즘)

은행원 알고리즘은 항상 최악의 경우를 생각하는 보수적인 방법으로 데드락을 회피한다. 

 

• 프로세스에 할당된 자원
• 한번의 요청에 최대로 필요한 자원

위의 두 가지를 계산하고 프로세스가 자원을 요청했을 때 최악의 상황 (= 최대로 자원을 사용할 경우)를 고려해서 가용자원으로 그 조건을 만족할 수 있다면 자원을 할당하고 그렇지 않는다면 자원을 할당하지 않는다. 

 

Sequence <P1,P3,P4,P2,P0>가 존재하므로 시스템은 Safe State이다 

 

 

 

이 포스팅은 이화여대에서 무료로제공하는 반효경님의 운영체제강의를 수강하며 정리한 내용입니다.

필자가 잘 이해하지 못해서 잘못된 내용이 있을 수 있으므로 주의바라며, 발견되면 알려주시면 감사하겠습니다.

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

운영체제