A version of badcnt c with a simple counter loop 15 213 The course that gives CMU its Zip Concurrency II Synchronization Nov 14 2000 int ctr 0 shared note counter should be equal to 200 000 000 main routine creates two count threads linux badcnt BOOM ctr 198841183 count thread void count void arg int i Topics for i 0 i NITERS i ctr return NULL Progress graphs Semaphores Mutex and condition variables Barrier synchronization Timeout waiting What went wrong class23 ppt Assembly code for counter loop 2 CS 213 F 00 Concurrent execution Key thread idea In general any sequentially consistent interleaving is possible but some are incorrect C code for counter loop Corresponding asm code gcc O0 fforce mem for i 0 i NITERS i ctr L9 Ii denotes that thread i executes instruction I eaxi is the contents of eax in thread i s context movl 4 ebp eax cmpl 99999999 eax jle L12 jmp L10 Head Hi L12 movl ctr eax Load leal 1 eax edx Update movl edx ctr Store L11 movl 4 ebp eax leal 1 eax edx movl edx 4 ebp jmp L9 Tail Ti L10 class23 ppt linux badcnt BOOM ctr 198269672 class23 ppt Load ctr Li Update ctr Ui Store ctr Si linux badcnt BOOM ctr 198261801 3 CS 213 F 00 class23 ppt i thread instri eax1 eax2 ctr 1 1 1 1 2 2 2 2 2 1 H1 L1 U1 S1 H2 L2 U2 S2 T2 T1 0 1 1 1 1 2 2 2 0 0 0 1 1 1 1 2 2 2 4 OK CS 213 F 00 Concurrent execution cont Incorrect ordering two threads increment the counter but the result is 1 instead of 2 i thread instri eax1 eax2 ctr 1 1 1 2 2 1 1 2 2 2 H1 L1 U1 H2 L2 S1 T1 U2 S2 T2 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 class23 ppt 5 Oops CS 213 F 00 Concurrent execution cont How about this ordering L1 S2 S2 Each axis corresponds to the sequential order of instructions in a thread U2 H2 O O H1 class23 ppt L1 U1 S1 T1 Thread 1 7 eax1 class23 ppt eax2 ctr 6 CS 213 F 00 Interleaved concurrent execution one processor or Parallel concurrent execution multiple processors Each point corresponds to a possible execution state Inst1 Inst2 L2 H1 L1 H2 L2 U2 S2 U1 S1 T1 T2 Legal state transitions A progress graph depicts the discrete execution state space of concurrent threads T2 instri 1 1 2 2 2 2 1 1 1 2 We can clarify our understanding of concurrent execution with the help of the progress graph Progress graphs Thread 2 i thread E g L1 S2 denotes state where thread 1 has completed L1 and thread 2 has completed S2 CS 213 F 00 or or parallel execution Key point Always reason about concurrent threads as if each thread had its own CPU class23 ppt 8 CS 213 F 00 Critical sections and unsafe regions Trajectories Thread 2 A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads Thread 2 T2 S2 Example U2 H1 L2 U1 H2 L2 S1 T1 U2 S2 T2 L2 L U and S form a critical section with respect to the shared variable ctr T2 Unsafe region S2 critical section wrt shared variable ctr Instructions in critical sections wrt to some shared variable should not be interleaved U2 L2 Sets of states where such interleaving occurs form unsafe regions H2 H2 O O O O H1 L1 U1 S1 T1 H1 L1 U1 S1 T1 Thread 1 Thread 1 critical section wrt shared variable ctr class23 ppt 9 class23 ppt CS 213 F 00 10 Safe trajectories Unsafe trajectories Thread 2 Unsafe region S2 critical section U2 Claim Any safe trajectory results in a correct value for the shared variable ctr L2 H2 O O T2 Touching a state of type y may or may not be OK Unsafe region critical section S2 y y y U2 x x y L2 x x correct because store completes before load incorrect because order of load and store are indeterminate y H2 H1 L1 U1 S1 T1 O O Thread 1 critical section class23 ppt Touching a state of type x is always incorrect Thread 2 Def A safe trajectory is a sequence of legal transitions that does not touch any states in an unsafe region T2 11 CS 213 F 00 H1 L1 U1 S1 T1 Thread 1 Moral be conservative and disallow all unsafe trajectories critical section CS 213 F 00 class23 ppt 12 CS 213 F 00 Sharing with semaphores Semaphore operations Question How can we guarantee a safe trajectory We must synchronize the threads so that they never enter an unsafe state T2 Classic solution Dijkstra s P and V operations on semaphores semaphore non negative integer synchronization variable P s while s 0 wait s Dutch for Proberen test V s s Dutch for Verhogen increment OS guarantees that operations between brackets are executed indivisibly Only one P or V operation at a time can modify s When while loop in P terminates only that P can decrement s Semaphore invariant s 0 s 1 s 0 s 1 V s ctr s 0 s 1 forbidden s 0 region 13 Semaphore invariant creates a forbidden region that encloses unsafe region and is never touched by any trajectory P s H2 O O s 1 H1 s 0 s 1 P s ctr V s Initially s 1 class23 ppt Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s initially set to 1 Thread 2 T1 Thread 1 class23 ppt CS 213 F 00 Semaphore used in this way is often called a mutex mutual exclusion 14 CS 213 F 00 Sharing with Posix semaphores Posix semaphores initialize semaphore sem to value pshared 0 if thread pshared 1 if process void Sem init sem t sem int pshared unsigned int value if sem init sem pshared value 0 unix error Sem init goodcnt c properly synch d version of badcnt c include ics h define NITERS 10000000 P operation on semaphore sem void P sem t sem if sem wait sem unix error P struct shared ctr int ctr sem t mutex semaphore shared counter thread void count void arg int i for i 0 i NITERS i P shared mutex shared ctr V shared mutex return NULL void count void arg int main pthread t tid1 tid2 V operation on semaphore sem void V sem t sem if sem post sem unix error V init mutex semaphore to 1 Sem init shared mutex 0 1 create 2 ctr threads and wait class23 ppt 15 CS 213 F 00 class23 ppt 16 CS 213 F 00 Progress graph for goodcnt c Deadlock Thread 2 Thread 2 deadlock state V s V m forbidden region for s f r P m Any trajectory that enters the …
View Full Document
Unlocking...