多核平台两级抢占式固定优先级DAG递归调度

Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms

为提高应用程序调度实时性,提高程序调度应用价值,采用有向无环图(DAG)建立多核平台上的并行和递归任务的集合,获得具有优先级约束(即有向边)的子任务(即节点),并保证在某个指定的截止日期之前完成其所有子任务的执行.每个任务都可能生成无限数量的实例,其中连续实例的发布被一些最小到达时间隔开.同时,DAG任务的每个子任务被分配一个固定优先级,提出一种两级抢占式全局固定优先级调度(GFP)策略:任务级调度器首先确定最高优先级就绪任务,然后,子任务级调度器选择其最高优先级子任务来执行.然后,为所提两级GFP调度器推导出一个可调度性测试,如果满足该测试则保证所有任务在GFP下满足其最后期限.最后,通过实验分析,验证了所提算法在接受率指标上的性能优势。

For real-time application scheduling,directed acyclic graph(DAG)is used to set up a set of parallel and recursive tasks on multi-core platforms to obtain sub-tasks(i.e.nodes)with priority constraints(i.e.directed edges)and to ensure that all the sub-tasks are executed before a specified deadline.Each task may generate an.unlimited number of instances,in which the publication of successive instances is separated by some minimum arrival time.At the same time,each sub task of the DAG task is assigned a fixed priority.A two-level preemptive global fixed priority scheduling(GFP)strategy is proposed.The task-level scheduler first determines the highest priority ready task,and then the sub-task-level scheduler selects its highest priority sub-task to execute.The sub task level scheduler then selects its highest priority sub task to perform.Then,a schedulability test is derived for the proposed two-level GFP scheduler,which guarantees that all tasks meet their deadlines under GFP.Finally,through experimental analysis,the performance advantage of the proposed algorithm on acceptance rate index is verified.