A preemptive deterministic scheduling algorithm for multithreaded replicas
Claudio Basile, Zbigniew Kalbarczyk, Ravi K. Iyer · 2004
Software-based active replication is expensive in terms of performance overhead. Multithreading can help improve performance; however, thread scheduling is a source of nondeterminism in replica behavior. This paper presents a Preemptive Deterministic Scheduling (PDS) algorithm for ensuring deterministic replica behavior while preserving concurrency. Threads are synchronized only on updates to the shared state. A replica execution is broken into a sequence of rounds and in a round each thread can acquire up to two mutexes. If a thread cannot acquire a mutex it requests, then it checks if all other threads are suspended. If so, the thread fires a new round; otherwise, the thread is suspended. When a new round fires, all threads' mutex requests are known; thus, it is possible to form a deterministic scheduling of mutex acquisitions in the round. No inter-replica communication is required. The algorithm is formally specified, and the proposed formalism is used to prove its correctness. Failure