self-doubt operating-system semaphore

Question

given solution is wait(P) , wait(Q), wait(p) , wait(Q) for s1,s2,s3,s4 respectively

I know this implementation is deadlock free just want to ask if it will follow bounded waiting and progress and how both of them are different?

 

Comments

Yes it’s deadlock free, I think progress isn’t satisfied and bounded waiting is satisfied. What do you think @adad20?

---

@ankit3009

can u explain why do u think progress isn’t satisfied?

this was one of the question in some test series but i don’t think they will ask such in question in gate without implementation details cause it depends on how wait queue is implement if its going to wake up random process from queue after signal then it won’t have bounded waiting but if it wakes up process in FIFO manner then it will have bounded waiting.

 

---

@ankit3009 @Arbaz__Malik

I think according to the solution mentioned wait(P) , wait(Q), wait(P) , wait(Q) for s1,s2,s3,s4 respectively, deadlock is surely not there. Before getting into bounded waiting and progress let’s see the difference between them.

Progress is there if one process who is not interested to get into CS is not stopping other process to get into CS and in the above question, if one process is not getting into CS other process can simply go into CS by implementing wait(P) and wait(Q). So progress is there.

Bounded waiting is one process should not wait for the infinite amount of time to get into CS. There should be bound on how many number of time one process is getting into CS. I think bounded waiting is not satisfied here because if process A come again and again to get into CS no one is stopping it in doing so, so there is a chance that process B might have to wait for the long period of time.

Correct me if I am wrong.

---

@Arbaz__Malik Bhai, you are right that this is implementation-specific. If FIFO is used then both bounded waiting and progress are satisfied. And I believe that’s what the test series is assuming. 

Now why I think that progress isn’t satisfied because progress can be defined as if a process running execution isn’t dependent on another process’s execution. Like if P1 and P2 both are running concurrently for the available resources. Then if P2’s process of accessing the CS shouldn’t be decided by P1’s execution. 

Here, assume process A executes first and enters CS, then executes Signal(P) and Signal(Q). Here comes the implementation part about which @Arbaz__Malik is talking, here if we are assuming that FIFO queue is used then we know that process B is in the front of the queue, and if process A again wants to access the CS, still as FIFO is implemented it can access CS after process B accesses Q because of queue implementation. So, here bounded waiting and progress both will be satisfied. As, here we can’t say that process A is not interested to execute if it has entered the queue, and if it hasn’t entered the queue then process B can freely execute.

Now, what if we don’t use queue here? Instead, we opt for waking up a random process. Assume, P1 executes CS and P2 is stuck at wait(P). Further P1 executes signal(P) and signal(Q). Now, if P1 isn’t interested then P2 can execute further. So, P2’s execution is not dependent on P1’s wish to execute, so progress is satisfied. And if P1 keeps on executing without giving chance to P2 then bounded waiting won’t be satisfied. I got confused between both definitions. So, sorry for my above statement and credits to @adad20 for making me correct :)