How do you logically formulate the problem of operating systems deadlocks?

Question

It is a programming assignment in Prolog to write a program that takes in input of processes, resources, etc and either print out the safe order of execution or simply return false if there is no safe order of execution.

I am very new to Prolog and I just simply can't get myself to think in the way it is demanding me to think (which is, formulating the problem logically and letting the compiler figure out how to do the operations) and I am stuck just thinking procedurally. How would you formulate such a problem logically, in terms of predicates and whatnot?

The sample input goes as follows: a list of processes, a list of pairs of resource and the number of available instances of that resource and facts allocated(x,y) with x being a process and y being a list of resources allocated to x and finally requested(x,y) such that x is a process and y is a list of resources requested by x.

For the life of me I can't think of it in terms of anything but C++. I am too stuck. I don't even need code, just clarity.

edit: here's a sample input. I seriously just need to see what I need to do. I am completely clueless.

processes([p1, p2, p3, p4, p5]).

available_resources([[r1, 2], [r2, 2], [r3, 2], [r4, 1], [r5, 2]]). 

allocated(p1, [r1, r2]).
allocated(p2, [r1, r3]).
allocated(p3, [r2]).
allocated(p4, [r3]).
allocated(p5, [r4]).

requested(p5, [r5]).

Answer 1

What you want to do is apply the "state search" approach.

• Start with an initial state S0.
• Apply a transformation to S0 according to allowed rules, giving S1. The rules must allowed only consistent states to be created. For example, the rules may not allow to generate new resources ex nihilo.
• Check whether the new state S1 fulfills the condition of a "final state" or "solution state" permitting you to declare victory.
• If not, apply a transformation to S1, according to allowed rules, giving S2.
• etc.

Applying transformations may get you to generate a state from which no progress is possible but which is not a "final state" either. You are stuck. In that case, dump a few of the latest transformations, moving back to an earlier state, and try other transformations.

Through this you get a tree of states through the state space as you explore the different possibilites to reach one of the final states (or the single final state, depending on the problem).

What we need is:

• A state description ;
• A set of allowed state transformations (sometimes called "operators") ;
• A criterium to decide whether we are blocked in a state ;
• A criterium to decide whether we have found a final state ;
• Maybe a heuristic to decide which state to try next. If the state space is small enough, we can try everything blindly, otherwise something like A* might be useful.
• The exploration algorithm itself. Starting with an initial state, it applies operators, generating new states, backtracks if blocked, and terminates if a final state has been reached.

State description

A state (at any time t) is described by the following relevant information:

• a number of processes
• a number of resources, several of the same kind
• information about which processes have allocated which resources
• information about which processes have requested which resources

As with anything else in informatics, we need a data structure for the above.

The default data structure in Prolog is the term, a tree of symbols. The extremely useful list is only another representation of a particular tree. One has to a representation so that it speaks to the human and can still be manipulated easily by Prolog code. So how about a term like this:

[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)]

This expresses the fact that process p1 owns two resources r1 and one resource r2 and wants r3 next.

The full state is then a list of list specifying information about each process, for example:

[[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)],
 [process(p2),owns(r3),wants(r1)],
 [process(p3),owns(r3)]]

Operator description

Prolog does not allow "mutable state", so an operator is a transformation from one state to another, rather than a patching of a state to represent some other state.

The fact that states are not modified in-place is of course very important because we (probably) want to retain the states already visited so as to be able to "back track" to an earlier state in case we are blocked.

I suppose the following operators may apply:

In state StateIn, process P requests resource R which it needs but can't obtain.

request(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn

In state StateIn, process P obtains resource R which is free.

obtain(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn

In state StateIn, process P frees resource R which is owns.

free(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn

The code would be written such that if StateIn were

[[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)],
 [process(p2),owns(r3),wants(r1)],
 [process(p3),owns(r3)]]

then free(StateIn, StateOut, p1, r2) would construct a StateOut

[[process(p1),owns(r1),owns(r1),wants(r3)],
 [process(p2),owns(r3),wants(r1)],
 [process(p3),owns(r3)]]

which becomes the new current state in the search loop. Etc. Etc.

A criterium to decide whether we are blocked in the current state

Often being "blocked" means that no operators are applicable to the state because for none of the operators, valid preconditions hold.

In this case the criterium seems to be "the state implies a deadlock".

So a predicate check_deadlock(StateIn) needs to be written. It has to test the state description for any deadlock conditions (performing its own little search, in fact).

A criterium to decide whether we have found a final state

This is underspecified. What is a final state for this problem?

In any case, there must be a check_final(StateIn) predicate which returns true if StateIn is, indeed, a final state.

Note that the finality criterium may also be about the whole path from the start state to the current state. In that case: check_path([StartState,NextState,...,CurrentState]).

The exploration algorithm

This can be relatively short in Prolog as you get depth-first search & backtracking for free if you don't use specific heuristics and keep things primitive.

You are all set!