Today’s AgendaRace AnalysisRace ConditionsGeneral & Data RacesExamplesSlide 6Locking DisciplineThe Algorithm (1)The Algorithm (2)Example (1)Example (2)False AlarmsInitializationRead-shared DataState TransitionsSlide 16Asynchronous vs. SynchronousCommunication Scheme (1)Communication Scheme (2)SR-sequenceExampleMessage Race (1)Message Race (2)Message Race (3)Message Race Detection (1)Message Race Detection (2)Message Race Detection (3)Message Race Detection (4)Message Race Detection (5)Today’s AgendaMidterm: Nov 3 or 10Finish Message PassingRace AnalysisAdvanced Topics in Software Engineering 1Advanced Topics in Software Engineering 2Race Analysis Introduction The Lockset Algorithm Message Race DetectionAdvanced Topics in Software Engineering 3Race ConditionsMany factors, such as unpredictable process scheduling and variations in message latencies, can contribute to the non-deterministic behavior of concurrent programs.These factors can be informally referred to as race conditions or just races. The activity of identifying races is referred to as race analysis.Advanced Topics in Software Engineering 4General & Data RacesThere are two different types of races that capture different kinds of bugs.General races cause nondeterministic execution and are failures in programs intended to be deterministic.Data races cause non-atomic execution of critical sections and are failures in programs that access and update shared data in critical sections.Advanced Topics in Software Engineering 5ExamplesProcess 1/* deposit */amount = read_amount ();P (mutex);balance = balance + amount;interest = interest + rate * balance;V (mutex);Process 2/* withdraw */amount = read_amount ();P (mutex);if (balance < amount) printf (“NSF”);else balance = balance – amount;interest = interest + rate * balance;V (mutex);Process 1/* deposit */amount = read_amount ();P (mutex);balance = balance + amount;interest = interest + rate * balance;V (mutex);Process 2/* withdraw */amount = read_amount ();if (balance < amount) printf (“NSF”);else balance = balance – amount;interest = interest + rate * balance;Advanced Topics in Software Engineering 6Race Analysis Introduction The Lockset Algorithm Message Race DetectionAdvanced Topics in Software Engineering 7Locking DisciplineA locking discipline is a programming policy that ensures the absence of data races. For example, a simple locking discipline is to require that every variable shared between threads is protected by a mutual exclusion lock. The lockset algorithm is to ensure that all shared-memory accesses follow the simple locking discipline.Advanced Topics in Software Engineering 8The Algorithm (1)For each shared variable v, the algorithm maintains the set C(v) of candidate locks as follows: When a variable is initialized, C(v) contains all possible locks; When a variable is accessed, C(v) is replaced with the intersection of C(v) and the set of locks held by the current thread. If C(v) becomes empty, it signals that there is no lock that consistently protects v. (Otherwise, there is at least one lock that remains in C(v).)Advanced Topics in Software Engineering 9The Algorithm (2)for each shared variable v, initialize CandidateLocks(v) to the set of all locksOn each read or write access to v by thread TCandidateLocks(v) = CandidateLocks(v)  LocksHeld (T)if (CandidateLocks(v) == {}) issue a warning.Advanced Topics in Software Engineering 10Example (1)Thread 1 LocksHeld(Thread1) CandidateLocks(s){ } { mutex1, mutex2}mutex1.lock(); { mutex1 } { mutex1, mutex2 }s = s + 1; { mutex1 } { mutex1, mutex2}mutex1.unlock(); { } { mutex1 }mutex2.lock(); { mutex2 } { mutex1 }s = s + 2; { mutex2 } { }mutex2.unlock(); { } { }Advanced Topics in Software Engineering 11Example (2){} {mutex1, mutex2}mutex1.lock{mutex1}{mutex1, mutex2}read s{mutex1} {mutex1}write s{mutex1}{mutex1}mutex1.unlock{} {mutex1}mutex2.lock{mutex2} {mutex1}read s{mutex2}{}LocksHeld CandidateLocksAdvanced Topics in Software Engineering 12False AlarmsThe simple locking discipline is strict, in the sense that some common programming practices violate this discipline and are still free from data races: Initialization: Shared variables are frequently initialized without a lock. Read-shared Data: Some shared variables are written during initialization and are read-only thereafter.Advanced Topics in Software Engineering 13InitializationThere is no need for a thread to lock out others if no other can possibly hold a reference to the data being accessed.To avoid false alarms caused by unlocked writes during initialization, we delay the refinement of a location’s candidate set until after it has been initialized.However, there is no easy way of knowing initialization is complete. Any solution?Advanced Topics in Software Engineering 14Read-shared DataSince simultaneous reads of a shared variable by multiple threads are not races, there is also no need to protect variable if it is read-only.To avoid false alarms caused by unlocked read-sharing for such data, we report races only after an initialized variable has become write-shared by more than one thread.Advanced Topics in Software Engineering 15State Transitionsvirginexclusivesharedshared-modifiedrd/wr, first threadwrrd, new thread rdwr, new threadwrAdvanced Topics in Software Engineering 16Race Analysis Introduction The Lockset Algorithm Message Race DetectionAdvanced Topics in Software Engineering 17Asynchronous vs. SynchronousIn an asynchronous message-passing program, each process uses non-blocking send and blocking receive operations to send and receive messages.This is in contrast with synchronous message-passing, where blocking send and blocking receive operations are used.Advanced Topics in Software Engineering 18Communication Scheme (1)A communication scheme may impose certain restrictions on the relationship between the order in which messages are sent and the order in which messages are received.The behavior of an asynchronous message-passing program depends on its underlying communication scheme.Advanced Topics in Software Engineering 19Communication Scheme (2)The fully asynchronous scheme allows that messages are received out of order.The FIFO scheme requires that messages exchanged between any two processes be received in the same order as they are sent.The causal scheme requires that all the messages are received in the same order as they are sent.Advanced Topics in