1,460 views
1 votes
1 votes
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?

1 Answer

0 votes
0 votes

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

Related questions

1 votes
1 votes
0 answers
1
1 votes
1 votes
1 answer
2
Rahul_Rathod_ asked Dec 12, 2018
1,503 views
a) s1-wait(p) , s2-wait(q) , s3-wait(q) , s4-wait(p)b) s1-wait(p) , s2-wait(q) , s3-wait(p) , s4-wait(q)c) s1-wait(q) , s2-wait(p) , s3-wait(p) , s4-wait(q)d) none of...
0 votes
0 votes
0 answers
3