Semaphore and Mutex

1965년에 E. W. Dijkstra는 wakeup 수를 카운트하기 위한 정수 변수, 즉 세마포어(Semaphore)라는 새로운 변수형을 제안하였다. 세마포어는 wakeup이 하나도 없는 0 값을 가질 수도 있고, 하나 이상이 보류되어 있는 양수값을 가질 수도 있다.

Dijkstra는 sleep과 wakeup에 대응되는 두 개의 동작 down, up을 갖도록 제안하였다. down 동작은 해당 세마포어 변수가 0보다 큰가를 검사한다. 큰 값이면 1만큼 감소시키고 계속된다. 만약 0이면 그 프로세스는 바로 자게 된다. 변수를 검사하고, 변경하고, 잘 수 있게 하는 동작은 분리되지 않는 단위동작으로 일어난다. 이것은 세마포어 동작이 일단 시작되면 다른 어떤 프로세스도 이 동작이 완료되거나 블록되지 않는 한 액세스 할 수 없다. 이 단위성(automicity)이 동기화 문제 해결이나 경쟁조건을 피하는데 절대적으로 필요하다.

up 동작은 지정한 세마포어의 변수값을 증가시킨다. 만약 이전의 down 동작을 완료하지 못한 하나 이상의 프로세스가 그 세마포어에서 자고 있다면 시스템은 그들 중 하나를 선택하여 down 동작을 끝낼 수 있도록 한다. 그러나 자고 있는 프로세스를 갖는 세마포어 상에서 up 동작 이후에도 세마포어는 0 값을 갖지만 이 세마포어에서 자고 있는 몇 개인가 프로세스가 아직 남아 있다. 세마포어 증가동작과 한 프로세스를 깨우는 동작도 단위동작으로 이루어진다. 앞의 모델에서와 같이 wakeup을 수행하는 동안 어떤 프로세스도 블록되지 않는 것처럼 up을 수행하는 중에도 어떤 프로세스도 블록되지 않는다.


세마포어의 카운트 기능이 필요 없을 때는 뮤텍스(Mutex)라는 세마포어의 간단한 버전이 간혹 사용된다. 뮤텍스는 어떤 공유 자원이나 코드 부분에 대한 상호 배제를 관리하는데 아주 좋다. 특히 사용자 공간에서 완전하게 구현될 수 있는 스레드 패키지에 아주 유용하게 간단하고 쉽게 구현될 수 있다.

뮤텍스는 잠김(lock)과 풀림(unlock)이란 두 상태 중 한 상태를 갖는 변수이다. 결국 한 비트만 가지고도 표현할 수 있다. 그러나 실제로는 0을 풀림, 잠김으로는 다른 값을 이용한다. 스레드 또는 프로세스가 임계구역에 들어갈 때 mutex_lock을 호출한다. 만일 뮤텍스가 임계구역의 사용 가능함을 의미하는 풀림 상태라면 호출은 성공하고, 호출한 스레드는 마음 놓고 임계구역에 들어갈 수 있다.

반면, 뮤텍스가 잠김 상태라면 호출한 프로세스는 임계구역에 있는 스레드가 수행을 마치고 mutex_unolck을 호출해줄 때까지 블록된다. 혹시 여러 스레드들이 뮤텍스상에서 블록되어 있다면 그 중 하나가 랜덤하게 선택되어 수행하도록 한다.

뮤텍스는 간단하기 때문에 TSL 명령만 갖고 있다면 쉽게 사용자 공간에서도 구현이 가능하다.


Reference
Andrew S. Tanenbaum, Modern Operating System, Second Edition