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

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

【學(xué)位級(jí)別】：博士

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



本文編號(hào)：3835504