chapter處理機(jī)調(diào)度與死鎖

1、第三章 處理機(jī)調(diào)度與死鎖第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的基本概念3.2 進(jìn)程調(diào)度算法3.3 實(shí)時(shí)調(diào)度3.4 多處理機(jī)系統(tǒng)中的調(diào)度3.5 產(chǎn)生死鎖的原因和必要條件3.6 預(yù)防死鎖的方法和死鎖避免3.7 死鎖的檢測和解除 3.1 處理機(jī)調(diào)度的基本概念 在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。 進(jìn)程調(diào)度要解決的問題WHAT：按什么原則分配CPU 進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī)HOW： 如何分配C

2、PU CPU調(diào)度過程（進(jìn)程的上下文切換）1. 高級、中級和低級調(diào)度l處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源l處理機(jī)調(diào)度算法對整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響l可把處理機(jī)調(diào)度分成三個(gè)層次： 高級調(diào)度高級調(diào)度 中級調(diào)度中級調(diào)度 低級調(diào)度低級調(diào)度 高級調(diào)度也稱為作業(yè)調(diào)度或長程調(diào)度 決定將外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程，排入就緒隊(duì)列，準(zhǔn)備執(zhí)行。作業(yè)調(diào)度的時(shí)間尺度通常是分鐘級。 中級調(diào)度中級調(diào)度又稱中程調(diào)度。 引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存

3、狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。涉及進(jìn)程在內(nèi)外存間的交換。 低級調(diào)度也稱進(jìn)程調(diào)度、短程調(diào)度，它決定就緒隊(duì)列中的哪個(gè)進(jìn)程獲得處理機(jī)。進(jìn)程調(diào)度的時(shí)間尺度通常是毫秒級的。2.進(jìn)程調(diào)度的任務(wù) 進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對CPU的競爭,即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程3.確定算法的原則 具有公平性 資源利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好） 在批處理系統(tǒng)情況下要追求系統(tǒng)

4、吞吐量4.進(jìn)程調(diào)度方式 非剝奪方式：分派程序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才把處理機(jī)分配給另一個(gè)進(jìn)程。 剝奪方式：當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。剝奪原則有：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時(shí)間片原則。5.進(jìn)程調(diào)度性能衡量的指標(biāo) 周轉(zhuǎn)時(shí)間 響應(yīng)時(shí)間 CPU-I/O執(zhí)行期6.進(jìn)程調(diào)度模型 1) 1)只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型圖 3 - 1 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 2)具有高低級調(diào)度的調(diào)度隊(duì)列模型圖 3-2 具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型3)具有三級調(diào)度的調(diào)度隊(duì)列

5、模型圖 3-3 具有三級調(diào)度時(shí)的調(diào)度隊(duì)列模型7.選擇進(jìn)程調(diào)度方式的準(zhǔn)則面向用戶的準(zhǔn)則： 周轉(zhuǎn)時(shí)間短； 所謂周轉(zhuǎn)時(shí)間，指作業(yè)從提交到完成的時(shí)間，作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時(shí)間 響應(yīng)時(shí)間快； 截止時(shí)間的保證； 優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；處理機(jī)利用率好；各類資源的平衡利用3.2 3.2 進(jìn)程調(diào)度算法 先進(jìn)先出(FIFO)算法 最短CPU運(yùn)行期優(yōu)先調(diào)度算法 最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 輪轉(zhuǎn)法 多級反饋隊(duì)列 1.先進(jìn)先出(FIFO)算法 該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，直到該進(jìn)程完成或阻塞時(shí)

6、，才釋放處理機(jī)。 優(yōu)點(diǎn):實(shí)現(xiàn)簡單. 缺點(diǎn):沒考慮進(jìn)程的優(yōu)先級1.先進(jìn)先出(FIFO)算法 FCFS有利于長作業(yè)，而不利于短作業(yè)。該算法短作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間為100，這是無法容忍的，而長作業(yè)D的帶權(quán)周轉(zhuǎn)時(shí)間僅為1.99。 所以，F(xiàn)CFS有利于CPU繁忙型作業(yè)（如科學(xué)計(jì)算），而不利于I/O繁忙型作業(yè)。目前大多數(shù)的事務(wù)處理都屬于I/O繁忙型作業(yè) 2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。 短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。 短

7、進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，使它立即執(zhí)行。圖 3-4 FCFS和SJF調(diào)度算法的性能 FCFS和SJF的性能比較 2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)： (1) 該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。 (2) 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。 (3) 由于作業(yè)(進(jìn)程

8、)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 3.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 該算法總是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。 搶占式 非搶占式 3.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 常用以下兩種方法來確定進(jìn)程的優(yōu)先權(quán)(優(yōu)先級根據(jù)優(yōu)先數(shù)來決定) 靜態(tài)優(yōu)先數(shù)法：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在整個(gè)運(yùn)行期間不再改變。依據(jù)有：進(jìn)程類型、進(jìn)程對資源的要求、用戶要求的優(yōu)先權(quán)。 3.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 動(dòng)態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先數(shù)，但在其生命周期內(nèi)優(yōu)先權(quán)可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的

9、，以便獲得更好的調(diào)度性能。 4.高響應(yīng)比優(yōu)先調(diào)度算法 優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 4.高響應(yīng)比優(yōu)先調(diào)度算法 (1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高， 從而也可獲得處理機(jī)。 5. 輪轉(zhuǎn)法 把CPU劃分成若干時(shí)間片,并且按順序

10、賦給就緒隊(duì)列中的每一個(gè)進(jìn)程，進(jìn)程輪流占有CPU，當(dāng)時(shí)間片用完時(shí)，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該進(jìn)程排在就緒隊(duì)列末尾。同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程運(yùn)行 簡單輪轉(zhuǎn)法：系統(tǒng)將所有就緒進(jìn)程按FIFO規(guī)則排隊(duì)，按一定的時(shí)間間隔把處理機(jī)分配給隊(duì)列中的進(jìn)程。這樣，就緒隊(duì)列中所有進(jìn)程均可獲得一個(gè)時(shí)間片的處理機(jī)而運(yùn)行。 多級隊(duì)列方法：將系統(tǒng)中所有進(jìn)程分成若干類，每類為一級。如分成前（輪轉(zhuǎn)法）、后臺(tái)（優(yōu)先權(quán)法）隊(duì)列。 6.分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇問題時(shí)間片選擇問題： 固定時(shí)間片 可變時(shí)間片與時(shí)間片大小有關(guān)的因素：與時(shí)間片大小有關(guān)的因素： 系統(tǒng)響應(yīng)時(shí)間正比 就緒進(jìn)程個(gè)數(shù)反比 CPU能力 1

11、)簡單輪轉(zhuǎn)法的調(diào)度模型2)多隊(duì)列反饋調(diào)度算法* 首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級。 第一個(gè)隊(duì)列的優(yōu)先級最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。* 每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級高的為第一級隊(duì)列，時(shí)間片最小，隨著隊(duì)列級別的降低，時(shí)間片加大* 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法* 一個(gè)新進(jìn)程就緒后進(jìn)入第一級隊(duì)列* 進(jìn)程由于等待而放棄CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列* 當(dāng)有一個(gè)優(yōu)先級更高的進(jìn)程就緒時(shí)，可以搶占CPU，被搶占進(jìn)程回到原來一級就緒隊(duì)列末尾* 當(dāng)?shù)谝患夑?duì)列空時(shí)，就去調(diào)度第二級隊(duì)列，如此類推* 當(dāng)時(shí)間片到后，進(jìn)程放棄CPU，回

12、到下一級隊(duì)列，如此下去，一個(gè)長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列 3)多隊(duì)列反饋調(diào)度算法 3)多隊(duì)列反饋調(diào)度算法多級反饋隊(duì)列調(diào)度算法的性能 終端型作業(yè)用戶。 短批處理作業(yè)用戶。 長批處理作業(yè)用戶。7.進(jìn)程調(diào)度算法 其中，RQ為就緒隊(duì)列指針，EP為運(yùn)行隊(duì)列指針。3.3 3.3 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度 1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 提供必要的信息(就緒時(shí)間、截止時(shí)間、處理時(shí)間、資源、優(yōu)先級)系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制3.3 3.3 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度 1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 具有快速切換機(jī)制對外部中斷的快速響應(yīng)能力。能及時(shí)響應(yīng)緊迫的外部事

13、件， 以免耽誤時(shí)機(jī)。 快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度， 應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開銷。 2.實(shí)時(shí)調(diào)度算法的分類 1)非搶占式調(diào)度算法非搶占式調(diào)度算法 : 非搶占式輪轉(zhuǎn)調(diào)度算法 非搶占式優(yōu)先調(diào)度算法2)2)搶占式調(diào)度算法搶占式調(diào)度算法: : 基于時(shí)鐘中斷的搶占優(yōu)先調(diào)度算法 幾毫秒幾十毫秒 立即搶占優(yōu)先權(quán)調(diào)度算法。 幾毫秒100微秒 圖 3-5 實(shí)時(shí)進(jìn)程調(diào)度 3.常用的幾種實(shí)時(shí)調(diào)度算法 1）最早截止時(shí)間優(yōu)先即）最早截止時(shí)間優(yōu)先即EDF(Earliest Deadline First)算法算法 圖 3-6

14、 EDF算法用于非搶占調(diào)度方式 3.常用的幾種實(shí)時(shí)調(diào)度算法 1）最早截止時(shí)間優(yōu)先即）最早截止時(shí)間優(yōu)先即EDF算法的缺點(diǎn)：算法的缺點(diǎn)： 圖 3-6 EDF算法用于非搶占調(diào)度方式 只考慮了進(jìn)程的截止時(shí)間，未考慮其運(yùn)行時(shí)間只考慮了進(jìn)程的截止時(shí)間，未考慮其運(yùn)行時(shí)間2）最低松弛度優(yōu)先(LLF)算法 該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。該算法主要用于可搶占調(diào)度方式中。 假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每 20 ms執(zhí)行一次，執(zhí)行時(shí)間為 10 ms；任務(wù)B只要求每50 ms執(zhí)行一次，執(zhí)行時(shí)間為 25 ms。 圖 3-7 A和B任務(wù)每次必須完成的時(shí)間 在剛開始

15、時(shí)(t1=0)，A1必須在20ms時(shí)完成，而它本身運(yùn)行又需 10 ms，可算出A1的松弛度為10ms；B1必須在50ms時(shí)完成， 而它本身運(yùn)行就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10 ms時(shí)，A2的松弛度可按下式算出： A2的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間 =40 ms-10 ms-10 ms=20 ms 類似地，可算出B1的松弛度為15ms，調(diào)度程序應(yīng)選擇B1運(yùn)行。t3=30 ms時(shí)，A2的松弛度已減為0，B1的松弛度為15 ms，于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行.圖 3-8 利用ELLF算法進(jìn)行調(diào)度的情況t4=4

16、0 ms時(shí)，A3的松弛度為10 ms ，B1的松弛度為5 ms，于是重新調(diào)度B1；t5=45 ms時(shí)，B1完成，而A3的松弛度只有5 ms，而B2還有30，先調(diào)度A3；t6=55 ms時(shí)，A3完成，而A4的松弛度有15 ms，而B2有20，應(yīng)先執(zhí)行A4，但由于A尚未進(jìn)入第4周期，而B已進(jìn)入第2周期，所以先調(diào)度B2；t7=70 ms時(shí)，A4的松弛度已減為0，而B2有20，于是調(diào)度程序應(yīng)搶占B2的處理機(jī)而調(diào)度A4運(yùn)行；圖 3-8 利用ELLF算法進(jìn)行調(diào)度的情況3.4 多處理機(jī)系統(tǒng)中的調(diào)度 1.1.多處理器系統(tǒng)的類型多處理器系統(tǒng)的類型 (1) 緊密耦合(Tightly Coupted)MPS。 (2

17、) 松散耦合(Loosely Coupled)MPS。2.2.對稱對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)3.進(jìn)程分配方式 (1)對稱多處理器系統(tǒng)中的進(jìn)程分配方式 靜態(tài)分配(Static Assigenment)方式 動(dòng)態(tài)分配(Dynamic Assgement)方式 (2)非對稱MPS中的進(jìn)程分配方式4. 進(jìn)程(線程)調(diào)度方式 (1）自調(diào)度(Self-Scheduling)方式 （2）成組調(diào)度(Gang Scheduling)方式英特爾 酷睿 雙核處理器 英特爾 酷睿 雙核處理器帶有兩個(gè)執(zhí)行內(nèi)核，專為多線程應(yīng)用和多任務(wù)處理進(jìn)行了優(yōu)化。 可以同時(shí)運(yùn)行多種要求苛刻的應(yīng)用，如圖形密集型游戲或序列號運(yùn)算

18、程序；同時(shí)在后臺(tái)下載音樂或運(yùn)行病毒掃描安全程序。2.91 億個(gè)晶體管65納米芯片加工工藝512核芯片 浮點(diǎn)運(yùn)算每秒5120億次Grape DR處理器采用90nm制程，由臺(tái)積電代工，尺寸為1717mm ，每秒5120億次浮點(diǎn)(512Gflops)運(yùn)算能力.60W其目標(biāo)是在2008年達(dá)到每秒運(yùn)算2000萬億次浮點(diǎn)(2Petaflops)，并以40Gbps帶寬連接各個(gè)中央處理單位. 2010年研發(fā)45納米工藝、計(jì)算能力達(dá)34Tflops的處理器Grape DR處理器芯片組，接口為PCI-XGrape DR處理器演示采用AMD Opteron 2路系統(tǒng)，可見其開放性 512核芯片 浮點(diǎn)運(yùn)算每秒5120

19、億次3.4 多處理機(jī)系統(tǒng)中的調(diào)度 1.1.多處理器系統(tǒng)的類型多處理器系統(tǒng)的類型 (1) 緊密耦合(Tightly Coupted)MPS。 這通常是通過高速總線或高速交叉開關(guān)，來實(shí)現(xiàn)多個(gè)處理器之間的互連的。它們共享主存儲(chǔ)器系統(tǒng)和I/O設(shè)備，并要求將主存儲(chǔ)器劃分為若干個(gè)能獨(dú)立訪問的存儲(chǔ)器模塊，以便多個(gè)處理機(jī)能同時(shí)對主存進(jìn)行訪問。系統(tǒng)中的所有資源和進(jìn)程，都由操作系統(tǒng)實(shí)施統(tǒng)一的控制和管理。3.4 多處理機(jī)系統(tǒng)中的調(diào)度 1.1.多處理器系統(tǒng)的類型多處理器系統(tǒng)的類型 (2) 松散耦合(Loosely Coupled)MPS。 在松散耦合MPS中，通常是通過通道或通信線路，來實(shí)現(xiàn)多臺(tái)計(jì)算機(jī)之間的互連。每臺(tái)

20、計(jì)算機(jī)都有自己的存儲(chǔ)器和I/O設(shè)備，并配置了OS來管理本地資源和在本地運(yùn)行的進(jìn)程。因此，每一臺(tái)計(jì)算機(jī)都能獨(dú)立地工作， 必要時(shí)可通過通信線路與其它計(jì)算機(jī)交換信息，以及協(xié)調(diào)它們之間的工作。 3.4 多處理機(jī)系統(tǒng)中的調(diào)度 2.2.對稱對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)(1) 對稱多處理器系統(tǒng)SMPS(Symmetric MultiProcessor System)。 在系統(tǒng)中所包含的各處理器單元，在功能和結(jié)構(gòu)上都是相同的， 當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC處理器構(gòu)成的。 (2) 非對稱多處理器系統(tǒng)。在系統(tǒng)中有

21、多種類型的處理單元， 它們的功能和結(jié)構(gòu)各不相同，其中只有一個(gè)主處理器，有多個(gè)從處理器。 3.4 多處理機(jī)系統(tǒng)中的調(diào)度 3.進(jìn)程分配方式 (1)對稱多處理器系統(tǒng)中的進(jìn)程分配方式在SMP系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為一個(gè)處理器池(Processor pool)，由調(diào)度程序或基于處理器的請求， 將任何一個(gè)進(jìn)程分配給池中的任何一個(gè)處理器去處理。在進(jìn)行進(jìn)程分配時(shí)，可采用以下兩種方式之一。 1) 靜態(tài)分配(Static Assigenment)方式 2) 動(dòng)態(tài)分配(Dynamic Assgement)方式 (2)非對稱MPS中的進(jìn)程分配方式3.4 多處理機(jī)系統(tǒng)中的調(diào)度 3.進(jìn)程分

22、配方式 (2)非對稱MPS中的進(jìn)程分配方式 對于非對稱MPS，其OS大多采用主從(Master-Slave)式OS，即OS的核心部分駐留在一臺(tái)主機(jī)上(Master)，而從機(jī)(Slave)上只是用戶程序，進(jìn)程調(diào)度只由主機(jī)執(zhí)行。 每當(dāng)從機(jī)空閑時(shí)，便向主機(jī)發(fā)送一索求進(jìn)程的信號，然后，便等待主機(jī)為它分配進(jìn)程。在主機(jī)中保持有一個(gè)就緒隊(duì)列，只要就緒隊(duì)列不空，主機(jī)便從其隊(duì)首摘下一進(jìn)程分配給請求的從機(jī)。從機(jī)接收到分配的進(jìn)程后便運(yùn)行該進(jìn)程，該進(jìn)程結(jié)束后從機(jī)又向主機(jī)發(fā)出請求。 3.4 多處理機(jī)系統(tǒng)中的調(diào)度 4. 進(jìn)程(線程)調(diào)度方式 (1）自調(diào)度(Self-Scheduling)方式 在多處理器系統(tǒng)中，自調(diào)度方式

23、是最簡單的一種調(diào)度方式。它是直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來的。在系統(tǒng)中設(shè)置有一個(gè)公共的進(jìn)程或線程就緒隊(duì)列，所有的處理器在空閑時(shí)，都可自己到該隊(duì)列中取得一進(jìn)程(或線程)來運(yùn)行。在自調(diào)度方式中，可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法，如先來先服務(wù)(FCFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。 3.4 多處理機(jī)系統(tǒng)中的調(diào)度 4. 進(jìn)程(線程)調(diào)度方式 (1）自調(diào)度(Self-Scheduling)方式缺點(diǎn)：瓶頸問題。 低效性。 線程切換頻繁。其調(diào)度算法可沿用單處理機(jī)系統(tǒng)所用的算法，亦即，很容易將單處理機(jī)環(huán)境下的調(diào)度機(jī)制移植到多處理機(jī)系統(tǒng)中， 故它仍然是

24、當(dāng)前多處理機(jī)系統(tǒng)中較常用的調(diào)度方式。3.4 多處理機(jī)系統(tǒng)中的調(diào)度 （2）成組調(diào)度(Gang Scheduling)方式為解決自調(diào)度中線程切換頻繁的問題，可將一個(gè)進(jìn)程中的一組線程分配給一組CPU執(zhí)行。 1) 面向所有應(yīng)用程序平均分配處理器時(shí)間2) 面向所有線程平均分配處理器時(shí)間圖 3 - 10 兩種分配處理器時(shí)間的方法 第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 死鎖的概念死鎖的概念1.1.死鎖例子死鎖例子: : 一個(gè)由于一個(gè)由于申請不同類型資源申請不同類型資源而產(chǎn)生死鎖而產(chǎn)生死鎖的例子的例子 設(shè)系統(tǒng)有一臺(tái)打印機(jī)設(shè)系統(tǒng)有一臺(tái)

25、打印機(jī)(R1)(R1)一臺(tái)掃描儀一臺(tái)掃描儀(R2)(R2)，兩進(jìn)程共享這兩臺(tái)設(shè)備。，兩進(jìn)程共享這兩臺(tái)設(shè)備。 用信號量用信號量S1S1表示表示R1R1是否可用，用信號量是否可用，用信號量S2S2表示表示R2R2是否可用，是否可用， S1S1、 S2S2初值為初值為1 1。 死鎖例子死鎖例子 這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過程中，可這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過程中，可能會(huì)發(fā)生死鎖。大家可以思考一下，如能會(huì)發(fā)生死鎖。大家可以思考一下，如何修改，進(jìn)程才不會(huì)發(fā)生死鎖。何修改，進(jìn)程才不會(huì)發(fā)生死鎖。2.死鎖概念 指多個(gè)進(jìn)程因競爭共享資源而造成的指多個(gè)進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程一種僵局，若無外

26、力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。都將永遠(yuǎn)不能再向前推進(jìn)。 即：一組進(jìn)程中，每個(gè)進(jìn)程都無限等即：一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。為死鎖進(jìn)程。2.死鎖概念3.5.2 產(chǎn)生死鎖的原因1.1.競爭系統(tǒng)資源競爭系統(tǒng)資源競爭非剝奪性資源（打印機(jī)、磁帶機(jī)）競爭非剝奪性資源（打印機(jī)、磁帶機(jī)）競爭臨時(shí)性資源競爭臨時(shí)性資源 只可使用一次的資源；如信號量只可使用一次的資源；如信號量, ,中斷信號，同步中斷信號，

27、同步信號等（可消耗性資源）信號等（可消耗性資源） “申請申請-分配分配-使用使用-釋放釋放”模式模式2.2.進(jìn)程的推進(jìn)順序不當(dāng)進(jìn)程的推進(jìn)順序不當(dāng) 1. 1. 競爭系統(tǒng)資源 若系統(tǒng)中只有一臺(tái)打印機(jī)若系統(tǒng)中只有一臺(tái)打印機(jī)R1R1和一臺(tái)和一臺(tái)讀卡讀卡機(jī)機(jī)R2R2，可供進(jìn)程，可供進(jìn)程P1P1和和P2P2共享。若共享。若形形成環(huán)路成環(huán)路，這樣會(huì)產(chǎn)生死鎖，這樣會(huì)產(chǎn)生死鎖。 2.2.進(jìn)程的推進(jìn)順序不當(dāng) 在進(jìn)程在進(jìn)程P1P1和和P2P2并發(fā)執(zhí)行時(shí)，按照左圖曲并發(fā)執(zhí)行時(shí)，按照左圖曲線線所示順序推進(jìn)時(shí)，兩進(jìn)程會(huì)順?biāo)卷樞蛲七M(jìn)時(shí)，兩進(jìn)程會(huì)順利完成，我們稱這種推進(jìn)順序是合法的。利完成，我們稱這種推進(jìn)順序是合法的。若按

28、曲線若按曲線的順序推進(jìn)時(shí)，進(jìn)入不安全的順序推進(jìn)時(shí)，進(jìn)入不安全區(qū)區(qū)D D內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。 2.2.進(jìn)程的推進(jìn)順序不當(dāng)若并發(fā)進(jìn)程P1和P2按曲線所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時(shí)P1保持了資源R1, P2保持了資源R2, 系統(tǒng)處于不安全狀態(tài)。因?yàn)?，這時(shí)兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運(yùn)行到P1:Request(R2)時(shí)，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)行到P2: Request(R1)時(shí)，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖。 3.5.3 產(chǎn)生死鎖的必要條件 綜上所述，在同時(shí)具備下列四個(gè)條件時(shí)，綜上所述，在同時(shí)具備下列

29、四個(gè)條件時(shí)，就會(huì)產(chǎn)生死鎖。就會(huì)產(chǎn)生死鎖?；コ鈼l件互斥條件（資源獨(dú)占）（資源獨(dú)占） 在一段時(shí)間內(nèi)，一個(gè)資源只能由一個(gè)進(jìn)程獨(dú)占使用，在一段時(shí)間內(nèi)，一個(gè)資源只能由一個(gè)進(jìn)程獨(dú)占使用，若別的進(jìn)程也要求該資源，則須等待，直至其占用者若別的進(jìn)程也要求該資源，則須等待，直至其占用者釋放；釋放；請求和保持條件請求和保持條件 允許進(jìn)程在不釋放其已分得資源的情況下請求并等待允許進(jìn)程在不釋放其已分得資源的情況下請求并等待分配新的資源；分配新的資源；不剝奪條件（不剝奪條件（不可強(qiáng)占）不可強(qiáng)占） 進(jìn)程所獲得的資源在未使用完之前，不能被其它進(jìn)程強(qiáng)行奪進(jìn)程所獲得的資源在未使用完之前，不能被其它進(jìn)程強(qiáng)行奪走，而只能由其自身釋放

30、；走，而只能由其自身釋放；環(huán)路等待條件。環(huán)路等待條件。 存在一個(gè)等待進(jìn)程集合，存在一個(gè)等待進(jìn)程集合，P0P0正在等待一個(gè)正在等待一個(gè)P1P1占用的資源，占用的資源，P1P1正在等待正在等待一個(gè)一個(gè)P2P2占用的資源，占用的資源，PnPn正在等待一個(gè)由正在等待一個(gè)由POPO占用的資源。占用的資源。解決死鎖的基本辦法 預(yù)防死鎖預(yù)防死鎖 避免死鎖避免死鎖 檢測死鎖檢測死鎖 解除死鎖解除死鎖 3.6 預(yù)防死鎖的方法和避免死鎖 1.預(yù)防死鎖的方法 在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件任何一個(gè)。 3.6 預(yù)防死鎖的方法和避免死鎖1)1)破壞請求和保持條件破壞

31、請求和保持條件資源一次性分配；資源一次性分配；要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才給予一次性分配(破壞請求和保持條件)2)2)破壞不可剝奪條件破壞不可剝奪條件可剝奪資源；可剝奪資源；即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的資源3)3)破壞環(huán)路等待條件破壞環(huán)路等待條件資源有序分配法資源有序分配法；系統(tǒng)給每類資源賦予一個(gè)編號，每一個(gè)進(jìn)程按編號遞增的順序請求資源，釋放則相反2. 死鎖避免 預(yù)防死鎖的幾種策略，會(huì)嚴(yán)重地?fù)p害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意得系統(tǒng)性能來避免死鎖。 死鎖避免定義死鎖避免定義:在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一

32、個(gè)系統(tǒng)能夠滿足的資源申請進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。 該方法把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要處于安全狀態(tài)就可以避免死鎖。3. 安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來為每個(gè)進(jìn)程分配其所需資源，直至最來為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。若大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這樣一個(gè)序列，則稱系統(tǒng)處系統(tǒng)不存在這樣一個(gè)序列，則稱系統(tǒng)處于不安全狀態(tài)。于不安全狀態(tài)。 1)安全序列 所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)

33、(稱P1, P2, , Pn序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。檢測可滿足請求 分配 不分配安全不安全系統(tǒng)處于安全狀態(tài)：存在安全進(jìn)程序列進(jìn)程序列安全，p1,p2,pn可依次進(jìn)行完。 2) 安全狀態(tài)之例安全狀態(tài)之例 我們通過一個(gè)例子來說明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程P1、 P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示： 進(jìn)

34、 程 最 大 需 求 已 分 配 可 用 P1P2P310495223進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495223給P3分配一個(gè)后 3) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)?，此時(shí)也無法再找到一個(gè)安全序列， 例如，把其余的2臺(tái)分配給P2，這樣，在P2完成后只能釋放出4臺(tái)，既不能滿足P1尚需5臺(tái)的要求，也不能滿足P3尚需6臺(tái)的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對

35、方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。 進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495223安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)可能導(dǎo)致死鎖4.利用銀行家算法避免死鎖 1)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。 (2) 最大需求矩陣Max。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)

36、程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 (3) 分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。 (4) 需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。 Needi,j=Maxi,j-Allocationi,j 2)銀行家算法銀行家算法 設(shè)Requesti是進(jìn)程Pi的請求向量，如果Reques

37、tij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej =Availablej-Requestij; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij;

38、(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 3)安全性算法（略讀）安全性算法（略讀） (1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work =Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi =false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi =true。 (2) 從進(jìn)程集合中找到一

39、個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 4) 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 圖 3-8 T0時(shí)刻的資源分配表 (1) T0時(shí)刻的安全性： 圖 3-9 T0時(shí)刻的安全序列 (2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修