Course contentsShow
← Computer Science
Lesson 1272 of 2,87230. Process SynchronizationFree lesson

Interleaving and Non-Determinism

Learning how different execution orders of instructions lead to unpredictable outcomes in concurrent programs.

Interleaving and Non-Determinism

You'll learn why concurrent programs can produce different results each time they run, even with the same input.

When multiple threads or processes share data, the CPU scheduler decides which instruction executes when. This creates interleaving—different possible orderings of instructions from concurrent execution paths.

The Core Problem

Imagine two threads both incrementing a shared counter. Thread A reads the counter (value: 5), Thread B reads it (still 5), Thread A writes 6, Thread B writes 6. Final result: 6, not 7!

But run it again, and the scheduler might let Thread A finish completely before Thread B starts. Now the result is 7.

Same program + same input = different outputs. This unpredictability is called non-determinism.

Why This Happens

The scheduler can pause a thread at any instruction. If Thread A has three steps (read, add, write) and Thread B has three steps, there are many valid interleavings:

  • A₁, A₂, A₃, B₁, B₂, B₃ (sequential)
  • A₁, B₁, A₂, B₂, A₃, B₃ (alternating)
  • A₁, B₁, B₂, B₃, A₂, A₃ (mixed)

Each ordering may produce different results if they touch shared data.

The Analogy

Think of two people editing the same document simultaneously without tracking changes. Person A reads line 10, Person B reads line 10, both make edits, both save—whoever saves last overwrites the other's work. The outcome depends on timing, not logic.

Key Takeaway: Interleaving creates non-determinism in concurrent programs because the scheduler can order instructions in many valid ways, leading to unpredictable outcomes when threads share data without coordination.