20160428

동시성 프로그램의 이해
– Data race bug는 race bug 중에 한 가지이다. Race bug는 race condition에서 발생할 수 있는 버그이다.
Race condition의 정의: A multithreaded program has a race condition if (1) execution order of certain operations are not fixed, and (2) their execution results are decided by their non-deterministic execution orders.
– Race condition을 없애려면 모든 것을 정해진 순서로 실행하면 됨. 하지만 그렇게 되면 성능이 많이 떨어질 것. Race condition 자체가 나쁜 것이 아님. Race condition이 해로운 것이냐, 아니냐를 판단해야 함. Therac-25에 data race bug가 있어서 환자가 죽기도 했음.
– 아래 코드는 Harmful race condition 사례이다. 두 개의 쓰레드가 동시에 같은 cnt에 대해 연산하고, 그 다음 요소를 빠뜨린 뒤 진행할 수 있음. cnt=32에 대해 두 개의 쓰레드가 동시에 진행하고, 33을 빠뜨리고 34를 연산할 수 있음.
harmful race condition.PNG
Data race의 정의: A data race is a pair of concurrent operations that read and write (or both write) data on a same memory location without synchronization (i.e., concurrently without any coordination). Data race가 발생하면 sequential consistency가 깨질 수 있다.
– Sequential consistency의 정의는 다음과 같다.
sequential consistency.PNG

– 다음 Java 코드에서 실제로 data race가 발생한다. Java의 메모리 모델이 예제처럼 오류를 일으킬 수도 있다. Balance 확인이 synchronized 영역의 밖에 있기 때문에 생기는 문제이다.
java data race example.PNG

– Sequential consistency 메모리 모델에서는 assertion이 항상 성립한다. 하지만 weak memory model에서는 성립하지 않을 수 있다. OoO 실행에서는 1과 2, 3과 4의 순서가 바뀔 수 있다. 그리고 delayed update가 발생할 수도 있다.
data race can break sequential consistency.PNG

Memory model의 정의: A memory model describes the interactions of threads through memory and their shared use of the data (necessary for compiler optimization). Java memory model에서는 적어도 변수 업데이트가 synchronization barrier에서는 전달되어야 한다. Memory model이 자유로울수록 더 높은 성능 달성이 가능하다.

– Data race가 항상 나쁜 것은 아니다. 다음 예제에서 test-test-and-set은 성능 향상을 위해 흔히 쓰이는 패턴이다. synchronized에서 락을 잡는 것은 오버헤드가 크므로 미리 한 번 걸러내는 것.
why is data race harmful.PNG
– Data race는 탐지하기가 매우 어려운데, thread interleaving에 따라서 data race가 bug를 일으킬 수도 있고, 아닐 수도 있기 때문이다. 그리고 공유 변수가 매우 많다는 것도 문제가 된다. Data race detection 기법에 happens-before와 lockset algorithm이 있다.
– Happens-before 기법은 Leslie Lamport가 고안했다. Happens-before에서는 서로 다른 연산의 순서를 정의한다. 두 개의 순서가 정의되지 않았으면 두 개의 연산이 concurrent하다고 한다. Happens-before relation의 정의는 다음과 같다.
happens-before relation 1.PNG
– Happens-before에서의 data race의 정의: The pair of operations 𝑎 and 𝑏 is data race if all of the following conditions hold:
(1) 𝑎 and 𝑏 access the same variable, and
(2) at least one operation is writing, and
(3) 𝑎⊀𝑏 and 𝑏⊀𝑎
– 다시 말해, 같은 변수를 공유하는 임의의 두 쓰레드에서, 해당 변수에 대한 연산의 순서가 non-deterministic하다면 data race가 있다고 탐지한다.
– 다음 예제에서 p3는 q1에 선행한다는 보장이 없다 (lock으로 보호되지 않음). 동시에 실행될 수 있으며, 같은 데이터에 대해 쓰기와 읽기가 동시에 진행되므로 유해한 data race이다.
p3 q1 happen before detection.PNG
– Happens-before에서는 false positive는 없다. 하지만 false negative는 발생할 수 있다. Happen-before detection은 여러 개의 가능한 실행 순서를 조사해 data race를 확인하지만, 그렇다고 해서 모든 경우를 확인할 수 있는 것은 아님. 따라서 false negative가 발생할 수 있다. 다음 예제는 false negative를 보이는 예제이다.
another execution scenario.PNG

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

누적 방문자 수
  • 103,570 hits
%d bloggers like this: