> Race condition, in terms of a computer programming, is a bug where two pieces of code cause an error if executed concurrently.
This article makes the common mistake of saying that a race condition is inherently a bug.
A race condition just means that observable program behaviour is dependent on the interleaving of two tasks. A race condition is only a bug if you don't want one of the possible interleavings.
You can often find great performance optimisations by working out how to work with race conditions rather than disallowing them.
I didn't link to Wikipedia myself - and I don't know what knowledge these people posting comments have - maybe they know more than I do - but I'd normally refer people to the Encyclopedia of Parallel Computing as the field's authoritative reference. It's written by a large number of experts and edited by an acknowledged leader in the field.
It says "Race conditions that can cause unintended non-determinacy are programming errors." and provides 23 references to the literature that you can follow for more history on it.
That's a good reference and I'll definitely look to that going forward.
Worth noting however, that the first article I found in those 23 references that actually used the phrase 'race condition' (in "What are race conditions? Some issues and formalizations") explicitly stated:
> However, in the literature, there seems to be little agreement as to precisely what constitutes a race condition. Indeed, two different notions have been used, but the distinction between them has not been previously recognized. Because no consistent terminology has appeared, several terms have been used with different intended meanings... [0]
Further,
> Data races cause nonatomic execution of critical sections and are failures in (nondeterministic) programs
All I'm trying to suggest is that colloquially, people will use this phrase to mean a lot of things, and I'm not sure the literature is entirely clear cut.
Querying multiple backends and responding with the data that has been received first. Not sure if this technique is really in use, but I figure this could be an optimization for dns queries and the like.
For example, some profilers that count the number of times something is run will update a counter without any synchronisation. This risks lost updates, but since you really just need to know if the counter is very low or very high a few lost updates here or there don't really matter.
But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.
Profiling is a tricky edge case though.
If gathering the profiling data costs too much, the results are completely useless. Especially relevant is all the quirky side effects like cache pressure.
So your choices here tend to be: sometimes wrong, or completely useless.
Let's say you have query that returns a bunch of rows from a sharded database by asking every shard and naively combining their responses by simply forwarding all rows as soon as you receive them.
That's a data race, the result will vary between executions because the row order will be different depending on how fast the various servers respond, but acknowledging that the order is not-well defined or guaranteed makes this data race accomodatable and even useful, since that gives a performance benefit compared to any solution that needs to ensure a specific order of these rows.
This is not a "data race" in a formal sense. A data race involves multiple threads accessing a non-atomic data object in ways that might result in an unintended and inconsistent state if the accesses overlap. That's always a bug.
The C++ standard's definition of a datarace only applies to ordinary memory access and rules those cases UB. But if you port such code to use relaxed load/store operations it's just as racey, but no longer UB. I'd consider still consider those cases data races, even though they don't meet the C++ standard's definition of them.
One time, I wrote a small network protocol stack to handle some proprietary UDP-based protocol that supported fragmentation.
Since the header on each fragment contained the total message size, I was able to pre-allocate the full size of the message upon receipt of the first fragment.
Then, as fragments arrived, I would copy their data into their respective areas of the message.
Typically, everything would arrive in order, so the message would be copied from beginning to end, piece by piece.
However, since this was Ethernet/UDP, it was possible for frames to arrive out of order.
This would result in the message being pieced together, with each fragment filling in its hole until all fragments have been received.
I guess this is a form of a data race? Or rather, a case where a data race at least wasn't detrimental.
A data race requires multiple threads to access the same memory at the same time and at least one of them to be writing the data.
There is no data race in your example, since the fragments are all written to different parts of memory, unless you had something else reading the message while the individual fragments were still being written.
I have one example where I didn't see a race as an issue. I was transferring data from one thread, to a second thread which would process it after a delay. This transfer was done by locking a mutex, then pushing it onto a queue.
The second thread does an unsynchronized fetch of the queue length, and then uses that fetched length as a condition in a loop that does a synchronised dequeue of a single item.
In this case, the race condition is not a problem, because the only place that data is removed is in that loop, which is a synchronised access.
So the worse case for a race here is that the length that's been read is less than the actual length, which is not a problem because that new data will just be handled the next time round.
Well for the readers (not saying you have a bug), what you describe can fail on any processor that doesn't implement TSO. Due to the fact that the write of your "queue length" may be visible before the queued item is fully visible. Meaning you read garbage from the newly queued item. Worse, even on a TSO architecture, unless you have a way to explicitly guarantee a compiler fence or there is an explicit data dependency the compiler is likely free to hoist the code which updates the queue length ahead of the code doing the queue update. Again meaning the unsyncronized thread reads that there is a new queue item before that queue item is visible to the reader.
How critical this ends up being to the program is heavily dependent on the queue data structure and how its being manipulated. But in a simple copy/linked list type situation referencing garbage data is quite likely.
A lot of traditional comp sci programs are plenty happy to teach about data synchronization primitives but completely fail to mention that most general API (posix/etc) primitives also have read/write fences implied. Those fences are as important on any processor made in the last two decades as the atomic operations themselves. As generally the implementations also provide both architectural memory barriers as well as compiler level fencing to assure the compiler isn't reordering the primitive with the code it is intended to protect. Going further, many architectures provide unfenced atomics. So, if you decide to code your own atomic_inc/swap/etc you have to also understand the memory model of the target machine before you have actually created something equivalent to what is taught in your average comp-sci department.
The code in question basically looks like this(C#):
// Called from Thread 1.
public void AddData(Data theData) {
lock(dataQueue) {
dataQueue.Enqueue(theData);
}
}
// Worker for Thread 2.
private void ProcessingThread() {
while(true) {
int length = dataQueue.Count;
for (int i = 0; i < length; i++) {
Data curData;
lock(dataQueue) {
curData = dataQueue.Dequeue();
}
// Process data.
}
// Sleep for a short while.
}
}
And all of that is in its own class, where these are the only two functions that access the data queue.
So, from what I can see, in the event where the length is updated before the data is actually inserted, Thread 2 is still forced to wait until Thread 1 is finished before it can access it so it's still safe. Though if I'm wrong, please tell me. No one wants garbage data.
I don't claim to know the c# memory model, but there is a chance that the compiler could hoist the 'int lenght = dataQueue.Count out of the loop.
Also, it is possible that Count is not a member but an accessor and it might return garbage or crash if it sees some inconsistent data.
Still, both of the above can be rare occurrences. The reason that you are not seeing no particular issues is because you are basically busy waiting and polling the queue (i.e. the sleep comment); if you replaced the dataQueue.Count with just a random number generator, the code will still work. If you were doing proper signaling instead of sleeping, then your code will get stuck in case of a missed wakeup.
I'm not sure if it would be allowed to hoist `dataQueue.Count` out of the loop. The docs [0] say that multiple concurrent readers are supported, so I'm not sure if the compiler would be allowed to assume anything about the call's return value.
You are correct in that `Count` is a property, and it could be doing extra things, but according to the implementation [1] it just returns the value of a private integer. Of course, this is an implementation detail and shouldn't be relied upon, but I'm not sure how much that could be changed.
However, you are mistaken about the code continuing to work if `dataQueue.Count` were replaced with an RNG, or if it were otherwise higher than it should be. The `Dequeue` function raises an exception if called on an empty queue. This one is part of the API, not an implementation detail. An uncaught exception here would crash the thread, not just blindly carry on.
Of course, I'm no expert, and could just be talking out of my ass.
Concurrent readers are supported, but not concurrent writers and readers. As Count is getting called outside of the critical section, the compiler can assume that there are no concurrent writers. Admittedly, the following critical section would make it hard for the compiler to actually apply any optimization in practice.
Count is implemented as a simple read currently, but that's not guaranteed to be the case in the future (that's the whole reason for having a property.
Fair enough about the rng, I'm not really a c# programmer, so I just assumed that dequeue would return a null on an empty queue.
I'm not an expert either, and certainly not a c# expert (although I kind of like the language, I haven't written a line in 7 years), so YMMV.
Any system where the only useful data is whatever was last written.
In certain kinds of signals intelligence software, the primary concern is access to the current frame of data. You don’t want to miss an RF peak that lasts just a few nanoseconds. It can be preferable to have half the the frame overwritten mid-processing every few million iterations than to slow down each iteration and force a lower overall refresh rate.
Data races on normal memory access are undefined behaviour in many languages (e.g. C, C++, Rust), so I assume that you mean races using atomic loads with relaxed ordering.
One practical example of using those is Hogwild, which is an implementation of stochastic gradient descent which skips synchronization on individual parameter updates, assuming that it'll converge even if some writes are lost or some reads are stale.
Could you explain that? Surely either it's dangerous to read and write simultaneously to a memory location or the operations are atomic (albeit perhaps unordered) and thus there is no data race?
Well, your memory model might fail to properly expose "atomic" access at the level you're actually relying on to prove that your 'data race' is safe. (Or using such fine-grained atomic accesses might have bad performance implications that can't be worked around using relaxed operations, etc.) But I don't think that's going to be a common case.
But any optimizing compiler is surely going to assume its memory model is adhered to, no? Therefore any "data races" will be undefined behaviour (even if they're atomic on physical hardware).
"Any" and "surely" are very strong words! Compilers implement different kinds of languages, guarantees, extensions and what not.
Even if your program is not conforming to whatever standard, it may be very well be useful and working in most compilers out there.
As an example, Linux is not conforming C, including triggering UB. But at least two major compilers support the intended semantics even if they are forbidden by the standard.
UB is UB. It might work. It might work now but not in the future. It might work in some situation but not others. It might appear to work but introduce subtle bugs elsewhere in the program.
Linux, as Linus has said, isn't written in ISO C it's written (or was) in GNU C. The two had something of a symbiotic relationship for a long time. Which is why porting it to LLVM was such a tremendous effort.
Which is to say, Linux conforms to the memory model of the compilers it compiles on (or vice versa). Not ISO C's memory model. So I'm not sure how your example is relevant.
Linux arguably relies on compiler extensions. Compilers are allowed to define behavior that is undefined by the language standards, effectively extending the language.
There has been a significant push to get Linux to use the c11 conformant gcc builtins. There has been significant push back though, but at least some bits have been updated.
No, it is not "dangerous". CPUs are designed to deal with that all the time (it is a whole field of research) and give you different guarantees when it does happen.
If your software is designed with that in mind, then a data race is not a bug.
>Data races don't imply memory unsafety (in the sense of having OOB accesses etc.).
Data races are undefined behavior on all major programming languages (C, C++, Rust, Java, Go, Swift, ...) and all major compilers compile code under the assumption that they do not happen.
If your program has a data-race, neither the language specification nor the compiler make any guarantees about the behavior of such programs.
Needles to say, this is neither safe, nor desirable, nor doing so produces perfectly safe programs.
The idea that data-races are safe because the load and store memory instructions that the CPU has are atomic is completely flawed, because it ignores the fact that the CPU does not execute the program you wrote, but the machine code that the compiler generates, and the compiler can and will reorganize non-atomic loads and stores under the assumption that they don't need to be atomic.
If your program has a data-race, the compiler provides no guarantees. It does not guarantee that the binary will reach the location where the data race happens. It does not even guarantee that the binary produced will be an executable binary, or that it will produce a binary at all (e.g. it does not guarantee that compilation terminates successfully).
* Data races using normal memory access function are impossible in safe code, and undefined behaviour in unsafe code. So unsafe code attempting this is incorrect.
* Data races using atomic types are possible in safe code. Some of the setup code might be unsafe internally while presenting a safe API (e.g. creating shared memory and giving you an `&[AtomicU8]` to that memory).
* Other race conditions (mostly non-deterministic order of lock acquisition) are also possible in safe code. The typical example of this is that writing to the console from multiple threads uses locks on individual write calls, which prevents torn writes but the order of those write outputs in non deterministic.
While true, it is still generally a mistake to leave a race condition in your code, because your human understanding of the possible interleavings is very unlikely to be correct. In addition to the way the code appears to be written, understanding the impact of a race condition requires you to fully understand the memory model in play, fully understanding all compiler optimizations that may have been made, which may include instruction reordering, fully understand all memory alignment issues on all machines you may execute this on and all their little differences, including on machines that don't exist yet that your code may run on in the future, and fully understand the entire stack of code involved in the race condition from the level of abstraction you're using pretty much all the way down to the compiled and optimized assembler. It also makes testing harder... all kinds of testing, automated and otherwise, because whether or not your tests can get to a given part of the state space becomes nondeterministic.
The average developer assessment that some race condition is completely harmless is wrong; there's usually a bug in the complicated state space somewhere.
A performance optimization involving a deliberate race condition should be pretty much your last resort.
Even the obvious ones are often less of a good idea than they may look, like a leaky incrementing counter for logging purposes. You might model that as being unlikely to lose more than a couple of percent, but I've seen cases where it lost the majority of logged events. Granted, this probably won't crash your program, but it can still result in surprisingly deceptive logging.
> And many race conditions don't have anything to do with the memory model or compiler optimizations.
For example, poorly structured response-handlers in JavaScript. If the code assumes that request R1 always returns before request R2, things may misbehave if that assumption is violated. That's a race condition, but as you say, it's nothing to do with memory models or compiler trickery, as JavaScript gives you just the one thread (not counting workers).
> If R2 returns before R1 that is still a race condition
That's not correct. Look at chrisseaton's definition.
If the observable program behaviour doesn't change depending on the order in which the requests complete, there's no race condition. (In JavaScript this might be done with Promise.all.) You're right that not all race conditions are bugs.
I don’t think you ever want a race condition for the sake of it but there are many daily cases where you don’t care that it races and fixing it would have terrible downsides. In a distributed system they’re practically unavoidable I think!
I think you might possibly be overstating how complex a race condition needs to be.
For example two consumers pushing results to a single result queue is a race condition, because the order in which they arrive depends on timing and is non-deterministic. That's a pretty normal thing to have.
Many languages people think of as being safe and high level are extremely racey - Erlang is my go-to example - two processes sending messages to a third is a race. Which message do you get first? It's non-deterministic. But it doesn't have to be a problem.
What you are describing sounds like non-deterministic behavior of a thread-safe primitive, e.g. non-deterministic ordering in a synchronized queue. On the other hand, a true race condition in the queue could mean messages overwriting each other.
I feel that leaning on a formal definition of a term in a way that's different from the normal usage that only matters in very rare circumstances is sniping rather than communication. You're only doing this so you can call it a mistake. Especially since you've not provided any examples.
(Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free")
Scheduler-dependent behaviour ends up being an absolute nightmare for automated testing and hunting of other bugs. It's not unreasonable to declare that all race conditions are bugs just for that reason.
Since pjc wanted a example that isn't explicitly a bug (a 'benign' race condition) I'll provide one that can be a major pita, two concurrent tasks are logging their event stream. Logs may not hit in exactly the order that you expect in your mind, forcing you to stop and think each time you're going over the logs. Definitely a race condition. Definitely expected behaviour. Not sure you can call that a bug.
More than once in my life I have thought that this was a bug, tried to correct it, and introduced another bug, followed by teeth gnashing, hair pulling, swearing, and then a revert.
Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
> What terminology do you use to describe something that is non-deterministic due to timing, but correct?
"Non-deterministic" works? However, I'm arguing that nondeterministic results from deterministic input are themselves a mild form of bug, like a compiler warning or "code smell".
Perhaps we also have to talk about causality and serialisability, clocks and timestamping. In a concurrent or distributed system it may not be easy to determine what order things happen in without unreasonable effort or performance impairment, but if so the system has to be designed so that doesn't matter.
> Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
Those I would call independent. Unless they're acting on something in common, in which case having the transactions serialised as A before B then logged as B before A is immensely annoying.
"Non-deterministic" totally works, but it's not necessarily a bug or even a code smell even if deterministic inputs lead to non-deterministic results. The order a series of parallel network calls returns is non-deterministic, for instance, but hardly a bug.
Otherwise, yes, agreed on all counts. It's telling that even when posing the question of what other term to use besides race condition, the op used 'non-deterministic'.
> Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free"
Informally, some people use it for that. But lock-free code is not that.
You may have lock-free code with locks, or lock-free code without data races, or lock-free code that can be shown to be incorrect (by your definition) yet work for the designed purpose...
I don't see how you can have that. If one process holding a lock halts then it will prevent system-wide progress, which is not allowed in the definition of 'lock-free'.
> If one process holding a lock halts then it will prevent system-wide progress
As others have mentioned already, if you had code that did that, that code would not be "lock-free". Lock-free requires progress in all circumstances even in the presence of ordering primitives (what we colloquially call "locks").
> if you had code that did that, that code would not be "lock-free"
Are you replying to the right person? That's what I just explained to the person I was replying to. You've quoted part of my comment but left out the "...which is not allowed in the definition of 'lock-free'".
That doesn't sound right. I suppose you could have locks in the trivial sense, where it never actually blocks, but I don't imagine that's what you meant.
Your first link confirms you can have locks in a multithreaded lock free algorithm - "The Lock-Free property guarantees that at least some thread is doing progress on its work" - I always thought this property should have been called deadlock free.
That's a good point, it does seem consistent with that definition.
This other blog post [0] seems to use a stricter definition of lock-free which precludes any way to schedule threads which would cause progress to cease indefinitely. That seems to be what the ConcurrencyFreaks blog refers to as Wait-free.
Any experts in lock-free programming able to clarify things?
I think it's a little unfair to characterize GP's comment as sniping. Race conditions don't necessarily involve schedulers, or CPUs operating on memory locations. It's true that concurrent processes that work correctly without synchronization are often called lock-free, but I don't see how that refutes the original point.
Given the context, and the confusion about what race conditions even are in some of the comments in the thread, I'd say the comment opened some good discussion. GP also provided examples of race conditions that are simple to reason about elsewhere in the thread, and also explained the difference between race conditions in general, and data races.
> This article makes the common mistake of saying that a race condition is inherently a bug.
No, it defines race condition, for purposes of the article, as something which is a bug. The author is only concerned with cases in which non-deterministic behavior causes errors.
When you write your own article, you are free to define "race condition" to include non-deterministic behavior that does not cause errors. But I don't think you can claim that the author's usage is simply wrong.
Try reproducing the race under an emulator like bochs. Bochs can be made fully deterministic, and you can take a snapshot at the beginning of the race and reproduce it every time from the snapshot. One downside is that bochs is very slow.
In the FreeBSD kernel, we've got fail(9) for this exact use (since 2009).
Check out the EXAMPLES section of the manual page. You can use the mechanisms to inject delay on some percentage of executions, and more generally some integer value can be injected, which can be used to simulate device failures (EIO) or whatever.
It's very powerful for creating reliable reproducers for all kinds of failures, including race conditions. And the KPI is not quite as verbose as the one presented in TFA.
This kind Man brought my Lover back In less than 3 days, i saw wonders, my Lover came back to me and my life got back just like a completed puzzle… am so happy.. thanks to Robinsonbucler@ { gmail }. com for saving my life. Mr Robinson is the best I’ve ever met! Thanks, thanks thanks_____________
90 comments
[ 3.1 ms ] story [ 144 ms ] threadThis article makes the common mistake of saying that a race condition is inherently a bug.
A race condition just means that observable program behaviour is dependent on the interleaving of two tasks. A race condition is only a bug if you don't want one of the possible interleavings.
You can often find great performance optimisations by working out how to work with race conditions rather than disallowing them.
[1] https://en.wikipedia.org/wiki/Race_condition
Indeed, there is even a debate about this issue in the talk page of wikipedia [https://en.wikipedia.org/wiki/Talk:Race_condition#Race_condi...]
https://link.springer.com/referenceworkentry/10.1007%2F978-0...
It says "Race conditions that can cause unintended non-determinacy are programming errors." and provides 23 references to the literature that you can follow for more history on it.
Worth noting however, that the first article I found in those 23 references that actually used the phrase 'race condition' (in "What are race conditions? Some issues and formalizations") explicitly stated:
> However, in the literature, there seems to be little agreement as to precisely what constitutes a race condition. Indeed, two different notions have been used, but the distinction between them has not been previously recognized. Because no consistent terminology has appeared, several terms have been used with different intended meanings... [0]
Further,
> Data races cause nonatomic execution of critical sections and are failures in (nondeterministic) programs
All I'm trying to suggest is that colloquially, people will use this phrase to mean a lot of things, and I'm not sure the literature is entirely clear cut.
[0]: https://dl.acm.org/doi/pdf/10.1145/130616.130623
Yes data races are always bugs, according to Padua et al.
But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.
jerf disagrees in last sentence of other comment: https://news.ycombinator.com/item?id=23079788
https://github.com/oracle/graal/blob/4553ea71f15c9e4721565e9...
You can argue this is a bug and they shouldn't write like this, but they don't consider it a bug and they do write like this.
So your choices here tend to be: sometimes wrong, or completely useless.
That's a data race, the result will vary between executions because the row order will be different depending on how fast the various servers respond, but acknowledging that the order is not-well defined or guaranteed makes this data race accomodatable and even useful, since that gives a performance benefit compared to any solution that needs to ensure a specific order of these rows.
Since the header on each fragment contained the total message size, I was able to pre-allocate the full size of the message upon receipt of the first fragment.
Then, as fragments arrived, I would copy their data into their respective areas of the message.
Typically, everything would arrive in order, so the message would be copied from beginning to end, piece by piece.
However, since this was Ethernet/UDP, it was possible for frames to arrive out of order.
This would result in the message being pieced together, with each fragment filling in its hole until all fragments have been received.
I guess this is a form of a data race? Or rather, a case where a data race at least wasn't detrimental.
There is no data race in your example, since the fragments are all written to different parts of memory, unless you had something else reading the message while the individual fragments were still being written.
The second thread does an unsynchronized fetch of the queue length, and then uses that fetched length as a condition in a loop that does a synchronised dequeue of a single item.
In this case, the race condition is not a problem, because the only place that data is removed is in that loop, which is a synchronised access.
So the worse case for a race here is that the length that's been read is less than the actual length, which is not a problem because that new data will just be handled the next time round.
How critical this ends up being to the program is heavily dependent on the queue data structure and how its being manipulated. But in a simple copy/linked list type situation referencing garbage data is quite likely.
A lot of traditional comp sci programs are plenty happy to teach about data synchronization primitives but completely fail to mention that most general API (posix/etc) primitives also have read/write fences implied. Those fences are as important on any processor made in the last two decades as the atomic operations themselves. As generally the implementations also provide both architectural memory barriers as well as compiler level fencing to assure the compiler isn't reordering the primitive with the code it is intended to protect. Going further, many architectures provide unfenced atomics. So, if you decide to code your own atomic_inc/swap/etc you have to also understand the memory model of the target machine before you have actually created something equivalent to what is taught in your average comp-sci department.
So, from what I can see, in the event where the length is updated before the data is actually inserted, Thread 2 is still forced to wait until Thread 1 is finished before it can access it so it's still safe. Though if I'm wrong, please tell me. No one wants garbage data.
Also, it is possible that Count is not a member but an accessor and it might return garbage or crash if it sees some inconsistent data.
Still, both of the above can be rare occurrences. The reason that you are not seeing no particular issues is because you are basically busy waiting and polling the queue (i.e. the sleep comment); if you replaced the dataQueue.Count with just a random number generator, the code will still work. If you were doing proper signaling instead of sleeping, then your code will get stuck in case of a missed wakeup.
You are correct in that `Count` is a property, and it could be doing extra things, but according to the implementation [1] it just returns the value of a private integer. Of course, this is an implementation detail and shouldn't be relied upon, but I'm not sure how much that could be changed.
However, you are mistaken about the code continuing to work if `dataQueue.Count` were replaced with an RNG, or if it were otherwise higher than it should be. The `Dequeue` function raises an exception if called on an empty queue. This one is part of the API, not an implementation detail. An uncaught exception here would crash the thread, not just blindly carry on.
Of course, I'm no expert, and could just be talking out of my ass.
[0] https://docs.microsoft.com/en-gb/dotnet/api/system.collectio... [1] https://github.com/dotnet/runtime/blob/master/src/libraries/...
Count is implemented as a simple read currently, but that's not guaranteed to be the case in the future (that's the whole reason for having a property.
Fair enough about the rng, I'm not really a c# programmer, so I just assumed that dequeue would return a null on an empty queue.
I'm not an expert either, and certainly not a c# expert (although I kind of like the language, I haven't written a line in 7 years), so YMMV.
In certain kinds of signals intelligence software, the primary concern is access to the current frame of data. You don’t want to miss an RF peak that lasts just a few nanoseconds. It can be preferable to have half the the frame overwritten mid-processing every few million iterations than to slow down each iteration and force a lower overall refresh rate.
One practical example of using those is Hogwild, which is an implementation of stochastic gradient descent which skips synchronization on individual parameter updates, assuming that it'll converge even if some writes are lost or some reads are stale.
https://papers.nips.cc/paper/4390-hogwild-a-lock-free-approa...
It is possible (and in rare cases, desirable) to have data races while still having a perfectly safe program.
Even if your program is not conforming to whatever standard, it may be very well be useful and working in most compilers out there.
As an example, Linux is not conforming C, including triggering UB. But at least two major compilers support the intended semantics even if they are forbidden by the standard.
Linux, as Linus has said, isn't written in ISO C it's written (or was) in GNU C. The two had something of a symbiotic relationship for a long time. Which is why porting it to LLVM was such a tremendous effort.
Which is to say, Linux conforms to the memory model of the compilers it compiles on (or vice versa). Not ISO C's memory model. So I'm not sure how your example is relevant.
If your software is designed with that in mind, then a data race is not a bug.
Data races are undefined behavior on all major programming languages (C, C++, Rust, Java, Go, Swift, ...) and all major compilers compile code under the assumption that they do not happen.
If your program has a data-race, neither the language specification nor the compiler make any guarantees about the behavior of such programs.
Needles to say, this is neither safe, nor desirable, nor doing so produces perfectly safe programs.
The idea that data-races are safe because the load and store memory instructions that the CPU has are atomic is completely flawed, because it ignores the fact that the CPU does not execute the program you wrote, but the machine code that the compiler generates, and the compiler can and will reorganize non-atomic loads and stores under the assumption that they don't need to be atomic.
If your program has a data-race, the compiler provides no guarantees. It does not guarantee that the binary will reach the location where the data race happens. It does not even guarantee that the binary produced will be an executable binary, or that it will produce a binary at all (e.g. it does not guarantee that compilation terminates successfully).
* Data races using normal memory access function are impossible in safe code, and undefined behaviour in unsafe code. So unsafe code attempting this is incorrect.
* Data races using atomic types are possible in safe code. Some of the setup code might be unsafe internally while presenting a safe API (e.g. creating shared memory and giving you an `&[AtomicU8]` to that memory).
* Other race conditions (mostly non-deterministic order of lock acquisition) are also possible in safe code. The typical example of this is that writing to the console from multiple threads uses locks on individual write calls, which prevents torn writes but the order of those write outputs in non deterministic.
The average developer assessment that some race condition is completely harmless is wrong; there's usually a bug in the complicated state space somewhere.
A performance optimization involving a deliberate race condition should be pretty much your last resort.
Even the obvious ones are often less of a good idea than they may look, like a leaky incrementing counter for logging purposes. You might model that as being unlikely to lose more than a couple of percent, but I've seen cases where it lost the majority of logged events. Granted, this probably won't crash your program, but it can still result in surprisingly deceptive logging.
And many race conditions don't have anything to do with the memory model or compiler optimizations.
For example, poorly structured response-handlers in JavaScript. If the code assumes that request R1 always returns before request R2, things may misbehave if that assumption is violated. That's a race condition, but as you say, it's nothing to do with memory models or compiler trickery, as JavaScript gives you just the one thread (not counting workers).
That's not correct. Look at chrisseaton's definition.
If the observable program behaviour doesn't change depending on the order in which the requests complete, there's no race condition. (In JavaScript this might be done with Promise.all.) You're right that not all race conditions are bugs.
Can you give an example of when one would (sanely) want to create a race condition?
For example two consumers pushing results to a single result queue is a race condition, because the order in which they arrive depends on timing and is non-deterministic. That's a pretty normal thing to have.
Many languages people think of as being safe and high level are extremely racey - Erlang is my go-to example - two processes sending messages to a third is a race. Which message do you get first? It's non-deterministic. But it doesn't have to be a problem.
That's what a race condition is - non-deterministic behavior of a thread-safe primitive.
> On the other hand, a true race condition in the queue could mean messages overwriting each other.
That's a data race, not a race condition.
(Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free")
Scheduler-dependent behaviour ends up being an absolute nightmare for automated testing and hunting of other bugs. It's not unreasonable to declare that all race conditions are bugs just for that reason.
I use 'race condition', but if you reserve that for something with bugs you'll need to invent a new term for the benign version.
More than once in my life I have thought that this was a bug, tried to correct it, and introduced another bug, followed by teeth gnashing, hair pulling, swearing, and then a revert.
Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
"Non-deterministic" works? However, I'm arguing that nondeterministic results from deterministic input are themselves a mild form of bug, like a compiler warning or "code smell".
Perhaps we also have to talk about causality and serialisability, clocks and timestamping. In a concurrent or distributed system it may not be easy to determine what order things happen in without unreasonable effort or performance impairment, but if so the system has to be designed so that doesn't matter.
> Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
Those I would call independent. Unless they're acting on something in common, in which case having the transactions serialised as A before B then logged as B before A is immensely annoying.
Otherwise, yes, agreed on all counts. It's telling that even when posing the question of what other term to use besides race condition, the op used 'non-deterministic'.
Informally, some people use it for that. But lock-free code is not that.
You may have lock-free code with locks, or lock-free code without data races, or lock-free code that can be shown to be incorrect (by your definition) yet work for the designed purpose...
That doesn't sound very lock-free?
I don't see how you can have that. If one process holding a lock halts then it will prevent system-wide progress, which is not allowed in the definition of 'lock-free'.
As others have mentioned already, if you had code that did that, that code would not be "lock-free". Lock-free requires progress in all circumstances even in the presence of ordering primitives (what we colloquially call "locks").
Are you replying to the right person? That's what I just explained to the person I was replying to. You've quoted part of my comment but left out the "...which is not allowed in the definition of 'lock-free'".
That doesn't sound right. I suppose you could have locks in the trivial sense, where it never actually blocks, but I don't imagine that's what you meant.
https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and...
https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFre...
This other blog post [0] seems to use a stricter definition of lock-free which precludes any way to schedule threads which would cause progress to cease indefinitely. That seems to be what the ConcurrencyFreaks blog refers to as Wait-free.
Any experts in lock-free programming able to clarify things?
[0] https://preshing.com/20120612/an-introduction-to-lock-free-p...
Given the context, and the confusion about what race conditions even are in some of the comments in the thread, I'd say the comment opened some good discussion. GP also provided examples of race conditions that are simple to reason about elsewhere in the thread, and also explained the difference between race conditions in general, and data races.
No, it defines race condition, for purposes of the article, as something which is a bug. The author is only concerned with cases in which non-deterministic behavior causes errors.
When you write your own article, you are free to define "race condition" to include non-deterministic behavior that does not cause errors. But I don't think you can claim that the author's usage is simply wrong.
Check out the EXAMPLES section of the manual page. You can use the mechanisms to inject delay on some percentage of executions, and more generally some integer value can be injected, which can be used to simulate device failures (EIO) or whatever.
It's very powerful for creating reliable reproducers for all kinds of failures, including race conditions. And the KPI is not quite as verbose as the one presented in TFA.
https://www.freebsd.org/cgi/man.cgi?query=fail&sektion=9