[TOOR] 17. Race Condition

what is Race Condition

둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과 값에 영향을 줄 수 있는 상태.

즉 공유 자원에 대해 여러 개의 프로세스가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다.

다음은 예시 코드이다.
예제 코드는 여기서 가져왔고 이후 설명도 해당 글에서 인용해왔다.

#include <stdio.h>
#include <pthread.h>

int sum;

void *run(void *param)
{
    int i;
    for (i = 0; i < 10000; i++)
        sum++;
    pthread_exit(0);
}

int main()
{
    pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, run, NULL);
    pthread_create(&tid2, NULL, run, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    printf("%d\n", sum);
}

main 에서 tid1 과 tid2 스레드를 생성 하고 각각 run 함수를 실행 시킨다.
pthread_join 으로 main은 각 스레드가 종료되는 걸 기다린다.
스레드가 종료되고 나면 sum 을 출력해주는데

코드만 봤을 때는 20000 이 출력되어야 할 것 같다.

하지만 실제로 실행을 해보면 20000이 나올 때도 있고 전혀 다른 값이 출력될 떄도 있다.

어셈블리어 수준으로 분해해보면 간단하게 이해할 수 있다고 한다.

tid1의 스레드에서 메모리에 있는 값을 변경시키기 위해서는 다음 세 단계의 인스트럭션이 필요하다.

• register1 = sum
• register1 = register1 + 1
• sum = register1

마찬가지로 tid2의 스레드에서도 다음 세 단계의 인스트럭션이 필요하다.

• register2 = sum
• register2 = register2 + 1
• sum = register2

두 스레드를 concurrent 하게 실행시키기 위해서 중간중간에 스레드 간 [MISC] 컨텍스트 스위칭 (context switching) 이 발생한다.

만약 sum == 0 인 상황에서 스레드 1을 실행하고 있다고 가정해보자.
이때 register1 에 sum == 0 을 저장하고 register1 = register1 + 1 까지 수행하고 스레드2로 컨텍스트 스위칭이 발생하면 register1에는 1의 값이 저장되어 있을 것이다.
그 상태에서 스레드2가 계속 실행되면 sum의 값이 증가하게 된다.
하지만 나중에 다시 스레드1로 컨텍스트 스위칭이 발생하게 되고 스레드1에서는 sum = register 1 ( == 1) 을 실행하게 되어 sum = 1 로 스레드2에서 실행한 결과가 무용지물이 된다.

이게 기본적인 race condition 에 대한 예시 이다.

Solution

race conditon 은 공유자원을 동시에 사용하고자 해서 생긴다.
따라서 공유자원을 순차적으로 사용할 수 있게 만들어 주면 되는데
이를 동기화라고 부른다.

탈의실을 이용해서 비유하는데

탈의실은 오직 한 사람만 들어갈 수 있다라는 규칙이 있다.

여기서 탈의실을 'critical section (임계 구역)'이라고 한다.
그리고 오직 한명만 들어갈 수 있는 것을 ‘mutually exclusive (상호 배제)’ 라고 한다.

Critical Section

임계 구역 또는 공유변수 영역은 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부를 말한다.
즉, 여러 프로세스가 동일 자원을 동시에 참조하여 값이 오염될 위험 가능성이 있는 영역이다.

Criticla Section 은 지정된 시간이 지난 후 종료된다. 때문에 어떤 스레드(task or process) 가 임계 구역에 들어가고자 한다면 지정된 시간만큼 대기해야 한다.
스레드가 공유자원의 배타적인 사용을 보장받기 위해 임계 구역에 들어가거나 나올때는 세마포어 나 뮤텍스 같은 동기화 매커니즘이 사용된다.

mutex

mutex 는 상호 배타적 잠금이다. 단 하나의 스레드만을 잠글 수 있다.

Critical Sectoin 을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행(상호배제_Mutual Exclution) 되도록 하는 기술이다.
다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 동기화(Synchronization) 또는 락(Lock) 을 사용하는데 이는 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없다는 것을 의미한다.

세마포어 (Semaphore)

멀티 프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법이다.
모든 deadlock 을 해결하지는 못한다.

세마포어 S 는 정수 값을 가지는 변수이며, P와 V라는 명령에 의해서만 접근할 수 있다.
P 는 critical section 에 들어가기 전에 수행되고, V는 critical section 에서 나올 때 수행된다. 이때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다.
다시 말해, 한 프로세스(또는 스레드) 에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안된다

 P(S) {
     while S <=0; // 아무것도 하지 않음 (반복문)
     S--;
 }

 V(S) {
     S++;
 }

최초 제시된 방법으로 [MISC] busy waiting 을 이용한 방법이다.

하지만 이 방법은 critical section 에 들어갈 수 있을 때까지 빈 반복문을 수행하기 때문에, 단일처리기 대중프로세스 환경에서 처리기 효율이 떨어진다.
또한 대기 중인 프로세스들 중 어느 것을 먼저 임계구역에 진입시킬지를 결정할 수 없다.

이를 보완한 방법으로 재움 큐 를 활용해서 프로세스를 재우는 방식이다.

 P(S) {
     S--;
     if S < 0
         // 이 프로세스를 재움 큐에 추가 (잠 듦)
 }

 V(S) {
     S++;
     if S <= 0
         // 재움 큐로부터 프로세스를 제거 (깨어남)
 }

종류

계수 세마포어

계수 세마포어(counting semaphore) 에서는 초기값은 가능한 자원의 수로 정해지며, 세마포어 값의 범위는 정해져 있지 않다.

이진 세마포어

이진 세마포어(binary semaphore) 에서는 세마포어 값으로 0 또는 1을 가진다.
계수 세마포어 보다 간단히 구현할 수 있으며, Test and Set 등 하드웨어가 지원하는 기능을 이용하여 구현하기도 한다.
또한, 이진 세마포어를 이용하여 계수 세마포어를 구현할 수도 있다.

약점

P함수와 V함수의 동작은 독립적이기 때문에 잘못 사용하는 경우 문제가 발생한다.

• P - 임계 구역 - P : 현재 프로세스가 임계 구역에서 빠져나갈 수 없게 된다 또한 다른 프로세스들은 임계 구역에 들어갈 수 없으므로 교착 상태가 발생한다.
• V - 임계 구옥 - P : 2개 이상의 프로세스가 동시에 임계구역에 들어갈 수 있으므로 상호 배제(Mutual Exclusion) 을 보장할 수 없게 된다.

참고 자료
https://charles098.tistory.com/88
https://tbonelee.tistory.com/43
https://ko.wikipedia.org/wiki/임계_구역
https://chelseashin.tistory.com/40
https://www.ibm.com/docs/ko/aix/7.3?topic=programming-using-mutexes
https://ko.wikipedia.org/wiki/세마포어

이 글은 옵시디언을 이용해서 작성되었습니다.