경쟁 상태

1. 소개[편집]

---

Race condition

프로그램이나 시스템 등의 실행/출력 결과가 일정하지 않고, 입력의 타이밍, 실행되는 순서나 시간 등에 영향을 받게 되는 상황. 결과가 매번 달라지므로 버그를 불러오기 딱 좋다.

2. 데이터 레이스[편집]

---

Data race

여러 프로세스/스레드가 공유된 데이터를 읽고 쓰는 작업을 할 때 실행 순서에 따라서 잘못된 값을 읽거나 쓰게 되는 상황. 병렬 처리를 하는 경우에 아주 흔하게 발생하므로 뮤텍스, 세마포어 등으로 처리해준다.

2.1. 프로그래밍 지식이 필요없는 예시[편집]

---

A와 B가 한 집에 사는데, 둘 다 달걀을 아주 좋아해서 자주 먹는다. 달걀이 다 떨어지면 사와야 하는데, 처음에는 A가 그걸 맡기로 했다. 그러자 곧 문제점을 발견할 수 있었는데, B가 달걀이 먹고 싶어도 A가 자기 일을 다 마치고 달걀을 사올 때까지 기다려야 한다는 것이다. 또는 B가 매번 A에게 달걀을 바로 사다달라고 부탁할수도 있지만 그것은 A에게 매우 귀찮은 일이다.

따라서 더 상식적인 방법으로, 달걀이 없는 걸 확인한 사람이 달걀을 사오기로 한다. 보통의 경우는 달걀을 곧바로 사와서 떨어지지 않게 잘 유지되지만, 어느날 문제가 생긴다. A가 달걀을 사러 간 사이에 B가 달걀이 없는 걸 보고 자신도 달걀을 사온 것이다. B가 집에 도착해보니 A가 이미 달걀을 사 와서 달걀이 너무 많아진 것이다. (이를 컴퓨터공학 쪽에서는 너무 많은 우유 문제라고 부른다.) 결국 둘은 머리를 맞대고 더 나은 방안을 생각해 보았다.

둘이 새로 생각해 낸 방법은 달걀이 떨어진 것을 보면 그 자리에 메모를 남겨두고 달걀을 사러 가는 것이다. 나중에 본 사람은 메모를 보고 상대방이 달걀을 사러 간 것을 알 수 있으니 자기는 달걀을 사지 않게 된다. 하지만 문제는 또 발생할 수 있는데, A가 메모를 쓰러 간 사이 B가 달걀이 없는 걸 보고 자기도 메모를 써놓고 잽싸게 달걀을 사와버렸다. A는 다 쓴 메모를 붙이고는 자신도 달걀을 사온다.

물론 보통의 사람이라면 그러지 않을 것이므로, 메모를 붙일 때에도 메모가 이미 붙어있는지, 또는 혹시 그새 다른 사람이 달걀을 사왔는지 확인한다고 하자. 그러나 마찬가지 문제는 또 발생할 수 있는데, A가 메모가 없는 걸 확인한 순간과 메모를 붙이는 순간 사이에 B가 메모를 붙인다면? 메모는 두 개 붙어있고 달걀도 두 판이 될 것이다. 그걸 막기 위해 메모를 붙인 다음에 혹시 메모가 두 장 붙어있지 않은지 확인한다면, 'A가 메모를 붙임 ▷ B가 메모를 붙임 ▷ A가 메모가 둘 있는 걸 확인함 ▷ B도 메모가 둘 있는 걸 확인함 ▷ 각자 자기 메모를 떼어내고 달걀은 사오지 않음' 의 순서로 사건이 일어나는 경우 아예 달걀을 누구도 사오지 않게 된다. 결과적으로 누군가 달걀을 사오게 될 때까지 위 행동을 반복한다면? 매번 같은 일이 일어나지 않으리란 보장이 없다.

이처럼 보통의 경우에는 잘 작동하는 것이 A와 B의 행동의 특정한 순서의 경우 문제가 발생하는 것이 경쟁 상태이다. 실제 달걀의 경우라면 두 개를 사왔든 아니면 조금 늦게 사왔든 전혀 문제가 없겠지만, 실수가 용납되지 않는 상황에서도 둘 이상의 사람이 무언가를 공유하고 있다면 같은 방식으로 의해 경쟁 상태가 발생할 수 있다.

물론 위의 예는 매우 과장된 것이다. 사람이라면 달걀이 없는 걸 확인한 다음 메모를 붙이는 것도, 메모가 없는 걸 확인한 다음 메모를 붙이는 것도, 또는 메모를 붙이고 메모가 둘 있는 건 아닌지 확인하는 것도 다른 누군가가 끼어들 수 없을만큼 찰나의 순간에 해낼 것이다. 그리고 사실은 이것이 경쟁 상태를 해결하는 핵심 아이디어인데, 바로 달걀이 없는 걸 확인하고 달걀을 사오는 과정에서의 특정 부분을 순식간에 해내는 것이다. 즉 달걀이 없는 것을 확인하는 것과 달걀을 사오는 것을 순식간에 하거나 (그러나 이것은 당연히 불가능하다), 달걀이 없는 것을 확인하는 것과 메모를 붙이는 것을 순식간에 하거나 (이것은 현실적으로 가능하다), 메모를 붙이고 메모가 두 장 있는 건 아닌지 확인하는 것을 순식간에 해내는 것이다 (이것은 앞의 것보다도 더 쉽다). 이렇게 하면 그 사이에 다른 사람이 잘못된 정보를 읽어가거나 하는 문제를 원천적으로 해결할 수 있다. 이것을 추상화 한 것이 뮤텍스, 세마포어 등이다.

2.2. 실제 소프트웨어에서[편집]

---

실제 CPU는 메모리에 적재되어 있는 값을 직접적으로 연산 하는것은 불가능하고 메모리에 적재되어 있는 값을 레지스터로 가져와서 연산을 수행하고 연산 결과를 레지스터에서 다시 메모리에 써야 하는데 데이터(보통은 메모리이므로 앞으로는 메모리로 쓰겠다.)를 읽고 쓰는 일은 매우 빠르게 일어나지만, 읽는 것과 쓰는 것은 별개의 명령어로 분리되어 있다. 예를 들어 C에서의 증가 연산자 ++는 하나의 연산으로 보이지만, 실제로는 변수를 읽는 명령어, 1을 더하는 명령어, 변수에 저장하는 명령어로 이루어진다. 또는 if(a==0)식의 조건 분기가 있다면, a를 읽는 명령어, 0인지 확인하는 명령어, 확인한 결과를 가지고 분기하는 명령어 등이 실행된다. 멀티태스킹을 하는 경우라도 이 명령어들은 매우 빠르게 실행되고 많은 경우에 문제를 발생시키지 않지만, 어떤 명령어 다음에서든지 실행이 멈추고 다른 스레드가 실행될 수 있다. 따라서 위의 예시처럼 A 스레드가 읽고 다시 쓰기 전에 B 스레드가 읽어간다든가, A 스레드가 a==0인 것을 확인하고 분기하려는데 그 사이 B 스레드가 a의 값을 바꾼다든가의 경쟁 상태가 발생한다.

해결책은 원자적(atomic) 명령어를 쓰는 것이다. 여기서 원자적은 작게 쪼갤 수 없다는, 즉 그 사이에 다른 일이 일어날 수 없다는 뜻이다. 예를 들어 x86에는 lock xadd라는 증가 연산자의 원자적 버전이 있는데, 읽고 증가하고 저장하는 와중에 다른 스레드가 맘껏 끼어들 수 있는 보통의 메모리 작업과는 다르게 lock xadd는 원자적이므로 겉으로 보기에 확실하게 1을 증가시켜 준다. 따라서 다른 스레드가 증가되기 전 값을 읽어간다거나 하는 문제가 발생하지 않는다. 또한 이러한 명령어들을 사용하여 추상화된 개념인 뮤텍스, 세마포어 등을 구현할 수 있다. 많은 프로그래밍 언어들이 원자적 연산을 직접적으로 지원하거나 뮤텍스 등을 지원한다.

2.2.1. 실제 프로그램 예[편집]

---

예를 들어서, int값 count를 100000회 올리는 간단한 프로그램을 생각해 보자.

class Counter {
  int count=0;
  Counter() {
    count();
  }

  void count() {
    for(int i=0; i<100000; i++) {
      count++;
    }
  }
}

이 코드는 문제없이 실행된다. 이제 이 코드를 멀티스레드로 변환시켜보자.

class Counter {
  int count=0;
  Counter() {
    Thread thread1 = new Thread(new Runnable() {
      @Override
      public void run() {
        count();
      }      
    });
    Thread thread2 = new Thread(new Runnable() {
      @Override
      public void run() {
        count();
      }      
    });
    thread1.start();
    thread2.start();
  }

  void count() {
    for(int i=0; i<100000; i++) {
      count++;
    }
  }
}

count를 10만회씩 올리는 스레드를 두 개 작성하여 실행했다. 이 코드를 실행시키면 직관적으로 20만이 나와야 한다. 그러나 실제로 이 코드를 실행시키면 count가 20만은 커녕 109012, 107496, 102658 등 10만에 가까운 엉뚱한 값이 나오게 된다. 왜 이상한 값이 나오는 걸까?
그 이유는 실제로 "count++"가 단일 명령이 아니기 때문이다. 실제로 count++는 세 가지 명령으로 구성되어있다. 알기 쉽도록 코드로 설명을 하자면,

int temp = count;
temp = temp+1;
count = temp;

[1]
그러면 이제 두 스레드가 돌아갈 때 무슨 일이 일어났는지 알 수 있게 된다.

1. 스레드 1이 count의 값 0을 받아온다.
2. 스레드 1이 0에 1을 더한다.
3. 컨텍스트 스위칭(작업하는 스레드를 바꿈)을 한다.
4. 스레드 2가 count의 값 0을 받아온다.
5. 스레드 2가 0에 1을 더한다.
6. 컨텍스트 스위칭을 한다.
7. 스레드 1이 더한 값 1을 count에 쓴다.
8. 스레드 2가 더한 값 1을 count에 쓴다.

[2]
스레드 두 개가 count를 하나씩 각각 올렸는데 값은 2가 아닌 1이 올랐다.

이렇게 잘못된 값이 쓰이는 것을 방지하기 위해서 Lock이라는 방법이 개발되었다.[3] 간단히 설명을 하자면, "내가 하는 행동이 끝나기 전에는 다른 어떤 곳에서도 이 값을 건드리지 마시오"라고 선언하는 것이다. 그러면 실행 순서는 이렇게 된다.

1. 스레드 1이 count에 Lock을 건다.
2. 스레드 1이 count의 값 0을 받아온다.
3. 스레드 1이 0에 1을 더한다.
4. 컨텍스트 스위칭을 한다.
5. 스레드 2가 count의 값을 받아오려고 하였으나 Lock이 걸려있어 풀릴 때까지 대기한다.
6. 컨텍스트 스위칭을 한다.
7. 스레드 1이 더한 값 1을 count에 쓴다.
8. 스레드 1이 count에 걸린 Lock을 푼다.
9. 컨텍스트 스위칭을 한다.
10. 스레드 2가 count에 Lock을 건다.
11. 스레드 2가 count의 값 1을 받아온다.
12. 스레드 2가 1에 2를 더한다.
13. 스레드 2가 더한 값 2를 count에 쓴다.
14. 스레드 2가 count에 걸린 Lock을 푼다.

이제 컨텍스트 스위칭이 1~13 어느 곳에 있어도, 매 단계마다 있는 한이 있더라도 정확한 값을 구할 수 있다.
그러나 이 방법에는 성능에 문제가 생긴다. 딱 봐도, 위에는 8단계이지만 밑에는 14단계다. 그래서 대부분의 프로그래밍 언어에서는 exclusive lock과 non-blocking algorithm을 모두 지원한다. Java를 예로 들면 전자는 synchronized 블록이고, 후자는 AtomicInteger 등이 대표적이다.

이렇게 공유되는 자원에 서로 값을 쓰려는 '경쟁적인' 상황을 경쟁 조건이라고 한다.