본 글의 내용은 Operating Systems: Three Easy Pieces의 Common Concurrency Problems 챕터를 정리한 것입니다.

☑️ 개요

• 수많은 연구자들이 몇년에 걸쳐 동시성 문제 해결을 위해 노력해왔다.

• 초기 작업은 대부분 deadlock에 초점을 맞췄으나, 최근에는 다른 유형의 동시성 문제 연구에 중점을 두고 있다.

☑️ 어떤 유형의 버그가 존재하는가?

• MySQL, Apache 등에서 확인된 버그는 위와 같았다. 즉, 수적으로도 비 deadlock 버그가 더 많은 것이다.

☑️ Non-Deadlock 버그

🔎 원자성 위반 버그 (atomicity violation)

• 위 코드에서는 Thread 1이 proc_info 가 null이 아닐 때 값을 할당하고, Thread 2는 proc_info 의 값을 null로 변경하고 있다.

• Thread 1이 조건문 내부에 진입했을 때 interrupt가 발생하면, Thread 2가 값을 null로 바꿔 Thread 1에게 예외를 발생시킨다.

• 즉, Thread 1의 코드는 if문과 함수가 묶여서 동작하는 것으로 가정, 즉, 원자성을 가정하고 동작한 것인데, 가정이 틀려버린 것이다.

• 각 코드에 lock을 설정하는 것으로, 필요하던 원자성을 보존하게 된다.

🔎 순서 위반 버그 (order violation)

• 원하는 순서가 뒤바뀌는 동시성 문제를 순서 위반이라고 한다.

• 위 코드가 실행되면 Thread 1이 객체를 생성하기도 전에 Thread 2가 접근할 수도 있다.

• lock과 condition variable을 활용하면 해결된다. (세마포어도 활용 가능)

🔎 Non-deadlock 버그 요약

• 교착 상태와 관련없는 비데드락 버그도 동시성 문제에 존재하고 있다.

• 상당 부분은 원자성 혹은 순서 위반이다.

☑️ Deadlock 버그

(단순 데드락)

• 많은 동시성을 가진 시스템에서 발생하는 고전적인 문제로, 두 스레드가 서로 쥐고 있는 lock을 기다리며 무한히 대기하는 상황이다.

• 그림에 표현된 것과 같이, 서로 lock에 대한 순환 구조를 가지게 된다.

🔎 Deadlock은 왜 발생하나요?

• 종속성

  • 코드 규모가 커지면 구성 요소간에 복잡한 종속성이 발생한다.

  • OS를 예시로 들면 가상 메모리와 디스크는 페이징을 위해 서로 접촉해야 하며 순환 구조가 생길 수도 있다.

  • 코드에서 자연스럽게 발생할 수 있는 순환적인 종속성이 있다면 신중하게 작성해야 한다.

• 캡슐화

  • 구현의 세부 사항을 숨기고 SW를 쉽게 구축하기 때문에 몇몇 interface는 deadlock을 유발할 수 있다.

  • 예시로, Java Vector 클래스의 o1.addAll(o2) 메소드는, 호출 주체와 파라미터 대상이 정해지는데, 두 객체 모두에 Lock이 설정된다.

  • 이때 다른 스레드에서 거의 동시에 o2.addAll(o1) 형태로 호출할 경우 deadlock이 발생할 수도 있다.

🔎 Deadlock 발생 조건

• Deadlock이 발생하려면 4가지 조건이 충족되어야 한다.

1. 상호 배제: 스레드가 필요 리소스에 대해 독점 제어를 요청한다. (스레드가 lock을 잡는 등)

2. 보류 및 대기: 리소스(lock)를 보유한채로 다른 리소스(다른 lock)를 기다린다.

3. 선점 불가: 스레드에게서 리소스를 강제로 뺏어올 수 없다.

4. 순환 대기: 각 스레드가 각자의 리소스(lock)를 순환하는 형태로 기다린다.

• 이 중 하나라도 충족되지 않으면 deadlock은 발생할 수 없다.

🔎 예방법

✴️ 순환 대기 (Circular wait)

• 당연히 순환적인 구조를 갖지 않도록 lock 코드를 작성하는 것이 예방법이다.

• 그 중 가장 간단한 방법은 lock 획득의 전체 순서를 지정해서 순환하지 않도록 하는 것이다.

• 현실적으로 복잡한 시스템에서는 lock이 두 개 이상 존재하기 때문에, 잠금 순서를 다 정하는 것은 쉽지 않다. 그래서 부분적으로 순서를 설정(partial ordering)하는 것이 유용하다.

• Lock 주소에 따라 접근 순서를 설정하는 것도 좋은 방법 중 하나이다.

• 전체적인 순서와 부분적인 순서를 설정할 때 항상 신중해야 하며, 엉성한 설계는 얼마든지 deadlock을 일으킬 수 있다.

✴️ 보류 및 대기 (Hold-And-Wait)

• 다른 Lock을 prevention lock으로 잠궈 원자성을 만드는 것으로 해결할 수 있다.

• 위 예시에서 prevention 이라는 lock을 통해, L1 혹은 L2 를 획득했을 때 interrupt가 발생하여 deadlock이 유발될 만한 상황을 예방한다.

• 다만 이 접근 방법은 어떤 lock을 잠그는지 정확히 이해하고 lock을 요청해야 하며, 꼭 필요한 시점이 아닌데도 싸잡아서 lock이 걸리므로 동시성이 부족해지는 문제가 있다.

✴️ 선점 불가 (No preemption)

• 보통 문제가 생기는 경우는, 여러 개의 lock을 얻을 때 특정 lock을 기다리면서 다른 lock을 놓지 않는 경우이다.

• 이런 상황을 피하기 위해 pthread_mutex_trylock 같은 함수가 있는데, lock을 가질 수 없을 때 대기하지 않고 바로 반환된다. 반환된 후 가지고 있던 lock의 선점도 포기한다.

• 이때 새롭게 발생하는 문제가 있는데 바로 livelock이다.

• 우연한 타이밍으로 락을 계속해서 얻지 못하는 상황이 발생하면서, 동작은 하지만 아무 일도 하지 않게 된다.

✴️ 상호 배제 (Mutual exclusion)

• 상호 배제 자체를 아예 없애는 방법이다. 물론 critical section이 존재하기 때문에 쉽지는 않다.

• 이런 경우에 lock이 전혀 없는 데이터 구조를 설계한다는 아이디어가 고안되었는데, lock-free(wait-free)라고 불렸다.

• 여기서 spin lock에서 소개되었던 CompareAndSwap 을 재조명할 수 있는데, 이CompareAndSwap 은 하드웨어에서 제공하는 원자 명령어이다.

• 이걸 활용하여 값을 원자 단위로 증가시키는 함수를 선언할 수 있는데, lock을 활용하는 대신 값을 갱신할 때까지 반복적으로 CompareAndSwap 을 시도한다.

• 이 방식으로 lock을 사용하지 않으며, deadlock은 발생하지 않는다. (livelock은 가능)

• 위는 리스트에 헤드를 삽입하는 예제이다. 여기에도 lock-free 방식을 적용할 수 있다.

• 이렇게 삽입 기능을 lock-free로 구현할 수 있지만, 삭제, 조회 등을 lock-free로 구현하는 것은 당연히 간단하지 않다고 할 수 있다.

✴️ 스케줄링으로 deadlock 방지

• 예방 대신 회피하는 방법이다.

• 여러 스레드가 어떤 lock을 얻을 수 있는지 파악하면, 해당 스레드들이 교착 상태를 일으키지 않도록 스케줄링할 수 있는 것이다.

• 위처럼 같은 lock을 얻는 스레드의 순서를 조정해서 스케줄링한다.

• 만약 위와 같은 상황이라면?

• 보수적으로 스케줄링을 하게 됨으로써 동시 작업 성능이 저하되며, 작업 완료 시간도 길어진다. 이 때문에 제한된 환경에서만 유용하게 사용된다.

✴️ 감지 및 복구

• 한편으로는 deadlock이 가끔 발생하도록 허용하고, 감지되면 그때 조치를 취할 수도 있다.

• deadlock이 발생하는 상황이 드물다면, 이런 방식은 굉장히 유용하다.

• 많은 DB들이 이런 기술을 사용하며, 교착 상태 감지기가 주기적으로 실행된다.

✅ 요약

• deadlock 버그만 존재하는 것은 아니며, Non-deadlock 버그인 atomicity violation과 order violation이 존재한다.

• Non-deadlock 버그는 lock과 condition variable을 적절히 활용하여 해결할 수 있다.

• deadlock 버그를 예방하기 위해서는 mutual exclusion, hold and wait, no preemption, circular wait을 제거해야 한다.

• lock을 아예 사용하지 않는 lock-free를 채택함으로써 deadlock을 회피할 수도 있다.

• lock-free 방식에서는 우연한 타이밍으로 끝없이 시도만 하게 되는 livelock을 야기할 수도 있다.

• lock을 획득하는 스레드를 파악한 뒤, 스케줄링으로 deadlock을 피할 수도 있지만 성능 하락의 원인이 되어 제한적으로 활용된다.