[OS] Deadlock handling (1)

Deadlock handling

Deadlock 이 발생하지 않도록 막는 방법

Deadlock prevention

직접적으로 4가지 조건을 막는 방법. 장치 사용률/시스템 처리량 저하

• Mutual exclusion : 공유 가능한 자원은 배타적 접근을 요구하지 않음 (공유해야 되는것만 공유하자)

• Hold and wait : 이미 공유 자원을 점유한 프로세스는 다른 자원을 요청할 수 없음

• 프로세스 실행 시 모든 자원을 할당 받은 뒤 실행 : 낮은 자원 이용률

• 이미 가진 자원을 release 한 상태에서만 요청 가능 : Starvation 발생 가능
  A 를 가지니 B가 필요하고, B를 위해 A를 해제하니 A가 다시 필요해져서 무한히 반복..

• No preemption : 이미 공유 자원을 점유한 프로세스가 즉시 할당 받을 수 없는 자원을 요청 시 현재 갖고 있는 모든 자원을 해제함
  CPU 레지스터, 메모리와 같이 상태가 쉽게 저장/복원 되는 경우에 사용

• Circular wait : 모든 자원 타입에 순서(order)를 부여, 각 프로세스는 정해진 순서(오름차순 혹은 내림차순)으로만 자원 요청 가능
  : 성능이 크게 저하

Deadlock avoidance

프로세스에게 미리 필요한 자원 정보를 요청하여 OS가 데드락 가능성을 판단하여 회피 (더 방어적인 방법)

• 각 프로세스가 필요한 최대치의 리소스를 미리 요청

• 동적으로 리소스 할당 상태를 파악

• available 자원의 수, allocated 자원의 수, maximum 자원을 미리 정의

• Safe state 에서 Safe state 로의 이동만을 허용

• Safe state = 데드락이 발생할 확률이 0인 상태

• Safe state = Pi 가 (현재 available resource) + (P1 ~ Pi-1의 allocated resource) 로 해결 가능하다면 Pi 는 Safe

• 모든 P 가 safe 한 경로가 1개라도 존재한다면 safe state 에 있다고 한다.

• Pi 가 현재 available 한 리소스만으로 해결 가능하다면 바로 safe 판정

• 그렇지 않다면 j < i 인 Pj 가 끝나기를 기다림 → Pj 가 terminate 되면 Pj 의 자원을 할당받기 위함

• Unsafe state = Deadlock 이 발생할 확률이 0이 아닌 상태

• Deadlock state = Deadlock 이 발생한 상태

Single instance resource type Deadlock avoidance

데이터를 요청해도 되는지 물어보는 Claim edge 가 추가된 Resource allocation graph 를 그리고, cycle 이 있는지 확인

위 경우 Deadlock 이 발생할 수 있음

Multiple instance resource type Deadlock avoidance

Banker’s 알고리즘

자원의 최대 개수를 허용했을 때에도 Safe state 에 있는지 판단

 

변수 정의

n = 프로세스의 수, m = 리소스 타입의 수

available[m] = 리소스 인스턴스를 표현하는 배열. 예) available[2] = 8  : 2번 리소스의 인스턴스는 8개

max[n][m] = 각 프로세스가 최대로 요구할 리소스의 크기   예) max[1][2] = 6  : 1번 프로세스가 2번 리소스를 최대 6개 요청

allocation[n][m] = 할당된 리소스의 크기  예) allocation[2][3] = 3 : 2번 프로세스가 3번 리소스를 3개 할당받음

need[n][m] = 필요한 리소스의 크기 = max[n][m] - allocation[n][m]

request[n][m] = 프로세스가 리소스를 요청  예) request[2][3] = 3 : 2번 프로세스가 3번 리소스를 3개 요청

 

Safety 알고리즘 : 현재 상태가 safe 인지 확인

 

1. Work = Available
   Finish[0 ~ n -1] = false 

2. Finish[i] = false, need[i] < Work 를 만족하는 i 를 찾음. 없으면 4번으로 이동

3. Work = Work + alloction[i]
   Finish[i] = true   // 프로세스 i 는 종료됨을 의미. 2번으로 이동

4. Finish가 true 이면 safe
   false 인 Finish 가 하나라도 존재하면 Deadlock 발생 가능함

 

P[i] 의 리소스 요청을 처리하는 알고리즘

1. request[i] <= need[i] 이면 2번으로 이동, request[i] > need[i] 는 에러 (최초에 등록한 max 보다 더 많은 양의 리소스를 요청했기때문)

2. request[i] <= available 이면 3번으로 이동, request[i] < available 이면 당장은 줄 수 없으므로 다른 프로세스가 종료되어 리소스가 해제되길 기다림

3. 해당 request[i] 를 받아줌

1. available = available - request;

2. allocation[i] = allocation[i] + request[i];

3. need[i] = need[i] - request[i];

4. safety 알고리즘을 수행하여 safe 이면 리소스를 할당

5. unsafe 이면 P[i] 는 대기상태로 가며 기존 resource-alloction-state 로 복구됨

계산 방법

1. max - allocation 을 하여 need 를 구함

2. 요청 값이 need 보다 작거나 같은지 확인

3. 요청 값이 available 보다 작거나 같은지 확인

4. Allocation + 요청값 <= Max 인지 확인 (타당성 검사)

5. Need = Need - 요청값
   Need 가 모두 0인 프로세스 i는 Available += Allocation[i]

6. safety check