세마포어
숫자 하나와 줄 하나로 태스크를 기다리게 할 수 있을까?
세마포어
카운터 하나, 큐 하나
세마포어(semaphore)는 1965년에 다익스트라가 내놓은 자료 구조입니다. 지금 지나갈 수 있는 수를 세는 카운터와, 차례를 기다리는 태스크가 서는 큐로 이루어집니다. 연산은 wait와 release 둘뿐입니다.
큐는 먼저 들어온 것이 먼저 나가는 줄입니다. 다익스트라는 두 연산을 P와 V라고 불렀습니다. 카운터의 2는 예시입니다.
wait
남아 있으면 하나 줄이고 지나갑니다
태스크가 wait를 부르면 세마포어는 카운터를 봅니다. 0보다 크면 1 줄이고 그 태스크를 지나가게 합니다. 카운터가 2였으니 둘까지 지나갑니다.
카운터의 처음 값 2는 예시입니다.
카운터가 0일 때
0이면 줄을 섭니다
카운터가 0일 때 wait를 부른 태스크는 지나가지 못하고 세마포어의 큐에 들어가 기다립니다. 2편에서 본 막힘 상태입니다. 그동안 프로세서는 준비 상태인 다른 태스크로 넘어갑니다.
넘겨받을 태스크가 하나도 없으면 교착 상태(서로 기다리다 모두 멈춤, 3편)입니다.
release
기다리는 쪽이 있으면 깨웁니다
일을 마친 태스크는 release를 부릅니다. 큐에 기다리는 태스크가 있으면 맨 앞 하나를 깨워 지나가게 하고, 큐가 비어 있으면 카운터를 1 늘립니다.
깨울 때는 카운터를 늘리지 않습니다. 돌려준 자리를 깨어난 태스크가 곧바로 차지하기 때문입니다.
경쟁 동기화
0과 1뿐이면 자물쇠
공유 데이터를 쓰는 코드를 wait와 release 사이에 넣으면 한 번에 한 태스크만 들어갑니다. 이렇게 카운터가 0과 1만 오가는 세마포어를 이진 세마포어(binary semaphore)라고 합니다.
1이면 열림, 0이면 잠김입니다. 의사코드는 실제 언어가 아니라 뜻만 적은 코드입니다.
원자적 연산
wait는 끊기면 안 됩니다
wait도 카운터를 확인하고 줄이는 두 걸음입니다. 그 사이에 다른 태스크가 끼어들면 둘 다 지나갑니다. 그래서 wait와 release는 끊기지 않는 한 덩어리, 곧 원자적(atomic) 연산이어야 합니다.
카운터가 1일 때의 예시입니다. 3편의 TOTAL과 같은 문제입니다.
다음 편