Scheduling

Random Number Generator

Every time that the simulation framework or program must make a choice, it derives its decision from the random number generator. By doing this, starting with the same seed will result in the same program execution, every time. This is the one simple rule that provides determinism.

class RNG {
 public:
  uint64_t random();

 private:
  std::mt19937_64 gen64;
};

extern RNG globalRng;

Async Framework

Concurrency may be expressed with any form of cooperative scheduling: a language’s native async/await implementation, a futures or coroutine library, or stateful objects and callbacks (in decreasing order of user friendlyness). Even the proposed switchTo/FUTEX_SWAP for directly scheduling native threads can work. It does not matter what language or library is used; all that matters is that you, the developer, are in control of which work runs in what order.

class Task {

}

The Ready Queue

Our next component is the queue of ready work to execute.

class ReadyQueue {
 public:
  void enqueue(Task&& t) {
    m_tasks.push_back(std::move(t));
  }

  Task dequeue() {
    size_t index = globalRng.random() % m_tasks.size();
    Task toRun = std::move(m_tasks[index]);
    m_tasks.erase(m_tasks.begin() + index);
    return toRun;
  }

 private:
  std::vector<Task> m_tasks;
};

Returning to the Scheduler: yield()

Scheduling Future Work: sleep()

Putting It Together

Alternatives

Though the scheduler is the most vital requirement for deterministic simulation, implementing the rest of this guide will instead provide non-deterministic simulation. Instead, one can attempt to recover the deterministic execution by relying on rr, a tool which can record the execution of a program and allow that exact execution to be replayed any number of times. rr can provide deterministic replay, but will execute slower, but has a number of limitations, and won’t allow you to recompile for printf debugging.

If trying to retrofit simulation onto an existing architecture of multiple processes (or multiple languages) seems overly daunting, one can give money to Antithesis, who have taken the approach of making the entire OS deterministic, and offer a minimal SDK for integration.