Synchronization: A collection of Implications

Question

1. Every 2 process solution satisfy Bounded waiting. I think yes

2. Every 3 or more process solution satisfy Bounded waiting. I think no.

Determine Which of the following Implications Holds-

1. Deadlock -> ! Bounded Wait

2. Deadlock --> ! Progress

3. Starvation --> !Progress

4. ! Progress --> Starvation

5. ! Progress --> Deadlock.

6. Progress --> Bounded Wait

7. Bounded Wait --> Progress

8. ! Starvation --> ! Deadlock

9. ! Starvation --> Bounded Wait

10. BW --> ! Starvation.

Comments

FOR POINT 1
Boolean variable x = 1

P1()                            P2()
{                               {
    P(x);                           P(x);
    <CS>                            <CS>
    V(x);                            V(x);
}                               }

We see there is no bound on how many times either process will be bypassed before it gets it's chance.

1. Strict alteration for 2 process system can never violate bounded waiting requirement.

2. If X was declared as Binary semaphore then by default a queue will be associated with X then BW satisfied.

---

We see there is no bound on how many times either process will be bypassed before it gets it's chance.

Please explain this in more simple term.

---

Bounded waiting is defined per-process i.e. bounded waiting is satisfied if there exists some function f such that after a process expresses his desire to enter the critical section, he will be bypassed at most f(N) times, where N is the process number.

Suppose P1 enters critical section and then ececutes V(x) but before P2 can execute P(x) P1 again takes the resource X and this goes on indefinitely. So there is no bound on how many times P2 will be bypassed before it can enter critical section.