Related Blog Items

• c/c++ blogging - January 10, 2007
• Multithreaded Programming using POSIX pthreads – Part 1
• Pelt: Posix Wrapper for Windows Threads
• dlwrapper: POSIX Wrapper for Windows Dynamic Library Loading Calls
• What is a reentrant function?

We have discussed very basics of multithreading in Part1, now before we actually go to Posix threads programming, we dig bit further in how to program an application using multiple threads and which applications require threads because we should not waste our effort and time by multithreading a program that is not worth multithreading.
Designing threaded programs
In order for a program to take advantage of threads, it must be able to be organized into discrete, independent tasks which can execute concurrently. For example, if routine1 and routine2 can be interchanged, interleaved and/or overlapped in real time, they are candidates for threading.
Tasks that may be suitable for threading include tasks that:

• Block for potentially long waits
• Use many CPU cycles
• Must respond to asynchronous events
• Are of lesser or greater importance than other tasks
• Are able to be performed in parallel with other tasks

Be careful if your application uses libraries or other objects that don’t explicitly guarantee thread-safeness. When in doubt, assume that they are not thread-safe until proven otherwise.
Thread-safeness: refers an application’s ability to execute multiple threads simultaneously without “clobbering” shared data or creating “race” conditions. For example, suppose that you use a library routine that accesses/modifies a global structure or location in memory. If two threads both call this routine it is possible that they may try to modify this global structure/memory location at the same time. If the routine does not employ some sort of synchronization constructs to prevent data corruption, then it is not thread-safe. The implication to users of external library routines is that if you aren’t 100% certain the routine is thread-safe, then you take your chances with problems that could arise.
The other terms you need to look at when using libraries/functions in threaded applications are
Reentrant code means that a program can have more than one thread executing concurrently? or a function get executed by itself after one or more function calls, example is a()->b()->x()->a(), in this a() is called again, if a() is not reentrant then we could be in troubles.
Async-safe means that a function is reentrant while handling a signal (e.g. can be called from a signal handler)
Concurrency vs. Parallelism - They are not the same! Parallelism is a subset of Concurrency. Parallelism implies simultaneous running of code (which is impossible on uniprocessor machines) while Concurrency implies that many tasks can run in any order and possibly in parallel.
Thread Design Patterns:

• Manager/worker: a single thread, the manager assigns work to other threads, the workers. Typically, the manager handles all input and parcels out work to the other tasks. At least two forms of the manager/worker model are common: static worker pool and dynamic worker pool.
• Pipeline: a task is broken into a series of suboperations, each of which is handled in series, but concurrently, by a different thread. An automobile assembly line best describes this model.
• Peer: similar to the manager/worker model, but after the main thread creates other threads, it participates in the work.

Protecting Shared Resources

Because most useful applications are more complex in general, we must synchronize our threads and protect globally shared data across multiple threads.

Mutual Exclusion

Mutual exclusion is the method of serializing access to shared resources. You do not want a thread to be modifying a variable that is already in the process of being modified by another thread! Another scenario would be a dirty read where the value is in the process of being updated and another thread reads an old value.

A mutex is a lock that guarantees three things:

1. Atomicity - Locking a mutex is an atomic operation, meaning that the operating system (or threads library) assures you that if you locked a mutex, no other thread succeeded in locking this mutex at the same time.
2. Singularity - If a thread managed to lock a mutex, it is assured that no other thread will be able to lock the thread until the original thread releases the lock.
3. Non-Busy Wait - If a thread attempts to lock a thread that was locked by a second thread, the first thread will be suspended (and will not consume any CPU resources) until the lock is freed by the second thread. At this time, the first thread will wake up and continue execution, having the mutex locked by it.

From these three points we can see how a mutex can be used to assure exclusive access to variables (or in general critical code sections). Here is some pseudo-code that updates the two variables we were talking about in the previous section, and can be used by the first thread:

lock mutex 'X1'.

set first variable to '0'.

set second variable to '0'.

unlock mutex 'X1'.

Meanwhile, the second thread will do something like this:

lock mutex 'X1'.

set first variable to '1'.

set second variable to '1'.

unlock mutex 'X1'.

Assuming both threads use the same mutex, we are assured that after they both ran through this code, either both variables are set to ‘0′, or both are set to ‘1′. You’d note this requires some work from the programmer - If a third thread was to access these variables via some code that does not use this mutex, it still might mess up the variable’s contents (this is just a framework to program in multi thread environment, right? If you use it properly it yields good results, otherwise you get screwed). Thus, it is important to enclose all the code that accesses these variables in a small set of functions, and always use only these functions to access these variables.
The code between the lock and unlock calls to the mutex, is referred to as the critical section. Minimizing time spent in the critical section allows for greater concurrency because it reduces the time other threads must wait to gain the lock. Therefore, it is important for a thread programmer to minimize critical sections.

Problems with Mutexes

An important problem associated with mutexes is the possibility of deadlock. A program can deadlock if two (or more) threads have stopped execution or are spinning permanently. The simplest deadlock situation: thread 1 locks lock A, thread 2 locks lock B, thread 1 wants lock B and thread 2 wants lock A. Instant deadlock. You can prevent this from happening by making sure threads acquire locks in an agreed order (lock ordering). Deadlock can also happen if threads do not unlock mutexes properly.

Race conditions occur when multiple threads share data and at least one of the threads accesses the data without going through a defined synchronization mechanism (Nichols 203). This could result in erroneous results even in an inconsistent manner which makes race conditions particularly difficult to debug. Library calls outside of your program’s control are common culprits. Make sure you take steps within your program to enforce serial access to shared file descriptors and other external resources. On most Solaris man pages, you can find out if your library call is safe to use in reentrant code. Towards the bottom of the man page, you will see Categories of MT Library Calls. MT Safe means that the function can be called concurrently from different threads. MT Hot are “fast” MT Safe functions (usually not found on man pages). MT Unsafe means that the function cannot be called concurrently. Alternative means that there are MT Safe equivalents (e.g. gethostbyname() and gethostbyname_r()).

Another problem with mutexes is that contention for a mutex can lead to priority inversion. A higher priority thread can wait behind a lower priority thread if the lower priority thread holds a lock for which the higher priority thread is waiting. This can be eliminated/reduced by limiting the number of shared mutexes between different priority threads.

Thread Synchronization Primitives

Mutexes are one method of synchronizing threads, however, there are many other ways.

Synch Technique I :: Condition Variables

A popular method of synchronizing multiple threads is through the use of condition variables. Condition variables allow threads to synchronize to a value of a shared resource. Condition variables provide a kind of notification system among threads.
For example, you could have a global counter, and once it reaches a certain count a thread activates. The thread that activates once the counter reaches the limit would wait on the condition variable. Other threads signal this condition variable if you want threads waiting/sleeping on this condition variable to wakeup. You can also use broadcast if you want to signal all threads waiting on the condition variable to wakeup. This sounds a bit confusing, but the pthread example below will clarify how condition variables work.

When waiting on condition variables, the wait should be inside a loop, not in a simple if statement because of spurious wakeups. You are not guaranteed that if a thread wakes up, it is the result of a signal or broadcastcall.

Synch Technique II :: Reader/Writer Locks

It is sometimes useful to allow multiple readers (threads) to read a shared resource variable without having to wait for locks if no thread is writing to the resource. With a multiple reader lock this is possible. Readers can enter the lock and do their business while writers wait until there are no readers left in the lock. Then the writer can modify the value while blocking all new readers from entering the lock.

Writer starvation is possible with the many reader/single writer lock technique. A priority system can eliminate writer starvation. For more information on r/w locks, see Nichols pgs. 84-89.

Synch Technique III :: Spinlocks

Spinlocks are less commonly used at the user-level. Spinlocks are used frequently in the Linux kernel itself. A spinlock will basically spin on a mutex. If a thread cannot obtain the mutex, it will keep polling the lock until it is free. The advantages to this is that if a thread is about to give up a mutex, you don’t have to context switch to another thread. This situation is a bit tricky because you don’t know when this might occur, and long spin times will result in poor performance.

Spinlocks should never be used on uniprocessor machines. Why is this?

Synch Technique IV :: Semaphores

Semaphores are another type of synchronization primitive that come in two flavors: binary and counting. Binary semaphores act much like mutexes, while counting semaphores can behave as recursive mutexes. Counting semaphores can be initialized to any arbitrary value which should depend on how many resources you have available for that particular shared data. Many threads can obtain the lock simultaneously until the limit is reached. This is referred to as lock depth.

Semaphores are more common in multiprocess programming (i.e. it’s usually used as a synch primitive between processes).
Now we are ready for programming and know about pthreads API.

Popularity: 8%

You need to log on to convert this article into PDF

Related Blog Items

• c/c++ blogging - January 10, 2007
• Multithreaded Programming using POSIX pthreads – Part 1
• Pelt: Posix Wrapper for Windows Threads
• dlwrapper: POSIX Wrapper for Windows Dynamic Library Loading Calls
• What is a reentrant function?

This entry was written by ponnada and posted on November 2, 2006 at 5:39 pm and filed under Multithreading. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.