Difference between racearound condition and deadlock

Question

What is the difference between a dead lock and a race around condition in programming terms?

Answer 1

I assume you mean "race conditions" and not "race around conditions" (I've heard that term...)

Basically, a dead lock is a condition where thread A is waiting for resource X while holding a lock on resource Y, and thread B is waiting for resource Y while holding a lock on resource X. The threads block waiting for each other to release their locks.

The solution to this problem is (usually) to ensure that you take locks on all resources in the same order in all threads. For example, if you always lock resource X before resource Y then my example can never result in a deadlock.

A race condition is something where you're relying on a particular sequence of events happening in a certain order, but that can be messed up if another thread is running at the same time. For example, to insert a new node into a linked list, you need to modify the list head, usually something like so:

newNode->next = listHead;
listHead = newNode;

But if two threads do that at the same time, then you might have a situation where they run like so:

Thread A                       Thread B
newNode1->next = listHead
                               newNode2->next = listHead
                               listHead = newNode2
listHead = newNode1

If this were to happen, then Thread B's modification of the list will be lost because Thread A would have overwritten it. It can be even worse, depending on the exact situation, but that's the basics of it.

The solution to this problem is usually to ensure that you include the proper locking mechanisms (for example, take out a lock any time you want to modify the linked list so that only one thread is modifying it at a time).

Answer 2

A deadlock is when two (or more) threads are blocking each other. Usually this has something to do with threads trying to acquire shared resources. For example if threads T1 and T2 need to acquire both resources A and B in order to do their work. If T1 acquires resource A, then T2 acquires resource B, T1 could then be waiting for resource B while T2 was waiting for resource A. In this case, both threads will wait indefinitely for the resource held by the other thread. These threads are said to be deadlocked.

Race conditions occur when two threads interact in a negatve (buggy) way depending on the exact order that their different instructions are executed. If one thread sets a global variable, for example, then a second thread reads and modifies that global variable, and the first thread reads the variable, the first thread may experience a bug because the variable has changed unexpectedly.

Answer 3

Think of a race condition using the traditional example. Say you and a friend have an ATM cards for the same bank account. Now suppose the account has $100 in it. Consider what happens when you attempt to withdraw $10 and your friend attempts to withdraw $50 at exactly the same time.

Think about what has to happen. The ATM machine must take your input, read what is currently in your account, and then modify the amount. Note, that in programming terms, an assignment statement is a multi-step process.

So, label both of your transactions T1 (you withdraw $10), and T2 (your friend withdraws $50). Now, the numbers below, to the left, represent time steps.

       T1                        T2
       ----------------          ------------------------
 1.    Read Acct ($100)          
 2.                              Read Acct ($100)
 3.    Write New Amt ($90)
 4.                              Write New Amt ($50)
 5.                              End
 6.    End

After both transactions complete, using this timeline, which is possible if you don't use any sort of locking mechanism, the account has $50 in it. This is $10 more than it should (your transaction is lost forever, but you still have the money).

This is a called race condition. What you want is for the transaction to be serializable, that is in no matter how you interleave the individual instruction executions, the end result will be the exact same as some serial schedule (meaning you run them one after the other with no interleaving) of the same transactions. The solution, again, is to introduce locking; however incorrect locking can lead to dead lock.

Deadlock occurs when there is a conflict of a shared resource. It's sort of like a Catch-22.

   T1            T2
   -------       --------
1.  Lock(x)
2.               Lock(y)
3.  Write x=1
4.               Write y=19
5.  Lock(y)
6.  Write y=x+1
7.               Lock(x)
8.               Write x=y+2
9.  Unlock(x)
10.              Unlock(x)
11. Unlock(y)
12.              Unlock(y)

You can see that a deadlock occurs at time 7 because T2 tries to acquire a lock on x but T1 already holds the lock on x but it is waiting on a lock for y, which T2 holds.

This bad. You can turn this diagram into a dependency graph and you will see that there is a cycle. The problem here is that x and y are resources that may be modified together.

One way to prevent this sort of deadlock problem with multiple lock objects (resources) is to introduce an ordering. You see, in the previous example, T1 locked x and then y but T2 locked y and then x. If both transactions adhered here to some ordering rule that says "x shall always be locked before y" then this problem will not occur. (You can change the previous example with this rule in mind and see no deadlock occurs).

These are trivial examples and really I've just used the examples you may have already seen if you have taken any kind of undergrad course on this. In reality, solving deadlock problems can be much harder than this because you tend to have more than a couple resources and a couple transactions interacting.

Hope this helps a little bit. As always, use Wikipedia as a starting point for CS concepts:

http://en.wikipedia.org/wiki/Deadlock

http://en.wikipedia.org/wiki/Race_condition