Programming with ThreadsApril 29, 2004Topics Shared variables The need for synchronization Synchronizing with semaphores Thread safety and reentrancy Races and deadlocksclass29.ppt15-213“The course that gives CMU its Zip!”–2–15-213, S’04Shared Variables in Threaded C ProgramsQuestion: Which variables in a threaded C program are shared variables? The answer is not as simple as “global variables are shared”and “stack variables are private”.Requires answers to the following questions: What is the memory model for threads? How are variables mapped to memory instances? How many threads reference each of these instances?–3–15-213, S’04Threads Memory ModelConceptual model: Each thread runs in the context of a process. Each thread has its own separate thread context.z Thread ID, stack, stack pointer, program counter, condition codes, and general purpose registers. All threads share the remaining process context.z Code, data, heap, and shared library segments of the process virtual address space.z Open files and installed handlersOperationally, this model is not strictly enforced: While register values are truly separate and protected.... Any thread can read and write the stack of any other thread. Mismatch between the conceptual and operation model is a source of confusion and errors.–4–15-213, S’04Example of Threads Accessing Another Thread’s Stackchar **ptr; /* global */int main(){int i;pthread_t tid;char *msgs[N] = {"Hello from foo","Hello from bar"};ptr = msgs;for (i = 0; i < 2; i++)Pthread_create(&tid, NULL, thread, (void *)i);Pthread_exit(NULL);}/* thread routine */void *thread(void *vargp){int myid = (int)vargp;static int svar = 0;printf("[%d]: %s (svar=%d)\n", myid, ptr[myid], ++svar);}Peer threads access main thread’s stackindirectly through global ptr variable–5–15-213, S’04Mapping Variables to Mem. Instanceschar **ptr; /* global */int main(){int i;pthread_t tid;char *msgs[N] = {"Hello from foo","Hello from bar"};ptr = msgs;for (i = 0; i < 2; i++)Pthread_create(&tid, NULL, thread, (void *)i);Pthread_exit(NULL);}/* thread routine */void *thread(void *vargp){int myid = (int)vargp;static int svar = 0;printf("[%d]: %s (svar=%d)\n", myid, ptr[myid], ++svar);}Global var: 1 instance (ptr [data])Local static var: 1 instance (svar [data])Local automatic vars: 1 instance (i.m, msgs.m )Local automatic var: 2 instances (myid.p0[peer thread 0’s stack],myid.p1[peer thread 1’s stack])–6–15-213, S’04Shared Variable AnalysisWhich variables are shared?Variable Referenced by Referenced by Referenced byinstance main thread? peer thread 0? peer thread 1?ptr yes yes yessvar no yes yesi.m yes no nomsgs.m yes yes yesmyid.p0 no yes nomyid.p1 no no yesAnswer: A variable x is shared iff multiple threads reference at least one instance of x. Thus: ptr, svar, and msgs are shared. i and myid are NOT shared.–7–15-213, S’04badcnt.c: An Improperly Synchronized Threaded Programunsigned int cnt = 0; /* shared */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?!–8–15-213, S’04Assembly 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(gcc -O0 -fforce-mem) for (i=0; i<NITERS; i++)cnt++;C code for counter loopHead (Hi)Tail (Ti)Load cnt (Li)Update cnt (Ui)Store cnt (Si)–9–15-213, S’04Concurrent ExecutionKey idea: In general, any sequentially consistent interleaving is possible, but some are incorrect! Iidenotes that thread i executes instruction I %eaxi is the contents of %eax in thread i’s contextH1L1U1S1H2L2U2S2T2T11111222221-011-----10001111222i (thread)instricnt%eax1OK-----1222-%eax2–10–15-213, S’04Concurrent 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!–11–15-213, S’04Concurrent Execution (cont)How about this ordering?H1L1H2L2U2S2U1S1T1T21122221112i (thread)instricnt%eax1%eax2We can clarify our understanding of concurrentexecution with the help of the progress graph–12–15-213, S’04Progress 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)–13–15-213, S’04Trajectories 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 2–14–15-213, S’04Critical 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–15–15-213, S’04Safe 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–16–15-213, S’04SemaphoresQuestion: 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.z P(s): [ while (s == 0) wait(); s--; ]» Dutch for "Proberen" (test)z V(s): [ s++; ]» Dutch for "Verhogen" (increment) OS
View Full Document