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.