an intuitive formal proof for deadline driven scheduler

United Nations University, Int. Inst. for Softw. Technol., China; Vietnam National University, Hanoi, Vietnam; Vietnam Academy of Science and Technology, Vietnam

一种静态最少优先级分配算法

随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.

一种新的基于优先级表的实时调度算法

本文提出了一种新的基于优先级表的实时调度算法 ,称作截止期—价值密度优先 (Deadline ValueDen sityFirst)算法 ,简称DVDF算法 .DVDF算法综合考虑了实时任务的截止期和价值密度两个参数 ,能够更好地适应不同的负载情况 .通过使用正常负载和过载情况下的典型数据对算法进行仿真研究表明 ,这种算法比单纯考虑截止期的EDF(EarliestDeadlineFirst)算法在性能方面有明显的改进 ,特别是在系统过载的情况下 ,能够优雅地降级