[운영체제] 6장: Concurrency: Deadlock and Starvation

Deadlock

• 하나의 프로세스가 단독으로 Deadlock에 걸릴 수 없다. 적어도 2개 이상의 프로세스가 Deadlock에 걸린다.
• 프로세스가 Deadlock에 걸리기 위해서는 Blocked 상태가 되어야 한다.
• 프로세스가 Blocked 되었다고 해서 반드시 Deadlock에 걸리는 것은 아니다.
• 프로세스의 Blocked 상태를 해제하는 이벤트를 실행하는 프로세스가 Blocked 일 때 Deadlock이 발생한다.

[Deadlock 발생 상황]
1. A, semWait(s1) 실행
2. B, semWait(s2) 실행
3. B, semWait(s1) 실행 -> B, Blocekd
4. A, semWait(s2) 실행 -> A, Blocked
- A의 Blocked 상태를 해제할 수 있는 프로세스 = B
- B의 Blocked 상태를 해제할 수 있는 프로세스 = A
- A, B 둘 다 Blocked 상태 -> Deadlock 발생
- semSignal() 코드를 다른 프로세스가 실행할 수 있다면 Deadlock이 발생하지 않을 수 있다.

Deadlock 발생 조건

💡 아래의 4가지 조건 모두 만족해야 Deadlock 이 발생한다.

1. Mutual Exclusion
   • 한 번에 하나의 프로세스만 자원에 접근할 수 있어야 한다.
   • 여러 프로세스가 동시에 자원에 접근할 수 있다면 Deadlock이 발생하지 않는다.
2. Hold-and-Wait
   • Hold: 프로세스에게 자원이 할당된 상태
   • Wait: 프로세스가 자원을 요청하고 할당 받기를 기다리고 있는 상태
   • 각 프로세스가 Hold, Wait 상태 둘 다 충족해야 Deadlock이 발생한다.
3. No Preemption
   • 한 프로세스가 사용 중인 자원을 다른 프로세스가 강제로 선점할 수 없어야 한다.
4. Circular Wait
   • 자원 할당 그래프에서 사이클이 형성되어야 한다.
   • 겉보기에 사이클인 것 같아도 요청한 자원이 현재 사용 가능하다면 Deadlock 이 발생하지 않는다.

주로 Deadlock은 두 프로세스 사이에서 발생한다.

• Deadlock에 걸린 두 프로세스가 가지고 있는 자원을 요청하는 프로세스 -> Blocked
• Blocked 상태의 프로세스가 가지고 있는 자원을 요청하는 프로세스 -> Blocked
• 연쇄적으로 프로세스가 Blocked 상태가 되는 상황이 발생할 수 있다.

Dealing with Deadlock

Prevent Deadlock

• Mutual Exclusion
• Hold-and-Waitz: Hold, Wait 중 하나의 상태만을 가져야 한다.
  • 프로세스는 실행에 필요한 모든 자원을 한 번에 요청한다.
  • 모든 자원을 한 번에 할당 받을 수 있으면 실행을 시작한다. (Hold)
  • 그렇지 않다면 아무 것도 할당 받지 않고 대기한다. (Wait)
  • Starvation O, 자원 낭비의 문제가 발생할 수 있다.
• No Preemption
  • 프로세스가 자원을 요청했을 때 할당 받을 수 없다면, 그 프로세스가 가지고 있는 모든 자원을 반납하고 처음부터 다시 실행시켜 재요청한다. (Blocked X)
  • OS가 특정 자원을 가지고 있는 프로세스에게 그 자원을 강제 반납시키고 원하는 프로세스에게 할당할 수 있다.
• Circular Wait: 자원에 번호를 부여하고 그 번호 순서대로 생략되는 것 없이 자원을 요청한다.
  • 자원 번호가 높은 자원을 할당 받은 후에, 낮은 번호의 자원을 요청하는 일은 발생하지 않는다.

    증명
    전제: P1, R1 소유 & R2 요청 / P2, R1 요청 & R2 소유
    P1 입장, R1# < R2#
    P2 입장, R1# > R2#
    두 프로세스의 입장이 동시에 성립 불가능 -> 사이클 X -> Deadlock 발생 X

Avoid Deadlock

• 자원을 할당하기 전에, 할당을 했을 때의 미래 상황을 가정하여 Deadlock이 발생하는지 확인하고, 발생하지 않으면 자원을 할당한다.
  • 모든 프로세스의 최대 자원 요구량을 미리 알아야 한다. 미리 자원을 요청하는 것은 아니다.
• Process Initiation Denial
  • 프로세스는 실행 시작 전에 최대 자원 요구량을 OS에게 알린다.
  • 현재 실행 중인 프로세스들의 최대 자원 요구량과 실행하려는 새로운 프로세스의 최대 자원 요구량을 합쳤을 때, 그 전체 양이 OS가 가지고 있는 전체 자원의 양보다 작거나 같으면 프로세스 실행을 진행하고, 그렇지 않으면 실행하지 않는다.
  • 프로세스들이 요구하는 최대 자원 요구량이 동시에 요구하는 것이 아니더라도 OS는 동시에 요구하는 상황을 가정하여 결정한다.
  • Prevent Deadlock의 Hold-and-Wait와 유사한 방식이다.
• Resource Allocation Denial (= Banker's Algorithm)
  • 시스템 자원의 양이 고정되어 있음을 가정한다.
  • 시스템 상태: 프로세스들이 자원을 요청하고 할당 받은 관계
  • Safe 상태: 자원 할당 과정에서 Deadlock이 발생하지 않고 정상적으로 종료할 수 있는 상태
  • Unsafe 상태: 자원 할당 과정에서 Deadlock이 발생할 가능성이 있는 상태. 무조건 발생하는 것은 아니다.
  • 최악의 상황을 가정하고 결정하기 때문에 실제로는 Safe 하더라도 Unsafe로 판단하여 자원을 할당하지 않는 경우가 발생할 수 있다.
  • 할당할 자원의 양이 고정되어야 한다.
• Determination of Safe State
  • 각 matrix는 OS가 관리한다.
  • Claim matrix: 프로세스의 최대 자원 요구량
  • Allocation matrix: 프로세스가 현재 점유하고 있는 자원의 양
  • Resource vector: 시스템 내의 전체 자원의 양
  • Available vector: 현재 사용 가능한 자원의 양

C - A의 각 행을 V와 비교했을 때 자원 할당 후 종료 가능한 프로세스는 P2이다.

↓

P2의 종료 가정 -> V += A[P2] = {6,2,3} / C-A[P2] = {0,0,0}
C-A의 각 행을 V와 비교했을 때 모든 프로세스의 종료가 가능하다. -> 프로세스 번호 순서대로 종료한다.
P1의 종료 가정 -> V += A[P1] = {7,2,3}
P3의 종료 가정 -> V += A[P3] = {9,3,4}
P4의 종료 가정 -> V += A[P4] = {9,3,6}
모든 프로세스의 종료가 가능하므로 자원 할당 전의 처음 상태는 Safe 상태이다.

P1이 R1과 R3을 하나씩 추가적으로 요청했을 때 할당한 것을 가정한 상황이다.
C-A의 각 행을 V와 비교했을 때 어떠한 프로세스도 종료가 불가능 하므로 Unsafe 상태이다.
자원 할당을 거절하고 이전 상태로 복구한다.

• Deadlock Avoidance Logic

- rest: 프로세스 집합
- currentavail: available 의 복사본 (원상태를 복구하기 위해)
- 종료 가능한 프로세스 탐색 과정을 모두 마친 후에 rest 집합이 비어 있다면 Safe 상태이고, 그렇지 않다면 Unsafe 상태이다.

Detect Deadlock

• 자원을 요청했을 때 사용 가능하다면 일단 할당한다.
• 주기적으로 Deadlock이 발생했는지 확인한다.
• Detection Algorithm
  • Allocation matrix A, Available vector, Request matrix Q
  • 처음에 모든 프로세스는 un-mark 상태이다.
  • mark: Deadlock에 걸려 있지 않은 상태
  1. Allocation matrix에서 모든 열의 값이 0인 프로세스를 mark 한다.
     • Hold-and-Wait 에 위배되는 것으로 Deadlock 발생 가능성이 없다.
  2. Available vector를 W vector에 복사한다.
  3. 현재 상황만을 고려하여 Q의 모든 열의 값이 W보다 작거나 같은 프로세스를 찾아 mark 한다.
  4. 과정3에서 mark된 프로세스가 있다면 프로세스 종료 및 자원 반납을 가정하여 W vector 를 갱신한다.
  5. 과정3 -> 과정4 반복

     • 알고리즘 수행 후에 un-mark 상태의 프로세스가 남아 있다면 Deadlock이 발생한 것이다.
     • un-mark 상태로 남아 있는 프로세스는 0개이거나 2개 이상이다. 1개일 수는 없다.

• Recovery Strategies Once Deadlock Detected
  • Deadlock에 걸린 모든 프로세스를 중단하고 재실행한다.
  • 프로세스 상태를 주기적으로 백업하고 Deadlock 발생이 확인되었을 때, Deadlock이 발생하기 전 상태로 복원한다.
    • Deadlock이 발생하기 전의 상태를 찾아내는 것이 어렵다.
  • Deadlock이 더 이상 존재하지 않을 때까지 Deadlock에 걸린 프로세스들을 순차적으로 하나씩 중단한다.
  • Deadlock이 더 이상 존재하지 않을 때까지 Deadlock에 걸린 프로세스를 자원 할당 전으로 하나씩 복원한다. (자원 선점)

Dining Philosophers Problem

[문제 발생 Solution]
- P0~P4 모두 왼쪽 포크만 잡고 타임 아웃이 되는 경우, 오른쪽 포크 잡기를 시도할 때 모든 프로세스가 Blocked 되면서 Deadlock이 발생한다.
- 포크를 잡고 놓는 순서를 바꾼다고 Deadlock이 발생하지 않는 것은 아니다.

[Real Solution]
- room에는 4개의 프로세스만이 진입할 수 있다.
- 따라서 하나의 프로세스는 반드시 두 포크 모두 사용 가능하므로 Deadlock이 발생하지 않는다.
- signal(room) 코드가 signal(fork) 코드 앞에 위치해도 Deadlock은 발생하지 않는다.

• Circular wait prevent 방식을 이용한 Deadlock prevent

  • P0~P3 은 왼쪽 -> 오른쪽 포크 순서로 잡는다.
  • P4 만 오른쪽 -> 왼쪽 포크 순서로 잡는다.

• A solution using a monitor

- fork: true(사용 가능), false(사용 중)
- 잡으려는 fork 값이 false 이면 모니터 내의 컨디션 변수에서 대기한다.
- 컨디션 변수의 개수 = fork 개수
- 왼쪽 fork 잡는 데에 성공한 철학자는 오른쪽 fork 점유 여부를 확인하는 작업을 마칠 때까지 모니터를 떠나지 않기 때문에 deadlock 이 발생하지 않는다.
- get_forks()를 왼쪽, 오른쪽 포크를 잡는 함수로 분리할 경우, Deadlock 발생 가능성이 있다.