【文章內(nèi)容簡(jiǎn)介】 微軟在嵌入式平臺(tái)的基礎(chǔ)。 為了適應(yīng)嵌入式環(huán)境，WinCE 的內(nèi)部結(jié)構(gòu)也是模塊化設(shè)計(jì)，可以根據(jù)實(shí)際情況進(jìn)行裁剪。 WinCE 來(lái)源于 大家最熟知的 Windows 操作系統(tǒng)， 目前內(nèi)部已經(jīng)集成了大約五百個(gè) Win32 API函數(shù) ，并且提供和 PC 機(jī)環(huán)境相當(dāng)?shù)淖烂姝h(huán)境 。所以 它的使用和開(kāi)發(fā)基本和通用Windows 環(huán)境下開(kāi)發(fā)流程類似。 嵌入式實(shí)時(shí)系統(tǒng)的關(guān)鍵在于多任務(wù)調(diào)度算法，因?yàn)椴煌恼{(diào)度算法會(huì)對(duì)實(shí)時(shí)性造成一定影響。目前在嵌入式實(shí)時(shí)系統(tǒng)中主要采用優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度算法，這類算法分為靜態(tài)優(yōu)先級(jí)調(diào)度算法和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法。 嵌入式系統(tǒng) 硬件部分 的 核心是嵌入式微處理器。嵌入式微處理器一般 具備以下特點(diǎn)： 一、 為了實(shí)現(xiàn)及時(shí)響應(yīng)和處理，內(nèi)核對(duì)多任務(wù)的調(diào)度算法和 任務(wù)間 切換時(shí)間以及 對(duì)應(yīng)于 處理實(shí)時(shí)任務(wù)的應(yīng)用程序的時(shí)間降到最低程度， 需要處理器有較高的運(yùn)行頻率和 很短的 中斷 響應(yīng)時(shí)間 ，以提高對(duì)實(shí)時(shí)多任務(wù)的支持能力。 二、 便于嵌入式系統(tǒng) 對(duì)實(shí)時(shí)操作系統(tǒng)的 裁剪， 實(shí)時(shí)操作系統(tǒng)已將 軟件 構(gòu)成 特別是驅(qū)動(dòng)和進(jìn)程間通信機(jī)制 高度模塊化。該特點(diǎn)需要硬件有較 強(qiáng) 的存儲(chǔ)區(qū)保護(hù)功能， 便于 軟件模塊之間正常工作、互不干擾，也利于軟件本身的測(cè)試。 三、 同嵌入式實(shí)時(shí)操作系統(tǒng)的模塊化構(gòu)成一樣， 硬件處理器也需要可裁剪功能 ， 以便功能的升級(jí)和產(chǎn)品的換代。 對(duì)硬件的這一需求，市場(chǎng)上流行的FPGA 就 可以完全滿足這一特點(diǎn)要求。 四、 微控制器的最大特點(diǎn)是單片化， 高度集成了外設(shè)模塊， 提高了系統(tǒng)的可第一章 緒論 5 靠性。另一方面， 特別在便攜式電子設(shè)備中使用的移動(dòng)電源，所以要求微處理器功耗極低 。功耗在 ????到 ????之間。 國(guó)內(nèi)外研究現(xiàn)狀及分析 任務(wù)調(diào)度在操作系統(tǒng)中的地位尤為重要，所以 目前針對(duì)任務(wù)調(diào)度所采用的算法已經(jīng)取得的很多成果。 下面主要介紹對(duì)于周期任務(wù)調(diào)度算法 ： 時(shí)間片輪轉(zhuǎn)法是分時(shí)系統(tǒng)中一種常用任務(wù)調(diào)度策略，它將系統(tǒng)時(shí)間劃分成等長(zhǎng)多個(gè)時(shí)間片段，給每個(gè)任務(wù)分配一小片系統(tǒng)時(shí)間 逐一 執(zhí)行 。這種算法在表面上看起來(lái)是最公平的算法， 可 是它不利于重要任務(wù)的優(yōu)先執(zhí)行。 單調(diào)速率調(diào)度算法 [24]是針對(duì)周期任務(wù)進(jìn)行調(diào)度的 基于 優(yōu)先級(jí)調(diào)度算法 。任務(wù)的優(yōu)先級(jí)取決于周期任務(wù)的周期，周期越短，優(yōu)先級(jí)就越高。 如果采用單調(diào)速率多任務(wù)調(diào)度算法，需要根據(jù)任務(wù)集的特性判定可調(diào)度性。 截止期 單調(diào) 調(diào)度算法 是在單調(diào)速率調(diào)度算法的基礎(chǔ)上發(fā)展起來(lái)的 基于優(yōu)先級(jí)多任務(wù)調(diào)度算法。 該算法分配給任務(wù)的優(yōu)先級(jí)是按照任務(wù)的截止時(shí)間來(lái)進(jìn)行分配的。 截止時(shí)間越短的任務(wù)優(yōu)先級(jí)就越高，反之任務(wù)的優(yōu)先級(jí)就越低。 和單調(diào)速率調(diào)度算法一樣，它也對(duì)被調(diào)度任務(wù)進(jìn)行可調(diào)度分析。 最早截止期優(yōu)先調(diào)度算法是一種截止期驅(qū)動(dòng)的動(dòng)態(tài)可搶占優(yōu)先級(jí)實(shí)時(shí)調(diào)度算法 。該算法是通過(guò)確定操作系統(tǒng)不斷地判斷任務(wù)的截止期而進(jìn)行動(dòng)態(tài)優(yōu)先級(jí)分配 ，即任務(wù)的時(shí)限與當(dāng)前時(shí)刻的距離越近，優(yōu)先級(jí)就越高，反則優(yōu)先級(jí)越低。 最小空閑時(shí)間優(yōu)先調(diào)度算法 是通過(guò)計(jì)算任務(wù)的截止時(shí)間和剩余執(zhí)行時(shí)間之差對(duì)任務(wù)的優(yōu)先級(jí)進(jìn)行動(dòng)態(tài)分配。 其差值越小，系統(tǒng)分配給任務(wù)的優(yōu)先級(jí) 就 越高 ，反則優(yōu)先級(jí)就越低 [25]。 主流靜態(tài)優(yōu)先級(jí)調(diào)度算法有 單調(diào)速率任務(wù)調(diào)度 算法，截止期單調(diào)調(diào)度算法 等，截止期 單調(diào) 算法已被證明是靜態(tài)最優(yōu)算法。動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法有最早截止期優(yōu)先算法，最小空閑時(shí)間優(yōu)先，其中期限最近者優(yōu)先調(diào)度算法是一種最優(yōu)的單處理器動(dòng) 態(tài)調(diào)度算法。 主流實(shí)時(shí)系統(tǒng)中任務(wù)調(diào)度算法的優(yōu)缺點(diǎn)如下： 昆明理工大學(xué)博士或碩士論文 表 1 靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)之間優(yōu)缺點(diǎn)比較 算法類別 優(yōu)點(diǎn) 缺點(diǎn) 靜態(tài)優(yōu)先級(jí)調(diào)度算法 系統(tǒng)開(kāi)銷小 低優(yōu)先級(jí)別的任務(wù)延遲大 動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法 調(diào)度靈活 系統(tǒng)開(kāi)銷大，易出現(xiàn)調(diào)度顛簸現(xiàn)象 針對(duì)上述兩類算法存在的問(wèn)題提出一種調(diào)度策略 —— 優(yōu)先級(jí)周期性互換，以滿足系統(tǒng)開(kāi)銷小，任務(wù)調(diào)度相對(duì)靈活。 其詳細(xì)情況將在第二 章介紹。 由于本文對(duì)于優(yōu)先級(jí)周期性互換尚處在研究階段，其可行性采用 Ptolemy II仿真驗(yàn)證的方法。一方面減少研究時(shí)間，加快項(xiàng)目進(jìn)度；另一方面通過(guò)仿真可以快速發(fā)現(xiàn)優(yōu)先級(jí)周期性互換 調(diào)度算法的 可行 性 ，存在的問(wèn)題等。 仿真工具是一種采用某種 （軟件或者硬件） 替代手段來(lái)模擬 真實(shí) 環(huán)境 。 仿真軟件是從上世紀(jì)五十年代隨著計(jì)算機(jī)技術(shù)的發(fā)展而出現(xiàn)的。 仿真軟件可以模擬真實(shí)環(huán)境， 使得 使用者在不具備真實(shí)環(huán)境 或者不可能具備 真實(shí) 環(huán)境的條件下在模擬軟件上進(jìn)行試驗(yàn)。 模擬軟件的優(yōu)勢(shì)是顯而易見(jiàn)的， 它 有 成本低，不受地域和時(shí)空的限制 和 靈活性大等特點(diǎn) ，從而在當(dāng)前的數(shù)字化領(lǐng)域應(yīng)用廣泛。 由于本論文所研究的對(duì)象 的特點(diǎn) 和 項(xiàng)目所處的 階段 ，對(duì)于提出的理論需要進(jìn)行 仿真 驗(yàn)證 ，以加快項(xiàng)目研發(fā)進(jìn)度和節(jié)約時(shí)間成本。 本文提出的理論是基于單處理器多任務(wù)環(huán)境下的任務(wù)調(diào)度算法。所以需要一個(gè)能夠模擬單處理器多任務(wù)環(huán)境的仿真軟件，以便對(duì)所提出的任務(wù)調(diào)度算法進(jìn)行仿真驗(yàn)證。 主流仿真軟件有Matlab 中自帶的 Simulink[26]模塊、 NI（美國(guó)國(guó)家儀器公司）開(kāi)發(fā)的 LabView[26]、Synopsys 的 Cocentric Studio[27]以及 Ptolemy[28]軟件等。 通過(guò)分析和了解， Ptolemy軟件在仿真單處理器多任務(wù)環(huán)境具有明顯優(yōu)勢(shì)。 Ptolemy軟件 是由 Berkeley大學(xué)開(kāi)發(fā)的采用面向角色 的設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。嵌入式領(lǐng)域的 硬件信號(hào) 特點(diǎn)是多種結(jié)構(gòu)共同，如頻域信號(hào)、時(shí)域信號(hào)、 模擬信號(hào)和 離散 信號(hào)等等 ；軟件特點(diǎn)則是通過(guò)劃分層次來(lái)進(jìn)行設(shè)計(jì)，下層給上層提供標(biāo)準(zhǔn)信號(hào)，對(duì)上層屏蔽底層操作 。這種 復(fù)雜 結(jié)構(gòu)在仿真 環(huán)境 中一般 比較難以 模擬層次間、異構(gòu)間的信號(hào) 進(jìn)行交互，而 Ptolemy采用角色設(shè)計(jì)方法很好的解決了不同結(jié)構(gòu)之間的信號(hào)交互 ， 實(shí)現(xiàn)了 異構(gòu)系統(tǒng)的模擬仿真。 Ptolemy內(nèi)部自帶有單處理器多任務(wù)調(diào)度模塊，直接可以進(jìn)行任務(wù)調(diào)度的算法級(jí)仿真。 本次選擇 Ptolemy軟件進(jìn)行仿真單處理器多任務(wù)調(diào)度環(huán)境，在此基礎(chǔ)上只實(shí)第一章 緒論 7 現(xiàn)多任務(wù)的調(diào)度算法。但是本項(xiàng)目是一個(gè)標(biāo)準(zhǔn)的嵌入式系統(tǒng)， 具有異構(gòu)性和層次性 [29]， 因此上它更適合于整個(gè)項(xiàng)目的仿真。 優(yōu)先級(jí)周期性互換 實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度算法的仿真對(duì)仿真軟件的要求： 需要 一個(gè)基于優(yōu)先級(jí)搶占式的 單處理器 任務(wù)調(diào)度模型； 該任務(wù)調(diào)度模型可以和 連續(xù)時(shí)間域的 傳遞函數(shù) 聯(lián)合仿真。 Ptolemy II 的時(shí)間多任務(wù)可以實(shí)現(xiàn)基于優(yōu)先級(jí)搶占式的單處理器任務(wù)調(diào)度模型，由于 Ptolemy II 的本身特性，它完全可以支持 不同模型之間的異構(gòu)。 課題來(lái)源 一、 國(guó)家自然科學(xué)基金項(xiàng)目“實(shí)時(shí)領(lǐng)域交互行為模型轉(zhuǎn)換方法及非功能語(yǔ)義規(guī)約研究”（項(xiàng)目編號(hào) 61263017） 二、 云南省自然科學(xué)基金項(xiàng)目“基于實(shí)時(shí)語(yǔ)義模型的模型轉(zhuǎn)換及語(yǔ)義一致性研究”（項(xiàng)目編號(hào) 2021FZ060） 本文組織結(jié)構(gòu) 本文 研究嵌入式實(shí)時(shí)系統(tǒng)多任務(wù)調(diào)度策略 。本文的重點(diǎn)是 學(xué)習(xí) Ptolemy II 仿真軟件，分析當(dāng)前實(shí)時(shí)系統(tǒng)多任務(wù)調(diào)度算法， 提出 一種改進(jìn) 的 多任務(wù) 調(diào)度方法 —— 優(yōu)先級(jí)周期性互換 ， 以及該方法的使用條件， 并用仿真軟件 Ptolemy II 對(duì)該方法 進(jìn)行仿真驗(yàn)證 。 第一章 介紹 實(shí)時(shí)系統(tǒng)的應(yīng)用范圍、實(shí)時(shí)操作系統(tǒng)種類 ； 常用任務(wù)調(diào)度算法；并簡(jiǎn)要介紹 Ptolemy II 仿真軟件 在任務(wù)調(diào)度方面的仿真優(yōu)勢(shì)。 第二章 對(duì)當(dāng)前多任務(wù)實(shí)時(shí)系統(tǒng)的任務(wù)調(diào)度方法進(jìn)行分析， 并通過(guò)仿真軟件Ptolemy II 進(jìn)行實(shí)例分析， 總結(jié)優(yōu)缺點(diǎn)。 第三章 研究 Ptolemy II 仿真軟件異構(gòu) 仿真 原理和 組件 功能 ， 重點(diǎn) 分析 任務(wù)調(diào)度方面的優(yōu)勢(shì)及使用方法。 第四章 提出周期性任務(wù)優(yōu)先級(jí)轉(zhuǎn)化調(diào)度算法的適用條件，并通過(guò)仿真來(lái)驗(yàn)證周期性任務(wù)優(yōu)先級(jí)轉(zhuǎn)化的可行性。 使用 Ptolemy II 軟件將周期性任務(wù)優(yōu)先級(jí)轉(zhuǎn)化 調(diào)度算法融合到實(shí)際系統(tǒng)中進(jìn)行 仿真 驗(yàn)證。 第五章 總結(jié) 優(yōu)先級(jí)周期性互換 調(diào)度算法，針對(duì)存在的問(wèn)題，提出下一階段的工作任務(wù)。 昆明理工大學(xué)博士或碩士論文 第二章 嵌入式實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度機(jī)制 9 第二 章 嵌入式實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度 機(jī)制 嵌入式實(shí)時(shí)操作系統(tǒng) 嵌入式實(shí)時(shí)操作系統(tǒng) 是針對(duì)于嵌入式系統(tǒng)而專門“定制”的一類 實(shí)時(shí) 操作系統(tǒng)的統(tǒng)稱。 按照嵌入式系統(tǒng) 對(duì) 時(shí)效 性的 要求， 分為嵌入式實(shí)時(shí)操作系統(tǒng)和嵌入式非實(shí)時(shí)操作系統(tǒng) 。 嵌入式實(shí)時(shí)操作系統(tǒng)就比如第一章舉例的汽車上的安全氣囊，它要求安全氣囊在規(guī)定的時(shí)間內(nèi)打開(kāi)。 這里就包括了兩個(gè)要素： 規(guī)定時(shí)間內(nèi)和安全氣囊打開(kāi)。這里 的“規(guī)定時(shí)間內(nèi)”就是系統(tǒng)對(duì)時(shí)效性的要求 ；安全氣囊打開(kāi)就是一般意義上的邏輯結(jié)果正確 。 這兩個(gè)要素必須同時(shí)滿足，缺一不可，才能成為“結(jié)果”正確。試想， 一旦超過(guò)這個(gè)“規(guī)定時(shí)間”，即便是安全氣囊成功 打開(kāi)，也已經(jīng)喪失了安全氣囊存在的必要性。 而對(duì)于通常情況下的時(shí)效性要求則并非實(shí)時(shí)系統(tǒng)中的時(shí)效性。例如 目前最為常見(jiàn)的智能手機(jī)，它的內(nèi)部就有 Android 操作系統(tǒng) （非實(shí)時(shí)操作系統(tǒng)） ，該系統(tǒng)來(lái)自于 Linux系統(tǒng)的改進(jìn)。 用戶經(jīng)常反映手機(jī)反應(yīng)快慢的問(wèn)題， 看起來(lái)好似實(shí)時(shí)系統(tǒng)中的時(shí)效性問(wèn)題，實(shí)則不然。 手機(jī)中某個(gè)程序響應(yīng)慢，甚至?xí)霈F(xiàn)“該 應(yīng)用程序無(wú)響應(yīng)”的提示。 出現(xiàn)這種結(jié)果，用戶最多是不耐煩，但不會(huì)出現(xiàn)其他意外。但實(shí)時(shí)系統(tǒng)對(duì)外部激勵(lì)做出響應(yīng)一旦錯(cuò)失時(shí)間，那就會(huì)導(dǎo)致致命性錯(cuò)誤。 從以上兩個(gè)例子，可以感性的了解到實(shí)時(shí)系統(tǒng)和非實(shí)時(shí)系統(tǒng)的區(qū)別。接下來(lái)給出 實(shí)時(shí)系統(tǒng) 中涉及 到 的概念 ， 便于后續(xù) 工作的介紹和論證。 實(shí)時(shí)操作 系統(tǒng)相關(guān)術(shù)語(yǔ) 同一般操作系統(tǒng)一樣，實(shí)時(shí)操作系統(tǒng)的主要工作仍然是對(duì) 系統(tǒng)內(nèi) 多任務(wù)的調(diào)度和 對(duì) 資源的管理 。為了詳細(xì)描述任務(wù)在各個(gè)時(shí)刻所處的狀態(tài)， 下面給出 實(shí)時(shí)系統(tǒng)中 所涉及到的 概念 [30]。 任務(wù)：是 系統(tǒng)中能夠完成某種功能的 軟件實(shí)體，它是 系統(tǒng)可以調(diào)度的基本單位 。 為了便于描述任務(wù)調(diào)度基本單位， 下文將用任務(wù)來(lái)表征調(diào)度基本單位。 不再使用其他文獻(xiàn)中作業(yè)的概念。 周期任務(wù)：指任務(wù)按照某個(gè)時(shí)間段間隔性的出現(xiàn)在系統(tǒng)中的任務(wù)。與之對(duì)應(yīng)的是非周期任務(wù) 。非周期任務(wù)出現(xiàn)時(shí)間是隨機(jī)的，不確定的。 昆明理工大學(xué)博士或碩士論文 雖然通常情況下任務(wù)大多都是非周期性任務(wù)，但由于非周期任務(wù)調(diào)度算法比較復(fù)雜，需要專門對(duì)其進(jìn)行分析。為了便于驗(yàn)證新提出的任務(wù)調(diào)度算法，本文選取的任務(wù)均為周期性任務(wù) 。以下凡是沒(méi)有特別說(shuō)明，所提到的任務(wù)均為周期性任務(wù)。 任務(wù)創(chuàng)建：將任務(wù)以可執(zhí)行二進(jìn)制代碼實(shí)體加載到內(nèi)存中。 就緒態(tài) ：任務(wù) 已 具備運(yùn)行條件，等待 CPU空閑。處于就緒態(tài)的任務(wù)可以是多個(gè)。 運(yùn)行態(tài)：任務(wù)獲取 CPU資源進(jìn)行執(zhí)行。 處于運(yùn)行態(tài)的任務(wù)只能有一個(gè)（在單處理器）。 釋放時(shí)間： 任務(wù) 由其他狀態(tài)轉(zhuǎn)變?yōu)榫途w態(tài)的那個(gè)時(shí)刻稱為它的釋放時(shí)間。 響應(yīng) 時(shí)間： 從任務(wù) 的釋放時(shí)間 ，到 任務(wù)所有功能都完成的時(shí)刻 ，這段時(shí)間是任務(wù)的 相應(yīng) 時(shí)間。 當(dāng)任務(wù)在執(zhí)行過(guò)程中，由于等待資源而被掛起， 從任務(wù)的釋放時(shí)間到任務(wù)被掛起這段時(shí)間只是響應(yīng)時(shí)間的一部分 ， 因?yàn)槿蝿?wù)并未完成所有的任務(wù)而放棄了CPU。 剩余執(zhí)行時(shí)間：響應(yīng)時(shí)間減去任務(wù) 已經(jīng)執(zhí)行了的時(shí)間。 截止期： 任務(wù)必須在此時(shí)刻之前完成它應(yīng)該 執(zhí)行的 所有 功能。 若任務(wù)的的截止期沒(méi)有限制，稱該任務(wù) 沒(méi)有截止期。 截止期是一個(gè)時(shí)間點(diǎn)。 空閑時(shí)間 ： 就是 任務(wù)的絕對(duì)截止期 減去任務(wù)的剩余執(zhí)行時(shí)間再減去 當(dāng)前時(shí)間 。任務(wù)的空閑時(shí)間 是一個(gè)時(shí)間段概念。 相對(duì)截止期：作業(yè)的響應(yīng)時(shí)間所允許的最大值稱為該作業(yè)的相對(duì)截止期。 絕對(duì)截止期 ： 它等于作業(yè)的釋放時(shí)間加上其相對(duì)截止期。 在實(shí)時(shí)系統(tǒng)中，所有的作業(yè)都應(yīng)該在各自的絕對(duì)截止期內(nèi)完成 。 最壞執(zhí)行時(shí)間： 指任務(wù)在執(zhí)行期間由于各種因素的影響，在最壞的條件（時(shí)間延遲）下完成所有功能所耗費(fèi)的最大執(zhí)行時(shí)間值。該參數(shù)主要用于硬實(shí)時(shí)任務(wù)調(diào)度系統(tǒng)中的一個(gè)重要衡量指標(biāo)。 截止期錯(cuò)失率： 是由系統(tǒng)中所有任務(wù)在一段時(shí)間內(nèi)未在截止期完成的總數(shù)和系統(tǒng)任務(wù)總數(shù)之間的一種比率。 該指標(biāo)主要用在衡量一種調(diào)度算法的優(yōu)良性。很明顯， 截止期錯(cuò)失率越低，系統(tǒng)對(duì)任務(wù)的調(diào)度成功率越高，調(diào)度算法性能越優(yōu)良。 處理器利用率： 就是 CPU被任務(wù)占用執(zhí)行時(shí)間與總時(shí)間的比值。 具體的衡量辦法是： 系統(tǒng)中所有任務(wù)的最壞執(zhí)行時(shí)間與 對(duì)應(yīng) 任務(wù)周期的比值 之和就是處理第二章 嵌入式實(shí)時(shí)系統(tǒng) 任務(wù)調(diào)度機(jī)制 11 器利用率。 系統(tǒng)中所采用的任務(wù)調(diào)度算法 應(yīng)使得 處理器的利用率必須小于 100%，否則 ，截止期錯(cuò)失率很高。 處理器的利用率越高，所能處理的數(shù)據(jù)量就越大， 效率也越高。 嵌入式實(shí)時(shí)操作系統(tǒng)特點(diǎn) 由于實(shí)時(shí)系統(tǒng)的結(jié)果 取決于運(yùn)算結(jié)果 邏輯的正確性和產(chǎn)生 結(jié)果的時(shí)間，這就與一般系統(tǒng)有了如下的顯著區(qū)別： 一、 時(shí)間約束性 實(shí)時(shí)系統(tǒng)最明顯的特點(diǎn)就是添加了時(shí)間的概念， 只有在規(guī)定時(shí)間內(nèi)產(chǎn)生正確的邏輯才算作最終結(jié)果的正確。 按照截