??上一章介紹的進(jìn)程主要從概念出發(fā)，但程序執(zhí)行終歸是動(dòng)態(tài)的。進(jìn)程如何參與程序的動(dòng)態(tài)執(zhí)行過(guò)程呢？在多道程序下，進(jìn)程的數(shù)量遠(yuǎn)大于處理機(jī)的數(shù)量。那如何對(duì)進(jìn)程進(jìn)行安排(處于就緒狀態(tài)的進(jìn)程有好多，選哪些進(jìn)程給處理機(jī)執(zhí)行)，才能達(dá)到一些我們期望的指標(biāo)(系統(tǒng)吞吐率，資源利用率，響應(yīng)的及時(shí)性)？而這一切的實(shí)現(xiàn)很大程度取決于處理機(jī)調(diào)度性能的好壞。
??從內(nèi)容上說(shuō)，本章大體可以分為三個(gè)部分：CPU調(diào)度、實(shí)時(shí)調(diào)度、死鎖。下面讓我們一一介紹下吧！

??一、 CPU調(diào)度

??一個(gè)程序從最開始在內(nèi)存中到最后執(zhí)行完畢經(jīng)歷了一段過(guò)程。從調(diào)度角度上來(lái)看，經(jīng)過(guò)了三個(gè)調(diào)度階段。分別是高級(jí)調(diào)度、中級(jí)調(diào)度、低級(jí)調(diào)度

??高級(jí)調(diào)度/長(zhǎng)程調(diào)度/作業(yè)調(diào)度

??高級(jí)調(diào)度指從外存中選出若干作業(yè)，為它們分配進(jìn)程，并改變進(jìn)程的狀態(tài)為就緒狀態(tài)

??低級(jí)調(diào)度/進(jìn)程調(diào)度/短程調(diào)度

??低級(jí)調(diào)度指在就緒隊(duì)列中選擇一個(gè)進(jìn)程為它提供處理機(jī)資源

??中級(jí)調(diào)度/內(nèi)存調(diào)度

??中級(jí)調(diào)度的目的是提高內(nèi)存利用率和系統(tǒng)吞吐率。方式是將內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程放到外存中(俗稱掛起)。當(dāng)具備運(yùn)行條件后再由中級(jí)調(diào)度重新調(diào)入內(nèi)存。
??大致順序就是高級(jí)調(diào)度->低級(jí)調(diào)度->（中級(jí)調(diào)度）->執(zhí)行結(jié)束。由于分時(shí)特點(diǎn)，低級(jí)調(diào)度可能要多次。
??衡量處理機(jī)調(diào)度算法的好壞有幾個(gè)指標(biāo)，也是目標(biāo)。優(yōu)化這些目標(biāo)就是我們的目的。

??周轉(zhuǎn)時(shí)間

??周轉(zhuǎn)時(shí)間指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括下圖四個(gè)部分：

??平均周轉(zhuǎn)時(shí)間

??平均周轉(zhuǎn)時(shí)間就是所有作業(yè)的周轉(zhuǎn)時(shí)間之和除以作業(yè)個(gè)數(shù)

??帶權(quán)周轉(zhuǎn)時(shí)間

??帶權(quán)周轉(zhuǎn)時(shí)間指周轉(zhuǎn)時(shí)間除以執(zhí)行時(shí)間。執(zhí)行時(shí)間就是結(jié)束時(shí)間減去開始時(shí)間

??概念比較抽象，下面結(jié)合一個(gè)例題看看：

??以作業(yè)二為例，計(jì)算它的周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間
??周轉(zhuǎn)時(shí)間是完成時(shí)間-提交時(shí)間 是13.00-10.10=2.9
??帶權(quán)周轉(zhuǎn)時(shí)間是周轉(zhuǎn)時(shí)間/執(zhí)行時(shí)間，執(zhí)行時(shí)間是完成時(shí)間-開始時(shí)間=13.00-12.00 = 1。帶權(quán)周轉(zhuǎn)時(shí)間 = 2.9/1 = 2.9。
??同理計(jì)算作業(yè)1，3的周轉(zhuǎn)時(shí)間求和再除以三，就得到平均周轉(zhuǎn)時(shí)間了。簡(jiǎn)不簡(jiǎn)單！

??說(shuō)別的都沒(méi)用，好壞還是要看調(diào)度算法怎么樣。下面就介紹一下6種調(diào)度算法：

??先來(lái)先服務(wù)調(diào)度算法（FCFS， first come first serve）

??這種是最容易實(shí)現(xiàn)的算法，先到先執(zhí)行。那我們來(lái)評(píng)價(jià)一下這個(gè)算法的性能：

??上圖有四個(gè)作業(yè)，A,B,C,D依次到達(dá)。直接看性能(帶權(quán)周轉(zhuǎn)性能)，A,B,D都可以看，但C有點(diǎn)兒慘。但實(shí)際上C執(zhí)行的時(shí)間相當(dāng)短，這就是因?yàn)镃在B這個(gè)很長(zhǎng)的任務(wù)后面。導(dǎo)致周轉(zhuǎn)時(shí)間特別長(zhǎng)，遠(yuǎn)超執(zhí)行時(shí)間。這種算法對(duì)短任務(wù)很不友好，短任務(wù)在長(zhǎng)任務(wù)前面執(zhí)行還好，但在后面性能就會(huì)特別差。

??短作業(yè)優(yōu)先調(diào)度算法

??（1） 最短作業(yè)優(yōu)先

??這種算法就有優(yōu)先級(jí)存在了，作業(yè)越短優(yōu)先級(jí)越高。這就保證了短任務(wù)都能先執(zhí)行。舉個(gè)例子，說(shuō)明執(zhí)行過(guò)程：

??假設(shè)它們都是同一時(shí)間到達(dá)，burst time是執(zhí)行時(shí)間。按照最小原則，執(zhí)行順序依次是4，??1，3，2。從直觀上感覺(jué)，這個(gè)性能應(yīng)該比FCFS好點(diǎn)兒。但這個(gè)算法有一個(gè)很難搞的問(wèn)題：我怎么知道一個(gè)進(jìn)程會(huì)執(zhí)行多長(zhǎng)時(shí)間呢？所以要用這個(gè)，就必須去估算一下，而且誤差還不能太大。

??（2） 最短剩余時(shí)間優(yōu)先

??這個(gè)和最短作業(yè)優(yōu)先很像，是它的搶占式版本。搶占的依據(jù)就是正在執(zhí)行的進(jìn)程A剩余時(shí)間比新來(lái)的進(jìn)程B整個(gè)時(shí)間還要長(zhǎng)。這種思想也很好理解，假如B一直沒(méi)有來(lái)，A作為唯一進(jìn)程執(zhí)行，執(zhí)行一旦開始就會(huì)直至結(jié)束。如果A很長(zhǎng)，B很短的話，B來(lái)了也不能執(zhí)行，有點(diǎn)兒退化成了FCFS。最短剩余時(shí)間每時(shí)每刻都檢查進(jìn)程的剩余時(shí)間來(lái)決定分配。用例子說(shuō)明下：

??0時(shí)刻，P1到達(dá)執(zhí)行P1。1時(shí)刻P2到達(dá)，P2是4，P1是7，優(yōu)先P2。2時(shí)刻到達(dá)，P1是7，P2是3，P3是9，繼續(xù)P2，3時(shí)刻仍是P2最小。P2執(zhí)行完選最小的是P4的5，P4結(jié)束后再進(jìn)行P1的7，再P3的9。畫出圖來(lái)，就是這樣：

??這個(gè)算法也有缺陷，也要執(zhí)行程序的執(zhí)行時(shí)間。不過(guò)性能和最短作業(yè)相比要好。

??優(yōu)先級(jí)調(diào)度算法

??（1） 普通優(yōu)先級(jí)調(diào)度

?? 其實(shí)前幾種方法已經(jīng)體現(xiàn)了優(yōu)先級(jí)思想，就是時(shí)間越少，優(yōu)先級(jí)越高。但這算法中顯式的給出優(yōu)先級(jí)，于是進(jìn)程就按照優(yōu)先級(jí)執(zhí)行就行了。

??（2） 高響應(yīng)比優(yōu)先級(jí)調(diào)度

?? 不過(guò)前一種方法存在一個(gè)問(wèn)題，優(yōu)先級(jí)是怎么確定呢？確定會(huì)不會(huì)不公平呢？所以高響應(yīng)比算法用相應(yīng)比去評(píng)價(jià)優(yōu)先級(jí)：

??當(dāng)使用響應(yīng)比以后，就比較公平啦！這樣的優(yōu)點(diǎn)是兼顧了長(zhǎng)短進(jìn)程，但計(jì)算優(yōu)先權(quán)也要一點(diǎn)兒額外開銷。

?? 輪轉(zhuǎn)調(diào)度算法

?? 輪轉(zhuǎn)調(diào)度有點(diǎn)兒像分時(shí)復(fù)用，把處理機(jī)分很多個(gè)時(shí)間片。均勻的分給所有進(jìn)程，這就保證了所有進(jìn)程都能夠得到執(zhí)行。這種方法問(wèn)題就是時(shí)間片的大小不好確定，時(shí)間太長(zhǎng)變成了先到先服務(wù)，時(shí)間太短來(lái)回上下文切換頻次太高，不值當(dāng)！

?? 多級(jí)隊(duì)列調(diào)度

??多級(jí)隊(duì)列的思想是針對(duì)于不同進(jìn)程的不同需求，對(duì)于交互進(jìn)程希望響應(yīng)時(shí)間短(且不管是否執(zhí)行完，但要開始執(zhí)行)，比較適合輪轉(zhuǎn)調(diào)度。但后臺(tái)的批處理(數(shù)值計(jì)算)，一直算就行，只要保證能夠執(zhí)行就可以，就可以用FCFS。所以這里的多級(jí)隊(duì)列就是將就緒隊(duì)列分成多個(gè)隊(duì)列，不同隊(duì)列根據(jù)需求使用不同算法。

?? 多級(jí)反饋隊(duì)列調(diào)度

?? 多級(jí)反饋隊(duì)列就是在多級(jí)隊(duì)列基礎(chǔ)上改進(jìn)了一下，增強(qiáng)了動(dòng)態(tài)性。使用多級(jí)隊(duì)列(不同隊(duì)列可以不同算法)，如果進(jìn)程在第一級(jí)沒(méi)有得到處理，就到第二級(jí)。。。以此類推，直到執(zhí)行為止。

??二、實(shí)時(shí)調(diào)度

?? 對(duì)于實(shí)時(shí)調(diào)度其實(shí)不是課程的重點(diǎn)，但在嵌入式操作系統(tǒng)中都是實(shí)時(shí)調(diào)度。還是有必要簡(jiǎn)單了解下滴。那啥叫實(shí)時(shí)調(diào)度呢？來(lái)一個(gè)引入：

??在這個(gè)系統(tǒng)中，周期是50ms，而每次處理時(shí)間10ms，如果對(duì)于5個(gè)任務(wù)來(lái)說(shuō)可以執(zhí)行(相鄰執(zhí)行時(shí)間滿足最大間隔要求)，但如果是6個(gè)任務(wù)的話，任務(wù)A第一次執(zhí)行和第二次執(zhí)行間隔60ms，超過(guò)了50ms的周期，沒(méi)法完成調(diào)度了。所以系統(tǒng)是否能夠進(jìn)行實(shí)時(shí)調(diào)度，是有條件的，就是：

??概念是概念，具體的調(diào)度過(guò)程是由算法決定的，下面就介紹一下常用的實(shí)時(shí)調(diào)度算法：

??最早截至?xí)r間優(yōu)先(EDF, earliest deadline first)

?? 這個(gè)算法思想很簡(jiǎn)單，就是按照截至?xí)r間來(lái)決定優(yōu)先級(jí)。越早截至，優(yōu)先級(jí)越高。舉個(gè)例子：

??這個(gè)例子中，任務(wù)到達(dá)都是在進(jìn)程執(zhí)行中。在非搶占式情況下是沒(méi)影響的。截至?xí)r間依次是1342，所以任務(wù)執(zhí)行順序也就是1342。

??最低松弛度優(yōu)先(LLF, least laxity first)

?? 這個(gè)需要先解釋啥什么叫松弛度，可以理解成該任務(wù)為保證完成最晚從哪里開始到當(dāng)前的長(zhǎng)度。選短的(最緊迫)執(zhí)行。這個(gè)理解比較抽象，舉個(gè)例子：

??進(jìn)程A1執(zhí)行截至?xí)r間是20，進(jìn)程B1截至?xí)r間是50，A1執(zhí)行時(shí)間是10，B1執(zhí)行時(shí)間是25。那A1松弛度為10，B1松弛度為25。A1優(yōu)先執(zhí)行。A1到10的時(shí)候執(zhí)行結(jié)束，其他任務(wù)還沒(méi)到，B1開始執(zhí)行。到20時(shí)，A2到達(dá)，A2截至?xí)r間為40，執(zhí)行時(shí)間為10，松弛度為10(30必須開始)。B1松弛度為15(已經(jīng)執(zhí)行了10，還有15，50-15-20=15)優(yōu)先執(zhí)行A2，依次類推，最終執(zhí)行結(jié)果圖如下：

??三、死鎖

?? 前面陸續(xù)地介紹過(guò)了死鎖，死鎖一種現(xiàn)象。會(huì)讓程序運(yùn)行終止，系統(tǒng)資源利用率降低。這節(jié)中更為詳細(xì)的介紹一下死鎖，并給出一些死鎖的解決辦法。
?? 了解了死鎖的含義，但也不知道怎么描述，下面給一個(gè)具體定義：如果一組進(jìn)程中每個(gè)進(jìn)程都在等待只有組內(nèi)其他進(jìn)程才能引發(fā)的事件，就稱這一組進(jìn)程處于死鎖狀態(tài)。有個(gè)問(wèn)題來(lái)了，如何避免死鎖呢？其實(shí)死鎖發(fā)生需要一些條件，如果我們能避免這些條件，那不就可以解除死鎖了嗎！我們稱這些條件為必要條件：

??對(duì)死鎖的解決還有三個(gè)策略：

??比較有意思的是，課程主要講了前兩種策略，但實(shí)際應(yīng)用過(guò)程中第三種更為廣泛。但對(duì)于第三種也沒(méi)有深刻探究，還是就介紹下學(xué)過(guò)的吧！

?? 預(yù)防策略

?? 之前說(shuō)要破壞條件，那上面介紹了四個(gè)條件。互斥條件是不可避免的(因?yàn)榛コ馐菫榱吮ＷC進(jìn)程之間有效運(yùn)行的必要條件，所有進(jìn)程的執(zhí)行都需要滿足互斥，不能為了這個(gè)不管那個(gè))
?? 另外三種都有一些方法(直接截圖介紹了)：

?? 避免策略

?? 為什么要提出避免策略呢？是因?yàn)轭A(yù)防策略過(guò)于保守(怎么理解？預(yù)防策略解決問(wèn)題的方式是直接不讓問(wèn)題發(fā)生，這顯然是一種方法，但過(guò)程過(guò)于絕對(duì)，可能帶來(lái)一些其他的影響。更優(yōu)的策略顯然是可以讓問(wèn)題發(fā)生，并進(jìn)而想方法解決問(wèn)題。這就是避免策略！)避免 策略有一些新規(guī)定：

??簡(jiǎn)單來(lái)說(shuō)，避免策略的思想就是，如果一個(gè)操作會(huì)讓安全狀態(tài)變成不安全狀態(tài)，那么就不執(zhí)行這個(gè)操作。那如何判定呢？不能每次都靠看啊。下面就介紹一個(gè)專門用來(lái)判斷的算法：銀行家算法。
?? 銀行家算法的思想是找到一個(gè)正確的就是正確的，找不到正確的就是錯(cuò)誤的。算法的描述如下：
??有四個(gè)變量：
??Available：當(dāng)前系統(tǒng)中可以進(jìn)行分配的資源數(shù)
??Max：各進(jìn)程所需要的最大資源數(shù)
?? Allocation：各進(jìn)程已經(jīng)分配的資源數(shù)
?? Need：各進(jìn)程還需要的資源數(shù) Need = Max – Allocaiton

?? 計(jì)算完四個(gè)變量后，就需要對(duì)操作進(jìn)行判斷。有幾個(gè)步驟：
??1. 首先將進(jìn)程請(qǐng)求設(shè)為變量request，如果requset小于need，跳轉(zhuǎn)2。否則認(rèn)為出錯(cuò)，因??為要求值超過(guò)宣布的最大值。
??2. 然后判斷request是否小于available，滿足到3，否則說(shuō)明進(jìn)程目前沒(méi)有足夠資源
??3. 試探將資源進(jìn)程分配，然后啟用安全策略進(jìn)行判斷。

??完成上面這些已經(jīng)差不多一半兒了！下面看看安全性算法吧：

??結(jié)合一個(gè)具體的例子看下：

??按照上面的算法，其中變量的變換過(guò)程如下圖：

??第三章打板兒，繼續(xù)學(xué)習(xí)，繼續(xù)加油吧！

因作者水平有限，如有錯(cuò)誤之處，請(qǐng)?jiān)谙路皆u(píng)論區(qū)指出，謝謝！

總結(jié)

以上是生活随笔為你收集整理的三、处理机调度与死锁的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。