论文部分内容阅读
把具有不同关键等级的多个功能集成于同一嵌入式计算平台，以平衡系统中越来越复杂的功能与受限的计算资源、硬件尺寸、功耗以及成本等资源之间的矛盾，是当代嵌入式系统发展的重要趋势。这种系统被称为混合关键级系统。在混合关键级系统的调度中，一方面需要充分考虑功能的关键等级，通过保证具有较高关键等级的功能的及时完成，以满足系统的安全性和可靠性要求，另一方面需要通过对系统资源的有效配置，优化具有低关键等级的功能调度，以提升系统的整体性能。传统的实时调度理论无法有效解决这一问题，因此，研究混合关键级系统的优化调度机制成为了当前实时调度领域中的一个热点问题。
本文以混合关键级系统为研究对象，以在满足系统可靠性的前提下提升系统整体性能为目标，研究混合关键级系统优化调度问题。从模型、作业调度、任务调度、任务划分、任务迁移等角度，采用需求边界函数分析、利用率分析、概率和期望计算、可调度性分析以及关键因子分析等方法，研究混合关键级优化调度的机制和算法问题。主要的研究工作与成果如下：
(1)提出以动态需求边界优化混合关键级作业调度的算法
针对混合关键级作业调度中，系统关键级向下切换机制不灵活导致的低关键级作业被大量丢弃和系统计算资源无法被充分利用的问题，提出了混合关键级作业的动态需求边界函数DDBF(Dynamic Demand Boundary Function)概念，充分考虑了作业的实时属性与关键级属性，以及作业在运行时的执行情况，动态的从多维度描述作业的需求边界。以之为基础，定义了关键级松弛时间的概念，并提出了一种混合关键级作业的关键级动态切换算法CSDDB(Criticality Switch based on Dynamic Demand Boundary)，选取具有最小松弛时间的关键级作为系统的执行关键级，充分利用系统计算资源，尽可能的维护低关键级作业的执行。实验证明，与已有混合关键级作业调度算法相比，CSDDB在降低系统的关键等级、优化低关键级作业的调度方面具有较好的效果。
(2)提出以利用率优化混合关键级任务调度的算法
针对经典的混合关键级调度算法EDF-VD(Earliest Deadline First-Virtual Deadline)的可调度性约束较为严格，导致计算资源被浪费的问题，修改了混合关键级调度的正确性条件，通过允许低关键级任务的延时完成，为低关键级任务的执行保留更多机会。在新的正确性条件的基础上，通过对系统利用率的分析，在不同的利用率条件下提出了EDF-WCR(Earliest Deadline First-Worst Case Reservation)、EDF-BE(Earliest Deadline First-Best Effort)等算法。特别是当系统利用率超出了EDF-VD的可调度性条件范畴时，通过为高、低关键级任务分别分配虚拟时限的方法，保留了低关键级任务，避免了计算资源的浪费。基于EDF-WCR、EDF-VD和EDF-BE，提出了一种基于利用率的混合关键级任务调度算法MSBU(Mixed Scheduling Based on Utilization)，通过不同利用率条件下的不同算法，积极调度任务。实验证明，MSBU在充分利用系统资源、优化低关键级任务的完成率方面具有优势。
(3)提出混合关键级任务在多处理器下调度的半划分算法
针对同构多处理器环境下，划分调度与全局调度各自存在的不足，提出了一种半划分调度算法SPBU(Semi Partition Based on Utilization)。通过提前对高、低关键级任务分别进行划分，并在运行时允许低关键级任务在满足一定的利用率条件和运行状态条件时迁移，一方面充分利用多处理器的剩余计算资源，积极调度低关键级任务，另一方面也有效的降低了低关键级任务的迁移次数，避免了系统资源的浪费。实验证明，SPBU能有效提升低关键级任务在同构多处理器平台上的完成率。
(4)提出关键级逐一切换的混合关键级任务优化调度算法
针对EDF-VD算法在关键级切换策略方面的不足，提出了一种优化算法O-EDF-VD(Optimized-Earliest Deadline First-Virtual Deadline)。该算法在系统进入高关键级阶段后，对高关键级任务的执行关键级进行逐一切换，有效的节约了系统处于高关键级阶段的时长，为低关键级任务争取了更多的执行时间。实验证明，O-EDF-VD可以有效降低系统在高关键级阶段的持续时间，为低关键级任务提供更多的执行机会。
(5)提出以概率优化在多处理器下划分混合关键级任务的模型和算法
针对当前混合关键级调度研究均基于最坏情况进行分析，而忽略了实际运行时的因素的问题，提出了一种概率混合关键级任务模型PMC(Probability Mixed Criticality)，把高关键级任务的过载概率作为参数加入到任务模型中，以描述任务在实际执行过程中的过载情况。以之为基础，分析了系统在实际运行过程中的各种情况，利用概率论的计算方法，计算了系统在低关键级阶段、高关键级阶段和整个超周期的执行时长期望，有效描述了周期性任务系统的实际执行状态。并以之为基础，提出了影响低关键级任务执行的关键因子。在同构多处理器平台上，以影响低关键级任务执行的关键因子为优化目标，提出了一种基于概率的混合关键级任务划分算法PPDC(Partition based on Probability for Dual-Criticality Tasks)，在充分考虑实际执行情况的基础上，优化了任务的划分。实验结果表明，PPDC在优化低关键级任务的完成率方面具有较好的效果。
本文以混合关键级系统为研究对象，以在满足系统可靠性的前提下提升系统整体性能为目标，研究混合关键级系统优化调度问题。从模型、作业调度、任务调度、任务划分、任务迁移等角度，采用需求边界函数分析、利用率分析、概率和期望计算、可调度性分析以及关键因子分析等方法，研究混合关键级优化调度的机制和算法问题。主要的研究工作与成果如下：
(1)提出以动态需求边界优化混合关键级作业调度的算法
针对混合关键级作业调度中，系统关键级向下切换机制不灵活导致的低关键级作业被大量丢弃和系统计算资源无法被充分利用的问题，提出了混合关键级作业的动态需求边界函数DDBF(Dynamic Demand Boundary Function)概念，充分考虑了作业的实时属性与关键级属性，以及作业在运行时的执行情况，动态的从多维度描述作业的需求边界。以之为基础，定义了关键级松弛时间的概念，并提出了一种混合关键级作业的关键级动态切换算法CSDDB(Criticality Switch based on Dynamic Demand Boundary)，选取具有最小松弛时间的关键级作为系统的执行关键级，充分利用系统计算资源，尽可能的维护低关键级作业的执行。实验证明，与已有混合关键级作业调度算法相比，CSDDB在降低系统的关键等级、优化低关键级作业的调度方面具有较好的效果。
(2)提出以利用率优化混合关键级任务调度的算法
针对经典的混合关键级调度算法EDF-VD(Earliest Deadline First-Virtual Deadline)的可调度性约束较为严格，导致计算资源被浪费的问题，修改了混合关键级调度的正确性条件，通过允许低关键级任务的延时完成，为低关键级任务的执行保留更多机会。在新的正确性条件的基础上，通过对系统利用率的分析，在不同的利用率条件下提出了EDF-WCR(Earliest Deadline First-Worst Case Reservation)、EDF-BE(Earliest Deadline First-Best Effort)等算法。特别是当系统利用率超出了EDF-VD的可调度性条件范畴时，通过为高、低关键级任务分别分配虚拟时限的方法，保留了低关键级任务，避免了计算资源的浪费。基于EDF-WCR、EDF-VD和EDF-BE，提出了一种基于利用率的混合关键级任务调度算法MSBU(Mixed Scheduling Based on Utilization)，通过不同利用率条件下的不同算法，积极调度任务。实验证明，MSBU在充分利用系统资源、优化低关键级任务的完成率方面具有优势。
(3)提出混合关键级任务在多处理器下调度的半划分算法
针对同构多处理器环境下，划分调度与全局调度各自存在的不足，提出了一种半划分调度算法SPBU(Semi Partition Based on Utilization)。通过提前对高、低关键级任务分别进行划分，并在运行时允许低关键级任务在满足一定的利用率条件和运行状态条件时迁移，一方面充分利用多处理器的剩余计算资源，积极调度低关键级任务，另一方面也有效的降低了低关键级任务的迁移次数，避免了系统资源的浪费。实验证明，SPBU能有效提升低关键级任务在同构多处理器平台上的完成率。
(4)提出关键级逐一切换的混合关键级任务优化调度算法
针对EDF-VD算法在关键级切换策略方面的不足，提出了一种优化算法O-EDF-VD(Optimized-Earliest Deadline First-Virtual Deadline)。该算法在系统进入高关键级阶段后，对高关键级任务的执行关键级进行逐一切换，有效的节约了系统处于高关键级阶段的时长，为低关键级任务争取了更多的执行时间。实验证明，O-EDF-VD可以有效降低系统在高关键级阶段的持续时间，为低关键级任务提供更多的执行机会。
(5)提出以概率优化在多处理器下划分混合关键级任务的模型和算法
针对当前混合关键级调度研究均基于最坏情况进行分析，而忽略了实际运行时的因素的问题，提出了一种概率混合关键级任务模型PMC(Probability Mixed Criticality)，把高关键级任务的过载概率作为参数加入到任务模型中，以描述任务在实际执行过程中的过载情况。以之为基础，分析了系统在实际运行过程中的各种情况，利用概率论的计算方法，计算了系统在低关键级阶段、高关键级阶段和整个超周期的执行时长期望，有效描述了周期性任务系统的实际执行状态。并以之为基础，提出了影响低关键级任务执行的关键因子。在同构多处理器平台上，以影响低关键级任务执行的关键因子为优化目标，提出了一种基于概率的混合关键级任务划分算法PPDC(Partition based on Probability for Dual-Criticality Tasks)，在充分考虑实际执行情况的基础上，优化了任务的划分。实验结果表明，PPDC在优化低关键级任务的完成率方面具有较好的效果。
