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