동기화 도구 — 경쟁 상태, 락, 조건 변수

1. 두 스레드가 같은 칸을 고친다

앞 글 끝에서 미뤄 둔 문제가 있었습니다. 선점 스케줄링에서는 프로세스가 공유 데이터를 고치던 도중에 프로세서를 뺏길 수 있고, 그러면 데이터가 어긋날 수 있습니다. 스레드는 처음부터 메모리를 함께 쓰니 이 문제를 더 자주 만납니다. 이 글은 어떻게 어긋나는지를 숫자로 직접 확인하고, 그것을 막는 도구들을 하나씩 만들어 봅니다.

상황 하나를 세웁니다. 생산자 스레드는 데이터를 만들어 버퍼에 넣고, 소비자 스레드는 버퍼에서 꺼내 씁니다. 버퍼는 둘이 함께 봅니다. 버퍼에 몇 개가 들어 있는지는 카운터라는 변수 하나로 셉니다. 생산자는 하나 넣을 때마다 카운터에 1을 더하고, 소비자는 하나 꺼낼 때마다 1을 뺍니다. 카운터가 5일 때 생산자가 하나 넣고 소비자가 하나 꺼냈다면, 당연히 5로 돌아와야 합니다. 그런데 실제로 돌려 보면 4가 되기도 하고 6이 되기도 합니다.

2. 한 줄짜리 더하기는 사실 세 걸음입니다

이유는 카운터에 1을 더하는 한 줄이 기계어로는 세 걸음이기 때문입니다. 먼저 메모리의 카운터 값을 레지스터로 읽어 옵니다. 다음 레지스터에서 1을 더합니다. 마지막으로 레지스터 값을 메모리에 다시 씁니다. 빼기도 똑같이 읽고, 빼고, 씁니다. 그리고 선점 스케줄러는 이 세 걸음 중 어디서든 프로세서를 다른 스레드에 넘길 수 있습니다.

최종 값은 4입니다. 생산자의 더하기가 통째로 사라졌습니다. 쓰는 순서가 반대였다면 6이 남았을 것입니다. 결과가 누가 언제 끼어들었느냐에 따라 달라집니다.

문제 1

전역 변수 값이 0입니다. 스레드 둘이 각각 이 변수에 1을 더하는 한 줄을 딱 한 번씩 실행합니다. 둘 다 끝났을 때 변수 값으로 나올 수 있는 것을 모두 답하고, 각각 어떤 순서일 때 그렇게 되는지 설명해 보십시오.

각 스레드는 읽기, 더하기, 쓰기 세 걸음을 합니다. 스레드 A가 세 걸음을 모두 마친 뒤에 스레드 B가 시작하면, A가 1을 쓰고 B는 1을 읽어 2를 씁니다. 결과는 2입니다. A가 0을 읽은 뒤 쓰기 전에 B로 넘어가면, B도 0을 읽습니다. 둘 다 1을 만들어 차례로 1을 씁니다. 결과는 1입니다. 한 번의 더하기가 사라진 것입니다. 그래서 답은 1과 2입니다. 0이나 3은 나올 수 없습니다. 적어도 한 번은 읽은 값에 1을 더해 쓰고, 두 번보다 많이 더할 수는 없기 때문입니다.

3. 경쟁 상태와 임계 구역

여럿이 같은 데이터를 동시에 읽고 고칠 때, 결과가 실행 순서에 따라 달라지는 상황을 경쟁 상태라고 합니다. 이것을 막으려면 한 번에 하나만 공유 데이터에 손대게 해야 합니다. 이렇게 순서를 맞추는 일을 동기화라고 합니다. 코드에서 공유 데이터를 고치는 부분을 임계 구역이라고 부릅니다. 한 스레드가 임계 구역에 있으면 다른 스레드는 자기 임계 구역에 들어가면 안 됩니다. 그래서 코드를 넷으로 나눠 봅니다.

• 진입 구역 — 들어가도 되는지 묻습니다.
• 임계 구역 — 공유 데이터를 고칩니다.
• 퇴출 구역 — 나왔다고 알립니다.
• 나머지 구역 — 공유 데이터와 상관없는 부분입니다.

운영체제 커널 안에서도 같은 일이 생깁니다. 두 프로세스가 동시에 fork를 부르면, 다음에 줄 pid 번호를 두 자식이 똑같이 받을 수 있습니다.

4. 락

해결의 기본 도구는 락입니다. 임계 구역 앞뒤에 코드를 한 줄씩 덧붙입니다. 들어가기 전에 락을 잡고, 나온 뒤에 락을 놓습니다. 락은 두 상태만 가집니다. 아무도 안 잡은 풀린 상태와, 정확히 한 스레드가 잡고 있는 잠긴 상태입니다. 락을 잡으려 할 때 이미 누가 잡고 있으면 풀릴 때까지 기다립니다. 그래서 임계 구역 안에는 언제나 하나만 있게 됩니다. 락을 잡은 스레드를 락의 주인이라고 하고, 주인만 락을 놓을 수 있습니다. pthread에서는 이런 락을 뮤텍스라고 부릅니다. 서로 배제한다는 뜻입니다.

좋은 락의 조건

1. 상호 배제 — 둘 이상이 동시에 임계 구역에 들어가면 안 됩니다.
2. 진행 — 임계 구역이 비어 있고 들어가려는 스레드가 있으면, 그중 누군가는 반드시 들어가야 합니다.
3. 한정 대기 — 들어가겠다고 한 뒤로 다른 스레드들이 먼저 들어가는 횟수에 한도가 있어야 합니다. 그래야 한 스레드가 영영 굶지 않습니다.
4. 성능 — 락을 쓰느라 드는 시간이 적게 걸려야 합니다.

5. 락을 만드는 쉬운 방법 둘, 그리고 실패

첫 번째 생각은 임계 구역 동안 인터럽트를 꺼 버리는 것입니다. 인터럽트가 없으면 끼어들 일도 없습니다. 하지만 응용 프로그램에게 인터럽트를 끌 권한을 주면, 한 프로그램이 프로세서를 독차지할 수 있습니다. 코어가 여럿이면 다른 코어는 막지도 못합니다.

두 번째 생각은 깃발 변수를 두는 것입니다. 깃발이 1이면 기다리고, 0이면 1로 바꾸고 들어갑니다. 그런데 깃발이 0인 것을 확인하고 1로 바꾸기 직전에 다른 스레드로 넘어가면, 그 스레드도 0을 보고 1로 바꾸고 들어갑니다. 둘 다 들어갑니다. 확인하는 걸음과 바꾸는 걸음 사이에 끼어든 것입니다. 앞에서 본 더하기와 같은 문제입니다.

6. 끊기지 않는 명령과 스핀 락

해결하려면 확인과 바꾸기를 끊기지 않는 한 걸음으로 해야 합니다. 이렇게 중간에 끼어들 수 없이 한 번에 끝나는 동작을 원자적이라고 합니다. 소프트웨어만으로는 어렵고 하드웨어가 도와줍니다. 대표가 테스트 앤 셋 명령입니다. 메모리 칸의 옛 값을 돌려주면서 동시에 새 값을 써넣습니다.

락은 이렇게 만듭니다. 깃발에 1을 쓰면서 옛 값을 받아 봅니다. 옛 값이 0이었다면 방금 내가 잡은 것이니 들어갑니다. 옛 값이 1이었다면 누가 잡고 있던 것이니 다시 시도합니다. 들어가지 못한 스레드는 이 시도를 계속 반복하며 제자리에서 돕니다. 그래서 이런 락을 스핀 락이라고 부릅니다.

스핀 락은 어떤가

상호 배제는 됩니다. 원자적 명령 덕분에 한 번에 하나만 들어갑니다. 공정성은 없습니다. 풀리는 순간 누가 먼저 잡을지 정해져 있지 않아서, 운 나쁜 스레드는 계속 돌기만 할 수 있습니다. 성능은 상황에 따라 다릅니다. 코어가 하나면 끔찍합니다. 락을 잡은 스레드가 프로세서를 뺏긴 동안, 기다리는 스레드는 받은 시간 조각인 퀀텀을 통째로 헛돌며 날립니다. 반대로 코어가 여럿이고 임계 구역이 짧으면 꽤 잘 동작합니다. 다른 코어에서 곧 풀어 주기 때문입니다.

7. 다른 원자적 명령들

하드웨어는 다른 원자적 명령도 줍니다. 비교 후 교환은 메모리 값이 기대한 값과 같을 때만 새 값으로 바꿉니다. 테스트 앤 셋보다 조건을 더 세밀하게 걸 수 있습니다. 가져오며 더하기는 값을 1 올리면서 옛 값을 돌려줍니다.

가져오며 더하기로 공정한 락을 만들 수 있습니다. 은행 번호표와 같습니다. 락을 원하는 스레드는 번호표를 한 장 뽑습니다. 락에는 지금 차례 번호가 있습니다. 자기 번호가 차례가 될 때까지 기다리고, 락을 놓을 때 차례 번호를 하나 올립니다. 뽑은 순서대로 들어가니 영영 굶는 스레드가 없습니다. 이것을 티켓 락이라고 합니다.

8. 헛돌지 말고 잠들기

스핀 락의 가장 큰 낭비는 헛도는 시간입니다. 운영체제의 도움을 받으면 줄일 수 있습니다. 가장 쉬운 방법은 락을 못 잡으면 프로세서를 스스로 양보하는 것입니다. 하지만 기다리는 스레드가 많으면 양보할 때마다 문맥 교환이 일어나 그 비용도 큽니다.

더 나은 방법은 기다리는 스레드를 줄 세워 재우는 것입니다. 락을 못 잡으면 대기 줄에 이름을 올리고 잠듭니다. 락을 놓는 스레드는 줄 맨 앞의 스레드 하나만 깨웁니다. 리눅스는 이 기능을 퓨텍스라는 시스템 콜로 줍니다. 실제로는 둘을 섞습니다. 곧 풀릴 것 같으면 잠깐 돌아 보고, 그래도 못 잡으면 잠드는 것입니다. 이것을 두 단계 락이라고 합니다.

9. 조건을 기다리기 — 조건 변수

락은 한 번에 하나만 들어가게 해 줍니다. 그런데 어떤 조건이 참이 될 때까지 기다려야 하는 경우도 있습니다. 예를 들어 부모 스레드는 자식 스레드가 끝나기를 기다려야 할 때가 있습니다. 끝났는지를 나타내는 변수를 두고 부모가 그 값을 계속 확인하며 돌면 프로세서를 낭비합니다.

이때 쓰는 것이 조건 변수입니다. 조건 변수는 조건을 기다리는 스레드들의 대기 줄입니다. 조건이 아직 아니면 기다리기를 불러 잠들고, 다른 스레드가 상태를 바꾼 뒤 신호 보내기를 부르면 그중 하나가 깹니다. 신호 보내기는 그 순간 줄에서 잠들어 있는 스레드만 깨웁니다. 기다리는 스레드가 없을 때 보낸 신호는 어디에도 남지 않습니다. 조건 변수는 항상 락, 그리고 상태를 적는 변수와 한 묶음으로 씁니다. 기다리기는 락을 쥔 채 불러야 하고, 잠들면서 락을 풀었다가 깨어날 때 다시 잡습니다.

문제 2

부모가 자식 스레드를 만든 뒤 조건 변수로 자식이 끝나기를 기다립니다. 그런데 이 코드는 끝났는지를 적는 상태 변수를 쓰지 않습니다. 부모는 락을 잡고 곧바로 기다리기를 불러 잠들고, 자식은 할 일을 마치면 락을 잡고 신호 보내기를 부른 뒤 락을 놓습니다. 만약 자식이 먼저 실행되어 부모가 기다리기를 부르기도 전에 끝나 버리면, 부모는 어떻게 될까요.

자식이 먼저 돌아 신호 보내기를 부릅니다. 그런데 그 순간 조건 변수의 대기 줄에는 아무도 없습니다. 부모가 아직 잠들지 않았기 때문입니다. 깨울 스레드가 없으니 신호는 아무 일도 일으키지 않고 사라집니다. 조건 변수는 신호를 저장해 두지 않습니다. 그다음 부모가 기다리기를 불러 잠듭니다. 신호를 보낼 자식은 이미 끝났으니 부모는 영원히 잡니다. 그래서 상태 변수가 필요합니다. 자식은 끝났다고 변수에 적고 신호를 보내고, 부모는 잠들기 전에 그 변수를 먼저 확인해서 이미 끝났으면 잠들지 않습니다.

10. 생산자와 소비자를 제대로

처음의 생산자와 소비자로 돌아갑니다. 버퍼 크기가 정해져 있으니, 가득 차면 생산자가 기다리고 비면 소비자가 기다려야 합니다. 이것을 유한 버퍼 문제라고 합니다. 셸에서 한 프로그램의 출력을 파이프로 다른 프로그램에 넘길 때 커널 안의 버퍼가 바로 이것입니다. 조건 변수로 풀 때 규칙이 둘 있습니다.

1. 깨어나면 조건을 다시 확인합니다. 신호를 받고 실제로 돌기까지의 사이에 다른 스레드가 먼저 버퍼 상태를 바꿔 놓았을 수 있기 때문입니다. 그래서 조건이 맞지 않는 동안은 몇 번이든 다시 기다리도록 씁니다.
2. 조건 변수를 둘로 나눕니다. 생산자는 빈자리를 기다리고 소비자는 채워지기를 기다립니다. 하나만 쓰면 소비자가 다른 소비자를 깨우는 엉뚱한 일이 생깁니다.

정리

한 줄짜리 더하기도 읽고, 고치고, 쓰는 세 걸음이라 그 사이에 끼어들면 결과가 어긋납니다. 이것이 경쟁 상태이고, 공유 데이터를 고치는 코드가 임계 구역입니다. 락은 임계 구역에 한 번에 하나만 들어가게 하고, 그 락은 하드웨어의 원자적 명령으로 만듭니다. 헛도는 낭비는 잠들고 깨우는 방식으로 줄이고, 조건을 기다릴 때는 조건 변수를 락, 상태 변수와 함께 씁니다. 다음 글에서는 이 도구들을 하나로 묶은 세마포어를 보고, 그것으로 이름난 동기화 문제들을 풀어 봅니다.