I was out of town last week- sorry for the missed post.

**The problem: **Deadlock Avoidance. This is problem SS22 in the appendix.

**The description: **(The definition in G&J is a little vague, so this comes more from the paper by Araki, Sugiyama, Kasami, and Okui). Given a set {P_{1}..P_{U}} of processes (represented as directed acyclic graphs with a fixed “start node”), and set {t_{1}..t_{T}} of resource types, where resource type t_{i} has a_{i} equivalent units available. Each process state may allocate or deallocate a resource type, with the stipulations that:

- Each process can only deallocate a resource it has allocated
- Each process must deallocate all allocated resources before completing (along any path through its DAG)

Given a state in this system (where each process is somewhere along its process flow), is the state of the system “safe”? That is, for each control flow, can we find a sequence of allocations and deallocations that allows each process to finish?

**Example: **I had a hard time with this definition until I realized we were asking about a specific state of the system. So here is the classic deadlock situation described in this terminology. Suppose we have 2 processes, P1 and P2. Each process’ start node is its name, the symbol a(X) means to allocate resource X and the symbol d(X) means to deallocate resource X.

The process flows look like:

If we set the starting state to after the second node of each graph (so P0 has R1, and P1 has R2), then we have a deadlock. But if we set the starting state to after the *first* node for each graph (so, before any resources are allocated) then we would call that “safe” because we can do all of P0, followed by all of P1, and have both processes finish.

**Reduction: **The paper by Araki, Sugiyama, Kasami, and Okui have several reductions for several variants of the problem. This is the first one (Theorem 2 in my paper) and uses 3SAT. We’re given a formula with n variables and m clauses, and build a system that has 3m+2n+1 processes and 7m+3n+1 resource types (each with 1 unit of the resource each). The resources are:

- B
_{i}, X_{i}and ~X_{i}for each variable - C
_{j}for each clause - C
_{jk}and D_{jk }for each literal position in each clause (k goes from 1 to 3). - A single resource A, which will control the flow through processes.

The processes are:

- P
_{xi}and P_{~xi}for each variable - P
_{jk}for each literal position in each clause - P
_{0}, which manages everything.

Here is the flow diagram for P_{xi}. “a” means allocate a resource, and “d” means deallocate a resource:

Here is the flow diagram for P_{~xi}. Notice that because they share B_{i} and A, only one of these processes can complete at a time:

The three P_{jk} processes for a clause are all similar. The resource “Yj1” refers to the resource that is the first literal in clause j (so it’s really an X resource):

(You can click the images to make them larger)

It’s worth noticing that resource C_{j} is in common among all 3 processes, and that each process allocates two D resources in a circular fashion.

The main P_{0} process is:

The starting state is the second node of each process (so after each process acquires its first resource).

If the original formula was satisfiable, then we have a way of setting each variable that satisfies each clause. Each variable has two processes: P_{xi} (corresponding to setting x_{i} to true) and P_{~xi} (corresponding to setting x_{i} to false). The process corresponding to the way we set each x_{i} to satisfy the formula is the one we want to let proceed. It will grab B_{i} and eventually wait on A (which is held by P_{0}). This will release the x_{i} (if the variable is set to true) or ~x_{i} (if the variable is set to false) resource. This means that the P_{jk} process that corresponds to that literal that can run to completion (this is the literal that makes clause C_{j} true). Once it’s done, we can run the other two P_{jk} processes to right before they each try to acquire C_{j}.

At this moment, none of the C_{j}‘s or C_{jk} resources are allocated, so process P_{0} can finish. This releases A, so process P_{x}_{i} (or P_{~xi}) can finish. This releases B_{i}, so the other of P_{xi} and P_{~xi} can finish. Then, finally, the other two P_{jk} in each clause can finish, in order. Since we found an order to terminate all processes, our starting state was safe.

If the original formula was unsatisfiable, for each B_{i}, we need to decide whether to allocate it to P_{xi} or P_{~xi}. The one we allocate to can release it’s X_{i} (or ~X_{i}) resource. That process is waiting to get A (currently held by P_{0}) and the other process for that variable is waiting to get B_{i} (currently held by the other X_{i} (or ~X_{i} ) process). P_{0} can’t release A until all C_{j} and C_{jk} resources are free, which only happens if some P_{jk} process completes. But these processes can’t complete until they get a resource corresponding to a literal in a clause (currently held by a X_{i}/~X_{i} process). Since we know the formula is unsatisfiable, no matter how we decide to allocate the B_{i}, there will always be at least one clause where all of the literals in that clause were *not* chosen to advance. The three processes for this clause cannot complete, meaning P_{0} cannot advance. Since we always get to a state where no processes can finish, we have a deadlock.

**Difficulty: **8. Tracing through the different processes is very cool, but very complicated. I wish I could teach a course one of these years in “cool hard reductions”. This is way to hard to fit into the last couple of weeks of an Algorithms class, but I think it is something students could sink their teeth into and learn a lot from.

One of the example to be taught could be my recent reduction for Exact Weight Bipartite Matching Problem. I have sent you the pdf file.

If you are interested, we would collaborate on some open problems this summer.

TDN

My reduction is too short in comparison to known ones. It comes from reading this weblog.

Thank you so much.

TDN