[운영체제] 데드락

자료 출처 : https://www.os-book.com/OS10/slide-dir/index.html

데드락

두개 이상의 프로세스들이 한 순간에 하나의 프로세스만 달성할 수 있는 작업을 동시에 수행하기 위해 상대 프로세스가 가지고 있는 자원을 계속 요구하여, 결과적으로 프로세스 진행이 멈추는 상태이다.

프로세스 P1 및 P2 가 공유 자원에 대한 세마포어 s1 및 s2를 사용하는 상황을 생각해보자. 만약 P1 및 P2 가 동시에 실행되면 P1은 s1, P2는 s2의 사용권을 가진 후 상대방에게 나머지 세마포어에 대한 사용권을 요구하게 된다. 이때 위 코드에서 별다른 수단이 없는 경우 P1 및 P2는 각각 s1 및 s2를 놓지 않고 무기한 자원 할당을 기다리는데, 이게 데드락이다.

def transaction(from, to, amount):
    lock1 = get_lock(from)
    lock2 = get_lock(to)
    
    acquire(lock1)
    acquire(lock2)
    
    withdraw(from, amount)
    withdraw(to, amount)
    
    release(lock2)
    release(lock1)

위에서 P1 및 P2는 서로 요청 순서가 다르기 때문에 데드락이 발생했다. 그렇다면, 동일 순서를 사용하면 데드락이 발생하지 않을까? 위 코드는 은행에서 거래에 대한 트랜잭션을 나타낸 것이다. 모든 사람이 동일한 함수를 이용하므로 lock1 및 lock2의 위치가 동일하여 데드락이 발생하지 않을 것이라고 짐작할 수 있다.

transaction(Tom, John, 100)
transaction(John, Tom, 200)

그러나 실제로는 위 코드도 데드락이 발생할 수 있다. 첫번째 함수 실행에서는 from = Tom / To = John 이고, 두번째는 반대의 상황을 띄고 있다. 실제 코드상에 해당 실 매개변수들이 적용되면 P1과 P2의 관계와 동일해진다. 즉, 데드락은 해당 자원 자체가 순환적으로 구성되는지 여부가 더 중요하다.

데드락의 특성

데드락은 다음 조건을 동시에 만족할 때 발생한다.

Mutual Exclusion
: 한 순간의 하나의 프로세스만이 자원을 이용할 수 있다.
Hold and wait
: 최소 하나의 자원을 들고 있는 프로세스는 다른 프로세스로부터 추가적인 자원을 요구하면서 기다린다.
- 철학자 문제에서 자신의 젓가락을 들고 다른 자원이 남기를 기다리는 상황 등 ...
No preemption
: 현재 프로세스의 작업이 끝나기 전에는 할당된 자원을 자발적으로 해제하지 않는다.
Circular wait
: 여러개의 프로세스 P0 ~ Pn 이 있을 때, P0은 P1의 자원을 ... Pn 은 P0의 자원을 요구하는 상태.
- 프로세스 자원 요청 관계에서 순환 관계가 나타나는 경우

Resource-Allocation Graph

정점 V와 간선 E의 형태로 나타낸다.

V
- P : 각각의 프로세스를 의미.
- R : 시스템 내의 리소스 "타입" 을 의미.
E
- request edge : 프로세스가 리소스에 대해 자원을 요청하는 관계. P -> R
- assignment edge : 프로세스가 리소스를 할당받은 관계. R -> P
- claim edge : P가 R을 요구할수도 있는 관계. P ---> R
  - 실제로 프로세스가 요청하는 경우 request edge로 바뀐다.
  - 프로세스가 리소스 할당을 해제하면 assignment edge가 claim edge로 바뀐다.

Resource Allocation Graph 예시

(좌측)

T1 : R1의 자원을 요청, R2의 자원을 할당.
T2 : R1 및 R2의 자원 할당, R3의 자원 요청
T3 : R3의 자원 할당.

자원 사이에서 circular wait 없으므로, 데드락 X

(우측)

T1은 T2가 할당받은 R1을 요구하고, T2는 T3가 할당받은 R3을 요구하며 T3는 T1 및 T2가 할당받은 R2을 요구하는 상황이므로, Circular Wait가 발생하여 데드락 현상이 나타난다.

데드락에 대한 사실

그래프에 순환 구조가 없다면, 데드락이 발생하지 않는다.
그래프에 순환 구조가 있을 때,
- 하나의 리소스 타입에 하나의 인스턴스만 가지고 있다면, 데드락이 발생한다.
- 하나의 리소스 타입이 여러 인스턴스를 가진다면 데드락이 발생할 수도 있다.

데드락을 다루는 방법

시스템 상에서 데드락 상태가 절대 발생하지 않도록 보장한다.
- Deadlock prevention
- Deadlock avoidance
데드락이 발생할 수는 있는데, 발생하면 시스템이 해당 상태를 복구한다.
데드락이 발생하더라도 시스템은 데드락이 발생하지 않은 것처럼 간주하며 동작한다.
- 의외로 많은 운영체제가 이 방식을 채택한다고 한다.

Deadlock Prevention

데드락은 앞서 언급한 4가지 성질 ( Mutual Exclusion, Hold and Wait, No preemption, Circular Wait ) 을 모두 만족하는 시스템에서 발생할 수 있다. 따라서 데드락을 예방하기 위해서는 4가지 조건 중 하나만 관리하면 된다.

Mutual Exclusion
: 상호 배제는 공유 자원에 동시에 접근할 때 발생하는 동기화 문제에서 나온 개념이다. 따라서 프로세스 사이의 공유 자원을 없애고, 각각이 개인적인 자원을 이용하면 된다.
Hold and Wait
: 프로세스들이 특정 자원을 들고 있는 상태에서 다른 자원을 요청하는 상황에서 발생하는 문제를 해결하면 된다.
프로세스가 실행되기 위한 모든 자원을 실행하기 전에 미리 모두 할당받고 시작하여 일단 프로세스가 진행되는 동안은 자원을 할당받지 않게 한다.
No Preemption
: 특정 프로세스가 실행되는 와중에 다른 자원을 요구하는 상황이 발생하면, 현재 가지고 있는 자원을 모두 반환한 후, 기존 자원 및 요구 자원을 모두 사용할 수 있는 경우 다시 시작한다.
응답성이 감소하고, 비효율성이 증가할 수 있다.
Circular Wait
: 모든 리소스 타입에 대해 일종의 순서를 매긴 후, 자원이 할당될 때마다 순환이 발생하는지 여부를 그래프 알고리즘 등을 통해 체크한다. 만약 순환이 발생하면 해당 요청은 무시될 수 있다.

Deadlock Avoidance

시스템 상에서 데드락이 발생하는지 여부를 지속적으로 검사하고, 발생한다고 판단된 경우 이를 막는다.

각각의 프로세스에 요구되는 리소스 타입의 최대 개수를 명시한다.
Circular wait 조건이 발생하지 않도록 동적으로 리소스 할당을 검사한다.
Resource-Allocation state : 현재 할당된 자원의 개수 및 요구하는 최대 개수

	요구 자원	현재 자원
P0	10	5
P1	4	2
P2	9	2
남은 자원	-	3

전체 자원 R = 12 이고, 현재 P0, P1, P2에 자원이 위와 같이 할당된 경우, 남은 자원은 3개이다.

	요구 자원	현재 자원
P0	10	5
P1	4	4 ( 2 + 2 )
P2	9	2
남은 자원	-	1 ( 3 - 2 )

P1이 자원 2를 추가로 할당받아 실행된 후에는 할당된 자원 4를 반환하며 종료된다.

	요구 자원	현재 자원
P0	10	10 ( 5 + 5 )
P2	9	2
남은 자원	-	0 ( 5 - 5 )

P0이 현재 자원 5를 이용하여 실행된 후 자원 10을 반환하며 종료된다.

	요구 자원	현재 자원
P2	9	9 ( 2 + 7 )
남은 자원	-	3 ( 10 - 7 )

P2는 현재 가용 자원 10 중 7을 가져와 실행한 후 자원 9를 반환하고 종료된다.

Safe State

시스템에 대해 어떤 순서에 따라 각 프로세스에 자원을 할당할 수 있고, 여전히 데드락을 피할 수 있는 경우 시스템은 안전하다고 한다. 다음 조건을 만족하면 Safe State라고 말할 수 있다.

Pi는 Pj에게 할당되어 현재 사용할 수 없는 자원을 요청하기 위해 대기할 수 있다.
Pj가 끝나면 Pi는 해당 자원을 할당받아 실행하고, 자원을 해제한 후 종료된다.
Pi가 끝나면 Pi+1 역시 해당 자원을 할당받아 사용할 수 있고, 이런 과정이 <P1, ... , Pn> 에 대해 적용된다.

알려진 사실은 다음과 같다.

시스템이 safe state 이면, 데드락이 발생하지 않는다.
시스템이 unsafe state 이면, 데드락이 발생할 가능성이 있다. 데드락이면 반드시 unsafe state이지만, unsafe state라고 반드시 데드락 상황이 발생하는 것은 아니다.
Deadlock Avoidance는 시스템이 절대 unsafe state가 되지 않도록 보장하는 것이다.

Avoidance algorithms

리소스 타입 당 하나의 인스턴스를 가지는 경우
: resource-allocation graph을 이용하여 순환 그래프가 발생하는지 검사한다.
리소스 타입 당 여러개의 인스턴스를 가지는 경우
: Banker's Algorithm을 이용한다.

resource-allocation graph

직접 그래프를 그려서 cycle이 발생하는지 여부를 검사한다. 만약 사이클이 발생하면 request을 받아들이지 않는다. 이 방식은 각 리소스 타입에 하나의 인스턴스가 존재할 때 유효하므로, 그 이상의 경우에는 Banker's Algorithm을 사용한다.

Banker's Algorithm

각각의 리소스 타입이 여러개의 인스턴스를 가지는 경우 사용되는 알고리즘. 프로세스가 리소스에 대한 request을 할 때 해당 request가 수행되었을 때 safe state인지 여부를 검사하고, 검사 결과 safe state로 예측되는 경우에만 자원을 할당하는 방식으로 동작한다.

사용되는 변수들은 다음과 같다.

CUSTOMERS : 현재 실행중인 프로세스들의 수
RESOURCES : 전체 리소스 타입의 수
Available[RESOURCES] : 특정 리소스 Ri에 대해 현재 사용할 수 있는 인스턴스 수를 저장한 배열
Max[CUSTOMERS][RESOURCES] : 프로세스가 완료되는데 필요한 자원의 양
Allocation[CUSTOMERS][RESOURCES] : 프로세스에 현재 할당된 자원의 양
Need[CUSTOMERS][RESOURCES] : 아직 프로세스가 필요한 자원의 양.
- Need = Max - Allocation의 관계를 가진다.

Safety Algorithm

현재 조건에서 safe state sequence 가 만들어질 수 있는지 검사하는 알고리즘으로, 자원을 요청할 때 해당 자원을 할당한 이후에도 safe state가 유지될 수 있는지 여부를 검사하는데 사용된다.

#01. Work 및 Finish 배열 선언
Work = Available # 현재 사용 가능한 자원량. 직접 Available을 건드리면 안됨.
Finish = [False for _ in range(CUSTOMERS)] # 사람 수만큼

Work 및 Finish 배열을 선언한다.

Work : 현재 사용 가능한 자원량. safe state 검사를 수행할 때 현재 자원을 이용하여 전체 과정을 끝낼 수 있는지 여부를 시뮬레이션하는데 Available을 직접 건드리면 안되므로, Work을 선언하여 자원의 양만 복사해 사용한다.
Finish: 특정 프로세스의 작업이 종료되었음을 의미한다. 프로세스가 종료되면 할당된 자원을 반환한다.

#02. 종료 여부 및 종료 가능한지 검사 
for i in range(COSTOMERS):
    if Finish(i) == False and Need[i] <= Work:
#03. 종료 가능한 프로세스의 경우
        Work = Work + Allocation # 종료해서 자원 반환
        Finish[i] = True # 종료했다고 표시
        goto 02 # 계속 반복.
#04. 종료 여부 검사
for all i, if Finish == True:
    system = safe state

종료되지 않은 프로세스 중 종료될 수 있는 프로세스를 검사한다. 종료되는 경우 자원을 반환한다.
모든 프로세스들이 종료되면 safe state로 판정한다. for문을 계속 순회한 끝에 Finish의 값이 변경되지 않았으면서 모든 프로세스가 종료된 상태가 아니라면 unsafe state가 된다.

Resource Request Algorithm

Request[RESOURCES] : 특정 프로세스가 요구하는 자원의 양. 요구 자원량은 필요 이상(Need) 일 수 없고, 사용 가능량(Available) 이상일 수도 없다.

#01.
if Request <= Need: # 필요량 이하를 요청하면
    goto #02
else :
	raise Exception # 필요량 이상을 요청하면 안된다.
#02.
	if Request <= Available: # 사용 가능량 이하로 요청하면
        goto #03
    else: # 요청하는 양이 현재 사용 가능 자원보다 많다면
        reject request # 요청 거부
#03.    
    Available = Available - Request # 요청량만큼 자원 빼서
    Allocation = Allocation + Request # 자원 할당해주고
    Need = Need - Request # 필요 자원량 감소
#04. 할당된 상태가 safe state인지 검사
    if safe state :
        accept request # 할당 인정
    else : # unsafe이면
        restore Request # 자원 돌려받고
        reject request # 할당 거부

필요량 이하로 요청하면서 현재 가용 자원량 하에 있다면 자원을 할당한다. 할당한 후의 상태가 safe state가 된다면 자원 할당을 수락하여 실제로 자원을 프로세스에게 제공하고, 반대의 경우 자원을 돌려받으면서 할당을 거절한다.

Deadlock Detection

프로세스가 동작할 때마다 데드락을 회피하거나 검사하는 것은 성능적인 문제가 존재한다. 따라서 데드락을 지속적으로 검사하는 대신, 일정 주기로 데드락이 발생했는지 여부를 감지하고, 복구하는 방식으로 데드락 상태를 다루기도 한다.

리소스 타입에 대해 하나의 인스턴스만 있는 경우

Wait-for 그래프를 생성한 후, 해당 그래프를 기반으로 safe state인지 여부를 검사한다. 일정 주기마다 그래프에서 사이클을 찾는 알고리즘을 수행하여, 사이클이 존재하면 데드락으로 간주, 데드락 상황에 참여하는 프로세스들에 대해 조치를 취한다.

일반적으로 O(n^2) 시간을 요구하므로, 적당한 검사 주기를 찾는 것이 중요하다.

그래프로 표현하는 경우 리소스 타입은 무시하고 프로세스들 사이의 관계로 나타내 해결한다.

여러개의 인스턴스를 가지는 리소스 타입

Banker's Algorithm과 거의 유사하게 동작한다.

알고리즘이 대략 O(m * n^2) 의 시간복잡도를 요구하므로, 적절한 반복 주기를 결정하는 것이 중요하다.

다음과 같은 요소들을 고려할 수 있다.

데드락이 얼마나 자주 발생하는지?
얼마나 많은 프로세스가 롤백되어야 하는지?

만약 Detection 알고리즘이 빈번하게 이뤄진다면 Deadlock Avoidance 알고리즘과 큰 차이가 없다. 또한 데드락이 발생한 경우, "누가" 데드락을 야기했는지에 대한 정보는 알 수 없지만 데드락과 관련된 프로세스들은 알 수 있다. 데드락이 발생한 상황에서는 해당 프로세스들의 자원을 반환하고 중단해야 하는데, 이때 다음과 같은 선택지가 있다.

데드락과 관련된 모든 프로세스를 종료한다. 성능적으로 비효율적일 수 있다.
데드락에 참여한 프로세스들을 다음과 같은 조건을 기반으로 데드락이 풀릴 때까지 종료한다.
- 우선순위 기반 ( 높은 프로세스? 낮은 프로세스? )
- 프로세스가 실행된 시간 ( 오래 실행된 프로세스? 실행된지 얼마 안된 프로세스? )
- 프로세스가 가진 자원 ( 자원이 많은 프로세스? 적은 프로세스? )
- ...

이러한 다양한 조건들은 데드락에 무엇을 중심으로 두는지에 따라 다른 선택이 가능하다. 선택은 시스템 관리자의 몫이며 적절한 방법을 선택하여 성능을 추구해야 한다.

'CS > 운영체제' 카테고리의 다른 글

[운영체제] 페이징 기법 (0)	2022.05.16
[운영체제] 메모리 (0)	2022.05.09
[운영체제] 동기화 문제 및 방법 (0)	2022.04.22
[운영체제] CPU 스케줄링 (0)	2022.04.11
[운영체제] 스레드 & Concurrency (0)	2022.04.06

정보 보관소

[운영체제] 데드락

데드락

데드락의 특성

Resource-Allocation Graph

Resource Allocation Graph 예시

데드락에 대한 사실

데드락을 다루는 방법

Deadlock Prevention

Deadlock Avoidance

Safe State

Avoidance algorithms

resource-allocation graph

Banker's Algorithm

Safety Algorithm

Resource Request Algorithm

Deadlock Detection

리소스 타입에 대해 하나의 인스턴스만 있는 경우

여러개의 인스턴스를 가지는 리소스 타입

'CS > 운영체제' 카테고리의 다른 글

티스토리툴바

[운영체제] 데드락

데드락

데드락의 특성

Resource-Allocation Graph

Resource Allocation Graph 예시

데드락에 대한 사실

데드락을 다루는 방법

Deadlock Prevention

Deadlock Avoidance

Safe State

Avoidance algorithms

resource-allocation graph

Banker's Algorithm

Safety Algorithm

Resource Request Algorithm

Deadlock Detection

리소스 타입에 대해 하나의 인스턴스만 있는 경우

여러개의 인스턴스를 가지는 리소스 타입

'CS > 운영체제' 카테고리의 다른 글

'CS/운영체제' Related Articles

티스토리툴바