What Types Of Bugs Exist?
위와같은 어플리케이션에서 deadlock은 총 31개 deadlock이 아닌 버그는 74개이다.
Non-Deadlock Bugs
Atomicity-Violation Bugs
첫번째 non deadlock 버그는 MySQL에서 발견한 atomicity-violation bug이다.
이 버그는 다른 2개의 thread가 proc-info라는 같은 데이터에 접근한다. 한 thread는 값이 null이 아닌것을 확인하여 출력하고, 다른 thread는 값을 null로 만든다.
분명 thread1이 fput을 호출하기 이전에 interrupt가 발생하여 thread2가 값을 null로 변경하고, 다시 thread1이 수행되어 fput을 하려고하면 이미 proc_info는 null이기 때문에 문제가 발생한다.
atomicity-violation은 다시말해서 여러개의 메모리에 접근하는 직렬화가 잘못된 경우를 말한다.
다시말해서 atomic하게 실행되도록 생각했지만 atomic하게 실행되지 않은 경우를 뜻한다.
위의 코드는 atomicity assumption을 하고 있기 때문에 우리가 critical section에 lock을 걸어서 이 문제를 해결할 수 있다.
Order-Violation Bugs
위의 코드에서 문제는 thread2에서 thread1에서 초기화 된 mThread가 당연히 null이 아닌 값으로 초기화되어 있을 것 이라는 가정을 하기 때문에 문제가 된다.
즉 다시말해서 ordering bug는 메모리에 접근해야하는 적절한 순서가 뒤집힌 경우를 말한다.
그래서 이 문제를 해결하기 위해서 적절한 순서를 강제해야만 한다.
따라서 이전에 공부한 condition variable을 사용한다.
Deadlock bugs
위의 코드에서 만약 thread1이 L1을 lock한 이후에 thread2로 context switch가 발생하여 L2가 lock이된 후에 thread2에서 L1의 lock을 기다리게 되고 thread1에서도 이미 lock된 L2를 기다리므로 deadlock이 발생하게 된다.
이를 그림으로 표현하면 32.7과 같은 그림이 된다. 이 그림에서 cycle이 바로 deadlock을 나타낸다.
Why Do Deadlocks Occur?
한가지 이유로는 구성요소들간의 의존성 문제가 점점 복잡해짐에 따라 deadlock이 발생한다는 점이다.
예를들어 운영체제에서 메모리 시스템은 디스크에 있는 block을 paging하기 위한 이유로 파일시스템에 접근해야한다. 그리고 파일시스템은 block을 읽기위해서 메모리 시스템의 page가 필요하다.
따라서 위와같은 circular dependency상황에서 deadlock이 발생하지 않도록 주의하는 것이 매우 중요하다.
또다른 deadlock의 원인은 encapsulation의 특징 때문이다. 개발자로서 자세한 실행은 숨기고, 프로그램이 쉽게 동작하도록 만들기 위해서 encapsulation이 필요하다.
하지만 이런 encapsulation, modular way가 locking과는 잘 맞지 않을 수 있다.
Conditions for Deadlock
- Mutual exclsion:
thread가 필요한 자원을 독점해서 통제하려함. - Hold-and-wait:
thread가 추가적인 자원을 기다리는동안 thread에 할당된 자원을 지니고 있음 - No preemption:
자원을 지니고 있는 thread로 부터 강제로 자원을 제거할 수 없음 - Curicular wait:
다른 thread에서 필요로하는 자원을 하나 이상 하나의 thread에서 갖고있어서 circular chain이 존재함.
preventation
Circular wait
lock의 전체 순서를 지정하여 circular wait이 발생하지 않도록 한다.
또한 좀 더 복잡한 시스템의 경우 전체 순서를 지정하는 것이 까다롭기 때문에 부분적인 순서를 지정 하여 deadlock을 피할 수 있다.
Hold-and-wait
hold-and-wait은 모든 lock을 동시에 얻는 것을 atomically하게 막아준다.
하지만 이 방법은 몇가지 단점이 존재한다.
예를들어 우리가 원하는 lock을 하기 위해선 반드시 앞서서 다른 lock이 충족되어야 하므로 concurrency를 감소시키는 문제가 있다.
No Preemption
pthread_mutex_trylock()을 활용하여 우리가 사용하려는 lock이 다른 lock의 조건을 기다리는 경우에 발생하는 문제를 해결 할 수 있다.
예를들어 L1이 lock을 시도할 때 L2에 따라서 lock이되거나, unlock이 되도록 만들 수 있다.
따라서 강제적인 순서가 생기게되서 deadlock-free한 코드를 만들 수 있다.
하지만 2개의 thread가 반복적으로 위의 상황을 시도하지만 계속 실패하는 livelock이라는 문제가 있다.
이 문제를 해결하기 위해서 loopback시(goto구문)에 약간의 random delay를 줘서 2개의 thread가 간섭되는 빈도를 줄여줌으로써 해결할 수 있다.
Mutual Exclusion
하드웨어의 도움으로 lock을 사용하지 않는 설계를 할 수 있다.
위의 코드가 하드웨어의 도움으로 atomically하게 동작할 때 lock을 얻지 않고, 값을 update함으로써 deadlock-free하게 동작할 수 있다. (단 livelock 문제는 존재할 수 있음.)
좀 더 복잡한 list에 새로운 노드를 삽입하는 경우에도 위와같이 lock을 활용하지 않는 방법으로 해결할 수 있다.
Deadlock avoidance via scheduling
deadlock을 예방하는 것 보다 deadlock을 피하는 것이 유용할 때가 있다.
예를들어 2개의 processor가 있고, 4개의 thread가 존재할 때 lock에 대한 수는 위와 같다고 하자.
따라서 scheduler는 T1, T2를 동시에 동작시키지 않도록 스케줄링을 해야한다.
하지만 만약 T3도 2개의 processor를 모두 사용하는 경우라면 역시나 processor가 겹치지 않도록 스케줄링을 해야하기 때문에 아래와 같은 상황이 된다.
따라서 위와같은 스케줄링 방법을 통해 deadlock을 막을 순 있지만 전체적인 프로세스의 처리시간이 길어지게된다.
따라서 위와같이 deadlock avoidance via shceduling 방식은 매우 제한된 경우에만 사용할 수 있다. (예를들면 embeded system..)
Detect and Recover
많은 데이터베이스 시스템에서는 deadlock을 탐지하고, 회복하는 기능을 갖고있다.
deadlock이 발생했을 때 시스템을 재부팅하여 문제를 해결한다.
출처: OSTEP
