Partitioned Fixed-Priority Real-Time Scheduling Based on Dependent Task-Split on Multicore Platform

摘要

Most real-time multicore scheduling algorithms ignore intra-task relationships, which cannot meet all deadlines by placing severe restrictions upon sequential programming models. Moreover, no partitioned algorithms can have a utilization bound over 50%. In this paper, a partitioned fixed-priority real-time scheduling based on dependent tasks-split on homogeneous multi-core platform is proposed, namely BDTD/TS (B-tree Dependent Task Dispatching/Task Splitting). BDTD converts dependent tasks into a series of sequential jobs and obtains the interrelated subtasks path as well as synthetic deadlines through the B-tree task model. Then in BDTS, dependent task in idle-wait state is qualified to split and all blocked sub-tasks would preempt CPU immediately to guarantee deadlines. With regard to utilization bound analysis, the new algorithm is proved to offer superior performance guarantee 69.31%. The simulations and experimental results prove that the proposed algorithm provides high practicability and efficiency.