# Deadlock not possible?

System is in safe state if there exists a safe sequence of all processes.

Sequence $$[P_1, P_2 …P_n]$$ is safe, if for each $$P_i$$ the resources that can still request can be satisfied by $$P_i$$ currently available resources + resources held by $$P_j$$ with $$j \lt i$$

The above is from a presentation distributed by my OS II teacher. Assuming it is true, then doesn't this mean that the system is always in a safe state?

I conjecture that $$\forall$$ set of processes $$X = [P_1 ... P_n]$$ requesting for a set of resources $$[R_1 ... R_n]$$ $$\exists$$ a safe sequence $$S = \{P_i ... P_k\}, S: S$$ is a permutation of $$X$$.

Reasoning behind my conjecture. Suppose I had $$n$$ processes and $$1$$ resource(each process requesting it.) I could order these processes in order of priority, or ascending order of size and run them. If resources were increased to $$k$$, there will still be a sequence such that every process completes in finite time. The challenge merely finding it.

Am I wrong?

## 1 Answer

Lets say for the sake of argument we have 6 units of memory available and three processes in a current state where each holds 2 resources. Each process needs 3 resources to finish and release its memory units to use by the others. This state is not safe, in fact this state is deadlock. Each needs one extra memory unit to finish, but this would require another process to release its units. No ordering of these 3 processes will be safe.

You are not looking at the state of the program, but the entirety of the program, in which case, with no new resource creation and single threading, every state is safe.

Edit for clarity: From the definition of a state: "In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given instant in time, to which the circuit or program has access".

The import point is "given instant". The state could be at the initial state as your argument would require, or it is at some arbitrary point in execution