一种有约束关系的实时周期任务调度算法研究

Research on a Real-time Scheduling Algorithm for Periodic Task with Constraint Relation

在多核嵌入式平台下,针对具有约束关系的实时周期任务,提出一种基于任务关键因子和截止时间的调度算法BVDS(Based on Value and Deadline Scheduling)。该算法以有效利用处理器为原则,根据每个处理器的实际运行情况,为有可能在截止时间前完成的任务分配处理器资源。算法实现分为两个阶段:第一阶段根据任务的到达时间、关键因子以及执行时间构建等待任务链表;第二阶段,在执行过程中,充分考虑不同任务的执行时间以及任务之间的约束关系进行优先级分配。实验结果表明,该算法在牺牲少量处理器利用率的前提下,有效地降低了任务的死限丢失率。

In this paper,propose a scheduling algorithm BVDS （based on value and deadline sc-heduling） for periodic task with con- straint relation in mutli-core embedded platform. In principle of effective utilization of processor resources, only tasks that are possible to be done before deadline can be assigned to implement. The process of BVDS can be organized into two phrases. In the first phrase, a wait- ing job list is constructed according to the release time, value and execution time of each job. In the second phrase, dynamically adjust the priority of each job according to its predecessor job and the availability of each processor. Simulation results show that BVDS algorithm can effectively reduce the deadline miss-ratio of tasks,