Analysis for Safe ConcurrencyOptional supplementary reading: Assuring and Evolving Concurrent Programs: Annotations and Policyand Policy15-214: Principles of Software System ConstructionJonathan Aldrich1Example: java.util.logging.Loggerpublic class Logger { ...private Filter filter;/** ...* @param newFilter a filter object (may be null)*/public void setFilter(Filter newFilter) ... {if (!anonymous) manager.checkAccess();[Source: AaronGreenhouse]if (!anonymous) manager.checkAccess();filter = newFilter;}public void log(LogRecord record) { ...synchronized (this) {if (filter != null&& !filter.isLoggable(record)) return;} ...} ...}29 November 2011Analysis of Software Artifacts:Concurrency 2Consider setFilter() in isolationExample: java.util.logging.Loggerpublic class Logger { ...private Filter filter;/** ...* @param newFilter a filter object (may be null)*/public void setFilter(Filter newFilter) ... {if (!anonymous) manager.checkAccess();[Source: AaronGreenhouse]if (!anonymous) manager.checkAccess();filter = newFilter;}public void log(LogRecord record) { ...synchronized (this) {if (filter != null&& !filter.isLoggable(record)) return;} ...} ...}29 November 2011Analysis of Software Artifacts:Concurrency 3Consider log() in isolationExample: java.util.logging.Logger/** ... All methods on Logger are multi-thread safe. */public class Logger { ...private Filter filter;/** ...* @param newFilter a filter object (may be null)*/public void setFilter(Filter newFilter) ... {if (!anonymous) manager.checkAccess();[Source: AaronGreenhouse]if (!anonymous) manager.checkAccess();filter = newFilter;}public void log(LogRecord record) { ...synchronized (this) {if (filter != null&& !filter.isLoggable(record)) return;} ...} ...}29 November 2011Analysis of Software Artifacts:Concurrency 4Consider class Logger in it’s entirety!Example: java.util.logging.Logger/** ... All methods on Logger are multi-thread safe. */ public class Logger { ...private Filter filter;/** ...* @param newFilter a filter object (may be null)*/public void setFilter(Filter newFilter)…{if (!anonymous) manager.checkAccess();1[Source: AaronGreenhouse]if (!anonymous) manager.checkAccess();filter = newFilter;}public void log(LogRecord record) { ...synchronized (this) {if (filter != null&& !filter.isLoggable(record)) return;} ...} ...}29 November 2011Analysis of Software Artifacts:Concurrency 5Class Logger has a race condition.213Example: java.util.logging.Logger/** ... All methods on Logger are multi-thread safe. */ public class Logger { ...private Filter filter;/** ...* @param newFilter a filter object (may be null)*/public synchronized void setFilter(Filter newFilter)…{if (!anonymous) manager.checkAccess();[Source: AaronGreenhouse]if (!anonymous) manager.checkAccess();filter = newFilter;}public void log(LogRecord record) { ...synchronized (this) {if (filter != null&& !filter.isLoggable(record)) return;} ...} ...}29 November 2011Analysis of Software Artifacts:Concurrency 6Correction: synchronize setFilter()Review: Race ConditionsProblem: Race condition in class Logger• Race condition:– A situation in which the result of computation is dependent on the sequence or timing of program events• Data race: a common source of race conditions(From Savage et al., Eraser: A Dynamic Data Race Detector for Multithreaded Programs)– Two threads access the same variable– At least one access is a write– No explicit mechanism prevents the accesses from being simultaneous29 November 2011Analysis of Software Artifacts:Concurrency 7Race Condition ChallengesProblem: Race condition in class Logger• Non-local error– Had to inspect whole class• Bad code invalidates good code–Could have to inspect all clients of class–Could have to inspect all clients of class• Hard to test– Problem occurs non-deterministically• Depends on how threads interleave29 November 2011Analysis of Software Artifacts:Concurrency 8Races and InvariantsProblem: Race condition in class Logger• Not all race conditions result in errors• Error results when invariant is violated–Logger invariant–Logger invariant• filter is not null at call following null test– Race-related error• race between write and dereference of filter• if the write wins the race, filter is null at the call29 November 2011Analysis of Software Artifacts:Concurrency 9Races and Design IntentProblem: Race condition in class Logger• Need to know design intent– Should instances be used across threads?– If so, how should access be coordinated?• Assumed log was correct: synchronize on this• Could be caller’s responsibility to acquire lock⇒⇒⇒⇒ log is incorrect⇒⇒⇒⇒ Need to check call sites of log and setFilter29 November 2011Analysis of Software Artifacts:Concurrency 10Review: Avoiding RacesHow would you make sure your code avoids race conditions?• Keep some data local to a single thread– Inaccessible to other threads– e.g. local variables, Java AWT & Swing, thread state• Protect shared data with locks– Acquire lock before accessing data, release afterwards–e.g. Java synchronized, OS kernel locks–e.g. Java synchronized, OS kernel locks• Forbid context switches/interrupts in critical sections of code– Ensures atomic update to shared state– e.g. many embedded systems, simple single processor OSs• Analyze all possible thread interleavings– Ensure invariants cannot be violated in any execution– Does not scale beyond smallest examples• Future: transactional memory29 November 2011Analysis of Software Artifacts:Concurrency 11Lock-based Concurrency• Associate a lock with each shared variable– Acquire the lock before all accesses– Group all updates necessary to maintain data invariant– Hold all locks until update is complete• Granularity– Fine-grained locks allow more concurrency• Can be tricky if different parts of a data structure are protected by different—perhaps dynamically created—locks– Coarse-grained locks have lower overhead29 November 2011Analysis of Software Artifacts:Concurrency 12JSure: Tool Support for Safe Concurrency29 November 2011Analysis of Software Artifacts:Concurrency 13Races and Design IntentProblem: Race condition in class Logger• Need to know design intent– Should instances be used across threads?– If so, how should access be coordinated?• Assumed log was correct: synchronize on this• Could be caller’s responsibility to acquire lock⇒⇒⇒⇒ log is incorrect⇒⇒⇒⇒ Need to check