[OS] Deadlock

본 내용은 Operating System Concepts 8th Edition 번역본 책을 읽고 공부한 내용입니다.

목차
1. Deadlock 필요조건들
  1) 상호배제(mutual exclusion)
  2) 점유하며 대기(hold-and-wait)
  3) 비선점(no preemption)
  4) 순환대기(circular wait)
2. 자원 할당 그래프(Resource-Allocation Graph)
  1) RAG 구성요소
  2) RAG - 사이클 기본
  3) RAG - 사이클 심화
  4) RAG - 순환적 연결 knot
3. 교착상태 예방(Deadlock Prevention)
  4가지 필요조건 중에서 최소한 하나가 성립하지 않도록 하는 방법들
4. 교착상태 회피(Deadlock Avoidance)
  1) 자원당 인스턴스가 하나일 때
  2) 자원당 인스턴스가 둘 이상일 때 - banker's algorithm
  3) safety algorithm
5. 교착상태 탐지(Deadlock Detection)
6. 교착상태로부터의 회복(Recovery from Deadlock)

---

1. Deadlock 필요조건들

프로세스는 자원을 사용하기 전에 반드시 요청해야 하고, 사용 후에는 반드시 방출해야 한다. 해당 용어에 대해 더 자세히 이해하고 넘어가자! 프로세스는 다음 순서로만 자원을 사용할 수 있다.
1.요청 -> 2. 사용 -> 3. 방출
요청은 장치의 request(), 파일의 open(), 메모리의 allocate(), 세마포어의 wait(), mutex 락의 획득 을 예로 들 수 있고,
방출은 장치의 release(), 파일의 close(), 메모리이 free(), 세마포어의 signal(), mutex 락의 방출 을 예로 들 수 있다.
Deadlock은 쉽게 말해 어떤 프로세스가 현재 다른 프로세스에게 할당된 자원을 요청했을 때를 의미한다.
Deadlock은 아래 4개의 조건이 동시에 성립될 때 발생할 수 있다.

1. 상호배제(mutual exclusion)

만약 한 프로세스가 자원 하나를 가지고 있다면, 해당 자원을 가지고 싶어하는 다른 프로세스들은 자원이 다 쓰이기 전까지 기다려야 한다.

2. 점유하며 대기(hold-and-wait)

프로세스들은 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
하나를 hold하고, 다른 애가 갖고 있는 걸 wait하고 있어야 한다.
즉 나는 빵을 쥐고 있고, 친구는 사탕을 쥐고 있는데 내가 (이기적이게도) 사탕도 기다리는 현상

3. 비선점(no preemption)

자원들을 선점할 수(뺏을 수) 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있다.

4. 순환대기(circular wait)

대기하고 있는 프로세스의 집합 {P0, P1, P2 ...}에서 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고 ... Pn-1은 Pn이 점유한 자원을 기다리고, Pn은 P0이 점유한 자원을 대기해야 한다.

---

2. 자원할당 그래프(RAG)

1. RAG 구성요소

RAG로 우리는 프로세스와 인스턴스의 요청 상태 등에 대해 좀 더 쉽게 이해할 수 있다.
이로써 교착 상태를 표현하고, 이 그래프를 바탕으로 교착상태 예방/회피/감지 등에 운용된다.
node - thread 및 프로세스는 원으로, 자원은 사각형으로 표시한다.
edge - 자원->스레드를 가리키는 할당 간선과 스레드->자원을 가리키는 요청 간선으로 나뉜다.

2. RAG - 사이클 기본

위의 그래프를 A, 아래 그래프를 B라고 하자.

위의 상황을 보자. A는 cycle이 애초에 존재하지 않으므로 deadlock이 발생하지 않는다. 
반면 B는 모든 프로세스가 서로의 자원을 요구하면서 무한정 대기할 수 있어 deadlock이 발생할 수 있다.

3. RAG - 사이클 심화

이번에는 위의 상황을 살펴보자.
왼쪽은 잘 보면 T1->R1->T2->R3->T3->R2->T1의 사이클과, T2->R3->T3->R2->T2의 사이클로, 두 개가 형성되어 있다.
오른쪽도 사이클이 하나 존재하는데 T1->R1->T3->R2->T1으로 존재한다.
왼쪽은 Deadlock이 발생할 수 있다. 하지만 오른쪽은 발생하지 않는다. 
왜냐하면 왼쪽은 서로 물고 물리기 때문에 deadlock이 발생할 수 있으나 오른쪽 그림은 T4가 자원 하나를 쓰다가 반납하면 사이클 속 thread들이 사용할 수 있고, T2도 자원 하나를 쓰다가 반납하면 사이클 속 thread들이 사용할 수 있기 때문이다. 즉 오른쪽은 사이클을 헝크러뜨릴 여지가 있다.

4. RAG - 순환적 연결 knot

위의 그래프를 C, 아래 그래프를 D라고 하자.

위 상황도 보자. C에서 보이는 용어 knot이란 cycle / circular wait이라고 알려진 상태를 의미하며, 순환적인 연결을 뜻한다.
C는 순환적 연결을 가지고 있어 deadlock이 일어난다!
하지만 D는 사이클이 knot(순환적 연결)은 아니다. 따라서 run이 가능하다. 즉 r1이 p1에 할당되고, r2가 p2에 할당되고, p3가 r3에 할당될 수 있으며, 만약 한 쪽이 반납하면 p2가 돌아갈 수 있게 되고, ...이 과정이 반복되면 deadlock이 걸리지 않는다.
따라서 우리는 knot은 deadlock을 발생시키는 '충분 조건'이 될 수 있으나 '필요 조건'은 되지 않아 위의 deadlock 필요조건에 설명하지 않는다고 말한다. 즉 일어날 '수도' 있으나, 교착상태를 발생시키기 위해 반드시 knot이 존재할 필요는 없다.

복합상태에서 knot이 존재하면 deadlock이 걸릴 '수도' 있으므로 이를 예방해야할 '필요가 있다'.

---

3. 교착상태 예방

교착상태 예방은 우리가 위에서 이야기했던 4가지 필요조건 중에서 최소한 하나가 성립하지 않도록 하여 교착상태의 발생을 예방하는 방법이다. 네 가지 조건을 각각 따로 검토함으로써 이 접근 방식을 구체화해보자.

1. 상호배제 X

결론적으로 말하면, 모든 resource를 sharable하게 하면 된다. 하지만 프린터는 동시에 여러 프로세스들에 의해 공유될 수 없다. 너 동시에 두 개 파일 출력할 수 있어? 없잖아.
반면에 읽기 전용 파일과 같은 것은 동시에 여러 곳에서 접근해도 되는 공유 가능한 자원이다. 그래도 근본적으로 공유가 불가능한 자원들이 있기 때문에 성립될 수 없는 조건이다.

2. 점유하며 대기 X

점유하며 대기 조건이 시스템에서 발생하지 않는다는 것을 보장하려면 프로세스가 자원을 요청할 때에는 다른 자원을 가지고 있지 않다는 것을 보장해야 한다. 
첫 번째 방법은 프로토콜은 프로세스가 자원을 전혀 갖고 있지 않을 때에만 자원을 요청할 수 있도록 하는 것이다. 즉 만약 프로세스가 3개의 파일을 open해놓았다고 했을 때, 1개의 파일을 요청하려면 기존에 있는 것들을 다 내려놓고(방출) 난 후 획득하도록 하는 것이다. 하지만 이는 실용적이지 않고, 어떤 프로세스 요청이 우선인지를 알기 어렵다.
두 번째 방법은 한 번에 필요한 모든 자원을 요청하는 것이다. 예를 들어 DVD로부터 디스크 파일로 자료를 복사하여 디스크 파일을 정렬하고 프린터에 결과를 인쇄하려고 한다고 하자. 이 때 프로세스는 처음에 모든 필요한 자원을 요청해야 하므로 DVD, 디스크파일, 프린터를 전부 요청해야 한다. 프린터는 마지막 단계에서만 필요할 뿐인데 이 전체 시간동안 계속 점유되어야 한다. 이는 자원 이용률을 낮추고, 여러 개의 자원들을 여러 개 필요로 하는 프로세스들이 있을 수 있기 때문에 이들이 기아 상태에 빠지게 한다.

3. No preemption X

세 번째 필요조건은 이미 할당된 자원이 선점되지 않아야 한다는 것이었다. 그렇다면 그냥 빼앗아버리자! (allow preemption).
또는 대안으로, 한 프로세스(A)가 어떤 자원들(X,Y,Z)을 요청하면 이들이 사용 가능한지 검사한다.
만약 사용 가능하다면 이들(X,Y,Z)을 (A에게) 할당한다.
사용 불가능하다면, 그 자원들(X,Y,Z)이 추가 자원을 기다리고 있는 다른 프로세스(B)에게 할당되어 있는지를 검사한다. 만약 할당되어 있다면 대기 중인 프로세스(B)로부터 필요로 하는 자원(X,Y,Z)을 선점해 요청 프로세스(A)에게 할당한다. 그런데 이 때 X,Y, Z가 가용하지 않거나 다른 대기 프로세스에게 점유되어 있지 않다면 요청 프로세스(A)는 반드시 대기해야 한다. 이 때 다른 프로세스들에게 빼앗길 수도 있다. 이걸 모두 되돌려 받았을 때에만 실행될 수 있는 것!
따라서 이 프로토콜은 CPU 레지스터나 memory 공간처럼 저장/복원이 용이한 자원들에 적용될 수 있으며 프린터나 테이프 드라이브 같은 자원에는 적용될 수 없다. 결국 이는 매우 이상적인 이야기이다.

4. Circular Wait 순환대기 ▵

그나마 4개 중 가장 현실적인 방법이다. 자원들의 순서를 미리 다 impose(정해놓고)해놓고, 더 번호가 높은 자원들만 요청한다. 예를 들어 P0 -> P1 -> P2 .. 가 있다고 하면 file -> memory -> sdd ... 이런 형태이다. 그러나 이는 transaction 측면에서 보았을 때 또 결국 문제가 생길 수 있다. 이 때 lock이나 wait() 명령어 등을 써야 한다.

되도록이면 예방 방식보다는 회피 방식을 사용한다.

---

3. 교착상태 회피

운영 체제는 교착상태에 빠질 수 있는 가능성이 존재하는 unsafe한 상태와 그렇지 않은 safe 상태로 나뉜다. 프로세스가 자원을 요청할 때 safe 상태의 것들은 수락하고 unsafe 상태는 거절한다.

1. 자원 당 인스턴스가 하나일 때

주로 위에서 말한 RAG를 사용하여 판단한다. 요약해서 다시 한 번 말하면
1. 그래프에 사이클이 있는지 확인
2. 사이클이 존재할 경우 자원 유형에 몇 개의 인스턴스가 있는지 확인
3. 하나의 인스턴스만 있으면 교착 상태, 여러 인스턴스가 있으면 교착 상태가 가능하다(knot)고 판별한다.
아래는 사이클이 존재하지만 교착상태가 무조건 일어나지는 않는 knot RAG의 예시이다. 

사이클이 존재하지만 교착상태가 아닌 RAG 예시!!! 프로세스 P1이 작업을 완료하고 R3의 자원을 반환하면 P3은 P1이 반환한 자원을 할당 받으면 된다.

코프만은 위와 같이 자료구조를 사용하여 RAG를 분석하여 교착상태를 판단할 때 사용하였다.

2. 자원 당 인스턴스가 둘 이상일 때 - 은행원 알고리즘(banker's Algorithm)

은행원 알고리즘은 자원 종류마다 자원이 둘 이상일 때(즉 많을 때, multiple instances) 교착 상태의 예방을 위해 사용된다. 프로세스의 자원 요청과 시스템의 안전 상태를 검사하여 교착 상태를 예방하는 방법이다. 간단히 말하자면, 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기한다. 
해당 과정을 표로 나타내보자.

Available[i][j] = Pi에 자원유형 Rj 인스턴스가 k개 있음을 의미한다.
Max[i][j] = k는 프로세스 Pi가 자원유형 Rj의 최대 k개의 인스턴스를 요청할 수 있음을 의미한다.
Allocation[i][h] = k는 프로세스 Pi가 현재 자원 유형 Rj k개의 인스턴스를 할당받았음을 의미한다.
Need[i][j] = k 는 프로세스 Pi가 현재 자원 유형 Rj k개의 인스턴스를 필요로 함을 의미한다.

다음 알고리즘은 파이썬으로 나타내보자.

# Banker's Algorithm
 
# Driver code:
if __name__=="__main__":
     
    # P0, P1, P2, P3, P4 are the Process names here
    n = 5 # Number of processes
    m = 3 # Number of resources
     
    # Allocation Matrix
    alloc = [[0, 1, 0 ],[ 2, 0, 0 ],
            [3, 0, 2 ],[2, 1, 1] ,[ 0, 0, 2]]
     
    # MAX Matrix
    max = [[7, 5, 3 ],[3, 2, 2 ],
            [ 9, 0, 2 ],[2, 2, 2],[4, 3, 3]]
     
    avail = [3, 3, 2] # Available Resources
     
    f = [0]*n
    ans = [0]*n
    ind = 0
    for k in range(n):
        f[k] = 0
         
    need = [[ 0 for i in range(m)]for i in range(n)]
    for i in range(n):
        for j in range(m):
            need[i][j] = max[i][j] - alloc[i][j]
    y = 0
    for k in range(5):
        for i in range(n):
            if (f[i] == 0): #프로세스가 완료되지 않았다면
                flag = 0
                for j in range(m):
                    if (need[i][j] > avail[j]): # need들이 avail보다 크다면 더이상 볼 필요가 없다
                        flag = 1
                        break
                 
                if (flag == 0): #모든 need들이 avail보다 작았다
                    ans[ind] = i 
                    ind += 1
                    for y in range(m):
                        avail[y] += alloc[i][y]
                    f[i] = 1
    print("Following is the SAFE Sequence")
     
    for i in range(n - 1):
        print(" P", ans[i], " ->", sep="", end="")
    print(" P", ans[n - 1], sep="")
 
# This code is contributed by SHUBHAMSINGH10

결과는 다음과 같이 출력된다.

Following is the SAFE Sequence
 P1 -> P3 -> P4 -> P0 -> P2

위의 코드에서 "Need값 각각이 Available 값보다 작은가?"에 만족하면 할당할 수 있고, 
할당시킬 때에는 Available += Allocation으로 값을 변경해줌에 주목하자!
그러면 Available은 아래와 같이 변하게 된다.

[3, 3, 2]
[5, 3, 2] (P1 할당 후)
[5, 3, 2] (P3 할당 후)
[7, 4, 3] (P5 할당 후)
[7, 4, 5] (P0 할당 후)
[7, 5, 5] (P2 할당 후)

3. Safety Algorithm 

안전성 알고리즘은 banker 알고리즘의 일부로, 교착 상태를 방지하기 위해 시스템에서 안전한 실행 순서를 찾는 알고리즘이다. 과정은 다음과 같다.

1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively. 
Initialize: Work = Available 
Finish[i] = false; for i=1, 2, 3, 4….n
2) Find an i such that both 
a) Finish[i] = false 
b) Needi <= Work 
if no such i exists goto step (4)
3) Work = Work + Allocation[i] 
Finish[i] = true 
goto step (2)
4) if Finish [i] = true for all i 
then the system is in a safe state

코드로는 아래와 같이 나타낼 수 있을 것이다.

def safety_algorithm(alloc, max, avail):
    n = len(alloc)  # 프로세스의 수
    m = len(avail)  # 자원의 수

    # 필요한 추가 변수와 리스트 초기화
    f = [False] * n
    ans = []
    work = avail[:]
    need = [[max[i][j] - alloc[i][j] for j in range(m)] for i in range(n)]

    # 안전한 실행 순서를 찾는 반복문
    while True:
        found = False
        for i in range(n):
            if not f[i]:
                if all(need[i][j] <= work[j] for j in range(m)):
                    work = [work[j] + alloc[i][j] for j in range(m)]
                    f[i] = True
                    ans.append(i)
                    found = True

        # 모든 프로세스를 확인했을 때 더 이상 실행 가능한 프로세스가 없으면 종료
        if not found:
            break

    # 안전한 실행 순서와 실행 불가능한 프로세스 반환
    if len(ans) == n:
        return ans, []
    else:
        remaining = [i for i in range(n) if not f[i]]
        return ans, remaining


alloc = [
    [0, 1, 0],
    [2, 0, 0],
    [3, 0, 2],
    [2, 1, 1],
    [0, 0, 2]
]

max = [
    [7, 5, 3],
    [3, 2, 2],
    [9, 0, 2],
    [2, 2, 2],
    [4, 3, 3]
]

avail = [3, 3, 2]

safe_sequence, remaining_processes = safety_algorithm(alloc, max, avail)

print("안전한 실행 순서:", safe_sequence)
print("실행 불가능한 프로세스:", remaining_processes)

#initialize
초기에 work 배열이 Available로 initialize되고 finish 불리언 벡터는 모두 false로 초기화된다.
work 는 현재 가용한 자원의 양, need는 각 프로세스가 필요로 하는 자원의 양이다.
#과정
request(need) 배열이 work 배열보다 작거나 같은 값을 가지는 프로세스에 한 해 Work += Allocation으로 더해준다.
즉, 프로세스 i가 사용한 자원을 가용 자원에 반영하는 것!
Finish 배열은 이 때 true로 변환된다. Finish 배열을 점점 true로 만드는 것이 이 알고리즘의 핵심이다.