CS 105 Tour of the Black Holes of Computing Programming with Threads Topics Threads Shared variables The need for synchronization Synchronizing with semaphores Thread safety and reentrancy Races and deadlocks Traditional View of a Process Process process context code data and stack Process context Program context Data registers Condition codes Stack pointer SP Program counter PC Code data and stack stack SP shared libraries brk run time heap read write data Kernel context VM structures File descriptor table brk pointer 2 PC read only code data 0 CS 105 Alternate View of a Process Process thread code data and kernel context Thread main thread Code and Data shared libraries SP stack Thread context Data registers Condition codes Stack pointer SP Program counter PC brk run time heap read write data PC read only code data 0 Kernel context VM structures File descriptor table brk pointer 3 CS 105 A Process With Multiple Threads Multiple threads can be associated with a process Each thread has its own logical control flow sequence of PC values Each thread shares the same code data and kernel context Each thread has its own thread id TID Thread 1 main thread Shared code and data Thread 2 peer thread shared libraries stack 1 run time heap read write data Thread 1 context Data registers Condition codes SP1 PC1 4 read only code data 0 Kernel context VM structures File descriptor table brk pointer stack 2 Thread 2 context Data registers Condition codes SP2 PC2 CS 105 Logical View of Threads Threads associated with a process form pool of peers Unlike processes which form tree hierarchy Threads associated with process foo Process hierarchy P0 T2 T4 T1 P1 shared code data and kernel context sh T5 5 T3 sh sh foo bar CS 105 Concurrent Thread Execution Two threads run concurrently are concurrent if their logical flows overlap in time Otherwise they are sequential same rule as for processes Examples Thread A Concurrent A B A C Sequential B C Thread B Thread C Time 6 CS 105 Threads vs Processes How threads and processes are similar Each has its own logical control flow Each can run concurrently Each is context switched How threads and processes are different Threads share code and data processes typically do not Threads are somewhat cheaper than processes Process control creating and reaping is twice as expensive as thread control Linux Pentium III numbers 20K cycles to create and reap a process 10K cycles to create and reap a thread 7 CS 105 Posix Threads Pthreads Interface Pthreads Standard interface for 60 functions that manipulate threads from C programs Creating and reaping threads pthread create pthread join Determining your thread ID pthread self Terminating threads pthread cancel pthread exit exit terminates all threads return terminates current thread Synchronizing access to shared variables pthread mutex init pthread mutex un lock pthread cond init pthread cond timed wait 8 CS 105 The Pthreads hello world Program hello c Pthreads hello world program include csapp h Thread attributes usually NULL void howdy void vargp int main pthread t tid Pthread create tid NULL howdy NULL Pthread join tid NULL exit 0 thread routine void howdy void vargp printf Hello world n return NULL 9 Thread arguments void p return value void p CS 105 Execution of Threaded hello world main thread call Pthread create Pthread create returns call Pthread join main thread waits for peer thread to terminate peer thread printf return NULL peer thread terminates Pthread join returns exit terminates main thread and any peer threads 10 CS 105 Pros and Cons of Thread Based Designs Threads take advantage of multicore multi CPU H W Easy to share data structures between threads E g logging information file cache Threads are more efficient than processes Unintentional sharing can introduce subtle and hardto reproduce errors 11 Ease of data sharing is greatest strength of threads Also greatest weakness CS 105 Shared Variables in Threaded C Programs Question Which variables in a threaded C program are shared variables Answer not as simple as global variables are shared and stack variables are private Requires answers to the following questions 12 What is the memory model for threads How are variables mapped to memory instances How many threads reference each of these instances CS 105 Threads Memory Model Conceptual model Each thread runs in larger 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 remaining process context Code data heap and shared library segments of process virtual address space Open files and installed handlers Operationally this model is not strictly enforced Register values are truly separate and protected But any thread can read and write the stack of any other thread Mismatch between conceptual and operational model is a source of confusion and errors 13 CS 105 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 14 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 CS 105 Mapping Vars to Mem Instances 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 15 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 CS 105 Shared Variable Analysis Which variables are shared 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 16 ptr svar and msgs are shared i and myid are NOT shared CS 105 badcnt c An Improperly Synchronized Threaded Program unsigned int cnt 0 shared int main pthread t tid1 tid2 Pthread create tid1 count Pthread create tid2 count NULL NULL NULL NULL Pthread join
View Full Document
Unlocking...