Dead Lock(교착 상태)

동시성 프로그래밍을 작성할 때, 프로그래머는 굉장히 세심한 주의가 필요하다.

단순히 동시성 문제를 해결하기 위한 상호 배제와 같은 기법을 사용 시

이로 인한 성능 저하와 그 외의 다양한 새로운 문제들을 직면할 수 있기 때문이다.

그중 가장 유명한 오류가 바로 데드락이다.

 

데드락이란?

교착 상태라고도 부르는 데드락은 동시성 프로그래밍에서 발생하는 가장 유명한 오류 중 하나이다.

출처: https://sujinnaljin.medium.com/ios-%EC%B0%A8%EA%B7%BC%EC%B0%A8%EA%B7%BC-%EC%8B%9C%EC%9E%91%ED%95%98%EB%8A%94-gcd-14-4aefd4ba1eb7

위 이미지는 데드락이 발생하는 상황에 대해 잘 설명하고 있다. 

위 이미지에서 두 스레드는 각각 공유 자원에 대한 락을 획득한 상태에서

서로가 이미 획득한 공유 자원에 대한 소유를 위해 대기 상태에 빠지게 된다.

이런 대기 상황은 해소되지 못한 채 결국 두 스레드 모두 작동하지 않게 된다.

 

데드락이 발생 조건

데드락이 발생하기 위해서는 다음의 4가지 조건이 충족되어야 한다.

• 상호 배제(Mutual Exclusion)
• 점유 및 대기(Hold and Wait)
• 비선점(Non-Preemption)
• 순환 대기(Circular Wait)

이를 풀어서 설명하면,

각 쓰레드는 스스로가 필요로 하는 공유 자원에 대한 독자적인 제어권(락)을 획득하는 상황 속에서, 스레드가 이미 획득한 제어권을 가진채 다른 공유 자원에 대한 제어권을 요구해야 한다. 만약 다른 스레드에서 이미 점유 중이라면, 공유 자원이 반환될 때까지 대기한다. 이때 다른 스레드가 점유한 자원을 뺏어올 수는 없다. 마지막으로, 스레드들 간의 대기가 순환 형태를 띠어야 한다.

 

데드락의 예방

순환 대기 해소

가장 많이 사용되고, 또 적용해볼만한 방식으로 순환대기가 발생하지 않도록 로직을 작성하는 방법이 있다.

이를 위해서는, 공유 자원을 획득하는 순서를 사전에 지정할 수 있다.

예를 들어 스레드 1과 스레드 2가 각각 공유 자원 A, B에 접근할 때,

스레드 1과 2가 각각 A와 B를 먼저 획득한 채 다른 하나를 대기할 때 데드락이 발생한다.

이런 상황에서 벗어나기 위해 무조건 A를 획득해야 B에 대한 요청을 할 수 있도록 강제하는 것이다.

그렇게 되면 순환 대기 문제가 해결되어 데드락을 예방할 수 있다. 

 

점유 및 대기 해소

해당 방식은 요구되는 모든 공유 자원에 대해, 이를 원자적으로 한번에 획득하도록 로직을 작성하는 것이다.

마치 트랜잭션처럼 말이다.

만약 요구되는 공유 자원 중 하나라도 획득하지 못한다면,

다른 자원에 대한 획득까지도 없던 일로 만들어서 이를 해결할 수 있다.(롤백)

 

비선점 해소

해당 방식은 특정 쓰레드가 여러개의 락을 얻고자할 때 하나를 얻은 상황에서

그 다음 락을 얻을 때 만약 해당 락이 이미 다른 스레드에 점유 중이면 기존에 획득했던 락을 모두 취소하고

락 획득 로직을 다시 수행하는 것이다.

만약 다른 스레드에서 이와 비슷한 방식으로 순서는 다르게 락을 획득한다해도 데드락 문제는 해소된다.

비록 다른 스레드가 획득한 락을 강제로 뺏는 선점 기능을 추가하지는 않지만,

데드락이 발생할 수 있는 상황에서 바로 대기에 빠지지 않고 해당 상황을 탈출하게 해준다.

 

상호 배제 해소

해당 방식은 데드락 문제를 완화하기 위해, 상호 배제 방식을 최소화하기 위한 접근 방식이다.

즉 락을 최소화하는 것인데, 이를 위해 비교 교환 방식(Compare and Swap)을 사용할 수 있다.

비교 교환 방식은 다음과 같이 로직 작성이 이루어진다.

import threading

# 공유 변수
count = 0


# 스레드 함수
def atomic_increment():
    global count
    for i in range(100000):
        # 락을 사용하지 않고, 비교-교환 연산을 사용하여 count 변수를 증가시킴
        while True:
            old_count = count
            new_count = old_count + 1
            if old_count == count:
                count = new_count
                break

# 스레드 생성
worker_1 = threading.Thread(target=atomic_increment)
worker_2 = threading.Thread(target=atomic_increment)

# 스레드 실행
worker_1.start()
worker_2.start()

# 스레드 종료 대기
worker_1.join()
worker_2.join()

# 결과 출력
print(count) # 200000

로직을 보면

공유 자원의 상태를 복사하는 변수를 하나 만든 후 수행할 연산을 이에 처리한다.

만약 그 때까지도 복사한 값과 공유 자원의 값이 동일하다면(다른 스레드를 통한 연산이 처리되지 않았다면)

연산 결과를 공유 자원에 대입한다.

해당 방식은 락을 최소화하는데 도움을 주지만,

만약 수행해야할 연산의 규모가 크다면 공유 자원의 상태와 이를 복사한 값이 일치할 확률이 적어져

무한 루프를 탈출하는 비율이 줄 수 있고, 또 운이 나쁘면 동시성 문제가 여전히 발생할 수 있기 때문에 만능은 아니다.

 

데드락의 회피

스케줄링을 통한 방식

스레드 1과 스레드 2가 데드락 발생 가능성이 존재한다는 것을 사전에 인지할 수 있다면,

해당 상황에서는 스케줄링을 통해 데드락을 피할 수 있다. 

스레드 1과 스레드 2가 동시에 실행되는 상황이 문제가 되는 것이기 때문에,

스케줄러가 이를 인지하고 스레드 1이 실행되는 동안에는 스레드 2를 실행시키지 않으면 되는 것이다.

다만 해당 방식은 스레드 간 병렬 처리를 저해할 수 있기 때문에 성능적 이슈가 발생할 수도 있다.