Abstract: In the environment of Xen virtual machine based on the SMP system with two or more physical CPU cores, the current virtual machine scheduling algorithms make all virtual CPUs be scheduled independently and do not consider the co-scheduling relationship of guest OS virtual CPUs, which leads to too much deviation of timer interruptions among virtual CPUs and so on, which causes the decline of guest OS stability. According to the problem, a more relaxed co-scheduling algorithm of virtual CPUs on Xen virtual machines than the relaxed co-scheduling one is given. It adopts a non-preemptive co-scheduling method to restrain relative running time of virtual CPUs between 0 and the upper limit to co-scheduling time detection T\-max. And it makes virtual CPUs co-scheduling more quickly and physical CPUs load more balanced by the method of optimized selection of virtual CPU and the method of dynamic migration of virtual CPUs in Credit. Meanwhile it reduces the whole virtualization systems overhead further. The experimental results show that the method ensures the stability of the virtualization system, and it improves the performance of virtual machines to a certain extent. The scheduling algorithm of virtual machines has the direct effect on the performance and stability, and it is a significant job to go into scheduling algorithms of virtual machines.