Research On Virtual Machine Based Deterministic Execution Of Multi-core System

With the development of multi-core technology, the development of operating systems on multi-core hardware is becoming the basis of most current parallel or multithreaded programs. Traditional multithread is actually an abstraction of the execution time division on a single core processor by operating systems, while the multi-core technology is a real concurrency for multi-threaded programs. Nevertheless, multithreaded programs bring the serious problem of non-determinism, which has a significant impact on the correctness of the multithreaded programs and is a great challenge for the debugging and security of those programs. Therefore, it has become a hotspot for researchers all over the world to solve the non-determinism problem and make it useful for the fields of debugging, security, etc.Nowdays, the debugging technology for operating systems on multi-core is still young. Those hardware based debugging technology still have lots of problems, such as complicated configuration and the difficulty on the replay of heisenbugs. Therefore, to address the non-determinism problem of the software developed on multi-core hardware, this paper made a research on the virtual machine monitor based deterministic execution and debugging of multi-core systems.To address the non-determinism of multi-core systems' execution, this paper based on SMP virtual machines, proposed an abstract of deterministic concurrent state machine. With this deterministic concurrent state machine, the execution of a SMP virutal machine can be divided into two parts--internal and external parts. Based on the characteristics of internal and external non-deterministic behaviors, diferent controls are taken for each part, which will finally deterministic controls and maintains the execution state of whole system and ensures the controlability of a multi-core system.To address the internal non-determinism of a SMP virtual machine, this paper based on shadow page table machanism, proposed a virtual private memory model. This model ensures the parallelism of several virtual CPUs, while at the same time maintains the synchronization and the determinism of virtual CPUs' state and memory's state. To address the external non-determinism of a SMP virtual machine, this paper based on the virtual private memory model, taking advantage of the record-and-replay technology and two deterministic execution algorithms, proposed two mechanisms--strict deterministic execution mechanism and relax deterministic execution mechanism. The tests results show that the overheads are acceptable in the case of proper chosen parameters for about 50%.Based on the deterministic execution of multi-core systems, this paper further proposed a debugging technology for operating systems, which can make a reverse debugging for the whole parallel system. According to the features of deterministic concurrent state machine, we proposed a coordinated controlable method based on parallel single step state point for the reverse debugging of multi-core systems. The parallel single step state point utilized the conditions of the states' transition to help programmers have a direct grasp on the whole system, shrink the range of the bugs' positions and finally improve the efficiency of debugging. According to the experiment results, the overheads are less when running in multi-checkpoint mode for raw format virtual machine images.