multithreading - 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

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.