嵌入式系統(tǒng)進程管理.ppt

1、進 程 管 理,1 進程的基本概念 2 進 程 控 制 3 進程互斥和同步 4 進 程 通 信 5 進 程 調(diào) 度 6 死 鎖 7 線 程 8 Linux中的進程管理,5.1 進程的基本概念,5.1.1 程序的順序執(zhí)行和并發(fā)執(zhí)行 1程序的順序執(zhí)行 所謂程序的順序執(zhí)行是指該程序獨占整個系統(tǒng)中的所有資源，處理機嚴格按照程序所規(guī)定的順序進行操作，只有在前一個操作執(zhí)行完后，才進行后繼操作。,程序的順序執(zhí)行有以下特征。 （1）順序性。 （2）封閉性。 （3）可再現(xiàn)性。,2多道程序設(shè)計的引入 執(zhí)行環(huán)境具有下述3個特點。 （1）獨立性。 （2）隨機性。 （3）資源共享。,3程序的并發(fā)執(zhí)行 程序的并發(fā)執(zhí)行可總

2、結(jié)為：一組在邏輯上互相獨立的程序或程序段在執(zhí)行過程中其執(zhí)行時間在客觀上互相重疊，即一個程序段的執(zhí)行尚未結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始的執(zhí)行方式。,程序并發(fā)執(zhí)行時具有如下特征。 （1）間斷性。 （2）失去封閉性。 （3）不可再現(xiàn)性。,5.1.2 進程的定義和特征 1進程的定義 進程是一個具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。,2進程的特征 （1）結(jié)構(gòu)特征 （2）動態(tài)性 （3）并發(fā)性 （4）獨立性 （5）異步性,5.1.3 進程的狀態(tài)及其轉(zhuǎn)換 1進程的基本狀態(tài) （1）就緒狀態(tài) 當(dāng)進程已分配到除處理機以外的所有必要的資源后，只要再獲得處理機便可立即執(zhí)行，這時進程的狀態(tài)稱為就緒狀態(tài)。

3、,（2）執(zhí)行狀態(tài) 執(zhí)行狀態(tài)是指進程已獲得處理機、其程序正在執(zhí)行的狀態(tài)。 （3）阻塞狀態(tài) 正在執(zhí)行的進程因發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，這種暫停狀態(tài)被稱為阻塞狀態(tài)。,2進程的狀態(tài)轉(zhuǎn)換,進程的3種基本狀態(tài)及其轉(zhuǎn)換,5.1.4 進程的結(jié)構(gòu) 1進程的實體 （1）進程控制塊（PCB） （2）程序段 （3）數(shù)據(jù)段,2進程控制塊 進程控制塊是進程實體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。PCB中記錄了操作系統(tǒng)所需的，用于描述進程進展情況及控制進程運行所需的全部信息。 PCB是進程存在的惟一標(biāo)志。 一般把PCB存放在操作系統(tǒng)專門開辟的PCB區(qū)內(nèi)。,在進程控制塊中，主要包括

4、下述4方面的信息。 （1）進程描述信息 進程標(biāo)識符。每個進程都有惟一的進程標(biāo)識符，用以識別不同的進程。 用戶名或用戶標(biāo)識號。每個進程都隸屬于某個用戶，有利于資源共享與保護。 家族關(guān)系。標(biāo)識進程之間的家族關(guān)系。,（2）處理機狀態(tài)信息 通用寄存器、指令計數(shù)器、程序狀態(tài)字（PSW）、用戶棧指針等 （3）進程調(diào)度信息 進程狀態(tài)。指明進程的當(dāng)前狀態(tài)，以作為進程調(diào)度和進程對換時的依據(jù)。,進程優(yōu)先級。用于描述進程使用處理機的優(yōu)先級別的一個整數(shù)，優(yōu)先級別高的進程先獲得處理機。 進程調(diào)度所需的其他信息。如進程已等待CPU的時間總和、進程已執(zhí)行的時間總 和等。 事件。指進程被阻塞的原因。,（4）進程控制信息 程

5、序和數(shù)據(jù)的地址。指出該進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地址，以便再調(diào)度到該進程執(zhí)行時，能從中找到其程序和數(shù)據(jù)。 進程同步和通信機制。指實現(xiàn)進程同步和進程通信時所必須的機制，如消息隊列指針、信號量等。這些數(shù)據(jù)應(yīng)全部或部分地存放在PCB中。, 資源清單。它是一張列出了除CPU之外的進程所需的全部資源和已經(jīng)分配給該進程的資源清單。 鏈接指針。它給出了本進程（PCB）所在隊列的下一個進程的PCB首地址。 在一個系統(tǒng)中，通常擁有數(shù)十個、數(shù)百個乃至數(shù)千個PCB。為了對PCB進行有效地管理，系統(tǒng)應(yīng)把所有的PCB用適當(dāng)?shù)姆绞浇M織起來。目前常用的PCB組織方式有鏈接方式和索引方式兩種。, 鏈接方式,PCB鏈接隊

6、列示意圖, 索引方式,PCB索引方式示意圖,5.2 進 程 控 制,5.2.1 操作系統(tǒng)內(nèi)核 為了防止操作系統(tǒng)及關(guān)鍵數(shù)據(jù)（如PCB等）受到用戶程序有意無意的破壞，通常將處理機的執(zhí)行狀態(tài)分成系統(tǒng)態(tài)和用戶態(tài)兩種。,（1）系統(tǒng)態(tài)。它具有較高特權(quán)，能執(zhí)行一切指令，訪問所有寄存器和存儲區(qū)。 （2）用戶態(tài)。這是具有較低特權(quán)的執(zhí)行狀態(tài)，只能執(zhí)行規(guī)定的指令，訪問指定的寄存器和存儲區(qū)。,（3）操作系統(tǒng)內(nèi)核： 在進行層次設(shè)計時，通常將一些與硬件緊密相關(guān)的模塊，諸如中斷處理程序、常用的設(shè)備驅(qū)動程序以及運行頻率較高的模塊（如時鐘管理、進程調(diào)度和公共基本操作模塊）都安排在緊靠硬件的軟件層次中，并使之常駐內(nèi)存，以提高操作

7、系統(tǒng)的運行效率，通常把這一部分稱為操作系統(tǒng)的內(nèi)核（Kernel）。,5.2.2 進程控制的概念 進程控制是進程和處理機管理的一個重要任務(wù)。所謂進程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進程以及完成進程在各種狀態(tài)之間的轉(zhuǎn)換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)資源共享的目的。,5.2.3 進程的創(chuàng)建與撤消 1進程的創(chuàng)建 2進程的撤消,5.2.4 進程的阻塞與喚醒 1進程的阻塞 2進程的喚醒,5.3 進程互斥和同步,5.3.1 進程互斥 1互斥的概念 所謂進程互斥是指當(dāng)有若干進程都要使用某一共享資源時，任何時刻最多允許一個進程使用，其他要使用該資源的進程必須等待，直到占用該資源者釋放

8、了該資源為止。,2臨界資源 操作系統(tǒng)中將一次只允許一個進程訪問的資源稱為臨界資源。,3臨界區(qū)（Critical Section） 把進程中訪問臨界資源的那段程序代碼段稱為臨界區(qū)。為實現(xiàn)對臨界資源的互斥訪問，應(yīng)保證諸進程互斥地進入各自的臨界區(qū)。必須在臨界區(qū)前面增加一段用于進行上述檢查的代碼，我們把這段代碼段稱為進入?yún)^(qū)（Entry Section）；相應(yīng)地，在臨界區(qū)后面也要加上一段稱為退出區(qū)（Exit Section）的代碼，用于將臨界區(qū)正被訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志。,一個含有訪問某一臨界資源的循環(huán)進程可描述如下： while(TRUE) entry section critical sec

9、tion exit section remainder section ,4同步機制應(yīng)遵循的準(zhǔn)則 （1）空閑讓進。 （2）忙則等待。 （3）讓權(quán)等待。 （4）有限等待。,5.3.2 進程同步 1同步的概念 把異步環(huán)境下的一組并發(fā)進程因直接制約，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。具有同步關(guān)系的一組并發(fā)進程稱為合作進程，合作進程間互相發(fā)送的信號稱為消息或事件。,2同步與互斥的關(guān)系 進程的同步與進程的互斥都涉及到并發(fā)進程共享資源的問題，進程的互斥實際上是進程同步的一種特殊情況。 有時也把進程的互斥與進程的同步統(tǒng)稱為進程的同步。,5.3.3 信號量機制 1記錄型信號量 struct s

10、emaphore int value； PCB *L； S；,2P、V原語操作 除了給信號量S初始化外，信號量的數(shù)值域僅能由P、V原語操作改變（P和V分別是荷蘭語Passeren和Verhoog的第一個字母，相當(dāng)于英文的Pass和Increment的意思）。,P原語操作的主要動作是： （1）S.value減1； （2）若S.value減1后仍大于或等于零，則進程繼續(xù)執(zhí)行； （3）若S.value減1后小于零，則該進程被阻塞，進入與該信號量相對應(yīng)的等待隊列L中，然后轉(zhuǎn)進程調(diào)度。 P原語操作的功能框圖如圖7.8。,P原語操作功能,V原語操作的主要動作是： （1）S.value加1； （2）若S.v

11、alue加1后結(jié)果大于零，進程繼續(xù)執(zhí)行； （3）若S.value加1后結(jié)果小于或等于零，則從該信號量的等待隊列L中喚醒一個等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉(zhuǎn)進程調(diào)度。 V原語操作的功能框圖如圖7.9。,圖 V原語操作功能,5.3.4 進程互斥和同步的實現(xiàn) 1進程互斥的實現(xiàn) 2進程同步的實現(xiàn),5.4 進 程 通 信,通信（Communication）意味著在進程間傳送數(shù)據(jù)。 也把進程間控制信息的交換稱為低級通信，而把進程間大批量數(shù)據(jù)的交換稱為高級通信。,5.4.1 進程通信的類型 1共享存儲器系統(tǒng) 共享存儲器系統(tǒng)為了傳送大量數(shù)據(jù)，在存儲器中劃出一塊共享存儲區(qū)，諸進程可通過對共享存儲區(qū)進行讀數(shù)

12、據(jù)或?qū)憯?shù)據(jù)以實現(xiàn)通信。,2消息傳遞系統(tǒng) 分為以下兩種。 （1）直接通信方式 發(fā)送進程可將消息直接發(fā)送給接收進程，即將消息掛在接收進程的消息緩沖隊列上，而接收進程可從自己的消息緩沖隊列中取得消息。 （2）間接通信方式 發(fā)送進程將消息發(fā)送到指定的信箱中，而接收進程從信箱中取得消息。,3管道通信系統(tǒng) 在UNIX操作系統(tǒng)中，開創(chuàng)了一種借助文件和文件系統(tǒng)形成的一種通信方式。所謂管道是指用于連接一個讀進程和一個寫進程，以實現(xiàn)它們之間通信的共享文件，又稱pipe文件。向管道提供輸入的發(fā)送進程，以字符流方式將大量的數(shù)據(jù)送入管道，而接收進程從管道中接收數(shù)據(jù)。由于發(fā)送進程和接收進程是利用管道進行通信的，故稱為管道

13、通信。,5.4.2 消息緩沖隊列通信機制 1消息緩沖隊列通信機制簡介 由于消息緩沖機制中所使用的緩沖區(qū)為公用緩沖區(qū)，因此使用消息緩沖機制傳送數(shù)據(jù)時，兩通信進程必須滿足如下條件。,第一，在發(fā)送進程把寫入消息的緩沖區(qū)掛入消息隊列時，應(yīng)禁止其他進程對該消息隊列的訪問，否則，將引起消息隊列的混亂。同理，當(dāng)接收進程正從消息隊列中取消息時，也應(yīng)禁止其他進程對該隊列的訪問。 第二，當(dāng)緩沖區(qū)中無消息存在時，接收進程不能接收到任何消息；而發(fā)送進程是否可以發(fā)送消息，則只由發(fā)送進程是否能夠申請到緩沖區(qū)決定。,2消息緩沖隊列通信機制中的數(shù)據(jù)結(jié)構(gòu) （1）消息緩沖區(qū) typedefstruct message buffe

14、r sender；/發(fā)送者進程標(biāo)識符 size；/消息長度 text；/消息正文 next；/指向下一個消息緩沖區(qū)的指針 ,（2）PCB中有關(guān)進程通信的數(shù)據(jù)項 typedefstruct message block mq；/消息隊列隊首指針 mutex；/消息隊列互斥信號量，初值為1 sm；/消息隊列資源信號量，用于消息隊列中的消息計數(shù)，初值為0 ,5.5 進 程 調(diào) 度,5.5.1 進程調(diào)度的概念 1高級、中級和低級調(diào)度 （1）高級調(diào)度 高級調(diào)度通常也稱作業(yè)調(diào)度，用于決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，準(zhǔn)備執(zhí)行。,（2）中級調(diào)度 中級調(diào)度大多針對于分時系統(tǒng)，是按一定的算法在內(nèi)存和外

15、存之間進行進程對換，目的在于緩和內(nèi)存的緊張。 （3）低級調(diào)度 低級調(diào)度用于將內(nèi)存中就緒隊列中的作業(yè)分配處理機，使其執(zhí)行。,2進程調(diào)度的方式 進程調(diào)度通常有以下兩種方式。 （1）非剝奪方式 （2）剝奪方式 3進程調(diào)度的功能 4進程調(diào)度算法的性能評價,5.5.2 進程調(diào)度算法 1先來先服務(wù)調(diào)度算法 在進程調(diào)度中，采用FCFS算法時，進程調(diào)度程序從就緒進程隊列中，選擇一個最先進入隊列的進程，把處理機分配給它，讓它進入執(zhí)行狀態(tài)。 公平性，并且實現(xiàn)也比較容易，這是它的優(yōu)點。但是，它的缺點是實際上不公平，它比較有利于長進程，而不利于短進程。,2短進程優(yōu)先調(diào)度算法 短進程優(yōu)先（SPF）調(diào)度算法，是指對執(zhí)行時

16、間短的進程優(yōu)先調(diào)度的算法。SPF是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或因等待某事件發(fā)生而放棄處理機時，再重新調(diào)度。,采用SPF算法，平均周轉(zhuǎn)時間比FCFS調(diào)度算法有很多改善，這是它的優(yōu)點。SPF調(diào)度算法的缺點是如下所述。 第一，對長進程非常不利。 第二，緊迫進程不能及時處理。 第三，執(zhí)行時間的估計值不準(zhǔn)確。,3高優(yōu)先級優(yōu)先調(diào)度算法 考慮到系統(tǒng)中的緊迫進程能得到優(yōu)先處理，引入了高優(yōu)先級優(yōu)先（HPF）調(diào)度算法，處理機總是分配給就緒進程隊列中優(yōu)先級最高的進程。 進程的優(yōu)先級可采用靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級兩種，優(yōu)先級可由用戶自定或由系統(tǒng)確定。,4

17、時間片輪轉(zhuǎn)法 時間片輪轉(zhuǎn)法的基本思想是將CPU的處理時間分成固定大小的時間片。如果一個進程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時間片，但未完成要求的任務(wù)，則它自行釋放自己所占有的CPU，而排到就緒隊列的末尾，等待下一次調(diào)度。同時，進程調(diào)度程序又去調(diào)度當(dāng)前就緒隊列中的第一個進程。,5多級反饋隊列調(diào)度算法 其基本思想如下所述。 （1）系統(tǒng)按優(yōu)先級設(shè)置N個就緒進程隊列，第一級隊列的優(yōu)先級最高，其余隊列的優(yōu)先級逐個降低，第N級隊列的優(yōu)先級最低。,5.6 死 鎖,在多道程序系統(tǒng)中，多個進程并發(fā)執(zhí)行，共享系統(tǒng)資源，從而提高了資源利用率和系統(tǒng)吞吐量，但可能發(fā)生一種危險死鎖。所謂死鎖，是指多個進程因競爭資源而形成

18、一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。,5.6.1 產(chǎn)生死鎖的原因和必要條件 1產(chǎn)生死鎖的原因 產(chǎn)生死鎖的主要原因可歸結(jié)為以下兩點。 （1）競爭資源 （2）進程推進順序不當(dāng),2產(chǎn)生死鎖的必要條件 （1）互斥條件 一個資源在一段時間內(nèi)只能被一個進程所使用，具有排它性。 （2）請求和保持條件 一個進程在請求新資源而阻塞時，對已獲得資源又保持不放。,（3）不剝奪條件 進程已獲得的資源，在未使用完之前不能被剝奪，只能在使用完時由自己釋放。 （4）環(huán)路等待條件 在發(fā)生死鎖時，必然存在一個進程資源的環(huán)形鏈。即進程集合P1，P2，Pn中的P1正在等待P2占用的資源，P2正在等待P3占用的資

19、源，Pn正在等待P1占用的資源。,只要同時具備上述4個必要條件，系統(tǒng)就會發(fā)生死鎖，只要上述條件之一不滿足，系統(tǒng)就不會發(fā)生死鎖。,3處理死鎖的方法 由于死鎖狀態(tài)的出現(xiàn)會給整個系統(tǒng)帶來嚴重的后果，所以如何解決死鎖問題引起了人們的普遍關(guān)注。目前常用的方法有以下3種。,（1）預(yù)防死鎖 為了使系統(tǒng)中不發(fā)生死鎖現(xiàn)象，在系統(tǒng)設(shè)計初期即選擇一些限制條件，來破壞產(chǎn)生死鎖的4個必要條件之一或其中幾個。這樣，系統(tǒng)中就不會出現(xiàn)死鎖現(xiàn)象。這種方法對預(yù)防死鎖的發(fā)生非常有效，但有可能降低系統(tǒng)資源的利用率。,（2）避免死鎖 由于一方面預(yù)防死鎖的方法會降低系統(tǒng)資源利用率，另一方面死鎖的必要條件的存在未必就一定會使系統(tǒng)發(fā)生死鎖，

20、因此為提高系統(tǒng)資源的利用率，可采用避免死鎖。避免死鎖并不嚴格限制死鎖必要條件的存在，而是在資源的動態(tài)分配過程中，使用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖的最終出現(xiàn)。,（3）檢測和解除死鎖 由于死鎖產(chǎn)生的概率總是比較小的，所以在一些相對簡單的系統(tǒng)中，為節(jié)省預(yù)防或避免死鎖中所增加的系統(tǒng)開銷，系統(tǒng)中允許出現(xiàn)死鎖狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個檢測機構(gòu)，可以隨時檢測出死鎖的發(fā)生，并能確定與死鎖有關(guān)的進程和資源，然后采用適當(dāng)?shù)姆椒ń獬到y(tǒng)中的死鎖狀態(tài)。,常用的解除死鎖的方法有兩種：一是強制性地撤銷一些死鎖進程，并剝奪它們的資源給其他的進程；另一種是使用一個有效的掛起和解除掛起機構(gòu)來掛起一些進

21、程，以便從被掛起進程中剝奪一些資源，用來解除死鎖。,5.6.2 預(yù)防死鎖 1打破“請求和保持”條件 打破“請求和保持”條件，即把進程運行中所要求的所有資源在進程開始運行之前，一次性地分配給進程，只要有一種資源不能滿足，該進程就必須等待。這樣，進程在運行過程中就不再需要新的資源，這種方法又稱為預(yù)先靜態(tài)分配法。,2打破“不剝奪”條件 打破“不剝奪”條件，即強迫那些請求新資源而沒有立即得到滿足的進程釋放它已保持的其他資源。這意味著一個進程在運行過程可以暫時釋放已占有的資源，即允許其他進程剝奪使用該資源，從而破壞了“不剝奪”條件的出現(xiàn)。,3打破“環(huán)路等待”條件 死鎖產(chǎn)生時，一定存在一種進程和資源的循環(huán)

22、鏈。打破“環(huán)路等待”條件就是在資源的分配過程中，對資源的請求做出某種限制，使環(huán)路不可能出現(xiàn)。,5.7 線 程,5.7.1 線程的引入 由于進程是一個資源擁有者，所以在進程的創(chuàng)建、撤消和調(diào)度切換以及進程的同步與通信中，系統(tǒng)必須付出較大的時空開銷。正因為如此，在系統(tǒng)中所設(shè)置的進程數(shù)目不宜過多，進程切換的頻率也不宜過高，這也就限制了并發(fā)程度的進一步提高。,由以上對進程的分析可知，如果將進程的上述兩個屬性分開，由操作系統(tǒng)分開處理，將使多個程序更好地并發(fā)執(zhí)行，同時又可減少系統(tǒng)的開銷。也就是說，對于作為調(diào)度和分派的基本單位，不同時作為擁有資源的單位；而對于擁有資源的基本單位，又不對之進行頻繁的切換。正是在這種思想的指導(dǎo)下，形成了線程（Thread）的概念。,在引入線程的操作系統(tǒng)中，