교착상태(deadlock)

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

  *** Resource(자원) - 하드웨어, 소프트웨어 등을 포함하는 개념

  ⇒ Request, Allocate, Use, Release (프로세스의 자원 사용절차)

발생의 4가지 조건

1. Mutual exclusion (상호배제)

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

2. No preemption (비선점)

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

3. Hold and wait (보유대기)

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

4. Circular wait (순환대기)

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

Resource-Allocation Graph (자원할당그래프)

프로세스 1이 자원1을 요청하고 있고, 프로세스 2가 자원1을 가지고 있는 상태이다.

프로세스 2는 또한 자원 3을 요청하고 있고, 자원 3은 프로세스 3이 가지고 있다,

⇒ 이런 상황이 데드락 일까??

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

아래 예제를 통해 살펴보도록 하자.

1. 첫번째 예제

• 1번 프로세스
  • 2번 자원을 가지고 있는 상태로, 1번 자원을 요청하였다.
• 2번 프로세스
  • 1번 자원과 2번 자원을 가지고 있는 상태로, 3번 자원을 요청하였다.
• 3번 프로세스
  • 3번 자원을 가지고있는 상태로 2번자원을 요청하였다.

⇒ 각 요청에 해당하는 자원들이 모두 사용중인 상태이고,

해당하는 자원들에 대해서 모두 사용할 수 없는 사이클이 만들어져 있기에 deadlock 상태이다.

1. 두번째 예제