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 variable = semaphore라는 건 아니다. 왜냐하면 semaphore는 up을 하면 시간이 흐른뒤에 down을 해도 유효한데, conditional variable은 siganl을 보낸 순간에 wait하고 있는 thread들만 영향을 받아야 하기 때문이다. 만약 signal을 보낸 뒤에 시간이 흐른 뒤에 wait를 호출해도 영향을 받는 형태로 구현을 한다고 치면 이것은 그냥 세마포어이지 conditional variable이 아니다.
만약 cond_signal이 호출되면 반드시 그 전에 cond_wait를 호출한 thread에게 signal이 가야만하는 경우라면 semaphore list를 사용하는 것이 옳고 대부분의 경우 이러한 implementation을 사용해야만 할 것이다.
관련 링크----
댓글
댓글 쓰기