9

The definition of a race condition: A race condition or race hazard is a flaw in a system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events.

Consider the following pseudocode: 

    Global variable i initialized to 6;
    Thread 1: 
        acquire(lock l)
        increment global variable i, i.e. i++;

    Thread 2: 
       acquire(lock l)
       double the value of global var i, i.e.: i*=2;

If T1 acquires the lock l first and T2 second the value of i will be 14. On the other hand, if T2 acquires the lock l first and T1 second the value of i will be 13.

So, is this a race condition or not ?

UPDATE: after a number of comments and answers, the opinions are still divergent. My opinion is in the "YES, this is a race condition" category. Actually I gave this example as a race condition situation, on a different question. At the same time, I also read some interesting comments in the "NO, this isn't a race condition" category. I think I will settle and conclude that this is or isn't a race condition depending on the perspective/level from which one looks at the problem. However, I'm still waiting for interesting answers/comments.

  • for a more classic example, make thread 1 make a file access before acquiring lock ,and thread 2 make a cpu intensive computation before acquiring the lock. If you tune it correctly it will go one way on a machine with a fast disk and the other on a machine with a fast cpu. – Markus Mikkolainen Aug 17 '12 at 14:02
  • You're comment makes no sense. What you're saying is that in a different scenario with a different pseudo-code a race-condition could happen. Yes, you are correct. Race-conditions have been spotted in the past, but what does this have to do with the current topic? – Paul Irofti Aug 17 '12 at 14:14
  • So , This is a race condition if you assumed that it would always produce the same result. It is not a race condition if you designed it to produce a different result in different circumstances. Ofcourse there are better random generators so I assume that randomness is unintentional. – Markus Mikkolainen Aug 17 '12 at 14:16
  • Stop rationalizing your answer. This is in no way a race condition. You think it is one because that's how the words sound in your head. But it has nothing to do with the *concept* of race conditions. Nothing! You're just confusing the OP in being unable to cope with the fact that you were wrong. – Paul Irofti Aug 17 '12 at 14:19
  • Also relevant: [What is a race condition?](http://stackoverflow.com/questions/34510/what-is-a-race-condition) – ArjunShankar Aug 17 '12 at 14:27
  • [Here is how Microsoft, officially, defines a race](http://support.microsoft.com/kb/317723): "A race condition occurs when two threads access a shared variable at the same time. The first thread reads the variable, and the second thread reads the same value from the variable. Then the first thread and second thread perform their operations on the value, and they race to see which thread can write the value last to the shared variable. The value of the thread that writes its value last is preserved, because the thread is writing over the value that the previous thread wrote." – ArjunShankar Aug 17 '12 at 14:31
  • This WOULDNT be a race condition if you could somehow guarantee that one thread accesses the lock first _always_ – Markus Mikkolainen Aug 17 '12 at 14:32
  • 1
    @Arjun that is a very hardware-centered view of a race condition. – Markus Mikkolainen Aug 17 '12 at 14:33
  • 1
    no. There are two potential races here, one is prevented by locking (data race) but the other (general race) is not prevented. Unless ofcourse it is by design that the program could return two different values. – Markus Mikkolainen Aug 17 '12 at 17:26
  • Yeah: the hardware memory model makes some operations atomic; adding locks merely makes larger chunks atomic. Locks don't magically fix race conditions: now the race is for whoever acquires the lock first. And from the perspective of the software dev, I don't care whether the race is for a software lock or a hardware memory access: only the observable behavior matters. – Eamon Nerbonne Aug 18 '12 at 09:13
  • @EamonNerbonne: So you're saying that this is a race condition, right ? –  Aug 18 '12 at 11:46
  • From the software perspective: definitely. That might not make it a bug, and it might not be a race in a larger program if the global variable *i* isn't observed (but then, why call it a global variable...). – Eamon Nerbonne Aug 18 '12 at 11:49

5 Answers5

8

I think whether the example algorithm has a race condition depends on the what the algorithm is expected to do.

There is no data race on the modification of i - those accesses are serialized and occur atomically with respect to each other.

However, if it's important to the correctness of the algorithm that the increment occur before the multiplication (or vice versa), then there is a race and other means would have to be used to synchronize the execution of the algorithm. If the algorithm is supposed to be a complicated way to calculate i * 2 + 1 (as ridiculous as it might be to perform the calculation using threads), then there's a race condition.

Consider the following program snippet:

int data;

pthread_cond_t condvar = PTHREAD_COND_INITIALIZER;
pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

void* wait_for_data(void*)
{
    pthread_mutex_lock( &mux);
    pthread_cond_wait( &condvar, &mux);

    puts("got the data: %d\n", data);

    pthread_mutex_unlock( &mux);

    return 0;
}


void* set_data(void*)
{
    pthread_mutex_lock( &mux);

    data = 42;

    pthread_cond_signal( &condvar);

    pthread_mutex_unlock( &mux);

    return 0;
}

Both threads are essentially completely mutually exclusive - there is no data race. However, if set_data() signals the condition variable before wait_for_data() gets around to waiting on it, wait_for_data() will never complete. I think most people would call that a race condition due to improper use of the condition variable.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
2

No it's not. Because it locks before reading and writing to i. So the reads and writes in your example are always consistent. Of course you should unlock after each operation, but I guess you just forgot to add that in your pseudo-code.

Paul Irofti
  • 412
  • 3
  • 17
2

No, this is one of the expected sequences of execution. A race would be not protecting the counter with some sort of a lock, thus allowing for load-modify-store cycles to run concurrently.

Edit 0:

@Gheorghe, think about an example of a joint bank account and two people taking their money out of it at difference bank offices at the same time. A clerk at each location would need to check account balance, give out cash, and write down new balance. If this is not "atomic" with regard to the balance, i.e. the account is not "locked" during this operation, they might end up getting more money between two of them then they had in the bank. Banks don't like that.

But if the account is locked while being manipulated, does the output depend on the timing? Yes, absolutely - total sum doesn't change, but the split between two of them can be different.

What matters is the consistency of the protected value - no matter in what sequence and how many times these two guys take money from the back, they don't get more then they originally had.

Nikolai Fetissov
  • 82,306
  • 11
  • 110
  • 171
  • that really depends on what they are doing with "i". – Markus Mikkolainen Aug 17 '12 at 14:04
  • 4
    No, it doesn't. A race is a race, what you are talking about is bad design. – Nikolai Fetissov Aug 17 '12 at 14:11
  • For example i had a case where the original developer of the software had made the software initialize with multiple threads and while he had used locks, the initialization result depended on the relative speeds of CPU and Disks on the machine. So while everything was correctly locked locally, the end result varied depending on luck and hardware. – Markus Mikkolainen Aug 17 '12 at 14:12
  • Ofcourse you might want to argue that the programmer has intentionally made a very unpredictable design.But I would say he assumed something always happens first , since it does on his machine and did a race condition. – Markus Mikkolainen Aug 17 '12 at 14:14
  • 1
    @NikolaiNFetissov: So race conditions means lack of synchronization leading to ouput depedant on timing of events ? –  Aug 17 '12 at 14:19
  • A race condition is when something gets changed from under your feet. Think about the i++ instruction. What it does is it fetches the object from memory, reads it content, adds one to it and then stores the new value back to the same address. If during these micro-instructions, say after the read, some other thread would write 2*i at the same address then that would lead to a hazard because it would be overwritten by the next write micro-instruction from the i++ thread. And now one thread would expect you to have i++ there and another 2*i. Knowing which is impossible. – Paul Irofti Aug 17 '12 at 14:25
  • Ok so you seem to disagree with my schoolbook and wikipedia (for example) on the definition of a race condition. I think the definition on top of this page is quite good. – Markus Mikkolainen Aug 17 '12 at 14:26
  • 2
    Have you even read the [wikipedia](https://en.wikipedia.org/wiki/Race_condition#Computing) article? The ideal example there is exactly what the OP's algorithm does! – Paul Irofti Aug 17 '12 at 14:29
  • look below that example. there is a more fitting one below that.the pseudocode bit – Markus Mikkolainen Aug 17 '12 at 14:40
  • 1
    so i guess according to you wikipedia is wrong and that ACM article is wrong? – Markus Mikkolainen Aug 17 '12 at 17:25
1

Note: I give an answer from a Java perspective as the question originated from a previous discussion about the Java Memory Model.

There seems to be a lot of confusion around the definition of "race condition", which is why you are getting different answers.

If you mean "data race", there is only one valid definition in the context of Java, and it is given by the Java Language Specification 17.4.5:

When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race.

Conflicting accesses is defined in 17.4.1:

Two accesses to (reads of or writes to) the same variable are said to be conflicting if at least one of the accesses is a write.

In your case, your code contains a happens-before relationship as defined by 17.4.5:

An unlock on a monitor happens-before every subsequent lock on that monitor.

So there is no data race in your code in a Java context - anyone saying otherwise is using a non-Java definition.

Others have commented about a "general race" in the sense that any of the 2 codes could run first, but that's an algorithm question: either your code is parallelizable and it should not matter, or it is not and you should run it sequentially. But that's a bug, not a data race.

Community
  • 1
  • 1
assylias
  • 321,522
  • 82
  • 660
  • 783
  • And what kind of bug is it when shared mutable state is updated inconsistently depending on which thread reaches the mutation point first? That's a race condition. The fact that it's not a race condition from the memory model's perspective just means it's a different type of race condition. – Eamon Nerbonne Aug 18 '12 at 09:08
  • @EamonNerbonne See my edit - the original question was about the Java Memory Model, hence the orientation of my answer. Regarding your comment, it really depends on what the program is doing. Most programs that parallelize tasks, working on some shared variables, would have race conditions with your definition because intermediate states are not predictable. But if the final state is predictable, thanks to proper synchronization, I would not call that a race condition. So it boils down to whether the fact that one code runs before the other is acceptable or not from an algorithm perspective. – assylias Aug 18 '12 at 09:32
  • And if it is not acceptable, then yes there is a race condition from that algorithm's perspective (although there still is no data race as the reads & writes to the shared variable are properly synchronized and therefore sequentially consistent (at least in Java)). – assylias Aug 18 '12 at 09:33
  • In this case, the *final* state of this code segment is not predictable: it's not just the intermediate state that's inconsistent (and it's the final state I'm talking about; or the observable state in a real-time program). Most (non-buggy) parallel programs will have predictable final state. – Eamon Nerbonne Aug 18 '12 at 11:46
  • Looking at the Q edits, the original question was not (specifically) about the java memory model. I'm not sure why you thought it was. – Eamon Nerbonne Aug 18 '12 at 11:47
  • 1
    @assylias: ok, in the Java Memory model, which seems a little bit more strict when it comes to the definition of the race condition, the lack of a happens-before condition is a requirement for a potential race condition. This clearly answers my question from the Java Mem model perspective, but in general the discussion it still open. –  Aug 18 '12 at 12:08
-1

yes. by definition it is. Also you will have a problem with variable volatility. In this case there is no guarantee which thread loads the variable from memory to which register and then saves it to memory. So it might be that in some cases,one thread will get a stale value. In many languages you will have to somehow make sure that you will always fetch a clean copy. (in java volatile)

http://www.freebsd.org/doc/en/books/developers-handbook/secure-race-conditions.html

I think that is a good definition also.

Reading: http://dl.acm.org/citation.cfm?id=130623

"Two different notions have been implicitly considered: one pertaining to programs intended to be deterministic (which we call general races) and the other to nondeterministic programs containing critical sections (which we call data races)."

so I would say that it is a "general race" if you assumed that program to always produce the same result. If not, you just have very weird design.

Markus Mikkolainen
  • 3,397
  • 18
  • 21
  • "*In this case there is no guarantee which thread loads the variable from memory to which register and then saves it to memory.*" - In C, there would be no way to know how `acquire` (a function call) modifies the value of `i` (a global). Therefore, an `i = i + 1` or `i++` written *after* the `acquire` necessarily needs to cause a `load` *after* the `acquire`. This means the value is not stale. – ArjunShankar Aug 17 '12 at 14:09
  • 2
    @Markus, You are wrong here. Locks, by definition, enforce memory coherence. There would be a "load memory fence" in front of the "lock", and "store memory fence" after the "unlock". – Nikolai Fetissov Aug 17 '12 at 14:16
  • @exacerbatedexpert: exactly; locks provide mutual exclusivity which is not the same thing as preventing races. You can use mutual exclusivity to prevent races, but that depends on making the right things mutually exclusive. In this case, the two threads still have a race condition; just now it's to acquire the lock first. The locks have prevented some non-deterministic behavior, but not all. – Eamon Nerbonne Aug 18 '12 at 09:21
  • @exacerbatedexpert: I think you've got it backwards. Defining a race to mean only those races visible to hardware is not helpful since the OP isn't designing hardware (or virtual "hardware" like a VM). If you just add a lock, and then "by definition" don't have a race anymore - what good is that? It's not like you've solved the bug. Locks *can* help avoid race conditions - it's just they need to lock the right code sections for long enough to ensure that the state is always consistent outside of a critical section. And what "consistent" means is unfortunately inevitably app-dependant. – Eamon Nerbonne Aug 20 '12 at 14:09