Zhikai Wang Homepage

Heteroclinic.net logo

www.heteroclinic.net

	Advanced Concurrency Topic: Runtime Deadlock Detection I Deadlock can be a nightmare, but when it happens, we may not notice it. It may be burried deep in the vast quantity of process/thread instances. Nothing is shown in the GUI, nothing is written in your log. Some programs may behave strangely, you may notice or not. We did some experiments, code hacking. Finally, under the very limited conditions of our experiment, we found such deadlocks are detect-able. Thus, we may provide some remedy. Our knowledge and understanding may be partial, in-complete even wrong. Please do not hesitate to point out them. Here we choose Java because Java is so convenient to deploy such an application. Other programming languages should be sufficient too. Our mission is to study/understand the deadlock phenomenon not to debate the features of different languages. The beginning part requires you set up the following Java program in a same package. For convenience, I used the latest JDK and the latest Eclipse IDE. Util.java import java.text.Format; import java.text.SimpleDateFormat; import java.util.Calendar; public class Util { public static String getMilSecondStamp() { Format formatter; Calendar.getInstance().getTimeInMillis(); formatter = new SimpleDateFormat("HH:mm:ss.SSS"); return formatter.format(Calendar.getInstance().getTimeInMillis()); } public static void main (String [] args ) { System.out.println(getMilSecondStamp()); System.out.println(getMilSecondStamp()); } } Indy.java import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicLong; public class Indy implements Runnable { static AtomicLong count = new AtomicLong(0); protected long id; protected Object instrument1; protected Object instrument2; public Indy (Object instrument1,Object instrument2) { id = count.incrementAndGet(); this.instrument1 = instrument1; this.instrument2 = instrument2; } @Override public void run() { try { synchronized (instrument1) { System.out.println(instrument1 +" is lokced by Indy "+id); TimeUnit.MILLISECONDS.sleep(1000); synchronized (instrument2) { System.out.println(instrument2 +" is lokced by Indy "+id); TimeUnit.MILLISECONDS.sleep(1000); } System.out.println(instrument2 +" is released by Indy "+id); } System.out.println(instrument1 +" is released by Indy "+id); } catch (InterruptedException e) { e.printStackTrace(); } } } FindRaceCondition.java import java.util.ArrayList; import java.util.List; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; public class FindRaceCondition { public static Object resource1 = new Object(){ public String toString () { return "resource1"; } }; public static Object resource2 = new Object(){ public String toString () { return "resource2"; } }; public static Object resource3 = new Object(){ public String toString () { return "resource3"; } }; public static Object resource4 = new Object(){ public String toString () { return "resource4"; } }; /** * @param args * @throws InterruptedException */ public static void main(String[] args) throws InterruptedException { List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); fl.add(exec.submit(new Indy(resource1,resource2))); fl.add(exec.submit(new Indy(resource2,resource1))); TimeUnit.MILLISECONDS.sleep(10000); exec.shutdown(); for (Future<?> f: fl) f.cancel(true); } } By change the two lines in `FindRaceCondition.java', we did some experiments. fl.add(exec.submit(new Indy(resource1,resource1))); fl.add(exec.submit(new Indy(resource2,resource2))); resource1 is lokced by Indy 1 resource2 is lokced by Indy 2 resource2 is lokced by Indy 2 resource1 is lokced by Indy 1 resource1 is released by Indy 1 resource1 is released by Indy 1 resource2 is released by Indy 2 resource2 is released by Indy 2 fl.add(exec.submit(new Indy(resource1,resource2))); fl.add(exec.submit(new Indy(resource3,resource4))); resource3 is lokced by Indy 2 resource1 is lokced by Indy 1 resource4 is lokced by Indy 2 resource2 is lokced by Indy 1 resource4 is released by Indy 2 resource3 is released by Indy 2 resource2 is released by Indy 1 resource1 is released by Indy 1 fl.add(exec.submit(new Indy(resource1,resource2))); fl.add(exec.submit(new Indy(resource1,resource4))); resource1 is lokced by Indy 1 resource2 is lokced by Indy 1 resource2 is released by Indy 1 resource1 is released by Indy 1 resource1 is lokced by Indy 2 resource4 is lokced by Indy 2 resource4 is released by Indy 2 resource1 is released by Indy 2 fl.add(exec.submit(new Indy(resource1,resource2))); fl.add(exec.submit(new Indy(resource1,resource2))); resource1 is lokced by Indy 1 resource2 is lokced by Indy 1 resource2 is released by Indy 1 resource1 is released by Indy 1 resource1 is lokced by Indy 2 resource2 is lokced by Indy 2 resource2 is released by Indy 2 resource1 is released by Indy 2 Finally when we set fl.add(exec.submit(new Indy(resource1,resource2))); fl.add(exec.submit(new Indy(resource2,resource1))); The deadlock is almost certain to happen. Please notice we say almost. In concurrency programming, nothing is certain (but statistically high probability). resource2 is lokced by Indy 2 resource1 is lokced by Indy 1 //JVM hangs them, even the f.cancel() does not work.
	Advanced Concurrency Topic: Runtime Deadlock Detection II Now we put two new files, if you change the value of the last argument of ThrottledIndy's constructor in file `DeadlockThrottle.java'. You will see deadlock may not be certain. Our experiments shows another mis-understanding that even every method is synchronized, it is still not safe -- at least, deadlock may happen. fl.add(exec.submit(new ThrottledIndy(resource1,resource2,10))); fl.add(exec.submit(new ThrottledIndy(resource2,resource1,10))); DeadlockThrottle.java import java.util.ArrayList; import java.util.List; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; public class DeadlockThrottle extends FindRaceCondition { /** * @param args * @throws InterruptedException / public static void main(String[] args) throws InterruptedException { List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); fl.add(exec.submit(new ThrottledIndy(resource1,resource2,10))); fl.add(exec.submit(new ThrottledIndy(resource2,resource1,10))); TimeUnit.MILLISECONDS.sleep(10000); exec.shutdown(); for (Future<?> f: fl) f.cancel(true); } } ThrottledIndy.java* import java.util.Random; import java.util.concurrent.TimeUnit; public class ThrottledIndy extends Indy { protected Random rand = new Random(); protected int throttle; public ThrottledIndy(Object instrument1, Object instrument2,int throttle) { super(instrument1, instrument2); if (throttle < 1) this.throttle = 1; else this.throttle = throttle; } @Override public void run() { try { synchronized (instrument1) { System.out.println(instrument1 +" is lokced by Indy "+id); TimeUnit.MILLISECONDS.sleep(1000); if (rand.nextInt() % throttle == 0 ){ synchronized (instrument2) { System.out.println(instrument2 +" is lokced by Indy "+id); TimeUnit.MILLISECONDS.sleep(1000); } System.out.println(instrument2 +" is released by Indy "+id); } else { System.out.println("Nothing is lokced by Indy "+id); TimeUnit.MILLISECONDS.sleep(1000); System.out.println("Nothing is released by Indy "+id); } } System.out.println(instrument1 +" is released by Indy "+id); } catch (InterruptedException e) { e.printStackTrace(); } } } Here are the results that are not certain: fl.add(exec.submit(new ThrottledIndy(resource1,resource2,1))); fl.add(exec.submit(new ThrottledIndy(resource2,resource1,1))); resource2 is lokced by Indy 2 resource1 is lokced by Indy 1 // it happened. fl.add(exec.submit(new ThrottledIndy(resource1,resource2,10))); fl.add(exec.submit(new ThrottledIndy(resource2,resource1,10))); resource2 is lokced by Indy 2 resource1 is lokced by Indy 1 Nothing is lokced by Indy 1 Nothing is lokced by Indy 2 Nothing is released by Indy 1 resource1 is released by Indy 1 Nothing is released by Indy 2 resource2 is released by Indy 2 // it did not happen
	Advanced Concurrency Topic: Runtime Deadlock Detection III We found Indies like to be alone almost all the time, otherwise, the results are really unpredictable or not what we want. So we design a class Duo. First, Duos should be able to do Indy's job. We also put class Resource to a separate file. The experiments is executed from the main of `TestDuoDeadlockableVersion.java'. You will find Duo behave the same as Indy. Duo.java /** * www.heteroclinic.net * May 2012 * Please keep this header. / import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicLong; public class Duo implements Runnable { static AtomicLong count = new AtomicLong(0); protected long id; // id is immutable public long getId() { return id; } // public void setId(long id) { // this.id = id; // } protected Resource instrument1; protected Resource instrument2; public String toString() { return "Duo " + id; } public Duo(Resource instrument1, Resource instrument2) { id = count.incrementAndGet(); this.instrument1 = instrument1; this.instrument2 = instrument2; } @Override public void run() { try { if (!instrument1.duolock(0)) { System.out.println( this + " is waiting for " +instrument1); while (!instrument1.duolock(0)) { instrument1.duowait(0); } } System.out.println(instrument1 + " is lokced by " + this); TimeUnit.MILLISECONDS.sleep(1000); if (!instrument2.duolock(0)) { System.out.println( this + " is waiting for " +instrument2); while (!instrument2.duolock(0)) { instrument2.duowait(0); } } System.out.println(instrument2 + " is lokced by " + this); TimeUnit.MILLISECONDS.sleep(1000); instrument2.duounlock(0); System.out.println(instrument2 + " is released by " + this); instrument1.duounlock(0); System.out.println(instrument1 + " is released by " + this); / if (!instrument1.duolock(0)) { //instrument1.duowait(0); //instrument1.wait(); System.out.println( this + " is waiting for " +instrument1); } else { System.out.println(instrument1 + " is lokced by " + this); TimeUnit.MILLISECONDS.sleep(1000); if (!instrument2.duolock(0)) { //instrument2.duowait(0); //instrument2.wait(); System.out.println( this + " is waiting for " +instrument2); } else { System.out.println(instrument2 + " is lokced by " + this); TimeUnit.MILLISECONDS.sleep(1000); } System.out.println(instrument2 + " is released by " + this); } System.out.println(instrument1 + " is released by " + this); / } catch (InterruptedException e) { e.printStackTrace(); } catch (DeadlockException e) { e.printStackTrace(); } } } Resource.java* /** * www.heteroclinic.net * May 2012 * Please keep this header. / import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.locks.ReentrantLock; public class Resource { // extends ReentrantLock // protected ConcurrentHashMap <Long,TrainedDuo> lockmap = // new ConcurrentHashMap <Long,TrainedDuo>(); protected TrainedDuo lockthread = null; protected ReentrantLock lock = new ReentrantLock(); protected boolean ready = true; public boolean isReady() { return ready; } public void setReady(boolean ready) { this.ready = ready; } /* * / @SuppressWarnings("unused") private static final long serialVersionUID = -1345377697065575731L; protected static AtomicLong count = new AtomicLong(0); protected long id; // immutable public long getId() { return id; } // public void setId(long id) { // this.id = id; // } public Resource() { id = count.incrementAndGet(); } public String toString() { return "Resource " + id; } // should be synchronized, but I have not figure out // lock.lock(), synchronized(lock), and synchronized(this)'s relations public boolean duolock(long tid) { if (!lock.tryLock()) return false; else { // lockmap.put(tid, TrainedDuo.trainedduos.get(tid)); if (tid > 0L) { this.lockthread = TrainedDuo.trainedduos.get(tid); lockthread.sputAResourceasLocked(this); } return true; } } // should be synchronized, but I have not figure out // lock.lock(), synchronized(lock), and synchronized(this)'s relations public void duowait(long tid) throws InterruptedException, DeadlockException { if (tid > 0L) { // this.lockthread =null; boolean isthatguywaiting = false; // TODO // When thread tid try to wait a resource, // 1. It will check the thread id that is holding the resource // (should be unique) // 2. It will check if the other thread in 1. is in wait status // 3. If the thread in 1. is waiting, is it waiting for something I // hold/lock. // 4. If 2. and 3., I(thread try to wait) will yield, release the // locks properly // (in the future, maybe a stack or tree structure, now just a // simple list or queue). // If we do so, only one thread will be in the wait status, deadlock // will not happen. // 1. get that guy // this.lockthread =null; // 2. isthatguywaiting = this.lockthread.isIswaiting(); if (isthatguywaiting) { // 3. whatthatguywaitingfor Resource whatthatguywaitingfor = this.lockthread .getResourceiamwaitingfor(); TrainedDuo me = TrainedDuo.trainedduos.get(tid); // Now I go upstage. if (me.isAResourceLockedbyme(whatthatguywaitingfor)) throw new DeadlockException(); } } // System.out.println("outside duowait synchronized block, "); synchronized (lock) { // System.out.println("inside duowait synchronized block, "); // Probably you can get here because lock.lock() locks the thread, // synchronized (lock) locks the lock object. Whatever, we can use // lock as a semaphore. if (tid > 0L) { TrainedDuo me = TrainedDuo.trainedduos.get(tid); me.setResourceiamwaitingfor(this); } lock.wait(); } } // should be synchronized, but I have not figure out // lock.lock(), synchronized(lock), and synchronized(this)'s relations // if I put this function syncrhonized, there will be a deadlock, I don't why? //TODO solve this problem. public void duounlock(long tid) { lock.unlock(); if (tid > 0L) { this.lockthread = null; } synchronized (lock) { lock.notifyAll(); } } } TestDuoDeadlockableVersion.java* /** * www.heteroclinic.net * May 2012 * Please keep this header. */ import java.util.ArrayList; import java.util.List; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; // to test the Duo deadlockable version public class TestDuoDeadlockableVersion { static Resource resource1 = new Resource(); static Resource resource2 = new Resource(); static Resource resource3 = new Resource(); static Resource resource4 = new Resource(); public static void main(String[] args) throws InterruptedException { List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); fl.add(exec.submit(new Duo(resource1,resource2))); fl.add(exec.submit(new Duo(resource2,resource1))); TimeUnit.MILLISECONDS.sleep(1000000); exec.shutdown(); for (Future<?> f: fl) f.cancel(true); } } //Resource 2 is lokced by Duo 2 //Resource 1 is lokced by Duo 1 //Duo 2 is waiting for Resource 1 //Duo 1 is waiting for Resource 2
	Advanced Concurrency Topic: Runtime Deadlock Detection IV DeadlockException We did a lot of code hacking to simulate the intrinsic lock of Java Object class. The final result is under our confining box, deadlock is detected, and the late thread yield the resource to the early thread. Please note there may be implementation that is wrong, you can find the remarks I put. After we give some training to Duos, it seem they are able to handle a situation we don't want to get into. Please notice the difference of Duo and TrainedDuo. The parameter in duowait(long) for example, is 0 for Duo, value greater than 1 for TrainedDuo. Finally, we want to talk something about topology. Topology is not a secret world jargon. It simply means the way to represent connections of different entities in a space. I once try to do some visualization. We have thread, resource, and time. It is a three-dimensional world thus the diagram is not easy to plot. However, if you deal with computer graphics, you won't be strange to edge pair. With the aiding of edge pairs, we can traverse a connected simplex, may we call it a manifold. The starting function main is in file `TestTrainedDuo.java'. A result that is still not certain to get Resource 2 is lokced by Duo 2 Resource 1 is lokced by Duo 1 Duo 2 is waiting for Resource 1 Duo 1 is waiting for Resource 2 Duo 1 DeadlockException Resource 1 is released by Duo 1 Resource 1 is lokced by Duo 2 at Resource.duowait(Resource.java:98) at TrainedDuo.run(TrainedDuo.java:82) at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:471) at java.util.concurrent.FutureTask$Sync.innerRun(FutureTask.java:334) at java.util.concurrent.FutureTask.run(FutureTask.java:166) at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1110) at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:603) at java.lang.Thread.run(Thread.java:722) Resource 1 is released by Duo 2 Resource 2 is released by Duo 2 DeadlockException.java /** * www.heteroclinic.net * May 2012 * Please keep this header. / public class DeadlockException extends Exception { /* * / private static final long serialVersionUID = 5225385071459143614L; public String toString () { return "DeadlockException"; } } TrainedDuo.java* /** * www.heteroclinic.net * May 2012 * Please keep this header. / import java.util.Iterator; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.TimeUnit; public class TrainedDuo extends Duo { public static ConcurrentHashMap <Long,TrainedDuo> trainedduos = new ConcurrentHashMap <Long,TrainedDuo>(); protected ConcurrentHashMap <Long,Resource> lockedresources = new ConcurrentHashMap <Long,Resource>(); public synchronized void sputAResourceasLocked (Resource res) { lockedresources.put(res.getId(),res); // //System.out.println("in sputAResourceasLocked (Resource res) "); // Iterator<Long> iterator = lockedresources.keySet().iterator(); // while (iterator.hasNext()) { // Long key = (Long)iterator.next(); // Resource value = (Resource)lockedresources.get(key); // //value.duounlock(this.getId()); // System.out.println(key +" "+value); // } } public synchronized void removeAResourcefromLocked (Resource res) { lockedresources.remove(res.getId()); } public synchronized boolean isAResourceLockedbyme (Resource res){ //System.out.println(" isAResourceLockedbyme (Resource res) " ); //System.out.println(" Resource res " +res.getId()); return lockedresources.containsKey(res.getId()); } protected boolean iswaiting = false; Resource resourceiamwaitingfor = null; public synchronized Resource getResourceiamwaitingfor() { return resourceiamwaitingfor; } public synchronized void setResourceiamwaitingfor(Resource resourceiamwaitingfor) { iswaiting = true; this.resourceiamwaitingfor = resourceiamwaitingfor; } public synchronized boolean isIswaiting() { return iswaiting; } public synchronized void setIswaiting(boolean iswaiting) { this.iswaiting = iswaiting; } public TrainedDuo(Resource instrument1, Resource instrument2) { super(instrument1, instrument2); trainedduos.put(this.id, this); } @Override public void run() { try { if (!instrument1.duolock(this.getId())) { System.out.println( this + " is waiting for " +instrument1); while (!instrument1.duolock(this.getId())) { instrument1.duowait(this.getId()); } this.setIswaiting(false); this.setResourceiamwaitingfor(null); } System.out.println(instrument1 + " is lokced by " + this); TimeUnit.MILLISECONDS.sleep(1000); if (!instrument2.duolock(this.getId())) { System.out.println( this + " is waiting for " +instrument2); while (!instrument2.duolock(this.getId())) { instrument2.duowait(this.getId()); } this.setIswaiting(false); this.setResourceiamwaitingfor(null); } System.out.println(instrument2 + " is lokced by " + this); TimeUnit.MILLISECONDS.sleep(1000); instrument2.duounlock(this.getId()); System.out.println(instrument2 + " is released by " + this); instrument1.duounlock(this.getId()); System.out.println(instrument1 + " is released by " + this); } catch (InterruptedException e) { e.printStackTrace(); } catch (DeadlockException e) { System.out.println(this); e.printStackTrace(); } finally { Iterator<Long> iterator = lockedresources.keySet().iterator(); while (iterator.hasNext()) { Long key = (Long)iterator.next(); Resource value = (Resource)lockedresources.get(key); value.duounlock(this.getId()); System.out.println(value + " is released by " + this); } lockedresources.clear(); this.setIswaiting(false); this.setResourceiamwaitingfor(null); } } } TestTrainedDuo.java* /** * www.heteroclinic.net * May 2012 * Please keep this header. */ import java.util.ArrayList; import java.util.List; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; public class TestTrainedDuo extends TestDuoDeadlockableVersion { public static void main(String[] args) throws InterruptedException { List<Future<?>> fl = new ArrayList<Future<?>>(); ExecutorService exec = Executors.newCachedThreadPool(); fl.add(exec.submit(new TrainedDuo(resource1,resource2))); fl.add(exec.submit(new TrainedDuo(resource2,resource1))); TimeUnit.MILLISECONDS.sleep(100000000); exec.shutdown(); for (Future<?> f: fl) f.cancel(true); } }