백엔드 개발자

2 분 소요

공유 자원에 접근할 때 여러 스레드가 동시에 접근할 때 발생할 수 있는 문제가 있습니다. 데이터베이스에도 이러한 문제가 발생하는데, 이를 해결하기 위해서 Lock 이라는 개념을 도입해 해결합니다. 하지만 Lock을 이용하면 DeadLock이라는 문제가 발생할 수 있는데 DeadLock이 무엇이고 어떤 상황에서 발생하는지, 어떻게 해결하는지에 대해서 알아보도록 하겠습니다.

DeadLck이란

데드락은 스레드가 아무것도 진행하지 못하는 대기 상황을 말합니다.

DeadLock이 일어나는 상황

데드락이 일어나기 위해서는 아래의 4가지의 조건을 만족해야 합니다.

  1. Mutual Exclusion

리소스를 공유해서 사용할 수 없다는 조건입니다. (여기서 말하는 리소스는 CPU 자원이 될 수 있고 Lock 등이 될 수 있습니다)

  1. Hold and Wait

스레드가 자신의 자원을 점유하면서 다른 스레드가 점유하고 있는 리소스를 기다려야 하는 상황입니다.

  1. No preemption

리소스를 점유한 스레드만이 리소스 점유를 해제할 수 있는 상황입니다.

  1. Circular Wait

여러 스레드가 순환 구조로 다른 스레드의 자원을 기다리는 상황입니다.

이렇게 4개의 조건이 만족되면 데드락이 발생하며, 이를 해결하기 위한 여러 방법들이 존재합니다.

DeadLock 해결 방법

데드락을 해결하는 방법은 여러가지가 있습니다.

데드락 감지와 복구

데드락을 감지하고 복구하는 방법인데, MySQL의 Innodb 엔진을 예로들어서 설명드리겠습니다.

MySQL Innodb는 wait for graph를 통해서 데드락을 감지합니다. 그리고 데드락이 걸린 트랜잭션들을 제거하는 방법으로 복구를 합니다. wait for graph는 방향 그래프이고 트랜잭션 간의 잠금 대기 관계를 나타냅니다.

wait-for-graph

위의 사진을 보면 알 수 있듯이 방향 그래프이고, 그래프가 순환 구조를 띄게 된다면 데드락이라고 판단을 하고 트랜잭션을 종료하게 됩니다. 시간 복잡도 자료를 찾아본 결과 DFS 알고리즘을 적용하면 O(V + E)가 걸리고, 최악의 경우 O(V^2) 시간 복잡도가 걸린다고 합니다.

트랜잭션을 종료하는 것도 기준이 있는데, innodb의 undo log가 적은 트랜잭션을 기준으로 삭제하게 됩니다. 왜냐하면 undo log가 작다는 것은 복구할 내용이 적다는 의미고 이는 MySQL에 부하를 덜 주게 되기 때문입니다.

데드락 회피

실제 환경에서 여러가지 정보를 토대로 데드락이 발생할 것 같은 상황을 회피하는 기법입니다. 위의 데드락 감지 부분에서는 리소스를 할당해주고 데드락이 걸렸는지를 확인하는데, 이 방법은 리소스 할당 요청을 거부하는 방법입니다.

  1. Resource-Allocation Graph Algorithm

  2. Banker’s Algorithm

데드락 방지

데드락 방지 방법은 User Level Application 에서 데드락이 발생하지 않게끔 디자인 하는 방법입니다.

  1. Mutual Exclusion이 발생하지 않게끔 설계

전공 서적에서는 대기없는 자료구조(wait free)라고 설명을 하고 하드웨어의 강력한 명령어를 사용하는 방법이라고 합니다. 대표적으로 Test_And_Set 처럼 Automic한 연산을 보장하는 명령어를 사용하는 것인데, 무한 반복과 같은 가능성이 발생할 수 있는 문제점이 있습니다.

  1. Hold And Wait가 발생하지 않게끔 설계

하나의 스레드가 두 개 이상의 리소스(R1, R2)가 필요할 때 R1을 얻고 R2를 얻으려는 시도를 하지 않고, R1과 R2를 모두 흭득한 상황에서 시작하는 방법입니다. 이 방식은 효율성이 좋지 않다는 문제가 있습니다. 예를 들어 R1 리소스를 처리하는 시간이 오래 걸린다면 R2의 리소스는 놀고 있는 상황이 됩니다.

또, 무한 반복(live lock) 문제가 발생할 수 있는데 이는 R1, R2를 모두 흭득하기 위해서 계속해서 try 하는 상태를 말합니다. 이 문제는 반복문에서 무작위 시간 지연 값을 넣어서 스레드 간의 반복 간섭 현상을 낮출 수 있다고 합니다.

  1. No Preemption이 발생하지 않게끔 설계

추가적인 리소스가 필요하다면 다른 스레드가 리소스를 선점 가능하게 하는 방법입니다. monitor 기법과 상당히 유사합니다.

  1. Circual Wait가 발생하지 않게끔 설계

이 방법은 리소스에 순서체계를 부여해서 해결할 수 있습니다. 예를 들어 R1을 얻고 R2를 얻어야 한다면 R2를 먼저 얻고 R1을 얻는 것입니다. 전공 서적에서는 4가지 방법 중 이 방법이 Best라고 설명을 합니다.

결론

하나의 공유 자원에 접근할 때 Lock 이라는 개념을 이용해서 임계 구역을 보호할 수 있습니다. 그런데 Lock 개념을 이용하면 DeadLock이라는 문제가 발생할 수 있는데, 이는 총 4가지의 조건이 달성되어야 합니다. DeadLock 문제를 해결하기 위해서는 데드락 감지와 회복, 데드락 회피, 데드락 방지 방법을 이용해서 해결할 수 있습니다.

참고