Similarity-Based Resource-Aware Partition Scheduling Algorithm For Multi-Processor Real-Time System

With the development of technology,single-core processors have not been able to meet the growing computing demands,and multi-core technology is rapidly developing and becoming the mainstream of the market.Task scheduling is one of the most important problem that multi-core real-time systems must handle.The mainstream multi-core real-time system scheduling methods are mainly divided into two: global scheduling and partition scheduling.Without overhead caused by task migration partition scheduling is becoming the mainstream strategy in the application.However,in the existing research,the partitioning algorithm for tasks with resource access is insufficient for the optimization of resource competition cost between tasks,and the performance of decision-making between task resource similarity and load balancing is poor.Therefore,designing the resource-aware algorithm based on similarity on homogeneous multi-core systems has its theoretical and practical significance.Based on the Partitioned-EDF scheduling algorithm and the task model of MSRP(Multiprocessor Stack Resource Policy)protocol,an effective similarity and resourceaware task partitioning algorithm SR-TPA(Similarity-based Resource-aware Task Partitioning Algorithm)is proposed.The algorithm accurately defines the similarity and utilizes some characteristics of K-means clustering,the load balancing problem that may be caused during task partitioning also is paid enough attention.In addition,the trade-off factor is introduced to reconcile the similarity and load to get the higher system's schedulable ratio.Specifically,in the selection task part,a more optimal dynamic estimation and sort of the estimated utilization is performed.Then,the processor core with the highest similarity but not overloading the load is selected,and the tasks are assigned to the optimal core to acquire higher schedulable ratio.A large number of experimental results show that because of the SR-TPA's degradation under the values of two extreme trade-off factors,the system's schedulable ratio is not monotonous with the trade-off factor.Besides,the SR-TPA algorithm generally achieves a higher schedulable ratio,and this advantage is more pronounced when system environment become constrictive.