Concurrent and Distrib Systems
Concurrent and Distrib Systems CS 475
Popular in Course
Popular in ComputerScienence
This 12 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 475 at George Mason University taught by Richard Carver in Fall. Since its upload, it has received 49 views. For similar materials see /class/215114/cs-475-george-mason-university in ComputerScienence at George Mason University.
Reviews for Concurrent and Distrib Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
310 Tracing Testing and Replay for Semaphores and Locks Outline I A technique for detecting violations of mutual exclusion I Tracing and replaying executions during debugging I Deadlock detection I Reachability testing 3101 NonDeterministic Testing with the Lockset Algorithm Recall from Chapter 1 that a data race is a failure to correctly implement critical sections for nonatomic shared variable accesses A concurrent program can be tested for data races I monitor shared variable accesses and make sure that each variable has been properly locked before it is accessed I execute the program several times with the same test input in order to increase our chances of finding dam races This type of testing is called nondaerministic test39mg Nondeterministic testing of a concurrent program CP involves the following steps 1 Select a set of inputs for CP 2 For each selected input X execute CP with X many times and examine the result of each execution The purpose of nondeterministic testing is to exercise as many behaviors as possible I Unfortunately experiments have shown that programs tend to exhibit the same behavior from execution to execution I Also probe effect see Section 17 may make it impossible for some failures to be observed To increase the likelihood of exercising different behaviors change the scheduling algorithm used by the operating system e g change the value of the time quantum that is used for roundrobin scheduling insert Sleept statements into the program with the sleep amount I randomly chosen Executing a Sleep statement forces a context switch and thus indirectly affects thread scheduling We have implemented the second technique as an execution option for programs that use a 1 v the binarySemaphore and T 39 in nu library When this option is specified Sleep smtements are executed at the beginning of methods P V lock and unlock To detect data races we combine nondeterministic testing with the lockset algorithm checks that all shared variables follow a consistent locking discipline in which every shared variable is protected by a lock for each variable we determine if there is some lock that is always held whenever the variable is accessed For shared variable v let the set CandidateLockshx be those locks that have protected v during the execution so far Thus a lock l is in CandidateLoccYW if during the execution so far every thread that has accessed v was holding l at the moment of access CandidateLockshx is computed as follows I When a new variable v is initialized its candidate set is considered to hold all possible locks I When v is accessed on a read or write operation by T CandidateLocksv is refined The new value of CandidateLockshx is the intersection of CandidateLockshx and the set of locks held by thread T Based on this refinement algorithm I if some lock I consistently protects v it will remain in CandidateLoccYW as CandidateLockrv is refined I if CandidateLocksv becomes empty it indicates that there is no lock that consistently protects v Locks et Algorithm Let LocksHeld T denote the set of locks currently held by thread T For each shared variable v initialize CandidateLocksv to the set of all locks On each read or write access to v by thread T CandidateLockYW CandidateLocksv LocksHeldT if CandidateLocksv 0 issue a warning In Fig 330 Threadl s access of shared variable s is protected first by mutexl then by mutexZ This violation of mutual exclusion can be detected by the lockset algorithm I CandidateLockrs is initialized to mutexl mutexZ and is refined as s is accessed I When Thread locks mutexl LocksHeMThreadI becomes mutexl I When s is accessed in the first assignment smtement CandidateLockrs becomes mutexl which is the intersection of sets CandidateLockss and LocksHeMThreadl I When the second assignment smtement is executed Thread holds lock mutexZ and the only candidate lock of s is mutexl I After the intersection of CandidateLockss and LocksHeMThreadI CandidateLockrs becomes empty The lockset algorithm has detected that no lock consistently protects shared variable 5 We have implemented the lockset algorithm in the mutexLock class and in the C sharedVariable class template that was presented in Chapter 2 I We assume that threads can access a sharedVariable only after it is initialized Thus no refinement is performed during initialization ie in the constructor of sharedVariable Readonly variables can be accessed without locking This means that warnings are issued only after a variable has been initialized and has been accessed by at least one write operation I The refinement algorithm can be turned off to eliminate false alarms For example a bounded buffer is shared by Producer and Consumer threads but no locks are needed Even so when this program is executed a warning will be issued by the lockset algorithm As a nondeterministic testing technique the lockset algorithm cannot prove that a program is free from dam races 3102 Simple SYNsequences for Semaphores and Locks We can characterize an execution of a concurrent program as a sequence of synchronization events on synchronization objects A sequence of synchronization events is called a SYNsequence There are several ways to define a SYNsequence and the definition of a SYNsequence has an affect on the design of a replay solution and vice versa Let CP be a concurrent program that uses shared variables semaphores and locks The result of executing CP with a given input depends on the unpredictable order in which the shared variables semaphores and locks in CF are accessed I The semaphores are accessed using P and V operations I The locks are accessed using lock and unlock operations I The shared variables are accessed using read and write operations 2 The synchronization objects in CF are its shared variables semaphores and locks The synchronization events in CF are executions of readwrite PV and lockunlock operations on these objects A SYNsequence for a shared variable v is a sequence of read and write operations on v ReadWritesequences for shared variables were defined in Chapter 2 A SYNsequence for a binarySemuphore or count39mgSemuphore s is a sequence of events of the following types I completion of a P operation I completion of a Voperation I start of a P operation that is never completed due to a deadlock or an exception start of a V operation that is never completed due to a deadlock or an exception We refer to such a sequence as a PVsequence of s An event in a PVsequence is denoted by the identifier ID of the thread that executed the P or V operation The order in which threads complete their P and V operations is not necessarily the same as the order in which they call P and Vor even the same as the order in which the P and V operations start For the operations that are completed it is their order of completion that must be replayed since this order determines the result of the execution We will also replay the starts of operations that do not complete so that the same events exceptions and deadlocks will occur during replay A SYNsequence for a mutexLock l is a sequence of events of the following types I completion of a lock operation I completion of an unlock operation I start of a lock operation that is never completed due to a deadlock or an exception I start of an unlock operation that is never completed due to a deadlock or an exception We refer to such a sequence as aLockUnlocksequence of l An event in a LockUnlock sequence is denoted by the identifier ID of the thread that executed the lock or unlock operation Example Consider the simple program in Listing 331 The final value of shared variable x is either 1 or 2 binarySemaphore mutex1 Thread1 hr mutexP1 mutexP x l mutexV mutexP error should be mutexV Listing 331 Illustrating ReadWritesequences and PVsequences A possible ReadWrite sequence of shared variable x is 1 0 0 2 1 0 from Ch 2 the format is thread Dversion numbertoml readers This denotes thatx was first accessed by Thread 1 and then by Thread 2 Since Thread1 accessed x first the PVsequence for mutex must be 1 1 2 2 indicating that Thread1 performed its P and Voperations before Thread2 The second P operation in Thread2 is an error This P operation will start but not complete and should be a V operation instead A SYNsequence for concurrent program CP is a collection of ReadWritesequences PV sequences and LockUnlocksequences There is one sequence for each shared variable semaphore and lock in the program A SYNsequence for the program in Listing 331 contains a ReadWritesequence for x and a PVsequence for mutex ReadWritesequence of x 100 210 PVsequence of mutex 1 1 2 2 This is a partial ordering of the events ie the events on a single object are totally ordered but the order of events among different objects is not specified A SYNsequence can also be a single tomllyordered sequence of synchronization events over all the synchronization objects A totallyordered sequence of events that is consistent with the above partiallyordered sequence is 1 1 0 0 1 2 2 1 0 2 In general there may be two or more totallyordered sequences that are consistent with a given partial ordering since two concurrent events can appear in the totalordering in either order The definition of a SYNsequence is intended to capture what it means for one execution to replay another Suppose that when the program above is executed I Thread2 executes mutexP and blocks because Thread1 is in its critical section I During replay of this execution assume Thread2 executes its first mutgxP operation without blocking because Thread1 has already executed its mutexP and mulgx V operations I These two executions are not identical but are they close enough In both executions I the sequence of completed P and V operations is the same I the final value ofx is 2 Thus we consider the second execution to replay the first 3103 Tracing and Replaying Simple PVsequences and LockUnlocksequences 31031 Modifying Methods P0 and V0 Tracing the identifier of the thread that completes a call to method sP or s V is recorded and saved to a trace file for s Replay we assume that each semaphore has a permit called a PVpermit I A thread must hold a semaphore s PVpermit before it executes a P0 or V operation on that semaphore I The order in which threads receive a semaphore s PVpermit is based on the PV sequence that is being replayed I A thread requests and releases a semaphore s PVpermit by calling methods requestPermitO and releasePermitO void P0 if replayMode controlrequestPermitD code to lock this semaphore appears here if replayMode controlreleasePermit rest of body ofP if traceMode controltraceCompletePD code to unlock this semaphore appears here public final void V if replayMode controlrequestPermitD code to lock this semaphore appears here if replayMode controlreleasePermit rest of body of V I if traceMode controltraceCompleteVD code to unlock this semaphore appears here 31032 Modifying Methods lockO and unlockO The implemenmtions of methods lock and unlock in class mutexLock are modified just like methods P and V I Class mutexLock contains calls to requestPermitO and releasePermitO before and after respectively the lock operation in mutexLock I Calls to traceCompleteLockO and traceCompleteUnlockO appear at the end of their respective critical sections Deadlocks and exceptions I When deadlock producing operations are replayed the calling threads will not be blocked inside the body of the operation rather they will be blocked forever on the call to requestPermitO before the operation I Events involving exceptions that occur during the execution of a P V lock or unlock operation are not replayed But the trace would indicate that the execution of these operations would raise an error which is probably enough help to debug the program 31033 Class control Each semaphore and lock is associated with a control object I Replay mode the control object inputs the simple SYNsequence of the semaphore or lock and handles the calls to requestPermit and releasePermit I Trace mode the control object collects the synchronization events that occur and records them in a trace file When a thread calls requestPermitO or one of the trace methods it passes its identifier ID Class TDThread in Chapter 1 handles the creation of unique thread IDs A C control class is shown in Listing 332 When the control object for a semaphore s is created it reads the simple PVsequence for s into vector SYNsequence Method requestPPermit Threads that try to execute an operation out of turn are delayed in method requestPPermit on a separate semaphore in the Threads array A thread uses its ID to determine which semaphore in the Threads array to wait on Method releasePPermit increments index to allow the next operation in the SYNsequence to occur If the thread that is to perform the next entry is blocked in requestPPermit it is awakened class control public control input integer IDs into SYNsequence initialize arrays threads and hasRequested void requestPermitint ID mutexloc 0 if ID I SYNsequenceindex thread D should execute next event hasRequestedD true No set flag to remember D s request mutexunlock threadsDP wait for permission hasRequestedD false reset flag and exit requestPermit else mutexunlock Yes exit requestPermit void releasePermit mutexlock index if index lt SYNsequencesize Are there more events to replay Has the next thread already requested permission if hasRequestedSYNsequenceindex threadsSYNsequenceindexVO Yes wake it up mutexunlock void traceCompletePint ID record integer D void traceCompleteVID record integer D private PVsequence or LockUnlocksequence a sequence of integer IDs vector SYNsequence binarySemaphore threads all semaphores are initialized to O hasReqaested is true if Thread i is delayed in requestPermit init to false bool hasRequested int index O SYNsequenceindex is D of next thread to execute an event mutexLock mutex note no tracing or replay is performed for tth lock Listing 332 C Class control for replaying PVsequences and LockUnlocksequences To illustrate the operation of the controller consider a corrected version of the simple program in Listing 331 Thread1 ThreadZ mutexP1 mutexP X 1 mutexV mutexV Assume that the PVsequence traced during an execution of this program is 1 1 2 2 Suppose that Thread2 tries to execute matexP first and thus calls requestPermit2 before Thread1 calls requestPermitI blocks itself in requestPermitO by executing Threads2P When Thread1 eventually calls requestPermitI it will be allowed to exit requestPemit and execute its matexP operation and checks whether the thread that is to execute the next PV operation already has already called requestPermit The next thread is SYNseqamceH which is 1 Thread1 has not called requestPermitO for the next operation so nothing further happens in releasePermitO Eventually Thread1 calls requestPermitI to request permission to execute its matexV operation Thread1 receives permission executes matexV and calls releasePermitO next PV operation is Thread2 Thread 2 having already called requestPermit is still blocked on its call to Threads2P This is indicated by the value of hasReqaested2 which is true Thus releasePermitO calls Threads2V This allows Thread2 to exit requestPermitO and perform its matexP operation Thread 2 will eventually request and receive permission for its matex V operation completing the replay Since the value of index is O and the value of SYNseqaence ndex is 1 not 2 ThreadZ Thread1 will then call releasePermitO Method releasePermitO increments index to 1 Method releasePermitO increments index to 2 and finds that the thread to execute the 3104 Deadlock Detection In Chapter 2 we defined a deadlock as a situation in which one or more threads become blocked forever Let CP be a concurrent program conmining threads that use semaphores and locks for synchronization Assume there is an execution of CP that exercises a SYNsequence S and at the end of S there exists a thread T that satisfies these conditions I T is blocked due to the execution of a P V or lock statement I T will remain blocked forever regardless of what the other threads will do Thread T is said to be deadlocked at the end of S and CP is said to have a deadlock A deadlock in CP is a global deadlock if every thread in CP is either blocked or completed otherwise it is a local deadlock In operating systems processes request resources eg printers and files and enter a waitsmte if the resources are held by other processes If the requested resources can never become available then the processes can never leave their waitsmte and a deadlock DCCUIS The information about which process is waiting for a resource held by which other process can be represented by a waitfor graph I an edge in a waitfor graph from node P to P1 indicates that process P is waiting for process P1 to release a resource that P needs I a deadlock exists in the system if and only if the waitfor graph contains a cycle periodically invoke an algorithm that searches for cycles in the waitfor graph Deadlock detection using waitfor graphs is not always applicable to concurrent programs A thread blocked in a P operation for example does not know which of the other threads can unblock it and thus the waitfor relation among the threads is unknown Another approach Assume that a deadlock occurs if all of the threads in a program are permanently blocked Assume also that all of the threads are expected to terminate To detect deadlocks mainmin a count of the threads that have not completed their mn methods and a count of the blocked threads and compare the two counts I The numThreads counter is incremented when a thread starts its mn method and decremented when a thread completes its mn method I The blockedThreads counter is incremented when a thread blocks in a P V or lock operation and decremented when a thread is unblocked during a V or unlocld operation The blockedThreads counter should also be maintained in other blocking methods such as join I If the numThreads and blockedThreads counters are ever equal and nonzero then all of the threads are blocked and we assume that a deadlock has occurred This approach can be used to detect global deadlocks but not local deadlocks since it requires all nondeadlocked threads to be completed This approach is implemented in the synchronization classes but the implementation is incomplete I the blockedThreads counter is not modified inside the join method I the numThreads counter is not modofoed when the main thread starts and completes simply because there is no convenient and transparent way to do so I Since the main thread is not included in numThreads and the status of the main thread is unknown it is possible for the numThreads and blockedThreads counters to become temporarily equal indicating that a deadlock has occurred and then for more threads to be created and start running Thus it is not known for sure that a deadlock has occurred when the counters are equal To handle the uncertainty about deadlock the numThreads and blockedThreads counters are compared only after no synchronization events have been generated for some period of time indicating that all the threads are blocked or completed or that running threads are stuck in infinite loops ie livelocked Smtus information is displayed when a deadlock is detected The events leading to a deadlock can be traced and replayed using the methods described earlier Deadlock detected philosopher3 blocked on operation P0 of semaphore chopstick 4 philosopher2 blocked on operation P0 of semaphore chopstick 3 l l philosopher4 blocked on operation P0 of semaphore chopstickO philosopherl blocked on operation P0 of semaphore chopstick2 l philosopherO blocked on operation P0 of semaphore chopstick 1 Some waitfor relations among threads can be captured by waitfor graphs I a thread blocked in a lock operation knows that the thread that owns the lock can unblock it Thus the waitfor relation among threads and locks is known when one thread tries to lock two locks in one order while another thread tries to lock them in reverse order a deadlock may occur such a deadlock will be indicated by a cycle in the waitfor graph A deadlock detection utility has been incorporated into the Java HotSpot VM This utility is invoked by typing Ctrl for Linux or the Solaris Operating Environment or CtrlPauseBreak for Microsoft Windows on the command line while an application is running If the application is deadlocked because two or more threads are involved in a cycle to acquire locks then the list of threads involved in the deadlock is displayed This utility will not find deadlocks involving one or more threads that are permanently blocked in a monitor see Chapter 4 waiting for a notification that never comes which is similar to the situation where a thread is blocked in a P operation waiting for a V operation that will never come 3105 Reachability Testing for Semaphores and Locks Nondeterministic testing is easy to carry out but it can be very inefficient It is possible that some behaviors will be exercised many times while others will not be exercised at all For Solution 1 to the dining philosophers problem with five philosophers no deadlock was detected during 100 executions after inserting random delays deadlocks were detected in eighteen out of one hundred executions for ten philosophers deadlocks were detected in only four out of one hundred executions As the number of threads increases and thus the total number of possible behaviors increases it apparently becomes harder to detect deadlocks with nondeterministic testing Furthermore the instrumenmtion added to perform tracing and deadlock detection may create a probe effect that prevents some failures from being observed Reachability testing allows us to examine all the behaviors of a program or at least as many different behaviors as is practical in a systematic manner By systematic we mean that a given SYNsequence is exercised only once and it is possible to know when all the SYNsequences have been exercised Reachability testing combines nondeterministic testing and program replay During reachability testing the SYNsequence exercised by a nondeterministic execution is traced as usual I The execution trace captures the behavior that actually happened The trace is also carefully defined so that it captures alternate behaviors that could have happened but didn t These alternate behaviors are called race variants of the trace Replaying a race variant ensures that a different behavior is observed during the next test execution Fig 333a shows a portion of an execution trace for the dining philosophers program Philosoperl and Philosopher race to pick up chopstick with Philosopher completing its P operation on chopstick2 before Philosopher can complete its P operation Philosopher and Philosopher share chopstick2 which lies between them MU 5 ka Phil M M W Phlll drugstlc l m complete P c P complete call 39 P u complete complete V call can V rnmnlere Can p c n t P call a b In general there is a race between calls to P or V operations on the same semaphore if these calls could be completed in a different order during another execution with the same input Fig 333b shows a race variant of the execution in Fig 333a I In this race variant Philosopher wins the race to chopstick2 and picks it up before Philosopher can grab it I The dashed arrow indicates thatPhilosopherl s P operation on chopstick2 was called but not completed in the race variant This call will be completed in an execution that replays the variant In general a race variant represents the beginning portion of a SYNsequence Reachability testing uses replay to make sure that the events in the race variant are exercised and then lets the execution continue nondeterministically so that a complete sequence can be traced There may be many complete SYNsequences that have a given race variant at the beginning I One of these sequences will be captured in the nondeterministic portion of the execution I The complete traced sequence can then be analyzed to derive more race variants which can be used to generate more traces and so on When replay is applied to the race variant in Fig 333b I Philosopher and Philosopher will both pick up their left chopsticks which is part of the deadlock scenario in which all the philosophers hold their left chopstick and are waiting for their right While the complete deadlock scenario may not occur immediately reachability testing ensures that every possible PVsequence of the dining philosophers program will eventually be exercised and thus that the deadlock will eventually be detected Table 32 shows the results of applying reachability testing to three Java programs I BB is the bounded buffer program from Listing 36 with multiple producers and CDHSUITIBI S DPl and DP4 are solutions 1 and 4 of the dining philosophers problem in Listing 37 and Listing 38 respectively Recall that program DPl has a deadlock I RW is the readers and writers program from Listing 311 The threads in these programs deposit withdraw read write or eat one time The second column shows the configuration of each program 1 For BB it indicates the number of producers P the number of consumers C and the number of slots S in the buffer 2 For RW it indicates the number of readers R and the number of writers W 3 For DP it indicates the number of philosophers P The third column shows the number of PVsequences generated during reachability testing The total reachability testing time for the DP4 program with 5 philosophers is 15 minutes on a 16GHz PC with 512 MB of RAM Observations about Table 32 1 There is only one possible sequence for program BB with one producer and one consumer There are six P and V operations exercised during an execution of BB why aren t there more sequences a Reachability testing exercises all of the partially ordered PVsequences of BB not all of the totally ordered sequences That is in a given execution trace if events E1 and E2 are concurrent and E1 appears before E2 then no race variant is generated to cover the case where the order of E1 and E2 is reversed 3 Reachability testing considers only sequences of compl ed P and V operations While there are many different orders in which the producer and consumer threads can start their P and V operations there is only one order in which they can complete these operations 2 Program DP1 with five philosophers has a total of 31 sequences one of which results in a deadlock For DP1 with 10 philosophers there is one deadlock sequence out of 1023 possible sequences 3 The number of sequences exercised during reachability testing grows quickly as the number of threads increases a It may be impractical to exercise all of the sequences let alone to manually inspect the output of all the test executions L7 Reachability testing does not have to be applied exhaustively rather it can stop when a selected coverage criterion is satisfied 4 Exercising every PVsequence may be more effort than is really required a Some race variants are created simply by reversing the order of two V operations But such variants are not very interesting since the order of the V operations has no effect on the rest of the execution Ignoring these and similar types of variants I The number of sequences for BB with 3P 3C drops from 9252 to 36 I The number of sequences for BB with 2P 2C drops from 132 to 4 L7 Reachability testing with three Producers will exercise all the possible orders in which the three Producers can deposit their items Producerl Producerz Producers Prodocerz Producerl Producers Producers Producerz Producerl etc But the Producers all execute the same code and their behavior is independent of their IDs so this batch of variants is not very interesting If you use the symmetry of the threads to ignore these duplicate variants I The number of sequences for BB with 3P 3C drops from 36 to 4 I The number of sequences for BB with 2P 2C drops from 4 to 2 or perhaps even lower see Exercise 75 These numbers are in line with the numbers we would likely come up with if we tried to generate sequences manually 3106 Putting it all Together 31061 Tracing and Replaying ClWin32lPthreads Programs Class TDThread ensures that threads receive unique thread IDs Tracing replay and analysis are controlled through the values of environment variables MODE and RACEANALYSIS To set tracing on in WindowsDOS execute set MODETRACE Unix setenv MODE TRACE before executing the program To execute random delays during TRACE mode execute the command set RANDOMDELAYON Unix setenv RANDOMDELAY ON This Will enable the execution of Sleep statements at the beginning of methods P V lock and unlock The command set RANDOMDELAYOFF Will turn off random delays and OFF is the default value To turn on deadlock detection during trace mode execute set DEADLOCKDETECTIONON Unix setenv DEADLOCKDETECTION ON The command set DEADLOCKDETECTIONOFF Will turn off deadlock detection and OFF is the default value Dam race detection using the lockset algorithm is enabled by set DATARACEDETECTION ON Unix setenv DATARACEDETECTION ON The command set DATARACEDETECTION OFF Will turn off data race detection and OFF is the default value Environment variable CONTROLLERS is used to determine the number of trace files that Will be created The value SINGLE causes one controller and one trace file to be created set CONTROLLERSSINGLE Unix setenv CONTROLLERS SINGLE The trace file semaphoresreplaytxt Will contain a totallyordered sequence of events for the semaphore and lock objects To create a separate controller for each object Which results in a separate trace file for each object s SYNsequence use the value MULTIPLE set CONTROLLERSMULTIPLE Unix setenv CONTROLLERS MULTIPLE The default value for the number of controllers is SINGLE An execution is replayed by setting the MODE to REPLAY and executing the program set MODEREPLAY Unix setenv MODE REPLAY The value of CONTROLLERS must be the same during tracing and replay No data race detection or random delays are performed during replay Reachability testing is performed by setting the MODE to RT and customizing the driver process in file RTDrivercpp Which is part of the synchronization library Directions for customizing the driver process are in the file
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'