[운영체제(OS)] 8-2) 교착상태(Deadlock) 예방, 회피

---

1. 교착상태(Deadlock) 처리 방법

1) 문제를 무시하고 교착상태가 절대 발생하지 않는 척(?)하기

: 교착상태를 해결하는 데 비용이 더 많이 들기 때문에 무시합니다. 교착상태가 지속될 경우 시스템 성능을 저하시킬 수 있기 때문에 수작업으로 다시 시작해야할 필요가 있습니다.

2) 교착상태를 예방, 회피하는 protocol을 사용

- 예방 : 교착상태 발생 조건 4가지 중 적어도 하나 이상 성립하지 않도록 합니다.

- 회피 : 프로세스가 사용할 리소스에 대한 부가적인 정보를 얻은 후에 프로세스를 기다려야할지 결정합니다.

3) 교착상태를 허용한 후 회복

: 교착상태가 발생했는지 조사하는 알고리즘, 복구 알고리즘을 사용합니다.

 

---

2. 교착상태(Deadlock) 방지 방법 (조건 중 하나만 끊어도 방지 가능)

1. 상호 배제(Mutual exclusion) => 공유 가능한 리소스를 설정합니다. (ex) 읽기 전용 파일을 설정

2. 점유 대기(Hold and wait) 

=> 프로세스가 작업을 수행하기 전 필요한 리소스를 모두 요청 및 획득(최대 자원 할당 방식)하도록 합니다. 

=> 스레드가 리소스을 전혀 가지고 있지 않을 때만 요청이 가능하도록 하며, 요청할 때 자신이 가진 리소스를 모두 방출하도록 합니다.

단점으로는 여러 리소스가 필요한 스레드는 무한정 대기하게 되어 기아 발생 가능성이 있고, 리소스가 장기간 사용되지 않아 리소스 이용률이 낮을 수 있습니다.

3. 비선점(No preemption) => 이미 할당된 자원에 선점권이 없어야 합니다. 즉, 스레드가 점유할 수 없는 리소스(대기가 필요)를 요구하면 그 스레드는 점유하고 있는 리소스를 모두 방출합니다. 따라서 기존에 사용중이던 프로세스가 작업 내용을 잃을 수 있는 단점이 있습니다.

4. 순환 대기(Circular wait) => 리소스에 resource type을 부여하여 순서를 할당하여 번호 순서대로 리소스를 요청하도록 합니다. 작업에 필요한 리소스는 오래 전부터 할당받아야 하므로 자원 낭비 가능성이 있습니다.

 

 

하지만 방지 알고리즘은 리소스 요청 방법에 제한을 두기 때문에 시스템의 총처리율이 감소할 수 있습니다. 따라서 이어지는 교착상태 회피 대안을 알아보겠습니다.

 

---

3. 교착상태(Deadlock) 회피 방법

: 리소스가 어떻게 요청될 지에 대한 추가 정보를 요구합니다. 현재 가용 리소스, 각 스레드에 할당되어 있는 리소스, 앞으로 각 스레드가 요청하거나 방출할 리소스의 정보를 고려합니다.

 

상태를 안전 상태(safe state), 불안전 상태(unsafe state)로 분류하는데, 안전 상태를 유지할 수 있는 요청만을 수락하고, 불안전 상태일 경우 안전 상태로 바뀔 때까지 계속 거절합니다.

- 안전 상태(safe state) : 안전 순서(safe sequence)를 찾을 수 있음.

- 불안전 상태(unsafe state) : 안전 순서(safe sequence)를 찾을 수 없음. 불안전 상태가 교착 상태를 의미하지는 않으며, 그럴 확률이 있다는 것을 의미합니다.

 

교착상태 회피의 가장 단순하고 유용한 모델은 각 스레드가 자신이 필요로 하는 리소스를 유형마다 최대 수를 선언하도록 하는 것입니다.

<T(1), T(2), ..., T(n-1), T(n)> 와 같은 안전 순서가 있다는 것은 T(n-1)이 작업을 완료하고 방출하는 리소스로 T(n)의 필요 리소스 최대 수를 충족시켜 줄 수 있음을 의미합니다.

T(m)이 리소스를 요구할 때 당장 리소스를 할당해줄 수 있더라도, 할당해준 후 불안전 상태가 된다면 리소스 할당을 거절합니다.

 

 

* 뱅커스 알고리즘(Banker's Algorithm)

- 뱅커스 알고리즘에 쓰이는 변수

* n = 프로세스의 수

* m = 리소스의 수

1) 최대요구자원(Max. 프로세스 별 최대 자리소스의 요구) : 각 프로세스가 최대로 필요로 하는 리소스의 개수를 나타내는 행렬[n][m].

2) 현재 점유랑(Allocation. 프로세스 별 할당 리소스의 수) : 각 프로세스가 점유하고 있는 리소스 개수를 나타내는 행렬[n][m].

3) 필요량(Need. 프로세스 별 남아있는 리소스의 수) : 각 프로세스가 이후 요청할 수 있는 리소스의 개수를 나타내는 행렬[n][m].

4) 현재여유자원(Available. 사용 가능한 리소스의 수) : 각 종류별로 이용 가능한 리소스의 개수를 나타내는 배열.

 

- 안전성 알고리즘 : 

1) Work[m], Finish[n] 배열이 각각 존재하며, Work는 Available로 초기화하고, Finish는 false로 초기화합니다.

2) Finish[n(i)] == false, Need[n(i)][m(j)] <= Work[m(j)]

위의 조건을 만족하는 i가 없다 = 안전 상태.

i가 있다 => Work[m(j)] = Work[m(j)] + Allocation[n(i)], Finish[n(i)] = true 로 만들어줌.

 

- 자원 요청 알고리즘 : Request[n]가 스레드 T[n]의 리소스 요청 배열.

1) Request[n(i)] <= Need[n(i)] 조건을 만족하지 않으면 오류로 처리합니다.

2) 1 조건 만족 => Request[n(i)] <= Available 조건을 만족하지 않으면 대기합니다.

3) 2 조건 만족 =>

Available = Available - Request[n(i)]

Allocation[n(i)], = Allocation[n(i)], + Request[n(i)]

Need[n(i)] = Need[n(i)] - Request[n(i)]

시스템의 상태를 다음과 같이 바꿨을 때 안전한 상태일 경우 자원을 할당해줍니다.