세마포어와 고전 동기화 문제 — 유한 버퍼, 읽기와 쓰기, 식사하는 철학자

1. 세 가지를 하나로

앞 글에서 락과 조건 변수를 봤습니다. 락은 한 번에 하나만 들어가게 하고, 조건 변수는 조건이 될 때까지 재워 둡니다. 둘을 따로 쓰면 락, 조건 변수, 그리고 끝났는지 같은 상태를 적어 두는 상태 변수까지 세 가지를 늘 묶어 다뤄야 했습니다. 이것을 정수 하나와 동작 두 개로 합친 도구가 세마포어입니다. 이 글은 세마포어가 어떻게 동작하는지 보고, 그것으로 운영체제에서 이름난 동기화 문제 세 가지를 풀어 봅니다.

2. 세마포어는 정수 하나와 동작 둘입니다

세마포어는 정수 값 하나를 가진 객체입니다. 이 값은 두 동작으로만 바꿀 수 있고, 두 동작은 모두 원자적 동작입니다.

• 기다리기 — 값을 1 뺍니다. 뺀 결과가 음수이면 부른 스레드는 잠듭니다.
• 알리기 — 값을 1 더합니다. 그리고 잠든 스레드가 있으면 하나를 깨웁니다.

리눅스의 표준 함수 이름으로는 기다리기가 sem_wait, 알리기가 sem_post입니다. 조건 변수의 기다리기와 신호 보내기와 비슷한 짝입니다. 다른 점은 세마포어는 값을 기억한다는 것입니다.

값은 무엇을 뜻하나

세마포어의 값은 남은 자원의 수로 읽으면 됩니다. 처음 값은 쓸 수 있는 자원의 개수로 정합니다. 프린터가 셋이면 3으로 시작합니다. 한 스레드가 기다리기를 부르면 2가 되고, 그 스레드는 프린터 하나를 씁니다. 셋이 모두 쓰고 있을 때 네 번째 스레드가 기다리기를 부르면 값이 마이너스 1이 되고, 그 스레드는 잠듭니다. 값이 음수이면 그 절댓값이 지금 잠들어 기다리는 스레드의 수입니다. 누군가 프린터를 다 쓰고 알리기를 부르면 값이 0이 되고, 잠들어 있던 스레드 하나가 깨어나 프린터를 받습니다. 값이 여러 가지일 수 있는 이런 세마포어를 계수 세마포어라고 합니다.

3. 초기값을 1로 하면 락이 됩니다

처음 값을 1로 두면 자원이 하나뿐인 셈입니다. 한 스레드가 기다리기를 부르면 0이 되고 임계 구역에 들어갑니다. 그동안 다른 스레드가 기다리기를 부르면 마이너스 1이 되어 잠듭니다. 먼저 들어간 스레드가 나오면서 알리기를 부르면 값이 0이 되고, 잠든 스레드가 깨어나 들어갑니다. 나올 때 다시 알리기를 부르면 1로 돌아옵니다. 한 번에 하나만 들어가니 락과 똑같습니다. 이런 세마포어를 이진 세마포어라고 합니다.

4. 순서를 맞추는 데도 씁니다

세마포어는 순서를 정하는 데도 씁니다. 앞 글에서 부모가 자식 스레드가 끝나기를 기다리는 문제를 조건 변수로 풀었습니다. 세마포어로는 이렇게 합니다. 자식은 할 일을 마치면 알리기를 부릅니다. 부모는 자식을 만든 뒤 기다리기를 부릅니다. 자식이 알리기 전이면 부모는 잠들어 있다가 알림이 오면 깨어나고, 이미 알렸다면 바로 지나갑니다. 이것이 제대로 되려면 세마포어의 처음 값을 알맞게 정해야 합니다.

문제 1

부모가 먼저 기다리기에 도착하든 자식이 먼저 끝나든, 부모는 반드시 자식이 끝난 뒤에만 다음 줄로 가야 합니다. 세마포어의 처음 값은 얼마여야 할까요. 두 경우를 모두 따라가 봅니다.

답은 0입니다. 부모가 먼저 기다리기를 부르면 0에서 1을 빼 마이너스 1이 되니 부모는 잠듭니다. 나중에 자식이 끝나며 알리기를 부르면 0이 되고 부모가 깨어납니다. 자식이 먼저 끝나면 알리기로 0이 1이 되고, 기다리는 스레드가 없으니 그대로 둡니다. 그 뒤 부모가 기다리기를 부르면 1이 0이 되고, 음수가 아니니 잠들지 않고 바로 지나갑니다. 두 경우 모두 자식이 끝난 뒤입니다.

조건 변수와 달리 세마포어는 먼저 온 알림을 값으로 기억하기 때문에, 끝났는지를 적어 둘 상태 변수가 따로 필요 없습니다. 처음 값이 1이었다면 부모는 자식을 기다리지 않고 바로 지나가 버립니다.

5. 유한 버퍼를 세마포어로

유한 버퍼로 돌아갑니다. 버퍼 칸이 정해진 수만큼 있고, 생산자는 빈칸이 있어야 넣을 수 있고, 소비자는 찬 칸이 있어야 꺼낼 수 있습니다. 세마포어 둘로 셉니다. 빈칸 수를 세는 세마포어는 칸 수로 시작합니다. 찬 칸 수를 세는 세마포어는 0으로 시작합니다.

• 생산자 — 빈칸 세마포어에 기다리기를 부르고, 넣은 뒤 찬 칸 세마포어에 알리기를 부릅니다.
• 소비자 — 찬 칸 세마포어에 기다리기를 부르고, 꺼낸 뒤 빈칸 세마포어에 알리기를 부릅니다.

버퍼가 가득 차면 빈칸 값이 0인 상태에서 생산자가 기다리기를 부르니 음수가 되어 잠듭니다. 버퍼가 비면 같은 이유로 소비자가 잠듭니다.

여럿이면 넣는 일 자체가 임계 구역입니다

생산자가 여럿이면 문제가 하나 더 있습니다. 넣는 동작은 지금 쓸 칸 번호에 값을 쓰고 칸 번호를 하나 올리는 두 걸음입니다. 생산자 둘이 동시에 같은 칸 번호를 읽으면 같은 칸에 차례로 써서 앞의 데이터가 덮입니다. 더하기에서 본 것과 같은 경쟁 상태입니다. 그래서 넣고 꺼내는 부분은 락으로 감싸야 합니다. 초기값 1인 이진 세마포어를 하나 더 둡니다. 이제 세마포어가 셋입니다. 빈칸, 찬 칸, 그리고 락입니다. 남은 질문은 락을 어디에 두느냐입니다.

6. 락을 바깥에 두면

문제 2

락을 가장 바깥에 두었습니다. 소비자는 먼저 락 세마포어에 기다리기를 부르고, 그다음 찬 칸 세마포어에 기다리기를 부르고, 꺼낸 뒤 빈칸에 알리기, 락에 알리기 순서로 부릅니다. 생산자도 똑같이 락부터 잡습니다. 버퍼가 비어 있을 때 소비자가 먼저 실행되면 어떻게 될까요.

소비자가 락에 기다리기를 부릅니다. 1이 0이 되어 락을 잡습니다. 그다음 찬 칸에 기다리기를 부릅니다. 버퍼가 비었으니 0이 마이너스 1이 되어 잠듭니다. 락을 쥔 채로 잠든 것입니다. 이제 생산자가 옵니다. 넣으려면 먼저 락에 기다리기를 불러야 하는데, 락은 0이라 마이너스 1이 되어 생산자도 잠듭니다. 소비자는 생산자가 채워 주기를 기다리고, 생산자는 소비자가 락을 놓기를 기다립니다. 서로가 가진 것을 기다리며 아무도 나아가지 못합니다. 이런 상태를 교착 상태라고 합니다.

고치는 방법은 락을 안쪽으로 옮기는 것입니다. 찬 칸이나 빈칸을 먼저 기다리고, 통과한 다음에 락을 잡습니다. 그러면 잠드는 동안에는 락을 쥐고 있지 않습니다.

7. 읽는 쪽과 쓰는 쪽

두 번째 고전 문제입니다. 여러 스레드가 같은 데이터를 봅니다. 어떤 스레드는 읽기만 하고, 어떤 스레드는 고칩니다. 읽기만 하는 스레드끼리는 동시에 봐도 아무 문제가 없습니다. 하지만 누가 고치는 동안에는 다른 누구도 읽거나 고치면 안 됩니다. 이것을 읽기와 쓰기 문제라고 합니다. 평범한 락을 쓰면 읽는 스레드도 하나씩만 들어가니 쓸데없이 느립니다. 그래서 읽기 여럿이나 쓰기 하나를 허락하는 특별한 락을 만듭니다. 읽기와 쓰기 락이라고 부릅니다.

만드는 법

세마포어 둘과 정수 하나로 만듭니다. 쓰기 락은 이진 세마포어입니다. 쓰는 스레드는 이것만 잡고 놓습니다. 읽는 스레드는 지금 읽는 중인 스레드 수를 셉니다. 이 수를 고치는 일도 경쟁 상태가 생기니 작은 락으로 감쌉니다.

• 들어올 때 수를 하나 올립니다. 올린 결과가 1이면 자기가 첫 번째라는 뜻이니, 그때 쓰기 락을 잡습니다.
• 나갈 때 수를 하나 내립니다. 내린 결과가 0이면 자기가 마지막이라는 뜻이니, 그때 쓰기 락을 놓습니다.

그러면 읽는 스레드가 하나라도 있는 동안에는 쓰기 락이 잡혀 있어 쓰는 스레드가 들어오지 못합니다.

이 락의 약점

이 방식에는 공정성 문제가 있습니다. 읽는 스레드가 끊이지 않고 계속 들어오면, 읽는 수가 한 번도 0으로 내려가지 않습니다. 쓰기 락이 계속 잡혀 있으니 쓰는 스레드는 영영 들어가지 못합니다. 스케줄링에서 본 기아입니다. 그래서 쓰는 스레드가 기다리기 시작하면, 그 뒤로 오는 읽는 스레드는 들여보내지 않도록 고친 방식도 씁니다.

8. 식사하는 철학자

세 번째 고전 문제입니다. 둥근 식탁에 철학자 다섯이 앉아 있습니다. 철학자는 생각하다가 배가 고프면 먹습니다. 자리마다 밥그릇이 있고, 두 자리 사이마다 젓가락이 하나씩, 모두 다섯 개가 놓여 있습니다. 먹으려면 자기 양옆의 젓가락 두 개를 모두 들어야 하고, 한 번에 하나씩만 집을 수 있습니다. 다 먹으면 젓가락을 내려놓습니다. 젓가락마다 초기값 1인 세마포어를 하나씩 둡니다. 가장 쉬운 방법은 모두가 왼쪽 젓가락부터 집고 그다음 오른쪽을 집는 것입니다.

모두가 왼쪽을 들면

그런데 다섯 명이 거의 동시에 배가 고파져 모두 왼쪽 젓가락을 집었다고 해 봅니다. 이제 식탁 위에 남은 젓가락이 없습니다. 모두가 오른쪽 젓가락을 기다리는데, 그 젓가락은 오른쪽 사람이 왼손에 들고 있습니다. 누구도 내려놓지 않으니 다섯 명 모두 영원히 기다립니다. 문제 2에서 본 것과 같은 교착 상태입니다. 기다림이 식탁을 따라 한 바퀴 원을 이룬 것입니다.

9. 원을 끊는 법

해결은 이 원을 끊는 것입니다. 가장 간단한 방법은 한 사람만 순서를 바꾸는 것입니다. 네 번째 철학자만 오른쪽부터 집게 합니다. 그러면 모두가 한 개씩 들고 서로를 기다리는 원이 생길 수 없습니다. 다른 방법도 있습니다.

• 식탁에 한 번에 넷까지만 앉게 합니다.
• 양쪽 젓가락이 모두 비었을 때만 집게 합니다.
• 홀수 번 철학자는 왼쪽부터, 짝수 번은 오른쪽부터 집게 합니다.

다만 이런 방법들도 특정 철학자가 계속 굶는 일까지 모두 막아 주지는 않습니다.

정리

세마포어는 정수 하나와 원자적 동작 둘, 기다리기와 알리기입니다. 처음 값을 1로 두면 락이 되고, 0으로 두면 순서를 맞추는 신호가 되며, 자원 수로 두면 남은 자원을 셉니다. 유한 버퍼는 빈칸과 찬 칸을 세마포어로 세고, 넣고 꺼내는 부분만 락으로 감쌉니다. 락을 바깥에 두면 서로를 기다리며 멈춥니다. 읽기와 쓰기 락은 읽기 여럿을 함께 들이고, 식사하는 철학자는 기다림의 원을 끊어 풉니다. 이 글에서 두 번이나 만난 이 멈춤, 서로가 가진 것을 기다리며 아무도 나아가지 못하는 교착 상태를 다음 글에서 제대로 봅니다.