多處理機(jī)實(shí)時(shí)任務(wù)動(dòng)態(tài)調(diào)度算法研究.pdf

1、現(xiàn)今，實(shí)時(shí)嵌入式系統(tǒng)在許多領(lǐng)域都得到了廣泛應(yīng)用，包括但不限于，通信系統(tǒng)、消費(fèi)電子、車輛電子、醫(yī)療圖像和航天航空等等。顯而易見，這些領(lǐng)域最為關(guān)鍵的核心問題在于任務(wù)的調(diào)度，亦即計(jì)算資源的管理，因此實(shí)時(shí)調(diào)度一直是人們研究的重點(diǎn)。隨著信息科學(xué)和電子技術(shù)的高速發(fā)展，面向應(yīng)用的嵌入式專用多處理機(jī)系統(tǒng)正越來越普及，人們擁有了質(zhì)量和數(shù)量都遠(yuǎn)超從前的計(jì)算資源。然而，傳統(tǒng)的單處理機(jī)實(shí)時(shí)任務(wù)調(diào)度已開始逐漸不能適應(yīng)當(dāng)前多處理機(jī)強(qiáng)勁的發(fā)展趨勢(shì)。所以，大力研究多處

2、理機(jī)的調(diào)度技術(shù)以便更加高效地利用計(jì)算資源在理論上和實(shí)際上都具有重要意義。
　　 本文的研究目的在于，根據(jù)各種實(shí)時(shí)應(yīng)用的復(fù)雜性和多樣性建立更加通用的多處理機(jī)實(shí)時(shí)任務(wù)模型并且提供一種新的調(diào)度算法，通過批處理和并行的方式盡量提高實(shí)時(shí)任務(wù)的調(diào)度成功率。本文的主要工作體現(xiàn)在如下幾個(gè)方面。
　　 (1)研究實(shí)時(shí)系統(tǒng)的主要特點(diǎn)，給出調(diào)度算法常見的分類以及相關(guān)的性能度量和最優(yōu)準(zhǔn)則。
　　 (2)全面總結(jié)近半個(gè)世紀(jì)以來單處理機(jī)實(shí)時(shí)

3、任務(wù)調(diào)度的研究。文章漸進(jìn)地分析了常用的任務(wù)模型，并詳細(xì)討論四種經(jīng)典的調(diào)度算法，指出各自的適用范圍、優(yōu)缺點(diǎn)以及計(jì)算復(fù)雜度。多處理機(jī)的實(shí)時(shí)任務(wù)調(diào)度問題哪怕是使用簡化的任務(wù)模型在絕大部分情況下都是NP完全的。本文從靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩個(gè)方面仔細(xì)研究多處理機(jī)實(shí)時(shí)任務(wù)的多種調(diào)度策略。
　　 (3)既然不存在最優(yōu)的動(dòng)態(tài)調(diào)度算法來為多處理機(jī)安排事先并不知曉相關(guān)參數(shù)的實(shí)時(shí)任務(wù)，本文提出一種時(shí)間復(fù)雜度是線性的新型多處理機(jī)實(shí)時(shí)任務(wù)啟發(fā)式調(diào)度算法，它