0
$\begingroup$

This is my new post linked with my previous post.

Is bounded waiting satisfied in the 2 Process Solution?


The answer in that post was very useful and cleared many concepts, but I just want to apply that answer for this example, that how BW works here .

Especially, I want to know this definition works for this example.

Define $k$-bounded waiting for a given mutual exclusion algorithm to mean that if $D_A^j \to D_B^l$ then $CS_A^{j} \to CS_B^{l+k}$.


Here, the Question comes

What can be said bout the Bounded Waiting of this 2 process solution"

<------- P1 ------->

While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}

<-------- P2 -------->

While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}
$\endgroup$
  • $\begingroup$ Can you articulate a more specific question than "What can be said about..."? What specifically are you unsure/confused about? Have you tried applying the definition to that example, and what did you come up with and where specifically did you get stuck/confused? $\endgroup$ – D.W. Dec 14 '16 at 9:53
3
$\begingroup$

In the following, I treat the first two statements acquire(lock1) acquire(lock2) as "trying", the middle two statements withdraw(from, amount) deposit(to, amount) as the "critical section", and the last two statements release(lock2) release(lock1) as "exiting".

This algorithm does not satisfy the bounded waiting property. Consider the following execution: $P_1$ and $P_2$ simultaneously execute acquire(lock1) and $P_1$ wins. $P_1$ acquires lock2 successfully, enters the critical section, and then exit by releasing locks. Now, $P_1$ and $P_2$ contend on acquire(lock1) again and $P_1$ wins again .... In this way, $P_2$ is actually starved.

$\endgroup$
  • $\begingroup$ why P1 is given more priority, there is nothing mentioned about priority right? $\endgroup$ – Pavan Kumar Munnam Dec 15 '16 at 4:53
  • $\begingroup$ @PavanKumarMunnam I am constructing an execution which violates the bounded waiting property. I am free to schedule processes as I will. $\endgroup$ – hengxin Dec 15 '16 at 5:00
  • $\begingroup$ if i replace the lock by P and V operations where P makes the processes goes into the block and V operation which wakes up the process from sleep , does that force P1 process to wake up P2 and allow that execution, is Bounded waiting satisfied in that case? $\endgroup$ – Pavan Kumar Munnam Dec 15 '16 at 5:15
  • 1
    $\begingroup$ @PavanKumarMunnam You are talking about a single individual detailed implementation. However, you should focus on the worst-case scenario. In addition, being woken up does not mean $P_2$ immediately holds the lock. It has to compete with $P_1$ which is also trying to acquire the same lock. The worst case here is to let $P_1$ always win. $\endgroup$ – hengxin Dec 15 '16 at 5:28
  • 1
    $\begingroup$ @PavanKumarMunnam: Design of any solution to Critical-Section Problem should be done which is free from or irrespective of speed and number of processors and priority of processes. $\endgroup$ – sameerkn Dec 15 '16 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.