교착상태(Deadlock)

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

Resource(자원)

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

Deadlock Example 1

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

Deadlock 발생의 4가지 조건

Mutual exclusion(상호 배제)

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

No preemption(비선점)

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

Hold and wait(보유대기)

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

Circular wait(순환대기)

• 자원을 기다리는 프로세스간에 사이클이 형성되어야함
  

• 그래프에 cycle 이 없으면 deadlock이 아니다.

• 그래프에 cycle이 있으면 만약 자원에 단 하나의 인스턴스가 있으면 deadlock 이다.

• 자원 안에 여러개의 인스턴스가 있더 하더라도 프로세스가 인서턴스를 요청 하였는데 주지못할경우 deadlock에 걸릴 수 있다.

Deadlock의 처리방법

Deadlock Prevention

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

Deadlcok Avoidance

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

Deadlock Detection and recovery

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

Deadlock Ignorance (현대 방식)

• Deadlock을 시스템이 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택

해결 방안

Mutual exclusion

• 공유해서는 안되는 자원의 경우 반드시 성립해야함

Hold and wait

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

No Preemption

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

Circular Wait

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

⇒ Utilization 저하 , throughput 감소 , starvation 문제

위의 그림과 같이 5개의 프로세스가 있고 A는 10개 B는 5개 C는 7개의 인스턴스가 있다.

프로세스가 자원을 요청할때 가용자원만으로 최대요청을 처리할 수 있을경우에만 자원을 주고

그렇지 않을 경우에 주게 되면 Deadlock이 걸리기 때문에 주지 않는다.

Deadlock avoidance

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

P0과 P2에서 자원을 요청하지 않으므로 사용후 Available로 넘어가서 Available에 있는 자원의 개수가 A는 3 B는 1 C는 3이 되어서 P1이 요청한 자원을 넘겨줄 수 있고 그렇게 되어 P1도 사용후 Available에 자원을 넘기고 P3 와 P4도 같은 방식으로 요청한 자원을 받고 사용하여 넘겨주기 때문에 deadlock이 걸리지 않는다.

Deadlock Detection and Recovery

-Process termination

• Abort all deadlocked processes (프로세스 다죽임)
• Abort one process at a time until the deadlock cycle is eliminated(프로세스 하나씩 죽임)

-Resource Preemption

• 비용을 최소화할 victim의 선정
• safe state로 rollback하여 process를 restart
• Starvation문제

-동일한 프로세스가 계속해서 victim으로 선정되는 겨웅

-cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

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