混合关键系统半划分调度算法研究

Research on semi-partition scheduling algorithm for mixed-criticality systems

混合关键系统是现代嵌入式系统发展的主要趋势之一,其中高关键任务代表紧急度高或者重要程度高的实际任务,往往需要优先保证.为了保证高关键级别任务的执行,当前的混合关键任务调度算法中常常存在对低关键级别任务采用丢弃或者调度不及时的现象,造成在关键级别转换时,任务丢失时限率较大且系统利用率较低.为此,本文在具有双重关键级别的混合关键系统中,对EDF-os半划分调度算法进行改进.首先,在划分阶段,将高关键级别的任务作为固定任务,低关键级别的任务按照利用率使用Worst-Fit策略进行划分.其次,在执行阶段,采用job边界迁移形式,并详细讨论了在不同系统关键级别之下,不同关键级别任务优先级确定的策略,根据优先级对任务进行调度执行.最后,模拟具有双关键级别的多处理器混合关键系统,随机产生任务集进行仿真实验,结果表明,该方法使得低关键级别任务的可执行比例平均提升了14.8%,任务丢失时限率降低了19.7%.

Mixed-criticality system is one of the main trends in the development of modem embedded systems.The high critical task represents the practical task with high urgency or importance,which usually needs to be guaranteed first.In order to ensure the execution of high-level critical tasks,the current mixed critical task scheduling algorithms often discard or schedule low-level critical tasks in a timely manner.As a result,the task loss time limit rate is large and the system utilization rate is low during the critical level conversion.Therefore,the EDF-os semi-partition scheduling algorithm is improved in hybrid critical systems with dual critical levels.First,in the division phase,the tasks at high critical levels are treated as fixed tasks and the tasks at low critical levels are divided by utilization using the Worst-Fit policy.Secondly,in the execution phase,the form of job boundary migration is used,and the strategies for determining the priority of tasks at different critical levels under different system critical levels are discussed in detail,and tasks are scheduled according to the priorities.Finally,a multi-processor hybrid critical system with dual critical levels is simulated,and task sets are randomly generated for simulation experiments.The results show that the proposed method increases the executable ratio of low-critical level tasks by 14.8%on average,and decreases the task loss time rate by 19.7%.