發(fā)布時間：2023-06-27 23:01

　　現(xiàn)代實時嵌入式系統(tǒng)不斷發(fā)展的一個重要趨勢是在同一硬件平臺中集成多種不同關鍵性級別的應用。與此同時,嵌入式系統(tǒng)硬件也在經(jīng)歷從單核平臺向多核平臺的變革之中,未來還將發(fā)展至眾核平臺。但是這種混合關鍵性系統(tǒng)的調(diào)度問題即便是對于單核平臺也是極具挑戰(zhàn)性的。目前,大多數(shù)復雜的嵌入式系統(tǒng)很難被傳統(tǒng)基于周期的簡單模型所精確描述。實時任務有向圖(DRT)模型具備很強的描述能力,可以用于沒有循環(huán)時間行為的復雜實時系統(tǒng)的建模。但是針對該模型的精確時間分析在時間復雜度上通常是不可接受的(指數(shù)級復雜度)。本文研究了基于混合關鍵性系統(tǒng)和DRT模型的實時調(diào)度算法的設計與分析等問題。在混合關鍵性系統(tǒng)研究方面,提出了一種高效的單核處理器運行時調(diào)度算法,和兩種多核、多處理器劃分調(diào)度算法。在DRT模型研究方面,提出了兩種有效的近似響應時間分析方法,并通過計算加速比進行了量化評價,還提出了一種有效的有向圖整形算法來提升系統(tǒng)的可調(diào)度性。本文的主要貢獻點可以被總結如下:(1)提出了基于OCBP策略的固定作業(yè)優(yōu)先級單處理器混合關鍵性實時調(diào)度算法LPA。與其它OCBP族的算法相比,LPA算法顯著提升了系統(tǒng)的運行時時間效率(線性時間復雜...

【文章頁數(shù)】：149 頁

【學位級別】：博士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 混合關鍵性系統(tǒng)
        1.2.2 基于圖的實時任務模型
    1.3 本文研究內(nèi)容與貢獻
        1.3.1 面向混合關鍵系統(tǒng)的研究
        1.3.2 面向實時任務有向圖模型的研究
    1.4 本文組織結構
第2章 線性時間復雜度混合關鍵性調(diào)度算法
    2.1 系統(tǒng)模型與定義
        2.1.1 混合關鍵性偶發(fā)任務系統(tǒng)的運行時行為
        2.1.2 混合關鍵性系統(tǒng)的可調(diào)度性
    2.2 LPA算法
        2.2.1 離線優(yōu)先級分配算法
        2.2.2 運行時調(diào)度算法
        2.2.3 LPA算法實例
        2.2.4 運行時時間復雜度
    2.3 忙碌周期上界計算
    2.4 LPA算法可調(diào)度性的證明
    2.5 實驗結果與分析
        2.5.1 隨機任務集合生成
        2.5.2 時間開銷
        2.5.3 空間開銷
        2.5.4 可調(diào)度接受率
    2.6 小結
第3章 基于虛擬截止期的劃分調(diào)度算法
    3.1 基本概念
        3.1.1 混合關鍵性任務和混合關鍵性作業(yè)
        3.1.2 需求上界函數(shù)DBF
        3.1.3 EY-VD方法
    3.2 MPVD劃分調(diào)度算法
        3.2.1 混合劃分策略
        3.2.2 MPVD劃分調(diào)度算法
    3.3 MPVD算法優(yōu)化技術
        3.3.1 重型低關鍵性任務敏感的劃分策略
        3.3.2 虛擬截止期調(diào)整優(yōu)化算法
    3.4 實驗結果與分析
        3.4.1 隨機任務集合生成
        3.4.2 實驗結果分析
    3.5 小結
第4章 多處理器混合關鍵性系統(tǒng)劃分調(diào)度策略
    4.1 基本概念
        4.1.1 需求上界函數(shù)DBF
    4.2 基于傳統(tǒng)劃分策略的混合關鍵性劃分調(diào)度算法
        4.2.1 多處理器劃分調(diào)度的基本方法
        4.2.2 MC-PEDF算法的描述
        4.2.3 MC-PEDF算法的時間復雜性與正確性分析
    4.3 針對混合關鍵性系統(tǒng)的多次劃分實時調(diào)度策略
        4.3.1 傳統(tǒng)劃分策略的局限性
        4.3.2 混合關鍵性模型中的新型劃分策略OCOP
        4.3.3 MC-MP-EDF算法描述
        4.3.4 算法正確性分析
        4.3.5 算法復雜性分析
    4.4 實驗仿真與結果分析
        4.4.1 隨機任務集生成算法
        4.4.2 實驗結果分析
    4.5 小結
第5章 實時任務有向圖的近似響應時間分析
    5.1 系統(tǒng)模型與定義
        5.1.1 模型定義
        5.1.2 模型語義
        5.1.3 靜態(tài)優(yōu)先級調(diào)度和最差響應時間
    5.2 近似響應時間分析
        5.2.1 RBF:需求上界函數(shù)分析方法
        5.2.2 IBF:干涉上界函數(shù)分析方法
        5.2.3 一些性質
    5.3 加速比分析
        5.3.1 RBF方法的加速比
        5.3.2 IBF方法的加速比
    5.4 實驗結果與分析
        5.4.1 隨機任務集合生成方法
        5.4.2 實驗結果分析
    5.5 小結
第6章 基于DRT模型的優(yōu)化可調(diào)度性算法
    6.1 問題模型
    6.2 任務有向圖整形的基本思想
    6.3 高效整形算法
        6.3.1 算法概述
        6.3.2 需求上界函數(shù)rbfT
        6.3.3 Slf_Bound()過程
        6.3.4 Itf_Bound()過程
        6.3.5 整形算法的性質
    6.4 實驗評價
        6.4.1 生成隨機任務集合
        6.4.2 實驗結果分析
    6.5 小結
第7章 結論
    7.1 本文主要貢獻與結論
        7.1.1 面向混合關鍵系統(tǒng)的研究
        7.1.2 面向實時任務有向圖模型的研究
    7.2 進一步的工作
        7.2.1 基于混合關鍵系統(tǒng)
        7.2.2 基于實時任務有向圖模型
參考文獻
致謝
攻博期間發(fā)表的論文
攻博期間參與的項目
作者簡介



本文編號：3835504