+1 vote
197 views
Does semaphore solution fulfill the condition of bounded wait for more than 2 processes

I know we can implement the waiting list in such a way that makes it satisfy bounded wait but what is the standard?
What is the meaning of standard??
standard--- he wants to know general convention which is assumed.

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)
{
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. If the list is implemented in the FIFO manner then it will fulfil bounded wait.

answered by Veteran (11.5k points) 7 63 148

+1 vote