[OS] Concurrency의 문제점 Deadlock - OS 공부 23

안녕하세요 Pingu입니다. 🐧

 

지난 글에서는 동시성을 구현하기 위해 사용했던 Lock과 condition variable(조건 변수) 역할을 한 번에 할 수 있는 semaphore(세마포어)에 대해 알아봤습니다. 세마포어를 활용하여 여러 가지 유명한 문제들을 해결해봤었는데요, 이렇게 동시성을 잘 구현할 수 있게 되었지만 동시성 프로그래밍에는 문제점이 존재합니다. 바로 Deadlock(교착 상태)라고 불리는 문제인데요, 이번 글에서는 교착 상태에 대해 알아보고 어떻게 예방하고 해결할 수 있는지에 대해 알아보도록 하겠습니다. 제가 공부할 때 참고하고 있는 책인 OSTEP에서는 Chapter 32 - Concurrecny Bug 부분입니다!

Common Concurrency Problems

동시성은 여러개의 스레드를 동시에 실행할 수 있었고 이때 주의할 점은 공유 자원에 대한 상호 배제와 스레드 간에 실행 순서를 지켜주는 동기화가 있었습니다. 이를 위한 Lock, condition variable이 존재했었죠. 이번 글에서는 동시성의 문제점에 대해 알아보려고 합니다. Deadlock이라고 불리는 문제는 잠시 후에 자세히 알아보겠지만 간단히 설명하자면 그냥 스레드들이 모두 일을 하지 않는 상태를 말합니다. 또한 Deadlock이 아닌 동시성 문제들도 존재하는데, 이러한 것들 역시 알아보도록 하겠습니다!

What Types Of Bugs Exist?

그럼 먼저 동시성 프로그래밍을 하게 되면 어떤 문제점들이 발생하는지 부터 알아보도록 하겠습니다.

위의 그림은 유명한 프로그램들이 동시성을 활용하게 되는데, 이 때 발생한 버그들을 수치화해둔 표입니다. 표를 보면 deadlock 버그보다 non-deadlock 버그가 더 많은 것을 볼 수 있습니다. 그래도 크게는 두 개의 버그로 나뉘니 먼저 non-deadlock 버그부터 알아보도록 하겠습니다.

Non-Deadlock Bugs

아까 표에서도 봤듯이 non deadlock 버그가 더 자주 발생하는 것을 알 수 있습니다. 이러한 버그들은 어떠한 버그이면 어떻게 고칠 수 있을지 지금부터 알아보겠습니다!

Atomicity-Violation Bugs

첫 번째 버그는 Atomicity Violation(원자성 위반)이라고 하는 문제입니다. 원자성이란 어떠한 작업이 실행 되는 동안 다른 것에 방해를 받지 않고 반드시 시작과 끝을 보장해주는 것입니다. 실제로 이전 글들에서 원자성이 지켜지지 않을 때 발생한 여러 문제들을 봤었는데요, MySQL에 있는 간단한 예로 무슨 버그인지 다시 한번 알아보도록 하겠습니다~

위의 코드를 보면 두 개의 스레드가 있고 두 스레드 모두 thd->proc_info에 접근합니다. 스레드 1은 thd->proc_info 값이 NULL인지 확인하고 아니라면 데이터를 넣습니다. 스레드 2는 thd->proc_info를 NULL로 만듭니다.

아까의 코드는 위와 같은 실행 과정을 겪을 수 있습니다. 스레드 1은 분명 thd->proc_info가 NULL이 아니라서 조건문 안의 코드를 실행하려고 하는데 context switch가 발생해서 스레드 2가 수행되게 됩니다. 스레드 2는 thd->proc_info를 NULL로 바꿔버립니다. 다시 스레드 1을 수행할 때 값이 NULL 이므로 오류를 발생하게 되는 것이죠. 이와 같은 문제가 발생하는 이유는 스레드에서 수행하려는 작업이 원자성을 보장하지 않기 때문입니다. 이를 해결하는 방법으로는 lock을 사용하는 방법이 있었죠. thd->proc_info가 두 스레드에서 모두 접근 가능한 공유 자원이므로 한 순간에 하나의 스레드만 접근할 수 있도록 lock을 추가해주면 아까의 문제를 해결할 수 있습니다.

위와 같이 thd->proc_info를 접근하기 전과 후에 lock을 사용하여 문제를 해결할 수 있습니다.

Order-Violation Bugs

또 다른 non deadlock 버그를 한 번 알아볼까요? 이번에 알아볼 버그는 order violation(순서 위반) 버그 입니다. 말 그대로 스레드의 실행 순서가 지켜지지 않은 문제라고 보시면 됩니다. 

위의 코드를 보시면 스레드 1은 스레드를 mThread를 만드는 코드이고 스레드2는 mThread의 상태를 변경시키는 코드입니다. 만약 스레드 1이 실행되기 전에 스레드 2가 수행되면 어떻게 될까요? 존재하지도 않는 mThread의 상태를 변경하려고 할 것이므로 오류를 발생시킬 거예요. 즉 반드시 스레드 1이 실행된 뒤에야 스레드 2가 수행되어야 하는 순서 관계가 있는 것이죠! 이러한 것을 동기화라고 하며 이전 글에서 알아본 것처럼 조건 변수를 사용하여 이 문제를 해결할 수 있었습니다.

위와 같이 조건 변수를 사용해서 스레드간에 순서 관계를 주면 이 문제를 해결할 수 있습니다.

 

Lu et al?의 연구에 따르면 non deadlock 버그의 97%는 지금 알아본 원자성 문제, 순서 위반 문제라고 합니다. 따라서 개발자는 이를 방지하게끔 코드를 짜야합니다. 

Deadlock Bugs

그럼 이제 deadlock 버그에 대해 알아볼까요? 동시성을 지원하는 시스템에서 고질적으로 발생하는 deadlock bug는 교착 상태라고 하며 스레드들이 일은 하지 않고 기다리기만 하는 상태라고 볼 수 있습니다. 간단한 예를 보며 교착 상태를 이해해보겠습니다.

위와 같이 코드를 만들면 교착 상태가 될 수 있습니다. 스레드 1은 L1 lock을 잡고 context switch 되어 스레드 2는 L2 lock을 잡는다고 하면 어떻게 될까요? 둘 다 그다음 코드인 L2 lock을 얻거나 L1 lock을 영원히 얻을 수 없기 때문에 계속 context switch만 하는 dead lock 문제가 발생하게 됩니다. 이를 그림으로 그려보겠습니다.

위와 같이 갖고 싶은 lock을 영원히 갖지 못하는 문제가 발생합니다. 이런 문제를 어떻게 해결 할 수 있으며 이런 문제는 어느 상황에서 발생하는 것일까요?

Why Do Deadlocks Occur?

그럼 교착 상태가 왜 발생하는지부터 살펴보도록 하겠습니다. 첫 번째 이유는 코드의 구성 요소 간에 복잡한 종속성이 발생하기 때문입니다. 지금 공부하고 있는 OS의 가상 메모리 시스템을 생각해보면 디스크에서 page 정보를 얻기 위해 파일 시스템에 접근한 뒤 디스크 블록을 읽어서 page 정보를 얻고 이를 page table의 정보로 변환하여 실제 메모리에 접근할 수 있는데, 이러한 순서가 반드시 지켜져야 원하는 작업을 할 수 있는 것이죠.

 

또 다른 이유는 캡슐화입니다. 개발자는 구현의 세부 사항을 숨기고 모듈 방식으로 소프트웨어를 쉽게 구축하려고 하는데, 이러한 모듈은 lock과 잘 어울리지 않는다고 합니다. 예를 들어 Java Vector 클래스에 AddAll()이라는 메서드는 아래와 같이 수행됩니다.

위와 같은 코드를 수행하려면 v1, v2에 대한 lock을 모두 획득해야 다른 스레드로부터 안전해지는데,  만약 다른 스레드에서 v2.AddAll(v1)을 동시에 수행한다면 지금 스레드가 v1 lock만 가지고 v2 lock을 얻고 싶지만 이미 다른 스레드에서 v2 lock을 가지고 있어서 영원히 v2 lock이 해제되기를 기다리는 교착 상태에 빠지게 되는 것이죠.

Conditions for Deadlock

Deadlock은 그럼 어떤 조건에서 발생할까요? Deadlock을 발생시키려면 아래 네 가지 조건이 모두 만족되어야 합니다.

• Mutual Exclusion (상호 배제) : 공유 자원에 접근할 때 한 시점에 하나의 스레드만 접근 가능하도록 하는 것
• Hold-and-wait (점유 대기) : 자원을 추가적으로 얻으려고 할 때 갖고 있던 자원을 계속 가지고 있는 것 (예를 들어 L1 Lock을 갖고 있는 상태로 L2 Lock을 얻으려고 할 때 L1 Lock을 계속 가진 상태로 L2 Lock을 얻으려고 하는 것)
• No Preemption (비선점) : 스레드의 자원을 강제로 제거할 수 없는 것
• Circular wait (순환 대기) : 각 스레드가 원하는 자원이 서로 물고 물리는 상태인데, 그림을 보면 이해가 빠릅니다.

위와 같은 상태가 순환 대기 상태입니다.

 

위의 네 가지 조건 중 하나라도 만족하지 않는다면 dead lock은 발생하지 않습니다. 따라서 이 네 가지 조건 중 하나만 발생하지 않게 코드를 짠다면 교착 상태는 발생하지 않는 것이죠.

Prevention Deadlock

교착 상태를 발생하는 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않으므로 하나씩 예방하는 방법을 알아보도록 하겠습니다.

 

Circular Wait 예방하기

순환 대기를 발생하지 않도록 하는 방법은 Lock을 획득할 때 모든 스레드에 동일한 획득 규칙을 적용하는 것입니다. 예를 들어 L1, L2로 Lock이 2개 있는 경우 Lock을 원하는 모든 스레드는 L1부터 획득하고 L2를 획득하면 순환 대기를 예방할 수 있습니다. 하지만 복잡한 시스템에서는 lock이 엄청 많을 수 있기 때문에 부분 정렬이 좋은 방법이 될 수 있습니다. 하지만 정말 많은 주의를 기울여서 코딩을 해야 교착 상태를 예방할 수 있습니다.

 

Hold-and-wait 예방하기

점유 대기를 예방하는 방법은 필요한 모든 lock을 한 번에 획득하도록 보장하면 됩니다. 즉 원자성을 보장해주면 되는 것이죠!

예를 들어 위와 같이 lock을 얻는 과정을 prevention이라는 lock을 획득해야 실행 가능하도록 설계하면 교착 상태를 예방할 수 있습니다. 스레드가 lock을 획득하기 위해서는 prevention lock을 먼저 획득해야 하며 만약 다른 스레드가 lock을 획득하려고 시도하더라고 prevention lock을 가지고 있기 때문에 원자성을 보장할 수 있습니다. 필요한 lock을 한 번에 획득할 수 있도록 보장하여 교착 상태를 피할 수 있는 것이죠.

 

No Preemption 예방하기

 

일반적으로 스레드가 lock을 획득하면 이를 해제할 때까지 lock을 유지하게 되는데 이 때문에 다른 스레드는 해당 lock을 얻지 못하는 상황이 발생하게 됩니다. pthread_mutex_trylock()이라는 인터페이스는 lock을 획득하는 것을 시도해보고 실패하면 오류를 반환합니다. 이를 사용하면 얻지 못하는 lock을 계속 얻으려고 하는 것이 아니라 나중에 다시 시도하기 때문에 교착 상태를 피할 수 있는 것이죠.

이를 사용하여 교착 상태가 없는 lock 획득 프로토콜을 위와 같이 만들 수 있습니다. Lock을 획득하려고 시도하고 실패하면 가지고 있던 lock을 해제하는 것이죠. 다른 스레드가 만약 위와 동일한 프로토콜은 따르지만 L2 lock을 먼저 획득하고 L1 lock을 획득하더라도 교착 상태는 발생하지 않습니다. 하지만 새로운 문제가 발생하게 되는데요, 아래 그림과 같은 상황이 발생할 수 있습니다.

위와 같이 계속 Lock을 얻고 해제하고 하는 일만 반복하는 문제가 발생합니다. 이를 livelock 문제라고 하며 이를 해결하는 방법은 임의로 작업들 사이에 지연 시간을 줘서 스레드 간에 간섭 가능성을 줄이면 됩니다.

 

Mutual Exclusion 예방하기

 

마지막으로 상호 배제를 전혀 고려하지 않으면 교착 상태를 피할 수 있습니다. 물론 지금까지 동시성에 대해 공부하면서 상호 배제는 반드시 필요한 것임을 알기 때문에 조금 의아할 수 있는데요, 이러한 작업은 원자적으로 실행되는 하드웨어 명령어를 사용하면 상호 배제를 고려하지 않으면서 프로그램을 설계할 수 있습니다.

예를 들어 위와 같이 원자적으로 수행되는 하드웨어 명령어가 있고 이를 사용하여 어떤 값을 원자적으로 증가시키는 작업 하고 싶다고 생각해보겠습니다.

그럼 위와 같이 하드웨어 명령어를 사용하여 코드를 작성하면 lock을 사용하지 않고도 잘 작동하며 교착 상태도 발생하지 않습니다.

위와 같이 링크드 리스트에 노드를 넣는 작업도 생각해보겠습니다.

링크드 리스트에 노드를 넣을 땐 위와 같이 header의 포인터와 새로 넣는 노드의 포인터를 원자적으로 설정해줘야 자료구조가 문제없이 동작할 수 있습니다. 따라서 방금 코드는 원자성이 보장되어 있지 않기 때문에 노드를 넣다가 문제를 발생할 수 있는 코드입니다.

이를 하드웨어 명령어를 사용하여 lock을 사용하지 않고 위와 같이 코딩하면 교착상태를 방지할 수 있게 됩니다.

 

이렇게 하드웨어 명령어를 사용하여 상호 배제를 고려하지 않고 동시성을 구현할 수 있지만 제한적인 작업만 가능하기 때문에 크게 좋은 방법은 아닙니다.

Deadlock Avoidance via Scheduling

지금 까지 알아본 것처럼 교착 상태를 예방하는 방법도 있지만 교착 상태를 피하는 방법도 있습니다. 이는 서로 같은 공유자원을 사용하는 스레드끼리는 같은 CPU가 실행하도록 스케줄링하는 방법인데요, 이를 위해서는 어떤 스레드가 어떤 공유자원을 사용하는지에 대한 정보가 필요합니다. 이를 이해하기 위해 간단한 예를 하나 보겠습니다.

위의 그림을 보시면 스레드가 4개 있고 공유 자원으로는 L1, L2가 있는 것을 볼 수 있습니다. 같은 공유자원을 사용하는 스레드끼리 같은 CPU에서 실행한다고 했으니 아래와 같이 스케줄링하면 교착상태가 발생하지 않는 것이죠.

여기서 의문을 가질 수 있는 부분은 T3도 L1을 사용하는데 왜 다른 CPU에서 실행해도 괜찮은지? 일거 같은데요, T3은 L1 하나만 사용하기 때문에 다른 스레드들과 동시에 실행하더라도 교착상태를 발생하진 않기 때문입니다. 그렇다면 만약 아래와 같은 상황에서는 어떻게 스케줄링해야 할까요?

이번에는 T1, T2, T3 스레드가 L1, L1를 모두 사용합니다. 아까 동일한 공유자원을 사용하는 스레드끼리는 같은 CPU에서 실행한다고 했으니 스케줄링을 하게 되면 아래와 같이 CPU를 사용하게 됩니다.

위와 같이 실행하게 되면 교착 상태는 발생하지 않지만 새로운 문제가 발생합니다. 예전에 CPU 가상화에 대해 알아볼 때 멀티 프로세서 시스템에서 모든 CPU를 동등하게 일하게 만드는 load balancing(부하 균등)이라는 개념을 기억하시나요? 위의 그림처럼 스레드들을 실행하게 되면 CPU 1이 비교적 적은 일을 하게 되기 때문에 부하 균등을 만족하지 않습니다. 이 때문에 성능 저하도 발생하게 됩니다. 따라서 위와 같은 방법은 모든 스레드가 사용하는 공유자원을 알고 있는 상태의 임베디드 시스템 정도의 제한된 환경에서만 유용하게 사용할 수 있습니다.

 

또한 유명한 알고리즘인 Banker's algorithm을 사용하여 교착상태를 피할 수 있습니다. Banker 알고리즘이란 교착상태가 발생하지 않는 상황을 유지하도록 만드는 알고리즘입니다. 위의 그림이 banker 알고리즘의 한 예인데요, (가)의 상황을 보시면 남은 자원의 수는 10개이고 이를 적절히 사용하면 교착상태가 발생하지 않는 safe 한 상태입니다. (나)의 상황을 보시면 자원은 2개밖에 남지 않았지만 C, D스레드에게 2개의 자원을 할당하면 교착상태가 발생하지 않는 safe한 상태입니다. 하지만 (다)의 상황을 보시면 남은 자원의 수는 1개뿐인데 모든 스레드가 요구하는 자원의 최솟값은 2개입니다. 따라서 교착상태가 발생하는 unsafe 한 상태라고 할 수 있습니다. Banker 알고리즘은 위의 (다) 상황과 같이 unsafe한 상태가 되지 않도록 하여 교착상태를 피하는 방법입니다!

Detect and Recover

마지막으로 살펴볼 교착 상태를 해결하는 방법은 교착 상태가 발생하면 이를 해결하는 방법입니다. 어떻게 보면 가장 간단한 방법이죠? 예를 들어 OS가 1년에 한 번 교착상태를 발생한다면 그냥 컴퓨터를 재부팅하는 게 더 효율적일 수 있다는 말입니다.

 

혹은 resource allocation graph(자원 할당 그래프)를 만들어서 교착 상태를 발생하는 스레드를 중지시켜서 교착상태를 해결할 수도 있습니다.

위와 같이 자원 할당 그래프를 만들고 교착상태를 발생하는 스레드를 kill 하면 교착상태가 해결됩니다. 

 

Summary

이번 글에서는 동시성에서 발생할 수 있는 버그들에 대해 알아봤습니다. 크게는 두 가지로 나눌 수 있었는데요, deadlock과 non deadlock 버그였습니다. 교착상태가 아닌 버그는 원자성 위반, 순서 위반 버그가 존재했으며 이를 해결하는 방법도 알아봤습니다.

 

교착상태가 발생하기 위해서는 4가지 조건이 필요했었는데요, 상호 배제, 순환 대기, 점유 대기, 비선점이 네 가지 조건이었습니다. lock을 사용하는 동시성 프로그램은 이와 같은 여러 가지 버그를 발생할 수 있기 때문에 lock을 사용하지 않고 시스템을 만드는 방법도 있는데요, 이와 같은 방법으로 만든 것이 Google의 MapReduce라고 합니다. 이로써 OSTEP의 두 번째 단원인 Concurrency 단원을 모두 공부했습니다. 다음 글부터는 Persistence(영속성)에 대해 알아보도록 하겠습니다!