-1

Suppose we are in a distributed environment, and mutual exclusion is not implemented yet. So how would we be able to detect race conditions?

When I researched, use of non-blocking algorithms was found as a solution. That is using datastructures like stack, queue, etc. So that we could avoid mutual exclusion.

But how do we detect it?

  • 4
    I thought mutual exclusion as a tool for avoiding race conditions, not for detecting them. So are you really after a method to detect race conditions, or do you just want to avoid them? – Doc Brown Dec 23 '13 at 13:43
8

Anomalous behavior. Like inconsistent updates. Like deadlocks. Like strange things happening.

Unfortunately, debugging anomalous behavior is DIFFICULT. You have no way of knowing, other than experience, whether you are dealing with a race condition, or something more mundane.

This is why you design race conditions out, at the very beginning. This is why you design mutual exclusion, or something else that accomplishes similar ends, into your system, from the very beginning.

This is also why operating systems used to be a required class. It was the one that taught you about concurrency issues, including race conditions, deadlock, and the need for mutual exclusion.

  • 1
    Without mutual exclusion, you can't get deadlocks (as threads/processes won't be waiting on each other). – Bart van Ingen Schenau Dec 23 '13 at 13:34
2

There is a race condition whenever there is a possibility of a resource accessed by two or more entities simultaneously. Access implies,

If a read/write happens simultaneously as follows

| Thread A  | Thread B | Problem?                                        |
--------------------------------------------------------------------------
|    Read   |  Read    | No                                              |
|    Read   |  Write   |There is a problem if A reads an obsolete value  |
|    Write  |  Read    |There is a problem if B reads an obsolete value  |
|    Write  |  Write   | There IS a problem. The final value will        |
|           |          | depend upon the last value written/over written |

Before Execution:

To pinpoint this in a piece of code one needs experience to understand if the resource will be modified in such a manner You need to think in all possible direction and develop test cases for the same

After (Several) Executions:

You need to keep an eye open for any unexpected/unexplained output. There are chances the problem lies somewhere else but you need to check if there is simultaneous access occurring somewhere in the code

  • I wonder if it would be possible to design a Java virtual machine which would keep track of which variables had been read or written by which threads, and trigger an alarm if a method which wasn't tagged with a special attribute accessed a variable sued by another thread without a proper "occurs after" or "occurs before" relation. I would guess such a VM would probably be 1-2 orders of magnitude slower than a "normal" one, but could probably make code which would normally fail 0.000001% of the time instead fail often. Any idea if any such thing exists? – supercat Dec 23 '13 at 19:35
  • @supercat glance at Clojure with STM (Software Transactional Memory). Take a look at the example for clojure - one need not have a different machine at all. – user40980 Dec 23 '13 at 19:53
  • 1
    @MichaelT: My question was whether it would be possible to have an implementation of a "mainstream language" such as Java which would be designed to--to the extent possible--make it so that code which could fail, would generally do so quickly. To use an analogy, on the old Mac OS, for example, many system calls were allowed to move any relocatable allocated memory blocks that weren't pinned, but would seldom if ever do so. A program called Discipline was available, however, which would cause every such system to randomly relocate everything which it legally could. Code which... – supercat Dec 23 '13 at 20:04
  • ...failed to pin a handle before calling a method which only needed to temporarily allocate a few bytes might work 99.999999% of the time when not running Discipline, but would fail almost immediately with it running. Discipline made everything run really slowly, but running a method once with Discipline running could do more to validate correctness than running it 100x without. I wonder if anything similar exists for something like the JVM, which has clear rules on what code is and is not allowed to do with regard to threading. – supercat Dec 23 '13 at 20:06
  • 1
    As to the table, there are additionally "read modify write" types of problems. For example, incrementing a shared integer counter without locking or using atomic instructions. And then there are so-called ABA types of problems even if atomic instructions are used. – rwong Oct 16 '16 at 9:53
1

Assuming you don't want to really detect race conditions (which IMHO hard with or without mutual exclusion available), but just want to avoid them: if your system does not provide you with some kind of Mutex out-of-the-box, you can implement your own. Wikipedia currently list five different algorithms (for a software solution), just pick your favorite one. Of course, Wikipedia also states that these algorithms don't work in an out-of-order execution environment, bat that's a special issue of your hardware and the compiler you are using.

0

Race conditions will be with us as long as people create software programs.

No best practices will completely guard you from race conditions, because correct use of best libraries and best practices still involves humans and a human cognitive error on all the stages, design, implementation, test, support.

We used the following principles:

First: We have learned that your best friend is a sophisticated dynamic analysis tool that is always on, analyzing every execution of your application. (Think of time and energy conservation. Why to waste the energy of software process execution?)

Second: Make your user to be your tester. I.e. release the product with an agent that performs the analysis at run time. That will shorten the time to market, as you will have the assurance that any missed during the tests race condition will be analyzed in real time and you will know about it before the user will.

Third: Make the issues identified by the agent come to your console in real time.

Forth: Make your agent perform complete and detailed analysis in real time and completely automatically. Then you will never have to worry about programmer not making incorrect analysis, even if your programmer was lucky to recreate race condition (often a very difficult proposition). Microsoft's research shows that over 30% of analysis of (detected) race conditions (by humans) was done incorrectly.

Fifth: If the analysis is captured alone with the dynamic information of the system, you will never have to worry about being able to reproduce the issue.

Six: 100 agents are less expensive and more reliable that 100 human testers. So if your console receives aggregated results from 100 (or more) agents, your Time-To-Market component affected by your testing just got 100 (or more) times shorter.

And Seven: If the analysis by the agent is explained on the level of source code, (while the agent actually analyses bytecode and no source code is provided or available at the time of the analysis) your "Black Box Testers" become "White Box Testers" overnight.

PS: This is not just an opinion, but a personal experience afforded by using the tools built by TinkingSoftware.com

Disclaimer: I would not be able to provide such detail answer if I was not involved in building and using this tool, "Race Catcher", and this service, "ARM-CM", standing for Application Reliability Monitoring via Collaborating Machines.

  • This does sound like a bit of an ad. But it's well written and does actually answer the question concerning detecting race conditions. – Tersosauros Oct 17 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.