데드락

동시성을 이해하기 위해 클린 코드에서 추가 설명하는 데드락에 대해 알아보자.

 

 

데드락, 한정된 자원을 여러 곳에서 사용하려고 할 때 모두 작업 수행을 할 수 없이 대기 상태에 놓이는 상태.

 

개수가 한정된 자원 풀 두개를 공유하는 웹 애플리케이션이 있다고 가정한다.

• 중앙 저장소 mercurial queue Connection pool
• 로컬 임시 데이터베이스 Connection pool

애플리케이션의 연산은 두 가지, 생성과 갱신

 

생성.

  중앙 저장소 연결 후 임시 데이터베이스 연결을 얻는다. 중앙 저장소와 통신한 후 임시 데이터베이스에 작업을 저장한다.

갱신.

  임시 데이터베이스 연결을 확보한 후 중앙 저장소 연결을 얻는다. 임시 데이터베이스에서 작업을 읽어 중앙 저장소로 보낸다.

 

여기서 커넥션 풀 크기를 10이라 제한하고 사용자가 10명보다 많다고 가정하면  낮은 확률로 다음과 같은 일이 벌어진다.

 

1. 10명의 사용자는 생성 연산을 시도해 중앙 저장소와 연결을 확보한다. 모든 스레드가 중앙 저장소와의 연결을 확보한 이후 임시 데이터베이스 연결을 확보하기 전 중단된다.
2. 새로운 10명의 사용자가 갱신을 시도해 데이터베이스 연결을 10개를 모두 확보하고, 모든 스레드가 중앙 저장소 연결을 확보하기 전에 중단된다.
3. 생성 스레드 10개는 임시 데이터베이스 연결을 확보하기 위해 기다리고, 갱신 스레드 10개는 중앙 저장소 연결을 확보하기 위해 기다린다.
4. 데드락이기에 시스템은 복구될 수 없다.

 

데드락은 굉장히 무섭다. 낮은 확률로 발생하는 증상은 재현하기도 너무 어려워서 디버깅에 많은 시간을 쏟아야 한다. 

 

데드락이 걸리는 이유

 

• 상호 배제(Mutual Exclusion)은 여러 스레드가 한 자원을 공유하나 그 자원은 여러 스레드가 동시에 사용하지 못하며 개수가 제한적이라면 상호 배제( Mutual Exclusion)를 만족한다. 
  예를 들면 데이터베이스 연결, 쓰기용 파일 열기, 레코드 락, 세마포어 등과 같은 자원이다.
• 잠금 & 대기 (Lock & wait)
  스레드가 자원을 점유하면 필요한 나머지 자원까지 모두 점유해 작업을 마칠 때까지 이미 점유한 자원을 반환하지 않는다.  
• 선점 불가 (No Preemption)
   한 스레드가 다른 스레드로부터 자원을 빼앗지 못한다. 즉 자원을 점유한 스레드가 스스로 반환하지 않는 이상 다른 스레드는 그 자원을 점유하지 못한다.
• 순환 대기 (Circular Wait)
  서로 필요한 자원을 요청하되, 그 필요한 자원들을 다른 스레드가 점유하고 있어 무한 대기에 걸리는 상태

데드락은 네 가지 조건이 모두 충족되어야 발생한다. 그렇기에 데드락을 피하는 전략 중 하나가 상호 배제 조건을 비껴가는 방법이다. 

 

상호배제는 공유 자원을 동시에 사용하지 못하기에 다른 스레드가 자원을 반환하기를 기다려야 하기 때문인데, 이를 동시에 사용해도 되는 자원으로 교체하거나, 스레드 수 이상으로 자원을 늘리거나, 자원을 점유하기 전 필요한 자원이 모두 있는지 확인하는 방법이 있다.

 하지만 대다수 자원은 그 수를 제한하는데는 이유가 있고 동시에 사용하기도 매우 어렵다. 필요한 자원을 확인하기 위한 조건이 첫 번째 자원일 수도 있다. 

 

그렇기에 다음 방법인 Lock & Wait 조건을 깨 보자.

대기를 하지 않으면 데드락이 발생하지 않는다. 따라서 자원을 점유하기 전에 필요한 자원을 점유할 수 있는지 확인하고 만약 전부 점유하지 못한다면 가지고 있는 자원을 전부 반환하고 처음부터 다시 시작한다. 

그런데 이 방법에는 문제가 있다.  Starvation과 Livelock 문제인데, 스레드가 모아야 하는 자원의 조합이 한 번에 확보하기 어려워 계속해서 자원을 점유하지 못하거나 여러 스레드가 동시에 잠금 단계로 진입하여 자원을 점유했다 반환했다를 반복한다. 이는 작업 처리량을 크게 떨어뜨린다.

그럼에도 저자가 해당 방법을 추천하는 이유가 있다. 아무 대책이 없는 경우보다는 좋다.

 

선점 불가 조건을 깨기 위해선 다른 스레드가 점유한 자원을 가져오는 방법이다. 필요한 자원이 다른 스레드에 의해 잠겨있다면 해당 스레드에 풀어달라고 요청한다. 해당 자원을 소유한 스레드가 다른 자원을 기다리는 중이었다면 소유한 자원을 전부 락을 해제한 후 처음부터 다시 시작한다. 

 

데드락을 방지하는 가장 흔한 전략으로 순환 대기 조건을 깨는 방법이 있다. 대다수 시스템에서는 모든 스레드가 동의하는 간단한 규약이면 충분하다. 

모든 스레드가 자원을 선점하는 순서를 일정하게 하는 것에 동의하고 그 순서로만 자원을 할당하면 데드락은 불가능하다. 

다만 자원을 할당하는 순서와 자원을 사용하는 순서가 다를지도 모르기에 맨 처음에 할당한 자원을 마지막에 쓸지도 모른다. 즉 자원을 필요한 이상으로 오랫동안 점유한다. 

또한 순서에 따라 자원을 할당하기 어렵다. 만약 첫 자원을 사용한 후에야 둘째 자원을 얻는다면 순서대로 할당하는 것 자체가 불가능하다.

 

데드락을 확실하게 피하는 전략은 없다. 다만 스레드 관련 코드를 분리하여 관리하면 조율과 실험이 가능해 최적의 전략을 찾기 쉬워질 수 있다.