Today’s AgendaTracing/Replay/Testing for MonitorsEntry-based ExecutionEntry-based Execution (cont’d)Simple M-sequenceSimple M-sequence (cont’d)ExampleTracing/Replay (SU)enterMonitorControlTracing/Replay (SC)waitCSlide 13Regression TestingRegression Testing (cont’d)A simple M-sequence is insufficient…Still insufficient …M-sequenceM-sequence (cont’d)ExampleFeasibility DeterminationSlide 22Slide 23signalC & exitMonitorSlide 25releaseMPermitIt is undecidable ...TimeoutwatchDogSlide 30Feasible SequencesValid SequencesCorrectnessSynchronization FaultComputational FaultSynchronization or Computation Fault?Slide 37Example (cont’d)Slide 39Slide 40Today’s AgendaHW #3 Replay MonitorAdvanced Topics in Software Engineering 1Advanced Topics in Software Engineering 2Tracing/Replay/Testing for Monitors Simple M-sequences M-sequences Correctness and FaultsAdvanced Topics in Software Engineering 3Entry-based ExecutionWe assume that (1) all shared variables are accessed inside a monitor; and (2) the only source of non-determinism in a program is due to uncertainty with thread scheduling.The executions of such a program is referred to as entry-based executions, as their behaviors are determined by the order in which the threads enter/reentry the monitor.Advanced Topics in Software Engineering 4Entry-based Execution (cont’d)An entry-based execution can be replayed if the order in which threads (re)enter the monitor is repeated.Advanced Topics in Software Engineering 5Simple M-sequenceA simple M-sequence can be used to replay a program’s execution during debugging.The synchronization events in a simple M-sequence depend on the type of monitors being used.Advanced Topics in Software Engineering 6Simple M-sequence (cont’d)A simple M-sequence for an SC monitor consists of the following two types of synchronization events: (1) entry into the monitor by a new thread; and (2) reentry into the monitor by a signaled thread.A simple M-sequence for an SU monitor consists of the only type of synchronization event: entry into the monitor by a new thread.An event in a simple M-sequence is denoted by the identifier (ID) of the thread that executed the event.Advanced Topics in Software Engineering 7Example Consider the bounded buffer monitor. Assume there is a single Producer thread (with ID 1) and a single Consumer thread (with ID 2). With SC monitor, a possible simple M-sequence is (2,1,2,1,1,2,2).The equivalent M-sequence with SU monitor is (2,1,1,1,2,2).Advanced Topics in Software Engineering 8Tracing/Replay (SU)In MonitorSU, mutex controls entry into the monitor.During execution, enterMonitor is modified to send entry event to a control monitor, which records the event into a trace file.To replay a simple M-sequence, a thread requests an entry permit from the control monitor to enter the monitor, and releases the permit to allow the next one to enter.Advanced Topics in Software Engineering 9enterMonitorpublic void enterMonitor () {if (replayMode) control.requestEntryPermit (ID);mutex.P ();if (replayMode)control.releasentryPermit ();elsecontrol.traceMonitorEntry (ID);}Advanced Topics in Software Engineering 10Controlclass Control extends MonitorSC () {Control () {}public void requestEntryPermit (int ID) {enterMonitor ();if (ID != ((Integer) simpleMSequence.elementAt(index)).intValue()) {threads[ID].waitC ();}exitMonitor ();}public void releaseEntryPermit () {enterMonitor ();if (index < simpleMSequence.size() – 1) {++ index;threads[((Integer) simpleMSequence.elementAt(index)).intValue()].signalC(); }exitMonitor ();}public void traceMonitorEntry (int ID) { // record ID in trace file }public void traceMonitorReEntry (int ID) { … }private vector simpleMSequences;private ConditionVariable[] threads;private int index = 1;}Advanced Topics in Software Engineering 11Tracing/Replay (SC)Tracing/Replay for SC monitor needs to record the reentry event, in addition to the entry event.Besides enterMonitor, waitC method also needs to be modified.Advanced Topics in Software Engineering 12waitCpublic void waitC () {numWaitingThreads ++;threadQue.VP (mutex);if (replayMode) control.requestEntryPermit (ID);mutex.P ();if (replayMode)control.releaseEntryPermit ();elsecontrol.traceMonitorReEntry (ID);}Advanced Topics in Software Engineering 13Tracing/Replay/Testing for Monitors Simple M-sequences M-sequences Correctness and FaultsAdvanced Topics in Software Engineering 14Regression TestingWhen a failure is detected during an execution, we want to replay the execution, perhaps for many times, to locate the fault that has caused the failure.After the fault is located, the program is then modified to correct the fault.Regression testing must be performed to ensure that the fault has been corrected and no new faults were introduced.Advanced Topics in Software Engineering 15Regression Testing (cont’d)Regression testing requires that we determine whether or not a particular SYN-sequence is feasible. (This is different from the replay problem. Why?)A SYN-sequence may represent an illegal behavior that was observed when the program failed. In this case, the sequence is expected to be infeasible. If the SYN-sequence represents a legal behavior, then the sequence is expected to remain feasible during RT.Advanced Topics in Software Engineering 16A simple M-sequence is insufficient…Consider a program that contains an SU monitor for a two-slot buffer. Assume that there is a single producer (Thread 1) and a single consumer (Thread 2). A possible simple M-sequence is (1,1,1,2,2,2).During replay, a thread always execute the same method as it did in the original execution. However, during RT, this is no longer true (why?).Advanced Topics in Software Engineering 17Still insufficient …Now we get a new M-sequence:((1, deposit), (1, deposit), (1, deposit), (2, withdraw), (2, withdraw))If the third item was actually deposited, then the first item was lost. However, if the third deposit operation was actually blocked in full.wait, then the program still behaves correctly.Advanced Topics in Software Engineering 18M-sequenceA complete M-sequence consists of the following types of events: the entry of a monitor method and, for SC monitors, the reentry of a monitor the exit of a monitor method the start of execution of a wait operation the start of execution of a signal, or signalAndExit, or signalAll operation.Advanced Topics in Software Engineering 19M-sequence