20160503

동시성 프로그램의 이해
2016/04/28에는 data race detection technique 중에서 happens-before 기법을 살펴보았다. 오늘은 lockset algorithm을 배울 것.
– Lockset based data race detection 기법은 lock discipline을 기반으로 data race를 탐지한다. Lock discipline: Every access to a shared variable MUST be guarded by at least one lock consistently. 공유 변수에 대해서는 모든 thread가 공유하는 lock이 있는지를 확인한다. Lock discipline을 지키면 correctness는 보장할 수 있지만, 성능은 떨어진다 (최대 병렬성을 이루지 못하기 때문이다). Eraser라는 도구가 lockset algorithm에 기반하여 data race를 탐지한다.
lockset algorithm.PNG
– Lockset algorithm은 false positive, false negative가 모두 발생한다. False positive: 1) Initialization에서 공유 변수를 초기화하는 단계에서 lock을 사용하지 않으면 false positive가 발생한다. 공유 변수를 초기화할 때에는 lock을 사용하지 않아도 괜찮은데, 엄밀히 따지면 lock discipline을 깨는 것이기 때문이다. 2) Read-shared variable에서는 lock을 사용할 필요가 없는데, false positive가 발생한다. False negative: reader-writers lock에서 false negative가 발생한다.
– Lockset의 false positive, false negative를 없애기 위해 memory location state를 도입한다. 모든 변수는 virgin state에서 시작되고, 그 외에 exclusive, shared, shared-modified 상태를 유지함으로써 각각의 경우를 해결한다. Data race는 shared-modified 상태에서만 발생할 수 있다. 하지만 여전히 모든 실행 시나리오를 보는 것이 아니므로, false negative가 발생할 수 있다. 다음 그림은 memory location state diagram이다.
memory location state.PNG
advanced lockset example code.PNG
advanced lockset example.PNG
– 하지만 여전히 false positive가 발생할 수 있고, 이러한 false positive를 줄이기 위해 happens-before를 추가로 사용할 수 있다. Memory location state에서는 메모리 주소에 대한 공유 상태만 봄. 따라서 할당 해제 이후 다른 변수로 쓰이는 것을 확인하지 못한다. Shared-modified 상태에서 상태가 virgin 상태로 바뀌는 것을 확인하지 못함.
– Data race detection technique은 많이 느리고, 전처리하거나 하드웨어를 추가로 사용해 해결하려는 시도가 있다. Sampling을 통해 일부만 확인함으로써 data race를 확인하고자 하는 시도도 있다.

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

누적 방문자 수
  • 96,354 hits
%d bloggers like this: