【正文】 統(tǒng)都是實時操作系統(tǒng)（ RTOS），實時系統(tǒng)的調(diào)度追求的是實時性， RTOS調(diào)度器要讓每個任務(wù)都在其最終時間期限（ deadline）之前完成，而各任務(wù)之間的公平性并不是最重要的指標(biāo)。 RTOS調(diào)度器多采用基于優(yōu)先級的可搶占調(diào)度算法。 ? 1． RTOS任務(wù)模型 ? RTOS任務(wù)模型如圖 ，在 RTOS任務(wù)模型中，每一個任務(wù)用一個 三元組來表示（執(zhí)行時間、周期、時間期限） 。其中： 執(zhí)行時間 （ execution time） E（ i）是指對于第 i個任務(wù)，當(dāng)它所需要的資源都己具備時，它的執(zhí)行所需要的最長時間。 周期 （ period）P（ i）是指第 i個任務(wù)的連續(xù)兩次運行之間的最小時間間隔。 時間期限 （ deadline）是指 D（ i）第 i個任務(wù)所允許的最大響應(yīng)時間（從任務(wù)啟動到運行結(jié)束所需的時間）。一般來說，一個任務(wù)的周期時間同時也是它的時間期限，因為該任務(wù)必須在它的下一個周期開始之前，完成此次運行。啟動時間 t（ i）是指第 i個任務(wù)的第 i次執(zhí)行的開始時間。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 62 圖 RTOS任務(wù)模型 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 63 ? 2．單調(diào)速率調(diào)度算法（ Rate Monotonic Scheduling， RMS） ? RMS（ Rate Monotonic Scheduling，單調(diào)速率調(diào)度算法）是一種靜態(tài)優(yōu)先級調(diào)度算法。 ? RMS算法假設(shè)：所有的任務(wù)都是周期性任務(wù)；任務(wù)的時間期限等于它的周期；任務(wù)在每個周期內(nèi)的執(zhí)行時間是一個常量；任務(wù)之間不進(jìn)行通信，也不需要同步；任務(wù)可以在任何位置被搶占，不存在臨界區(qū)的問題。 ? RMS算法的基本思路是任務(wù)的優(yōu)先級與它的周期表現(xiàn)為單調(diào)函數(shù)的關(guān)系， 任務(wù)的周期越短，優(yōu)先級越高 ；任務(wù)的周期越長，優(yōu)先級越低。 ? RMS算法是一種 最優(yōu)調(diào)度算法 。如果存在一種基于靜態(tài)優(yōu)先級的調(diào)度順序，使得每個任務(wù)都能在其期限時間內(nèi)完成，那么 RMS算法總能找到這樣的一種可行的調(diào)度方案。 ? 在任務(wù)比較多的情況下， RMS可調(diào)度的 CPU使用率上限 為 ln2＝， CPU使用率如此低，對于大多數(shù)系統(tǒng)來說是不可接受的。另外，在一個實際的系統(tǒng)中，任務(wù)之間通常都需要進(jìn)行通信和同步。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 64 ? 3．最早期限優(yōu)先算法（ Earliest Deadline First， EDF） ? EDF（ Earliest Deadline First，最早期限優(yōu)先）調(diào)度算法是一種動態(tài)優(yōu)先級調(diào)度算法。 ? EDF算法的基本思路是：根據(jù)任務(wù)的截止時間來確定其優(yōu)先級，對于時間期限最近的任務(wù)，分配最高的優(yōu)先級 。當(dāng)有一個新的任務(wù)處于就緒狀態(tài)時，各個任務(wù)的優(yōu)先級就有可能要進(jìn)行調(diào)整。 ? EDF算法假設(shè)條件除了它不要求系統(tǒng)中的任務(wù)都必須是周期任務(wù)外，其他的假設(shè)條件與 RMS相同。 ? EDF算法可調(diào)度上限為 100％。對于給定的一組任務(wù)，只要它們的CPU使用率小于或等于 1， EDF就能找到合適的調(diào)度順序 ，使得每個任務(wù)都能在自己的時間期限內(nèi)完成。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 65 嵌入式系統(tǒng)的存儲管理 ? ? 嵌入式系統(tǒng)的存儲管理方式與系統(tǒng)的實際應(yīng)用領(lǐng)域及硬件環(huán)境密切相關(guān)，不同的嵌入式系統(tǒng)采用不同的存儲管理方式，需要 考慮硬件條件、實時性要求、系統(tǒng)規(guī)模、可靠性要求等因素 。 系統(tǒng)的實時性要求直接影響到存儲管理的實現(xiàn)方式 ，為了確保系統(tǒng)的實時性，快速和確定是內(nèi)存管理的基本要求，即在存儲管理方面的開銷不能太大，對于每一項工作都要有明確的實時約束，即必須在某個限定的時刻之前完成。在 實時系統(tǒng)中，存儲管理方法就比較簡單 ，甚至不提供存儲管理功能。而對一些實時性要求不高，可靠性要求比較高、比較復(fù)雜的應(yīng)用系統(tǒng)，需要實現(xiàn)對操作系統(tǒng)或任務(wù)的保護(hù)，在存儲管理方式上就相對較為復(fù)雜。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 66 ? 在嵌入式微處理器中， MMU（ Memory Management Unit, 存儲管理單元）提供了一種內(nèi)存保護(hù)的硬件機(jī)制 。內(nèi)存保護(hù)用來防止地址越界和防止操作越權(quán)。采用內(nèi)存保護(hù)機(jī)制的每個應(yīng)用程序都有自己獨立的地址空間，當(dāng)一個應(yīng)用程序要訪問某個內(nèi)存單元時，由硬件檢查該地址是否在限定的地址空間內(nèi)，如果不是的話就要進(jìn)行地址越界處理；二是防對于允許多個應(yīng)用程序共享的某塊存儲區(qū)域，每個應(yīng)用程序都有自己的訪問權(quán)限，如果違反了權(quán)限規(guī)定，則要進(jìn)行操作越權(quán)處理。 ? 操作系統(tǒng)通常 利用 MMU來實現(xiàn)系統(tǒng)內(nèi)核與應(yīng)用程序的隔離，以及應(yīng)用程序與應(yīng)用程序之間的隔離。防止應(yīng)用程序去破壞操作系統(tǒng)和其他應(yīng)用程序的代碼和數(shù)據(jù)，防止應(yīng)用程序?qū)τ布闹苯釉L問。MMU通常只在一些對安全性和可靠性的要求比較高、系統(tǒng)比較復(fù)雜的嵌入式系統(tǒng)中存在。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 67 ? 實模式和保護(hù)模式是嵌入式操作系統(tǒng)中常見的兩個存儲管理方式。 ? 1．實模式存儲管理 ? 在實模式存儲管理方式中，系統(tǒng)不使用 MMU；不劃分 “ 系統(tǒng)空間 ” 和“ 用戶空間 ” ，整個系統(tǒng)只有一個地址空間，即物理內(nèi)存地址空間；應(yīng)用程序和系統(tǒng)程序都能直接對所有的內(nèi)存單元進(jìn)行隨意訪問，無須進(jìn)行地址映射；操作系統(tǒng)的內(nèi)核與外圍應(yīng)用程序在編譯連接后，兩者通常被集成在同一個系統(tǒng)文件中；系統(tǒng)中的 “ 任務(wù) ” 或 “ 進(jìn)程 ” 均是內(nèi)核線程，只有運行上下文和棧是獨享的，其他資源都是共享的。 ? 在實模式存儲管理方式中，系統(tǒng)的內(nèi)存地址空間一般可以分為 text、 data、bss、堆、棧五個部分 。其中： .text：（代碼段）用來存放操作系統(tǒng)和應(yīng)用程序的 所有代碼 。 .data：（數(shù)據(jù)段）用來存放操作系統(tǒng)和應(yīng)用程序當(dāng)中所有 帶有初始值的全局變量 。 .bss：用來存放操作系統(tǒng)和應(yīng)用程序當(dāng)中所有 未帶初始值的全局變量 。堆為 動態(tài)分配的內(nèi)存空間 ，在系統(tǒng)運行時，可以通過類似于 malloc/free之類的函數(shù)來申請或釋放一段連續(xù)的內(nèi)存空間。棧用來保存運行上下文以及函數(shù)調(diào)用時的 局部變量和運行參數(shù) 。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 68 ? 對于實時系統(tǒng)來說，實模式方案簡單、存儲管理的開銷確定，比較適合于規(guī)模較小、簡單和實時性要求較高的系統(tǒng)。其缺點是沒有存儲保護(hù)、安全性差，在應(yīng)用程序中出現(xiàn)的任何一個小錯誤或蓄意攻擊都有可能導(dǎo)致整個系統(tǒng)的崩潰。 ? 2．保護(hù)模式存儲管理 ? 在保護(hù)模式存儲管理方式中， 微處理器必須具有 MMU硬件 并啟用它。 ? 在保護(hù)模式存儲管理方式中，系統(tǒng)內(nèi)核和用戶程序有各自獨立的地址空間，操作系統(tǒng)和 MMU共同完成邏輯地址到物理地址的映射；每個應(yīng)用程序只能訪問自己的地址空間，對于共享的內(nèi)存區(qū)域，也必須按照規(guī)定的權(quán)限規(guī)則來訪問，具有存儲保護(hù)功能。 ? 保護(hù)模式存儲管理方式的安全性和可靠性較好，適合于規(guī)模較大、較復(fù)雜和實時性要求不太高的系統(tǒng)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 69 ? 分區(qū)存儲管理適合在多道程序操作系統(tǒng)中應(yīng)用。分區(qū)存儲管理把整個內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)兩大區(qū)域，然后再把用戶區(qū)劃分為若干個分區(qū)，可以同時有多個任務(wù)在系統(tǒng)中運行，每個任務(wù)都有各自的地址空間。 ? 分區(qū)存儲管理又可以分為固定分區(qū)和可變分區(qū)兩類 。 ? 1．固定分區(qū)存儲管理 ? 采用固定分區(qū)存儲管理方法時，各個用戶分區(qū)的個數(shù)、位置和大小一旦確定后，就固定不變，不能再修改了。為了滿足不同程序的存儲需要，各個分區(qū)的大小可以是相等的，也可以是不相等的。 ? 固定分區(qū)存儲管理方法的優(yōu)點是易于實現(xiàn)，系統(tǒng)的開銷比較小，空閑空間的管理、內(nèi)存的分配和回收算法都非常簡單。其缺點是內(nèi)存的利用率不高，在任務(wù)所占用的分區(qū)內(nèi)部未被利用的空間的碎片（內(nèi)碎片）會造成很大的浪費；分區(qū)的總數(shù)是固定的，限制了并行執(zhí)行的程序個數(shù)， N個分區(qū)最多只能有 N個任務(wù)在同時運行。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 70 ? ? 采用可變分區(qū)存儲管理方法時，各分區(qū)不是預(yù)先劃分好的固定區(qū)域，而是系統(tǒng)動態(tài)創(chuàng)建的。在系統(tǒng)生成后，操作系統(tǒng)會占用內(nèi)存的一部分空間，通常放在內(nèi)存地址的最低端，其余的空間則成為一個完整的大空閑區(qū)。在裝入一個程序時，系統(tǒng)將根據(jù)它的需求和內(nèi)存空間的使用情況，從這個空閑區(qū)當(dāng)中劃出一塊來，分配給它，當(dāng)程序運行結(jié)束后會釋放所占用的存儲區(qū)域。系統(tǒng)通過對內(nèi)存的分配和回收，將一個完整的空閑區(qū)劃分成若干個占用區(qū)和空閑區(qū)。 ? 與固定分區(qū)相比，可變分區(qū)存儲管理的分區(qū)的個數(shù)、位置和大小都是隨著任務(wù)的進(jìn)出而動態(tài)變化的，非常靈活。每個分區(qū)都是按需分配的，分區(qū)的大小正好等于任務(wù)的大小。這樣就避免了在固定分區(qū)當(dāng)中由于分區(qū)的大小不當(dāng)所造成的內(nèi)碎片，從而提高了內(nèi)存的利用效率。但可變分區(qū)存儲管理也可能會存在外碎片。所謂的外碎片，就是在各個占用的分區(qū)之間，難以利用的一些空閑分區(qū)。外碎片通常是一些比較小的空閑分區(qū)。 ? 在具體實現(xiàn)可變分區(qū)存儲管理技術(shù)的時候，需要考慮內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)、內(nèi)存的分配算法以及內(nèi)存的回收算法三個方面的問題。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 71 ? 在內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)上，系統(tǒng)會維護(hù)一個分區(qū)鏈表，來跟蹤記錄每一個內(nèi)存分區(qū)的情況，包括該分區(qū)的狀態(tài)（已分配或空閑）、起始地址、長度等信息。 ? 在內(nèi)存的分配算法上，當(dāng)一個新任務(wù)來到時，需要為它尋找一個空閑分區(qū)，其大小必須大于或等于該任務(wù)的要求。若是大于要求，則將該分區(qū)分割成兩個小分區(qū)，其中一個分區(qū)為要求的大小并標(biāo)記為 “ 占用 ” ，另一個分區(qū)為余下部分并標(biāo)記為 “ 空閑 ” 。選擇分區(qū)的先后次序一般是從內(nèi)存低端到高端。通常的分區(qū)分配算法有：最先匹配法（ firstfit）、下次匹配法（ nextfit）、最佳匹配法 ( bestfit）和最壞匹配法（ worstfit）。 ? 在內(nèi)存的回收算法上，當(dāng)一個任務(wù)運行結(jié)束，并釋放它所占用的分區(qū)后，如果該分區(qū)的左右鄰居也是空閑分區(qū)，則需要將它們合并為一個大的空閑分區(qū)。與此相對應(yīng)，在分區(qū)鏈表上，也要將相應(yīng)的鏈接節(jié)點進(jìn)行合并，并對其內(nèi)容進(jìn)行更新。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 72 ? 1．物理地址和邏輯地址 ? 地址映射涉及到物理地址和邏輯地址兩個基本概念。 ? （ 1）物理地址（ physical address） ? 物理地址也叫內(nèi)存地址、絕對地址或?qū)嵉刂?。將系統(tǒng)內(nèi)存分割成很多個大小相等的存儲單元，如字節(jié)或字，每個單元給它一個編號，這個編號就稱為物理地址。操作時只有通過物理地址，才能對內(nèi)存單元進(jìn)行直接訪問。物理地址的集合就稱為物理地址空間，或者內(nèi)存地址空間。物理地址是一個一維的線性空間，例如，一個內(nèi)存的大小為 256MB，那么它的內(nèi)存地址空間是從 0x0到0x0FFFFFFF。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 73 ? （ 2）邏輯地址（ logical address） ? 邏輯地址也叫相對地址或虛地址 。用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，而這些目標(biāo)代碼通常采用的就是相對地址的形式，其首地址為 0，其余指令中的地址都是相對于這個首地址來編址的。顯然，邏輯地址和物理地址是完全不同的，不能用邏輯地址來直接訪問內(nèi)存單元。 ? 因此，為了保證 CPU在執(zhí)行指令時可以正確地訪問存儲單元，系統(tǒng)在 裝入一個用戶程序后，需要將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機(jī)器直接尋址的物理地址 ，這個過程就稱為地址映射。只有把程序當(dāng)中的邏輯地址轉(zhuǎn)換為物理地址，才能正常運行。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 Tech. 電子信息工程學(xué)院 74 ? 2. 地址映射方式 ? 地址映射是由存儲管理單元 MMU來完成的 。當(dāng)一條指令在 CPU當(dāng)中執(zhí)行時，在需要訪問內(nèi)存時， CPU就發(fā)送一個邏輯地址給 MMU，MMU負(fù)責(zé)把這個邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址，并根據(jù)這個物理地址去訪問內(nèi)存。地址映射主要有靜態(tài)地址映射和動態(tài)地址映射兩種方式。