多处理器系统实时任务限制抢占调度算法
Real-Time Task Limited Preemptive Scheduling on Multi-processors
-
摘要: 针对多处理器平台完全可抢占调度(Fully Preemptive Scheduling,F-PS)可能造成低优先级任务的响应时间超出截止期限的问题,提出了两种基于固定抢占点模型的限制抢占调度算法:一种是常规延迟(Regular Deferrable Scheduling,RDS),即高优先级任务抢占正在运行的执行到最近抢占点的低优先级任务,被抢占的任务可能不具有最低优先级;另一种是自适应延迟(Adaptive Deferrable Scheduling,ADS),即高优先级任务等待正在运行的最低优先级任务执行到最近的可抢占点位置,并抢占。搭建了一个仿真实验平台,并在该平台上进行一系列的仿真实验来探究两种算法的性能表现。实验结果表明:在动态和静态优先级调度下,任务抢占次数大小顺序为F-PS > RDS > ADS;当抢占时间消耗大于临界值时,RDS和ADS的任务可调度率与F-PS接近。Abstract: In multi-processors scheduling,fully preemptive scheduling (F-PS) may result in the tasks with lower priority beyond the deadline.In this work,two limited preemptive scheduling (LPS) algorithms are proposed to solve the above problem.The first one is regular deferrable scheduling (RDS),in which the tasks with higher priority preempt the first among the lower priority tasks that finish executing a non-preemptive region.The other is adaptive deferrable scheduling (ADS),where the scheduler waits to preempt the lowest priority running task.A series of experiments are carried out via the built simulator to investigate the performance of the two LPS,which show:(1) the number of preemptions in dynamic and static scheduling is F-PS > RDS >ADS;(2) the schedulable ratios of RDS and ADS are almost equal to the one of F-PS when the time consuming in preemptions is bigger that the threshold.