badcnt c An Improperly Synchronized Threaded Program 15 213 The course that gives CMU its Zip shared volatile unsigned int cnt 0 define NITERS 100000000 Synchronization November 19 2008 int main pthread t tid1 tid2 Pthread create tid1 count Pthread create tid2 count Topics NULL NULL NULL NULL linux badcnt BOOM cnt 198841183 linux badcnt BOOM cnt 198261801 Pthread join tid1 NULL Pthread join tid2 NULL Synchronizing with semaphores Races and deadlocks Thread safety and reentrancy if cnt unsigned NITERS 2 printf BOOM cnt d n cnt else printf OK cnt d n cnt lecture 24 ppt linux badcnt BOOM cnt 198269672 cnt should be equal to 200 000 000 What went wrong 2 Assembly Code for Counter Loop Key idea In general any sequentially consistent interleaving is possible but some are incorrect Corresponding asm code Ii denotes that thread i executes instruction I eaxi is the contents of eax in thread i s context L9 movl 4 ebp eax cmpl 99999999 eax jle L12 jmp L10 Head Hi L12 Load cnt Li Update cnt Ui Store cnt Si movl cnt eax leal 1 eax edx movl edx cnt Load Update Store L11 movl 4 ebp eax leal 1 eax edx movl edx 4 ebp jmp L9 Tail Ti 15 213 F 08 Concurrent Execution C code for counter loop for i 0 i NITERS i cnt L10 3 thread routine void count void arg int i for i 0 i NITERS i cnt return NULL 4 15 213 F 08 Page 1 i thread instri eax1 eax2 cnt 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 OK 15 213 F 08 Concurrent Execution cont Concurrent Execution cont Incorrect ordering two threads increment the counter but the result is 1 instead of 2 How about this ordering i thread instri eax1 eax2 cnt 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 5 Oops A progress graph depicts the discrete execution state space of concurrent threads U2 L2 H2 7 Thread 1 A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads S2 Example U2 Each point corresponds to a possible execution state Inst1 Inst2 T1 cnt 15 213 F 08 T2 Each axis corresponds to the sequential order of instructions in a thread S2 S1 eax2 Thread 2 L1 S2 U1 eax1 Trajectories in Progress Graphs Thread 2 L1 H1 L1 H2 L2 U2 S2 U1 S1 T1 T2 6 Progress Graphs H1 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 15 213 F 08 T2 i thread H1 L1 U1 H2 L2 S1 T1 U2 S2 T2 L2 E g L1 S2 denotes state where thread 1 has completed L1 and thread 2 has completed S2 H2 H1 8 15 213 F 08 Page 2 L1 U1 S1 T1 Thread 1 15 213 F 08 Critical Sections and Unsafe Regions Thread 2 T2 Unsafe region critical section wrt cnt Sets of states where such interleaving occurs form unsafe regions L2 L1 U1 S1 T1 Claim A trajectory is correct wrt cnt iff it is safe U2 H2 Thread 1 H1 L1 U1 S1 T1 Thread 1 critical section wrt cnt critical section wrt cnt 9 Unsafe trajectory Unsafe region Def A trajectory is safe iff it doesn t touch any part of an unsafe region L2 H2 H1 Safe trajectory S2 Instructions in critical sections wrt to some shared variable should not be interleaved S2 U2 Thread 2 L U and S form a critical section with respect to the shared variable cnt T2 critical section wrt cnt Safe and Unsafe Trajectories 10 15 213 F 08 15 213 F 08 Semaphores Locking with Semaphores Question How can we guarantee a safe trajectory Here is one way we could use P and V operations to synchronize the threads that update cnt We must synchronize the threads so that they never enter an unsafe state Semaphore used like this referred to as a lock Classic solution Dijkstra s P and V operations on semaphores Semaphore s is initially 1 semaphore non negative integer synchronization variable Thread routine void count void arg int i P s while s 0 wait s Dutch for Proberen test V s s Dutch for Verhogen increment for i 0 i NITERS i P s cnt V s return NULL 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 11 12 15 213 F 08 Page 3 15 213 F 08 Safe Sharing With Locks Wrappers on POSIX Semaphores Thread 2 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 V s Forbidden region 1 S2 0 U2 L2 P s 0 0 0 0 1 1 1 1 1 1 1 1 Unsafe region 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 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 Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s initially set to 1 T2 P operation on semaphore sem void P sem t sem if sem wait sem unix error P Semaphore invariant creates a forbidden region that encloses unsafe region and is never touched by any trajectory V operation on semaphore sem void V sem t sem if sem post sem unix error V H2 1 H1 P s L1 U1 S1 V s T1 Initially s 1 Thread 1 13 14 15 213 F 08 Sharing With POSIX Semaphores properly sync d counter program include csapp h define NITERS 10000000 create 2 threads and wait if cnt unsigned NITERS 2 printf BOOM cnt d n cnt else printf OK cnt d n cnt exit 0 A race occurs when the correctness of the program depends on one thread reaching point x before another thread reaches point y for i 0 i NITERS i P sem cnt V sem return NULL int main pthread t tid1 tid2 Sem init sem 0 1 sem 1 One worry races thread routine void count void arg int i volatile unsigned int cnt sem t sem semaphore a threaded program with a race int main pthread t tid N int i for i 0 i N i Pthread create tid i NULL thread i for …
View Full Document
Unlocking...