20160407

1. 동시성 프로그램의 이해
bug detection techniques for concurrent programs.PNG
– 동시성 프로그램에서의 버그 탐지 기법들은 scalability와 precision에 따라 크게 세 가지 종류로 나뉠 수 있다. Precision이 높고 scalability가 낮은 기법은 model checking technique이다. Model checking techniuqe을 사용하면 아주 정확하게 버그를 확인할 수 있으나, 연산에 오랜 시간이 걸린다. SPIN, Fusion, KISS, CHESS 등이 model checking technique에 해당한다. 중간 수준의 precision, 중간 수준의 scalability를 보이는 기법들도 있다. CalFuzzer, ConTest, rstest 등이 이에 해당한다. 정확도는 꽤 높은 편이지만, 테스트 케이스 생성이 쉽지 않다. 일반적인 버그를 찾아내기에 적합하다. 매우 scalability가 높지만 precision이 많이 떨어지는 기법도 있다. Atomizer, Eraser, RacerX, MetaL 등이 이에 해당하며, 이들은 heuristic하게 버그를 찾아낸다. 이 기법들은 각각에 특화된 버그를 찾아낸다.
– 한편, 버그를 찾아내고자 할 때에는 false positive와 false negative를 함께 고려해야 한다. False positive는 버그가 없는데 버그가 있다고 판단하는 것이고, false negative는 버그가 있는데 버그가 없다고 판단하는 것이다. 이 두 가지와 동시에 runtime complexity도 고려해야 함.

resource deadlock.PNG

– Deadlock은 thread의 집합이 특정 조건에서 더이상 진행하지 못하고 block되는 경우에 발생하는 버그이다. Deadlock 버그는 실제로 흔히 발생하는 버그이다. 서베이에 따르면 105개의 버그 중에서 31개가 deadlock 버그임을 확인했다 (Lu et al, ASPLOS’08).
– Deadlock에는 두 종류가 있다. Resource deadlock, communication deadlock이 있다. Resource deadlock은 공유 자원이 있을 때 두 개 이상의 쓰레드가 서로 다른 쓰레드가 자원 사용 해제하기를 기다리며 deadlock이 걸리는 것. Communication deadlock은 통신 상의 시점이 맞지 않아 deadlock이 걸리는 것.
– Resource deadlock은 서로 다른 두 락 집합이 다른 락 집합을 무한하게 대기하는 것. 흔히 ABBA 순서로 lock을 잡으면 deadlock이 발생한다. Deadlock은 한 개의 thread가 여러 개의 lock을 사용할 때 발생하기 쉽다. 한 개의 thread가 반드시 한 개의 lock을 사용하는 경우에는 문제가 발생하지 않는다.
ABBA deadlock.PNG

– Deadlock의 가능성을 없애기 위해 non-blocking 방식으로 알고리즘을 구현하는 연구도 활발히 진행되고 있다. Non-blocking algorithm은 lock-free / wait-free algorithm로 불리기도 한다. 이렇게 연구된 non-blocking algorithm의 대부분은 atomic한 write after read instruction이 있다는 가정 아래에 만들어졌다. Lock을 사용하는 것은 성능, 발생 가능한 버그 측면 모두에서 좋지 않다. Sequential program은 dependency를 찾기가 쉽지만, 동시성 프로그램에서 dependency를 찾기는 쉽지 않음. 하지만 non-blocking algorithm은 blocking algorithm보다 훨씬 복잡하다는 문제가 있음. 유명한 non-blocking 알고리즘의 버그가 수 년이 지나 드러나는 경우도 있음.
– Non-blocking / lock-free / wait-free의 정확한 정의는 다음과 같음.

An algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress.

communication deadlock.PNG
– wait() & notify()는 Java에서 많이 쓰인다. wait()을 사용해 한 쓰레드가 다른 thread의 notify() 또는 notifyAll()을 기다리도록 할 수 있다. Thread에서 객체의 모니터를 획득한 다음에 wait()을 호출해야 한다. 따라서 synchronized 구문 안에서 쓰여야 한다.
– wait() & notify() 짝이 깨지는 경우에 communication deadlock이 발생하며, interrupt와 spurious wakeup으로 인해 이같은 경우가 발생할 수 있다. Spurious wakeup을 허용하는 것은 성능 향상을 위한 운영체제의 정책이다. wait() & notify()의 짝을 유지하는 status table이 예외적으로 깨진다면, 운영체제는 어떻게 해야 할 것인가? 그대로 두면 wait()을 호출한 쓰레드는 계속해서 sleep할 것이다. 이러한 경우에는 원칙적으로는 옳지 않지만, 깨우는 편이 낫다(spurious wakeup). 이와 별개로, notify()는 wait()을 호출한 여러 개의 thread 중에 임의로(arbitrary) 선택해서 깨우도록 구현되어 있다. wait()을 호출한 thread의 순서대로 깨우는 것이 아님에 유의해야 한다.
– Communication deadlock이 발생하는 이유: notify()가 wait()보다 먼저 호출되면, notify()가 wait() 함수에 전달되지 않음. notify()는 일종의 메시지로, 해당 시점에 대기하는 thread에게 전달됨. 따라서 notify() 함수를 호출할 때에는 시점도 주의해야 한다.

– Deadlock 버그를 찾기 어려운 이유. 1) 특정 스케쥴링 환경에서만 deadlock이 발생하기 때문. 2) 성능을 위해 많은 수의 lock을 사용하기 때문. 3) 함수 호출 관계가 lock 사용을 더 복잡하게 만든다. 예를 들어 caller가 lock을 잡고, callee가 lock을 반환하는 경우.
– Resource deadlock 탐지에는 GoodLock, communication deadlock의 탐지에는 CHECKMATE 기법이 있다.
– Deadlock bug를 해결하는 기법에는 detection, prediction, prevention이 있다. Detection은 발생한 버그를 찾는 것. Prediction은 버그를 예측하는 것. Prevention은 예방하는 것.
Basic deadlock detection technique에서는 lock을 획득할 때 노드를 생성하고, lock을 잡은 상태에서 다른 lock을 획득하고자 할 때 edge를 그린다. 그리고 cycle이 생기면 deadlock으로 인지한다. 이렇게 구현한 deadlock detection technique에서는 thread interleaving에 따라 deadlock이 발견될 수도 있고, 발견되지 않을 수도 있다는 문제점이 있다 (false negative).
basic potential deadlock detection.PNG
cyclic deadlock detection example 1.PNG
cyclic deadlock detection example 2.PNG
Deadlock prediction 기법은 실제로 deadlock이 발생하지는 않더라도, thread interleaving에 따라 deadlock이 발생되는 경우도 탐지해낸다. Unlock 시점에서도 node와 edge를 지우지 않음으로써 deadlock 발생을 예측할 수 있다. 이같은 deadlock prediction technique은 false positive 가능성이 높다는 문제점이 있다. 이 기법에서 deadlock이 발생하는 이유는 어떤 코드들이 동시에 실행되는지 모르기 때문이다.

basic deadlock prediction technique.PNG
potential cyclic deadlock detection example.PNG
false positive example 1 - single thread cycle.PNG
false positive example 2 - gate lock.PNG
false positive example 3 - thread creation.PNG
– 이를 해결하기 위해 GoodLock algorithm이 제안됨. GoodLock algorithm에서는 thread segment graph, extended lock graph를 그려서 deadlock을 확인한다. Thread segment graph는 thread segment의 선행 관계를 그래프로 표현한다. Extended lock graph는 두 개의 thread가 동시에 lock을 잡는지 확인한다. Extended lock graph에서 valid한 cycle이 발생하면 deadlock이다.
– Cycle이 valid하기 위한 조건 1) 두 개의 thread가 다르고, 2) Gate lock이 없고, 3) 정해진 순서 없이 실행될 때. 단순히 GoodLock algorithm이 어떻게 돌아가는지 아는 것보다, 조건의 의미를 이해하는 것이 중요하다. 첫 번째 조건은 deadlock이 발생하기 위한 가장 기본적인 조건이다. 두 개의 다른 thread가 서로가 잡고 있는 lock을 잡으려해야 하기 때문이다. 두 번째 조건은 기존의 cycle detection algorithm에서 걸러내지 못한 것을 걸러내기 위한 조건이다. 이미 잡고 있는 lock이 서로 exclusive함을 확인한다. 세 번째 조건에서는 두 개의 쓰레드가 동시에 실행됨을 확인한다. 동시에 실행되지 않으면 (exclusive하다면) deadlock은 발생하지 않는다.
GoodLock Algorithm.PNG
thread segment example.PNG
extended lock graph.PNG
potential deadlock detection.PNG
thread creation example revisit.PNG
revisiting single thread cycle example.PNG
revisiting gate lock example.PNG
– CHECKMATE는 원래의 프로그램을 단순화한 trace program을 사용해 communication deadlock이 발생하는지 확인한다. CHECKMATE는 deadlock prediction 알고리즘이다. 실제로 communication deadlock이 발생하지 않는 interleaving에서도 deadlock이 발생할 것임을 예측해준다.


2. 버그 해결
photo_2016-04-07_21-44-03.jpg
“Error 16: Inconsistent filesystem structure” 메시지가 발생함. grub2로 업데이트하니 해결됨.

Advertisements
Tagged with: , , , , , , , , , , , , , , , , , , ,
Posted in 1) Memo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

누적 방문자 수
  • 88,328 hits
%d bloggers like this: