Shared Variables in Threaded C Programs 15 213 The course that gives CMU its Zip Question Which variables in a threaded C program are shared variables Synchronization December 6 2006 Requires answers to the following questions Topics Shared variables The need for synchronization Synchronizing with semaphores Thread safety and reentrancy Races and deadlocks The answer is not as simple as global variables are shared and stack variables are private class26 ppt What is the memory model for threads How are variables mapped to memory instances How many threads reference each of these instances 15 213 F 06 2 Example of Threads Accessing Another Thread s Stack Threads Memory Model Conceptual model Multiple threads run within the context of a single process Each thread has its own separate thread context char ptr 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 handlers Operationally 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 3 15 213 F 06 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 4 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 stack indirectly through global ptr variable 15 213 F 06 Mapping Variables to Mem Instances Shared Variable Analysis Global var 1 instance ptr data Local automatic vars 1 instance i m msgs m char 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 Local automatic var 2 instances myid p0 peer thread 0 s stack myid p1 peer thread 1 s stack thread routine void thread void vargp int myid int vargp static int svar 0 printf d s svar d n myid ptr myid svar Local static var 1 instance svar data 15 213 F 06 badcnt c An Improperly Synchronized Threaded Program shared volatile unsigned int cnt 0 define NITERS 100000000 NULL NULL NULL NULL Pthread join tid1 NULL Pthread join tid2 NULL if cnt unsigned NITERS 2 printf BOOM cnt d n cnt else printf OK cnt d n cnt 7 thread routine void count void arg int i for i 0 i NITERS i cnt return NULL Variable instance Referenced by main thread Referenced by peer thread 0 Referenced by peer thread 1 ptr svar i m msgs m myid p0 myid p1 yes no yes yes no no yes yes no yes yes no yes yes no yes no yes Answer A variable x is shared iff multiple threads reference at least one instance of x Thus 5 int main pthread t tid1 tid2 Pthread create tid1 count Pthread create tid2 count Which variables are shared ptr svar and msgs are shared i and myid are NOT shared 15 213 F 06 6 Assembly Code for Counter Loop C code for counter loop for i 0 i NITERS i cnt Corresponding asm code L9 movl 4 ebp eax cmpl 99999999 eax jle L12 jmp L10 Head Hi linux badcnt BOOM cnt 198841183 L12 Load cnt Li Update cnt Ui Store cnt Si linux badcnt BOOM cnt 198261801 movl cnt eax leal 1 eax edx movl edx cnt Load Update Store L11 linux badcnt BOOM cnt 198269672 cnt should be equal to 200 000 000 What went wrong 15 213 F 06 movl 4 ebp eax leal 1 eax edx movl edx 4 ebp jmp L9 Tail Ti L10 8 15 213 F 06 Concurrent Execution Concurrent Execution cont Key idea In general any sequentially consistent interleaving is possible but some are incorrect Incorrect ordering two threads increment the counter but the result is 1 instead of 2 Ii denotes that thread i executes instruction I eaxi is the contents of eax in thread i s context 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 Concurrent Execution cont instri 1 1 2 2 2 2 1 1 1 2 H1 L1 H2 L2 U2 S2 U1 S1 T1 T2 eax2 cnt 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 Oops 15 213 F 06 Beware of Optimizing Compilers Code From Book define NITERS 100000000 eax1 eax2 Generated Code cnt movl movl L6 leal decl movl jns movl shared counter variable unsigned int cnt 0 thread routine void count void arg int i for i 0 i NITERS i cnt return NULL We can clarify our understanding of concurrent execution with the help of the progress graph 11 eax1 H1 L1 U1 H2 L2 S1 T1 U2 S2 T2 10 How about this ordering i thread instri 1 1 1 2 2 1 1 2 2 2 OK 15 213 F 06 9 i thread 15 213 F 06 12 Global variable cnt shared between threads Multiple threads could be trying to update within their iterations cnt ecx 99999999 eax 1 ecx edx eax edx ecx L6 edx cnt Compiler moved access to cnt out of loop Only shared accesses to cnt occur before loop read or after write What are possible program outcomes 15 213 F 06 Controlling Optimizing Compilers Revised Book Code A progress graph depicts the discrete execution state space of concurrent threads Thread 2 define NITERS 100000000 Generated Code shared counter variable volatile unsigned int cnt 0 thread routine void count void arg int i for i 0 i NITERS i cnt return NULL Progress Graphs Declaring variable as volatile forces it to be kept in memory movl L15 movl incl decl movl jns 99999999 edx cnt eax eax edx eax cnt L15 T2 L1 S2 Each axis corresponds to the sequential order of instructions in a thread S2 U2 Each point corresponds to a possible execution state Inst1 Inst2 L2 Shared variable read and written each iteration H2 H1 15 213 F 06 13 Trajectories in Progress Graphs L1 U1 S1 Thread 1 T1 E g L1 S2 denotes state where thread 1 has completed L1 and thread 2 has completed S2 15 213 F 06 14 Critical Sections and Unsafe Regions Thread 2 Thread 2 A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads T2 S2 Example U2 H1 L1 U1 H2 L2 S1 T1 U2 S2 T2 L U and S form a critical section with respect to the shared variable cnt T2 Instructions …
View Full Document
Unlocking...