이전 포스트에서 한정된 공유 자원에 대한 접근을 관리하는 Lock에 대해서 공부했다. Lock을 사용할 때에는 Dead Lock이 발생하지 않도록 주의해야 한다.

Dead Lock

교착 상태 (Dead Lock)이란, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

데드 락을 발생시키기 위해서는 네 가지 조건을 만족해야 한다.

1. 상호 배제 (Mutual Exclusion)
   프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
2. 점유 대기 (Hold and wait)
   프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
3. 비 선점 (No preemption)
   프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
4. 순환 대기 (Circular wait)
   각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

예시

어떤 한 대륙이 있다.

편의를 위해 해당 대륙은 가로로 길고 총 100 단위의 땅을 가지고 있으며, 그 중 1부터 50까지의 땅은 A 국가에, 51부터 100까지의 땅은 B 국가에 속해있다고 가정한다.

a_land = list(range(1,51))
b_land = list(range(51,101))

각 국가는 대륙을 정찰하기 위해 정찰병을 파견하였다.
A 국가의 정찰병은 1부터 순서대로 100까지 올라가고, B 국가의 정찰병은 100부터 순서대로 1까지 내려간다.

a_scout = 0
b_scout = 99

각 국가는 서로 정찰병을 파견했다는 것을 알고 있지만, 정찰병의 정찰 속도를 알지 못한다. 따라서 본인의 국가를 정찰하는 것에 대해 배타적인 권리를 행사하도록 한다.

a_lock = threading.Lock()
b_lock = threading.Lock()

즉, 본인 국가에 대한 정찰이 완료된 이후에야 타 국가에게 정찰 권리를 넘긴다는 의미이다.

각 국가의 정찰병은 다음과 같은 방법으로 정찰을 수행한다.

class A_Scouting(threading.Thread):
    def __init__(self):
        super().__init__()

    def run(self):
        global a_scout
        a_lock.acquire()

        for i in range(50):
            a_land[a_scout-50] = "A"
            a_scout += 1
            time.sleep(0.1)
        
        b_lock.acquire()
        a_lock.release()

        for i in range(50):
            b_land[a_scout] = "A"
            a_scout += 1
            time.sleep(0.1)

        b_lock.release()

우선 정찰병은 A 국가의 정찰에 대해 배타적 권리를 행사한다. (a_lock.acquire)

A 국가의 정찰병은 0부터 차례대로 정찰하면서 정찰이 완료된 토지에 대해서는 "A"라는 표식을 남긴다. 그리고 휴식을 취한다.

그러나 B 국가에게 A국에게 정찰 권한을 넘겼음에도 불구하고 B 국가가 B국의 정찰 권한을 넘기지 않을 수도 있기 때문에, B국에 대한 정찰 권한을 먼저 받고 (b_lock.acquire) 나서야 A국의 정찰 권한을 넘기고자한다.(a_lock.release)

물론 이는 B 국가도 똑같이 생각하고 있다.

자 그러면, 각 국가가 각 국가의 토지에 대한 정찰을 마치고 난 이후에는 어떤 일이 발생할까?

교착 상태 발생

A 국가는 A 국가에 대한 정찰을 모두 완료했으니 B 국가에 대해 정찰 권리를 요구한다.

B 국가는 B 국가에 대한 정찰을 모두 완료했으니 A 국가에 대해 정찰 권리를 요구한다.

그러나 A 국가는 B 국가에게 정찰 권리를 넘기기 이전에 B 국가의 정찰권리를 먼저 받고 싶어하고, B 국가 역시 A 국가에게 정찰 권리를 넘기기 이전에 A 국가의 정찰 권리를 먼저 받고 싶어 한다.

서로가 서로의 정찰 권리를 요구하고 있으므로 협상은 진전되지 않고 교착 상태에 빠지게 된다.

앞서 언급한 교착 상태의 네 가지 필요조건에 대입하여 생각해보자.

1. 상호 배제 (Mutual Exclusion)
   프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

• A 국가의 토지(a_land)의 정찰권은 A가 가지고 있으며, B 국가의 토지(b_land)의 정찰권은 B가 가지고 있다. 그리고 각 정찰권리는 각 국가가 배타적으로 행사한다.

2. 점유 대기 (Hold and wait)
   프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

• 각 국가는 정찰권을 가지고 있는 상태에서, 타 국가의 정찰권을 얻고자 한다.

3. 비 선점 (No preemption)
   프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

• 한 국가가 정찰 중일 때 다른 국가는 정찰할 수 없다.

4. 순환 대기 (Circular wait)
   각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

• B 국가가 요구하는 자원은 A 국가의 정찰권이고, B 국가가 요구하는 자원은 A 국가의 정찰권이다. 각 국가는 다음 프로세스로 타 국가를 정찰하고자 하며, 각 국가는 본인 국가에 대한 정찰권을 가지고 있다.

협상하자

앞선 네 가지 조건 중에서 한 가지 조건이라도 만족하지 못한다면 교착 상태는 해제된다.

가장 간단한 방법은 두 국가 모두 정찰 권리를 포기하는 것이다. 즉, 락을 걸지 않는 것이다. 그럴 경우 정찰에 필요한 자원(정찰권)이 없어지기 때문에, 네 가지 조건이 동시에 해제된다.

그러나 정찰권이 있는 상태에서 협상하고자 한다면 두 번째 조건 (점유 대기)를 해제 하면 된다.

즉, 본 국가에 대한 정찰권을 가지고 있는 상태에서 타 국의 정찰권을 요구하는 것 보다는, 본 국에 대한 정찰권을 양도하고 타 국의 정찰권을 받아오면 된다.

이를 코드로 구현하면 다음과 같이 수정할 수 있다.

class A_Scouting(threading.Thread):
    def __init__(self):
        super().__init__()

    def run(self):
        global a_scout
        a_lock.acquire()

        for i in range(50):
            a_land[a_scout] = "A"
            a_scout += 1
            time.sleep(0.1)

        a_lock.release() # 먼저 정찰권을 넘겨주고
        b_lock.acquire() # 타 국의 정찰권을 받아온다.

        for i in range(50):
            b_land[a_scout-50] = "A"
            a_scout += 1
            time.sleep(0.1)

        b_lock.release()

그렇다면 두 국가 모두 두 국가가 속한 대륙에 대한 정찰을 완료할 수 있다.

참조

1. Wikipedia : 교착 상태