Zhikai Wang Homepage

Heteroclinic.net logo

www.heteroclinic.net

	Advanced Concurrency Topic: Runtime Deadlock Detection XXV A Bad Prototype Here, we present a bad prototye. We also give some reasons to present it even it is bad. How to: java -cp treetorplus3.jar;jdfrbadprototype01.jar javax.util.concurrent.profilable.test.TwoLayersDeadlockImprovisedSolution .\ You would need these two jars: and treetorplus3.jar and jdfrbadprototype01.jar. You can study the source code inside jdfrbadprototype01.jar. You can also check out the entry point TwoLayersDeadlockImprovisedSolution.java. package javax.util.concurrent.profilable.test; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.ProfilableRunnable; import javax.util.concurrent.profilable.locks.ProfilableReentrantLock; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class TwoLayersDeadlockImprovisedSolutionTryer1 extends LoopRun { public TwoLayersDeadlockImprovisedSolutionTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted) { //LockerRoom.samplelocks[0].lock(); if (LockerRoom.samplelocks[0].tryLock() ) { System.out.println("---- Tryer1: lock0 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[0].getProfiableId(), LockerRoom.samplelocks[0]); } else { //LockerRoom.samplelocks[0].g long blockerthreadid = LockerRoom.samplelocks[0].getOwnerId(); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer1: lock0 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer1: lock0 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); System.out.println("---- Tryer1: lock0 yielded."); continue; } else { System.out.println("---- Tryer1: lock0 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer1: lock0 entering blocked tree. The peer is not blocked."); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(2000); //LockerRoom.samplelocks[1].lock(); if (LockerRoom.samplelocks[1].tryLock() ) { System.out.println("---- Tryer1: lock1 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[1].getProfiableId(), LockerRoom.samplelocks[1]); } else { //LockerRoom.samplelocks[1].g long blockerthreadid = LockerRoom.samplelocks[1].getOwnerId(); System.out.println("---- Tryer1: lock1 Peer thread blockerthreadid "+ blockerthreadid); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); System.out.println("---- Tryer1: lock1 Peer thread blockerthread pr "+ pr.getProfiableId()); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer1: lock1 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer1: lock1 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); //System.out.println("Tryer 1 yielded."); System.out.println("---- Tryer1: lock1 yielded."); } else { System.out.println("---- Tryer1: lock1 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer1: lock1 entering blocked stutus. The peer is not blocked."); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(500); // LockerRoom.samplelocks[0].unlock(); // LockerRoom.samplelocks[1].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); boolean shouldyield = false; if (this.locksheld.size() == 2) shouldyield = true; while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); if (shouldyield) { //Thread.currentThread(); Thread.yield(); } } } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } finally { // LockerRoom.samplelocks[0].unlock(); // LockerRoom.samplelocks[1].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); } } } class TwoLayersDeadlockImprovisedSolutionTryer2 extends LoopRun { public TwoLayersDeadlockImprovisedSolutionTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted) { //LockerRoom.samplelocks[1].lock(); if (LockerRoom.samplelocks[1].tryLock() ) { System.out.println("---- Tryer2: lock1 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[1].getProfiableId(), LockerRoom.samplelocks[1]); } else { //LockerRoom.samplelocks[1].g long blockerthreadid = LockerRoom.samplelocks[1].getOwnerId(); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer2: lock1 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer2: lock1 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); System.out.println("---- Tryer2: lock1 yielded."); continue; } else { System.out.println("---- Tryer2: lock1 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer2: lock1 entering blocked status. The peer is not blocked"); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(3000); //LockerRoom.samplelocks[0].lock(); if (LockerRoom.samplelocks[0].tryLock() ) { System.out.println("---- Tryer2: lock0 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[0].getProfiableId(), LockerRoom.samplelocks[0]); } else { //LockerRoom.samplelocks[0].g long blockerthreadid = LockerRoom.samplelocks[0].getOwnerId(); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer2: lock0 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer2: lock0 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); System.out.println("---- Tryer2: lock0 yielded."); } else { System.out.println("---- Tryer2: lock0 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer2: lock0 entering blocked status. The peer is not blocked"); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(500); // LockerRoom.samplelocks[1].unlock(); // LockerRoom.samplelocks[0].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); boolean shouldyield = false; if (this.locksheld.size() == 2) shouldyield = true; while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); if (shouldyield) { //Thread.currentThread(); Thread.yield(); } } } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } finally { // LockerRoom.samplelocks[1].unlock(); // LockerRoom.samplelocks[0].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); } } } public class TwoLayersDeadlockImprovisedSolution { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { // TODO Auto-generated method stub Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "LIVE_LOCK_DEMO"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = false; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 51.375, 39.0); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); LoopRun lpr1 = new TwoLayersDeadlockImprovisedSolutionTryer1(startSignal); LoopRun lpr2 = new TwoLayersDeadlockImprovisedSolutionTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(20000); lpr1.setHalted(true); lpr2.setHalted(true); //TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(3000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } Why it is bad? Simply, it does not full-fill the purpose of the desgin or the requirement(s). In "Advanced Concurrency Topic: Runtime Deadlock Detection XIX Visualization of an Imaginary Concurrency Event" and "Advanced Concurrency Topic: Runtime Deadlock Detection XX Visualization Results of XIX", I drew a series of diagrams. We tried to conjecture a scheduler that creates a live-lock. Two threads keep yielding each other, but neither of them can acquire all the resources it needs. Neither of them can finish its job. To build this prototype, we made an assumption. It was also made from the beginning I dived into the dead-lock detection topic. The assumption is that we would be able to read one thread's status from another thread. Thus, we can detect deadlock. Live-lock is construct-able if a thread can know what its peer thread trying to get. If it just gives up one but not all the peer needs, live-lock could happen. From this prototype, we know this assumption is wrong. If we execute the command line given, it will create either a dead-lock or the starvation of one of the threads. A thread's status is so volatile. A running thread will be blocked, go to sleeping, or perished. A blocked thread can be unblocked just next several CPU ticks. One thing is certain if a thread had finished. We may say two threads are like two particles, can this be called 'entangling', to observe accurately will affect the behavior the object being observed. Or to say, we can describe space/status or time accurately either of them but not both of them at the same time. I am not in physics area, so I stop short here and come back to our topic. So if we can not read another thread's status from one thread, which is a fundamental mis-understanding, are we completely wrong so we can do nothing( we may also argue that we can lock status, a thread status has read write lock etc-- nightmare of spaghetti)? In our previous discussion, we show a healthy system is a tree-like structure. When a dead-lock is formed, it becomes a cyclic graph. But once the dead-lock is formed, no threads can change their status, suppose we use a no-time-out lock(). What we did in the middle of this topic, help us properly construct the graph. When dead-lock happens, we can detect it. The profiling or detecting mission is accomplished.
	Advanced Concurrency Topic: Runtime Deadlock Detection XXVI An Artificial Livelock Although our attempt at XXV failed, we can still make a scheduler that follows the digram we drew. You would need these two jars: and treetorplus3.jar and jdfr1.0.jar. How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130115_ArtificialLivelock .\ You can check out the entry point: package javax.util.concurrent.profilable.test; import java.util.ArrayList; //import java.util.Iterator; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; //import javax.util.concurrent.profilable.ProfilableRunnable; //import javax.util.concurrent.profilable.locks.ProfilableReentrantLock; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class ArtificialLivelockTryer1 extends LoopRun { protected String CV = ""; public ArtificialLivelockTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { System.out.println("Tryer1: start a new loop"); //[1] if ( LockerRoom.samplelocks[1].tryLock() ) { CV+="R1+"; } else { LockerRoom.samplelocks[1].lock(); CV+="R1+"; } TimeUnit.MILLISECONDS.sleep(200); //[1] //[2] if ( LockerRoom.samplelocks[2].tryLock() ) { CV+="R2+"; } else { LockerRoom.samplelocks[2].lock(); CV+="R2+"; } TimeUnit.MILLISECONDS.sleep(200); //[2] //[3] if ( LockerRoom.samplelocks[3].tryLock() ) { CV+="R3+"; } else { LockerRoom.samplelocks[3].lock(); CV+="R3+"; } //[3] //[4] //get blocked //[4] //[5] //Tryer2 tries R1 result it realsing R1 //[5] //[6] TimeUnit.MILLISECONDS.sleep(200); //[6] //[7] //Tryer2 will try R3 //[7] //[8] //Blocking Tryer2 TimeUnit.MILLISECONDS.sleep(200); //[8] //[9] // tryer1 tries R4 resulting tryer1 release R3 if ( LockerRoom.samplelocks[4].tryLock() ) { CV+="R4+"; } else { //LockerRoom.samplelocks[3].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3-"; } //[9] //[10] //nothing happens this phase // tryer1 has R3,R4 // tryer2 has R1,R2 TimeUnit.MILLISECONDS.sleep(200); //[10] //[11] // drop all locks, end this thread //LockerRoom.samplelocks[1].unlock(); // CV+="R1-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) CV+="R1-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) CV+="R4-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[2])) CV+="R2-"; //[11] // break; //halted =true; // tell parent class proper end CV+="\n"; } } catch (InterruptedException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } finally { if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) CV+="R1e"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3e"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) CV+="R4e"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[2])) CV+="R2e"; } System.out.println("Tryer1 CV:\n"+CV); } } class ArtificialLivelockTryer2 extends LoopRun { protected String CV = ""; public ArtificialLivelockTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted) { //[1] if ( LockerRoom.samplelocks[3].tryLock() ) { CV+="R3+"; } else { LockerRoom.samplelocks[3].lock(); CV+="R3+"; } TimeUnit.MILLISECONDS.sleep(200); //[1] //[2] if ( LockerRoom.samplelocks[4].tryLock() ) { CV+="R4+"; } else { LockerRoom.samplelocks[4].lock(); CV+="R4+"; } TimeUnit.MILLISECONDS.sleep(200); //[2] //[3] //block tryer1, tryer is trying R3 TimeUnit.MILLISECONDS.sleep(200); //[3] //[4] //no time slice, but there is a graph, graph in [3] shows try edge, graph in [4] shows a tree //[4] //[5] if ( LockerRoom.samplelocks[1].tryLock() ) { //this will be false CV+="R1+"; } else { if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) //LockerRoom.samplelocks[3].unlock(); CV+="R3-"; } TimeUnit.MILLISECONDS.sleep(200); //[5] //[6] // let tryer1 get R3 TimeUnit.MILLISECONDS.sleep(200); //[6] //[7] if ( LockerRoom.samplelocks[3].tryLock() ) { //this will be false CV+="R3+"; } else { LockerRoom.samplelocks[3].lock(); CV+="R3+"; } // //[7] //[8] // get blocked //[8] //[9] // tryer1 tries R4 resulting tryer1 release R3 //TimeUnit.MILLISECONDS.sleep(200); //[9] //[10] //nothing happens this phase // tryer1 has R3,R4 // tryer2 has R1,R2 TimeUnit.MILLISECONDS.sleep(200); //[10] //[11] // drop all locks, end this thread //LockerRoom.samplelocks[1].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) CV+="R1-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) //LockerRoom.samplelocks[3].unlock(); CV+="R3-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) //LockerRoom.samplelocks[4].unlock(); CV+="R4-"; //[11] // break; //halted =true; // tell parent class proper end CV+="\n"; //System.out.println("Tryer2 CV:\n"+CV); } } catch (InterruptedException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } finally { if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) //LockerRoom.samplelocks[1].unlock(); CV+="R1e"; //LockerRoom.samplelocks[3].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3e"; //LockerRoom.samplelocks[4].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) CV+="R4e"; } System.out.println("Tryer2 CV:\n"+CV); } } public class Test20130115_ArtificialLivelock { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "LIVE_LOCK_DEMO"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,51.375,35.75); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(2000); lpr1.setHalted(true); lpr2.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(10000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } So, you would see the concern is no longer to create a live-lock. At the end of each thread, we did something. I hope this will provide some hint about how to deal with concurrent program that looks bizzare. In general, we should not fear live-lock. As long as the threads are alive, we will have a chance to change the resource access pattern. If a system has no hope, that is the real problem.
	Advanced Concurrency Topic: Runtime Deadlock Detection XXVII More Tested Examples Multi-tier How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_MultiTier .\ Entry point: package javax.util.concurrent.profilable.test; import java.util.ArrayList; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class MulitiTierTryer1 extends LoopRun { //protected String CV = ""; public MulitiTierTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[1].lock(); LockerRoom.samplelocks[2].lock(); TimeUnit.MILLISECONDS.sleep(2000); halted = true; } } catch (InterruptedException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[1]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } } } class MulitiTierTryer2 extends LoopRun { //protected String CV = ""; public MulitiTierTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[3].lock(); LockerRoom.samplelocks[4].lock(); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[2].lock(); halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[3]); LoopRun.properlyUnlock(LockerRoom.samplelocks[4]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } } } class MulitiTierTryer3 extends LoopRun { //protected String CV = ""; public MulitiTierTryer3(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[5].lock(); LockerRoom.samplelocks[6].lock(); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[3].lock(); halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[5]); LoopRun.properlyUnlock(LockerRoom.samplelocks[6]); LoopRun.properlyUnlock(LockerRoom.samplelocks[3]); } } } class MulitiTierTryer4 extends LoopRun { //protected String CV = ""; public MulitiTierTryer4(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[0].lock(); LockerRoom.samplelocks[9].lock(); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[5].lock(); halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[0]); LoopRun.properlyUnlock(LockerRoom.samplelocks[9]); LoopRun.properlyUnlock(LockerRoom.samplelocks[5]); } } } public class Test20130120_MultiTier { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "PROF_MUTLTI_TIER"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,91.375,71.5); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); //LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); //LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); LoopRun lpr1 = new MulitiTierTryer1(startSignal); LoopRun lpr2 = new MulitiTierTryer2(startSignal); LoopRun lpr3 = new MulitiTierTryer3(startSignal); LoopRun lpr4 = new MulitiTierTryer4(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); fl.add(exec.submit(lpr3)); fl.add(exec.submit(lpr4)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(5000); lpr1.setHalted(true); lpr2.setHalted(true); lpr3.setHalted(true); lpr4.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(5000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } Fast How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_Fast .\ Entry point: package javax.util.concurrent.profilable.test; // Search YOU_CAN_ADJUST_THIS_VALUE // On my latop (Q9000 processor): // 100 milli-second, two thread / three locks, proper lock/unlock order //Tryer2 count: 1272 //Thread stopped by itself! //Tryer1 count: 324 //Thread stopped by itself! //50 milli-second, two thread / three locks, proper lock/unlock order //MSG: createATNodeforProfilable:2 2 11 //Tryer2 count: 296 //Thread stopped by itself! //Tryer1 count: 214 //Thread stopped by itself! // it produces too much pitures, so we don't show them. import java.util.ArrayList; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class FastTryer1 extends LoopRun { //protected String CV = ""; public FastTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { long count = 0; try { while (!halted ) { LockerRoom.samplelocks[1].lock(); LockerRoom.samplelocks[2].lock(); LockerRoom.samplelocks[3].lock(); //TimeUnit.MILLISECONDS.sleep(2000); //halted = true; LockerRoom.samplelocks[1].unlock(); LockerRoom.samplelocks[2].unlock(); LockerRoom.samplelocks[3].unlock(); ++count; } } // catch (InterruptedException e) { // e.printStackTrace(); // } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[1]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } System.out.println("Tryer1 count: "+ count); } } class FastTryer2 extends LoopRun { //protected String CV = ""; public FastTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { long count = 0; try { while (!halted ) { LockerRoom.samplelocks[1].lock(); LockerRoom.samplelocks[2].lock(); LockerRoom.samplelocks[3].lock(); //TimeUnit.MILLISECONDS.sleep(2000); //halted = true; LockerRoom.samplelocks[1].unlock(); LockerRoom.samplelocks[2].unlock(); LockerRoom.samplelocks[3].unlock(); ++count; } } // catch (InterruptedException e) { // e.printStackTrace(); // } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[1]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } System.out.println("Tryer2 count: "+ count); } } public class Test20130120_Fast { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "PROF_FAST"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,91.375,71.5); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); //LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); //LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); LoopRun lpr1 = new FastTryer1(startSignal); LoopRun lpr2 = new FastTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); //TODO YOU_CAN_ADJUST_THIS_VALUE long thisvalue = 50; TimeUnit.MILLISECONDS.sleep(thisvalue); lpr1.setHalted(true); lpr2.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(20000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } Random How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130121_Random .\ Entry point: package javax.util.concurrent.profilable.test; import java.util.ArrayList; import java.util.Calendar; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.IndexPermutation; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class RandomTryer1 extends LoopRun { //protected String CV = ""; public RandomTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { int [] indices = IndexPermutation.getARandomPermutation(10,5); try { while (!halted ) { for (int i:indices) { LockerRoom.samplelocks[i-1].lock(); } TimeUnit.MILLISECONDS.sleep(200); for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } } } } class RandomTryer2 extends LoopRun { //protected String CV = ""; public RandomTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { int [] indices = IndexPermutation.getARandomPermutation(10,5); try { while (!halted ) { for (int i:indices) { LockerRoom.samplelocks[i-1].lock(); } TimeUnit.MILLISECONDS.sleep(200); for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } } } } public class Test20130121_Random { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Calendar.getInstance().getTimeInMillis(); Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "PROF_RANDOM"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,51.375,58.5); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); //LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); //LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); LoopRun lpr1 = new RandomTryer1(startSignal); LoopRun lpr2 = new RandomTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(500); lpr1.setHalted(true); lpr2.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(5000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } }
	Advanced Concurrency Topic: Runtime Deadlock Detection XXVIII Period So far, months have been spent upon this topic. The resources are limited, I have to put a period. We may continue on with the same topic or similiar topic. Today, we release jdfr1.0.jar. - it fully supports Java ReentrantLock - it has several proto-types, quick-starts or just say examples -- in the Blog section It will be a very useful tool to profile concurrent programming. We also have treetor treetorplus3.jar which can render about several thousands nodes of a-cyclic graph or a forest. If I got enough support, we may switch to OpenGL rendering engine and using more advanced IPC. We corrected some mis-understandings. They are critical but finally not fatal to this project. I am still not sure about next step. I hope there will be more people download and study what I did. It will be a great pleasure that you can achieve something with these tools. Science and technology does not rely on luck. If you find any bug or errors, please feel free to point them out. This project is done by one person, so it is convenient to control. In real life projects, we have to resolve human conflicts, legacy pacakges etc. Some time you do not even have the source code not mention how to modify them. So we can not simply put a easy or difficult label for a project. The methods we tried or proposed, may be helpful while extending to profile database system, interprocess concurrent programming, the operating system, or for clustered computing units. Concurrent programming in some sense destroyed the von Neuman architecture, much more effort is needed for understanding or utilizing the nature of concurrency.

	Advanced Concurrency Topic: Runtime Deadlock Detection XXV A Bad Prototype Here, we present a bad prototye. We also give some reasons to present it even it is bad. How to: java -cp treetorplus3.jar;jdfrbadprototype01.jar javax.util.concurrent.profilable.test.TwoLayersDeadlockImprovisedSolution .\ You would need these two jars: and treetorplus3.jar and jdfrbadprototype01.jar. You can study the source code inside jdfrbadprototype01.jar. You can also check out the entry point TwoLayersDeadlockImprovisedSolution.java. package javax.util.concurrent.profilable.test; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.ProfilableRunnable; import javax.util.concurrent.profilable.locks.ProfilableReentrantLock; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class TwoLayersDeadlockImprovisedSolutionTryer1 extends LoopRun { public TwoLayersDeadlockImprovisedSolutionTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted) { //LockerRoom.samplelocks[0].lock(); if (LockerRoom.samplelocks[0].tryLock() ) { System.out.println("---- Tryer1: lock0 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[0].getProfiableId(), LockerRoom.samplelocks[0]); } else { //LockerRoom.samplelocks[0].g long blockerthreadid = LockerRoom.samplelocks[0].getOwnerId(); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer1: lock0 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer1: lock0 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); System.out.println("---- Tryer1: lock0 yielded."); continue; } else { System.out.println("---- Tryer1: lock0 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer1: lock0 entering blocked tree. The peer is not blocked."); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(2000); //LockerRoom.samplelocks[1].lock(); if (LockerRoom.samplelocks[1].tryLock() ) { System.out.println("---- Tryer1: lock1 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[1].getProfiableId(), LockerRoom.samplelocks[1]); } else { //LockerRoom.samplelocks[1].g long blockerthreadid = LockerRoom.samplelocks[1].getOwnerId(); System.out.println("---- Tryer1: lock1 Peer thread blockerthreadid "+ blockerthreadid); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); System.out.println("---- Tryer1: lock1 Peer thread blockerthread pr "+ pr.getProfiableId()); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer1: lock1 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer1: lock1 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); //System.out.println("Tryer 1 yielded."); System.out.println("---- Tryer1: lock1 yielded."); } else { System.out.println("---- Tryer1: lock1 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer1: lock1 entering blocked stutus. The peer is not blocked."); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(500); // LockerRoom.samplelocks[0].unlock(); // LockerRoom.samplelocks[1].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); boolean shouldyield = false; if (this.locksheld.size() == 2) shouldyield = true; while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); if (shouldyield) { //Thread.currentThread(); Thread.yield(); } } } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } finally { // LockerRoom.samplelocks[0].unlock(); // LockerRoom.samplelocks[1].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); } } } class TwoLayersDeadlockImprovisedSolutionTryer2 extends LoopRun { public TwoLayersDeadlockImprovisedSolutionTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted) { //LockerRoom.samplelocks[1].lock(); if (LockerRoom.samplelocks[1].tryLock() ) { System.out.println("---- Tryer2: lock1 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[1].getProfiableId(), LockerRoom.samplelocks[1]); } else { //LockerRoom.samplelocks[1].g long blockerthreadid = LockerRoom.samplelocks[1].getOwnerId(); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer2: lock1 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer2: lock1 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); System.out.println("---- Tryer2: lock1 yielded."); continue; } else { System.out.println("---- Tryer2: lock1 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer2: lock1 entering blocked status. The peer is not blocked"); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[1].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(3000); //LockerRoom.samplelocks[0].lock(); if (LockerRoom.samplelocks[0].tryLock() ) { System.out.println("---- Tryer2: lock0 tried and acquired."); this.locksheld.put(LockerRoom.samplelocks[0].getProfiableId(), LockerRoom.samplelocks[0]); } else { //LockerRoom.samplelocks[0].g long blockerthreadid = LockerRoom.samplelocks[0].getOwnerId(); ProfilableRunnable pr = ProfilableRunnable.dict_threadid_runnableobj.get(blockerthreadid); if ( null != pr.getBlocker() ) { System.out.println("---- Tryer2: lock0 Peer thread blocked."); // the lock we tried's owner is being blocked. if (this.isItHeldbyMe(pr.getBlockerProfilableid()) ) { System.out.println("---- Tryer2: lock0 I hold what Peer thread want."); // we have to handle deadlock here // OK, to avoid deadlock, I will give you just what you want... // But we will see other problems, which will be discussed later. ProfilableReentrantLock lk = this.locksheld.get(pr.getBlockerProfilableid()); this.locksheld.remove(pr.getBlockerProfilableid()); lk.unlock(); System.out.println("---- Tryer2: lock0 yielded."); } else { System.out.println("---- Tryer2: lock0 entering blocked tree. I don't have what it wants."); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } else { System.out.println("---- Tryer2: lock0 entering blocked status. The peer is not blocked"); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[0].lock();// try to lock a again, getting the lock or being blocked. } } TimeUnit.MILLISECONDS.sleep(500); // LockerRoom.samplelocks[1].unlock(); // LockerRoom.samplelocks[0].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); boolean shouldyield = false; if (this.locksheld.size() == 2) shouldyield = true; while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); if (shouldyield) { //Thread.currentThread(); Thread.yield(); } } } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } finally { // LockerRoom.samplelocks[1].unlock(); // LockerRoom.samplelocks[0].unlock(); Iterator<Long> it = this.locksheld.keySet().iterator(); while (it.hasNext()) { //long key = it.next(); this.locksheld.get(it.next()).unlock(); } this.locksheld.clear(); } } } public class TwoLayersDeadlockImprovisedSolution { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { // TODO Auto-generated method stub Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "LIVE_LOCK_DEMO"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = false; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 51.375, 39.0); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); LoopRun lpr1 = new TwoLayersDeadlockImprovisedSolutionTryer1(startSignal); LoopRun lpr2 = new TwoLayersDeadlockImprovisedSolutionTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(20000); lpr1.setHalted(true); lpr2.setHalted(true); //TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(3000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } Why it is bad? Simply, it does not full-fill the purpose of the desgin or the requirement(s). In "Advanced Concurrency Topic: Runtime Deadlock Detection XIX Visualization of an Imaginary Concurrency Event" and "Advanced Concurrency Topic: Runtime Deadlock Detection XX Visualization Results of XIX", I drew a series of diagrams. We tried to conjecture a scheduler that creates a live-lock. Two threads keep yielding each other, but neither of them can acquire all the resources it needs. Neither of them can finish its job. To build this prototype, we made an assumption. It was also made from the beginning I dived into the dead-lock detection topic. The assumption is that we would be able to read one thread's status from another thread. Thus, we can detect deadlock. Live-lock is construct-able if a thread can know what its peer thread trying to get. If it just gives up one but not all the peer needs, live-lock could happen. From this prototype, we know this assumption is wrong. If we execute the command line given, it will create either a dead-lock or the starvation of one of the threads. A thread's status is so volatile. A running thread will be blocked, go to sleeping, or perished. A blocked thread can be unblocked just next several CPU ticks. One thing is certain if a thread had finished. We may say two threads are like two particles, can this be called 'entangling', to observe accurately will affect the behavior the object being observed. Or to say, we can describe space/status or time accurately either of them but not both of them at the same time. I am not in physics area, so I stop short here and come back to our topic. So if we can not read another thread's status from one thread, which is a fundamental mis-understanding, are we completely wrong so we can do nothing( we may also argue that we can lock status, a thread status has read write lock etc-- nightmare of spaghetti)? In our previous discussion, we show a healthy system is a tree-like structure. When a dead-lock is formed, it becomes a cyclic graph. But once the dead-lock is formed, no threads can change their status, suppose we use a no-time-out lock(). What we did in the middle of this topic, help us properly construct the graph. When dead-lock happens, we can detect it. The profiling or detecting mission is accomplished.
	Advanced Concurrency Topic: Runtime Deadlock Detection XXVI An Artificial Livelock Although our attempt at XXV failed, we can still make a scheduler that follows the digram we drew. You would need these two jars: and treetorplus3.jar and jdfr1.0.jar. How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130115_ArtificialLivelock .\ You can check out the entry point: package javax.util.concurrent.profilable.test; import java.util.ArrayList; //import java.util.Iterator; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; //import javax.util.concurrent.profilable.ProfilableRunnable; //import javax.util.concurrent.profilable.locks.ProfilableReentrantLock; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class ArtificialLivelockTryer1 extends LoopRun { protected String CV = ""; public ArtificialLivelockTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { System.out.println("Tryer1: start a new loop"); //[1] if ( LockerRoom.samplelocks[1].tryLock() ) { CV+="R1+"; } else { LockerRoom.samplelocks[1].lock(); CV+="R1+"; } TimeUnit.MILLISECONDS.sleep(200); //[1] //[2] if ( LockerRoom.samplelocks[2].tryLock() ) { CV+="R2+"; } else { LockerRoom.samplelocks[2].lock(); CV+="R2+"; } TimeUnit.MILLISECONDS.sleep(200); //[2] //[3] if ( LockerRoom.samplelocks[3].tryLock() ) { CV+="R3+"; } else { LockerRoom.samplelocks[3].lock(); CV+="R3+"; } //[3] //[4] //get blocked //[4] //[5] //Tryer2 tries R1 result it realsing R1 //[5] //[6] TimeUnit.MILLISECONDS.sleep(200); //[6] //[7] //Tryer2 will try R3 //[7] //[8] //Blocking Tryer2 TimeUnit.MILLISECONDS.sleep(200); //[8] //[9] // tryer1 tries R4 resulting tryer1 release R3 if ( LockerRoom.samplelocks[4].tryLock() ) { CV+="R4+"; } else { //LockerRoom.samplelocks[3].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3-"; } //[9] //[10] //nothing happens this phase // tryer1 has R3,R4 // tryer2 has R1,R2 TimeUnit.MILLISECONDS.sleep(200); //[10] //[11] // drop all locks, end this thread //LockerRoom.samplelocks[1].unlock(); // CV+="R1-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) CV+="R1-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) CV+="R4-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[2])) CV+="R2-"; //[11] // break; //halted =true; // tell parent class proper end CV+="\n"; } } catch (InterruptedException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } finally { if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) CV+="R1e"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3e"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) CV+="R4e"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[2])) CV+="R2e"; } System.out.println("Tryer1 CV:\n"+CV); } } class ArtificialLivelockTryer2 extends LoopRun { protected String CV = ""; public ArtificialLivelockTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted) { //[1] if ( LockerRoom.samplelocks[3].tryLock() ) { CV+="R3+"; } else { LockerRoom.samplelocks[3].lock(); CV+="R3+"; } TimeUnit.MILLISECONDS.sleep(200); //[1] //[2] if ( LockerRoom.samplelocks[4].tryLock() ) { CV+="R4+"; } else { LockerRoom.samplelocks[4].lock(); CV+="R4+"; } TimeUnit.MILLISECONDS.sleep(200); //[2] //[3] //block tryer1, tryer is trying R3 TimeUnit.MILLISECONDS.sleep(200); //[3] //[4] //no time slice, but there is a graph, graph in [3] shows try edge, graph in [4] shows a tree //[4] //[5] if ( LockerRoom.samplelocks[1].tryLock() ) { //this will be false CV+="R1+"; } else { if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) //LockerRoom.samplelocks[3].unlock(); CV+="R3-"; } TimeUnit.MILLISECONDS.sleep(200); //[5] //[6] // let tryer1 get R3 TimeUnit.MILLISECONDS.sleep(200); //[6] //[7] if ( LockerRoom.samplelocks[3].tryLock() ) { //this will be false CV+="R3+"; } else { LockerRoom.samplelocks[3].lock(); CV+="R3+"; } // //[7] //[8] // get blocked //[8] //[9] // tryer1 tries R4 resulting tryer1 release R3 //TimeUnit.MILLISECONDS.sleep(200); //[9] //[10] //nothing happens this phase // tryer1 has R3,R4 // tryer2 has R1,R2 TimeUnit.MILLISECONDS.sleep(200); //[10] //[11] // drop all locks, end this thread //LockerRoom.samplelocks[1].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) CV+="R1-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) //LockerRoom.samplelocks[3].unlock(); CV+="R3-"; if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) //LockerRoom.samplelocks[4].unlock(); CV+="R4-"; //[11] // break; //halted =true; // tell parent class proper end CV+="\n"; //System.out.println("Tryer2 CV:\n"+CV); } } catch (InterruptedException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } finally { if (LoopRun.properlyUnlock(LockerRoom.samplelocks[1])) //LockerRoom.samplelocks[1].unlock(); CV+="R1e"; //LockerRoom.samplelocks[3].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[3])) CV+="R3e"; //LockerRoom.samplelocks[4].unlock(); if (LoopRun.properlyUnlock(LockerRoom.samplelocks[4])) CV+="R4e"; } System.out.println("Tryer2 CV:\n"+CV); } } public class Test20130115_ArtificialLivelock { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "LIVE_LOCK_DEMO"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,51.375,35.75); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(2000); lpr1.setHalted(true); lpr2.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(10000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } So, you would see the concern is no longer to create a live-lock. At the end of each thread, we did something. I hope this will provide some hint about how to deal with concurrent program that looks bizzare. In general, we should not fear live-lock. As long as the threads are alive, we will have a chance to change the resource access pattern. If a system has no hope, that is the real problem.
	Advanced Concurrency Topic: Runtime Deadlock Detection XXVII More Tested Examples Multi-tier How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_MultiTier .\ Entry point: package javax.util.concurrent.profilable.test; import java.util.ArrayList; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class MulitiTierTryer1 extends LoopRun { //protected String CV = ""; public MulitiTierTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[1].lock(); LockerRoom.samplelocks[2].lock(); TimeUnit.MILLISECONDS.sleep(2000); halted = true; } } catch (InterruptedException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[1]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } } } class MulitiTierTryer2 extends LoopRun { //protected String CV = ""; public MulitiTierTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[3].lock(); LockerRoom.samplelocks[4].lock(); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[2].lock(); halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[3]); LoopRun.properlyUnlock(LockerRoom.samplelocks[4]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } } } class MulitiTierTryer3 extends LoopRun { //protected String CV = ""; public MulitiTierTryer3(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[5].lock(); LockerRoom.samplelocks[6].lock(); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[3].lock(); halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[5]); LoopRun.properlyUnlock(LockerRoom.samplelocks[6]); LoopRun.properlyUnlock(LockerRoom.samplelocks[3]); } } } class MulitiTierTryer4 extends LoopRun { //protected String CV = ""; public MulitiTierTryer4(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { try { while (!halted ) { LockerRoom.samplelocks[0].lock(); LockerRoom.samplelocks[9].lock(); TimeUnit.MILLISECONDS.sleep(200); LockerRoom.samplelocks[5].lock(); halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[0]); LoopRun.properlyUnlock(LockerRoom.samplelocks[9]); LoopRun.properlyUnlock(LockerRoom.samplelocks[5]); } } } public class Test20130120_MultiTier { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "PROF_MUTLTI_TIER"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,91.375,71.5); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); //LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); //LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); LoopRun lpr1 = new MulitiTierTryer1(startSignal); LoopRun lpr2 = new MulitiTierTryer2(startSignal); LoopRun lpr3 = new MulitiTierTryer3(startSignal); LoopRun lpr4 = new MulitiTierTryer4(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); fl.add(exec.submit(lpr3)); fl.add(exec.submit(lpr4)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(5000); lpr1.setHalted(true); lpr2.setHalted(true); lpr3.setHalted(true); lpr4.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(5000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } Fast How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_Fast .\ Entry point: package javax.util.concurrent.profilable.test; // Search YOU_CAN_ADJUST_THIS_VALUE // On my latop (Q9000 processor): // 100 milli-second, two thread / three locks, proper lock/unlock order //Tryer2 count: 1272 //Thread stopped by itself! //Tryer1 count: 324 //Thread stopped by itself! //50 milli-second, two thread / three locks, proper lock/unlock order //MSG: createATNodeforProfilable:2 2 11 //Tryer2 count: 296 //Thread stopped by itself! //Tryer1 count: 214 //Thread stopped by itself! // it produces too much pitures, so we don't show them. import java.util.ArrayList; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class FastTryer1 extends LoopRun { //protected String CV = ""; public FastTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { long count = 0; try { while (!halted ) { LockerRoom.samplelocks[1].lock(); LockerRoom.samplelocks[2].lock(); LockerRoom.samplelocks[3].lock(); //TimeUnit.MILLISECONDS.sleep(2000); //halted = true; LockerRoom.samplelocks[1].unlock(); LockerRoom.samplelocks[2].unlock(); LockerRoom.samplelocks[3].unlock(); ++count; } } // catch (InterruptedException e) { // e.printStackTrace(); // } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[1]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } System.out.println("Tryer1 count: "+ count); } } class FastTryer2 extends LoopRun { //protected String CV = ""; public FastTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { long count = 0; try { while (!halted ) { LockerRoom.samplelocks[1].lock(); LockerRoom.samplelocks[2].lock(); LockerRoom.samplelocks[3].lock(); //TimeUnit.MILLISECONDS.sleep(2000); //halted = true; LockerRoom.samplelocks[1].unlock(); LockerRoom.samplelocks[2].unlock(); LockerRoom.samplelocks[3].unlock(); ++count; } } // catch (InterruptedException e) { // e.printStackTrace(); // } catch (Exception e) { e.printStackTrace(); } finally { LoopRun.properlyUnlock(LockerRoom.samplelocks[1]); LoopRun.properlyUnlock(LockerRoom.samplelocks[2]); } System.out.println("Tryer2 count: "+ count); } } public class Test20130120_Fast { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "PROF_FAST"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,91.375,71.5); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); //LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); //LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); LoopRun lpr1 = new FastTryer1(startSignal); LoopRun lpr2 = new FastTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); //TODO YOU_CAN_ADJUST_THIS_VALUE long thisvalue = 50; TimeUnit.MILLISECONDS.sleep(thisvalue); lpr1.setHalted(true); lpr2.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(20000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } } Random How to: java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130121_Random .\ Entry point: package javax.util.concurrent.profilable.test; import java.util.ArrayList; import java.util.Calendar; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import javax.util.concurrent.profilable.IndexPermutation; import javax.util.concurrent.profilable.LockerRoom; import javax.util.concurrent.profilable.LoopRun; import javax.util.concurrent.profilable.messenger.GraphMessenger; import net.heteroclinic.graph.Bag; import net.heteroclinic.graph.ForestMinistry; class RandomTryer1 extends LoopRun { //protected String CV = ""; public RandomTryer1(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { int [] indices = IndexPermutation.getARandomPermutation(10,5); try { while (!halted ) { for (int i:indices) { LockerRoom.samplelocks[i-1].lock(); } TimeUnit.MILLISECONDS.sleep(200); for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } } } } class RandomTryer2 extends LoopRun { //protected String CV = ""; public RandomTryer2(CountDownLatch startsignal) { super(startsignal); } @Override public void loop() { int [] indices = IndexPermutation.getARandomPermutation(10,5); try { while (!halted ) { for (int i:indices) { LockerRoom.samplelocks[i-1].lock(); } TimeUnit.MILLISECONDS.sleep(200); for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } halted = true; } } catch (Exception e) { e.printStackTrace(); } finally { for (int i:indices) { LoopRun.properlyUnlock(LockerRoom.samplelocks[i-1]); } } } } public class Test20130121_Random { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { Calendar.getInstance().getTimeInMillis(); Bag.tierdistance = 10.0d; Bag.nodesize = 2.5d; Bag.nodespace = 1.3d Bag.nodesize; Bag.familydistance = 2.0d * Bag.nodespace; Bag.boderspace = 3.0d * Bag.nodespace; Bag.OneDoubleequalpixels = 15; Bag.fontsize = 14; Bag.fontwidth = 8; // not accurate. Bag.edgetrim = 1.5d; // ratio if (args.length >= 1) { Bag.testresultfilepath = args[0]; } else { Bag.testresultfilepath = "C:\\Users\\Graphics\\Desktop\\treetortest\\"; } Bag.testunitname = "PROF_RANDOM"; Bag.testresultfiletype = ".png"; Bag.treeinteveralinforest = 1.0d * Bag.nodespace; // first pass set Bag.forestministryusepresetgraphborder false // second pass set true, change the values with // ForestMinistry.initGraphBorder Bag.forestministryusepresetgraphborder = true; if (Bag.forestministryusepresetgraphborder) { Bag.forestministryupdategraphborder = false; ForestMinistry.initGraphBorder(-1,0.0,0.0,0.0,0.0,0.0,0.0,51.375,58.5); } else { Bag.forestministryupdategraphborder = true; } CountDownLatch startSignal = new CountDownLatch(1); List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); Future<?> mesgrfuture = exec.submit(new GraphMessenger(startSignal)); //LoopRun lpr1 = new ArtificialLivelockTryer1(startSignal); //LoopRun lpr2 = new ArtificialLivelockTryer2(startSignal); LoopRun lpr1 = new RandomTryer1(startSignal); LoopRun lpr2 = new RandomTryer2(startSignal); fl.add(exec.submit(lpr1)); fl.add(exec.submit(lpr2)); // fl.add(exec.submit(new GraphMessenger(startSignal))); TimeUnit.MILLISECONDS.sleep(500); lpr1.setHalted(true); lpr2.setHalted(true); TimeUnit.MILLISECONDS.sleep(500); exec.shutdown(); for (Future<?> f : fl) { f.cancel(true); //TimeUnit.MILLISECONDS.sleep(20000); } TimeUnit.MILLISECONDS.sleep(5000);// CountDownLatch will be better. // So far, I don't want to // change the base jars. mesgrfuture.cancel(true); ForestMinistry.printStaticGraphBorder(); } }
	Advanced Concurrency Topic: Runtime Deadlock Detection XXVIII Period So far, months have been spent upon this topic. The resources are limited, I have to put a period. We may continue on with the same topic or similiar topic. Today, we release jdfr1.0.jar. - it fully supports Java ReentrantLock - it has several proto-types, quick-starts or just say examples -- in the Blog section It will be a very useful tool to profile concurrent programming. We also have treetor treetorplus3.jar which can render about several thousands nodes of a-cyclic graph or a forest. If I got enough support, we may switch to OpenGL rendering engine and using more advanced IPC. We corrected some mis-understandings. They are critical but finally not fatal to this project. I am still not sure about next step. I hope there will be more people download and study what I did. It will be a great pleasure that you can achieve something with these tools. Science and technology does not rely on luck. If you find any bug or errors, please feel free to point them out. This project is done by one person, so it is convenient to control. In real life projects, we have to resolve human conflicts, legacy pacakges etc. Some time you do not even have the source code not mention how to modify them. So we can not simply put a easy or difficult label for a project. The methods we tried or proposed, may be helpful while extending to profile database system, interprocess concurrent programming, the operating system, or for clustered computing units. Concurrent programming in some sense destroyed the von Neuman architecture, much more effort is needed for understanding or utilizing the nature of concurrency.