Shared variables in threaded C programs 15 213 The course that gives CMU its Zip Programming with Threads Dec 6 2001 Question 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 Topics Shared variables The need for synchronization Synchronizing with semaphores Synchronizing with mutex and condition variables Thread safety and reentrancy Races and deadlocks class29 ppt class29 ppt Threads memory model Conceptual model Each thread runs in the context of a process Each thread has its own separate thread context Thread ID stack stack pointer program counter condition codes and general purpose registers All threads share the remaining process context Code data heap and shared library segments of the process virtual address space 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 class29 ppt 3 CS 213 F 01 2 CS 213 F 01 Example of threads accessing another thread s stack 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 class29 ppt thread routine void thread void vargp int myid int vargp static int cnt 0 printf d s cnt d n myid ptr myid cnt Peer threads access main thread s stack indirectly through global ptr variable 4 CS 213 F 01 Mapping variables to memory instances Global var 1 instance ptr data Which variables are shared 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 class29 ppt thread routine void thread void vargp int myid int vargp static int cnt 0 printf d s cnt d n myid ptr myid cnt Referenced by main thread Referenced by peer thread 0 Referenced by peer thread 1 ptr cnt 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 Local static var 1 instance cnt data 5 unsigned int cnt 0 shared NULL NULL NULL NULL CS 213 F 01 thread routine void count void arg int i for i 0 i NITERS i cnt return NULL class29 ppt if cnt unsigned NITERS 2 printf BOOM cnt d n cnt else printf OK cnt d n cnt 7 6 CS 213 F 01 Assembly code for counter loop C code for counter loop Corresponding asm code gcc O0 fforce mem for i 0 i NITERS i ctr L9 movl 4 ebp eax cmpl 99999999 eax jle L12 jmp L10 Head Hi linux badcnt BOOM ctr 198841183 Pthread join tid1 NULL Pthread join tid2 NULL class29 ppt Variable instance ptr cnt and msgs are shared i and myid are NOT shared badcnt c An improperly synchronized threaded program int main pthread t tid1 tid2 Pthread create tid1 count Pthread create tid2 count Shared variable analysis Load ctr Li Update ctr Ui Store ctr Si linux badcnt BOOM ctr 198261801 L12 movl ctr eax leal 1 eax edx movl edx ctr Load Update Store L11 linux badcnt BOOM ctr 198269672 ctr should be equal to 200 000 000 What went wrong CS 213 F 01 movl 4 ebp eax leal 1 eax edx movl edx 4 ebp jmp L9 Tail Ti L10 class29 ppt 8 CS 213 F 01 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 ctr 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 class29 ppt 9 i thread instri eax1 eax2 ctr 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 OK class29 ppt CS 213 F 01 10 Concurrent execution cont A progress graph depicts the discrete execution state space of concurrent threads Thread 2 instri 1 1 2 2 2 2 1 1 1 2 H1 L1 H2 L2 U2 S2 U1 S1 T1 T2 eax1 eax2 ctr 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 H2 We can clarify our understanding of concurrent execution with the help of the progress graph class29 ppt 11 CS 213 F 01 CS 213 F 01 Progress graphs How about this ordering i thread Oops H1 L1 class29 ppt U1 S1 T1 Thread 1 12 E g L1 S2 denotes state where thread 1 has completed L1 and thread 2 has completed S2 CS 213 F 01 Trajectories in progress graphs 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 L2 L U and S form a critical section with respect to the shared variable cnt T2 Instructions in critical sections wrt to some shared variable should not be interleaved S2 critical section wrt cnt Unsafe region U2 Sets of states where such interleaving occurs form unsafe regions L2 H2 H2 H1 L1 U1 S1 Thread 1 T1 H1 L1 U1 S1 T1 Thread 1 critical section wrt cnt class29 ppt 13 CS 213 F 01 Safe and unsafe trajectories class29 ppt 14 CS 213 F 01 Synchronizing with semaphores Question How can we guarantee a safe trajectory Thread 2 We must synchronize the threads so that they never enter an unsafe state T2 Safe trajectory S2 critical section wrt cnt Unsafe trajectory Unsafe region Def A trajectory is safe iff it doesn t touch any part of an unsafe region Claim A trajectory is correct wrt cnt iff it is safe U2 L2 H2 H1 L1 U1 S1 T1 Thread 1 semaphore non negative integer synchronization variable P …
View Full Document
Unlocking...