Can we have race conditions in a single-thread program?

Question

You can find on here a very good explanation about what is a race condition.

I have seen recently many people making confusing statements about race conditions and threads.

I have learned that race conditions could only occur between threads. But I saw code that looked like race conditions, in event and asynchronous based languages, even if the program was single thread, like in Node.js, in GTK+, etc.

Can we have a race condition in a single thread program?

Answer 1

Finite state machines running in a single thread should have neither race conditions nor data races:

Single threaded code can have race conditions due to unaccounted for order of events. (You are in an unanticipated and inexplicit state). But they cannot have data races (Incompatible changes to a structure by simultaneous threads). You could however have something approaching a data race with insufficient encapsulation of a data structure.

Finite state machines should not have race condition because any event order's produced st state should be accounted for. It could have a data race if it can be modified by simultaneous access by another thread.

Answer 2

Sure can. Disk I/O runs asynchronously. If you fire off disk IO and go do something else and fire off more disk IO you can eventually fill the hardware's internal command queue and get a "no" back. Gotta handle the disk IO hasn't finished by the time you want to do more disk IO even if the data rates say you have ten times as much time as you need.

Source: I have an SD card with a slow spot. Writing to it takes many times longer than expected. I lost a race condition.

Answer 3

All examples are in a fictional language very close to Javascript.

Short:

1. A race condition can only occur between two or more threads / external state (one of them can be the OS). We cannot have race conditions inside a single thread process, non I/O doing program.

2. But a single thread program can in many cases :

   1. give situations which looks similar to race conditions, like in event based program with an event loop, but are not real race conditions

   2. trigger a race condition between or with other thread(s), for example, or because the execution of some parts of the program depends on external state :

      1. other programs, like clients
      2. library threads or servers
      3. system clock

I) Race conditions can only occur with two or more threads

A race condition can only occur when two or more threads try to access a shared resource without knowing it is modified at the same time by unknown instructions from the other thread(s). This gives an undetermined result. (This is really important.)

A single thread process is nothing more than a sequence of known instructions which therefore results in a determined result, even if the execution order of instructions is not easy to read in the code.

II) But we are not safe

II.1) Situations similar to race conditions

Many programming languages implements asynchronous programming features through events or signals, handled by a main loop or event loop which check for the event queue and trigger the listeners. Example of this are Javascript, libuevent, reactPHP, GNOME GLib... Sometimes, we can find situations which seems to be race conditions, but they are not.

The way the event loop is called is always known, so the result is determined, even if the execution order of instructions is not easy to read (or even cannot be read if we do not know the library).

Example:

setTimeout(
  function() { console.log("EVENT LOOP CALLED"); },
  1
); // We want to print EVENT LOOP CALLED after 1 milliseconds

var now = new Date();
while(new Date() - now < 10) //We do something during 10 milliseconds

console.log("EVENT LOOP NOT CALLED");

in Javascript output is always (you can test in node.js) :

EVENT LOOP NOT CALLED
EVENT LOOP CALLED

because, the event loop is called when the stack is empty (all functions have returned).

Be aware that this is just an example and that in languages that implements events in a different way, the result might be different, but it would still be determined by the implementation.

II.2) Race condition between other threads, for example :

II.2.i) With other programs like clients

If other processes are requesting our process, that our program do not treat requests in an atomic way, and that our process share some resources between the requests, there might be a race condition between clients.

Example:

var step;
on('requestOpen')(
  function() {
    step = 0;
  }
);

on('requestData')(
  function() {
    step = step + 1;
  }
);

on('requestEnd')(
  function() {
    step = step +1; //step should be 2 after that
    sendResponse(step);
  }
);

Here, we have a classical race condition setup. If a request is opened just before another ends, step will be reset to 0. If two requestData events are triggered before the requestEnd because of two concurrent requests, step will reach 3. But this is because we take the sequence of events as undetermined. We expect that the result of a program is most of the time undetermined with an undetermined input.

In fact, if our program is single thread, given a sequence of events the result is still always determined. The race condition is between clients.

There is two ways to understand the thing :

• We can consider clients as part of our program (why not ?) and in this case, our program is multi thread. End of the story.
• More commonly we can consider that clients are not part of our program. In this case they are just input. And when we consider if a program has a determined result or not, we do that with input given. Otherwise even the simplest program return input; would have a undetermined result.

Note that :

• if our process treat request in an atomic way, it is the same as if there was a mutex between client, and there is no race condition.
• if we can identify request and attach the variable to a request object which is the same at every step of the request, there is no shared resource between clients and no race condition

II.2.ii) With library thread(s)

In our programs, we often use libraries which spawn other processes or threads, or that just do I/O with other processes (and I/O is always undetermined).

Example :

databaseClient.sendRequest('add Me to the database');

databaseClient.sendRequest('remove Me from the database');

This can trigger a race condition in an asynchronous library. This is the case if sendRequest() returns after having sent the request to the database, but before the request is really executed. We immediately send another request and we cannot know if the first will be executed before the second is evaluated, because database works on another thread. There is a race condition between the program and the database process.

But, if the database was on the same thread as the program (which in real life does not happen often) is would be impossible that sendRequest returns before the request is processed. (Unless the request is queued, but in this case, the result is still determined as we know exactly how and when the queue is read.)

II.2.i) With system clock

@mingwei-samuel answer gives an example of a race condition with a single thread JS program, between to setTimeout callback. Actually, once both setTimeout are called, the execution order is already determined. This order depends on the system clock state (so, an external thread) at the time of setTimeout call.

Conclusion

In short, single-thread programs are not free from trigerring race conditions. But they can only occur with or between other threads of external programs. The result of our program might be undetermined, because the input our program receive from those other programs is undetermined.

Answer 4

Yes.

A "race condition" is a situation when the result of a program can change depending on the order operations are run (threads, async tasks, individual instructions, etc).

For example, in Javascript:

setTimeout(() => console.log("Hello"), 10);
setTimeout(() => setTimeout(() => console.log("World"), 4), 4);

// VM812:1 Hello
// VM812:2 World

setTimeout(() => console.log("Hello"), 10);
setTimeout(() => setTimeout(() => console.log("World"), 4), 4);

// VM815:2 World
// VM815:1 Hello

So clearly this code depends on how the JS event loop works, how tasks are ordered/chosen, what other events occurred during execution, and even how your operating system chose to schedule the JS runtime process.

This is contrived, but a real program could have a situation where "Hello" needs to be run before "World", which could result in some nasty non-deterministic bugs. How people could consider this not a "real" race condition, I'm not sure.

Data Races

It is not possible to have data races in single threaded code.

A "data race" is multiple threads accessing a shared resource at the same time in an inconstant way, or specifically for memory: multiple threads accessing the same memory, where one (or more) is writing. Of course, with a single thread this is not possible.

This seems to be what @jillro's answer is talking about.

---

Note: the exact definitions of "race condition" and "data race" are not agreed upon. But if it looks like a race condition, acts like a race condition, and causes nasty non-deterministic bugs like a race condition, then I think it should be called a race condition.

Answer 5

Race conditions can occur with any system that has concurrently executing processes that create state changes in external processes, examples of which include :

• multithreading,
• event loops,
• multiprocessing,
• instruction level parallelism where out-of-order execution of instructions has to take care to avoid race conditions,
• circuit design,
• dating (romance),
• real races in e.g. the olympic games.