Page 1SynchronizationNovember 19, 2008Topics Synchronizing with semaphores Races and deadlocks Thread safety and reentrancylecture-24.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, F’08badcnt.c: An Improperly Synchronized Threaded Program/* shared */volatile unsigned int cnt = 0;#define NITERS 100000000 int main() {pthread_t tid1, tid2;Pthread_create(&tid1, NULL, count, NULL);Pthread_create(&tid2, NULL, count, NULL);Pthread_join(tid1, NULL);Pthread_join(tid2, NULL);if (cnt != (unsigned)NITERS*2)printf("BOOM! cnt=%d\n", cnt);elseprintf("OK cnt=%d\n", cnt);}/* thread routine */void *count(void *arg) {int i;for (i=0; i<NITERS; i++)cnt++;return NULL;}linux> ./badcntBOOM! cnt=198841183linux> ./badcntBOOM! cnt=198261801linux> ./badcntBOOM! cnt=198269672cnt should beequal to 200,000,000. What went wrong?!– 3 –15-213, F’08Assembly Code for Counter Loop.L9:movl -4(%ebp),%eaxcmpl $99999999,%eaxjle .L12jmp .L10.L12:movl cnt,%eax # Loadleal 1(%eax),%edx # Updatemovl %edx,cnt # Store.L11:movl -4(%ebp),%eaxleal 1(%eax),%edxmovl %edx,-4(%ebp)jmp .L9.L10:Corresponding asm code for (i=0; i<NITERS; i++)cnt++;C code for counter loopHead (Hi)Tail (Ti)Load cnt (Li)Update cnt (Ui)Store cnt (Si)– 4 –15-213, F’08Concurrent ExecutionKey idea: In general, any sequentially consistent interleaving is possible, but some are incorrect! Iidenotes that thread i executes instruction I %eaxiis the contents of %eax in thread i’s contextH1L1U1S1H2L2U2S2T2T11111222221-011-----10001111222i (thread)instricnt%eax1OK-----1222-%eax2Page 2– 5 –15-213, F’08Concurrent Execution (cont)Incorrect ordering: two threads increment the counter, but the result is 1 instead of 2.H1L1U1H2L2S1T1U2S2T21112211222-01--11---0000011111i (thread)instricnt%eax1----0--111%eax2Oops!– 6 –15-213, F’08Concurrent Execution (cont)How about this ordering?H1L1H2L2U2S2U1S1T1T21122221112i (thread)instricnt%eax1%eax2We can clarify our understanding of concurrentexecution with the help of the progress graph– 7 –15-213, F’08Progress GraphsA progress graph depictsthe discrete execution state space of concurrentthreads.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 L1and thread2 has completed S2.H1L1U1S1T1H2L2U2S2T2Thread 1Thread 2(L1, S2)– 8 –15-213, F’08Trajectories in Progress GraphsA trajectory is a sequence of legal state transitions that describes one possible concurrent execution ofthe threads.Example:H1, L1, U1, H2, L2, S1, T1, U2, S2, T2H1L1U1S1T1H2L2U2S2T2Thread 1Thread 2Page 3– 9 –15-213, F’08Critical Sections and Unsafe RegionsL, U, and S form a critical section withrespect to the sharedvariable cnt.Instructions in criticalsections (wrt to someshared variable) should not be interleaved.Sets of states where suchinterleaving occursform unsafe regions.H1L1U1S1T1H2L2U2S2T2Thread 1Thread 2Unsafe regioncritical section wrt cntcritical section wrt cnt– 10 –15-213, F’08Safe and Unsafe TrajectoriesDef: A trajectory is safeiff it doesn’t touch any part of an unsafe region.Claim: A trajectory is correct (wrt cnt) iff it issafe.H1L1U1S1T1H2L2U2S2T2Thread 1Thread 2Unsafe regionUnsafetrajectorySafe trajectorycritical section wrt cntcritical section wrt cnt– 11 –15-213, F’08SemaphoresQuestion: How can we guarantee a safe trajectory? We must synchronize the threads so that they never enter an unsafe state.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 sSemaphore invariant: (s >= 0)– 12 –15-213, F’08Locking with SemaphoresHere is one way we could use P and V operations to synchronize the threads that update cnt Semaphore used like this referred to as a “lock”/* Semaphore s is initially 1 *//* Thread routine */void *count(void *arg){int i;for (i=0; i<NITERS; i++) {P(s);cnt++;V(s);}return NULL;}Page 4– 13 –15-213, F’08Forbidden regionSafe Sharing With LocksProvide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphores (initially set to 1).Semaphore invariant creates a forbidden regionthat encloses unsafe region and is never touched by any trajectory.H1P(s) V(s) T1Thread 1Thread 2L1U1S1H2P(s)V(s)T2L2U2S2Unsafe region110000111100001100-1 -1 -1 -10000-1 -1 -1 -10000-1 -1 -1 -10000-1 -1 -1 -1001100001111000011Initiallys = 1– 14 –15-213, F’08Wrappers on 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");}/* 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");}– 15 –15-213, F’08Sharing With POSIX Semaphores/* properly sync’d counter program */#include "csapp.h"#define NITERS 10000000volatile unsigned int cnt; sem_t sem; /* semaphore */int main() {pthread_t tid1, tid2;Sem_init(&sem, 0, 1); /* sem=1 *//* create 2 threads and wait */...if (cnt != (unsigned)NITERS*2)printf("BOOM! cnt=%d\n", cnt);elseprintf("OK cnt=%d\n", cnt);exit(0);}/* thread routine */void *count(void *arg){int i;for (i=0; i<NITERS; i++) {P(&sem);cnt++;V(&sem);}return NULL;}Warning:It’s really slow!– 16 –15-213, F’08One worry: racesA race occurs when the correctness of the program depends on one thread reaching point x before another thread reaches point y/* 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 (i = 0; i < N; i++)Pthread_join(tid[i], NULL);exit(0);}/* thread routine */void *thread(void *vargp) {int myid = *((int *)vargp);printf("Hello from thread %d\n", myid);return NULL;}Page 5– 17 –15-213, F’08Race EliminationMake sure don’t have unintended sharing of state/* a threaded program with a race */int main() {pthread_t tid[N];int i;for (i = 0; i < N; i++) {int *valp =
View Full Document
Unlocking...