【正文】 待狀態(tài)（ waiting）。 ? 如圖 ，在一定條件下，任務(wù)會(huì)在不同的狀態(tài)之間來(lái)回轉(zhuǎn)換，存在運(yùn)行 → 阻塞、運(yùn)行 → 就緒、就緒 → 運(yùn)行、阻塞 → 就緒四種轉(zhuǎn)換關(guān)系。 Tech. 電子信息工程學(xué)院 48 ? 4．任務(wù)控制塊 ? TCB（ Task Control Block，任務(wù)控制塊）是在操作系統(tǒng)當(dāng)中用來(lái)描述和管理一個(gè)任務(wù)的數(shù)據(jù)結(jié)構(gòu)。利用 TCB這個(gè)數(shù)據(jù)結(jié)構(gòu)可以描述任務(wù)的基本情況，以及它的運(yùn)行變化過(guò)程。當(dāng)需要?jiǎng)?chuàng)建一個(gè)新任務(wù)的時(shí)候，就為它生成一個(gè) TCB，并初始化這個(gè) TCB的內(nèi)容；當(dāng)需要終止一個(gè)任務(wù)的時(shí)候，只要回收它的 TCB即可。 TCB主要包括任務(wù)的管理信息、 CPU上下文信息、資源管理信息等內(nèi)容。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。在實(shí)際的嵌入式系統(tǒng)中， CPU上下文信息不一定直接存放在 TCB當(dāng)中，而是存放在任務(wù)的棧當(dāng)中，可以通過(guò)相應(yīng)的棧指針來(lái)訪問(wèn)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 任務(wù)切換通常包含有以下幾個(gè)基本步驟： ? （ 1）將處理器的運(yùn)行上下文保存在當(dāng)前任務(wù)的 TCB中； ? （ 2）更新當(dāng)前任務(wù)的狀態(tài)，從運(yùn)行狀態(tài)變?yōu)榫途w狀態(tài)或阻塞狀態(tài)。 ? （ 4）修改新任務(wù)的狀態(tài)，從就緒狀態(tài)變成運(yùn)行狀態(tài)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。通常采用任務(wù)隊(duì)列的方式來(lái)組織它的所有任務(wù)，以提高對(duì)這些任務(wù)的管理效率。例如，處于運(yùn)行狀態(tài)的所有任務(wù)構(gòu)成了運(yùn)行隊(duì)列，處于就緒狀態(tài)的所有任務(wù)構(gòu)成了就緒隊(duì)列，而對(duì)于處于阻塞狀態(tài)的任務(wù)，則要根據(jù)它們阻塞的原因，分別構(gòu)成相應(yīng)的阻塞隊(duì)列。然后，對(duì)于系統(tǒng)當(dāng)中的每一個(gè)任務(wù)，根據(jù)它的狀態(tài)把它的 TCB加入到相應(yīng)的隊(duì)列當(dāng)中去。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。通常利用調(diào)度器（ scheduler）選擇就緒隊(duì)列中的那些任務(wù)中的一個(gè)去運(yùn)行，調(diào)度器是 CPU這個(gè)資源的管理者。 ? 一般來(lái)說(shuō)，在一個(gè)新的任務(wù)被創(chuàng)建時(shí)、在一個(gè)任務(wù)運(yùn)行結(jié)束時(shí)、在一個(gè)任務(wù)由于 I/O操作、信號(hào)量或其他原因被阻塞時(shí)、在一個(gè)I/O中斷發(fā)生時(shí)、在一個(gè)時(shí)鐘中斷發(fā)生時(shí)這五種調(diào)度時(shí)機(jī)都可能會(huì)發(fā)生任務(wù)的調(diào)度。 ? （ 1）在可搶占調(diào)度方式，當(dāng)一個(gè)任務(wù)正在運(yùn)行的時(shí)候，出現(xiàn)調(diào)度時(shí)機(jī)當(dāng)中的五種情況之一，都有可能會(huì)發(fā)生調(diào)度。實(shí)時(shí)操作系統(tǒng)大都采用可搶占的調(diào)度方式。 Tech. 電子信息工程學(xué)院 53 ? （ 2）在不可搶占調(diào)度方式，一個(gè)任務(wù)長(zhǎng)時(shí)間地占用著 CPU系統(tǒng)也不會(huì)強(qiáng)制它中止。而對(duì)于發(fā)生的各種中斷，并不會(huì)去調(diào)用調(diào)度程序，而是在中斷處理完成后，又會(huì)回到剛才被打斷的任務(wù)中繼續(xù)執(zhí)行?？梢愿鶕?jù)響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間、調(diào)度開(kāi)銷(xiāo)、公平性、均衡性、吞吐量等指標(biāo)來(lái)評(píng)價(jià)一個(gè)調(diào)度算法的好壞。 ? ● 一個(gè)任務(wù)從提交到完成所經(jīng)歷的時(shí)間稱(chēng)為周轉(zhuǎn)時(shí)間（ turnaround time ）。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。另外，要防止饑餓（ starvation）情況出現(xiàn)，即某一個(gè)任務(wù)始終得不到處理器去運(yùn)行。 ? ● 單位時(shí)間內(nèi)完成的任務(wù)數(shù)量稱(chēng)為吞吐量（ throughput ）。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 FCFS的基本思想就是按照任務(wù)到達(dá)的先后次序來(lái)進(jìn)行調(diào)度，它是一種不可搶占的調(diào)度方式。 ? FCFS的最大優(yōu)點(diǎn)就是簡(jiǎn)單，易于理解也易于實(shí)現(xiàn)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。可以證明，對(duì)于一批同時(shí)到達(dá)的任務(wù)，采用 SJF算法將得到一個(gè)最小的平均周轉(zhuǎn)時(shí)間。在不可搶占方式，只有任務(wù)運(yùn)行完畢或者是被阻塞時(shí)，才會(huì)讓出 CPU進(jìn)行新的調(diào)度。這種方法也稱(chēng)為 SRTF（ Shortest Remaining Time First，最短剩余時(shí)間優(yōu)先算法） 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 圖 SJF算法示意圖 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。在 RR（ Round Robin，時(shí)間片輪轉(zhuǎn)算法）中，把系統(tǒng)當(dāng)中的所有就緒任務(wù)按照先來(lái)先服務(wù)的原則進(jìn)行排列，然后，在每次調(diào)度的時(shí)候，處理器分派給隊(duì)列當(dāng)中的第一個(gè)任務(wù)一小段 CPU執(zhí)行時(shí)間（ time slice，時(shí)間片）。如果一個(gè)任務(wù)在分配給它的時(shí)間片結(jié)束前就已經(jīng)運(yùn)行結(jié)束了或者是被阻塞了，那么它就會(huì)立即讓出 CPU給其他的任務(wù)。 ? 采用 RR算法時(shí)，時(shí)間片 q既不能太大，也不能太小。如果 q太小，每個(gè)任務(wù)都需要更多的時(shí)間片才能運(yùn)行完，增加了在任務(wù)之間的切換次數(shù)，增大了系統(tǒng)的管理開(kāi)銷(xiāo)，降低了 CPU的使用效率。 Tech. 電子信息工程學(xué)院 59 圖 RR算法示意圖 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。例如，在短作業(yè)優(yōu)先算法中，以時(shí)間為優(yōu)先級(jí)，運(yùn)行時(shí)間越短，優(yōu)先級(jí)越高。在可搶占方式中，當(dāng)一個(gè)任務(wù)正在運(yùn)行的時(shí)候，如果這時(shí)來(lái)了一個(gè)新的任務(wù)，其優(yōu)先級(jí)更高，則立即搶占 CPU去運(yùn)行這個(gè)新任務(wù)。 ? 可以采用靜態(tài)方式和動(dòng)態(tài)方式確定任務(wù)的優(yōu)先級(jí)。動(dòng)態(tài)優(yōu)先級(jí)方式在創(chuàng)建任務(wù)的時(shí)候確定任務(wù)的優(yōu)先級(jí)，但是該優(yōu)先級(jí)可以在任務(wù)的運(yùn)行過(guò)程中動(dòng)態(tài)改變，以便獲得更好的調(diào)度性能。 ? 在優(yōu)先級(jí)算法中，對(duì)于優(yōu)先級(jí)相同的兩個(gè)任務(wù)，通常是把任務(wù)按照不同的優(yōu)先級(jí)進(jìn)行分組，然后在不同組的任務(wù)之間使用優(yōu)先級(jí)算法，而在同一組的各個(gè)任務(wù)之間使用時(shí)間片輪轉(zhuǎn)法。 Tech. 電子信息工程學(xué)院 61 實(shí)時(shí)系統(tǒng)調(diào)度 ? 許多嵌入式操作系統(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)。 ? 1． RTOS任務(wù)模型 ? RTOS任務(wù)模型如圖 ，在 RTOS任務(wù)模型中，每一個(gè)任務(wù)用一個(gè) 三元組來(lái)表示（執(zhí)行時(shí)間、周期、時(shí)間期限） 。 周期 （ period）P（ i）是指第 i個(gè)任務(wù)的連續(xù)兩次運(yùn)行之間的最小時(shí)間間隔。一般來(lái)說(shuō)，一個(gè)任務(wù)的周期時(shí)間同時(shí)也是它的時(shí)間期限，因?yàn)樵撊蝿?wù)必須在它的下一個(gè)周期開(kāi)始之前，完成此次運(yùn)行。 吳貴芳 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算法的基本思路是任務(wù)的優(yōu)先級(jí)與它的周期表現(xiàn)為單調(diào)函數(shù)的關(guān)系， 任務(wù)的周期越短，優(yōu)先級(jí)越高 ；任務(wù)的周期越長(zhǎng)，優(yōu)先級(jí)越低。如果存在一種基于靜態(tài)優(yōu)先級(jí)的調(diào)度順序，使得每個(gè)任務(wù)都能在其期限時(shí)間內(nèi)完成，那么 RMS算法總能找到這樣的一種可行的調(diào)度方案。另外，在一個(gè)實(shí)際的系統(tǒng)中，任務(wù)之間通常都需要進(jìn)行通信和同步。 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)度算法。當(dāng)有一個(gè)新的任務(wù)處于就緒狀態(tài)時(shí)，各個(gè)任務(wù)的優(yōu)先級(jí)就有可能要進(jìn)行調(diào)整。 ? EDF算法可調(diào)度上限為 100％。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 系統(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í)刻之前完成。而對(duì)一些實(shí)時(shí)性要求不高，可靠性要求比較高、比較復(fù)雜的應(yīng)用系統(tǒng)，需要實(shí)現(xiàn)對(duì)操作系統(tǒng)或任務(wù)的保護(hù)，在存儲(chǔ)管理方式上就相對(duì)較為復(fù)雜。 Tech. 電子信息工程學(xué)院 66 ? 在嵌入式微處理器中， MMU（ Memory Management Unit, 存儲(chǔ)管理單元）提供了一種內(nèi)存保護(hù)的硬件機(jī)制 。采用內(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)處理。防止應(yīng)用程序去破壞操作系統(tǒng)和其他應(yīng)用程序的代碼和數(shù)據(jù)，防止應(yīng)用程序?qū)τ布闹苯釉L問(wèn)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 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ú)享的，其他資源都是共享的。其中： .text：（代碼段）用來(lái)存放操作系統(tǒng)和應(yīng)用程序的 所有代碼 。 .bss：用來(lái)存放操作系統(tǒng)和應(yīng)用程序當(dāng)中所有 未帶初始值的全局變量 。棧用來(lái)保存運(yùn)行上下文以及函數(shù)調(diào)用時(shí)的 局部變量和運(yùn)行參數(shù) 。 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)。 ? 2．保護(hù)模式存儲(chǔ)管理 ? 在保護(hù)模式存儲(chǔ)管理方式中， 微處理器必須具有 MMU硬件 并啟用它。 ? 保護(hù)模式存儲(chǔ)管理方式的安全性和可靠性較好，適合于規(guī)模較大、較復(fù)雜和實(shí)時(shí)性要求不太高的系統(tǒng)。 Tech. 電子信息工程學(xué)院 69 ? 分區(qū)存儲(chǔ)管理適合在多道程序操作系統(tǒng)中應(yīng)用。 ? 分區(qū)存儲(chǔ)管理又可以分為固定分區(qū)和可變分區(qū)兩類(lèi) 。為了滿足不同程序的存儲(chǔ)需要，各個(gè)分區(qū)的大小可以是相等的，也可以是不相等的。其缺點(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)行。 Tech. 電子信息工程學(xué)院 70 ? ? 采用可變分區(qū)存儲(chǔ)管理方法時(shí)，各分區(qū)不是預(yù)先劃分好的固定區(qū)域，而是系統(tǒng)動(dòng)態(tài)創(chuàng)建的。在裝入一個(gè)程序時(shí)，系統(tǒng)將根據(jù)它的需求和內(nèi)存空間的使用情況，從這個(gè)空閑區(qū)當(dāng)中劃出一塊來(lái)，分配給它，當(dāng)程序運(yùn)行結(jié)束后會(huì)釋放所占用的存儲(chǔ)區(qū)域。 ? 與固定分區(qū)相比，可變分區(qū)存儲(chǔ)管理的分區(qū)的個(gè)數(shù)、位置和大小都是隨著任務(wù)的進(jìn)出而動(dòng)態(tài)變化的，非常靈活。這樣就避免了在固定分區(qū)當(dāng)中由于分區(qū)的大小不當(dāng)所造成的內(nèi)碎片，從而提高了內(nèi)存的利用效率。所謂的外碎片，就是在各個(gè)占用的分區(qū)之間，難以利用的一些空閑分區(qū)。 ? 在具體實(shí)現(xiàn)可變分區(qū)存儲(chǔ)管理技術(shù)的時(shí)候，需要考慮內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)、內(nèi)存的分配算法以及內(nèi)存的回收算法三個(gè)方面的問(wèn)題。 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)度等信息。若是大于要求，則將該分區(qū)分割成兩個(gè)小分區(qū)，其中一個(gè)分區(qū)為要求的大小并標(biāo)記為 “ 占用 ” ，另一個(gè)分區(qū)為余下部分并標(biāo)記為 “ 空閑 ” 。通常的分區(qū)分配算法有：最先匹配法（ firstfit）、下次匹配法（ nextfit）、最佳匹配法 ( bestfit）和最壞匹配法（ worstfit）。與此相對(duì)應(yīng)，在分區(qū)鏈表上，也要將相應(yīng)的鏈接節(jié)點(diǎn)進(jìn)行合并，并對(duì)其內(nèi)容進(jìn)行更新。 Tech. 電子信息工程學(xué)院 72 ? 1．物理地址和邏輯地址 ? 地址映射涉及到物理地址和邏輯地址兩個(gè)基本概念。將系統(tǒng)內(nèi)存分割成很多個(gè)大小相等的存儲(chǔ)單元，如字節(jié)或字，每個(gè)單元給它一個(gè)編號(hào)，這個(gè)編號(hào)就稱(chēng)為物理地址。物理地址的集合就稱(chēng)為物理地址空間，或者內(nèi)存地址空間。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。用戶的程序經(jīng)過(guò)匯編或編譯后形成目標(biāo)代碼，而這些目標(biāo)代碼通常采用的就是相對(duì)地址的形式，其首地址為 0，其余指令中的地址都是相對(duì)于這個(gè)首地址來(lái)編址的。 ? 因此，為了保證 CPU在執(zhí)行指令時(shí)可以正確地訪問(wèn)存儲(chǔ)單元，系統(tǒng)在 裝入一個(gè)用戶程序后，需要將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址 ，這個(gè)過(guò)程就稱(chēng)為地址映射。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。當(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)