论文部分内容阅读
随着实时应用的不断深入,实时系统具有多种任务类型、约束复杂性、短暂超载等一些新的特点。为了适应这些新特点和新的要求,论文在分析了传统的常规可调度理论和方法的基础上,着重研究了现代可调度技术的新理论和新方法,特别对实时调度理论中的任务调度技术进行了研究。 针对实时系统具有多种任务类型的特点,为了满足系统可预测性要求,论文研究了周期任务请求的响应时间计算方法。针对固定优先级抢占式调度策略,提出了ACRik和HCRik算法。ACRik和HCRik根据CPU使用函数和负载生成函数计算请求的响应时间。针对抢占阈值调度策略,提出了CRFS算法。在CRFS中需先求出请求的开始执行时刻,然后采用忙周期分析法得到请求的响应时间。与已有方法相比,ACRik、HCRik和CRFS具有运行时间短,正确率高的优点。 针对约束复杂性的特点,论文对强实时任务的可调度性分析方法进行了扩展和补充。为了精确估计端到端任务中的后继子任务的最大释放抖动,针对抢占阈值调度策略和EDF抢占式调度策略,分别提出了强实时任务最小响应时间的计算方法。同时,针对这两种策略,还提出了具有释放抖动和特定释放偏移的强实时任务最大响应时间的计算方法WRPT和WREP。与已有方法相比,WRPT、WREP具有运行时间短的优点。 针对优先级数目受限的情况,论文研究了基于有限优先级的优先级分配问题,提出了相应的静态优先级分配算法AGP。同时,抽象出任务集合的特征,定义了初等任务集合,证明了AGP对该类任务集合是最优的。 针对短暂超载的特点,论文研究了采用跳跃因子模型和(m,k)模型降低系统负载的方法。研究了跳跃因子模型中的静态调度算法,提出了请求丢弃算法UDB。通过降低高优先级任务对低优先级任务的干扰时间,UDB提高了任务集的可调度性。研究了(m,k)模型中的动态调度算法,综合考虑了任务的状态和截止期限,提出了动态调度算法SEF,并分别给出了SEF算法可调度的必要条件和充分条件。与已有算法相比,SEF算法能降低动态失效的次数,并能提高资源利用率。 针对多处理器系统,论文深入分析了已有非周期任务的多处理器动态调度算法,提出了基于分组与适当选取策略的分组适度算法。在满足较小目标函数值的任务截止期限的情况下,分组策略优先扩展共享访问资源的任务,提高了资源的利用率。根据任务所需资源的最早可用时刻和系统中处理器的最早可用时刻的关系,适当选取策略将任务调度到适合的处理器上,提高了处理器的利用率。与已有算法相比,在任务的资源使用率较高时,分组适度算法具有较好的性能。