混合关键级调度的若干关键问题研究

发布时间：2019-05-17 09:29

【摘要】：以航空、汽车领域为代表的现代嵌入式实时系统,高安全标准的软件功能与其它非安全关键的软件功能共享一个嵌入式平台,以解决软件功能多样化、复杂化的需求与硬件平台受限SWa P(size weight and price)需求的冲突。此类系统的实时调度需同时满足两个目标:一是在相对保守的时间属性设定下,满足认证标准对涉及安全关键功能的验证要求;同时在较乐观的时间属性设定下,满足高效利用计算资源的设计要求。这类混合关键级系统的调度问题,无法使用传统的实时调度算法解决。混合关键级调度问题已成为嵌入式领域极富挑战的课题之一。本文基于混合关键级调度对安全关键与非安全关键任务的不同调度需求,以及高效利用资源的目标,分别研究了针对高、低关键级任务的不同调度策略。主要研究工作与成果如下:(1)基于事件触发系统关键级提升的实际情况,分析了高关键级任务的可调度性,得到了关键级提升期,高关键级任务可调度的充分条件。指出系统关键级提升的触发源于系统外部事件,基于响应时间分析技术,研究了关键级提升时刻对满足高关键级任务截止时限的影响;并据此,在关键级提升期,提出了一个有条件的优先级交换算法,可确保更多高关键级任务得到正确调度。仿真实验显示了可调度条件以及优先级交换算法的有效性。(2)提出了一种适合以截止时限为关键参数的混合关键级任务调度算法。定义了截止时限依赖于关键级的混合关键级任务模型,分析了关键级提升期低关键级任务对高关键级任务调度可能产生的干扰,以预先提升关键级的方式,牺牲有限的低关键任务,可始终满足高关键级任务随系统关键级动态变化的截止时限。仿真实验验证了预关键级提升算法适合以截止时限为关键参数的任务调度,且不受高关键级任务比率和截止时限变化程度的影响。(3)提出了一种适合同构多处理器平台上调度混合关键级任务的半局部调度算法。兼顾高关键任务利用率和低关键级任务可调度性,将全部高关键级任务和大部分低关键级任务固定在既定处理器上执行,仅有数量不超过处理器数目的低关键级任务成为迁移任务,能且仅能在相邻的两个处理器上发生迁移,并同步执行。以有限的迁移换取对处理器资源的高效利用,并总能满足高关键级任务的截止时限。仿真实验结果表明该半局部调度算法,相较于局部调度混合关键级任务的方法,将可调度任务比率提升了近10%。(4)提出了一种积极处理低关键任务的策略。对于符合标准认证的混合关键级系统,在关键级提升之后,回收多处理平台上执行中的空闲时段,以全局分配的方式匹配到被抛弃的低关键级任务,既不干扰局部调度的高关键级任务,又能让尽可能多的任务获得正确调度,以提升资源利用率。仿真实验与既有的TA、CD、CD-A算法比较,积极处理低关键级任务策略在系统可接受任务数目和抛弃任务比率上,均有明显优势。(5)提出了一种自适应回落系统关键级的闭环机制。基于实时任务在不同执行模式下实际执行时间的分布特性,监测高关键级任务的实际执行时间,预测高关键级任务利用率变化趋势与执行模式,可及时恢复调度此前关键级提升时被抛弃的低关键任务,且不影响高关键级任务的正确执行,实现安全降低系统关键级。仿真实验结果显示了自适应关键级回落算法优于至今被认为最优的BP方法。
[Abstract]:The modern embedded real-time system represented by the aviation and the automobile field, the software functions of the high security standard and other non-safety critical software functions share an embedded platform, so as to solve the problem that the software functions are diversified, Complicating demand conflicts with hardware platform limited SWa P (size and price) requirements. The real-time scheduling of such systems shall meet the two objectives at the same time: one is to meet the verification requirements for safety critical functions under the setting of relatively conservative time attribute; and at the same time, the design requirements of the high-efficiency utilization of the computing resources are met under the setting of a more optimistic time attribute. The scheduling problem of such hybrid key-level systems cannot be solved using the traditional real-time scheduling algorithm. The key-level scheduling problem has become one of the most challenging topics in the embedded field. In this paper, based on the different scheduling requirements of key-level scheduling for security and non-safety critical tasks, and the goal of efficient utilization of resources, different scheduling strategies for high and low key-level tasks are studied respectively. The main research work and results are as follows: (1) Based on the actual situation of the key-level improvement of the event-triggered system, the schedulability of the high-key task is analyzed, and the sufficient conditions for the scheduling of key-level and high-key tasks are obtained. It is pointed out that the trigger of the key-level improvement of the system is derived from the external event of the system. Based on the response time analysis technology, the influence of the key-level lifting time on the deadline for meeting the deadline of the high-critical-level tasks is studied. Based on this, a conditional priority switching algorithm is proposed in the key-level promotion period. Ensure that more critical-level tasks are properly scheduled. The simulation experiment shows the availability of the schedulable condition and the priority switching algorithm. (2) A hybrid key-level task scheduling algorithm, which is suitable for deadline-critical parameters, is proposed. The key-level task model of the critical-level task is defined, and the possible interference of the key-level task to the task scheduling of the high-critical stage is analyzed, so that the key-level task is improved in advance, and the limited low-key task is sacrificed. The deadline for critical-level tasks to dynamically change with system-critical levels can always be met. The simulation experiments prove that the pre-critical-level lifting algorithm is suitable for the task scheduling with the deadline as the key parameter, and is not affected by the high critical-level task ratio and the deadline change degree. (3) A semi-local scheduling algorithm is proposed for scheduling hybrid key-level tasks on a homogeneous multi-processor platform. in that invention, the high-key task utilization rate and the low-key-level task schedulability are taken into account, all high-critical tasks and most of the low-key-level tasks are fixed on a given processor, only a low-key-level task with a number of no more than the number of processors is the migration task, Can and can only be migrated on two adjacent processors, and can be synchronously executed. In exchange for efficient utilization of processor resources, the deadline for high-critical tasks can always be met. The simulation results show that the semi-local scheduling algorithm increases the schedulable task ratio by nearly 10% compared with the local scheduling hybrid key-level task. (4) A strategy to actively deal with the low-key task is put forward. for the hybrid key-level system with the standard authentication, after the critical level is improved, the idle time period in the execution in the multi-processing platform is recovered, the idle time period in the execution in the multi-processing platform is matched in a global allocation manner, the high-key task of the local scheduling is not interfered, It also allows as many tasks as possible to get the right schedule to improve resource utilization. The simulation experiment is compared with the existing TA, CD and CD-A algorithms, and the active processing of the low-key task strategy has a clear advantage in the number of acceptable tasks and the abandoned task ratio of the system. (5) A closed-loop mechanism for adaptive back-down system is proposed. based on the distribution characteristics of the actual execution time of the real-time task in different execution modes, the actual execution time of the high-key-level task is monitored, the trend and the execution mode of the high-key-level task utilization rate are predicted, and the low-key task which is abandoned when the key-level improvement in the scheduling is timely recovered, And the key level of the safety reduction system is realized. The simulation results show that the self-adaptive critical-level back-down algorithm is better than the BP method which is considered to be the best.
【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】