Having studied mutual exclusion protocols in the previous year's competition you are now facing a more challenging problem. You have a big enterprise system with a number concurrently running processes. The system has several resources - databases, message queues, etc. Each concurrent process works with two resources at a time. For example, one process might copy a job from a particular database into the message queue, the other process might take a job from the message queue, perform the job, and then put the result into some other message queue, etc.
All resources are protected from concurrent access by mutual exclusion protocols also known as locks. For example, to access a particular database process acquires the lock for this database, then performs its work, then releases the lock. No two processes can hold the same lock at the same time (that is the property of mutual exclusion). Thus, the process that tries to acquire a lock waits if that lock is taken by some other process.
The main loop of the process that works with resources P and Q looks like this:
loop forever
DoSomeNonCriticalWork()
P.lock()
Q.lock()
WorkWithResourcesPandQ()
Q.unlock()
P.unlock()
end loop
The order in which locks for resources P and Q are taken is important. Consider a case where process c had acquired lock P with P.lock() and is waiting for lock Q in Q.lock(). It means that lock Q is taken by some other process d. If the process d is working (not waiting), then we say that there is a wait chain of length 1. If d had acquired lock Q and is waiting for another lock R, which is acquired by a working process e, then we say that there is a wait chain of length 2, etc. If any process in this wait chain waits for lock P that is already taken by process c, then we say that the wait chain has infinite length and the system deadlocks.
For this problem, we are interested only in alternating wait chains where processes hold their first locks and wait for the second ones. Formally:
Alternating wait chain of length n (n >= 0) is an alternating sequence of resources Ri (0 <= i <= n + 1) and distinct processes ci (0 <= i <= n): R0 c0 R1 c1 ... Rn cn Rn+1, where process ci acquires locks for resources Ri and Ri+1 in this order. Alternating wait chain is a deadlock when R0 = Rn+1.
You are given a set of resources each process works with. Your task is to decide the order in which each process has to acquire its resource locks, so that the system never deadlocks and the maximum length of any possible alternating wait chain is minimized.