【正文】 地址映射主要有靜態(tài)地址映射和動態(tài)地址映射兩種方式。 Tech. 電子信息工程學(xué)院 74 ? 2. 地址映射方式 ? 地址映射是由存儲管理單元 MMU來完成的 。只有把程序當(dāng)中的邏輯地址轉(zhuǎn)換為物理地址，才能正常運(yùn)行。顯然，邏輯地址和物理地址是完全不同的，不能用邏輯地址來直接訪問內(nèi)存單元。 Tech. 電子信息工程學(xué)院 73 ? （ 2）邏輯地址（ logical address） ? 邏輯地址也叫相對地址或虛地址 。物理地址是一個一維的線性空間，例如，一個內(nèi)存的大小為 256MB，那么它的內(nèi)存地址空間是從 0x0到0x0FFFFFFF。操作時只有通過物理地址，才能對內(nèi)存單元進(jìn)行直接訪問。 ? （ 1）物理地址（ physical address） ? 物理地址也叫內(nèi)存地址、絕對地址或?qū)嵉刂?。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 在內(nèi)存的回收算法上，當(dāng)一個任務(wù)運(yùn)行結(jié)束，并釋放它所占用的分區(qū)后，如果該分區(qū)的左右鄰居也是空閑分區(qū)，則需要將它們合并為一個大的空閑分區(qū)。選擇分區(qū)的先后次序一般是從內(nèi)存低端到高端。 ? 在內(nèi)存的分配算法上，當(dāng)一個新任務(wù)來到時，需要為它尋找一個空閑分區(qū)，其大小必須大于或等于該任務(wù)的要求。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。外碎片通常是一些比較小的空閑分區(qū)。但可變分區(qū)存儲管理也可能會存在外碎片。每個分區(qū)都是按需分配的，分區(qū)的大小正好等于任務(wù)的大小。系統(tǒng)通過對內(nèi)存的分配和回收，將一個完整的空閑區(qū)劃分成若干個占用區(qū)和空閑區(qū)。在系統(tǒng)生成后，操作系統(tǒng)會占用內(nèi)存的一部分空間，通常放在內(nèi)存地址的最低端，其余的空間則成為一個完整的大空閑區(qū)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 固定分區(qū)存儲管理方法的優(yōu)點(diǎn)是易于實現(xiàn)，系統(tǒng)的開銷比較小，空閑空間的管理、內(nèi)存的分配和回收算法都非常簡單。 ? 1．固定分區(qū)存儲管理 ? 采用固定分區(qū)存儲管理方法時，各個用戶分區(qū)的個數(shù)、位置和大小一旦確定后，就固定不變，不能再修改了。分區(qū)存儲管理把整個內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)兩大區(qū)域，然后再把用戶區(qū)劃分為若干個分區(qū)，可以同時有多個任務(wù)在系統(tǒng)中運(yùn)行，每個任務(wù)都有各自的地址空間。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 在保護(hù)模式存儲管理方式中，系統(tǒng)內(nèi)核和用戶程序有各自獨(dú)立的地址空間，操作系統(tǒng)和 MMU共同完成邏輯地址到物理地址的映射；每個應(yīng)用程序只能訪問自己的地址空間，對于共享的內(nèi)存區(qū)域，也必須按照規(guī)定的權(quán)限規(guī)則來訪問，具有存儲保護(hù)功能。其缺點(diǎn)是沒有存儲保護(hù)、安全性差，在應(yīng)用程序中出現(xiàn)的任何一個小錯誤或蓄意攻擊都有可能導(dǎo)致整個系統(tǒng)的崩潰。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。堆為 動態(tài)分配的內(nèi)存空間 ，在系統(tǒng)運(yùn)行時，可以通過類似于 malloc/free之類的函數(shù)來申請或釋放一段連續(xù)的內(nèi)存空間。 .data：（數(shù)據(jù)段）用來存放操作系統(tǒng)和應(yīng)用程序當(dāng)中所有 帶有初始值的全局變量 。 ? 在實模式存儲管理方式中，系統(tǒng)的內(nèi)存地址空間一般可以分為 text、 data、bss、堆、棧五個部分 。 Tech. 電子信息工程學(xué)院 67 ? 實模式和保護(hù)模式是嵌入式操作系統(tǒng)中常見的兩個存儲管理方式。MMU通常只在一些對安全性和可靠性的要求比較高、系統(tǒng)比較復(fù)雜的嵌入式系統(tǒng)中存在。 ? 操作系統(tǒng)通常 利用 MMU來實現(xiàn)系統(tǒng)內(nèi)核與應(yīng)用程序的隔離，以及應(yīng)用程序與應(yīng)用程序之間的隔離。內(nèi)存保護(hù)用來防止地址越界和防止操作越權(quán)。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。在 實時系統(tǒng)中，存儲管理方法就比較簡單 ，甚至不提供存儲管理功能。 Tech. 電子信息工程學(xué)院 65 嵌入式系統(tǒng)的存儲管理 ? ? 嵌入式系統(tǒng)的存儲管理方式與系統(tǒng)的實際應(yīng)用領(lǐng)域及硬件環(huán)境密切相關(guān)，不同的嵌入式系統(tǒng)采用不同的存儲管理方式，需要 考慮硬件條件、實時性要求、系統(tǒng)規(guī)模、可靠性要求等因素 。對于給定的一組任務(wù)，只要它們的CPU使用率小于或等于 1， EDF就能找到合適的調(diào)度順序 ，使得每個任務(wù)都能在自己的時間期限內(nèi)完成。 ? EDF算法假設(shè)條件除了它不要求系統(tǒng)中的任務(wù)都必須是周期任務(wù)外，其他的假設(shè)條件與 RMS相同。 ? EDF算法的基本思路是：根據(jù)任務(wù)的截止時間來確定其優(yōu)先級，對于時間期限最近的任務(wù)，分配最高的優(yōu)先級 。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 在任務(wù)比較多的情況下， RMS可調(diào)度的 CPU使用率上限 為 ln2＝， CPU使用率如此低，對于大多數(shù)系統(tǒng)來說是不可接受的。 ? RMS算法是一種 最優(yōu)調(diào)度算法 。 ? RMS算法假設(shè)：所有的任務(wù)都是周期性任務(wù)；任務(wù)的時間期限等于它的周期；任務(wù)在每個周期內(nèi)的執(zhí)行時間是一個常量；任務(wù)之間不進(jìn)行通信，也不需要同步；任務(wù)可以在任何位置被搶占，不存在臨界區(qū)的問題。 Tech. 電子信息工程學(xué)院 62 圖 RTOS任務(wù)模型 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。啟動時間 t（ i）是指第 i個任務(wù)的第 i次執(zhí)行的開始時間。 時間期限 （ deadline）是指 D（ i）第 i個任務(wù)所允許的最大響應(yīng)時間（從任務(wù)啟動到運(yùn)行結(jié)束所需的時間）。其中： 執(zhí)行時間 （ execution time） E（ i）是指對于第 i個任務(wù)，當(dāng)它所需要的資源都己具備時，它的執(zhí)行所需要的最長時間。 RTOS調(diào)度器多采用基于優(yōu)先級的可搶占調(diào)度算法。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。動態(tài)優(yōu)先級方式可以克服在靜態(tài)優(yōu)先級方式中高優(yōu)先級的任務(wù)一直占用著 CPU，而那些低優(yōu)先級的任務(wù)可能會長時間地得不到 CPU的情況。靜態(tài)優(yōu)先級方式根據(jù)任務(wù)的類型或重要性，在創(chuàng)建任務(wù)的時候就確定任務(wù)的優(yōu)先級，并且一直保持不變直到任務(wù)結(jié)束。而不可搶占方式則是需要等當(dāng)前任務(wù)運(yùn)行完后再決定。 ? 優(yōu)先級算法可以分為可搶占和不可搶占兩種方式。 Tech. 電子信息工程學(xué)院 60 ? 5．優(yōu)先級算法（ priority） ? 在優(yōu)先級調(diào)度算法（ priority）中，給每一個任務(wù)都設(shè)置一個優(yōu)先級，然后在任務(wù)調(diào)度的時候，在所有處于就緒狀態(tài)的任務(wù)中選擇優(yōu)先級最高的那個任務(wù)去運(yùn)行。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 q太大，每個任務(wù)都在一個時間片內(nèi)完成，這就失去了 RR算法的意義。 ? 采用 RR算法，各個就緒任務(wù)平均地分配 CPU的使用時間，例如有 n個就緒任務(wù)，那么每個任務(wù)將得到 1/n的 CPU時間。當(dāng)這個時間片結(jié)束的時候，如果任務(wù)還沒有執(zhí)行完的話，將會發(fā)生時鐘中斷，調(diào)度器將會暫停當(dāng)前任務(wù)的執(zhí)行，并把這個任務(wù)送到就緒隊列的末尾，然后再執(zhí)行當(dāng)前的隊列的第一個任務(wù)。 Tech. 電子信息工程學(xué)院 58 ? 4．時間片輪轉(zhuǎn)算法（ Round Robin， RR） ? RR算法如圖 。 Tech. 電子信息工程學(xué)院 57 ? 不可搶占的 SJF算法如圖 ，由于任務(wù) T3的執(zhí)行時間最短，所以首先被調(diào)度運(yùn)行，其次是 T1和 T2。而在可搶占方式，當(dāng)前任務(wù)正在運(yùn)行的時候，來了一個比它執(zhí)行時間更短的任務(wù)，而且它的運(yùn)行時間要小于當(dāng)前正在運(yùn)行的任務(wù)的剩余時間，那么這個新任務(wù)就會搶占 CPU去運(yùn)行。 ? SJF算法有不可搶占方式和可搶占方式兩種實現(xiàn)方案。 Tech. 電子信息工程學(xué)院 56 ? 3．短作業(yè)優(yōu)先算法（ Shortest Job First， SJF） ? 在 SJF（ Shortest Job First，短作業(yè)優(yōu)先算法）中，在各個任務(wù)在開始執(zhí)行前，事先預(yù)計好各任務(wù)的執(zhí)行時間，調(diào)度算法根據(jù)這些預(yù)計時間，安排執(zhí)行時間較短的任務(wù)優(yōu)先執(zhí)行。缺點(diǎn)是一批任務(wù)的平均周轉(zhuǎn)時間取決于各個任務(wù)到達(dá)的順序，如果短任務(wù)位于長任務(wù)之后，那么將增大平均周轉(zhuǎn)時間。 FCFS也叫做 FIFO（ First In First Out，先進(jìn)先出算法）。 Tech. 電子信息工程學(xué)院 55 ? 2．先來先服務(wù)算法（ First Come First Served， FCFS） ? FCFS（ First Come First Served，先來先服務(wù)算法）是一種最簡單的調(diào)度算法。 ? 對于一個調(diào)度算法來說，這些指標(biāo)中一些是共存的，而另一些是相互牽制的，這些指標(biāo)不可能全部都實現(xiàn)，而是需要根據(jù)系統(tǒng)的要求，綜合權(quán)衡和折中選擇。 ? ● 均衡性（ balance）是指要盡可能使整個系統(tǒng)的各個部分（ CPU， I/O）都忙起來，提高系統(tǒng)資源的使用效率。 Tech. 電子信息工程學(xué)院 54 ? ● 公平性（ fairness ）是指大致相當(dāng)?shù)膬蓚€任務(wù)所得到的 CPU時間也應(yīng)該是大致相同的。 ? ● 調(diào)度器在做出調(diào)度決策時所需要的時間和空間開銷稱為調(diào)度開銷（ overhead）。其中： ? ● 調(diào)度器為一個就緒任務(wù)進(jìn)行上下文切換時所需的時間，以及任務(wù)在就緒隊列中的等待時間稱為響應(yīng)時間（ response time ）。 ? 在嵌入式操作系統(tǒng)中，存在著許多的調(diào)度算法，每一種算法都有各自的優(yōu)點(diǎn)和缺點(diǎn)。當(dāng)出現(xiàn)新任務(wù)創(chuàng)建、任務(wù)運(yùn)行結(jié)束及任務(wù)被阻塞的調(diào)度時機(jī)時，有可能會發(fā)生調(diào)度。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。調(diào)度程序可以去打斷它，并安排另外的任務(wù)去運(yùn)行。 ? 任務(wù)調(diào)度存在可搶占調(diào)度（ preemptive）和不可搶占調(diào)度（ nonpreemptive）兩種調(diào)度方式。調(diào)度器在決策過程中所采用的算法稱為調(diào)度算法。 Tech. 電子信息工程學(xué)院 52 任務(wù)的調(diào)度 ? 1．任務(wù)調(diào)度概述 ? 在多道程序操作系統(tǒng)中，當(dāng)有兩個或多個任務(wù)同時處于就緒狀態(tài)時，而系統(tǒng)中只有一個 CPU而且這個 CPU己經(jīng)空閑下來了，就會出現(xiàn)多個任務(wù)同時去競爭這個 CPU的情況。如果一個任務(wù)的狀態(tài)發(fā)生變化，就要把它的 TCB從一個狀態(tài)隊列中脫離出來，加入到另一個隊列當(dāng)中去。不同的狀態(tài)用不同的隊列來表示。 ? 操作系統(tǒng)用一組隊列來表示系統(tǒng)當(dāng)中所有任務(wù)的當(dāng)前狀態(tài)。 Tech. 電子信息工程學(xué)院 51 ? 6．任務(wù)隊列 ? 在一個多任務(wù)的操作系統(tǒng)中，各個任務(wù)的狀態(tài)是經(jīng)常變化的，有時處于運(yùn)行狀態(tài)，有時處于就緒狀態(tài)，有時又處于阻塞狀態(tài)。 ? （ 5）根據(jù)新任務(wù)的 TCB的內(nèi)容，恢復(fù)它的運(yùn)行上下文環(huán)境。 ? （ 3）按照一定的策略，從所有處于就緒狀態(tài)的任務(wù)中選擇一個去運(yùn)行。 Tech. 電子信息工程學(xué)院 50 ? 5．任務(wù)切換 ? 任務(wù)切換（ context switching）是指一個任務(wù)正在 CPU上運(yùn)行，由于某種原因，系統(tǒng)需要調(diào)度另一個任務(wù)去運(yùn)行，那么這時就需要進(jìn)行把當(dāng)前任務(wù)的運(yùn)行上下文保存起來，并設(shè)置新任務(wù)的上下文，這一過程稱為任務(wù)切換。 ? （ 3）資源管理信息 ? 在操作系統(tǒng)中，任務(wù)表示的是進(jìn)程，則還應(yīng)包含一些資源管理方面的信息，如段表地址、頁表地址等存儲管理方面的信息，根目錄、文件描述字等文件管理方面的信息。 Tech. 電子信息工程學(xué)院 49 ? （ 2） CPU上下文信息 ? CPU上下文信息包括通用寄存器、 PC寄存器、程序狀態(tài)字、棧指針等各種 CPU寄存器的當(dāng)前值。 ? （ 1）任務(wù)的管理信息 ? 任務(wù)的管理信息包括任務(wù)的標(biāo)識 ID、任務(wù)的狀態(tài)、任務(wù)的優(yōu)先級、任務(wù)的調(diào)度信息、任務(wù)的時間統(tǒng)計信息、各種隊列指針等。對任務(wù)的組織和管理可以通過對它們的 TCB的組織和管理來實現(xiàn)。可以把 TCB看成是任務(wù)存在的唯一標(biāo)志。通過對各個任務(wù)的 TCB的操作來實現(xiàn)任務(wù)管理。 圖 任務(wù)間的狀態(tài)轉(zhuǎn)換圖 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。此時，即使 CPU已經(jīng)空閑下來了，該任務(wù)也還是不能運(yùn)行。 吳貴芳 qq:6974784 Henan Uni versity of Sci . amp。 ? 當(dāng)一個任務(wù)已具備運(yùn)行條件，但由于 CPU正在運(yùn)行其他的任務(wù)，暫時不能運(yùn)行該任務(wù)時，稱為就緒狀態(tài)。 ? 任務(wù)在運(yùn)行狀態(tài)時占有 CPU并在 CPU上運(yùn)行，在任何一個時刻，處于運(yùn)行狀態(tài)的任務(wù)個數(shù)必須小于或等于 CPU的數(shù)目。 ? 3．任務(wù)的狀態(tài) ? 在多道程序系統(tǒng)中，任務(wù)是獨(dú)立運(yùn)行的實體，需要競爭系統(tǒng)資源，而任務(wù)所擁有的資源是在不斷變化中的，使得任務(wù)的狀態(tài)也在不斷的變化。 Tech. 電子信息工程學(xué)院 46 ? 在一些操作系統(tǒng)中可以提供一些系統(tǒng)調(diào)用函數(shù)，用來把一個任務(wù)從系統(tǒng)中清除出局，稱為被其他任務(wù)踢出。 ? 當(dāng)一個任務(wù)在執(zhí)行過程中，出現(xiàn)了致命的錯誤（例如執(zhí)行了非法指令、內(nèi)存訪問錯誤等），系統(tǒng)中止該任務(wù)的運(yùn)行，強(qiáng)制性地讓該任務(wù)退出，稱為錯誤退出。 ? （ 2）任務(wù)