Exclusive Access 2

Having studied mutual exclusion protocols in last year's competition, you are now facing a more challenging problem. You have a large enterprise system in which several concurrent processes operate. The system contains multiple resources—databases, message queues, and so on. Each concurrent process works with two resources at a time. For example, one process may move a job from a particular database to the message queue, another process may take a job from the message queue, perform the job, and place the result in another message queue, and so on.

All resources are protected from concurrent access by mutual exclusion protocols, also known as locks. For instance, to access a particular database, a process acquires the lock for this database, performs its work, and then releases the lock. No two processes can hold the same lock at the same time (this is the mutual exclusion property). Thus, a process that tries to acquire a lock waits if that lock is held by another process.

The main loop of a process working with resources P and Q is as follows:

loop forever
    DoSomeNonCriticalWork()
    P.lock()
    Q.lock()
    WorkWithResourcesPandQ()
    Q.unlock()
    P.unlock()
end loop

The order in which the locks for resources P and Q are acquired is important. Suppose process c has acquired the lock P using P.lock() and is waiting for lock Q in Q.lock(). This means that lock Q is held by another process d. If process d is working (not waiting), we say there is a wait chain of length $1$. If d has acquired lock Q and is now waiting for another lock R, which is held by a working process e, we say there is a wait chain of length $2$, and so on. If any process in this wait chain is waiting for lock P, which is already held by process c, we say the wait chain is of infinite length and the system deadlocks.

For this problem, we are only interested in alternating wait chains where processes hold their first locks and wait for their second locks. Formally:

An alternating wait chain of length $n$ (n \ge 0) is an alternating sequence of resources R_i (0 \le i \le n+1) and different processes c_i (0 \le i \le n): R_0\ c_0\ R_1\ c_1\ \dots R_n\ c_n\ R_{n+1}, where process c_i acquires locks for resources R_i and R_{i+1} in this order. An alternating wait chain is a deadlock when R_0 = R_{n+1}.

You are given the set of resources each process works with. Your task is to determine the order in which each process should acquire the locks for its resources so that the system never deadlocks and the maximum possible length of any alternating wait chain is minimized.