Operating Systems and Systems Integration Workshop on POSIX Threads and the Problem of Deadlock — Solutions 1 Background • posix is a standard for Unix • Linux implements posix threads • On Red Hat 8.x, documentation is at $ info '(libc) POSIX Threads' ◦ or in Emacs, C-H m libc then middle-click on POSIX threads • Provides: ◦ semaphores, ◦ mutex es and ◦ condition variables for locking (synchronisation) 2 Generic Procedure for Compiling POSIX Threads Applications 1. You need to use the libpthread library • Specify this with the option -lpthread 2. Need to tell the other libraries that they should be reentrant (or “thread safe”) • This means that the library uses no static variables that may be overwritten by another thread • Specify this with the option -D REENTRANT 3. So, to compile the program program .c, do: $ gcc -D_REENTRANT -lpthread -o program program .c 3 Procedure 1. Download the source code for these programs from the subject web site: hello.c, deadlock.c and error.h. Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 2 Program 1 A simple program hello.c that is the program hello.c given in the lecture. #include #include #include #include #define NUM THREADS 5 void ∗print hello( void ∗threadid ) { printf ( "\n%d: Hello World!\n", ( int ) threadid ); pthread exit( NULL ); } int main() { static pthread t threads[ NUM THREADS ]; int rc, t; for ( t = 0; t < NUM THREADS; t++ ) { printf ( "Creating thread %d\n", t ); rc = pthread create( &threads[ t ], NULL, print hello, ( void ∗ ) t ); if ( rc ) { printf ( "ERROR; pthread_create() returned %d\n", rc ); printf ( "Error string: \"%s\"\n", strerror ( rc ) ); exit( −1 ); } } pthread exit( NULL ); } 3.1 An Introduction to Posix Threads 1. Compile and run program 1, using the generic instructions given in section 2 on the page before. 2. Refer to the lecture notes on the topic Processes and Threads and read the few slides starting at slide 71. Read about the four parameters that are passed to pthread create(). Note that there is a detailed manual page for every single library function used here. For example, you can see man pthread create, and man strerror, man 3 exit, man 3 printf, and so on. 3. Modify hello.c, increasing the number of threads until you find the maximum number of threads that your system can support. 4. Download the program file hello-with-logs.c, which makes each thread do cpu intensive calculations. Observe the output of vmstat 1 and also, run top in another window. Watch the load average.∗ Load Average is the average number of processes that are in the ready-to-run state. In other words, the number of additional processes that would be running if each had a cpu. ∗ Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 3 Program 2 Pseudocode for the two threads. deadlock no mutual exclusion Thread a() { lock mutex1 ; give up CPU; lock mutex2 ; unlock mutex1 ; unlock mutex2 ; } Thread b() { lock mutex2 ; give up CPU; lock mutex1 ; unlock mutex2 ; unlock mutex1 ; } /∗ No locking No mutexes ∗/ Thread a() { use resource1 ; use resource2 ; } Thread b() { use resource2 ; use resource1 ; } no hold & wait Thread a() { /∗ no H & W ∗/ lock mutex1 ; give up CPU; unlock mutex1 ; lock mutex2 ; unlock mutex2 ; } Thread b() { lock mutex2 ; give up CPU; lock mutex1 ; unlock mutex2 ; unlock mutex1 ; } no circular wait Thread a() { lock mutex1 ; give up CPU; lock mutex2 ; unlock mutex1 ; unlock mutex2 ; } Thread b() { /∗ same order ∗/ lock mutex1 ; give up CPU; lock mutex2 ; unlock mutex1 ; unlock mutex2 ; } 3.2 Deadlock 1. Compile and execute the program deadlock.c shown in program 3 on page 6 and program 8. Observe what happens when you run it. 2. Read about mutexes in slide 83 in the lecture notes on the topic Processes and Threads. Also read slides 84–86 showing example code using a mutex. 3. Notice that most of the code of program 3 on page 6 is printf() statements, error checking and such. The code for the two threads can be expressed quite simply, as shown in program 2. Examine the pseudocode in program 2 and compare it with the C program 3, and see how the pseudocode is a summary of the C program. 4. The standard posix library function sched yield() allows a thread or process to voluntarily give up the cpu, so that the scheduler will move it to the end of the queue for its own priority, and allow another thread or process to run. See man sched yield. 5. Note that there are four conditions required for deadlock; if you remove any one of these, then deadlock will not happen. They are: • Mutual exclusion ◦ where only one process can use a resource at one time • Hold and Wait ◦ Processes holding resources given earlier can request new resources • No Preemption ◦ Resources given to a process or thread cannot be taken away forcibly by os or anything other than that process or thread • Circular Wait Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 4 ◦ Each process is waiting for a resource held by another 6. Describe here how this program satisfies the deadlock requirement of mutual exclusion i The program uses mutexes, which by their very nature, enforce mutual ex clusion. If one thread locks a mutex, no other thread can lock it until the first thread unlocks it. 7. Describe here how this program satisfies the deadlock requirement of hold and wait i locking thread a() locks mutex 1, then while still holding it, locks mutex 2. locking thread b() locks mutex 2, then while still holding it, locks mutex 1. This is hold and wait. 8. Describe here how this program satisfies the deadlock requirement of no preemption i A thread cannot take a mutex away from another thread by force, and the code is not written so that one thread will give up the lock voluntarily to the other, so there is no preemption. 9. Describe here how this program satisfies the deadlock requirement of circular wait i locking thread a() locks mutex1 then waits for mutex2, which can be held by locking thread b(), whereas locking thread b() locks mutex2 then waits for mutex1, which can be held by locking thread a(). The result is that both threads are blocked, waiting for the availablity of a resource held by the other. 10. Copy the original program (deadlock.c) to a new file name, and make simple changes to it to remove at least one of the conditions required for deadlock. Note that there are many ways of solving this problem, not just one or two. Look for as many as you can. Use simple logic rather than spending a lot of time reading the manuals for new posix threads library functions. First, simply try rearranging the pseudocode in program 2 on the page before. • Do this a number of times, using a different method for each program. Solution: There are many solutions that may be correct, but many are wrong. For example, removing the call to shed yield() does not remove any conditions for deadlock, since the program is very likely to deadlock on an smp machine, and on a single cpu machine if there is some real work for the threads to do. Program 4 on page 7 shows the mutual exclusion removed. The main() fucntion is still the same as program 8 on page 11. Note that the danger here is that the data may be corrupted if two threads write to it at the same time, or there may be a race condition that results in the wrong values stored in or read from the data. Program 5 on page 8 removes hold and wait from locking thread a(). Note that this would not always be possible; the two resources may be both needed at the same time. Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 5 Program 6 on page 9 is based on backoff.c; see section 3.3 on page 11. The idea is that if locking thread a() has mutex1, and cannot lock mutex2, it releases mutex1 and tries again later. This eliminates hold and wait, since locking thread a() does not continue holding mutex1 while waiting for mutex2. Have a good look at the code, and see how it works. Porgram 7 on page 10 simply re-orders the requests for resources so that all threads request them in the same order. This is a common practice in operating systems and threaded applications, but there may be some situations where it cannot be done. End of Solution. • Put a comment at the top of the program, indicating which conditions for deadlock you have removed. • Put your name and class in a comment at the top of each file. • Demonstrate to your lab supervisor. • Write a text file containing your answers to questions 6, 7, 8 and 9. • Use the tar or zip program to combine the sources and the text file mentioned above into one file, and • Submit to the online submission system at http://ictlab.tyict.vtc.edu.hk/perl2/submit.cgi. Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 6 Program 3 The first part of the program deadlock.c that is unable to run to completion. #include #include #include "errors.h" /∗ Initialize 2 mutexes. ∗/ pthread mutex t mutex1 = PTHREAD MUTEX INITIALIZER; pthread mutex t mutex2 = PTHREAD MUTEX INITIALIZER; void ∗locking thread a( void ∗arg ) { int status; printf ( "locking_thread_a starting\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "a has lock 1\n" ); sched yield(); printf ( "a now trying to get lock 2\n" ); status = pthread mutex lock( &mutex2 ); printf ( "a has lock 2\n" ); if ( status != 0 ) err abort( status, "lock 2" ); pthread mutex unlock( &mutex1 ); pthread mutex unlock( &mutex2 ); printf ( "locking_thread_a finishing\n" ); pthread exit( NULL ); } void ∗locking thread b( void ∗arg ) { int status; printf ( "locking_thread_b starting\n" ); status = pthread mutex lock( &mutex2 ); if ( status != 0 ) err abort( status, "lock 2" ); printf ( "b has lock 2\n" ); sched yield(); printf ( "b now trying to get lock 1\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "b has lock 1\n" ); pthread mutex unlock( &mutex2 ); pthread mutex unlock( &mutex1 ); printf ( "locking_thread_b finishing\n" ); pthread exit( NULL ); } Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 7 Program 4 This simple solution removes mutual exclusion by removing the mutexes. Note that although this leaves nothing much, in real life a mutex is associated with data, and the data would be accessed, even though it is no longer protected by a mutex. #include #include #include "errors.h" void ∗locking thread a( void ∗arg ) { int status; printf ( "(NON) locking_thread_a starting\n" ); printf ( "a is using data 1\n" ); sched yield(); printf ( "a now using data 2\n" ); printf ( "(NON) locking_thread_a finishing\n" ); pthread exit( NULL ); } void ∗locking thread b( void ∗arg ) { int status; printf ( "(NON) locking_thread_b starting\n" ); printf ( "b is now using data 2\n" ); sched yield(); printf ( "b now using data 1\n" ); printf ( "(NON) locking_thread_b finishing\n" ); pthread exit( NULL ); } Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 8 Program 5 Here we removed the condition of hold and wait from locking thread a(), by simply unlocking mutex1 before locking mutex2. #include #include #include "errors.h" /∗ Initialize 2 mutexes. ∗/ pthread mutex t mutex1 = PTHREAD MUTEX INITIALIZER; pthread mutex t mutex2 = PTHREAD MUTEX INITIALIZER; void ∗locking thread a( void ∗arg ) { int status; printf ( "locking_thread_a starting\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "a has lock 1\n" ); sched yield(); // Note: unlock mutex1 before lock mutex 2: pthread mutex unlock( &mutex1 ); printf ( "a now trying to get lock 2\n" ); status = pthread mutex lock( &mutex2 ); printf ( "a has lock 2\n" ); if ( status != 0 ) err abort( status, "lock 2" ); pthread mutex unlock( &mutex2 ); printf ( "locking_thread_a finishing\n" ); pthread exit( NULL ); } void ∗locking thread b( void ∗arg ) { int status; printf ( "locking_thread_b starting\n" ); status = pthread mutex lock( &mutex2 ); if ( status != 0 ) err abort( status, "lock 2" ); printf ( "b has lock 2\n" ); sched yield(); printf ( "b now trying to get lock 1\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "b has lock 1\n" ); pthread mutex unlock( &mutex2 ); pthread mutex unlock( &mutex1 ); printf ( "locking_thread_b finishing\n" ); pthread exit( NULL ); } Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 9 Program 6 This method is based on backoff.c; see section 3.3 on page 11. #include #include #include "errors.h" /∗ Initialize 2 mutexes. ∗/ pthread mutex t mutex1 = PTHREAD MUTEX INITIALIZER; pthread mutex t mutex2 = PTHREAD MUTEX INITIALIZER; void ∗locking thread a( void ∗arg ) { printf ( "locking_thread_a starting\n" ); for (;;) { int status; status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "a has lock 1\n" ); sched yield(); printf ( "a now trying to get lock 2\n" ); status = pthread mutex trylock( &mutex2 ); if ( status == 0 ) break; printf ( "a failed to lock; backing off\n" ); pthread mutex unlock( &mutex1 ); sched yield(); } printf ( "a has lock 2\n" ); pthread mutex unlock( &mutex1 ); pthread mutex unlock( &mutex2 ); printf ( "locking_thread_a finishing\n" ); pthread exit( NULL ); } void ∗locking thread b( void ∗arg ) { int status; printf ( "locking_thread_b starting\n" ); status = pthread mutex lock( &mutex2 ); if ( status != 0 ) err abort( status, "lock 2" ); printf ( "b has lock 2\n" ); sched yield(); printf ( "b now trying to get lock 1\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "b has lock 1\n" ); pthread mutex unlock( &mutex2 ); pthread mutex unlock( &mutex1 ); printf ( "locking_thread_b finishing\n" ); pthread exit( NULL ); } Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 10 Program 7 By re-ordering the reequest for resources, we can eliminate the condition of circular wait. We simply request the resources in the same order. #include #include #include "errors.h" /∗ Initialize 2 mutexes. ∗/ pthread mutex t mutex1 = PTHREAD MUTEX INITIALIZER; pthread mutex t mutex2 = PTHREAD MUTEX INITIALIZER; void ∗locking thread a( void ∗arg ) { int status; printf ( "locking_thread_a starting\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "a has lock 1\n" ); sched yield(); printf ( "a now trying to get lock 2\n" ); status = pthread mutex lock( &mutex2 ); printf ( "a has lock 2\n" ); if ( status != 0 ) err abort( status, "lock 2" ); pthread mutex unlock( &mutex1 ); pthread mutex unlock( &mutex2 ); printf ( "locking_thread_a finishing\n" ); pthread exit( NULL ); } void ∗locking thread b( void ∗arg ) { int status; printf ( "locking_thread_b starting\n" ); status = pthread mutex lock( &mutex1 ); if ( status != 0 ) err abort( status, "lock 1" ); printf ( "a has lock 1\n" ); sched yield(); printf ( "a now trying to get lock 2\n" ); status = pthread mutex lock( &mutex2 ); printf ( "a has lock 2\n" ); if ( status != 0 ) err abort( status, "lock 2" ); pthread mutex unlock( &mutex1 ); pthread mutex unlock( &mutex2 ); printf ( "locking_thread_b finishing\n" ); pthread exit( NULL ); } Nick Urbanik ver. 1.6 Solutions Workshop on POSIX Threads and the Problem of Deadlock Operating Systems and Systems Integration 11 Program 8 The second part of the program deadlock.c that is unable to run to completion. int main() { pthread t thread1, thread2 ; int status; printf ( "Creating thread a\n" ); status = pthread create( &thread1, NULL, locking thread a, NULL ); if ( status ) err abort( status, "locking_thread_a" ); printf ( "Creating thread b\n" ); status = pthread create( &thread2, NULL, locking thread b, NULL ); if ( status ) err abort( status, "locking_thread_b" ); pthread exit( NULL ); } 3.3 Some Other Resources Some students wanted to know how you check if a mutex is locked without the calling thread going to sleep if the mutex is already locked by another thread. The answer is the posix threads library function: int pthread_mutex_trylock( pthread_mutex_t *MUTEX ); which immediately returns the value EBUSY if the mutex is locked. You can see an interesting example from the file backoff.c, shown on pages 66–69 of Butenhof (see [But97] below). You can read backoff.c from the subject web site at http://ictlab.tyict.vtc.edu.hk/ ossi/lectures/processes/programming-posix-threads/backoff.c. References There are many good sources of information in the library and on the Web about processes and threads. Here are some I recommend: [tut] [links] http://www.llnl.gov/computing/tutorials/workshops/workshop/ pthreads/MAIN.html gives a good online tutorial about posix threads. http://www.humanfactor.com/pthreads/ provides links to a lot of information about posix threads [But97] The best book about posix threads is Programming with POSIX Threads, David Butenhof, Addison-Wesley, May 1997. Even though it was written so long ago, David wrote much of the posix threads standard, so it really is the definitive work. It made me laugh, too! [Nut02] Operating Systems: A Modern Perspective: Lab Update, 2nd Edition, Gary Nutt, Addison-Wesley, 2002. A nice text book that emphasises the practical (like I do!) Nick Urbanik ver. 1.6