Scheduling Periodic Tasks On Realtime Multi-core Systems With Less Preemptions And Migrations

In recent years, real-time systems have been widely applied in many areas, e.g. aerospace, medical instruments, vehicles and so on. At the same time, with the revolution of semiconductor production technologies, multi-core CPUs have gained most of the market share. The scheduling algorithm is one of the key components of real-time systems, and how to improve the real-time scheduling performance in multi-core CPU has attracted much research attention. Existing multi-core scheduling algorithms, e.g. EKG and DPWRAP, have improved the utilization rate of multi-core CPU for periodic tasks. However, they still raise large number of task migrations and preemptions, which introduces high system runtime overhead and degrades system performance.In order to reduce the task migrations and preemptions and to further improve system performance, an original scheduling algorithm, D2_EDF is proposed in this thesis, which is based the time slice partitioning technology as well as CPU utilization rate calculation method of DP-WRAP scheduling algorithm and combined with task priority sorting technology of EDF scheduling algorithm, D2_EDF scheduling algorithm has adapted the resource pre-allocation technology, for each task, it will allocate time resource on each core, and during the time slice when a new task hasn't arrived, it will use EDF scheduling algorithm to schedule tasks on each core. D2_EDF has improved the idea of DP-WRAP as well as kept its advantages, e.g. the relative lese time slices and high CPU utilization rate. Also, it will react according to the current status of tasks, the resource pre-allocation technology in D2_EDF scheduling algorithm make it can react before the execution of tasks. In principle, for periodic tasks, compared with DP-WRAP scheduling algorithm, D2_EDF scheduling algorithm should have less task migration and preemption quantity; compared with DP-WRAP, EKG algorithm, D2_EDF doesn't have much difference in terms of scheduling cost. So D2_EDF algorithm can further reduce the whole cost in the system when guaranteeing the real-time performance.To evaluate the performance of D2_EDF algorithm, we developed a simulator which named RTScheduler Sim Core. It is developed by Python, and used Sim Py open source Python library to simulate the real-time scheduling on multi-core homogeneous system, also, it can be extended its functions very easily, for example, it can be extended to multi-core uniform system by adding more parameters for CPU core, and it can be added friendly user interface by using PyQt4 open source library. We use Rand Fixed Sum algorithm to generate task sets which we will use for the test. The test result on the simulator showed that D2_EDF has obvious improvement compared with DP_WRAP and EKG in terms of task migration and task preemption quantity for periodic tasks on the multi-core homogeneous system.