《同步互斥與通信》PPT課件

嵌入式系統(tǒng)及應(yīng)用,第六章同步、互斥與通信,主要內(nèi)容,概述信號量郵箱和消息隊(duì)列管道,ISRx,Tasky,POST,PEND,任務(wù)與ISR之間的同步（單向）,Taskx,Tasky,POST,PEND,POST,PEND,任務(wù)與任務(wù)之間的同步（雙向）,任務(wù)與任務(wù)之間的同步（單向）,Taskx,Tasky,POST,PEND,在單處理器平臺上，嵌入式操作系統(tǒng)內(nèi)核提供的同步、互斥與通信機(jī)制主要包括：信號量（semaphore），用于互斥與同步事件（組）（eventgroup），用于同步異步信號（asynchronoussignal），用于同步郵箱（mailbox）、消息隊(duì)列（messagequeue），用于消息通信管道（pipe），提供非結(jié)構(gòu)化數(shù)據(jù)交換和實(shí)現(xiàn)同步,以下一些機(jī)制也可用于同步與通信（在單處理器或多處理器系統(tǒng)中）：全局變量共享內(nèi)存Sockets遠(yuǎn)程過程調(diào)用（RemoteProcedureCall）,第一節(jié)信號量,信號量的種類及用途信號量的定義互斥信號量二值信號量計(jì)數(shù)信號量信號量機(jī)制的主要數(shù)據(jù)結(jié)構(gòu)典型的信號量操作,什么是信號量,信號量被定義為一個(gè)整形變量，在其上定義了以下三個(gè)操作：1、可以被初始化一個(gè)非負(fù)數(shù)2、wait操作（P操作）將信號量的值減1后，若該值為負(fù)，則執(zhí)行wait操作的任務(wù)等待3、signal操作（V操作）將信號量的值增1后，若該值為非正，則執(zhí)行signal操作的任務(wù)喚醒,信號量用于實(shí)現(xiàn)任務(wù)與任務(wù)之間、任務(wù)與中斷處理程序之間的同步與互斥。信號量一般分為三種：,信號量的種類及用途,用于解決互斥問題。它比較特殊，可能會引起優(yōu)先級反轉(zhuǎn)問題。,用于解決同步問題,用于解決資源計(jì)數(shù)問題,將信號量進(jìn)行種類細(xì)分，可以根據(jù)其用途，在具體實(shí)現(xiàn)時(shí)做專門處理，提高執(zhí)行效率和可靠性。,互斥信號量,計(jì)數(shù)信號量,二值信號量,互斥信號量,WaitB(S):/申請信號量ifS.value1;/當(dāng)前沒有其他任務(wù)使用信號量thenS.value=S.value-1=0/將信號量值修改為0，獨(dú)占共享資源elsebeginInsert(CALLER,S.L);/如果當(dāng)前有其他任務(wù)使用信號量，將該任務(wù)放入等待隊(duì)列Block(CALLER);/修改該任務(wù)的狀態(tài)為等待態(tài)（阻塞任務(wù)）endSignalB(S):/釋放信號量ifS.Lqueueisempty;/如果等待序列為空，沒有其他任務(wù)等待使用該共享資源thenS.value=1;/釋放信號量elsebeginRemove(S.L,id);/如果有其他任務(wù)等待使用該共享資源，則從等待隊(duì)列中將該任務(wù)移除wakeup(id);/將該任務(wù)的狀態(tài)改為就緒態(tài)(喚醒任務(wù))end,用信號量實(shí)現(xiàn)任務(wù)間的互斥,varmutex:SharedSemaphore;beginmutex:=1;parbeginP1:P2:Pi:repeatWait(mutex);“進(jìn)程Pi的臨界代碼段”；Signal(mutex);foreverPn:parendend,互斥信號量狀態(tài)圖,互斥信號量狀態(tài)圖,各種互斥機(jī)制比較,二值信號量,可獲得,不可獲得,申請并獲得(值為0),釋放(值為1),初始化值為0,二值信號量狀態(tài)圖,Task1()執(zhí)行一些操作;將信號量sem1置1;申請信號量sem2;,Task2()申請信號量sem1;執(zhí)行一些操作;將信號量sem2置1;,Task2申請信號量sem1失敗，系統(tǒng)切換到Task1,sem1被置1后，Task2得到sem1并搶占Task1,Task2運(yùn)行到某處時(shí)因某種原因被阻塞，系統(tǒng)切換到Task1,用二值信號量實(shí)現(xiàn)兩個(gè)任務(wù)之間的雙向同步Task2優(yōu)先級高于Task1sem1和sem2的初始值均為0,二值信號量實(shí)現(xiàn)同步,計(jì)數(shù)信號量,計(jì)數(shù)信號量,計(jì)數(shù)信號量狀態(tài)圖,可獲得,不可獲得,初始化值大于0,申請并獲得值為0,釋放值為1,申請并獲得值減1,釋放值加1,計(jì)數(shù)(一般)信號量同步原語,Wait(S):S.value:=S.value-1;/有新任務(wù)來使用共享資源將信號量的值減1ifS.value0/如果信號量的值為負(fù)，表示共享資源已經(jīng)分配完畢thenbeginInsert(CALLER,S.L);/將該任務(wù)插入等待序列Block(CALLER);/將該任務(wù)狀態(tài)改為等待態(tài)(阻塞任務(wù))endSignal(S):S.value:=S.value+1;/任務(wù)使用完共享資源，將信號量的值加1，釋放一個(gè)信號量ifS.value=0/如果信號量為負(fù)，表示仍有等待該資源的任務(wù)被阻塞thenbeginRemove(S.L,id);/將等待隊(duì)列中的一個(gè)任務(wù)從隊(duì)列中移除wakeup(id);/將該任務(wù)的狀態(tài)修改為就緒態(tài)，喚醒任務(wù)endS的絕對值表示在該信號量列表中已阻塞的任務(wù)數(shù)目,計(jì)數(shù)信號量,計(jì)數(shù)信號量使用實(shí)例：有界緩沖問題,計(jì)數(shù)信號量,VarE,F:Semaphore;mutex:binarySemaphore;begin(*mainprogram*)F:=0;E:=n;mutex=1;parbeginproducer1;producern;consumer1;consumerm；parendend,生產(chǎn)者任務(wù)beginrepeat生產(chǎn)數(shù)據(jù)/生產(chǎn)者生產(chǎn)數(shù)據(jù)Wait(E);/減少一個(gè)空緩沖區(qū)項(xiàng)Wait(mutex);/分配空緩沖區(qū)和移動(dòng)指針P操作是互斥的“分配空緩沖區(qū)并調(diào)整指針P的臨界段”；“向空緩沖區(qū)中裝入數(shù)據(jù)”Signal(mutex);/釋放互斥信號量Signal(F);/增加一個(gè)滿緩沖區(qū)項(xiàng)foreverend,消費(fèi)者任務(wù)beginrepeat消費(fèi)數(shù)據(jù)/消費(fèi)者取走數(shù)據(jù)Wait(F);/減少一個(gè)滿緩沖區(qū)項(xiàng)Wait(mutex);/分配滿緩沖區(qū)和移動(dòng)指針C操作是互斥的“分配滿緩沖區(qū)并調(diào)整指針C的臨界段”；“從滿緩沖區(qū)中取走數(shù)據(jù)”Signal(mutex);/釋放互斥信號量Signal(F);/增加一個(gè)空緩沖區(qū)項(xiàng)foreverend,計(jì)數(shù)信號量,信號量機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),信號量機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),信號量控制塊：管理所有創(chuàng)建的信號量，內(nèi)核在系統(tǒng)運(yùn)行時(shí)動(dòng)態(tài)分配和回收信號量控制塊互斥和二值信號量控制塊結(jié)構(gòu):Binary_Semaphore_Control_Block,wait_queue任務(wù)等待隊(duì)列attributes信號量屬性lock_nesting_behavior試圖嵌套獲得時(shí)的規(guī)則wait_discipline任務(wù)等待信號量的方式priority_ceiling優(yōu)先級天花板值lock是否被占有holder擁有者nest_count嵌套層數(shù),計(jì)數(shù)信號量控制結(jié)構(gòu)Counting_Semaphore_Control_Blockwait_queue任務(wù)等待隊(duì)列attributes計(jì)數(shù)信號量屬性maximum_count最大計(jì)數(shù)值wait_discipline任務(wù)等待信號量的方式count當(dāng)前計(jì)數(shù)值,信號量機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),典型的信號量操作,創(chuàng)建信號量獲?。ㄉ暾垼┬盘柫酷尫判盘柫縿h除信號量清除信號量的任務(wù)等待列表獲取有關(guān)信號量的各種信息,創(chuàng)建信號量,功能：根據(jù)應(yīng)用傳遞的參數(shù)創(chuàng)建一個(gè)信號量參數(shù)：信號量的名字、屬性和初始值等。內(nèi)核動(dòng)作：從空閑信號量控制塊鏈中分配一個(gè)信號量控制塊，并初始化信號量屬性。創(chuàng)建成功時(shí)，為其分配唯一的ID號返回給應(yīng)用。如果已創(chuàng)建信號量數(shù)量已達(dá)到用戶配置的最大數(shù)量，就返回錯(cuò)誤。,信號量的屬性,信號量的屬性,信號量的類型,互斥信號量（MUTEX_SEMAPHORE）,計(jì)數(shù)信號量（COUNTING_SEMAPHORE）,二值信號量（BINARY_SEMAPHORE）,任務(wù)等待信號量的方式,先進(jìn)先出（FIFO）順序,優(yōu)先級（PRIORITY）順序,優(yōu)先級反轉(zhuǎn)問題的解決方法（只適用于互斥信號量）,優(yōu)先級繼承算法（INHERIT_PRIORITY）,優(yōu)先級天花板算法(PRIORITY_CEILING)，需給出所有可能獲得此信號量的任務(wù)中優(yōu)先級最高的任務(wù)的優(yōu)先級。,獲?。ㄉ暾垼┬盘柫?功能：試圖獲得應(yīng)用指定的信號量。該功能流程如下：if信號量的值大于0then將信號量的值減1else根據(jù)接收信號量的選項(xiàng)，將任務(wù)放到等待隊(duì)列中，或是直接返回,獲?。ㄉ暾垼┬盘柫?當(dāng)所申請的信號量不能被立即獲得時(shí)，可以有以下幾種選擇：永遠(yuǎn)等待不等待，立即返回，并返回一個(gè)錯(cuò)誤狀態(tài)碼指定等待時(shí)限（可有效避免死鎖）注意：不允許在ISR中選擇等待當(dāng)任務(wù)選擇等待時(shí)，將被按FIFO或優(yōu)先級順序放置在等待隊(duì)列中,釋放信號量,功能：釋放一個(gè)應(yīng)用指定的信號量。if沒有任務(wù)等待這個(gè)信號量then信號量的值加1else將信號量分配給一個(gè)等待任務(wù)（將相應(yīng)的任務(wù)移出等待隊(duì)列，使其就緒）如果使用了優(yōu)先級繼承或優(yōu)先級天花板算法，那么執(zhí)行該功能（系統(tǒng)調(diào)用）的任務(wù)的優(yōu)先級將恢復(fù)到原來的高度。,刪除信號量,功能：從系統(tǒng)中刪除應(yīng)用指定的一個(gè)信號量內(nèi)核動(dòng)作：將信號量控制塊返還給系統(tǒng)刪除信號量的不一定是創(chuàng)建信號量的任務(wù)如果有任務(wù)正在等待獲得該信號量，執(zhí)行此功能將使所有等待這個(gè)信號量的任務(wù)回到就緒隊(duì)列中，且返回一個(gè)狀態(tài)碼指示該信號量已被刪除,清除信號量的任務(wù)等待列表,為了清除等待一個(gè)信號量的所有任務(wù)，某些內(nèi)核支持Flush操作，以便釋放信號量等待任務(wù)列表中的所有任務(wù)。當(dāng)多個(gè)任務(wù)的執(zhí)行必須在某些點(diǎn)相遇時(shí)，需要這樣的機(jī)制。,第二節(jié)郵箱和消息隊(duì)列,通信方式概述消息隊(duì)列機(jī)制的主要數(shù)據(jù)結(jié)構(gòu)典型的消息隊(duì)列操作,任務(wù)間的通信方式,任務(wù)間的通信方式:直接通信間接通信消息：內(nèi)存空間中一段長度可變的緩沖區(qū)，其長度和內(nèi)容均可以由用戶定義，其內(nèi)容可以是實(shí)際的數(shù)據(jù)、數(shù)據(jù)塊的指針或空。消息進(jìn)一步分為：郵箱和消息隊(duì)列,消息隊(duì)列機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),消息隊(duì)列及其相關(guān)的參數(shù)和支持?jǐn)?shù)據(jù)結(jié)構(gòu),發(fā)送和接收消息的消息拷貝和內(nèi)存使用這種消息傳遞方法效率低、占用空間大一種效率更高的方式是傳遞消息指針,消息的發(fā)送或接收的兩種方法,number_of_message,max_message_count,消息隊(duì)列控制塊,消息隊(duì)列緩沖區(qū),消息隊(duì)列機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),消息隊(duì)列的環(huán)形緩沖,消息隊(duì)列機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),max_message_count,queue_end,queue_start,queue_out,number_of_message,queue_in,消息指針,消息隊(duì)列狀態(tài)圖,非空,滿,隊(duì)列創(chuàng)建消息數(shù)為0,消息隊(duì)列狀態(tài)圖,消息發(fā)送消息數(shù)加1,空,消息發(fā)送消息數(shù)為1,消息接收消息數(shù)為0,消息接收消息數(shù)減1,消息接收消息數(shù)減1,消息發(fā)送消息數(shù)等于隊(duì)列長度,典型的消息隊(duì)列操作,創(chuàng)建消息隊(duì)列發(fā)送普通消息發(fā)送緊急消息發(fā)送廣播消息接收消息刪除消息隊(duì)列獲取有關(guān)消息隊(duì)列的各種信息,創(chuàng)建消息隊(duì)列,創(chuàng)建消息隊(duì)列時(shí)，調(diào)用者可以指定如下參數(shù)：消息的最大長度每個(gè)消息隊(duì)列中最多的消息數(shù)消息隊(duì)列的屬性任務(wù)等待消息時(shí)的排隊(duì)方式：FIFO或PRIORITY系統(tǒng)為新創(chuàng)建的消息隊(duì)列分配唯一的ID,發(fā)送消息,接收消息,刪除消息隊(duì)列,從系統(tǒng)中刪除指定的消息隊(duì)列，釋放消息隊(duì)列控制塊及消息隊(duì)列緩沖區(qū)。任何知道此消息隊(duì)列ID號的代碼都可以刪除它。消息隊(duì)列被刪除后，所有等待從這個(gè)消息隊(duì)列接收消息的任務(wù)得到一個(gè)錯(cuò)誤信息表明消息隊(duì)列已被刪除都回到并回到就緒態(tài)。,消息隊(duì)列的其他典型使用,緊耦合的單向數(shù)據(jù)通信：發(fā)送任務(wù)發(fā)送消息后要求一個(gè)響應(yīng)信號，表明接收任務(wù)已經(jīng)成功接收到消息。,消息隊(duì)列的其他典型使用,緊耦合的雙向數(shù)據(jù)通信：如果數(shù)據(jù)需要在任務(wù)之間雙向流動(dòng)，則可以采用緊耦合的雙向數(shù)據(jù)通信模式（也稱為全雙工通信）。,第三節(jié)管道,概述管道機(jī)制的主要數(shù)據(jù)結(jié)構(gòu)典型的管道操作管道機(jī)制的典型應(yīng)用,管道機(jī)制概述,管道（pipe）是提供非結(jié)構(gòu)化數(shù)據(jù)交換和實(shí)現(xiàn)任務(wù)間同步的內(nèi)核對象。在傳統(tǒng)的實(shí)現(xiàn)中，管道是單向數(shù)據(jù)交換設(shè)施。,Task1,Task2,管道,管道中的數(shù)據(jù),寫描述符,讀描述符,向管道寫數(shù)據(jù),從管道讀數(shù)據(jù),數(shù)據(jù)在管道內(nèi)像一個(gè)非結(jié)構(gòu)字節(jié)流，按FIFO的次序從管道中讀出。當(dāng)管道空時(shí)，阻塞讀者，當(dāng)管道滿時(shí)，阻塞寫者。,管道機(jī)制概述,管道允許有多個(gè)讀者和寫者。,管道,管道的狀態(tài)轉(zhuǎn)換圖,非空,滿,創(chuàng)建管道無寫入數(shù)據(jù),讀數(shù)據(jù)，有剩余數(shù)據(jù),空,寫數(shù)據(jù),讀數(shù)據(jù)，無數(shù)據(jù)留下,寫數(shù)據(jù)，有剩余空間,讀數(shù)據(jù),寫數(shù)據(jù)，無剩余空間,管道機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),典型的管道操作,選擇（Select）操作Select操作允許一個(gè)任務(wù)阻塞并等待一個(gè)或多個(gè)管道上的一個(gè)指定條件的發(fā)生。,Task1,ISR,Task2,Task3,任務(wù)Task3等待從Pipe1和Pipe2這兩個(gè)管道讀數(shù)據(jù)并寫到第三個(gè)管道Pipe3上。在這種情況下，當(dāng)頭兩個(gè)管道中的任意一個(gè)有數(shù)據(jù)時(shí)，Select調(diào)用返回。,管道機(jī)制的典型應(yīng)用,TaskA,TaskB,Select操作,Select操作,管道C,管道D,任務(wù)A和任務(wù)B打開兩個(gè)管道作為任務(wù)間的通信方式：打開管道C作為從任務(wù)A到任務(wù)B的數(shù)據(jù)傳輸，打開管道D作為從任務(wù)B到任務(wù)A的回應(yīng)。任務(wù)A等待管道C編程可寫，也等待管道D上來自任務(wù)B的回應(yīng)。,兩個(gè)任務(wù)之間的同步,管道主要用于任務(wù)到任務(wù)或ISR到任務(wù)的數(shù)據(jù)傳輸,第四節(jié)事件,概述事件機(jī)制的主要數(shù)據(jù)結(jié)構(gòu)典型的事件操作事件機(jī)制的典型應(yīng)用,在嵌入式實(shí)時(shí)內(nèi)核中，事件是指一種表明預(yù)先定義的系統(tǒng)事件已經(jīng)發(fā)生的機(jī)制。事件機(jī)制用于任務(wù)與任務(wù)之間、任務(wù)與ISR之間的同步。其主要的特點(diǎn)是可實(shí)現(xiàn)一對多的同步。一個(gè)事件就是一個(gè)標(biāo)志，不具備其它信息。一個(gè)或多個(gè)事件構(gòu)成一個(gè)事件集。事件集可以用一個(gè)指定長度的變量（比如一個(gè)8bit,16bit或32bit的無符號整型變量，不同的操作系統(tǒng)其具體實(shí)現(xiàn)不一樣）來表示，而每個(gè)事件由在事件集變量中的某一位來代表。,概述,事件及事件集有以下特點(diǎn)：事件間相互獨(dú)立事件僅用于同步，不提供數(shù)據(jù)傳輸功能事件無隊(duì)列，即多次發(fā)送同一事件，在未經(jīng)過任何處理的情況下，其效果等同于只發(fā)送一次。提供事件機(jī)制的意義在于：當(dāng)某任務(wù)要與多個(gè)任務(wù)或中斷服務(wù)同步時(shí)，就需要使用事件機(jī)制。若任務(wù)需要與一組事件中的任意一個(gè)發(fā)生同步，可稱為獨(dú)立型同步（邏輯“或”關(guān)系）。任務(wù)也可以等待若干事件都發(fā)生時(shí)才同步，稱為關(guān)聯(lián)型同步（邏輯“與”關(guān)系）。,概述,“或”同步和“與”同步,概述,任務(wù),任務(wù),任務(wù),任務(wù),ISR,ISR,OR,AND,“與”型同步,“或”型同步,事件集,事件集,POST,POST,PEND,PEND,用多個(gè)事件的組合發(fā)信號給多個(gè)任務(wù),概述,任務(wù),任務(wù),任務(wù),ISR,OR,AND,事件集,事件集,事件集（8，16或32位）,POST,PEND,PEND,術(shù)語：發(fā)送事件集。指在一次發(fā)送過程中發(fā)往接收者（比如任務(wù)）的一個(gè)或多個(gè)事件的組合。待處理事件集。指已被發(fā)送到一個(gè)接收者但還沒有被接收（即正在等待處理）的所有事件的集合。事件條件。指事件接收者在一次接收過程中期待接收的一個(gè)或多個(gè)事件的集合?！盎颉蓖剑捍幚硎录灰ㄊ录l件中的任一事件即可滿足要求；“與”同步：其二是待處理事件集必須包括事件條件中的全部事件方可滿足要求。,概述,事件機(jī)制的主要數(shù)據(jù)結(jié)構(gòu),（1）事件集控制塊結(jié)構(gòu)（Event_set_Control_Block）：attribute事件集的屬性（排隊(duì)方式:FIFO或PRIORITY）event_set當(dāng)前事件集（指示被置位且未被接受的事件標(biāo)志位）eventset_condition_queue_and事件集”與”等待隊(duì)列eventset_condition_queue_or事件集”或”等待隊(duì)列內(nèi)核為每個(gè)等待事件集的任務(wù)生成一個(gè)“任務(wù)事件集等待控制塊”（2）任務(wù)事件集等待控制塊結(jié)構(gòu)（Event_set_Task_Waited_Buddy）task等待任務(wù)的控制塊指針event_set任務(wù)當(dāng)前等待的事件集flag_node_array任務(wù)等待標(biāo)志節(jié)點(diǎn)數(shù)組任務(wù)等待標(biāo)志節(jié)點(diǎn)數(shù)組的長度等于事件集的位數(shù)，其中每個(gè)節(jié)點(diǎn)元素對應(yīng)一個(gè)等待的事件標(biāo)志,典型的事件操作,創(chuàng)建事件集刪除事件集發(fā)送事件（集）接收事件（集）獲取有關(guān)事件集的各