實(shí)時(shí)操作系統(tǒng)的內(nèi)核

實(shí)時(shí)操作系統(tǒng)的內(nèi)核第1頁/共20頁任何時(shí)刻系統(tǒng)中只能有一個(gè)任務(wù)在運(yùn)行狀態(tài)，各任務(wù)按級別通過時(shí)間片使它獲得對CPU的訪問權(quán)。任務(wù)就緒后進(jìn)入就緒態(tài)，等待隊(duì)列。通過調(diào)度程序使它獲得CPU和資源使用權(quán)，從而進(jìn)入運(yùn)行態(tài)。任務(wù)在運(yùn)行時(shí)因申請資源等原因而掛起，轉(zhuǎn)入掛起態(tài)，等待運(yùn)行條件的滿足。當(dāng)條件滿足后，任務(wù)被喚醒進(jìn)入就緒態(tài)，等待系統(tǒng)調(diào)度程序依據(jù)調(diào)度算法進(jìn)行調(diào)度。任務(wù)的休眠態(tài)是任務(wù)雖然在內(nèi)存中，但不被實(shí)時(shí)內(nèi)核所調(diào)度的狀態(tài)。任務(wù)還有一個(gè)狀態(tài)，即被中斷狀態(tài)，它指任務(wù)在運(yùn)行態(tài)時(shí)有中斷請求到達(dá)，系統(tǒng)響應(yīng)中斷，轉(zhuǎn)而執(zhí)行中斷服務(wù)子程序，任務(wù)被中斷后所處的狀態(tài)。多任務(wù)運(yùn)行的實(shí)現(xiàn)是靠CPU在許多任務(wù)之間轉(zhuǎn)換、調(diào)度。CPU只有一個(gè)，輪流服務(wù)于一系列任務(wù)中的某一個(gè)。多任務(wù)系統(tǒng)中，內(nèi)核負(fù)責(zé)管理各個(gè)任務(wù)，并負(fù)責(zé)任務(wù)之間的通信。內(nèi)核提供的基本服務(wù)是任務(wù)切換。內(nèi)核對CPU的占用時(shí)間一般在2-5％之間。第2頁/共20頁任務(wù)要獲得CPU的控制權(quán)，從就緒態(tài)進(jìn)入運(yùn)行態(tài)是通過任務(wù)調(diào)度器完成的。任務(wù)調(diào)度器從當(dāng)前已就緒的所有任務(wù)中，依照任務(wù)調(diào)度算法選擇一個(gè)最符合算法要求的任務(wù)進(jìn)入運(yùn)行狀態(tài)。任務(wù)調(diào)度算法的選擇很大程序上決定了該操作系統(tǒng)的實(shí)時(shí)性能，這也是種類繁多的實(shí)時(shí)內(nèi)核卻無一例外選用特定的幾個(gè)實(shí)時(shí)調(diào)度算法的原因。調(diào)度是操作系統(tǒng)的主要職責(zé)之一，它決定該輪到哪個(gè)任務(wù)運(yùn)行。往往調(diào)度是基于優(yōu)先級的，根據(jù)其重要不同被給于任務(wù)不同的優(yōu)先級。CPU總是讓處于就緒態(tài)的優(yōu)先級最高的任務(wù)先運(yùn)行。何時(shí)讓高優(yōu)先級任務(wù)掌握CPU的使用權(quán)，要看用的是什么類型的內(nèi)核，是非搶占式的還是搶占式的內(nèi)核。實(shí)時(shí)操作系統(tǒng)中常用的任務(wù)調(diào)度算法包括基于優(yōu)先級的搶占式調(diào)度算法、同一優(yōu)先級的時(shí)間片輪轉(zhuǎn)調(diào)度算法和單調(diào)速率調(diào)度算法。第3頁/共20頁1.1基于優(yōu)先級的搶占式調(diào)度算法實(shí)時(shí)系統(tǒng)為每個(gè)任務(wù)賦予一個(gè)優(yōu)先級。任務(wù)優(yōu)先級在一定程序上體現(xiàn)了任務(wù)的緊迫性和重要性，越重要的任務(wù)賦予的優(yōu)先級就越高。實(shí)時(shí)系統(tǒng)允許多個(gè)任務(wù)共享一個(gè)優(yōu)先級，通過同一優(yōu)先級的時(shí)間片輪轉(zhuǎn)調(diào)度算法，完成任務(wù)的調(diào)度。優(yōu)先級調(diào)度原則是讓高優(yōu)先級的任務(wù)在得到資源運(yùn)行的事件上比低優(yōu)先級的任務(wù)更有優(yōu)先權(quán)。這保證了實(shí)時(shí)系統(tǒng)中緊急的、對時(shí)間有嚴(yán)格限制的任務(wù)能得到更為優(yōu)先的處理，而相對不緊急的任務(wù)則等到緊急任務(wù)處理完后才繼續(xù)運(yùn)行。實(shí)時(shí)操作系統(tǒng)都采用基于優(yōu)先級的任務(wù)調(diào)度算法。按照任務(wù)在運(yùn)行過程中是否能被搶占，可以分為搶占式調(diào)度和非搶占式調(diào)度。第4頁/共20頁1.1.1非搶占式調(diào)度非搶占式調(diào)度法也稱為合作型多任務(wù)，各個(gè)任務(wù)彼此合作共享一個(gè)CPU。中斷服務(wù)可以使一個(gè)高優(yōu)先級的任務(wù)由掛起狀態(tài)變?yōu)榫途w狀態(tài)。但中斷服務(wù)以后控制權(quán)還是回到原來被中斷的那個(gè)任務(wù)，直到該任務(wù)主動(dòng)放棄CPU的使用權(quán)，那個(gè)高優(yōu)先級的任務(wù)才能獲得CPU的使用權(quán)。非搶占式內(nèi)核的一個(gè)特點(diǎn)是幾乎不需要使用信號量保護(hù)共享數(shù)據(jù)。運(yùn)行的任務(wù)占有CPU，而不必?fù)?dān)心被別的任務(wù)搶占。非搶占式內(nèi)核的最大缺陷在于其響應(yīng)高優(yōu)先級的任務(wù)慢，任務(wù)已進(jìn)入就緒態(tài)但還不能運(yùn)行，也許要等很長的時(shí)間，直到當(dāng)前運(yùn)行的任務(wù)釋放CPU。內(nèi)核的任務(wù)級響應(yīng)時(shí)間是不確定的，最高優(yōu)先級的任務(wù)什么時(shí)候才能拿到CPU的控制權(quán)完全取決于應(yīng)用程序什么時(shí)候釋放CPU。見P27圖1-6。第5頁/共20頁由于其他任務(wù)不能搶占該任務(wù)的CPU控制權(quán)，如果該任務(wù)不主動(dòng)釋放CPU，則勢必使系統(tǒng)進(jìn)入死鎖。每個(gè)任務(wù)在設(shè)計(jì)過程必須在任務(wù)結(jié)束時(shí)釋放所占用的資源，它不能是一個(gè)無限運(yùn)行的循環(huán)。這是非搶占式內(nèi)核運(yùn)行的先決條件。優(yōu)點(diǎn)：*響應(yīng)中斷快。*可使用不可重入函數(shù)。由于任務(wù)運(yùn)行過程中不會(huì)被其他任務(wù)搶占，各任務(wù)使用的子函數(shù)不會(huì)被重入，所以在非搶占式調(diào)度算法中可以使用不可重入函數(shù)。*共享數(shù)據(jù)方便。任務(wù)運(yùn)行過程中不被搶占，內(nèi)存中的共享數(shù)據(jù)被一個(gè)任務(wù)使用時(shí)，不會(huì)出現(xiàn)被另一個(gè)任務(wù)使用的情況，這使得任務(wù)在使用共享數(shù)據(jù)時(shí)不使用信號量等保護(hù)機(jī)制。當(dāng)然，由于中斷服務(wù)子程序可以中斷任務(wù)的執(zhí)行，所以任務(wù)與中斷服務(wù)子程序的共享數(shù)據(jù)保護(hù)問題仍然是設(shè)計(jì)系統(tǒng)中必須考慮的問題。第6頁/共20頁1.1.2搶占式調(diào)度當(dāng)系統(tǒng)響應(yīng)時(shí)間很重要時(shí)，要使用搶占式內(nèi)核。最高優(yōu)先級的任務(wù)一旦就緒，總能得到CPU的控制權(quán)。當(dāng)一個(gè)運(yùn)行的任務(wù)時(shí)，另一個(gè)比它優(yōu)先級高的任務(wù)進(jìn)入了就緒態(tài)，當(dāng)前任務(wù)的CPU使用權(quán)就被剝奪了，或者說被掛起了，高優(yōu)先級的任務(wù)立即得到CPU的控制權(quán)。搶占式調(diào)度算法滿足在處理器中運(yùn)行的任務(wù)是已就緒任務(wù)中優(yōu)先級最高的任務(wù)。任務(wù)在執(zhí)行過程中允許更高的優(yōu)先級任務(wù)搶占該任務(wù)對CPU的控制權(quán)。與非搶占式調(diào)度算法不同的是當(dāng)任務(wù)被中斷，中斷服務(wù)子程序運(yùn)行完成后，不一定返回被中斷的任務(wù)，而是執(zhí)行新的任務(wù)調(diào)度，看就緒隊(duì)列中是否有比被中斷的任務(wù)擁有更高優(yōu)先級的任務(wù)就緒。如果有，更高優(yōu)先級的任務(wù)就調(diào)入并運(yùn)該任務(wù);否則，繼續(xù)運(yùn)行被中斷的任務(wù)。如P28圖1-7。第7頁/共20頁搶占式調(diào)度算法的特點(diǎn)是任務(wù)級響應(yīng)時(shí)間得到最優(yōu)化，而且是確定的，因而中斷響應(yīng)較快。由于任務(wù)在運(yùn)行過程中可以被其他任務(wù)搶占，所以任務(wù)不應(yīng)直接使用不可重入函數(shù)，只有對不可重入函數(shù)進(jìn)行加鎖保護(hù)才能使用。同理，對共享數(shù)據(jù)的使用也需要互斥，信號量等保護(hù)機(jī)制。絕大多數(shù)的實(shí)時(shí)內(nèi)核使用基于優(yōu)先級的搶占式調(diào)度算法。在實(shí)時(shí)系統(tǒng)中，使用基于優(yōu)先級的搶占式調(diào)度算法時(shí)，要特別注意對優(yōu)先級反轉(zhuǎn)問題進(jìn)行處理。優(yōu)先級反轉(zhuǎn)問題體現(xiàn)的是高優(yōu)先級的任務(wù)等待，屬于被低優(yōu)先級任務(wù)占有系統(tǒng)資源而形成的高優(yōu)先級任務(wù)等待低優(yōu)先級運(yùn)行的反常情況。如果低優(yōu)先級在運(yùn)行時(shí)又被其他任務(wù)搶占，則系統(tǒng)運(yùn)行情況會(huì)更糟。見P28實(shí)例。解決優(yōu)先級反轉(zhuǎn)的問題有優(yōu)先級繼承和優(yōu)先級封頂兩種方法。第8頁/共20頁（1）優(yōu)先級繼承優(yōu)先級繼承要點(diǎn)如下：*設(shè)C為正占用某項(xiàng)共享資源的進(jìn)程P以及所有正在等待占用此資源的進(jìn)程的集合。*找出這個(gè)集合中的優(yōu)先級最高者P_h，其優(yōu)先級為P’。*把進(jìn)程P的優(yōu)先級設(shè)置為P’。見圖P1-9。第9頁/共20頁（2）優(yōu)先級封頂優(yōu)先級封項(xiàng)要點(diǎn)如下：*設(shè)C為所有可能競爭使用某項(xiàng)共享資源的進(jìn)程的集合。事先為這個(gè)集合規(guī)定一個(gè)優(yōu)先級上限P’，使得這個(gè)集合中所有進(jìn)程的優(yōu)先級都小于P’。注意：P’并不一定是整個(gè)系統(tǒng)中的最高優(yōu)先級。*在創(chuàng)建保護(hù)該項(xiàng)資源的信號量或互斥量時(shí)，將P’作為一個(gè)參數(shù)。*每當(dāng)有進(jìn)程通過這個(gè)信號量或互斥量取得對共享資源的獨(dú)占使用權(quán)時(shí)，就將此進(jìn)程的優(yōu)先級暫時(shí)提高到P’，一直到釋放該項(xiàng)資源時(shí)才恢復(fù)其原有的優(yōu)先級。優(yōu)先級封頂是當(dāng)任務(wù)申請某資源時(shí)，把該任務(wù)的優(yōu)先級提升為可訪問這個(gè)資源的所有任務(wù)中的最高優(yōu)先級，這個(gè)優(yōu)先級稱為該資源的優(yōu)先級封頂。資源的優(yōu)先級封頂在資源被創(chuàng)建時(shí)就確定了。見P30圖1-10。第10頁/共20頁（3）優(yōu)先級繼承和優(yōu)先級封頂?shù)谋容^兩種算法都改變了任務(wù)的優(yōu)先級，但改變優(yōu)先級的時(shí)間和范圍有所不同。優(yōu)先級繼承只在占有資源的低優(yōu)先級任務(wù)阻塞了高優(yōu)先級的任務(wù)運(yùn)行時(shí)，才動(dòng)態(tài)更改低優(yōu)先級的任務(wù)到高優(yōu)先級。這種算法對應(yīng)用中任務(wù)的流程影響較小。優(yōu)先級封頂則不管任務(wù)是否阻塞了高優(yōu)先級的任務(wù)運(yùn)行，只要任務(wù)訪問該資源，都會(huì)提升任務(wù)的優(yōu)先級到可訪問這個(gè)資源的所有任務(wù)的最高優(yōu)先級。這兩種算法各有優(yōu)缺點(diǎn)，實(shí)際選擇時(shí)根據(jù)具體情況而定。第11頁/共20頁1.2同一優(yōu)先級的時(shí)間片輪轉(zhuǎn)調(diào)度算法對于復(fù)雜、高性能的多任務(wù)實(shí)時(shí)內(nèi)核（如VxWorks），由于多個(gè)任務(wù)允許共用一個(gè)優(yōu)先級，實(shí)時(shí)內(nèi)核提供了同一優(yōu)先級的時(shí)間片輪轉(zhuǎn)調(diào)度算法來調(diào)度同優(yōu)先級的多任務(wù)的運(yùn)行。實(shí)時(shí)內(nèi)核的調(diào)度器在就緒隊(duì)列中尋找最高優(yōu)先級的任務(wù)運(yùn)行時(shí)，如果系統(tǒng)中優(yōu)先級最高的任務(wù)有兩個(gè)或兩個(gè)以上，則調(diào)度器依照就緒的先后次序調(diào)度第一個(gè)任務(wù)。當(dāng)其執(zhí)行一段特定的時(shí)間片后，無論任務(wù)完成與否，處理器都會(huì)結(jié)束該任務(wù)的運(yùn)行，轉(zhuǎn)入下一個(gè)就緒的同優(yōu)先級任務(wù)。未運(yùn)行完的任務(wù)釋放處理器的控制權(quán)后，放到就緒隊(duì)列的末尾，等待下一個(gè)時(shí)間片來競爭處理器。當(dāng)然，沒有更高優(yōu)先級的任務(wù)就緒，就應(yīng)用基于優(yōu)先級的可搶占調(diào)度算法。實(shí)時(shí)內(nèi)核以輪轉(zhuǎn)策略保證具有同優(yōu)先級的任務(wù)相對平等地享有CPU的控制權(quán)。第12頁/共20頁在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小選擇會(huì)影響系統(tǒng)的性能和效率。時(shí)間片太小，任務(wù)頻繁進(jìn)行上下切換，實(shí)際運(yùn)行程序的時(shí)間很少，系統(tǒng)的效率很低;時(shí)間片太大，算法變成先進(jìn)先出算法，調(diào)度的公平性就沒有得到體現(xiàn)。時(shí)間片的選擇根據(jù)實(shí)時(shí)內(nèi)核的不同而有所差異。1.2單調(diào)速率調(diào)度算法單調(diào)速率調(diào)度算法主要用于分配任務(wù)的優(yōu)先級。它根據(jù)任務(wù)執(zhí)行的頻率確定優(yōu)先級的。任務(wù)的執(zhí)行頻率越高，其優(yōu)先級越高;反之，優(yōu)先級越低。第13頁/共20頁1.2任務(wù)間的通信在多任務(wù)的實(shí)時(shí)系統(tǒng)中，一項(xiàng)工作可能需要多個(gè)任務(wù)或多個(gè)任務(wù)與多個(gè)中斷處理程序（ISR）共同完成。它們之間必須協(xié)調(diào)動(dòng)作，互相配合，必要時(shí)還要交換信息。在實(shí)時(shí)操作系統(tǒng)中提供了任務(wù)間的通信與同步機(jī)制以解決這個(gè)問題。任務(wù)間的同步與通信一般要滿足任務(wù)與其他任務(wù)或中斷處理程序間進(jìn)行交換數(shù)據(jù);任務(wù)能以單向同步和雙向同步方式與另一個(gè)任務(wù)或中斷處理程序同步處理;任務(wù)必須能對共享資源進(jìn)行互斥訪問。1.2.1任務(wù)間的通信任務(wù)間的通信有兩種方式：共享數(shù)據(jù)結(jié)構(gòu)和消息機(jī)制。第14頁/共20頁1.2.1.1共享數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)任務(wù)間通信的最簡單方法是共享數(shù)據(jù)結(jié)構(gòu)。共享數(shù)據(jù)結(jié)構(gòu)的類型可以是全局變量、指針、緩沖區(qū)等。在使用共享數(shù)據(jù)結(jié)構(gòu)時(shí)，必須保證共享數(shù)據(jù)結(jié)構(gòu)使用的排它性;否則，會(huì)導(dǎo)致競爭和對數(shù)據(jù)時(shí)效的破壞。因此，在使用共享數(shù)據(jù)結(jié)構(gòu)時(shí)，必須實(shí)現(xiàn)存取的互斥的機(jī)制。實(shí)現(xiàn)互斥比較常用的方法有：開/關(guān)中斷、設(shè)置測試標(biāo)志位、禁止任務(wù)切換以及信號量機(jī)機(jī)制等。*開/關(guān)中斷實(shí)現(xiàn)互斥指在進(jìn)行共享數(shù)據(jù)結(jié)構(gòu)的訪問時(shí)先進(jìn)行關(guān)中斷操作，在訪問完成后再開中斷。*設(shè)置測試標(biāo)志位方法指在使用共享數(shù)據(jù)的兩個(gè)任務(wù)間約定時(shí)，每次使用共享數(shù)據(jù)前都要檢測某個(gè)事先約定的全局變量。如果變量為0，則可讀寫，若為1，則不能。第15頁/共20頁*禁止任務(wù)切換指在進(jìn)行共享數(shù)據(jù)的操作前，先禁止任務(wù)的切換，操作完成后再解除任務(wù)禁止切換。這種方式雖然實(shí)現(xiàn)了共享的互斥，但是實(shí)時(shí)系統(tǒng)的多任務(wù)切換在此時(shí)被禁止，有違多任務(wù)的初衷，應(yīng)盡量少使用。*信號量在多任務(wù)的實(shí)時(shí)內(nèi)核中的主要作用是用做共享數(shù)據(jù)結(jié)構(gòu)或共享資源的互斥機(jī)制，標(biāo)志某個(gè)事件的發(fā)生，以及同步兩個(gè)任務(wù)。信號量有兩種：二進(jìn)制信號量和計(jì)數(shù)信號量。1.2.1.2消息機(jī)制任務(wù)間的另一種通信方式是使用消息機(jī)制。任務(wù)可以通過系統(tǒng)服務(wù)向另一個(gè)任務(wù)發(fā)送消息。消息通常是一個(gè)指針變量，指針指向的內(nèi)容就是消息。消息機(jī)制包括消息郵箱和消息隊(duì)列。*消息郵箱通常是內(nèi)存空間的一個(gè)數(shù)據(jù)結(jié)構(gòu)。*消息隊(duì)列實(shí)際上是一個(gè)郵箱陣列，在消息隊(duì)列允許存放多個(gè)消息。對消息隊(duì)列的操作和對消息郵箱的操作的操作基本相同。第16頁/共20頁1.2.1任務(wù)間的同步任務(wù)同步中也常常使用信號量。與任務(wù)通信不同的是，信號量的使用不再作為一種互斥機(jī)制，而是代表某個(gè)特定的事件是否發(fā)生。任務(wù)的同步有單向同步和多向同步兩種。*單向同步：標(biāo)志事件是否發(fā)生的信號量初始化為0。一個(gè)任務(wù)在等待某個(gè)事件時(shí)，查看該事件的信號量是否為非0。另一個(gè)任務(wù)或中斷處理程序在進(jìn)行操作時(shí)，當(dāng)該事件發(fā)生后，將該信號量置為1。等待該事件的任務(wù)查詢到信號量的變換，代表事件已經(jīng)發(fā)生，任務(wù)繼續(xù)自身的運(yùn)行。*雙向同步：兩個(gè)任務(wù)之間可以通過兩個(gè)信號量進(jìn)行雙向同步。雙向同步有兩個(gè)初始化為0的信號量，每個(gè)信號量進(jìn)行一個(gè)方向的任務(wù)同步，兩個(gè)信號的同步方向是相反的。第17頁/共20頁1.3存儲(chǔ)器管理存儲(chǔ)器管理是提供對內(nèi)存資源的合理分配和存儲(chǔ)保護(hù)功能。由于其應(yīng)用環(huán)境的特殊性，實(shí)時(shí)內(nèi)核的存儲(chǔ)管理與一般操作系統(tǒng)的存儲(chǔ)管理存在著很大的差異。通常的操作系統(tǒng)，資源充足，實(shí)時(shí)要求不高，其內(nèi)核主要考慮提供更好的性能和安全機(jī)制。所以引入的是虛擬存儲(chǔ)器管理。嵌入式實(shí)時(shí)操作系統(tǒng)的存儲(chǔ)管理相對較為簡單。由于虛擬存儲(chǔ)器中經(jīng)常要對頁進(jìn)行換入換出操作，所以內(nèi)存中頁命中率和換入換出所耗費(fèi)的時(shí)間嚴(yán)重破壞了整個(gè)系統(tǒng)的確定性。這種存儲(chǔ)機(jī)制不能提供實(shí)時(shí)系統(tǒng)所要求的時(shí)間確定性，對于大多數(shù)嵌入式實(shí)時(shí)應(yīng)用來說，響應(yīng)和運(yùn)行時(shí)間的確定是至關(guān)重要的。對于實(shí)時(shí)應(yīng)用，一個(gè)失去時(shí)效的正確結(jié)果與錯(cuò)誤結(jié)果沒有什么本質(zhì)的不同，所以實(shí)時(shí)內(nèi)核一般不采用虛擬內(nèi)存管理。在大多數(shù)嵌入式實(shí)時(shí)操作系統(tǒng)中，內(nèi)核把內(nèi)存分成多個(gè)空間大小不等的分區(qū)，每個(gè)內(nèi)存分區(qū)又分為許多大小相同的塊。第18頁/共20頁1.4定時(shí)器和中斷管理實(shí)時(shí)內(nèi)核要求為用戶提供定時(shí)中斷以