本文共 961 字,大约阅读时间需要 3 分钟。
本文研究的调度算法是基于可抢占、优先级驱动的前提,包括静态优先级(固定优先级)和动态优先级。
周期任务的描述,定义第i个任务描述
为任务的周期,为任务的执行时间,请求速率定义为周期的倒数。
调度算法中一个关键的概念是任务的critical instant(关键时刻)。
基于以上概念,推导定理:
Theorem 1:当任务发出请求的同时,所有高优先级的任务也发出请求,认为此时刻为critical time。
Theorem 2:对于一个静态优先级的任务集,如果存在可执行的调度算法,那么对于RM调度算法,该任务集一定可以调度。
Theorem 3:对于两个固定优先级的任务,其CPU资源利用率上界为 。
Theorem 4:对于m个具有固定优先级的任务集,其CPU资源利用率上界为
Liu C L , Layland J W . Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment[J]. Journal of the ACM, 1973, 20(1):46-61.
转载地址:http://jrkai.baihongyu.com/