Design a class which provides a lock if no deadlocks

Problem

Design a class which provides a lock only if there are no possible deadlocks.

Solution

Deadlock will occur with a lock only if the locks can be held in a circular fashion; that is, if you define an ordering < on locks such that A < B only if lock A can be held with lock B also held, then<  is not a strict partial ordering. For example, if thread 1 tries to acquire lock A and then lock B, while thread 2 tries to acquire lock B and then lock A, then A < B and B < A, so < is not a strict partial ordering. Indeed, deadlock can occur if threads 1 and 2 each get locks A and B, respectively, then try to acquire the other lock.

So, a class can create a deadlock, by acquiring the control of the entire set of related locks that might be involved in such deadlocks. It can then, for example, require they be taken in some specific order (e.g. alphabetic ordering based on a name associated with each lock, arbitrary unique integers hardcoded in the source).

For our solution, we implement a wait / die deadlock prevention scheme.

Wait-die scheme: It is a non-preemptive technique for deadlock prevention. When transaction T_i requests a data item currently held by T_j, T_i is allowed to wait only if it has a timestamp smaller than that of T_j (That is T_i is older than T_j), otherwise T_i is rolled back (dies)
For example:
Suppose that transaction T₂₂, T₂₃, T₂₄ have time-stamps 5, 10 and 15 respectively. If T₂₂ requests a data item held by T₂₃ then T₂₂ will wait. If T₂₄ requests a data item held by T₂₃, then T₂₄ will be rolled back.
(definition taken from code bank.)

Java code

class MyThread extends Thread {
    long time;
    ArrayList<Resource> res = new ArrayList<Resource>();
 
    public ArrayList<Resource> getRes() {
        return res;
    }
 
    @Override
    public void run() {
        // Run infinitely
        time = System.currentTimeMillis();
        int count = 0;
        while (true) {
            if (count < 4) {
                if (Question.canAcquireResource(this, Question.r[count])) {
                    <span class="skimlinks-unlinked">res.add(Question.r</span>[count]);
                    count++;
                    <span class="skimlinks-unlinked">System.out.println("Resource</span>: ["
                            + Question.r[count - 1].getId()
                            + "] acquired by thread: [" + this.getName()
                            + "]");
                    try {
                        sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            } else {
                <span class="skimlinks-unlinked">this.stop</span>();
            }
        }
    }
 
    public long getTime() {
        return time;
    }
 
    public void setRes(ArrayList<Resource> res) {
        <span class="skimlinks-unlinked">this.res</span> = res;
    }
 
    MyThread(String name) {
        super(name);
    }
}

Thanks
References

• http://tianrunhe.wordpress.com/2012/05/01/design-a-class-which-provides-a-lock-if-no-deadlocks/