RaceCondition

여기, 하나의 값(파이)을 추측하는 식이 있다고 가정하자. 값의 발산식과 의사코드는 다음과 같이 나온다.

이를 pthread로 계산하면 다음과 같은 코드가 나온다.

이 코드가 과연 잘 돌아갈까?

그것은 아니다. n을 증가시킬 수록 값이 달라진다.
그 이유는 sum에 합산을 하는 곳에서 Race condition이 발생하기 때문이다(Pthread들이 sum을 공유변수로써 사용하기 때문이다).

Example

여기, y = Compute(my_rank)와 x = x + y를 계산하는 식이 있다고 가정하자. x의 초기값은 0이고 0번 스레드는 y = 1, 1번 스레드는 y = 2로 계산된다. x의 올바른 답이 3이 되어야 한다.

하지만 Time 5에서, thread1이 x의 값을 참조할 때 thread0에서 계산한 x의 값이 반영되지 않으므로, 0을 조회하게 된다. 따라서, 0 + 2를 하여 결국 x는 2가 나온다.

• Race Condition
  여러 개의 스레드들이 공유변수를 접근하고 업데이트할 때, 공유변수에 접근하기 위해 경쟁한다. -> 이로 인해 예측하지 못한 결과가 나올 수도 있다.

• Critical Section
  무조건 하나의 스레드가 공유 변수 하나를 잡을 수 있도록 한다. 작업이 끝나면 다른 스레드가 공유 변수를 잡을 수 있다.
  한번에 하나의 스레드에서 하나의 데이터를 업데이트할 수 있다.

Busy-Waiting

Critical Section을 구현하기 위해 사용하는 방법으로, Flag 변수를 사용한다.

스레드는 해당 부분을 반복적으로 컨디션 테스트를 한다. 컨디션을 만족하지 못하면 계속 기다리기 때문에 성능이 나빠질 수도 있다.

pthread 프로그래밍에 Busy Waiting을 추가한 소스코드이다. 하지만 결국 하나의 공유변수에 하나의 스레드가 접근하므로, 병렬 프로그래밍을 하는 의미가 사라진다.

그래서, 미리 factor를 계산하고 합산할 때만 Critical Section을 만들면 좋다.]

하지만 Busy Waiting 자체가 좋다곤 할 수 없다. 스레드가 기다리는 동안 CPU를 점유하지만 작업을 하지 않는다. 이는 자원낭비로 이어질 수 있다. 이 때 Mutex를 사용한다.

Mutex

Critical Section에서 싱글 스레드만 접근하도록 하는 특별한 변수이다.
mutex 코드는 다음과 같다.

pthread_mutex_init : 뮤텍스 변수를 생성한다.
pthread_mutex_lock : lock한 시점부터 Critical Section을 불러온다.
pthread_mutex_unlock : Critical Section을 해제한다.
pthread_mutex_destroy : 뮤텍스 변수를 해제한다.

lock ~ unlock 시점까지 Critical Section을 불러오므로, sum을 더하는 곳은 하나의 싱글 스레드만 들어올 수 있다.

그 결과, 스레드의 수가 많아질수록 Busy-Waiting 기법에 비해 Mutex가 더 효율적이다.
그 이유는 Busy-waiting은 스레드 넘버, 즉 Flag로 제어하기 때문에 아무리 빨리 처리를 해도 자기 순서가 되지 않으면 Critical Section에 들어갈 수 없다. 이는 스레드가 많아질수록 더 심해진다. 반면에 Mutex는 빨리 처리되는대로 싱글 스레드가 들어갈 수 있다.

Busy-waiting이 일어나는 과정을 테이블로 나타낸 것이다.

3번 스레드와 4번 스레드는 이미 작업을 끝냈지만 2번 스레드의 처리가 늦어 Critical Section에 진입하지 못하고 있다. 때문에 3, 4번 스레드는 2번 스레드가 완전히 끝내기 전까지 Critical Section에 진입하지 못한다.