Chap 6. Concurrency : Deadlock and Starvation

Deadlock

두 명의 프로세스가 서로 자원 하나씩 상대편이 원하는 자원을 가지는 동시에 상대편이 가지고 있는 자원을 원하는 상황.

• semSignal 프로세스 ≠ Process A or Process B
  • Deadlock X

Process A와 process B Block & Signal을 Process A와 ProcessB만 줄 수 있는 상황 ⇒ Deadlock

Deadlock 발생 조건

다음 조건중 하나라도 만족하지 않는다면, Deadlock은 발생하지 않는다.

• Mutual Exclusion
  • 한 번에 한 프로세스만 Resource 접근 가능
• Hold-and-Wait
• No preemption
  • preemption 가능 ⇒ Deadlock X
    • 어떠한 코드를 뒤로 돌리거나 자원을 뺏어가는게 가능하지 않은 연산에서 Deadlock이 발생
• Circular Wait
  • Deadlock에 빠져있는 프로세스들 = 사이클 존재
  • Resource Allocation Graph에서 사이클이 발생 ⇒ Circular Wait

Resource Allocation Graphs of deadlock

오른편 그림은 Ra, Rb의 자원이 1개가 아니라 3개, 2개로 존재한다. 사이클이 아니므로 Deadlock도 아니다.

• 자원 할당 ⇒ OS가 판단
  • 자원 요청 ⇒ OS가 누구한테 줄지, 언제줄지를 결정

Dealing with Deadlock

• Prevent deadlock
  • 자원을 할당하는 규칙
  • 근본적으로 deadlock 발생 가능성 차단
• Avoid deadlock
  • 매번 자원을 할당하기 전 Deadlock 발생 가능성 검사
• Detect deadlock
  • Deadlock이 발생하게 둠
  • Deadlock 발생 시, Deadlock 찾아서 해결

deadlock prevention

• Mutual Exclusion
  • Mutal Exclusion은 깰 수 없다.
• hold and wait
  • 모든 프로세스가 실행하기 전에 자기가 사용할 자원을 한꺼번에 요청
  • 그 다음 필요한 자원 전부 다 할당 ⇒ 실행 시작
  • Wait를 하지 않음
  • 컴파일할 때 자원 파악
  • 자원 낭비가 심한 방법
• no-preemption
  • preempt 한다 = 자원을 뺏는다.
  • 자원이 할당되지 않는 경우 ⇒ 실행 중단 후 모든 자원을 뺏은 다음 처음부터 다시 실행
  • 자원을 할당받지 못한 프로세스 preempt된다.
  • 어떤 프로세스가 언제 실행을 끝내게 될지 알 수가 없다.
• circular wait

  • 모든 자원들한테 아이디 부여 (중복 X)

  • 자원의 번호 순서대로(오름차순) 자원 요청

    • 1, 5, 3 순서로 필요
    • 5번 요청 ⇒ 3, 5 요청

  • 구현 가능한 방법

    왜 번호순서로 할당하게 되면 circular wait가 발생하지 않는지 증명할 수 있어야 한다.

위의 그림이 circular wait를 방지하기 위한 방법으로 구현되었다고 하면, P1 입장에서는 Rb의 번호가 Ra의 번호보다 작다. 그래서 Rb를 먼저 할당받은 다음 Ra를 요청한다.

그런데 P2 입장에서는 Ra를 먼저 할당받고 Rb를 요청한다. 즉, P2는 Ra의 번호가 Rb보다 작다.

위 내용대로면 모순이 발생한다. 그렇기 때문에 두 가지 조건을 동시에 만족하는 조건은 있을 수 없으므로 이러한 사이클은 발생하지 않는다.

Deadlock Avoidance

• 미리 자원을 할당하는 규칙을 정하지 않고 각각의 프로세스들은 자원이 필요한 시점에 할당 요청
• OS는 자원 할당을 해주기 전에 Deadlock 발생이 가능한 상태인지 확인
  • Deadlock 발생 가능성이 있는 경우, 프로세스 Suspend
• Deadlock Avoidance를 사용하려면 사전정보가 필요
  • 각각의 프로세스들이 실행을 시작해서 끝날 때까지 각각의 자원들을 최대 몇 개까지 요구할건지에 대한 정보
• 이러한 정보는 컴파일할 때 확인
• 프로세스가 자원을 요청하면,
  • 요청을 받아들였다고 가정
  • 시스템 상태 업데이트
• 그런다음 결과가 safe state인지 확인
  • safe state라면 자원을 부여
  • 그렇지 않다면, 프로세스 block

Two Approaches to Deadlock Avoidance

• Process Initiation Denial
  • 프로세스를 실행 시작시켰을 때 deadlock 발생 가능성 확인
  • Deadlock 발생 가능성이 존재한다면, 프로세스 실행을 멈추고 Suspend
• Resource Allocation Denial
  • 실행을 하다가 리소스 요청을 하게 되면, deadlock 발생 가능성 확인
  • Deadlock 발생 가능성이 존재한다면, 프로세스 실행을 멈추고 suspend

Process Initiation Denial

• 현재 실행하는 프로세스들은 자원 타입 별 사용 최대치를 미리 얘기를 하고 사용
• 실행중인 프로세스들의 자원 타입 별 사용 최대치 + 새로 실행하려고 하는 프로세스의 자원 타입 별 사용 최대치 ≤ 현재 시스템이 갖고 있는 자원 ⇒ 실행 시작
  • 현재 실행하고 있는 프로세스의 Claim matrix 합 + 실행시킬 프로세스의 Claim matrix ≤ Resource Vector 이면 실행 가능
• Not optimal
  • 실제 각각의 프로세스 동시에 요청 X
  • 최악의 상황 가정

• Claim matrix = 각각의 프로세스들이 실행하면서 타입별 자원 최대 요청양 = 내가 최대 요청하는 리소스 개수.
• Allocation matrix = 지금 OS가 각각의 프로세스한테 할당한 자원 = 지금 현재 할당받은 숫자
• Resource vector = 지금 시스템에서 가지고 있는 자원 = 앞으로 실행을 끝마칠 때까지 더 요청할 수 있는 양.
• C-A = Claim matrix - Allocation matrix
• Available vector = 지금 남아있는 시스템 자원 수 = Resource vector - Allocation matrix
• P1 도착 : R1 3개, R2 2개, R3 2개 요청 ⇒ 모든 자원들이 가지고 있는 자원의 수보다 작거나 같음
• P2 도착 : R1 6개, R2 1개, R3 3개 요청 ⇒ 실행하고 있는 P1이 요청한 최대치 자원과 합친다(두 프로세스가 동시에 최대치 자원을 달라고 할 수 있으므로) ⇒ <9, 3, 5>는 <9, 3, 6>보다 작거나 같으므로 P2 실행 가능
• P3 도착 : R1 3개, R2 1개, R3 4개 요청 ⇒ 12개 4개 9개이므로 작거나 같지 않다. ⇒ P3는 Ready/Suspend로 보낸다.

Resource Allocation Denial(= banker`s Algorithm)

• 자원 요청 시, 자원을 줬을 때 deadlock 발생 유무 판단
  • Safe 상태, Unsafe한 상태 구분
• state of the system : 시스템 안에 있는 리소스들을 프로세스한테 어떤 식으로 나누어줬는지에 대한 상황
• safe 상태 : deadlock이 발생하지 않는 상태. 데드락이 발생하지 않는 순서가 적어도 1개 존재한다.
• unsafe 상태 : deadlock이 발생할 가능성이 있는 상태
• claim matrix, allocation matrix, resource vector ⇒ 시스템의 상태
  • 시스템 상태를 표현하라고 하면 matrix와 표를 그리면 된다.

• C-A, available vector는 직접 그릴 수 있어야 함
• 실행을 계속하는데 Deadlock이 걸리지 않고 무사히 종료할 수 있는 종료 순서가 하나라도 존재하면 Safe 상태
• Unsafe 상태는 어떤 순서로 종료시키더라도 결국 Deadlock에 걸릴 수 밖에 없는 상태

Determination of Safe State

1. C-A를 그린다.

2. Avilable vector를 그린다.

3. 남아있는 자원(= available vector)을 가지고 종료할 수 있는 프로세스가 있는지 찾는다. ⇒ available vector와 C-A를 비교한다.

   3-1. P2 종료 가능 ⇒ P2가 필요한 자원을 다 가진 후 P2가 종료하게 되면, 자기가 가진 자원을 반납 ⇒ available vector는 <6, 2, 3> 이 된다.

   

   3-2. 다음 종료되는 프로세스는 1, 3, 4 중 1번이다. 0부터 n까지 종료 가능한 프로세스를 찾기 때문이다. P1이 종료하고 자원을 반납한다.

   

   3-3. P3가 종료하고 자원을 반납한다.

   

   3-4. P4가 종료하고 자원을 반납한다.

💡 위 이미지 중 어떤 이미지를 safe 상태라고 할까?

맨 처음의 상태가 safe한 상태이다.

Determination of Unsafe State

(b)에서 P1이 R1 타입 자원 1개, R3 타입 자원 1개를 요청한다. 이 요청을 받아들여서 자원을 주고 난 후의 상태가 safe한지 판단해야 한다.

OS가 자원을 줬다고 가정하면 Allocation matrix의 P1이 바뀐다. Available vector는 <0, 1, 1> 로 바뀌게 된다.

현재 Available vector 가 <0, 1, 1> 인데 이 값을 가지고 종료시킬 수 있는 프로세스는 존재하지 않는다. 따라서 (b)의 상태는 unsafe 상태이다.

그래서 P1의 자원 요청을 거절하고 P1 프로세스를 suspend 시킨다. 이런 식으로 deadlock avoidance 알고리즘을 실행시킨다.

Deadlock Avoidance Logic

• allocation + request > claim = 오류 ⇒ Terminate
  • 처음 시작할 때의 최대 요청값보다 더 많은 값 요청 시, 현재 Safe하다고 믿고 있는 상태가 Unsafe 상태일 수 있기 때문에 요청 거절
• request > available ⇒ 프로세스 Suspend
  • 줘야될 자원이 모자른 상황
  • 해당 프로세스 Suspend, 자원 요청 거절
• safe 상태인지 검사
  • 지금 상태가 아닌 자원을 줬다고 가정 후 검사
  • allocation = allocation + request
  • available = available - request
• safe 상태라면 자원을 할당하고 그렇지 않으면 프로세스는 suspend시키고 원상복귀 시킨다.

• rest
  • 처음에 모든 프로세스를 다 집어넣고 프로세스가 종료 가능할 때마다 집합에서 하나씩 제거
  • rest = 공집합 ⇒ 모든 프로세스 종료 가능 = safe 상태
• while 문
  • 각각의 프로세스의 C-A값과 available 값 비교
    • 종료 가능한 프로세스 체크
  • 종료 가능한 프로세스가 있다면 종료했다고 가정
    • rest 집합에서 제외
    • currentavail = currentavail + alloc (자원 반납)
  • 만족하는 프로세스가 더 이상 없다면 while 문을 빠져나온다.
• rest 집합이 비었다면 true 리턴

이 방법은 optimal한 방법이 아니다. 실제로 이처럼 전투적으로 deadlock avoidance를 하지 않는다. 실제 많은 시스템에서 deadlock avoidance를 위해 보통 2-3 프로세스 사이에서 deadlock 발생 가능성이 있는지 검사한다.

deadlock이 발생하는 시점에서 semWait를 거절한다. 그러나 프로세스 시스템 안에 있는 모든 프로세스 사이에서의 자원 할당을 조사하지는 않는다.

시간복잡도 : $O(N*M)$

Deadlock Avoidance Restrictions

• 리소스 요청 최대치가 얼마인지 미리 얘기
  • 이 최대치가 정확한 값인지 생각해봐야 한다. 처음에 3 가지 자원을 <3, 3, 3>개 필요하다고 요구할 수 있다. 하지만, 그 자원을 동시에 요구하지 않을 수도 있고, 3-3-3개 요구 조차 하지 않을 수도 있다. if-else에 따라서 어떤 코드는 실행되지 않으므로 실제보다 적은 수의 자원을 요청할 수 있다. 따라서 사실 deadlock이 발생하지 않는 상태인데도 unsafe 상태라고 판단할 수 있다.
• 알고리즘이 작동하려면 시스템 안에 있는 자원의 개수가 고정적이어야 한다.
  • 대부분의 하드웨어 자원, 메모리 자원은 고정적이다. 그러나 세마포 같은 자원은 고정적이지 않다.

그래서 deadlock avoidance를 하고 싶지만 아주 제한적인 상황에서만 한다. 왜냐하면 실제로 시스템 안에 프로세스가 수백 개가 돌아가고 자원이 수백개가 있다고 하지만, 실제 deadlock이 발생하는 상황은 90% 이상 두 프로세스 사이에서 deadlock이 발생한다.

전체 프로세스와 전체 자원에 대해서 검사 = 시간낭비

그래서 2-3개 제한적인 상황에서 deadlock avoidance를 하고 대부분의 시스템에서는 deadlock detection을 한다.

Deadlock Detection

• Deadlock이 발생하도록 놔둔다. 그 다음 Deadlock이 발생했는지 체크한다.
• Deadlock이 발생해서 시스템 전체가 안 움직이는 상태가 되기 전에 OS가 deadlock을 발견해서 시스템을 안전하게 복구

A Common Detection Algorithm

• allocation matrix = 실제로 각각의 프로세스들한테 자원을 얼만큼 할당해줬는지 나타낸다. deadlock이 아니더라도 OS가 관리해야하는 정보
• allocation vector = available vector
• resource vector = 시스템 안에 원래 자원이 몇 개씩 있는지에 대한 정보
• request matrix = OS가 각각의 프로세스가 어떤 자원을 요청했는지 알아야 한다.

Detection Algorithm

deadlock이 아니라고 확신되는 프로세스를 하나씩 마크한다. 알고리즘을 다 실행시키고 나서 모든 프로세스가 마크되어 있으면 deadlock이 존재하지 않는다.

1. allocation matrix 값이 전부 0인 프로세스를 제일 먼저 마크한다. allocation matrix가 다 0 이라는 말은 프로세스가 홀드하고 있는 자원이 없다는 뜻이다. 따라서 deadlock 2번째 조건인 hold-and-wait 조건에 위배된다.
2. available vector(allocation vector)를 임시변수 w에다가 카피한다.
3. available vector와 request matrix값을 비교한다. request 값이 available vector 값보다 작거나 같은 프로세스를 찾는다. request한 만큼 자원이 있어야 하기 때문이다.
4. 그런 프로세스가 있다면 마크하고 자원을 반납한다. w에다가 allocation matrix 값을 더한다.

위 그림에서는 P4, P3만 마크되고 P1, P2는 마크되지 않는다. 이 뜻은 P1과 P2는 deadlock에 빠져있다고 할 수 있다.

또는 resource allocation 그래프를 통해 알아볼 수도 있다.

Recovery Strategies Once Deadlock Detected

Deadlock에 걸린 Process ⇒ 복구 X ⇒ Terminate O

Recovery : Deadlock Process 복구가 아닌, Deadlock Process를 Terminate해서 시스템 전체 복구

시스템 복구 방법

• Deadlock 프로세스 전부 Terminate
• 순차적으로 프로세스 Terminate
  • 1개의 사이클 ⇒ 1개의 프로세스만 Terminate시켜도 해결 가능
  • 사이클이 2-3개 얽혀있을 수 있음
• Deadlock 발생 ⇒ Deadlock에 걸린 모든 프로세스 다시 실행 시작
  • Deadlock 발생 ⇒ 가장 마지막 저장 상태부터 다시 실행
• Deadlock 발생 ⇒ Deadlock에 걸린 여러 프로세스 중 사이클 당 한 명씩 골라서 마지막 단계부터 다시 실행

Dining Philosophers Problem

• 철학자는 5명, 포크 5개
• 철학자 포크 2개 사용
• 어떤 두 철학자도 같은 포크를 동시에 사용 불가
• 어떤 철학자도 굶주려서는 안된다.

First Solution Using Semaphores

• Deadlock 발생 코드
• 5개의 포크는 semaphores로 구성
• 모든 철학자가 포크 하나씩 잡고 Deadlock에 걸릴 수 있음

Avoiding Deadlock

• Deadlock이 발생하지 않는 솔루션
  • 생각을 하는 공간과 밥을 먹는 공간 분리
• room을 먼저 통과해야 한다.
  • 전체 5명 중 최대 4명만 방에 들어갈 수 있다.
• 한 사람은 오른쪽 포크까지 잡을 수 있음
  • 5명이 있지만 4명만 room을 통과하기 때문에 한 사람은 포크 2개를 잡을 수 있게 된다.

💡Circular Wait를 prevent하는 방식으로 철학자 문제를 해결하려면 코드를 어떻게 변경해야 할까?

if ((i+1) mod 5 < i) {
		wait(fork[(i+1) mod 5]);
		wait(fork[i]);
		eat();
		signal(fork[i]);
		signal(fork[(i+1) mod 5]);
}
else {
		wait(fork[i]);
		wait(fork[(i+1) mod 5]);
		eat();
		signal(fork[(i+1) mod 5]);
		signal(fork[i]);
}

A solution using a monitor

여러 철학자가 get_forks 함수를 실행하려고 해도 한 번에 한 명씩 모니터 안에 들어가서 get_forks 함수를 실행한다.

get_forks 함수 안에서는 포크 2개를 다 잡는다. 2개를 다 잡으면 밥을 먹고 포크를 놓는다. 놓는 작업 역시 모니터 안에서 진행한다.

그러나 모니터 안에 들어갔다고 해서 포크 두 개를 다 잡는다는 보장은 없다.

fork 값이 true ⇒ 사용 가능

fork 값이 false ⇒ 사용 불가

포크가 사용중이라면, cwait를 통해서 모니터 밖에 있는 큐에서 기다린다.

💡deadlock이 발생하는 semaphore 코드와 유사한데 deadlock이 발생하지 않는 이유는?

모니터를 사용하고 있기 때문 X, 포크를 잡지 못했을 때 모니터 밖에 있는 큐에서 기다리기 때문 X

왼편 fork를 잡는데 성공한 philosopher는 오른편 fork의 점유여부를 확인하는 작업을 마칠때까지 monitor를 떠나지 않기 때문이다. 즉, 철학자 1이 왼편잡고 타임아웃 = 모니터를 빠져나간 것이 아니다. 따라서 다른 철학자가 get_forks 함수로 들어갈 수 없다.

UNIX의 병행성 기법

다양한 형태의 동기화와 Mutual Exclusion을 해결하는 방법이 있다.

• Pipe
• Message Passing
• Shared Memory
• Semaphore
• Signal

Solaris의 Thread 동기화 기법

• Mutex locks
• Semaphore
• Multiple readers, single writer locks
• Condition variable

Windows의 병행성 기법

• Mutex
• Semaphore
• Waitable timer
• Event
• Reader-Writer locks