Doubt (Count semph, implemented by bin semph.)

[Rashmi Konnur]

In the slide pg.22, why is wait(S) nested inside another wait_b-signal_b pair? Shouldn't the wait_b(S2) be sufficient for maintaining a queue of procs? Is the Wait_b(S3) used for bounded waiting?

[Mandar Mitra]

I did not have time to discuss binary semaphores in class, so this is, strictly speaking, not in the syllabus.

But the answer is yes, S3 is required to ensure bounded waiting.

Without S3, the following could happen. Suppose C is initialised to 1, and P0 is in the critical section. When P1 is inside wait(S), there could be a context switch between signal_b(S1) and wait_b(S2). During this time, P2 and P0 could get alternating access to the critical section an arbitary number of times before P1 gets access, violating bounded waiting.