现代实时嵌入式系统不断发展的一个重要趋势是在同一硬件平台中集成多种不同关键性级别的应用。与此同时,嵌入式系统硬件也在经历从单核平台向多核平台的变革之中,未来还将发展至众核平台。但是这种混合关键性系统的调度问题即便是对于单核平台也是极具挑战性的。目前,大多数复杂的嵌入式系统很难被传统基于周期的简单模型所精确描述。实时任务有向图(DRT)模型具备很强的描述能力,可以用于没有循环时间行为的复杂实时系统的建模。但是针对该模型的精确时间分析在时间复杂度上通常是不可接受的(指数级复杂度)。本文研究了基于混合关键性系统和DRT模型的实时调度算法的设计与分析等问题。在混合关键性系统研究方面,提出了一种高效的单核处理器运行时调度算法,和两种多核、多处理器划分调度算法。在DRT模型研究方面,提出了两种有效的近似响应时间分析方法,并通过计算加速比进行了量化评价,还提出了一种有效的有向图整形算法来提升系统的可调度性。本文的主要贡献点可以被总结如下:(1)提出了基于OCBP策略的固定作业优先级单处理器混合关键性实时调度算法LPA。与其它OCBP族的算法相比,LPA算法显著提升了系统的运行时时间效率(线性时间复杂度)、空间效率和可调度性。LPA算法的核心思想是尽可能晚的调整作业的运行时优先级,从而避免了与实际调度决策不相关的冗余优先级调整工作。本文还提出了更精确的混合关键性系统忙碌周期上界的计算方法。使用随机生成任务集合的实验结果表明本文提出算法显著提升了运行时时间效率、空间效率和可调度性。(2)提出了新型混合关键性划分调度算法MPVD,将单处理器上可调度性能最佳的算法EY-VD扩展至多处理器平台。MPVD算法的核心思想是将不同关键性级别的任务尽可能均匀地分配到各个处理器中,以更好地利用不同关键性级别任务间的差异性,从而提升系统的可调度性。本文还分析了 MPVD的不足,并提出了两个优化技术来进一步提升算法的性能。使用随机生成任务集合的实验结果表明本文提出算法的可调度性显著高于己有算法。(3)提出了新型混合关键性多处理器划分调度策略OCOP。本文首先结合EY-VD算法和传统划分调度策略提出了混合关键性系统划分调度算法MC-PEDF。该算法的性能显著高于其它已有划分调度算法,但本文研究发现传统的划分策略不能很好的利用任务在不同关键性级别中工作量的差异性。为了解决该问题,本文放松了划分调度禁止所有运行时作业迁移的限制,提出了 OCOP划分调度策略。OCOP允许系统关键性模式切换时,调整任务在处理器间的分配,从而显著提升了不同关键性模式中的系统资源利用率。最后本文本文还提出了使用OCOP策略的新划分调度算法MC-MP-EDF。实验结果表明MC-PEDF和MC-MP-EDF算法在可调度性上优于先前的多处理器混合关键性实时调度算法,而采用OCOP划分调度策略的MC-MP-EDF算法则具有更好的可调度性能。(4)提出了两种伪多项式时间复杂度的近似分析DRT任务系统响应时间的方法RBF和IBF,并通过分别计算加速比,从理论上量化评价了这两种近似方法的性能。本文证明了 RBF近似响应时间分析方法的精确加速比为2(即便是双任务的简易系统)。IBF方法的加速比是随干涉任务数量k单调递增的函数。该函数在k趋于无穷大时收敛于2,并在= 2时取值为1。因此IBF方法在分析双任务系统时,结果是精确的。随机任务实验结果表明本文提出的近似分析方法具有很好的时间效率,同时仅有很小的精度损失。(5)提出了一种高效率的DRT任务有向图整形算法以提升系统的可调度性。算法的主要思想是在任务有向图的特定顶点上添加一个人为设定的释放时间延迟,从而得到一个释放工作量更平滑的新图,同时新图还能保持原有的时间约束条件。延迟特定顶点的释放时间能够使得有向图释放的某些路径上的工作量更平滑,同时会造成其它路径的工作量更集中。本文提出算法能高效率地为每个顶点搜索适当的释放时间延迟取值。实验结果表明本文提出算法能够显著提升DRT任务集合的可调度性,并且能够在很短时间内处理大规模的任务集合。综上,本文研究了面向混合关键性系统以及DRT模型的实时调度问题,为现代嵌入式系统的设计与分析提供了可参考的理论依据与技术方法。