7. 교착 상태 Deadlock (2) - Deadlock model

출처 : https://www.youtube.com/watch?v=czjtYkjhtgo&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=20

 

 

 

Deadlock 발생의 예

 

• 2개의 프로세스 (P1, P2)
• 2개의 자원 (R1, R2)

1. P1이 R2를 요청한다. R2를 쓰고 있는 프로세스가 없으므로 P1이 R2를 사용하게 된다.
2. P2가 R1을 요청한다. R1을 쓰고 있는 프로세스가 없으므로 P2가 R1을 사용하게 된다.
3. P1이 R1을 요청한다. P2가 R1을 사용하고 있으므로, P1은 대기하게 된다. 이때는 아직 P2가 작업을 마치고 R1을 release 하면 작업을 수행할 수 있는 상황이므로 Deadlock은 아니다.
4. P2가 R2를 요청한다. P1이 R2를 사용하고 있는데 R1을 얻을 때까지 대기하고 있고, P2는 R1을 사용하고 있는데 R2를 얻을 때까지 대기하게 된다. 이렇게 불가능한 이벤트들을 기다리고 있으므로 Deadlock 상태가 된다.

 

 

Deadlock Model

 

Deadlock을 표현하는 기법들은 2가지가 존재한다.

• Graph Model
• State Transition Model

 

 

Graph Model

 

• Node
  • 프로세스 노드(P1, P2), 리소스 노드(R1, R2)
• Edge
  • Rj -> Pi : 자원 Rj가 프로세스 Pi에게 할당 됨
  • Pi -> Rj : 프로세스 Pi가 자원 Rj을 요청 (대기 중)

이 그래프 모델을 통해 맨 처음 예시를 표현하면 다음과 같다.

1. R2가 P1에게 할당된다.
2. R1이 P2에게 할당된다.
3. P1이 R1을 요청한다.
4. P2가 R2를 요청한다.

즉, 서로가 서로에게 할당된 자원을 요청해서 이도저도 못하게 되는 상황, 발생할 수 없는 이벤트를 기다리게 되는 상황이 바로 Deadlock이다.

 

그래프 모델로 표현했을 때, 사이클이 형성되면 Deadlock임을 알 수 있다.

 

State Transition Model

 

•  예제
  • 2개의 프로세스와 A type의 자원 2개(unit) 존재. 즉, Ra 라는 자원이 2개 존
  • 프로세스는 한 번에 자원 하나만 요청 / 반납 가능
• State
  • 0 : 현재 할당된 자원이 없는데, 요청도 안하는 경우
  • 1 : 현재 할당된 자원이 없는데, 요청하는 경우
  • 2 : 현재 할당된 자원이 1개 있는데, 요청을 안하는 경우
  • 3 : 현재 할당된 자원이 1개 있는데, 또 요청하는 경우
  • 4 : 현재 할당된 자원이 2개인 경우

만약 프로세스가 1개라면 위의 state와 같으나 2개라면 5 x 5 = 25 가지의 state가 존재할 수 있음

 

 

맨 처음 노드 S00에서 첫번째 0 = P1의 state, 두번째 0 = P2의 state를 나타낸다. 엣지의 2는 P2에 의해 state가 변한 것, 엣지의 1은 P1에 의해 state가 변한 것을 의미한다.

 

Deadlock은 S33에서 발생하게 된다. 즉, P1이 자원을 하나 가지고있는 상황에서 하나를 또 요청하고, 마찬가지로 P2도 자원을 하나 가지고 있는 상황에서 자원을 또 요청하는 상황에서 Deadlock이 발생하게 된다.

 

돌려말하면, S23과 S32에서 S33으로 가는 상황을 막으면 Deadlock이 발생하지 않게 된다.

 

 

Deadlock의 발생 필요 조건

 

Deadlock이 발생하려면 밑의 4가지 조건(자원의 특성 + 프로세스의 특성)이 모두 성립하여야 한다.

• 자원의 특성
  • Exclusive use of resources : 나만 사용하는 자원
  • Non-preemptible resources : 한번 선점하면 다시는 반납하지 않는 자원
• 프로세스의 특성
  • Hold and wait (Partial allocation)
    • 자원을 하나 hold하고 다른 자원 요청
    • 내가 필요한 자원을 모두 갖고있다면 deadlock이 발생하지 않고, 자원을 하나도 가지고 있지 않다면 deadlock의 원인이 되지 않는다.
  • Circular wait