Today’s AgendaQuick ReviewTracing/Replay for Shared VariablesTracing and ReplayChallengesSYN-sequenceSYN-sequence (cont’d)Slide 8Slide 9DefinitionEncodingEncoding (cont’d)Slide 13ExampleSlide 15Slide 16InstrumentationstartRead & endReadstartWrite & endWriteCREWC++ ImplementationJava ImplementationAdvanced Topics in Software Engineering 1Today’s Agenda HW #1 Quick Review Finish The CS Problem Replay Shared VariablesAdvanced Topics in Software Engineering 2Quick Review What are the three requirements for the critical section problem?Advanced Topics in Software Engineering 3Tracing/Replay for Shared Variables Introduction RW-Sequence Tracing and Replay Implementation IssuesAdvanced Topics in Software Engineering 4Tracing and ReplayReplay is to repeat the behavior of a previous execution of a concurrent program.Tracing is to capture necessary information during a concurrent execution such that it can be repeated later in a controlled fashion.Advanced Topics in Software Engineering 5ChallengesThere are a number of challenges to address for tracing and replay: What exactly should be replayed? What information should be captured?  How should such information be encoded?Advanced Topics in Software Engineering 6SYN-sequenceA SYN-sequence is a sequence of synchronization operations, i.e. operations that are performed on shared variables or synchronization constructs.A concurrent execution can be repeated, in terms of producing the same results, if the same SYN-sequence is replayed.Advanced Topics in Software Engineering 7SYN-sequence (cont’d)A SYN-sequence can be object-based or thread-based.An object-based SYN-sequence is associated with a shared object, consisting of all synchronization operations that are executed on that object. A thread-based SYN-sequence is associated with a thread, consisting of all synchronization operations that are executed by that thread.Advanced Topics in Software Engineering 8SYN-sequence (cont’d)Replay based on SYN-sequences can be accomplished by inserting additional control into programming objects.The alternative is to record thread schedules, i.e., we record information about how context switches are performed. Replay based on thread schedules often involve modifications to the thread scheduler, which is usually more difficult to implement, but can be more efficient.Advanced Topics in Software Engineering 9Tracing/Replay for Shared Variables Introduction RW-sequence Tracing and Replay Implementation IssuesAdvanced Topics in Software Engineering 10DefinitionA SYN-sequence for a shared variable is a sequence of read and write operations, called a RW-sequence.Each write operation on a shared variable creates a new version of the variable.An execution can be replayed by ensuring each thread reads and writes the same variable versions that were recorded in the execution trace.Advanced Topics in Software Engineering 11EncodingFor each variable, we keep track of its versions: a write operation increases the version number; a read operation keeps the version number unchanged.In a RW-sequence, a read event is encoded as (ID, version), where ID is the ID of the thread that executes the read event, and version is the current version number.Advanced Topics in Software Engineering 12Encoding (cont’d)A write event is encoded as (ID, version, total reads), where ID is the ID of the thread that executes the write operation, version is the old version number, and total reads is the number of read operations that read the old version of the variable.Advanced Topics in Software Engineering 13Encoding (cont’d)There are two important points to be made about the definition of RW-sequence: We record the order in which read and write operations are performed, not the values that are read and written. There is no need to record any type information.Advanced Topics in Software Engineering 14ExampleT1 T2 T3temp = s; temp = s; s = s + 1;Assume that s is initialized to 0. A possible RW-sequence of s is:(3, 0)(1, 0)(3, 0, 2)(2, 1)Advanced Topics in Software Engineering 15Tracing/Replay for Shared Variables Introduction RW-sequence Tracing and Replay Implementation IssuesAdvanced Topics in Software Engineering 16Tracing and ReplayDuring program tracing, a RW-sequence is recorded for each shared variable.During program replay, we make sure that each read/write operation reads/writes the same version of shared variable as recorded in a RW-sequence.Advanced Topics in Software Engineering 17InstrumentationRead and write operations are instrumented by adding routines to control the start and end of the operation:startRead(x)read the value of xendRead(x)readstartWrite(x)write the value of xendWrite(x)writeAdvanced Topics in Software Engineering 18startRead & endReadstartRead (x)if (mode == trace) {++ x.activeReaders;RWSeq.record(ID, x.version);}else {readEvent r = RWSeq.nextEvent (ID);myVersion = r.getVersion ();while (myVersion != x.version) delay;}endRead (x)++ x.totalReaders;-- x.activeReaders;Advanced Topics in Software Engineering 19startWrite & endWritestartWrite (x)if (mode == trace) {while (x.activeReaders > 0) delay;RWSeq.record(ID, x.version, x.totalReaders);}else {writeEvent w = RWSeq.nextEvent (ID);myVersion = w.getVersion ();while (myVersion != x.version) delay;myTotalReaders = w.getTotalReaders ();while (x.totalReaders < myTotalReaders) delay;}endWrite (x)x.totalReaders == 0;++ x.version;Advanced Topics in Software Engineering 20CREWIf two or more readers read a particular version during tracing, then they must read the same version during replay, but these read operations can be in any order.In our solution, readers are only partially ordered with respect to write operations, while write operations are totally ordered for each shared variable.This is known as Concurrent Reading and Exclusive Writing (CREW) policy.Advanced Topics in Software Engineering 21C++ ImplementationThe course pack has shown a template class sharedVariable that can be used to trace and replay C++ programs.The only change involved is to wrap each variable as an instance of sharedVariable.int turn; sharedVariable<int> turn;Advanced Topics in Software Engineering 22Java ImplementationMore changes are necessary for Java programs, due to the lack of the features of template class and operator overloading. However, such changes can be made automatically, without leaving developers with too much