Pintos의 conditional variable implementation에서 semaphore list를 쓰는 이유
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...