Taeguk's Blog

mutex, semaphore, conditional variable, monitor의 차이점에 대해 서술해보겠다. 참고로 아래의 내용은 특정 OS에 국한된 특수한 내용이 아니라 general concept에 대한 내용이다.   mutex는 locking mechanism이다. 즉 mutual exclusion을 위한 것으로서 lock의 owner가 존재한다. 교과서적으로는(이론적으로는) mutex와 binary semaphore를 같게 취급하는 경우도 있지만, 실제 implementation에서는 mutex는 ownership의 개념이 있다는 측면에서 다르다. binary semaphore는 누구나 up하고 down할 수 있지만, mutex는 lock의 owner만 release할 수 있다.   semaphore는 signal mechanishm이다. semaphore count가 0일 경우 non-signaled, 1이상일 경우 signaled상태라고 할 수 있다. 누구나 semaphore count를 up 혹은 down할 수 있다. semaphore는 mutex보다 general하게 사용될 수 있다. semaphore도 locking mechanism으로서 사용될 수 있겠지만 mutex를 사용하는 것이 좀 더 옳은 방법일 것이다.    semaphore는 생산자-소비자 모델에서 활용될 수 있을 것이다. 여러개의 생산자 thread, 여러개의 소비자 thread가 있을 때 생산자는 생산이 완료되면 semaphore를 up하고, 소비자는 소비를 하기전에 down하는 식으로 생산자-소비자 모델을 구현할 수 있을 것이다.   conditional variable은 특정 조건이 성립할 때까지 wait하고, 조건이 성립할 때 wait하고 있는 thread 1개 혹은 여러개를 깨울 수 있는 mechanism이다. conditional variable은 보통 mutex와 associated되어 사...

Pintos의 threads/synch.c 의 일부이다. Pintos에서는 conditional variable을 구현하기 위해 semaphore list를 사용한다. 근데 사실 semaphore 한 개만을 사용해도 괜찮아 보일 수 있다. 어차피 semaphore 자체적으로 waiter들을 list로 관리하고, queue처럼 사용되므로 semaphore list를 사용할 필요없이 한 개의 semaphore를 가지고 conditional variable을 구현해도 상관이 없어 보인다. 하지만 이렇게 되면 cond_wait가 호출 된 후 cond_signal이 호출 됬는데, 먼저 호출된 cond_wait에서 signal을 받지 못하는 경우가 있을 수 있다. 왜냐면 lock_release를 하고 sema_down을 하게 될 텐데, lock_release 직후에 다른 thread가 스케쥴링되고 그 thread에서 cond_signal하게 되면 semaphore에 waiter가 없으므로 sema_up을 하지 않을테고 먼저의 thread는 signal을 받지 못하는 경우가 생길 수 있다. 이것이 그렇게 critical한 문제일까? lock_release시에 lock을 기다리는 thread가 없는 경우라면 아마 대부분 sema_down으로 흐름이 이어질테니까 대부분의 경우에는 문제가 안생기고 가끔 문제가 발생할 것이다. 근데 lock을 기다리고 있고 lock을 얻은 후 cpu-burst동안 cond_signal을 호출 하는 thread가 있을 경우에는 cond_wait가 평균적으로 1개의 signal을 씹을 것이다. 즉 충분히 critical한 문제라고 할 수 있다. 하지만 만약 cond_wait에서 1개 정도의 signal은 씹혀도 크게 상관없는 상황이라면 한 개의 semaphore를 가지고 conditional varaible을 구현해도 상관이 없을 것이다. 여기서 한 개의 semaphore를 가진다고 해서 conditional varia...