yeolyi.com성열의 컴퓨터공학

경쟁 상태

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

방문자 수를 세는 웹 서버가 있다고 합시다. 방문자가 올 때마다 스레드 하나가 변수 count에 1을 더합니다.

count += 1

+=는 count = count + 1을 줄여 쓴 것입니다. 스레드 A와 B가 이 줄을 1000번씩 실행하면 count는 2000이 되어야 합니다. 정말 그럴까요?

한 줄은 한 번에 실행되지 않는다

컴파일러는 이 한 줄을 명령어 세 줄로 바꿉니다. count가 메모리 12번 주소에 있다면 이렇습니다.

LOAD 12       ← count를 R0으로 가져온다
ADDI R0, 1    ← R0에 1을 더한다
STORE 12      ← R0을 다시 쓴다

스레드마다 R0은 따로입니다. 컨텍스트 스위치가 레지스터를 저장하고 복원하기 때문입니다. 그리고 커널은 타이머가 울리면 아무 명령어 사이에서나 스레드를 바꿀 수 있습니다. 처음 count는 0입니다.

함께 쓰는 메모리
12번 주소count = 0
스레드 A
  1. LOAD 12
  2. ADDI R0, 1
  3. STORE 12
R0 = 0
스레드 B
  1. LOAD 12
  2. ADDI R0, 1
  3. STORE 12
R0 = 0
실행한 순서아직 없습니다. 어느 스레드를 먼저 실행할지 골라 봅시다.
  1. A를 세 줄 모두 실행한 뒤 B를 세 줄 실행해 봅시다.
  2. 처음으로를 누르고 A를 한 줄(LOAD), B를 한 줄(LOAD) 실행한 뒤 나머지를 아무 순서로나 끝내 봅시다.

두 번째 순서에서는 A와 B가 모두 0을 읽고, 둘 다 1을 씁니다. 나중에 쓴 쪽이 먼저 쓴 쪽을 덮어써서 더하기 한 번이 사라집니다.

여섯 줄을 섞는 순서는 여섯 자리 중 A의 세 줄이 들어갈 자리를 고르는 조합이라 6C3 = 20가지입니다. 그중 2가 나오는 것은 한 스레드가 다 끝난 뒤 다른 스레드가 시작하는 두 가지뿐입니다.

경쟁 상태

이처럼 여러 실행 흐름이 같은 데이터를 다룰 때 결과가 명령어가 섞이는 순서에 따라 달라지는 상황을 경쟁 상태(race condition)라 합니다. SR 래치 글에서 어느 게이트가 먼저 반응하느냐에 따라 Q가 달라진 것도 같은 이름으로 불렀습니다. 누가 먼저 하느냐에 결과가 달린다는 점이 같습니다.

이번에는 두 스레드가 1000번씩 더하고, 스레드가 바뀌는 자리는 무작위입니다.

스레드 A와 B가 각각 count += 1을 1000번 합니다. 기대하는 값은 2000입니다.

실행을 눌러 봅시다.

실행을 여러 번 눌러 봅시다.

값이 매번 다르고 2000은 한 번도 나오지 않습니다. 이 데모는 스레드를 자주 바꿔 매번 틀립니다. 실제 코어 하나에서는 스레드가 바뀌는 일이 드물어 대부분 맞는 답이 나오고 가끔만 틀립니다. 그래서 시험할 때는 멀쩡하다가 사용자가 많은 날에야 틀립니다. 멀티코어에서는 두 스레드가 같은 순간에 LOAD를 실행할 수도 있어 더 쉽게 일어납니다.

도전 문제

스레드 A와 B가 각자 count += 1을 세 번씩 실행합니다. 한 번은 본문처럼 LOAD, ADDI, STORE 세 명령어이고, 처음 count는 0이며, 스레드는 아무 명령어 사이에서나 바뀔 수 있습니다. 두 스레드가 모두 끝난 뒤 count로 나올 수 있는 가장 작은 값은 얼마일까요? 숫자로 답하세요.