第三章處理機調度與死鎖3.1處理機調度的基本概念3.2調度算法3.3實時調度3.4多處理機系統中的調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除3.1處理機調度的基本概念3.1.1高級、中級和低級調度1.高級調度(HighScheduling)(作業調度)

在每次執行作業調度時，都須做出以下兩個決定。

1)接納多少個作業

2)接納哪些作業2.低級調度(LowLevelScheduling)（進程調度）

1)非搶占方式(Non-preemptiveMode)

在采用非搶占調度方式時，可能引起進程調度的因素可歸結為這樣幾個：①正在執行的進程執行完畢，或因發生某事件而不能再繼續執行；②執行中的進程因提出I/O請求而暫停執行；③在進程通信或同步過程中執行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調度方式的優點是實現簡單、系統開銷小，適用于大多數的批處理系統環境。但它難以滿足緊急任務的要求——立即執行，因而可能造成難以預料的后果。顯然，在要求比較嚴格的實時系統中，不宜采用這種調度方式。2)搶占方式(PreemptiveMode)搶占的原則有：優先權原則。(2)短作業(進程)優先原則。(3)時間片原則。3.中級調度(Intermediate-LevelScheduling)

中級調度又稱中程調度(Medium-TermScheduling)。引入中級調度的主要目的，是為了提高內存利用率和系統吞吐量。為此，應使那些暫時不能運行的進程不再占用寶貴的內存資源，而將它們調至外存上去等待，把此時的進程狀態稱為就緒駐外存狀態或掛起狀態。當這些進程重又具備運行條件、且內存又稍有空閑時，由中級調度來決定把外存上的哪些又具備運行條件的就緒進程，重新調入內存，并修改其狀態為就緒狀態，掛在就緒隊列上等待進程調度。3.1.2調度隊列模型1.僅有進程調度的調度隊列模型圖3-1僅具有進程調度的調度隊列模型2.具有高級和低級調度的調度隊列模型圖3-2具有高、低兩級調度的調度隊列模型就緒隊列的形式。

(2)設置多個阻塞隊列。

圖3-2示出了具有高、低兩級調度的調度隊列模型。該模型與上一模型的主要區別在于如下兩個方面。3.同時具有三級調度的調度隊列模型圖3-3具有三級調度時的調度隊列模型3.1.3選擇調度方式和調度算法的若干準則1.面向用戶的準則(1)周轉時間短。

可把平均周轉時間描述為：作業的周轉時間T與系統為它提供服務的時間TS之比，即W=T/TS，稱為帶權周轉時間，而平均帶權周轉時間則可表示為:(2)響應時間快。(3)截止時間的保證。(4)優先權準則。2.面向系統的準則系統吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。3.2調度算法3.2.1先來先服務和短作業(進程)優先調度算法1.先來先服務調度算法圖3-4FCFS和SJF調度算法的性能2.短作業(進程)優先調度算法

短作業(進程)優先調度算法SJ(P)F，是指對短作業或短進程優先調度的算法。它們可以分別用于作業調度和進程調度。短作業優先(SJF)的調度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機時，再重新調度。SJ(P)F調度算法也存在不容忽視的缺點：

(1)該算法對長作業不利，如作業C的周轉時間由10增至16，其帶權周轉時間由2增至3.1。更嚴重的是，如果有一長作業(進程)進入系統的后備隊列(就緒隊列)，由于調度程序總是優先調度那些(即使是后進來的)短作業(進程)，將導致長作業(進程)長期不被調度。

(2)該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業(進程)會被及時處理。

(3)由于作業(進程)的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。3.2.2高優先權優先調度算法1.優先權調度算法的類型非搶占式優先權算法

在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程后，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用于批處理系統中；也可用于某些對實時性要求不嚴的實時系統中。2)搶占式優先權調度算法在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在采用這種調度算法時，是每當系統中出現一個新的就緒進程i時，就將其優先權Pi與正在執行的進程j的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi＞Pj,則立即停止Pj的執行，做進程切換，使i進程投入執行。顯然，這種搶占式的優先權調度算法，能更好地滿足緊迫作業的要求，故而常用于要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。2.優先權的類型1)靜態優先權靜態優先權是在創建進程時確定的，且在進程的整個運行期間保持不變。一般地，優先權是利用某一范圍內的一個整數來表示的，例如，0~7或0~255中的某一整數，又把該整數稱為優先數。只是具體用法各異：有的系統用“0”表示最高優先權，當數值愈大時，其優先權愈低；而有的系統恰恰相反。確定進程優先權的依據有如下三個方面：進程類型。(2)進程對資源的需求。(3)用戶要求。2)動態優先權動態優先權是指，在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以速率a提高。若所有的進程都具有相同的優先權初值，則顯然是最先進入就緒隊列的進程，將因其動態優先權變得最高而優先獲得處理機，此即FCFS算法。若所有的就緒進程具有各不相同的優先權初值，那么，對于優先權初值低的進程，在等待了足夠的時間后，其優先權便可能升為最高，從而可以獲得處理機。當采用搶占式優先權調度算法時，如果再規定當前進程的優先權以速率b下降，則可防止一個長作業長期地壟斷處理機。3.高響應比優先調度算法優先權的變化規律可描述為：由于等待時間與服務時間之和，就是系統對該作業的響應時間，故該優先權又相當于響應比RP。據此，又可表示為：(1)如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業。

(2)當要求服務的時間相同時，作業的優先權決定于其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。

(3)對于長作業，作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機。3.2.3基于時間片的輪轉調度算法1.時間片輪轉法在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則，排成一個隊列，每次調度時，把CPU分配給隊首進程，并令其執行一個時間片。時間片的大小從幾ms到幾百ms。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程序便據此信號來停止該進程的執行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內，均能獲得一時間片的處理機執行時間。2.多級反饋隊列調度算法(1)應設置多個就緒隊列，并為各個隊列賦予不同的優先級。第一個隊列的優先級最高，第二個隊列次之，其余各隊列的優先權逐個降低。該算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。圖3-5是多級反饋隊列算法的示意。圖3-5多級反饋隊列調度算法(2)當一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉的方式運行。(3)僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1~(i-1)隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1~(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。3.多級反饋隊列調度算法的性能終端型作業用戶。(2)短批處理作業用戶。(3)長批處理作業用戶。

3.3進程調度

進程調度是OS中必不可少的一種調度。因此在三種類型的OS中，都無一例外地配置了進程調度。此外它也是對系統性能影響最大的一種處理機調度，相應的，有關進程調度的算法也較多。3.3.1進程調度的任務、機制和方式

1.進程調度的任務

進程調度的任務主要有三：

(1)保存處理機的現場信息。

(2)按某種算法選取進程。

(3)把處理器分配給進程。

2.進程調度機制

為了實現進程調度，在進程調度機制中，應具有如下三個基本部分，如圖3-1所示。

(1)排隊器。

(2)分派器。

(3)上下文切換器。圖3-1進程調度機制

3.進程調度方式

1)非搶占方式(NonpreemptiveMode)

在采用這種調度方式時，一旦把處理機分配給某進程后，就一直讓它運行下去，決不會因為時鐘中斷或任何其它原因去搶占當前正在運行進程的處理機，直至該進程完成，或發生某事件而被阻塞時，才把處理機分配給其它進程。

2)搶占方式(PreemptiveMode)

這種調度方式允許調度程序根據某種原則，去暫停某個正在執行的進程，將已分配給該進程的處理機重新分配給另一進程。在現代OS中廣泛采用搶占方式，這是因為：對于批處理機系統，可以防止一個長進程長時間地占用處理機，以確保處理機能為所有進程提供更為公平的服務。在分時系統中，只有采用搶占方式才有可能實現人—機交互。在實時系統中，搶占方式能滿足實時任務的需求。但搶占方式比較復雜，所需付出的系統開銷也較大。3.3.2輪轉調度算法

1.輪轉法的基本原理

在輪轉(RR)法中，系統將所有的就緒進程按FCFS策略排成一個就緒隊列。系統可設置每隔一定時間(如30?ms)便產生一次中斷，去激活進程調度程序進行調度，把CPU分配給隊首進程，并令其執行一個時間片。當它運行完畢后，又把處理機分配給就緒隊列中新的隊首進程，也讓它執行一個時間片。這樣，就可以保證就緒隊列中的所有進程在確定的時間段內，都能獲得一個時間片的處理機時間。

2.進程切換時機

在RR調度算法中，應在何時進行進程的切換，可分為兩種情況：①若一個時間片尚未用完，正在運行的進程便已經完成，就立即激活調度程序，將它從就緒隊列中刪除，再調度就緒隊列中隊首的進程運行，并啟動一個新的時間片。②在一個時間片用完時，計時器中斷處理程序被激活。如果進程尚未運行完畢，調度程序將把它送往就緒隊列的末尾。

3.時間片大小的確定

在輪轉算法中，時間片的大小對系統性能有很大的

影響。

圖3-2示出了時間片大小對響應時間的影響，其中圖(a)是時間片略大于典型交互的時間，而圖(b)是時間片小于典型交互的時間。圖3-3示出了時間片分別為q?=?1和q?=?4時對平均周轉時間的影響。圖3-2時間片大小對響應時間的影響圖3-3q?=?1和q?=?4時進程的周轉時間3.3.3優先級調度算法

1.優先級調度算法的類型

優先級進程調度算法，是把處理機分配給就緒隊列中優先級最高的進程。這時，又可進一步把該算法分成如下兩種。

(1)非搶占式優先級調度算法。

(2)搶占式優先級調度算法。

2.優先級的類型

1)靜態優先級

靜態優先級是在創建進程時確定的，在進程的整個運行期間保持不變。優先級是利用某一范圍內的一個整數來表示的，例如0～255中的某一整數，又把該整數稱為優先數。確定進程優先級大小的依據有如下三個：

(1)進程類型。

(2)進程對資源的需求。

(3)用戶要求。

2)動態優先級

動態優先級是指在創建進程之初，先賦予其一個優先級，然后其值隨進程的推進或等待時間的增加而改變，以便獲得更好的調度性能。3.3.4多隊列調度算法

如前所述的各種調度算法，尤其在應用于進程調度時，由于系統中僅設置一個進程的就緒隊列，即低級調度算法是固定的、單一的，無法滿足系統中不同用戶對進程調度策略的不同要求，在多處理機系統中，這種單一調度策略實現機制的缺點更顯突出，由此，多級隊列調度算法能夠在一定程度上彌補這一缺點。3.3.5多級反饋隊列(multilevedfeedbackqueue)調度算法

1.調度機制

多級反饋隊列調度算法的調度機制可描述如下：

(1)設置多個就緒隊列。

圖3-4是多級反饋隊列算法的示意圖。圖3-4多級反饋隊列調度算法

(2)每個隊列都采用FCFS算法。當新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可撤離系統。否則，即它在一個時間片結束時尚未完成，調度程序將其轉入第二隊列的末尾等待調度；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，依此類推。當進程最后被降到第n隊列后，在第n隊列中便采取按RR方式運行。

(3)按隊列優先級調度。調度程序首先調度最高優先級隊列中的諸進程運行，僅當第一隊列空閑時才調度第二隊列中的進程運行；換言之，僅當第1～(i-1)所有隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時又有新進程進入任一優先級較高的隊列，此時須立即把正在運行的進程放回到第i隊列的末尾，而把處理機分配給新到的高優先級進程。

2.調度算法的性能

在多級反饋隊列調度算法中，如果規定第一個隊列的時間片略大于多數人機交互所需之處理時間時，便能較好地滿足各種類型用戶的需要。

(1)終端型用戶。

(2)短批處理作業用戶。

(3)長批處理作業用戶。3.3.6基于公平原則的調度算法

1.保證調度算法

保證調度算法是另外一種類型的調度算法，它向用戶所做出的保證并不是優先運行，而是明確的性能保證，該算法可以做到調度的公平性。一種比較容易實現的性能保證是處理機分配的公平性。如果在系統中有n個相同類型的進程同時運行，為公平起見，須保證每個進程都獲得相同的處理機時間1/n。在實施公平調度算法時系統中必須具有這樣一些功能：

(1)跟蹤計算每個進程自創建以來已經執行的處理時間。

(2)計算每個進程應獲得的處理機時間，即自創建以來的時間除以n。

(3)計算進程獲得處理機時間的比率，即進程實際執行的處理時間和應獲得的處理機時間之比。

(4)比較各進程獲得處理機時間的比率。如進程A的比率最低，為0.5，而進程B的比率為0.8，進程C的比率為1.2等。

(5)調度程序應選擇比率最小的進程將處理機分配給它，并讓該進程一直運行，直到超過最接近它的進程比率為止。

2.公平分享調度算法

分配給每個進程相同的處理機時間，顯然，這對諸進程而言，是體現了一定程度的公平，但如果各個用戶所擁有的進程數不同，就會發生對用戶的不公平問題。3.3實時調度3.3.1實現實時調度的基本條件1.提供必要的信息就緒時間。(2)開始截止時間和完成截止時間。(3)處理時間。(4)資源要求。(5)優先級。2.系統處理能力強

在實時系統中，通常都有著多個實時任務。若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務不能得到及時處理，從而導致發生難以預料的后果。假定系統中有m個周期性的硬實時任務，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件：

系統才是可調度的。假如系統中有6個硬實時任務，它們的周期時間都是50ms，而每次的處理時間為10ms，則不難算出，此時是不能滿足上式的，因而系統是不可調度的。解決的方法是提高系統的處理能力，其途徑有二：其一仍是采用單處理機系統，但須增強其處理能力，以顯著地減少對每一個任務的處理時間；其二是采用多處理機系統。假定系統中的處理機數為N，則應將上述的限制條件改為：3.采用搶占式調度機制

當一個優先權更高的任務到達時，允許將當前任務暫時掛起，而令高優先權任務立即投入運行，這樣便可滿足該硬實時任務對截止時間的要求。但這種調度機制比較復雜。對于一些小的實時系統，如果能預知任務的開始截止時間，則對實時任務的調度可采用非搶占調度機制，以簡化調度程序和對任務調度時所花費的系統開銷。但在設計這種調度機制時，應使所有的實時任務都比較小，并在執行完關鍵性程序和臨界區后，能及時地將自己阻塞起來，以便釋放出處理機，供調度程序去調度那種開始截止時間即將到達的任務。4.具有快速切換機制

該機制應具有如下兩方面的能力：

(1)對外部中斷的快速響應能力。為使在緊迫的外部事件請求中斷時系統能及時響應，要求系統具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務)。

(2)快速的任務分派能力。在完成任務調度后，便應進行任務切換。為了提高分派程序進行任務切換時的速度，應使系統中的每個運行功能單位適當的小，以減少任務切換的時間開銷。3.3.2實時調度算法的分類1.非搶占式調度算法非搶占式輪轉調度算法。(2)非搶占式優先調度算法。2.搶占式調度算法基于時鐘中斷的搶占式優先權調度算法。(2)立即搶占(ImmediatePreemption)的優先權調度算法。圖3-6實時進程調度3.3.3常用的幾種實時調度算法1.最早截止時間優先即EDF(EarliestDeadlineFirst)算法圖3-7EDF算法用于非搶占調度方式2.最低松弛度優先即LLF(LeastLaxityFirst)算法

該算法是根據任務緊急(或松弛)的程度，來確定任務的優先級。任務的緊急程度愈高，為該任務所賦予的優先級就愈高，以使之優先執行。例如，一個任務在200ms時必須完成，而它本身所需的運行時間就有100ms，因此，調度程序必須在100ms之前調度執行，該任務的緊急程度(松弛程度)為100ms。又如，另一任務在400ms時必須完成，它本身需要運行150ms，則其松弛程度為250ms。在實現該算法時要求系統中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的任務排在隊列最前面，調度程序總是選擇就緒隊列中的隊首任務執行。該算法主要用于可搶占調度方式中。假如在一個實時系統中，有兩個周期性實時任務A和B，任務A要求每20ms執行一次，執行時間為10ms；任務B只要求每50ms執行一次，執行時間為25ms。圖3-8A和B任務每次必須完成的時間

在剛開始時(t1=0)，A1必須在20ms時完成，而它本身運行又需10ms，可算出A1的松弛度為10ms；B1必須在50ms時完成，而它本身運行就需25ms，可算出B1的松弛度為25ms，故調度程序應先調度A1執行。在t2=10ms時，A2的松弛度可按下式算出：A2的松弛度=必須完成時間-其本身的運行時間-當前時間

=40ms-10ms-10ms=20ms

類似地，可算出B1的松弛度為15ms，故調度程序應選擇B2運行。在t3=30ms時，A2的松弛度已減為0(即40-10-30)，而B1的松弛度為15ms(即50-5-30)，于是調度程序應搶占B1的處理機而調度A2運行。在t4=40ms時，A3的松弛度為10ms(即60-10-40)，而B1的松弛度僅為5ms(即50-5-40)，故又應重新調度B1執行。在t5=45ms時，B1執行完成，而此時A3的松弛度已減為5ms(即60-10-45)，而B2的松弛度為30ms(即100-25-45)，于是又應調度A3執行。在t6=55ms時，任務A尚未進入第4周期，而任務B已進入第2周期，故再調度B2執行。在t7=70ms時，A4的松弛度已減至0ms(即80-10-70)，而B2的松弛度為20ms(即100-10-70)，故此時調度又應搶占B2的處理機而調度A4執行。圖3-9利用ELLF算法進行調度的情況3.4多處理機系統中的調度3.4.1多處理器系統的類型(1)緊密耦合(TightlyCoupted)MPS。這通常是通過高速總線或高速交叉開關，來實現多個處理器之間的互連的。它們共享主存儲器系統和I/O設備，并要求將主存儲器劃分為若干個能獨立訪問的存儲器模塊，以便多個處理機能同時對主存進行訪問。系統中的所有資源和進程，都由操作系統實施統一的控制和管理。(2)松散耦合(LooselyCoupled)MPS。在松散耦合MPS中，通常是通過通道或通信線路，來實現多臺計算機之間的互連。每臺計算機都有自己的存儲器和I/O設備，并配置了OS來管理本地資源和在本地運行的進程。因此，每一臺計算機都能獨立地工作，必要時可通過通信線路與其它計算機交換信息，以及協調它們之間的工作。2.對稱多處理器系統和非對稱多處理器系統(1)對稱多處理器系統SMPS(SymmetricMultiProcessorSystem)。在系統中所包含的各處理器單元，在功能和結構上都是相同的，當前的絕大多數MPS都屬于SMP系統。例如，IBM公司的SR/6000ModelF50,便是利用4片PowerPC處理器構成的。

(2)非對稱多處理器系統。在系統中有多種類型的處理單元，它們的功能和結構各不相同，其中只有一個主處理器，有多個從處理器。3.4.2進程分配方式1.對稱多處理器系統中的進程分配方式在SMP系統中，所有的處理器都是相同的，因而可把所有的處理器作為一個處理器池(Processorpool)，由調度程序或基于處理器的請求，將任何一個進程分配給池中的任何一個處理器去處理。在進行進程分配時，可采用以下兩種方式之一。

1)靜態分配(StaticAssigenment)方式

2)動態分配(DynamicAssgement)方式2.非對稱MPS中的進程分配方式對于非對稱MPS，其OS大多采用主—從(Master-Slave)式OS，即OS的核心部分駐留在一臺主機上(Master)，而從機(Slave)上只是用戶程序，進程調度只由主機執行。每當從機空閑時，便向主機發送一索求進程的信號，然后，便等待主機為它分配進程。在主機中保持有一個就緒隊列，只要就緒隊列不空，主機便從其隊首摘下一進程分配給請求的從機。從機接收到分配的進程后便運行該進程，該進程結束后從機又向主機發出請求。3.4.3進程(線程)調度方式

1.自調度(Self-Scheduling)方式

1)自調度機制在多處理器系統中，自調度方式是最簡單的一種調度方式。它是直接由單處理機環境下的調度方式演變而來的。在系統中設置有一個公共的進程或線程就緒隊列，所有的處理器在空閑時，都可自己到該隊列中取得一進程(或線程)來運行。在自調度方式中，可采用在單處理機環境下所用的調度算法，如先來先服務(FCFS)調度算法、最高優先權優先(FPF)調度算法和搶占式最高優先權優先調度算法等。2)自調度方式的優點自調度方式的主要優點表現為：首先，系統中的公共就緒隊列可按照單處理機系統中所采用的各種方式加以組織；其調度算法也可沿用單處理機系統所用的算法，亦即，很容易將單處理機環境下的調度機制移植到多處理機系統中，故它仍然是當前多處理機系統中較常用的調度方式。其次，只要系統中有任務，或者說只要公共就緒隊列不空，就不會出現處理機空閑的情況，也不會發生處理器忙閑不均的現象，因而有利于提高處理器的利用率。3)自調度方式的缺點瓶頸問題。(2)低效性。(3)線程切換頻繁。2.成組調度(GangScheduling)方式

在成組調度時，如何為應用程序分配處理器時間，

1)面向所有應用程序平均分配處理器時間

2)面向所有線程平均分配處理器時間圖3-10兩種分配處理器時間的方法3.專用處理器分配(DedicatedProcessorAssigement)方式圖3-11線程數對加速比的影響3.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因競爭資源。(2)進程間推進順序非法。1.競爭資源引起進程死鎖可剝奪和非剝奪性資源2)競爭非剝奪性資源3)競爭臨時性資源圖3-12I/O設備共享時的死鎖情況圖3-13進程之間通信時的死鎖2.進程推進順序不當引起死鎖1)進程推進順序合法圖3-14進程推進順序對死鎖的影響2)進程推進順序非法若并發進程P1和P2按曲線④所示的順序推進，它們將進入不安全區D內。此時P1保持了資源R1,P2保持了資源R2,系統處于不安全狀態。因為，這時兩進程再向前推進，便可能發生死鎖。例如，當P1運行到P1:Request(R2)時，將因R2已被P2占用而阻塞；當P2運行到P2:Request(R1)時，也將因R1已被P1占用而阻塞，于是發生了進程死鎖。3.5.2產生死鎖的必要條件互斥條件(2)請求和保持條件(3)不剝奪條件(4)環路等待條件3.5.3處理死鎖的基本方法預防死鎖。(2)避免死鎖。(3)檢測死鎖。(4)解除死鎖。3.6預防死鎖的方法3.6.1預防死鎖摒棄“請求和保持”條件2.摒棄“不剝奪”條件3.摒棄“環路等待”條件3.6.2系統安全狀態

1.安全狀態在避免死鎖的方法中，允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態，則將資源分配給進程；否則，令進程等待。所謂安全狀態，是指系統能按某種進程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。2.安全狀態之例我們通過一個例子來說明安全性。假定系統中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P3104952233.由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統把剩余3臺中的1臺分配給P3，則系統便進入不安全狀態。因為，此時也無法再找到一個安全序列，例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結果導致死鎖。3.6.3利用銀行家算法避免死鎖1.銀行家算法中的數據結構(1)可利用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果Available［j］=K，則表示系統中現有Rj類資源K個。(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max［i,j］=K，則表示進程i需要Rj類資源的最大數目為K。

(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation［i,j］=K，則表示進程i當前已分得Rj類資源的數目為K。

(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need［i,j］=K，則表示進程i還需要Rj類資源K個，方能完成其任務。Need［i,j］=Max［i,j］-Allocation［i,j］

2.銀行家算法設Requesti是進程Pi的請求向量，如果Requesti［j］=K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：

(1)如果Requesti［j］≤Need［i,j］，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。

(2)如果Requesti［j］≤Available［j］，便轉向步驟(3)；否則，表示尚無足夠資源，Pi須等待。(3)系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值：

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。3.安全性算法(1)設置兩個向量：①工作向量Work:它表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work∶=Available;②Finish:它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］∶=false;當有足夠資源分配給進程時，再令Finish［i］∶=true。(2)從進程集合中找到一個能滿足下述條件的進程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執行步驟(3)，否則，執行步驟(4)。

(3)當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：

Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;(4)如果所有進程的Finish［i］=true都滿足，則表示系統處于安全狀態；否則，系統處于不安全狀態。4.銀行家算法之例

假定系統中有五個進程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表(1)T0時刻的安全性：圖3-16T0時刻的安全序列(2)P1請求資源：P1發出請求向量Request1(1，0，2)，系統按銀行家算法進行檢查：①Request1(1,0,2)≤Need