Concurrency II: Synchronization Nov 14, 2000Topics• Progress graphs• Semaphores• Mutex and condition variables• Barrier synchronization• Timeout waitingclass23.ppt15-213“The course that gives CMU its Zip!”CS 213 F’00– 2 –class23.pptA version of badcnt.c witha simple counter loopint ctr = 0; /* shared */ /* main routine creates*//* two count threads *//* count thread */void *count(void *arg) { int i; for (i=0; i<NITERS; i++) ctr++; return NULL;}linux> badcntBOOM! ctr=198841183linux> badcntBOOM! ctr=198261801linux> badcntBOOM! ctr=198269672note: counter should beequal to 200,000,000What went wrong?CS 213 F’00– 3 –class23.pptAssembly code for counter loop.L9:movl -4(%ebp),%eaxcmpl $99999999,%eaxjle .L12jmp .L10.L12:movl ctr,%eax # Loadleal 1(%eax),%edx # Updatemovl %edx,ctr # Store.L11:movl -4(%ebp),%eaxleal 1(%eax),%edxmovl %edx,-4(%ebp)jmp .L9.L10:Corresponding asm code(gcc -O0 -fforce-mem)for (i=0; i<NITERS; i++) ctr++;C code for counter loopHead (Hi)Tail (Ti)Load ctr (Li)Update ctr (Ui)Store ctr (Si)CS 213 F’00– 4 –class23.pptConcurrent executionKey thread idea: In general, any sequentially consistentinterleaving is possible, but some are incorrect!• Ii denotes that thread i executes instruction I• %eaxi is the contents of %eax in thread i’s contextH1L1U1S1H2L2U2S2T2T11111222221-011-----10001111222i (thread)instrictr%eax1OK-----1222-%eax2CS 213 F’00– 5 –class23.pptConcurrent execution (cont)Incorrect ordering: two threads increment the counter,but the result is 1 instead of 2.H1L1U1H2L2S1T1U2S2T21112211222-01--11---0000011111i (thread)instrictr%eax1----0--111%eax2Oops!CS 213 F’00– 6 –class23.pptConcurrent execution (cont)How about this ordering?H1L1H2L2U2S2U1S1T1T21122221112i (thread)instrictr%eax1%eax2We can clarify our understanding of concurrentexecution with the help of the progress graphCS 213 F’00– 7 –class23.pptProgress graphsA progress graph depictsthe discrete execution state space of concurrent threads.Each axis corresponds tothe sequential order ofinstructions in a thread.Each point corresponds toa possible execution state(Inst1, Inst2).E.g., (L1, S2) denotes statewhere thread 1 hascompleted L1 and thread2 has completed S2.H1L1U1S1T1H2L2U2S2T2Thread 1Thread 2(L1, S2)(O,O)CS 213 F’00– 8 –class23.pptLegal state transitionsInterleaved concurrent execution (one processor):orParallel concurrent execution (multiple processors)or orKey point: Always reason about concurrent threads asif each thread had its own CPU.(parallel execution)CS 213 F’00– 9 –class23.pptTrajectoriesA trajectory is a sequence of legal state transitions that describes one possible concurrent execution ofthe threads.Example:H1, L2, U1, H2, L2, S1, T1, U2, S2, T2H1L1U1S1T1H2L2U2S2T2Thread 1Thread 2(O,O)CS 213 F’00– 10 –class23.pptH1L1U1S1T1H2L2U2S2T2Thread 1Thread 2(O,O)Critical sections and unsafe regionsL, U, and S form a critical section withrespect to the sharedvariable ctr.Instructions in criticalsections (wrt to someshared variable) should not be interleaved.Sets of states where suchinterleaving occursform unsafe regions.critical section wrt shared variable ctrcritical sectionwrtsharedvariablectrUnsafe regionCS 213 F’00– 11 –class23.pptSafe trajectoriesH1L1U1S1T1H2L2U2S2T2Thread 1Thread 2(O,O)critical sectioncritical sectionDef: A safe trajectory is a sequence of legal transitions that does nottouch any states in anunsafe region.Claim: Any safe trajectory results in a correct value for the shared variable ctr.Unsafe regionCS 213 F’00– 12 –class23.pptUnsafe trajectoriesH1L1U1S1T1H2L2U2S2T2Thread 1Thread 2(O,O)critical sectioncritical sectionUnsafe regionTouching a state of type xis always incorrect.Touching a state of type ymay or may not be OK:xxx xyyyyycorrect becausestore completesbefore load.incorrect becauseorder of load andstore areindeterminate.Moral: be conservativeand disallow all unsafe trajectories.CS 213 F’00– 13 –class23.pptSemaphore operationsQuestion: How can we guarantee a safe trajectory?• We must synchronize the threads so that they never enter an unsafestate.Classic solution: Dijkstra's P and V operations onsemaphores.• 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 executedindivisibly.–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)CS 213 F’00– 14 –class23.ppts = 0s = 1s = 1s = 0Sharing with semaphoresH1P(s)ctr++;V(s) T1H2P(s)ctr++;V(s)T2Thread 1Thread 2(O,O)s = -1(forbiddenregion)s = 0s = 0 s = 1Initially, s = 1s = 1Provide mutuallyexclusive access toshared variable bysurrounding criticalsection with P and Voperations on semaphores (initially set to 1).Semaphore invariantcreates a forbidden regionthat encloses unsaferegion and is nevertouched by any trajectory.Semaphore used in thisway is often called amutex (mutual exclusion).CS 213 F’00– 15 –class23.pptPosix 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");}/* P operation on semaphore sem */void P(sem_t *sem) { if (sem_wait(sem)) unix_error("P");}/* V operation on semaphore sem */void V(sem_t *sem) { if (sem_post(sem)) unix_error("V");}CS 213 F’00– 16 –class23.pptSharing with Posix semaphores/* goodcnt.c - properly synch'd *//* version of badcnt.c */#include <ics.h>#define NITERS 10000000void *count(void *arg);struct { int ctr; /* shared ctr */ sem_t mutex; /* semaphore */} shared;int main() { pthread_t tid1, tid2; /* init mutex semaphore to 1 */ Sem_init(&shared.mutex, 0, 1); /* create 2 ctr threads and wait */ ...}/* counter thread */void *count(void *arg) { int i; for (i=0; i<NITERS; i++) { P(&shared.mutex); shared.ctr++; V(&shared.mutex); } return NULL;}CS 213 F’00– 17 –class23.pptProgress graph for goodcnt.cP(m)Thread 1Initially, mutex = 1P(m)Thread 2V(m)P(m) V(m) P(m) V(m)V(m)P(m)V(m)P(m)V(m)f.r.f.r.f.r.CS 213 F’00– 18 –class23.pptdeadlockregionDeadlockP(s) V(s)V(t)Thread 1Thread 2Initially, s=t=1P(t)P(t) V(t)forbiddenregion for sforbiddenregion for tP(s)V(s)deadlockstateSemaphores
View Full Document
Unlocking...