Parallel Programming CPSC 390
Popular in Course
verified elite notetaker
Popular in ComputerScienence
verified elite notetaker
This 11 page Class Notes was uploaded by Ashlee Volkman on Monday October 12, 2015. The Class Notes belongs to CPSC 390 at Ferris State University taught by James Nystrom in Fall. Since its upload, it has received 38 views. For similar materials see /class/221615/cpsc-390-ferris-state-university in ComputerScienence at Ferris State University.
Reviews for Parallel Programming
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
Getting Started With POSIX Threads Tom Wagner Don Towsley Department of Computer Science University of Massachusetts at Amherst July 19 1995 1 Introduction What is a thread and What is it good for Threads are often called lightweight processes and while this term is somewhat of an over simpli cation it is a good starting point Threads are cousins to UNIX processes though they are not processes themselves To understand the distinction we must examine the relation between UNIX processes and Mach tasks and threads In UNIX a process contains both an executing program and a bundle of resources such as the le descriptor table and address space In Mach a task contains only a bundle of resources threads handle all execution activities A Mach task may have any number of threads associated with it and all threads must be associated with some task All threads associated with a given task share the tasks resources Ihus a thread is essentially a program counter a stack and a set of registers all the other data structures belong to the task A UNIX process in Mach is modeled as a task with a single thread Since threads are very small compared with processes thread creation is relatively cheap in terms of CPU costs As processes require their own resource bundle and threads share resources threads are likewise memory frugal Mach threads give programmers the ability to write concurrent applications that run on both uniprocessor and multiprocessor machines transparently taking advantage of the additional processors when they exist Additionally threads can increase 1 f in a 391 39 when the application performs operations that are likely to block or cause delays such le or socket 10 In the following sections we discuss portions of the POSIX threads standard and its speci c implementation in the DEC OSFl OS V30 POSIX threads are called pthreads and are similar to the nonPOSIX cthreads 2 Hello World Now that the formalities are over with lets jump right in The pthreadcreate function creates a new thread It takes four arguments a thread variable or holder for the thread a thread attribute the function for the thread to call when it starts execution and an argument to the function For example pthreadt athread pthreadattrt athreadattribute void threadfunctionvoid argument char someargument pthreadcreate ampathread athreadattribute void ampthreadfunction void ampsomeargument A thread attribute currently only speci es the minimum stack size to be used In the future thread attributes may be more interesting but for now most applications can get by simply using the default by passing pthreadattrdefault in the thread attribute parameter position Unlike processes created by the UNIX fork function that begin execution at the same point as their parents threads begin their execution at the function speci ed in pthreadcreate The reason for this is clear if threads did not start execution elsewhere we would have multiple threads executing the same instructions with the same resources Recall that processes each have their own resource bundle and threads share theirs Now that we know how to create threads we are ready for our rst application Lets design a multithreaded application that prints the beloved quotHello Worldquot message on stdout First we need two thread variables and we need a lnction for the new threads to call when they start execution We also need some way to specify that each thread should print a different message One approach is to partition the words into separate character strings and to give each thread a different string as its quotstartupquot parameter Take a look at the following code void printmessagefunction void ptr main pthreadt threadl thread2 char messagel quotHelloquot char message2 quotWorldquot pthreadcreate ampthreadl pthreadattrdefault voidampprintmessagefunction void messagel pthreadcreateampthread2 pthreadattrdefault voidampprintmessagefunction void message2 exit0 void printmessagefunction void ptr char message message char ptr printfquots quot message Note the lnction prototype for printmessagefunction and the casts preceding the message arguments in the pthreadcreate call The program creates the rst thread by calling pthreadcreate and passing quotHelloquot as its startup argument the second thread is created with quotWorldquot as its argument When the rst thread begins execution it starts at the printmessagefunction with its quotHelloquot argument It prints quotHelloquot and comes to the end of the lnction A thread terminates when it leaves its initial function therefore the rst thread terminates after printing quotHelloquot When the second thread executes it prints quotWorldquot and likewise terminates While this program appears reasonable there are two major aws First and foremost threads execute concurrently Thus there is no guarantee that the rst thread reaches the printf lnction prior to the second thread Therefore we may see quotWorld Helloquot rather than quotHello Worldquot There is a more subtle point Note the call to exit made by the parent thread1 in the main block If the parent thread executes the exit call prior to either of the child threads executing printf no output will be generated at all This is because the exit function exits the process releases the task thus terminating all threads Any thread parent or child who calls exit can terminate all the other threads along with the process Threads wishing to terminate explicitly must use the pthreadexit function Thus our little hello world program has two race conditions The race for the exit call and the race to see which child reaches the printf call rst Lets x the race conditions with a little crazy glue and duct tape Since we want each child thread to nish before the parent thread lets insert a delay in the parent that will give the children time to reach printf To ensure that the rst child thread reaches printf before the second lets insert a delay prior to the pthreadcreate call that creates the second thread The resulting code is void printmessagefunction void ptr main pthreadt threadl thread2 char messagel quotHelloquot char message2 quotWorldquot pthreadcreate ampthreadl pthreadattrdefault void ampprintmessagefunction void messagel sleeplO pthreadcreateampthread2 pthread attrdefault vo39 id ampprinEmessagefunction void message2 sleeplO exit0 void printmessagefunction void ptr char message message char ptr printfquotsquot message pthreadexit0 Does this code meet our objective Not really It is never safe to rely on timing delays to perform synchronization Because threads are so tightly coupled its tempting to approach them with a less rigorous attitude concerning synchronization but that temptation must be avoided The race condition here is exactly the same situation we have with a distributed application and a shared resource The resource is the standard output and the distributed computing elements are the three threads Thread one must use printfstdout prior to thread two and both must do their business before the parent thread calls exit Beyond our attempt to synchronize using delays we have made yet another blunder The sleep function like the exit function relates to processes When a thread calls sleep the entire process sleeps ie all threads sleep while the process sleeps Thus we have exactly the same situation as we had without the calls to sleep but the program takes twenty seconds longer to run The proper function to use when delaying a thread is pthreaddelaynp np stands for not process For example to delay a thread for two seconds 1 While all threads are equal we shall often refer to the single thread that begins execution with the application the parent thread to distinguish it from later spawned threads which we will refer to as child threads or children 3 struct timespec delay delaytvsec 2 delaytvnsec 0 pthreaddelaynp ampdelay Functions covered in this section pthreadcreate pthreadexit pthreaddelaynp 3 Thread Synchronization POSIX provides two thread synchronization primitives the muteX and the condition variable Mutexes are simple lock primitives that can be used to control access to a shared resource Note that with threads the entire address space is shared so everything can be considered a shared resource However in most cases threads work individually with conceptually private local variables those created within the function called by pthreadcreate and successive functions and combine their efforts through global variables Access to the commonly written items must be controlled Lets create a readerswriters application where a single reader and a single writer communicate using a shared buffer and access is controlled using a muteX void readerfunctionvoid void writerfunctionvoid char buffer int bufferhasitem O pthreadmutext mutex struct timespec delay main pthreadt reader delaytvsec 2 delaytvnsec O pthreadmutexinitampmutex pthreadmutexattrdefault pthreadcreate ampreader pthreadattrdefault voidampreaderfunction NULL writerfunction void writerfunctionvoid whilel pthreadmutexlock ampmutex if bufferhasitem 0 buffer makenewitem bufferhasitem l i pthreadmutexunlock ampmuteX pthreaddelaynp ampdelay void readerfunctionvoid whilel pthreadmutexlock ampmutex if bufferhasitem 1 consumeitem buffer bufferhasitem O pthreadmutexunlock ampmuteX pthreaddelaynp ampdelay In this simple program we assume that the buffer can only hold one item so it is always in one of two states either it has an item or it doesn t The writer rst locks the muteX blocking until it is unlocked if it is already locked then checks to see if the buffer is empty If the buffer is empty it creates a new item and sets the ag buf f erhasitem so that the reader will know the buffer now has an item It then unlocks the muteX and delays for two seconds to give the reader a chance to consume the item This delay is different from our previous delays in that it is only meant to improve program eff1ciency Without the delay the writer will release the lock and in the neXt statement attempt to regain the lock again with the intent of creating another item Its very likely that the reader has not had a chance to consume the item so quickly so the delay is a good idea The reader takes a similar stance It obtains the lock checks to see if an item has been created and if so consumes the item It releases the lock and then delays for a short while giving the writer the chance to create a new item In this example the reader and writer run forever generating and consuming items However if a muteX is no longer needed in a program it should be released using pthreadmutexdestroy ampmuteX Observe that in the muteX initialization function which is required we used the pthread mutexattrdefault as the muteX attribute In OSFl the muteX attribute serves no purpose what so ever so use of the default is strongly encouraged The proper use of mutexes guarantees the elimination of race conditions However the muteX primitive by itself is very weak as it has only two states locked or unlocked The POSIX condition variable supplements mutexes by allowing threads to block and await a signal from another thread When the signal is received the blocked thread is awaken and attempts to obtain a lock on the related muteX Thus signals and mutexes can be combined to eliminate the spinlock problem eXhibited by our readerswriters problem We have designed a library of simple integer semaphores using the pthread muteX and condition variables and will henceforth discus synchronization in that conteXt The code for the semaphores can be found in Appendix A and detailed information about condition variables can be found in the man pages Functions covered in this section pthread mutex init pthread mutexlock pthreadmutexunlock pthreadmutexdestr0y 4 Coordinating Activities With Semaphores Let us revisit our readerswriters program using semaphores We will replace the muteX primitive with the more robust integer semaphore and eliminate the spinlock problem Semaphore operations are semaphoreup semaphoredown semaphoreinit semaphoredestroy and semaphoredecrement The up and down functions conform to traditional semaphore semantics the down operation blocks if the semaphore has avalue less than or equal to zero and the up operation increments the semaphore The init lnction must be called prior to semaphore use and all semaphores are initialized with avalue of one The destroy function releases the semaphore if it is no longer used All functions take a single argument that is a pointer to a semaphore object Semaphore decrement is a nonblocking function that decrements the value of the semaphore It allows threads to decrement the semaphore to some negative value as part of an initialization process We will look at an example that uses semaphoredecrement after the readerswriters program void readerfunctionvoid void writerfunctionvoid char buffer Semaphore writersturn Semaphore readersturn main pthreadt reader semaphoreinit ampreadersturn semaphoreinit ampwritersturn writer must go first semaphoredown ampreadersturn pthreadcreate ampreader pthreadattrdefault vo39 id ampreaderfunction NULL writerfunction void writerfunctionvoid whilel semaphoredown ampwritersturn buffer makenewitem semaphoreup ampreadersturn void readerfunctionvoid whilel semaphoredown ampreadersturn consumeitem buffer semaphoreup ampwritersturn This example still does not fully utilize the power of the general integer semaphore Let us revise the hello world program from Section 2 and X the race conditions using the integer semaphore void printmessagefunction void ptr Semaphore childcounter Semaphore worldsturn main pthreadt threadl thread2 char messagel quotHelloquot char message2 quotWorldquot semaphoreinit ampchildcounter semaphoreinit ampworldsturn semaphoredown ampworldsturn world goes second semaphoredecrement ampchildcounter value now 0 semaphoredecrement ampchildcounter value now 1 childcounter now must be up ed 2 times for a thread blocked on it to be released pthreadcreate ampthreadl pthreadattrdefault void ampprintmessagefunction void messagel semaphoredown ampworldsturn pthreadcreateampthread2 pthreadattrdefault void ampprintmessagefunction void message2 semaphoredown ampchildcounter not really necessary to destroy since we are exiting anyway semaphoredestroy ampchildcounter semaphoredestroy ampworldsturn exit0 void printmessagefunction void ptr char message message char ptr printfquots quot message fflushstdout semaphoreup ampworldsturn semaphoreup ampchildcounter pthreadexit0 Readers can easily satisfy themselves that there are no race conditions in this version of our hello world program and that the words are printed in the proper order The semaphore childcounter is used to force the parent thread to block until both children have executed the printf statement and the following semaphoreup ampchildcounter L Functions covered in this section semaphoreinit semaphoreup semaphoredown semaphoredestroy and semaphoredecrement 5 Pragmatics To compile with pthreads you must include the pthread header le include ltpthread hgt and must link tothep neadhbnuyForexmnpbcc helloworldc o helloworld lpthreads To use the semaphore library you must likewise include its header le and link to the object le or the library The DEC pthreads are based on the POSIX IV threads standard not the POSIX VIII threads standard The 1nction pthreadj oin allows one thread to wait for another to exit While this could be used in the hello world program to determine when the children are done instead of our decrementup semaphore operations the DEC implementation of pthreadj oin has unreliable behavior if the thread object speci ed no longer exists For example in the code below if somethread no longer exists pthreadj oin may cause an error instead of just returning pthreadt somethread void exitsta us pthreadjoin somethread ampexitstatus Other strange errors may occur from functions outside of the thread routines While these errors are few and far between some libraries make quotuniprocessquot assumptions For example we have experienced intermittent dif culties with the buffered stream IO functions fread and f write that can only be attributed to race conditions On the issue of errors though we did not check the return values of the thread calls in our examples to streamline them the return values should be consistently checked Almost all pthread related functions will return 1 on an error For example pthreadt somethread if pthreadcreate ampsomethread 1 perrorquotThread creation errorquot exitl The semaphore library will print a message and exit on erorrs Some useful functions not covered in the examples pthreadyield Informs the scheduler that the thread is willing to yield its quantum requires no arguments pthreadt me me pthreadself Allows a pthread to obtain its own identi er pthreadt thread pthreaddetachthread Informs the library that the threads exit status will not be needed by subsequent pthreadj oin calls resulting in better threads performance For more information consult the library or the man pages eg man k pthreadquot Appendix A Semaphore Library Code File semaphore h include ltstdiohgt include ltpthreadhgt ifndef SEMAPHORES define SEMAPHORES typedef struct Semaphore int V pthreadimutexit mutex pthreadicondit cond Semaphore int semaphoreidown Semaphore s int semaphore up Semaphore s Void semaphoredestroy Semaphore s Void semaphoreiinit Semaphore s int semaphore Value Semaphore s int twipthreadicondisignal pthreadicondit c int twipthreadicondiwait pthreadicondit c pthreadimutexit m int tw pthread mutex unlock pthread mutex t m int twpthreadmutexlock pthreadimutexiti m Void doierror char msg endif File semaphorec include quotsemaphorehquot function must be called prior to semaphore use H handles setu and initialization maphore destroy below should be called when the semaphore is no longer neede V semaphoreiinit Semaphore s segtv 1 if pthreadimutexiinit ampsegtmuteX pthreadimutexattridefault fl doierror quotError setting up semaphore mutexquot if pthreadicondiinit ampsegtcond pthreadicondattridefault fl doierror quotError setting up semaphore condition sign 1quot function should be called when there is no longer a need for the semaphore handles deallocationrelease oid semaphoreidestroy Semaphore s pthreadimutex destroy amps7gtmutex 7 7D doierror quotError destroying semaphore muteXquot if pthreadicondidestroy amps7gtcond if doierror quotError destroying semaphore condition signalquot function increments the semaphore and signals any threads that are blocked waiting a change in the semapho semaphoreiup Semaphore s int yalueiafteriop twipthreadimutexilock amps7gtmuteX s7gty yalueiafteriop s7gty twipthreadimutexiunlock twipthreadicondisignal amp amps7gtmuteX s7gtcond return yalueiafteriop function decrements the semaphore and blocks if the semaphore is lt until another thread signals a change nt semaphoreidown Semaphore a int yalueiafteriop twipthreadimutexilock amps7gtmuteX while s7gty lt twgpthreadicondiwait amps7gtcond amps7gtmutex s7gtV Value fteriop s7gty twipthreadimutexiunlock amps7gtmuteX return yalueiafteriop function does NOT block but simply decrements the semaphore should not be used instead of down on y for programs where multiple threads must up on a semaphore before another thread can go do n i e allows programmer to set the semaphore to a negative Value prior to using it for synchronizatio int semaphoreidecrement Semaphore s int yalueiafteriop twipthreadimutexilock amps7gtmuteX s gtv7 7 valueiafteri 0P twipthre adimut exi s7gtv unlock amp s7gtmutex 7 return valueiafteriop 5 function returns the value of the semaphore at the time the critical section is accessed obviously the value is not guarenteed e an alternative is to simply record the value returned by semaphoreiup or semaphoreidown int semaphoreivalue Semaphore s not for sync int valueiafteriop twipthreadimutexilock amps7gtmutex 7 valueiafterio s7gtv twipthreadimutexiunlock amps7gtmuteX 7 return valueiafteriop 3 The following functions replace standard library functions in that they exit on any error returned from the system calls Saves us from having to check each and every call abo lt k int twipthreadimutexiunlock pthreadimutexit m int returnivalue if returnivalue pthreadimutexiunlock m fl doierror quotpthreadimutexiun c quot return returnivalue int twipthreadimutexilock pthreadimutexit m int returnivalue if returnivalue pthreadimutexilock m fl doierror quotpthreadimutexiloc quot return returnivalue int twipthreadicondiwait pthreadicondit c pthreadimutexit m int returnivalue if returnivalue 7 pthreadicondiwait c m doierror quotpthreadicondiwaitquot