Research And Implementation Of MDSF-A Deterministic Scheduling Framework Of Multithreading Replication System

Replication is an important approach in fault-tolerant distributed systems. Multithreading replication makes good use of multi-core CPU, multi-CPU resources, but also faces the problem of how to ensure determinism. At present several multithreading scheduling algorithms to some extent support multithreaded operation, but they all adopt a conservative method to avoid the non-determinism brought from multithreading, resulting in a bad effect upon concurrency of multithreading.Having analyzing the existing multithreading scheduling algorithms, this paper proposes an advanced algorithm based on MAT algorithm. The future knowledge of synchronized actions of the multithreads in the run time is a must to the advanced algorithm. This paper presents code analysis and code transformation as a new method to achieve this purpose. At the same time, code analysis and code transformation is also able to perform the interception of the synchronization statements, thus transparently modify the non-replicated code to replicated code. This method can avoid modification of the underlying operating system, virtual machine, and manually modification of the code is not required.In this paper, MDSF, a deterministic scheduling framework is introduced. It consists of two parts, one is the source code analysis and transformation module working in pre-compiled phase and the other is the multithread scheduling module operating in running time. The former performs a code analysis upon the multithreaded source code, and a code transformation based on the analysis the results. The transformed code is deployed to the environment to work with the multithread scheduling module, which implements AMAT algorithm and will carry out a unified multithread scheduling. Proven by test, the scheduling framework supports the reuse of the existing non-replicating code, and can realize high-performance multithreaded scheduling.