운영체제론[13]: 데드락

시스템 모델

시스템은 리소스로 구성되며, 리소스 유형(CPU 사이클, 메모리 공간, 입출력 장치 등) R1, R2 ... Rm이 존재한다.

각 리소스 유형 Ri는 Wi개의 인스턴스를 갖는다.

각 프로세스는 리소스를 요청-사용-해제 로 사용한다.

 

 

데드락 in 멀티스레드 프로그램

데드락은 스레드 1이 first_mutex를 확보하고, 스레드가 2가 second_mutex를 확보할 때, 스레드 1이 second_mutex를 기다리고 동시에 스레드 2가 first_mutex를 기다릴 때 발생할 수 있다.

라이브락은 데드락처럼 스레드가 멈추진 않았지만 계속 시도해도 진행이 안되는 경우에 발생한다.

 

데드락은 네 가지 조건이 동시에 성립할 때 발생한다. (필요조건)

상호배제(Mutual exclusion): 한 번에 하나의 프로세스만 리소스를 사용할 수 있음 (적어도 하나의 자원이 공유 불가하다)

대기 및 보유(hold and wait): 최소한 하나의 리소스를 가지고 있는 프로세스가 다른 프로세스가 보유한 추가 리소스를 얻기 위해 대기함

비선점(no preemption): 리소스는 보유한 프로세스가 자발적으로 해제될 때만 릴리즈됨, 그 프로세스가 작업을 완료한 후에 해제된다.

순환대기(circular wait):  대기 프로세스 집합 P0 ... Pn이 존재하고, P0은 P1이 보유한 리소스를 대기, Pn-1은 Pn이 보유한 리소스를 대기, Pn은 P0이 보유한 리소스를 대기한다.

 

 

자원 할당 그래프

정점 집합 V와 간선 집합 E에 대하여,

V는 두 가지 유형으로 분할된다.

P = {P1,,,Pn}: 시스템 내 모든 프로세스로 구성된 집합

R = {R1,,,Rm} : 시스템 내 모든 리소스 유형으로 구성된 집합

요청 간선(request edge): 방향성이 있는 간선 Pi -> Rj

할당 간선(assignment edge): 방향성이 있는 간선 Rj -> Pi

 

 

 

R1, R3의 인스턴스 각각 1개

R2 인스턴스 2개

R4 인스턴스 3개

 

T1은 R2의 인스턴스 1개를 보유, R1의 인스턴스 1개 대기중

T2는 R1과 R2의 인스턴스 1개 보유, R3의 인스턴스 1개 대기중

T3는 R3의 인스턴스를 1개 보유중이다.

 

 

 

 

 

 

 

 

 

 

 

 

만약 T3가 R2의 인스턴스를 대기하게 되면, 사이클이 발생한다.

사이클이 발생하는 경우에 데드락이 발생할 수 있다.

 

만약 single instance에서 사이클이 발생하면 무조건 데드락이 발생한다.

multiple instsance에서는 데드락이 발생했다면 사이클이 존재하는 것이지만, 사이클이 존재한다고 무조건 데드락이 발생하지는 않는다.

 

 

 

 

 

 

시스템이 데드락이 걸리지 않게 보장하려면, 데드락을 회피하거나 예방해야한다.

- 시스템이 데드락에 진입한 후 recover할 수 있도록 허용한다. (데이터베이스 시스템에서 사용)

- 문제를 무시하고 시스템에서 데드락이 발생하지 않는 것처럼 가정한다. (대부분 OS에서 사용, 비용이 저렴하기 때문)

 

 

 

데드락 예방(prevention)

데드락에 대한 네 가지 필요 조건 중 하나를 무효화 시킨다.

 

상호배제 : 공유 불가능한 자원에는 필요하다. (이 조건을 막기는 어려움)

 

대기 및 보유 : 어떤 프로세스가 자원을 요청할 때, 다른 자원을 보유하지 않도록 보장해야한다. 프로세스가 실행을 시작하기 전에 모든 자원을 요청하고 할당받도록 요구하거나, 프로세스가 자원을 요청할 때 자원이 할당되지 않은 경우에만 요청을 허용한다.

=> 자원 이용률이 낮아지고 굶주릴 수 있음.

 

비선점 : 어떤 프로세스가 일부 자원을 보유한 상태에서 즉시 할당할 수 없는 다른 자원을 요청할 때, 현재 보유 중인 모든 자원을 해제한다. 선점된 자원은 해당 프로세스가 대기 중인 자원 목록에 추가되고, 프로세스는 이전의 자원과 함께 요청하는 새로운 자원을 모두 재획득 할 수 있을 때 다시 시작된다. (자원 할당이 불가능하면 가지고 있는 모든 자원을 내려놓고, 자원을 다 할당받을 수 있을 때 재시작)

 

순환대기 : 가장 현실적인 방법으로 모든 자원 유형에 대한 전체적인 순서를 부여하고, 각 프로세스가 열거 순서에 따라 자원을 요청하도록 요구한다. 각 자원에 고유한 번호를 할당하고, 순서대로 획득되어야 한다.

 

 

데드락 회피(avoidance)

시스템에 추가적인 사전 정보가 제공되어야 한다.

가장 간단하고 유용한 모델은 각 프로세스가 필요로 할수 있는 각 유형의 최대 자원수를 선언한다.

데드락 회피 알고리즘은 자원 할당 상태를 동적으로 검사해서, 순환 대기 조건이 발생하지 않도록 보장한다.

자원 할당 상태는 사용 가능한 자원 수, 할당된 자원 수, 프로세스의 최대 요구량에 의해 정의된다.

 

프로세스가 사용 가능한 자원을 요청할 때, 시스템은 즉시 할당하더라도 시스템이 안전한 상태(safe state)에 머무르는지 결정한다.

시스템이 안전한 상태에 있다는 것은 시스템 내의 모든 프로세스가 각자 필요한 자원을 사용할 수 있는 실행 순서가 존재할 때 우리는 시스템이 안전한 상태에 있다고 말한다.

 

 

deadlock avoidance algorithm for single instance of a resource type

single instance에서는 자원할당그래프를 사용한다.

Claim edge Pi -> Rj 는 Pi가 앞으로 Rj를 요청할 수도 있다는 것을 뜻하며 점선으로 표시된다.

프로세스가 리소스를 요청하면 Claim edge는 Request edge로 변환된다.

리소스가 프로세스에 할당되면 Request edge는 Assignment edge로 변환된다.

프로세스가 리소스를 해제하면 Assignment edge는 Claim edge로 변환된다.

리소스는 시스템에서 사전에 선언되어야 한다.

 

만약 Request edge에서 Assignment edge로 변환했을 때, 자원할당그래프에서 사이클이 형성된다면 요청을 승인하지 않는다.

 

 

deadlock avoidance algorithm for multiple instance of a resource type

multiple instance에서는 은행원알고리즘을 사용한다.

각 프로세스는 사전에 최대 사용량을 선언해야한다.

프로세스가 리소스를 요청하면 대기해야 할 수도 있다.

프로세스가 모든 리소스를 획득하면 유한한 시간 내에 리소스를 반환해야한다.

 

n을 프로세스의 개수, m을 리소스 유형의 개수라고 할 때,

Available : 길이가 m인 벡터, Available[j] = k 이면 리소스 유형 Rj의 인스턴스 k개가 현재 사용 가능하다.

Max : n*m 행렬, 만약 Max[i,j] = k 이면 프로세스 Pi는 리소스 유형 Rj의 최대 k개의 인스턴스를 요청할 수 있다.

Allocation : n*m 행렬, 만약 Allocation[i,j] = k 이면 프로세스 Pi는 현재 Rj의 인스턴스 k개를 할당받았다.

Need : n*m 행렬, 만약 Need[i,j] = k 이면 프로세스 Pi는 작업을 완료하기 위해 Rj의 추가적인 k개의 인스턴스가 필요할 수 있다. 

* Need[i,j] = Max[i,j] - Allocation[i,j]

 

Safety algorithm : 시스템이 안전 상태에 있는지를 판별하는 알고리즘

 

1. Work와 Finish라는 두 벡터 선언. Work는 현재 사용 가능한 자원을 나타내고, Finish는 각 프로세스가 필요한 자원을 모두 얻었는지 여부를 나타냄. Work는 사용 가능한 모든 자원으로 초기화되고, Finish는 False로 초기화된다.

 

2. 다음 두 조건을 모두 만족하는 프로세스 i를 찾는다.  (Finish[i] == false && Need(i) <= Work)

   존재한다면 프로세스 i가 자신이 필요로하는 자원을 얻었으므로 Work에 프로세스 i가 가지고 있던 자원 Allocation(i)를 추가한다.

   그리고 해당 프로세스의 Finish[i]에 true를 설정해서 프로세스 i가 필요한 자원을 모두 얻었음을 표시한다.

   위 과정을 그러한 조건을 만족하는 프로세스 i가 없을 때까지 반복한다.

 

3. 만약 모든 프로세스에 대해 finish[i]가 true이면 시스템은 안전 상태에 있는 것이다.

 

 

Resource Request Algorithm : 프로세스 Pi가 자원을 요청했을 때, 이를 할당했을 때 안전하다면 할당하고 그렇지 않으면 대기상태로!

 

1. 프로세스 Pi가 요청한 자원의 양인 Request(i)가 Pi가 필요로 하는 자원 최대 양인 Need(i)보다 작거나 같은지 확인. 만약 크다면 프로세스가 최대 요구량을 초과하여 자원을 요청한 것이므로 오류를 발생시킨다.

 

2. Request(i)가 Available보다 작거나 같은지 확인. 만약 크다면 요청한 자원이 현재 사용 불가하므로 프로세스 Pi는 대기 상태로 들어간다.

 

3. 가상으로 요청한 자원을 프로세스 Pi에게 할당하고 상태를 업데이트한다.

    Available = Available - Request(i) // 사용 가능한 자원에서 요청한 자원을 뺌

    Allocation(i) = Allocation(i) + Request(i) // 프로세스 Pi에게 할당된 자원에 요청한 자원을 추가함

    Need(i) = Need(i) - Request(i) // 프로세스 Pi가 필요로 하는 자원에서 요청한 자원을 뺌

이렇게 업데이트 된 상태를 Safety algorithm으로 안전한지 확인한다.

 

만약 안전하다면 요청한 자원을 실제로 Pi에게 할당하고, 그렇지 않다면 이전으로 복구하고 Pi는 대기 상태로 들어간다.

 

 

 

Single Instance of Each Resource Type

Resource-allocation graph에서 resource를 뺀 것이다.

대기 그래프에서, 노드가 프로세스, 한 프로세스가 프로세스를 기다리고 있다면 그 사이에 간선이 형성된다. Pi가 Pj를 기다리고 있다면 Pi -> Pj라고 표기한다.

주기적으로 그래프에서 사이클을 탐색하는 알고리즘을 호출한다. 그래프에 사이클이 존재한다면 데드락이 걸린 것이다. 그래프에서 사이클을 탐지하는 알고리즘은 그래프의 정점 수를 나타내는 n에 대해 n^2의 연산이 필요하다.

 

Available : 길이가 m인 벡터, 리소스 유형 R[i]의 사용 가능한 인스턴스 수

Allocation :  n*m 행렬, Allocation[i][j]는 Pi에 할당된 Rj의 인스턴스 수

Request : n*m 행렬, Request[i][j]=k는 Pi가 Rj의 인스턴스를 k개 요청했음을 뜻한다.

 

Deadlock Avoidance와 비교하였을 때 Max가 없는 대신 현재 Request를 Need로 간주한다. 여기서 unsafe state이면 데드락으로 판정한다.

 

1. work = available,  finish[n]은, allocation[i][1]~allocation[i][m]의 값이 모두 0이면 finish[i]를 false로 초기화 (아니라면 true)

 

2. finish[i]가 false이고 request[i]가 work보다 작거나 같은 인덱스 i를 찾는다.

그런 인덱스 i가 있다면 work[i] = work[i] + allocation[i], finish[i] = true를 수행한다.

그런 인덱스 i가 없을 때까지 반복한다.

 

3. 모든 finish가 true라면 데드락에 걸리지 않은 것이고, false가 있다면 데드락에 걸린 것이다.

 

 

만약 deadlock detection 알고리즘을 아무 때나 수행하면 이를 유발한 스레드를 식별하지 못할 수 있다.

자원요청이 실패할 때 수행하면 이를 유발한 스레드를 식별하는데 도움이 된다.

 

 

데드락 해결 방법 : 프로세스 종료

다음은 데드락이 발생했을 때 프로세스 중단 순서를 결정할 때 고려할 요소이다.

1. 프로세스의 우선순위

2. 프로세스가 실행된 시간과 완료까지 남은 시간

3. 프로세스가 사용한 리소스

4. 프로세스가 완료하기 위해 필요한 리소스

5. 중단될 프로세스의 수

6. 프로세스가 대화형인지 배치(batch)인지 여부

 

프로세스를 강제로 종료하면 시스템 불일치 상태가 발생할 수 있다.

 

 

피해 프로세스(victim) 선택 : 시스템 자원이나 성능에 최소한의 영향을 주는 프로세스로

롤백 : 피해 프로세스를 안전한 상태로 되돌림. 프로세스를 이전의 안전한 상태로 복원하고 그 상태에서 프로세스를 재시작한다.

기아 현상 : 항상 같은 프로세스가 피해를 받을 수 있고, 이를 통해 롤백 횟수가 증가하는 경우가 발생할 수 있다. 따라서 롤백 횟수를 고려하여 피해 프로세스를 선택한다.