do semaphores satisfies bounded waiting

Question

Does semaphore satisfies bounded waiting or they are just for providing mutual exclusion??

Answer 1

Answer

It may break bounded waiting condition theoretically as you'll see below. Practically, it depends heavily on which scheduling algorithm is used.

The classic implementation of wait() and signal() primitive is as:

//primitive
wait(semaphore* S)
{
    S->value--;
    if (S->value < 0)
    {
        add this process to S->list;
        block();
    }
}

//primitive
signal(semaphore* S)
{
    S->value++;
    if (S->value <= 0)
    {
        remove a process P from S->list;
        wakeup(P);
    }
}

When a process calls the wait() and fails the "if" test, it will put itself into a waiting list. If more than one processe are blocked on the same semaphore, they're all put into this list(or they are somehow linked together as you can imagine). When another process leaves critical section and calls signal(), one process in the waiting list will be chosen to wake up, ready to compete for CPU again. However, it's the scheduler who decides which process to pick from the waiting list. If the scheduling is implemented in a LIFO(last in first out) manner for instance, it's possible that some process are starved.

Example

T1: thread 1 calls wait(), enters critical section
T2: thread 2 calls wait(), blocked in waiting list
T3: thread 3 calls wait(), blocked in waiting list
T4: thread 1 leaves critical section, calls signal()
T5: scheduler wakes up thread 3
T6: thread 3 enters critical section
T7: thread 4 calls wait(), blocked in waiting list
T8: thread 3 leaves critical section, calls signal()
T9: scheduler wakes up thread 4
..

As you can see, although you implements/uses the semaphore correctly, thread 2 has a unbounded waiting time, even possibly starvation, caused by continuous entering of new processes.