Operating System :Deadlock :

Question

We know that whenever a process needs i/o time it goes to block/wait state. At that time cpu is idle and it can run other processes. What happens during the deadlock ? In which state do the processes go, so that the cpu freezes ? If all the processes during deadlock, go into block state then why does the cpu freezes ? The cpu should stay idle, but it should not freeze . Can anyone clarify ?

Comments

Please correct me if i am wrong.

For a process to run on CPU it must have the resources requested,until then it will be waiting in ready queue.Now,a deadlock between 2 processes will occur if they are holding resources that both of them require and unwilling to release until they are executed.Now,if all the processes are in a deadlock then no other process will running on CPU that's why the CPU remains idle.Here the point to be noted is that the processes will remain in ready queue rather than in the block queue.If not all the processes are in deadlock then the processes whose resources are allocated will run on CPU.

Answer 1

For starters, all the processes going in a deadlock simultaneously, is a very very rare occurrence, at least on the CPUs our generation is used to. In fact its so rare that major names in the market, like Windows and Ubuntu, do not have any deadlock resolving mechanism at all. The ultimate solution is that the user gets frustrated and restarts the system.

But still, if a condition occurs wherein all the processes are in deadlock, then CPU goes in an idle state (as there is no process to execute) and its same as what we call as freezing or "hang". After some time, if one of the processes is killed the deadlock may be resolved and the system starts running again. But if one the process stuck in deadlock is of kernel type, the only solution is a total restart.$^{[1]}$

Also, there may be the case wherein not all, but only a few processes are in a deadlock. In that case, the CPU may be (in fact is) used by other processes. Its one of those moments when one of our application (say Chrome becomes unresponsive) while rest of the applications are running well and good.

Comments

Thank you for your answer...so I guess I was right about cpu being in a idle state.... But the logic that you gave...that cpu freezes since there are no processes to execute... But that doesn't guarantee the fact that there are no processes in the ready queue waiting to be scheduled... Since all processes are in deadlock and cpu is idle, the short term scheduler can schedule any other process(that was waiting in the ready queue while others are being executed... And that's when deadlock occurred ) for execution. That doesn't explain the answer that you gave. Tell me if it made sense to you.

---

Yes, short term scheduler can put up processes from Ready Q to CPU, provided that there are processes waiting in Ready Q. In fact, that is what happens in most of the cases. 

For example, if we have got 64 processes (in total including ready Q and the one in already using CPU), and if somehow 3 processes go into deadlock(while waiting outside after acquiring a part of their resources), it will be they who will be waiting outside and not getting the CPU. Why should rest 60 be devoid of opportunity to use CPU. So, CPU won't just sit around. It will actually execute other guys in Ready Q, while there is deadlock already happening simultaneously.

It's just those 3 processes going into deadlock, not the whole system. The whole system in deadlock means either a very crucial process(say kernel) is stuck in deadlock or all (literally all) processes are in a deadlock.

In theory, we just study just take 2 or 3 processes and the CPU is rendered unusable as supposedly there are no other processes we have considered, but the reality is quite different. There are surely many other processes which will be scheduled while these 2 or 3 guys are still in a deadlock. Let them be and give the CPU to others. Simple!

---

Thank you so much for your detailed answer. Now i could relate the real scenario with the theory. One more thing, you said if one process is killed whilst all processes are in deadlock... How is that one process going to be killed?

---

Different manufacturers go about different ways to resolve the deadlocked situation if they have got such an implementation.

One of the simplest solutions is that if CPU sees that a couple of processes are not at all coming for execution, even though these have got some resources, it assumes that they may be deadlocked. So, it randomly selects one of the processes, kills it and hopes that it will resolve the issue, as this guy will release all the resources he was holding. If not, another process is victimized. This killing spree goes on till the deadlock is resolved.

But still, as I said, investments for such algorithms is not feasible enough, given the rarity of such deadlocks. So, they tend to avoid any such implementation at all.

---

I would like to add another question to this if you don't mind. What happens during spinlock? What is the difference between spinlock and deadlock?
The spinlock situation that I have heard of is that, if a process with lower priority is being executed, and a higher priority process comes in, then the ST scheduler tries to schedule the higher priority process, due to priority scheduling. But the turn variable does not allow the higher priority process to enter critical section since the lower priority process isn't finished with the critical section and turn variable isn't set to '1'. Hence both process are stuck and both of them are sent back to ready state and no one of them can execute the critical section.
Is this the correct scenario?

---

NO, you are going wrong somewhere or misinterpreting something. May I have the source from where you are quoting the above scenario. Lemme have a look first.

---

I was going through rabindrababu ******'r videos... He described the scenario... What I am confused is whether the processes end up in ready queue or not.. If you could describe please

---

Also I saw somewhat similar answer in this post, https://gateoverflow.in/46833/difference-between-deadloack-%26-spinlock
The answer posted by Varun Taneja on 25th february, 2018.