OS : Concurrency - Race Condition

학부 수업 내용을 필기한 내용입니다.
필자가 이해를 제대로 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분이 있다면 댓글로 이야기하여 수정하게 해 주시면 감사하겠습니다.

Why It Gets Worse : Shared Data

공유된 자원이 있을 때 왜 악화될까?

#include <stdio.h>
#include <pthread.h>
#include "common.h"
#include "common_threads.h"

static volatile int counter = 0;

//mythread()
//
//Simply adds 1 to counter repeatedly, in a loop
//No, this is not how you would add 10,000,000 to
//a counter, but it shows the problem nicely.
//
void *mythread(void *arg) {
    printf("%s: begin\n", (char *) arg);
    int i;
    for (i = 0; i < 1e7; i++) {
        counter = counter + 1;
    }
    printf("%s: done\n", (char *) arg);    
    return NULL;
}

//main()
//
//Just launches two threads (pthread_create)
//and then waits for them (pthread_join)
int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("main: begin (counter = %d)\n", counter);
    Pthread_create(&p1, NULL, mythread, "A");    
    Pthread_create(&p2, NULL, mythread, "B");
    // join waits for the threads to finish   
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("main: done with both (counter = %d)\n", counter);
    return 0;
}

아까의 코드에서 mythread 부분이 좀 바뀌었다.

보면 전역 변수로

static volatile int counter = 0;

이렇게 선언이 되어있고

mythread()에서는...

for (i = 0; i < 1e7; i++) {
        counter = counter + 1;
    }

각 스레드에서 10,000,000 씩 증가시키게 되어있다.

그리고 이러한 전역 변수 counter과 대비되는 것이 지역변수 i이다.

그래서 구조를 보게 되면

전역 변수는 Address space에서 Data 영역에서 공유가 되고 있으며

각 스레드의 execute Stack에서 i는 별도로 갖게 되어있다.

그럼 이를 실제로 실행하게 되면 어떻게 될 것인지 한 번 보자.

위에 결과는 사람이 코드를 작성했을 때 기대한 결과이다.

그러나 실제로는 2천만이 나오지도 않으며, 심지어 실행 때마다 결과마저 다르다.

결과가 비결정적이다.

왜 이런 일이 발생했을까?

 

Counter 증가?

여기에서 보면 문맥 교환이 2회 일어났다.

mov 8049a1c, %eax

이 명령어의 주소가 100 번지이기 때문에

실행되기 이전에 PC는 100이었으며 eax는 0, counter 변수는 50인 상태였다.

그리고 위의 명령어가 실행되면서

PC는 그다음

add $0x1, %eax

주소인 105를 가리키며, eax는 8049a 1c주소(counter)에서 값을 받아 50이 되었다.

그다음

add $0x1, %eax

이 되면서 eax 증가

그다음에 스레드가 교체되면서 문맥 교환이 발생하는데...

그다음에 T2도 T1과 같은 명령어를 수행한다 다만, 차이가 있다면 T2는

mov %eax, 8049a1c

까지 실행하면서 증가한 i값을 counter에 저장하는 것까지 완료하고

그다음에 다시 T2에서 T1으로 문맥 교환이 발생한다.

그러면 T1은 이전에 끊겼던 부분이 복원되면서

108번지 명령어를 다시 실행하게 된다.

mov %eax, 8049a1c

그러면 여기쯤에서 생각을 해 보자.

분명 처음 시작할 때 Counter의 값은 50이었다.

그리고 현재까지 Add 명령어는 2번 실행되었다.

Counter는 전역 변수이므로 2번 증가하게 되었다면 52가 되어야 하는데

T1의 Store 연산이 끝난 후에 보이는 Counter의 값은 51이다.

 

왜 이럴까?

간단하다. T1이 증가한 값을 Counter에 저장하기 이전에 문맥 교환이 발생했고

T2는 증가하지 않은 Counter를 받아 거기서 1을 증가시켰다.

그리고 T2는 다시 문맥 교환을 하고 이전에 멈췄던 부분에서 증가시킨걸 그제야 반영했다.

이 Counter를 증가하는 부분이 Atomic하지 않아 발생한 Concurrency 문제이다!

 

The Wish for Atomicity

그렇다면 이 증가하는 과정을 기계어 하나로 처리할 수 있으면 되지 않을까?(현재는 3줄)

아니라면 이 세 개의 명령어를 Atomic 하게 만들 수 있다면?

이것에 대해서는 천천히 알아보고 우선 용어에 대해 알아보자

용어 설명

• Critical Section
  • 일반적으로 변수 또는 데이터 구조인 공유 리소스에 액세스 하는 코드 조각입니다.
• Race condition
  • 여러 실행 스레드가 거의 동시에 중요 섹션에 진입할 경우 발생합니다. 둘 다 공유 데이터 구조를 업데이트하려고 시도하여 놀라운(아마도 바람직하지 않은) 결과를 초래합니다.
• indeterminate
  • 프로그램은 하나 이상의 'Race Condition'으로 구성됩니다. 프로그램의 출력은 실행마다 다릅니다. 어떤 스레드가 실행되었느냐에 따라 달라집니다. 따라서 결과는 우리가 보통 컴퓨터 시스템에서 기대하는 결정론적이지 않다.
• mutual exclusion
  • 이러한 문제를 피하기 위해 스레드는 일종의 상호 배제 원형(Lock?) 사용해야 한다; 그렇게 함으로써 단 하나의 스레드만이 중요한 섹션에 진입하는 것을 보장하고, 따라서 경주를 피하고, 결과적으로 결정론적 프로그램 출력을 초래한다.

 

현재 지금까지 우리가 본 상황에 대해 위의 용어를 통해 다시 나열하자면,

Counter를 증가시키는 코드 조각들이 Critical Section이며, 따라서 Race Condition은 두 스레드가 같이 Counter를 증가하려고 시도하는 상황을 말한다. 이에 우리는 비결정적인 결괏값을 얻었는데 (2천만이 안나오고 실행마다 매 번 다른 결과값을 얻음) 이것이 indeterminate이다.

이러한 문제를 피하기 위해 해야 하는 것이 mutual exclusion