GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
155 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?
asked in Operating System by Active (2.4k points)   | 155 views
What is the meaning of standard??
standard--- he wants to know general convention which is assumed.

1 Answer

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.

answered by Boss (6.8k points)  

Related questions



Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3120 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,969 questions
32,072 answers
74,565 comments
30,147 users