Finding Bugs in Concurrent SoftwareCMSC 433Fall 2006Options• Static analysis• Normal testing– hard to set up tests, results notreproducible• stepwise controlled testing• Dynamic data race detectionOne Place Bufferpublic class OnePlaceBuffer<T> {T value;synchronized public void put(@NonNull T v) {if (v == null) throw new NullPointerException();while (value != null) wait();value = v;notifyAll();}synchronized public @NonNull T get() {while (value == null) wait();T result = value;value = null;notifyAll();return result;}}Testing• At a minimum, we want full branchcoverage– we probably want to test situations whilewhile loops execute 2+ times as wellMultithreaded test caseclass MyTest extends MultithreadedTestCase { OnePlaceBuffer<String> buf; public initialize() { buf = new OnePlaceBuffer<String>(); } public void thread1() { buf.put(“a”); } public void thread2() { assertEquals(“a”, buf.get()); } }class MyTest extends MultithreadedTestCase { OnePlaceBuffer<String> buf; public void initialize() { buf = new OnePlaceBuffer<String>(); } public void thread1() { buf.put(“a”); } public void thread2() { Thread.sleep(1000); buf.put(“b”); } public void thread3() { Thread.sleep(2000); assertEquals(“a”, buf.get()); } public void thread4() { Thread.sleep(3000); assertEquals(“b”, buf.get()); }}What to do?• Making code depend upon sleep andtiming is yucky– doesn’t scale– doesn’t work in debugger– doesn’t always work• Introduce new idea– a metronome timer for thread test casesMetronome timer• Timer starts at zero• Advances only when all threads areblocked• Threads can wait until the timer reachesa particular value• Threads can query the current value ofthe timerOne place buffer example• Let’s figure out the timing/ticks for a testcase where two threads try to putsomething before any thread tries toremove somethingput(“a”)put(“b”)get()get()Thread 1 Thread 2 Thread 3 Thread 4Tick0123Running a test case• TestFramework.runOnce( new MyMTTestCase())• will run the test case once• TestFramework.runManyTimes( new MyMTTestCase(),42)• will run the test case 42 timesMore details on setting up amultithreaded test case• initialize() method is executed• all void thread…() methods are run,each in a separate thread• finish() method is executed• Class extends junit Assert class, so allthe assertXXX(…) methods areavailableTesting with metronomeclass MyTest extendsMultithreadedTestCase {OnePlaceBuffer<String> buf;public void initialize() { buf = new OnePlaceBuffer<String>();}public void thread1() { buf.put("a"); assertEquals(0,getTick());}public void thread2() { waitForTick(1); buf.put("b"); assertEquals(2,getTick());}public void thread3() { waitForTick(2); assertEquals("a", buf.get()); assertEquals(2,getTick());}public void thread4() { waitForTick(3); assertEquals("b", buf.get()); assertEquals(3,getTick());}}Runtime tools• You can use various tools to performdynamic instrumentation and testing forconcurrency:– data race detection– introduce additional thread interleavingPreventing Data Races• One programming technique to prevent races:– Ensure that for every shared field x, there is somelock L such that no thread accesses x withoutholding lock L• Note: This is not the only way to avoid races– There are fancier, more complicated techniques– But this is what you should do for your projectDetecting Races withcheckSync• Algorithm– Locks_held(t) = set of locks held by thread t– For each shared field x, C(x) := { all locks }– On each access to x by thread t,• C(x) := C(x) locks_held(t)• If C(x) = then issue a warning– From Savage et al, “Eraser: A Dynamic Race Detector forMultithreaded Programs,” TOCS 1997An Improvement• Unsynchronized r eads of ashared location are OK– As long as no one write s tothe field after it becomesshared• Track state of each field– Only enforce lockingprotocol when it becomesshared and writtenCheckSync• added a new file to your project 2distribution:– lib/checkSync.jar• add -javaagent:lib/checkSync.jar to yourJVM arguments to use checkSyncWhat checkSync does• Instruments your code to apply theeraser protocol• throws an exception if an accessviolates it– use -javaagent:lib/checkSync.jar=keepGoingto force it to keep going, printing error logto sync.log– use =report to get a report on all fieldsprinted to
View Full Document
Unlocking...