Multithreading: Common Pitfalls

Share on Facebook3Tweet about this on Twitter10Share on Google+2Share on Reddit1Share on StumbleUpon20

Deadlocks, Starvation, Livelock and Race Conditions

If I had an hour to solve a problem I’d spend 55 minutes thinking about the problem and 5 minutes thinking about solutions. – Albert Einstein 

Deadlocks, starvation, and race conditions are the bane of multithreaded programming and they can bring down any system in which they occur.

Defining the Problem(s)

Deadlock – Occurs when two competing processes are waiting for each other to finish, allowing neither to finish.

Starvation – Occurs when a process never gains accesses to resources, never allowing the program to finish.

Race Conditions – Occurs when processes that must occur in a particular order occur out of order due to multiple threading. More specifically, this is discussing a data race, please avoid arguments such as this one.

Livelock – Occurs when two threads are dependent on each other signals and are both threads respond to each others signals. If this is the case, the threads can cause a loop similar to something between a deadlock and starvation.

Deadlock

I have on occasion heard the analogy that deadlock occurs in multithreading the same way gridlock occurs in traffic.

Gridlock.svg

Essentially, one thread, say thread A, attempts to complete a process (hogging some resources). Another thread, thread B, attempts to use resources from A to complete it’s process, but cannot. A cannot complete it’s process until recourses from B are released and thus we have a deadlock. The table below is representative of a deadlock situation:

Screen Shot 2014-05-05 at 9.42.19 PM

Each thread in the example needs resources 1, 2, 3, and 4 to complete, but only has access to two, and neither thread will give up their resources. Similar to the traffic gridlock example, there is no way out unless something changes. In programming we can use signaling (such as interprocess communication i.e. pipes), a mutex or semaphores (with timesharing/timeouts) to break deadlocks.

Starvation

Starvation is exactly what it sounds like, a process is quite literally “starved” never gaining recourses and in turn no progress is made. A real life example could occur at a two way stop sign, where two parallel lanes do not contain stop signs, but the two adjacent do. The way only way this would occur is if there a never ending stream of cars, but for this example that is the case.

NZTA Give Way_5 02-12 FOR INSERT2

In the example, so long as cars are driving from either left to right or right to left there is no way for the red car to cross the street. This is the same issue processes face upon starvation. The table below represents code in which thread B always yields to thread A and thread A never releases the resources so long as they are in use (and in this case suppose they are always in use).

Screen Shot 2014-05-05 at 10.08.09 PM

In the table thread A is constantly using all of the resources, never yielding them to thread B, thereby starving thread B. A simple solution to this problem is to create a mutex and share the resources based on time or some other factor which occurs. The caveat being, if the resources are not shared based on time, they must be shared based on some event(s) which avoid starvation.

Race Conditions

Race conditions, usually refers to a data race, in which two threads simultaneously have access to a critical section, which is a section of code which contains a process which is required to be atomic. Data races are some times difficult to determine in multithreaded programs because a program can often run correctly one, two, or even hundreds of times without ever running into a problem. However, if a program does run into a data race condition it can be disastrous, often leading to deadlock or starvation.

An real world example would be two cars and one intersection. The intersection is representative of the critical section in which only one car (or rather lane of cars) should have access to at a given time.

640px-Japanese_car_accident_blur

In the real world this happens fairly often, one car attempts to gain access to the intersection and one runs a red light, BAM (deadlock)! In programming this can occur if we do not ensure our critical sections are atomic (Definition of Atomic: forming a single irreducible unit or component in a larger system). In other words, we must use a mutex to protect our critical section of code and only allow one thread access to atomic variables at a given time. If we code without protecting our critical sections we can have the following occur:

Screen Shot 2014-05-05 at 10.45.51 PM

In this case, because Thread A and Thread B are running simultaneously and we have no way of knowing (without a mutex) which thread changed resource one at any given time we have no clue what resource 1 currently is. Possible outcomes include:

  • Resource 1 = 3 (Thread A finishes before B starts)
  • Resource 1 = 4 (Thread B finishes before A starts)
  • Resource 1 = 5 (A: Resource 1 = 2; B: Resource 1 = 3; A: Recourse 1 += 1; B: Resource 1 += 1)
  • There are also other ways to get to 3 or 4

The point being (in this case) we needed to ensure that only one thread has access to a given resource at a given time.

Note that we do not always need to worry about protecting against race conditions. In many cases, such as this Producer-Consumer example, we do not care the order in which the orders are served. We do however ensure that the “count” of how many orders are currently ready, but not served is protected from a race condition by a mutex. This is because the “count” is data which is critical, the order is not.

Livelock

Livelocks – the deadlock with good intentions – are somewhere in-between a deadlock and starvation. Livelocks occur when two threads can communicate (through pipes, variables, or some other method) and both threads react to one another. This usual occurs when both threads relinquish their resources upon any request from another process (and immediately attempt to regain that resource).

Breaking from the car example, imagine two friends are walking together to a coffee shop. When they reach the door one friend stops (friend A), opens the door and offers the other to walk in (friend B). Instead of walking in the friend B tells friend A, “No you.” Friend A then says, “No you.” This is a classic livelock example, where one signal effects the other and no progress is made because neither friend takes initiative.

2cebfdae7a8ea5d691033c085990a9d4_L

In programming this happens much the same way, one thread communicates with the other and so on creating the same situation as a deadlock since neither process can complete their execution.

Screen Shot 2014-05-06 at 1.04.30 AM

In this program, thread A and B relinquish their resource any time it is requested and since both thread A and B need access to resource 1 no progress is made. A simple (though perhaps naive) solution to this issue is adding a time delay for each request.

Related Articles

Share on Facebook3Tweet about this on Twitter10Share on Google+2Share on Reddit1Share on StumbleUpon20

 Subscribe

If you enjoyed this article subscribe via email, it's free!

Plus exclusive email only content and problem solutions.

View Archived Emails (no surprises, no spam!)

4 comments on “Multithreading: Common Pitfalls

  1. Nice article! Threads cannot solve all your problems with performance. They can even introduce new bugs and problems. Hopefully there will be more and more frameworks that ‘automate’ scalability and multithreading.

    In C++, std::future and std::async looks promising, for instance. Have you used it? Or maybe similar technique in other languages?

    • I use OpenMP regularly to simply add some multithreading to my programs. I’ve also used async and future once, it’s pretty nice and I would recommend it. Personally, I still love the POSIX C way of multithreading, for me I enjoy the control, but there is more mistakes to be made as well.

Leave a Reply

Your email address will not be published.


4 + = five

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">