第3章進(jìn)程調(diào)度與死鎖預(yù)防

第3章進(jìn)程調(diào)度與死鎖預(yù)防3.1作業(yè)的組織和管理3.2作業(yè)控制方式3.3進(jìn)程調(diào)度3.4死鎖的基本概念

3.5產(chǎn)生死鎖的示例3.6解決死鎖的方案3.7其他相關(guān)問(wèn)題習(xí)題3.1作業(yè)的組織和管理3.1.1作業(yè)和作業(yè)處理過(guò)程1.作業(yè)的概念作業(yè)是用戶在一次算題過(guò)程中或一個(gè)事務(wù)處理過(guò)程中要求計(jì)算機(jī)系統(tǒng)所做工作的總和，它是用戶向計(jì)算機(jī)系統(tǒng)提交一項(xiàng)工作的基本單位。作業(yè)與作業(yè)步的概念編輯(輸入、修改)源程序編譯連接運(yùn)行成功？否否編輯(輸入、修改)另一源程序……job1job2該作業(yè)的第一步該作業(yè)的第二步該作業(yè)的第三步該作業(yè)的第四步該作業(yè)的第一步……根據(jù)計(jì)算機(jī)系統(tǒng)作業(yè)處理方式的不同，通?？砂炎鳂I(yè)分為脫機(jī)作業(yè)和聯(lián)機(jī)作業(yè)兩大類：(1)脫機(jī)作業(yè)：是指用戶不能直接與計(jì)算機(jī)系統(tǒng)交互，中間需要通過(guò)操作員進(jìn)行控制和干預(yù)的作業(yè)。(2)聯(lián)機(jī)作業(yè)：用戶能夠直接與計(jì)算機(jī)系統(tǒng)交互作用，所以聯(lián)機(jī)作業(yè)也稱為交互型作業(yè)、終端作業(yè)或者前臺(tái)作業(yè)。用戶向操作系統(tǒng)提供作業(yè)加工步驟的方式稱為作業(yè)控制方式。根據(jù)作業(yè)類型的不同，可以把作業(yè)控制方式分為兩種：(1)脫機(jī)作業(yè)控制方式(也稱為作業(yè)自動(dòng)控制方式)：即用戶把作業(yè)執(zhí)行的目的連同程序和數(shù)據(jù)及故障處理措施一起輸入到系統(tǒng)中，由系統(tǒng)根據(jù)該目的來(lái)控制作業(yè)執(zhí)行的全過(guò)程。(2)聯(lián)機(jī)作業(yè)控制方式(也稱作業(yè)直接控制方式)：采用人機(jī)對(duì)話的方式來(lái)控制作業(yè)的運(yùn)行。2.作業(yè)的組成作業(yè)由程序、數(shù)據(jù)和作業(yè)控制信息(如作業(yè)說(shuō)明書(shū))三部分組成。作業(yè)控制信息包括作業(yè)基本情況、作業(yè)控制和作業(yè)資源要求的描述，它體現(xiàn)用戶對(duì)作業(yè)控制的意圖。在批處理系統(tǒng)中，用戶不能直接與自己的作業(yè)交互作用，只能委托系統(tǒng)代替用戶進(jìn)行控制和干預(yù).作業(yè)說(shuō)明書(shū)包括三方面的內(nèi)容:(1)作業(yè)基本情況：包括用戶名、作業(yè)名、編程語(yǔ)言、最大處理時(shí)間等。(2)作業(yè)控制描述：包括作業(yè)控制方式、作業(yè)步的操作順序、作業(yè)執(zhí)行出錯(cuò)處理。(3)作業(yè)資源要求描述：包括處理時(shí)間、優(yōu)先級(jí)、內(nèi)存空間、外設(shè)類型和數(shù)量、實(shí)用程序要求等。3.作業(yè)的處理過(guò)程一個(gè)作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般需要經(jīng)歷“輸入”、“后備”、“執(zhí)行”和“完成”4個(gè)階段，相應(yīng)地，稱作業(yè)處于輸入、后備、執(zhí)行和完成4個(gè)不同的狀態(tài)。

(1)輸入狀態(tài)。又稱為提交或錄入，是指用戶將自己的程序和數(shù)據(jù)提交給系統(tǒng)的后援存儲(chǔ)器。

(2)后備狀態(tài)。在作業(yè)的輸入階段，操作員將用戶提交的作業(yè)通過(guò)脫機(jī)輸入或調(diào)用SPOOLing系統(tǒng)輸入過(guò)程，將作業(yè)輸入到直接存取的后援存儲(chǔ)器，然后由“作業(yè)注冊(cè)”程序負(fù)責(zé)為進(jìn)入系統(tǒng)的作業(yè)建立作業(yè)控制塊，并把它加入到后備作業(yè)隊(duì)列中，等待作業(yè)調(diào)度程序調(diào)度，這時(shí)作業(yè)處于后備狀態(tài)。

(3)執(zhí)行狀態(tài)。一個(gè)作業(yè)被作業(yè)調(diào)度程序選中并分配了必要的資源，建立了一組相應(yīng)的進(jìn)程后，該作業(yè)就進(jìn)入了執(zhí)行狀態(tài)。

(4)完成狀態(tài)。當(dāng)作業(yè)正常運(yùn)行結(jié)束或因發(fā)生錯(cuò)誤而終止時(shí)，作業(yè)進(jìn)入完成狀態(tài)，退出系統(tǒng)。作業(yè)退出的工作流程如下所述：

把輸出結(jié)果送到輸出設(shè)備上(啟動(dòng)緩輸出進(jìn)程完成)。

回收各種資源。

緩輸出進(jìn)程(脫機(jī))。

從輸出井上將結(jié)果輸出。作業(yè)狀態(tài)轉(zhuǎn)換過(guò)程如圖3.1所示。圖3.1批處理系統(tǒng)中的作業(yè)處理及狀態(tài)3.1.2作業(yè)的輸入/輸出方式

1．聯(lián)機(jī)輸入/輸出該方式由主機(jī)直接控制輸入/輸出。由于主機(jī)和外圍設(shè)備的速度相差懸殊，因而這種方式降低了CPU的利用率。2.脫機(jī)輸入/輸出(人工干預(yù))由于主機(jī)和外圍設(shè)備的速度相差懸殊，早期的輸入/輸出采用脫機(jī)外圍設(shè)備解決這一問(wèn)題。專門設(shè)置一臺(tái)衛(wèi)星機(jī)(或稱外圍處理機(jī))負(fù)責(zé)輸入/輸出，利用外圍處理機(jī)把作業(yè)先輸入到輔助存儲(chǔ)器上(如磁盤，磁帶)，然后再通過(guò)輔助存儲(chǔ)器與主機(jī)相連。3．SPOOLing系統(tǒng)一般的輸入/輸出設(shè)備都是獨(dú)享設(shè)備并屬于慢速設(shè)備，因此，當(dāng)一個(gè)作業(yè)使用這類設(shè)備進(jìn)行一次較大量的數(shù)據(jù)交換時(shí)，其他需要同時(shí)訪問(wèn)該設(shè)備的作業(yè)就要等待較長(zhǎng)時(shí)間，從而降低了整個(gè)系統(tǒng)的并發(fā)能力。SPOOLing技術(shù)正是針對(duì)上述問(wèn)題提出的一種設(shè)備管理技術(shù)。3.1.3作業(yè)控制塊1．作業(yè)控制塊在多道批處理系統(tǒng)中通常有上百個(gè)作業(yè)被收容在輸入井(磁盤)中。為了管理和調(diào)度作業(yè)，每個(gè)作業(yè)進(jìn)入系統(tǒng)時(shí)，系統(tǒng)會(huì)自動(dòng)為其建立作業(yè)控制塊(JobControlBlock，JCB)，用來(lái)存放管理和控制作業(yè)所必需的信息。每個(gè)JCB的具體內(nèi)容根據(jù)作業(yè)調(diào)度的要求而定，它包括該作業(yè)的標(biāo)識(shí)信息、狀態(tài)信息、調(diào)度參數(shù)、資源需求和其他控制信息等，如：(1)作業(yè)名。(2)用戶名及用戶賬號(hào)。(3)內(nèi)存需求量。(4)估計(jì)執(zhí)行時(shí)間。 (5)優(yōu)先數(shù)(用于調(diào)度)。 (6)作業(yè)類型。 (7)作業(yè)說(shuō)明書(shū)文件名。 (8)資源要求量。 (9)作業(yè)狀態(tài)(提交、后備、執(zhí)行、就緒、等待、完成)。 (10)作業(yè)的存儲(chǔ)信息：包括輸入井地址和輸出井地址。

2.作業(yè)后備隊(duì)列作業(yè)建立完成后，形成一個(gè)“后備作業(yè)”。輸入井中存在著許多后備作業(yè)，為了調(diào)度程序能夠方便地工作，通常按照某種原則將這些后備作業(yè)的JCB排成一個(gè)或多個(gè)序列，形成作業(yè)后備隊(duì)列。圖3.3三種調(diào)度3.1.4作業(yè)調(diào)度在一些操作系統(tǒng)中，一個(gè)作業(yè)從提交到完成需要經(jīng)過(guò)高級(jí)、中級(jí)和低級(jí)三級(jí)調(diào)度，見(jiàn)圖3.3。高/中/低級(jí)調(diào)度高級(jí)調(diào)度（作業(yè)調(diào)度）決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備執(zhí)行。低級(jí)調(diào)度（進(jìn)程調(diào)度）決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。非搶占方式和搶占方式中級(jí)調(diào)度決定把又具備運(yùn)行條件的掛起進(jìn)程重新調(diào)入內(nèi)存，掛到就緒隊(duì)列上，準(zhǔn)備執(zhí)行。調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完交互用戶進(jìn)程調(diào)度進(jìn)程完成等待事件事件發(fā)生……具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成等待事件1阻塞隊(duì)列阻塞隊(duì)列等待事件2等待事件n事件1發(fā)生事件2發(fā)生事件n發(fā)生后備隊(duì)列

具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)阻塞隊(duì)列掛起等待事件中級(jí)調(diào)度事件發(fā)生后備隊(duì)列塞阻、掛起隊(duì)列掛起1.作業(yè)調(diào)度算法的評(píng)價(jià)因素作業(yè)調(diào)度又稱為高級(jí)調(diào)度或宏觀調(diào)度，它根據(jù)系統(tǒng)的情況和作業(yè)調(diào)度策略，將一些作業(yè)置為執(zhí)行狀態(tài)。作業(yè)調(diào)度按照某種算法把后備狀態(tài)作業(yè)中的一個(gè)或一批作業(yè)調(diào)到主機(jī)上運(yùn)行。(1)?CPU利用率。希望獲得較高的CPU的利用率。CPU的利用率可從0％～100％。在實(shí)際的系統(tǒng)中，一般CPU的利用率從40％(輕負(fù)荷系統(tǒng))～90％(重負(fù)荷系統(tǒng))。(2)吞吐量。它表示單位時(shí)間內(nèi)CPU完成作業(yè)的數(shù)量。(3)周轉(zhuǎn)時(shí)間。通常把周轉(zhuǎn)時(shí)間或周轉(zhuǎn)系數(shù)作為評(píng)價(jià)批處理系統(tǒng)的性能指標(biāo)，下面給出它們的定義。設(shè)作業(yè)Ji(i=1,2,…,n)的提交時(shí)間為tsi，執(zhí)行時(shí)間為tri，作業(yè)完成時(shí)間為toi，則作業(yè)Ji的周轉(zhuǎn)時(shí)間Ti和周轉(zhuǎn)系數(shù)Wi可定義為Ti=toi-tsi,i=1,2,…,nWi=Ti/tri,i=1,2,…,nn個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T和平均周轉(zhuǎn)系數(shù)W分別定義為帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間3.如何選擇調(diào)度算法選擇調(diào)度算法的依據(jù)：(1)選擇的調(diào)度算法應(yīng)與系統(tǒng)的整個(gè)設(shè)計(jì)目標(biāo)一致。(2)注意系統(tǒng)資源的均衡搭配使用，使“I/O繁忙”的作業(yè)和“CPU繁忙”的作業(yè)搭配起來(lái)執(zhí)行。(3)平衡系統(tǒng)和用戶的要求。3.作業(yè)調(diào)度算法1)單道批處理系統(tǒng)的作業(yè)調(diào)度算法對(duì)于單道批處理系統(tǒng)，常用的作業(yè)調(diào)度算法有：(1)先來(lái)先服務(wù)調(diào)度算法(FCFS)。先來(lái)先服務(wù)調(diào)度算法是一種比較簡(jiǎn)單的調(diào)度算法。(2)短作業(yè)優(yōu)先調(diào)度算法(SJF)。短作業(yè)優(yōu)先調(diào)度算法是指對(duì)短作業(yè)優(yōu)先調(diào)度的算法，作業(yè)控制塊按照作業(yè)的估計(jì)運(yùn)行時(shí)間串成作業(yè)隊(duì)列，每次調(diào)度時(shí)從后備作業(yè)隊(duì)列中選擇隊(duì)首的一個(gè)作業(yè)。(3)最高響應(yīng)比優(yōu)先調(diào)度算法(HRP)。在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一個(gè)比較好的算法。其主要的缺點(diǎn)是長(zhǎng)作業(yè)的運(yùn)行得不到保證。如果能為每個(gè)作業(yè)設(shè)置一個(gè)優(yōu)先權(quán)，并使它以速率a增加，則長(zhǎng)作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。該優(yōu)先權(quán)的變化可描述為優(yōu)先權(quán)=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間由于等待時(shí)間加上要求服務(wù)時(shí)間就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP，因此可表示為RP==

2)多道批處理系統(tǒng)的作業(yè)調(diào)度算法在多道批處理系統(tǒng)中，為提高處理機(jī)的利用率，改善主存和I/O設(shè)備的利用情況，作業(yè)調(diào)度程序可以選擇多個(gè)作業(yè)同時(shí)執(zhí)行。在多道批處理系統(tǒng)中，通常采用以下兩種作業(yè)調(diào)度算法：(1)優(yōu)先級(jí)調(diào)度算法。在多道批處理系統(tǒng)中，為了照顧時(shí)間緊迫的作業(yè)或“I/O繁忙”的作業(yè)，可根據(jù)下述方法設(shè)置作業(yè)優(yōu)先級(jí)，并根據(jù)優(yōu)先級(jí)進(jìn)行作業(yè)調(diào)度：

時(shí)間要求緊迫的作業(yè)獲得高優(yōu)先級(jí)?！癐/O繁忙”的作業(yè)獲得高優(yōu)先級(jí)，以便充分發(fā)揮外設(shè)的效率。

在一個(gè)兼顧分時(shí)操作和批處理的系統(tǒng)中，為了照顧終端會(huì)話型作業(yè)，給它以高優(yōu)先級(jí)，以便獲得合理的響應(yīng)時(shí)間。(2)均衡調(diào)度算法。這種算法的基本思想是根據(jù)系統(tǒng)的運(yùn)行情況和作業(yè)本身的特性對(duì)作業(yè)進(jìn)行分類。作業(yè)調(diào)度程序輪流地從這些不同類別的作業(yè)中挑選作業(yè)執(zhí)行。這種算法力求均衡地使用系統(tǒng)的各種資源，既注意發(fā)揮系統(tǒng)效率，又使用戶滿意。例如：把出現(xiàn)在輸入井中的作業(yè)分成A、B、C3類，每類作業(yè)再按照優(yōu)先級(jí)排成1個(gè)隊(duì)列：A隊(duì)：短作業(yè)隊(duì)列，作業(yè)計(jì)算時(shí)間小于一定值，無(wú)特殊外設(shè)要求。B隊(duì)：要用到磁帶的作業(yè)隊(duì)列，它們屬于I/O繁忙的作業(yè)。C隊(duì)：長(zhǎng)作業(yè)隊(duì)列，作業(yè)計(jì)算時(shí)間超過(guò)一定值。在作業(yè)調(diào)度時(shí)，從這3個(gè)作業(yè)隊(duì)列的隊(duì)首分別選擇1個(gè)作業(yè)調(diào)度執(zhí)行。3.作業(yè)調(diào)度算法的性能分析以上內(nèi)容使我們對(duì)調(diào)度算法有了理論上的了解，下面給出具體的例子來(lái)分析幾種算法的適用情況。

1)單道程序環(huán)境下作業(yè)調(diào)度性能的分析設(shè)有4個(gè)作業(yè)，它們的提交時(shí)刻、執(zhí)行時(shí)間如表3.1所示。作業(yè)提交時(shí)刻執(zhí)行時(shí)間18.002.0028.500.5039.000.1049.500.20(1)先來(lái)先服務(wù)調(diào)度算法。按照先來(lái)先服務(wù)思想，4個(gè)作業(yè)的執(zhí)行順序是1，2，3，4。計(jì)算該作業(yè)序列的平均周轉(zhuǎn)時(shí)間T和平均周轉(zhuǎn)系數(shù)W，如表3.2所示。表3.2計(jì)算T和W(先來(lái)先服務(wù)調(diào)度算法)作業(yè)提交時(shí)刻ts執(zhí)行時(shí)間tr/小時(shí)開(kāi)始時(shí)刻tls完成時(shí)刻to周轉(zhuǎn)時(shí)間Ti/小時(shí)周轉(zhuǎn)系數(shù)Wi18.002.008.0010.002.001.0028.500.5010.0010.502.004.0039.000.1010.5010.601.6016.0049.500.2010.6010.801.306.50平均周轉(zhuǎn)時(shí)間T=1.725小時(shí)平均周轉(zhuǎn)系數(shù)W=6.8756.9027.50(2)最短作業(yè)優(yōu)先調(diào)度算法。按最短作業(yè)優(yōu)先調(diào)度算法，該作業(yè)序列的執(zhí)行順序?yàn)?，3，4，2。由于在8.00開(kāi)始執(zhí)行作業(yè)，當(dāng)時(shí)僅有1，而作業(yè)2，3，4尚未到達(dá)，故作業(yè)1是最短作業(yè)。作業(yè)1執(zhí)行完成后是10.00，此時(shí)作業(yè)2，3，4均已經(jīng)到達(dá)，故選最短作業(yè)3，依此類推，平均周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)系數(shù)的計(jì)算結(jié)果如表3.3所示。表3.3計(jì)算T和W(最短作業(yè)優(yōu)先調(diào)度算法)作業(yè)提交時(shí)刻ts執(zhí)行時(shí)間tr/小時(shí)開(kāi)始時(shí)刻tls完成時(shí)刻to周轉(zhuǎn)時(shí)間Ti/小時(shí)周轉(zhuǎn)系數(shù)Wi18.002.008.0010.002.001.0028.500.5010.3010.802.303.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.803.00平均周轉(zhuǎn)時(shí)間T=1.55小時(shí)平均周轉(zhuǎn)系數(shù)W=5.156.2020.60(3)最高響應(yīng)比優(yōu)先調(diào)度算法。按最高響應(yīng)比優(yōu)先調(diào)度算法，該作業(yè)序列的執(zhí)行順序?yàn)?，3，2，4。當(dāng)作業(yè)1執(zhí)行完成時(shí)，計(jì)算作業(yè)2，3，4的響應(yīng)比分別為：4，11，3.5，因此，作業(yè)1執(zhí)行完成后選中作業(yè)3執(zhí)行。按此算法求得的平均周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)系數(shù)如表3.4所示。表3.4計(jì)算T和W(最高響應(yīng)比優(yōu)先調(diào)度算法)作業(yè)提交時(shí)刻ts執(zhí)行時(shí)間tr/小時(shí)開(kāi)始時(shí)刻tls完成時(shí)刻to周轉(zhuǎn)時(shí)間Ti/小時(shí)周轉(zhuǎn)系數(shù)Wi18.002.008.0010.002.001.0028.500.5010.1010.603.103.2039.000.1010.0010.101.1011.0049.500.2010.6010.801.306.50平均周轉(zhuǎn)時(shí)間T=1.625小時(shí)平均周轉(zhuǎn)系數(shù)W=5.6756.5023.722.(10-8.5+0.5)/0.53.(10-9+0.1)/0.14.(10-9.5+0.2)/0.2

2)多道程序環(huán)境下作業(yè)調(diào)度性能的分析有一個(gè)具有多道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)進(jìn)駐內(nèi)存后，采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，即作業(yè)運(yùn)行時(shí)間越短，其對(duì)應(yīng)產(chǎn)生的優(yōu)先數(shù)越大。如有4個(gè)作業(yè)序列，現(xiàn)已知它們的提交時(shí)刻和運(yùn)行時(shí)間如表3.5所示。表3.54個(gè)作業(yè)的提交時(shí)刻和運(yùn)行時(shí)間作業(yè)號(hào)提交時(shí)刻運(yùn)行時(shí)間/分鐘110:0030210:0520310:1020410:2010表3.6計(jì)

算

結(jié)

果作業(yè)提交時(shí)刻ts執(zhí)行時(shí)間tr/分鐘開(kāi)始時(shí)刻tls完成時(shí)刻to

周轉(zhuǎn)時(shí)間Ti/分鐘周轉(zhuǎn)系數(shù)Wi

110:003010:0011:20803.667210:052010:0510:25201310:102010:3510:55453.25410:201010:2510:35151.5平均周轉(zhuǎn)時(shí)間T=40分鐘平均周轉(zhuǎn)系數(shù)W=1.8541607.4173.2作業(yè)控制方式3.3.1脫機(jī)作業(yè)控制方式作業(yè)控制語(yǔ)言(JCL)是人們根據(jù)一個(gè)作業(yè)在運(yùn)行過(guò)程中所能遇到的各種情況及狀態(tài)改變，總結(jié)出的一種表達(dá)作業(yè)控制意圖和步驟的語(yǔ)言。JCL包括兩種類型的語(yǔ)句：①表達(dá)申請(qǐng)功能的說(shuō)明性語(yǔ)句；②作業(yè)控制和操作的執(zhí)行性語(yǔ)句。表3.7是一個(gè)151-1操作系統(tǒng)的簡(jiǎn)單作業(yè)控制說(shuō)明書(shū)，各語(yǔ)句含義解釋如下：表3.7151-1的作業(yè)控制說(shuō)明書(shū)標(biāo)號(hào)動(dòng)詞參數(shù)注釋

36JL:SQ:BY:ZR:QD:CL:CL:A102,ABCD,65,2500;KH1,GD2,CD3;ALGOL,A202,A203,36;A203;1.36;Y;W;(1)(2)(3)(4)(5)(6)(7)(1)作業(yè)名=A102，用戶名=ABCD，優(yōu)先級(jí)=65，內(nèi)存要求=2500，申請(qǐng)建立此作業(yè)。(2)申請(qǐng)外設(shè)資源：寬行打印機(jī)1臺(tái)，光電機(jī)2臺(tái)，磁帶機(jī)3臺(tái)。(3)編譯源文件A202。該文件使用ALGOL語(yǔ)言編寫，文件名A202經(jīng)過(guò)編譯后形成目標(biāo)文件A203。(4)編譯語(yǔ)句正確執(zhí)行后執(zhí)行該語(yǔ)句，把A203裝入該作業(yè)的內(nèi)存區(qū)中。(5)按啟動(dòng)點(diǎn)1啟動(dòng)A203運(yùn)行，在該程序出現(xiàn)各種事件時(shí)轉(zhuǎn)到標(biāo)號(hào)36的語(yǔ)句執(zhí)行撤離。(6)在A203運(yùn)行完畢時(shí)開(kāi)始執(zhí)行本語(yǔ)句，完成有條件撤離該作業(yè)。(7)該語(yǔ)句是編譯過(guò)程中或A203程序運(yùn)行過(guò)程中出現(xiàn)錯(cuò)誤時(shí)轉(zhuǎn)來(lái)的，無(wú)條件撤離該作業(yè)。3.3.2聯(lián)機(jī)作業(yè)控制方式1.MS-DOS的作業(yè)控制1)?DOS命令處理程序DOS的命令處理程序處于DOS的最外層，直接面向用戶。它駐留在內(nèi)存中，在系統(tǒng)運(yùn)行期間不再退出。(1)命令類型。DOS中的操作命令分成三類：內(nèi)部命令：隨裝入內(nèi)存，都集中在根目錄下的文件里。外部命令：以com和exe為后綴的文件，存在于外存中。批處理文件：由一組內(nèi)部命令或外部命令以及批處理命令組成的命令序列構(gòu)成的文件，類型名為.bat。(2)命令處理程序的組成。命令處理程序可分為三部分：非常駐部分：DOS在啟動(dòng)后會(huì)自動(dòng)運(yùn)行autoexec.bat這個(gè)文件，該文件是一個(gè)特殊的批處理文件，由若干個(gè)命令行組成，系統(tǒng)啟動(dòng)時(shí)執(zhí)行它，進(jìn)行一些處理。常駐部分：包括三個(gè)中斷處理子程序(終止地址INT22H、CTRL-BREAK處理INT23H和標(biāo)準(zhǔn)錯(cuò)誤處理INT24H)和一個(gè)恢復(fù)暫駐部分的程序。

暫駐部分：也稱覆蓋部分，這部分包括所有的內(nèi)部命令處理程序、批命令處理程序以及一個(gè)用來(lái)裝入并執(zhí)行外部命令的程序。2)命令處理舉例文件中存放著所有命令及執(zhí)行的入口地址，用戶輸入一個(gè)命令后，系統(tǒng)要進(jìn)行識(shí)別，找到相應(yīng)的處理程序，否則會(huì)提示用戶輸入的命令有誤，重新輸入。(1)內(nèi)部命令：直接由本身完成，功能簡(jiǎn)單，使用頻繁。例如dir，cd，copy。(2)外部命令：通過(guò)運(yùn)行相應(yīng)的可執(zhí)行文件來(lái)完成。(3)輸入/輸出重定向和管道：<，>，>>，|。“<”為輸入重定向。例如：findstring<temp.txt 將顯示文件temp.txt中有string串的行more<temp.txt 將逐屏顯示輸出文件temp.txt的內(nèi)容“>”為輸出重定向，“>>”為追加輸出重定向。例如：dir>temp.txt 將把dir命令在屏幕上的輸出保存在新文件temp.txt中dir>>temp.txt 將屏幕輸出追加在文件temp.txt的結(jié)尾

管道“|”是將前一個(gè)命令的屏幕輸出作為后一個(gè)命令的鍵盤輸入。例如：dir|sort 將把dir命令的輸出按行進(jìn)行排序3)DOS批處理

后綴是bat的文件就是批處理文件，它的作用就是把若干條要被多次重復(fù)使用的命令組織成一個(gè)文件，一次性的成批執(zhí)行。例如下面的批處理將顯示當(dāng)前目錄及其子目錄中所有的文件名(含路徑名)：echoofffor/R%%fin(*.*)doecho%%f3.UNIX的作業(yè)控制UNIX系統(tǒng)的典型作業(yè)就是一系列命令行，在命令行中可以是一些簡(jiǎn)單的命令、Shell腳本文件、以管道相連的命令等。這些命令擁有相同的作業(yè)ID。1)與作業(yè)控制有關(guān)的Shell命令UNIX系統(tǒng)提供的Shell本質(zhì)上是一個(gè)解釋程序，Shell命令一般具有以下幾個(gè)特性：(1)命令行。和DOS一樣，在UNIX命令中也有內(nèi)部命令和外部命令之分。(2)保留字。保留字是Shell程序中具有特殊意義的字符，如do，if，while等。(3)Shell變量。Shell變量是作為字符串存儲(chǔ)的，如PATH是保存命令執(zhí)行的搜索路徑，PWD是保存當(dāng)前工作目錄的絕對(duì)路徑名。在CShell中，變量賦值命令的基本格式是set[變量名[=變量值]]或set變量名=word變量的值可以用命令print或echo查看。(4)通配符。通配符是特殊的符號(hào)?！?”表示任意的或所有的字符，如hh*表示以hh開(kāi)頭的所有字符串，如果用來(lái)表示文件名則是指所有以hh開(kāi)頭的文件?！埃俊北硎疽粋€(gè)字符，如hh？表示以hh開(kāi)頭的所有三個(gè)字符的字符串，表示文件名則是指以hh開(kāi)頭的有三個(gè)字符的文件名。2)Shell腳本文件UNIX系統(tǒng)中的Shell腳本，類似于批處理的概念，是包含一個(gè)或多個(gè)Shell命令集合的文件。在需要執(zhí)行這些命令的時(shí)候，只需要輸入這個(gè)腳本的名字就可以了，不必再逐條輸入命令，簡(jiǎn)化了操作的過(guò)程。一般的Shell中指定解釋執(zhí)行腳本的程序都是以“#!/bin/sh”或“#!/opt/bin/perl”開(kāi)頭的。其中，perl是一個(gè)文本文件分析工具。在CShell中有三種方式運(yùn)行腳本：①為文件添加腳本的執(zhí)行權(quán)限；②運(yùn)行/bin/csh[腳本文件名]命令；③腳本文件以#!/bin/csh開(kāi)始，強(qiáng)制腳本在CShell中執(zhí)行，當(dāng)Shell讀到“#!”時(shí)，這一行的其他部分就是要執(zhí)行的Shell的絕對(duì)路徑，文件的腳本將在這個(gè)新的Shell中執(zhí)行。3)管道UNIX系統(tǒng)可以通過(guò)管道實(shí)現(xiàn)將一個(gè)命令的標(biāo)準(zhǔn)輸出連接到另一個(gè)命令的標(biāo)準(zhǔn)輸入上。管道是指通過(guò)使用“|”把一個(gè)命令或進(jìn)程的輸出作為另一個(gè)命令或進(jìn)程的輸入的方法。通過(guò)管道連接起來(lái)的命令稱為過(guò)濾器，它是一類UNIX命令。3.3進(jìn)程調(diào)度3.3.1確定進(jìn)程調(diào)度算法的原則正如前面講到的，引入多道程序設(shè)計(jì)的操作系統(tǒng)允許多個(gè)進(jìn)程同時(shí)進(jìn)入內(nèi)存，通過(guò)分時(shí)復(fù)用技術(shù)共享CPU。進(jìn)程調(diào)度的任務(wù)是：有效地選擇占用CPU的進(jìn)程，控制并協(xié)調(diào)系統(tǒng)安全、高效地工作。這就要求在設(shè)計(jì)算法時(shí)盡可能地安全、高效。面向系統(tǒng)性能應(yīng)注意：(1)公平性。每個(gè)進(jìn)程都有機(jī)會(huì)被運(yùn)行，即使是低優(yōu)先級(jí)的進(jìn)程也不例外。(2)較大的吞吐量。使每小時(shí)處理的作業(yè)數(shù)量最多，盡量讓CPU處于忙狀態(tài)，提高CPU的利用率。(3)平衡資源。面向用戶性能應(yīng)注意：(1)及時(shí)性。用戶最關(guān)心系統(tǒng)的響應(yīng)速度，應(yīng)盡可能使用戶覺(jué)得他的要求會(huì)及時(shí)得到滿足。(2)較短的周轉(zhuǎn)時(shí)間。尤其是批處理系統(tǒng)，從用戶提交到得到相應(yīng)的結(jié)果的時(shí)間不能過(guò)長(zhǎng)，使用戶感到滿意。（3）最后期限。3.3.2進(jìn)程調(diào)度算法針對(duì)以上原則，我們介紹幾種進(jìn)程調(diào)度算法。1．先進(jìn)先出進(jìn)程調(diào)度算法先進(jìn)先出法(FIFO)是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序進(jìn)行調(diào)度的算法。先到達(dá)的進(jìn)程先占用CPU，直到執(zhí)行結(jié)束或被迫等待才讓出CPU。2．基于優(yōu)先數(shù)的調(diào)度這種算法是讓每一個(gè)進(jìn)程都擁有一個(gè)優(yōu)先數(shù)，數(shù)值大的表示優(yōu)先級(jí)高，系統(tǒng)在調(diào)度時(shí)總選擇優(yōu)先數(shù)大的占用CPU。優(yōu)先數(shù)的確定方法有以下兩種：(1)靜態(tài)優(yōu)先數(shù)法：進(jìn)程創(chuàng)建時(shí)就規(guī)定好它的優(yōu)先數(shù)，這個(gè)數(shù)值在進(jìn)程運(yùn)行時(shí)不變。作業(yè)緊急程度、作業(yè)類型、申請(qǐng)資源情況(2)動(dòng)態(tài)優(yōu)先數(shù)法：克服靜態(tài)優(yōu)先數(shù)法中優(yōu)先數(shù)值不能改變的缺陷，動(dòng)態(tài)優(yōu)先數(shù)法使得進(jìn)程的優(yōu)先數(shù)在執(zhí)行過(guò)程中可以根據(jù)情況而改變。根據(jù)占用CPU時(shí)間長(zhǎng)短；跟進(jìn)在就緒隊(duì)列中等待CPU時(shí)間長(zhǎng)短；

動(dòng)態(tài)優(yōu)先數(shù)法：線性優(yōu)先級(jí)調(diào)度策略新創(chuàng)建的進(jìn)程按FCFS方式排成就緒隊(duì)列，優(yōu)先級(jí)以a的速率增加，正在執(zhí)行的進(jìn)程優(yōu)先級(jí)以b的速率改變。P(t)=a’(t1’-t1)+b’(t-t1’)進(jìn)程占用CPU的方式有以下兩種：(1)不可剝奪式：也稱不可搶占式(non-preemptive)，是指當(dāng)一個(gè)進(jìn)程被分配占用CPU后，就可以不被打斷執(zhí)行到結(jié)束。先進(jìn)先出法就屬于這種方式。(2)可剝奪式：也稱可搶占式(preemptive)，是指當(dāng)一個(gè)進(jìn)程被分配占用CPU的過(guò)程中出現(xiàn)了更高級(jí)的進(jìn)程請(qǐng)求時(shí)，當(dāng)前進(jìn)程必須讓出CPU。3.時(shí)間片輪轉(zhuǎn)程序調(diào)度算法時(shí)間片輪轉(zhuǎn)程序調(diào)度算法(RoundRobin，RR)簡(jiǎn)稱輪轉(zhuǎn)法，其基本思想是：系統(tǒng)規(guī)定一個(gè)時(shí)間長(zhǎng)度作為允許進(jìn)程運(yùn)行的時(shí)間，如果進(jìn)程在這段時(shí)間里沒(méi)有執(zhí)行完，它就必須讓出CPU，等待下一次分配時(shí)間片。時(shí)間就好像一個(gè)不停旋轉(zhuǎn)的輪子，只有轉(zhuǎn)到那個(gè)進(jìn)程前，該進(jìn)程才可以占用CPU，否則只有等待。時(shí)間片輪轉(zhuǎn)調(diào)度算法可總結(jié)為以下幾步：(1)將系統(tǒng)中所有的就緒進(jìn)程按照某種原則(如FCFS原則)排成一個(gè)隊(duì)列。(2)每次調(diào)度時(shí)將CPU分派給就緒隊(duì)列的隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。(3)在一個(gè)時(shí)間片結(jié)束時(shí)發(fā)生時(shí)鐘中斷，調(diào)度程序暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾。選擇就緒隊(duì)列的隊(duì)首進(jìn)程，并通過(guò)上下文切換執(zhí)行該進(jìn)程。時(shí)間片選擇的方法一般有：(1)固定時(shí)間片，即分配給每個(gè)進(jìn)程相等的時(shí)間片，使所有進(jìn)程都公平執(zhí)行，是一種實(shí)現(xiàn)簡(jiǎn)單又有效的方法。時(shí)間片=R/Nmax=響應(yīng)時(shí)間/最大進(jìn)程數(shù)(2)可變時(shí)間片，即根據(jù)進(jìn)程的不同要求對(duì)時(shí)間片的大小實(shí)時(shí)修改，可以更好地提高效率。在選擇時(shí)間片的大小時(shí)，應(yīng)考慮以下幾方面的因素：(1)系統(tǒng)響應(yīng)時(shí)間。在交互式的分時(shí)系統(tǒng)中，用戶對(duì)系統(tǒng)的響應(yīng)時(shí)間非常關(guān)心，如果時(shí)間片過(guò)大，會(huì)使用戶感到請(qǐng)求不能得到及時(shí)的響應(yīng)。(2)就緒進(jìn)程個(gè)數(shù)。在就緒隊(duì)列中的進(jìn)程個(gè)數(shù)是在隨時(shí)變化的，如果時(shí)間片過(guò)大，進(jìn)入就緒隊(duì)列中的進(jìn)程不斷增多，就使得時(shí)間片輪轉(zhuǎn)一次的總時(shí)間過(guò)長(zhǎng)。(3)CPU的能力。隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，CPU的處理能力也越來(lái)越高，時(shí)間片就可以越來(lái)越短。4.多級(jí)隊(duì)列算法多級(jí)隊(duì)列算法(Multiple-LevelQueue)引入多個(gè)就緒隊(duì)列，通過(guò)對(duì)各隊(duì)列的區(qū)別對(duì)待，達(dá)到一個(gè)綜合的調(diào)度目標(biāo)。1962年，Corbato等人提出的CTSS是最早使用優(yōu)先級(jí)調(diào)度的系統(tǒng)之一。由于CTSS的內(nèi)存空間有限，只能存放一個(gè)進(jìn)程，進(jìn)程的切換都需要在內(nèi)、外存進(jìn)行，進(jìn)程切換速度太慢。他們考慮到，給占用CPU多的進(jìn)程分配以較大的時(shí)間片比分配較短的時(shí)間片會(huì)減少切換次數(shù)，提高運(yùn)行效率，但是給進(jìn)程分配大的時(shí)間片又會(huì)影響響應(yīng)時(shí)間，所以他們采用多個(gè)優(yōu)先級(jí)隊(duì)列的方法。首先根據(jù)進(jìn)程的性質(zhì)或類型的不同，將就緒隊(duì)列再分為若干個(gè)子隊(duì)列，見(jiàn)圖2.10。圖2.10多級(jí)隊(duì)列算法實(shí)時(shí)調(diào)度由于在實(shí)時(shí)系統(tǒng)中都存在著若干實(shí)時(shí)進(jìn)程或任務(wù)，它們用來(lái)反應(yīng)或控制某個(gè)外部事件，往往帶有某種程度的緊迫性。因而對(duì)實(shí)時(shí)系統(tǒng)中的調(diào)度提出了某些特殊的要求，為此提出了一種新的調(diào)度技術(shù)，即實(shí)時(shí)調(diào)度。在實(shí)時(shí)系統(tǒng)中，硬實(shí)時(shí)任務(wù)與軟實(shí)時(shí)任務(wù)都系著一個(gè)截止時(shí)間。為保證系統(tǒng)能正常工作，實(shí)時(shí)調(diào)度必須能滿足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求，為此，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：就緒時(shí)間。該任務(wù)成為就緒態(tài)的起始時(shí)間，在周期任務(wù)下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)情況下，它可能是預(yù)知的；開(kāi)始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用，只需知道二者之一；處理時(shí)間。這是指一個(gè)任務(wù)從開(kāi)始執(zhí)行直至完成所需要的時(shí)間；資源要求。指任務(wù)執(zhí)行時(shí)所需要的一組資源。優(yōu)先級(jí)。如果某任務(wù)錯(cuò)過(guò)了開(kāi)始截止時(shí)間就會(huì)引起故障，則應(yīng)為該任務(wù)賦予絕對(duì)優(yōu)先級(jí)，如果無(wú)重大影響，則可賦予相對(duì)優(yōu)先級(jí)，供調(diào)度程序參考。實(shí)時(shí)系統(tǒng)處理能力在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)不能及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的實(shí)時(shí)任務(wù)，他們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個(gè)實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50ms，而每次的處理時(shí)間是10ms，則不難算出，上式不滿足，系統(tǒng)不可調(diào)度。解決方法是提高系統(tǒng)的處理能力。途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)，假定處理機(jī)數(shù)增加至N，則上述限制條件改為：常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先算法(EarliestDeadlineFirst,EDF)非搶占式調(diào)度用于非周期實(shí)時(shí)任務(wù)

該算法是根據(jù)任務(wù)的開(kāi)始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間越早，其優(yōu)先級(jí)越高。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間早晚排序；當(dāng)然，具有最早截止時(shí)間的任務(wù)排在隊(duì)列前面。1342

開(kāi)始截止時(shí)間任務(wù)執(zhí)行1342隊(duì)列任務(wù)到達(dá)1234t0t1搶占式調(diào)度用于周期實(shí)時(shí)任務(wù)2)最低松弛度優(yōu)先算法(LeastLaxityFirst，LLF)該算法是根據(jù)任務(wù)的緊急（或松弛）的程度，來(lái)確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度越高，為該任務(wù)所賦予的優(yōu)先級(jí)就越高(換言之，松弛度越低，剩給調(diào)度的事件越少，即越緊急)，以使之優(yōu)先執(zhí)行。例如一個(gè)任務(wù)在200ms時(shí)必須完成，而本身所需的運(yùn)行時(shí)間有100ms，因此調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度（松弛程度）為100ms。又如，另一任務(wù)在400ms時(shí)必須完成，它本身運(yùn)行需要150ms，則其松弛程度為250ms。在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列的最前面，調(diào)度程序總是選擇就緒隊(duì)列中的首任務(wù)執(zhí)行。例:假如在一個(gè)實(shí)時(shí)系統(tǒng)中有兩個(gè)周期任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間是10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。A1,A2…，B1,B2…分別表示各任務(wù)的完成截止時(shí)間。A1A2A3A4A5A6A7A8B1B2B3020406080100120140160

01020304050607080A1(10)A2(10)A3(10)A4(10)

B1(20)B1(5)B2(15)B2(10)

松弛度=截止運(yùn)行時(shí)間－任務(wù)本身需要的執(zhí)行時(shí)間－當(dāng)前時(shí)間3.4死鎖的基本概念死鎖主要是由兩個(gè)或多個(gè)進(jìn)程對(duì)資源需求的沖突引起的。Dijkstra在1968年提出了這種情況：兩個(gè)或多個(gè)進(jìn)程都占有其他進(jìn)程請(qǐng)求的資源，就像兩個(gè)過(guò)獨(dú)木橋的人，同時(shí)站在橋中央，兩個(gè)人都等待對(duì)方讓出路，但是誰(shuí)也不肯退回去讓別人先走，導(dǎo)致誰(shuí)也到不了對(duì)岸，這兩個(gè)人就像兩個(gè)進(jìn)程，同時(shí)在等待對(duì)方讓出占有的“橋”這一資源，兩個(gè)進(jìn)程都不能執(zhí)行，處于永遠(yuǎn)的等待狀態(tài)。3.3.1資源在計(jì)算機(jī)系統(tǒng)中，存在著許多資源，我們稱其中那些在任一時(shí)刻只能允許一個(gè)進(jìn)程占有的資源叫做獨(dú)占資源。系統(tǒng)資源在總體上按照是否能被消耗可以分為永久性資源和臨時(shí)性資源。永久性資源就是指獨(dú)占資源，可以重復(fù)使用；臨時(shí)性資源是指可消耗的資源，例如進(jìn)程通信時(shí)使用的郵件等。3.2.2產(chǎn)生死鎖的4個(gè)必要條件并不是所有的并發(fā)進(jìn)程都會(huì)產(chǎn)生死鎖，死鎖的產(chǎn)生是有條件的。Coffman等人在1971年總結(jié)出了產(chǎn)生死鎖的4個(gè)必要條件：(1)互斥使用(資源獨(dú)占)：進(jìn)程對(duì)其申請(qǐng)的資源進(jìn)行排他控制，其他申請(qǐng)資源的進(jìn)程必須等待。(2)非剝奪控制(不可強(qiáng)占)：占用資源的進(jìn)程只能自己釋放資源，不能被其他進(jìn)程強(qiáng)迫釋放，即使該進(jìn)程處于阻塞狀態(tài)，它所占有的資源也不能被其他進(jìn)程使用，其他進(jìn)程只能等待該資源的釋放。(3)零散請(qǐng)求：進(jìn)程可以按需要逐次申請(qǐng)資源，而不是集中性一次請(qǐng)求所有資源。這樣，進(jìn)程在已經(jīng)占有資源的情況下，又申請(qǐng)其他資源而得不到滿足時(shí)，并不釋放已占有的資源。(4)循環(huán)等待：等待資源的進(jìn)程形成了一個(gè)封閉的鏈，鏈上的進(jìn)程都在等待下一個(gè)進(jìn)程占有的資源，造成了無(wú)止境的等待狀態(tài)。3.5產(chǎn)生死鎖的示例1．P、V操作不當(dāng)引起死鎖在第2章中我們介紹了利用P、V操作可以實(shí)現(xiàn)進(jìn)程同步。設(shè)有兩個(gè)信號(hào)量S1和S2，初值為0，進(jìn)程T1和T2如果按照?qǐng)D3.1所示的方式使用這兩個(gè)信號(hào)量，就會(huì)發(fā)生死鎖，因?yàn)檫M(jìn)程T1中P(S2)和V(S1)的順序顛倒了。圖3.1P、V操作不當(dāng)引起死鎖2．進(jìn)程申請(qǐng)順序不當(dāng)引起死鎖假設(shè)系統(tǒng)有一臺(tái)打印機(jī)和一臺(tái)掃描儀，進(jìn)程T1和T2共享這兩臺(tái)設(shè)備，兩個(gè)進(jìn)程對(duì)資源的執(zhí)行順序如圖3.2所示。圖3.2申請(qǐng)順序不當(dāng)引起死鎖3．同類資源分配不當(dāng)引起死鎖假如系統(tǒng)中有9個(gè)資源，4個(gè)進(jìn)程，每個(gè)進(jìn)程都需要4個(gè)資源才能完成執(zhí)行。進(jìn)程總需求量是16個(gè)資源，遠(yuǎn)大于9?，F(xiàn)在系統(tǒng)給每個(gè)進(jìn)程都分配了兩個(gè)資源，系統(tǒng)還剩1個(gè)資源，這樣無(wú)論把剩余的1個(gè)資源分給誰(shuí)，也不能執(zhí)行下去，造成了死鎖。4.進(jìn)程通信引起死鎖對(duì)于消耗性資源的使用有時(shí)也會(huì)引起死鎖，例如進(jìn)程間同步時(shí)交換信息、數(shù)據(jù)文件等也可能引起死鎖。假設(shè)，進(jìn)程T1發(fā)送信息S1，要求從T3接收信息S3；進(jìn)程T2發(fā)送信息S2，要求從T1接收信息S1；進(jìn)程T3發(fā)送信息S3，要求從T2接收信息S2。圖3.3信息傳送引起的死鎖如果按照以下順序執(zhí)行：T1：釋放S1，請(qǐng)求S3；T2：釋放S2，請(qǐng)求S1；T3：釋放S3，請(qǐng)求S2；系統(tǒng)不會(huì)死鎖。但要按照以下的順序執(zhí)行：T1：請(qǐng)求S3，釋放S1；T2：請(qǐng)求S1，釋放S2；T3：請(qǐng)求S2，釋放S3；3.6解決死鎖的方案1．鴕鳥(niǎo)政策這是一種最簡(jiǎn)單的方法，又稱鴕鳥(niǎo)政策，就像鴕鳥(niǎo)一樣把頭埋進(jìn)沙子，對(duì)危險(xiǎn)視而不見(jiàn)。類似的，系統(tǒng)對(duì)死鎖不加理會(huì)。鴕鳥(niǎo)政策的出發(fā)點(diǎn)是，由于并發(fā)系統(tǒng)中的死鎖現(xiàn)象并不是每時(shí)每刻都會(huì)發(fā)生，特別是在早期的系統(tǒng)中是極偶然的現(xiàn)象。所以，系統(tǒng)的設(shè)計(jì)者寧愿花更多的精力和資源，解決其他更加棘手、出現(xiàn)更為頻繁的問(wèn)題。2．不讓死鎖發(fā)生這是一種以遏制死鎖為出發(fā)點(diǎn)的想法，即在進(jìn)程執(zhí)行前和執(zhí)行過(guò)程當(dāng)中，對(duì)資源的分配加以限制，使系統(tǒng)永遠(yuǎn)不會(huì)死鎖。對(duì)資源分配的策略可以分為靜態(tài)策略和動(dòng)態(tài)策略。靜態(tài)策略是指進(jìn)程在創(chuàng)建時(shí)就由系統(tǒng)為其分配了所有資源，滿足后方可執(zhí)行，并且在以后的執(zhí)行過(guò)程中沒(méi)有資源分配工作。3．讓死鎖發(fā)生如果說(shuō)不讓死鎖發(fā)生是事前控制，那么讓死鎖發(fā)生就是事后彌補(bǔ)的方法，主要是指當(dāng)死鎖發(fā)生時(shí)，我們采取的應(yīng)對(duì)措施。畢竟用戶使用計(jì)算機(jī)時(shí)，更注重效率，而不讓死鎖發(fā)生的策略都有些極端，當(dāng)死鎖偶然發(fā)生的時(shí)候我們?cè)賮?lái)解決也為時(shí)不晚。3.6.1死鎖的預(yù)防產(chǎn)生死鎖的必要條件我們已經(jīng)了解了，預(yù)防死鎖的工作可以從破壞這些條件入手。1)破壞互斥條件我們知道，允許兩個(gè)進(jìn)程同時(shí)使用打印機(jī)這種獨(dú)占資源會(huì)造成混亂，如果資源允許進(jìn)程共享，那么死鎖肯定不會(huì)產(chǎn)生。通過(guò)借助SPOOLing技術(shù)可以允許若干個(gè)進(jìn)程同時(shí)產(chǎn)生打印數(shù)據(jù)。2)破壞"不可剝奪"條件允許進(jìn)程剝奪也應(yīng)當(dāng)包括剝奪自己的“請(qǐng)求”，也就是進(jìn)程申請(qǐng)資源得不到滿足時(shí)，進(jìn)程可以收回請(qǐng)求，轉(zhuǎn)去做其他的工作。有許多可以破壞這個(gè)條件的方法，這里介紹兩種:如果一個(gè)已經(jīng)占有資源的進(jìn)程再次申請(qǐng)資源時(shí)，所申請(qǐng)的資源不能得到滿足，它必須先放棄已經(jīng)占有的資源，若這些資源還沒(méi)有使用完，則只能以后一起申請(qǐng)。另一種方法只適用于申請(qǐng)資源的進(jìn)程優(yōu)先級(jí)比占有該資源的進(jìn)程優(yōu)先級(jí)高的情況，如果一個(gè)進(jìn)程申請(qǐng)的資源正被別的進(jìn)程占用，若申請(qǐng)進(jìn)程的優(yōu)先級(jí)高，它就可以強(qiáng)迫占有資源的進(jìn)程放棄使用。3)破壞“零散請(qǐng)求”條件許多操作系統(tǒng)破壞“零散請(qǐng)求”條件時(shí)都采用靜態(tài)分配策略。靜態(tài)分配是指當(dāng)一個(gè)進(jìn)程得到了它所需要的所有資源后才能執(zhí)行。利用這種分配機(jī)制，進(jìn)程在執(zhí)行的過(guò)程中就不需要申請(qǐng)資源了，死鎖的四個(gè)必要條件之一的“零散請(qǐng)求”得以破壞。4)破壞“循環(huán)等待”條件按序分配資源的方法對(duì)破壞“循環(huán)等待”條件很有效。系統(tǒng)依據(jù)一定的策略給資源編號(hào)，例如按照資源特性、使用的頻度或數(shù)量的多少等，由低到高順序編號(hào)，進(jìn)程必須按從小到大的順序申請(qǐng)資源，并規(guī)定進(jìn)程占有的資源號(hào)小于申請(qǐng)的資源號(hào)時(shí)才能得到申請(qǐng)資源。例3.1再次探討著名的哲學(xué)家就餐問(wèn)題。如圖2.12所示，將5把叉子依次編號(hào)為0～4，規(guī)定哲學(xué)家必須先拿小序號(hào)的叉子，再拿大序號(hào)的叉子。若小號(hào)的叉子正被占用，他就進(jìn)入阻塞，直到小號(hào)的叉子被放下。這樣，即使5個(gè)哲學(xué)家同時(shí)伸出左手，第4號(hào)哲學(xué)家應(yīng)先拿第0號(hào)叉子，但第0號(hào)叉子被第一個(gè)哲學(xué)家占據(jù)，所以，第4號(hào)哲學(xué)家因?yàn)椴荒軗碛?號(hào)叉子而無(wú)法申請(qǐng)4號(hào)叉子，因而被阻塞。這樣，拿第3號(hào)叉子的哲學(xué)家同時(shí)可以拿到4號(hào)叉子，先吃完了通心粉，釋放其占據(jù)的叉子，喚醒其他哲學(xué)家進(jìn)程。依此類推，最終大家都可以順利地吃完。設(shè)5個(gè)哲學(xué)家對(duì)應(yīng)5個(gè)進(jìn)程P0、P1、P2、P3、P4，5把叉子對(duì)應(yīng)5個(gè)資源r0、r1、r2、r3、r4，進(jìn)程Pi必須先申請(qǐng)叉子ri，再申請(qǐng)叉子ri+1，進(jìn)程P4必須先申請(qǐng)叉子r0，再申請(qǐng)叉子r4，設(shè)5個(gè)信號(hào)量為S0、S1、S2、S3、S4，初值為1。5個(gè)哲學(xué)家就餐的程序如下：beginS0，S1，S2，S3，S4:semaphore;S0=S1=S2=S3=S4=1;ProcessPi(i=0，1，2，3)BeginLi:thinking；hungry；P(Si);pickupri;P(Si+1);pickupri+1;eating;putdownri;putdownri+1;V(Si);V(Si+1);gotoLi;end;ProcessP4BeginL4:thinking；hungry；P(S0);pickupr0;P(S4);pickupr4;eating;putdownr0;putdownr4;V(S0);V(S4);gotoL4;end;對(duì)資源按序號(hào)分配的時(shí)候要注意：如果資源有多種類型，那么也要將這些資源類型按照一定的策略安排成一個(gè)序列，進(jìn)程申請(qǐng)資源的時(shí)候先要確定類型的高低，再看此類型中各資源的序號(hào)大小。將預(yù)防死鎖的各種方法總結(jié)如表3.7所示。死鎖的條件方法互斥對(duì)所有資源進(jìn)行SPOOLing操作零散請(qǐng)求進(jìn)程創(chuàng)建時(shí)申請(qǐng)所有的資源非剝奪控制將資源剝奪循環(huán)等待對(duì)資源進(jìn)行編號(hào)，按序申請(qǐng)3.6.2死鎖的避免死鎖的預(yù)防策略是以破壞死鎖產(chǎn)生的必要條件為目的，對(duì)資源的申請(qǐng)加以限制的。雖然這對(duì)死鎖的預(yù)防有一定的效果，但是幾種方法都降低了系統(tǒng)的效率和資源的利用率。死鎖的避免策略有所不同，它用動(dòng)態(tài)的方法判斷資源的使用情況和系統(tǒng)的狀態(tài)，在分配資源之前，系統(tǒng)將判斷假若滿足進(jìn)程的要求是否會(huì)發(fā)生死鎖，如果會(huì)，資源就不予分配，從而避免死鎖的發(fā)生。系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。所謂安全狀態(tài)，是指當(dāng)多個(gè)進(jìn)程動(dòng)態(tài)地申請(qǐng)資源時(shí)，系統(tǒng)將按照某種順序逐次地為每個(gè)進(jìn)程分配所需資源，使每個(gè)進(jìn)程都可以在最終得到最大需求量后，依次順利地完成。反之，如果不存在這樣一種分配順序使得進(jìn)程都能順利完成，則稱系統(tǒng)處于不安全狀態(tài)。

安全序列處于安全狀態(tài)下的系統(tǒng)是不會(huì)發(fā)生死鎖的。不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一定屬于不安全狀態(tài)。安全狀態(tài)、不安全狀態(tài)以及死鎖的關(guān)系如圖3.4所示。因此，避免死鎖的關(guān)鍵就是：讓系統(tǒng)在動(dòng)態(tài)分配資源的過(guò)程中，不進(jìn)入不安全狀態(tài)。安全狀態(tài)不安全狀態(tài)死鎖圖3.4系統(tǒng)的狀態(tài)關(guān)系1．單項(xiàng)資源的銀行家算法銀行家算法是避免死鎖的一個(gè)著名的算法，是由E.W.Dijkstra在1965年為T.H.E系統(tǒng)設(shè)計(jì)的一種避免死鎖算法。它以銀行借貸系統(tǒng)的分配策略為基礎(chǔ)，判斷并保證系統(tǒng)的安全運(yùn)行。實(shí)現(xiàn)銀行家算法的程序流程如圖3.5所示。圖3.5銀行家算法的程序流程暫時(shí)的插入安全序列亦是一個(gè)求安全序列的過(guò)程。若存在安全序列,則分配；若不存在,則撤消預(yù)分配的策略。假設(shè)，有一個(gè)銀行家擁有的資金量是10(為敘述簡(jiǎn)便，這里省略資金量的單位)，現(xiàn)在有4個(gè)客戶a、b、c、d，各自需要的最大資金量分別是4、5、6、7，狀態(tài)如圖3.6(a)所示。顯然，銀行家不能同時(shí)滿足4個(gè)客戶，因?yàn)檫@需要22的資金量。在某一時(shí)刻，4個(gè)客戶的狀態(tài)如圖3.6(b)所示，這時(shí)先滿足客戶a，分配資金量3，使他擁有最大資金量4。圖3.6單項(xiàng)資源的銀行家算法客戶名已用資金最大資金仍需資金剩余資金a044b055c066d07710剩余資金a143b253c165d2754剩余資金a---b253c165d2755剩余資金a143b253c561d2750(a)(b)(c)(d)2．多項(xiàng)資源的銀行家算法假設(shè)系統(tǒng)中有以下各類多個(gè)資源：5臺(tái)打印機(jī)，7個(gè)手寫板，8臺(tái)掃描儀，9個(gè)讀卡器。為了方便，我們把系統(tǒng)資源總量用向量sum表示，上述4種資源分別用R1、R2、R3、R4表示，已分配資源用向量allocation表示，系統(tǒng)當(dāng)前剩余資源用向量available表示，進(jìn)程還需申請(qǐng)資源用向量claim表示，共有5個(gè)進(jìn)程T1、T2、T3、T4、T5共享這些資源。各進(jìn)程所需最大資源量如圖3.7(a)所示，現(xiàn)已知：系統(tǒng)資源總量：sum＝(5，7，8，9)，已分配資源向量：allocation＝(3，5，7，7)系統(tǒng)當(dāng)前狀態(tài)如圖3.7(b)所示，計(jì)算可知：當(dāng)前剩余資源向量：available＝sum－allocation＝(2，2，1，2)allocationmax圖3.7多項(xiàng)資源的銀行家算法系統(tǒng)資源總量：sum＝(5，7，8，9)當(dāng)前剩余資源向量：available＝sum－allocation＝(2，2，1，2)allocationmaxclaim例3.2設(shè)系統(tǒng)中有3種類型的資源(A,B,C)和5個(gè)進(jìn)程P1、P2、P3、P4、P5,已知A,B,C的總量是[17,5,20],在T0時(shí)刻的狀態(tài)如下所示:T0時(shí)刻:max=ABCallocation=ABCABCclaim=系統(tǒng)采用銀行家算法避免死鎖，問(wèn):(1)T0時(shí)刻是否為安全狀態(tài)？(2)T0時(shí)刻若P2請(qǐng)求[0,3,4],能否分配?(3)在(2)的基礎(chǔ)上P4請(qǐng)求[2,0,1],能否實(shí)施分配?(4)在(3)的基礎(chǔ)上,P1又請(qǐng)求[0,2,0],能否實(shí)施分配?(2)不能.此時(shí)的剩余資源為[2,3,3],資源不夠分配.(1)由allocaiton得出剩余資源為[2,3,3],與claim矩陣比較,可找出安全序列:54231或45213等,因此,T0時(shí)刻是安全的.(3)按算法，(2)的基礎(chǔ)上，假設(shè)為P4分配[2,0,1],剩余[0,3,2],此時(shí)的請(qǐng)求矩陣為：(4)在(3)的基礎(chǔ)上，假設(shè)為P1分配[0,2,0]，剩余[0,1,2],此時(shí),所有的進(jìn)程都處于未完成的狀態(tài),剩余需求量矩陣當(dāng)前的剩余矩陣與請(qǐng)求矩陣比較,不能滿足任何一個(gè)進(jìn)程的要求,故P1-P5都不可能完成,即不存在安全序列,如若資源完全分配,則P1-P5因均得不到資源而阻塞,出現(xiàn)死鎖，因此不分配。claim=claim=，可找到安全序列p4,p5,p2,p1,p3，因此可以分配。3.3.3死鎖的檢測(cè)和解除1．資源分配圖及死鎖的檢測(cè)資源分配圖是描述進(jìn)程申請(qǐng)資源和資源分配情況的關(guān)系模型圖，它可以直觀地檢測(cè)系統(tǒng)是否會(huì)死鎖。其實(shí)在第2章中出現(xiàn)的圖2.15就是一個(gè)簡(jiǎn)單的資源分配圖。在資源分配圖中，有以下規(guī)定：(1)圓表示一個(gè)進(jìn)程。(2)方塊表示一個(gè)資源類，其中的圓點(diǎn)表示該類型資源中的單個(gè)資源。(3)從資源指向進(jìn)程的箭頭表示資源被分配給了這個(gè)進(jìn)程。(4)從進(jìn)程指向資源的箭頭表示進(jìn)程申請(qǐng)一個(gè)這類資源。

例如在圖3.8中我們可以了解到的信息是：資源類R1中的兩個(gè)資源分別分配給了進(jìn)程T1和T3；進(jìn)程T2正在申請(qǐng)R1；資源類R2中的兩個(gè)資源分別給了進(jìn)程T2和T4；進(jìn)程T1正在申請(qǐng)一個(gè)R2。圖3.8一個(gè)簡(jiǎn)單的資源分配圖設(shè)資源類Rj有資源Wj個(gè)，用|(Rj,Pi)|表示Rj分配給進(jìn)程Pi的資源個(gè)數(shù)，用|(Pi,Rj)|表示進(jìn)程Pi申請(qǐng)Rj的資源個(gè)數(shù)。一張合理的資源分配圖應(yīng)該代表系統(tǒng)中某個(gè)時(shí)刻進(jìn)程對(duì)資源的申請(qǐng)和占有狀態(tài)，因此，它應(yīng)當(dāng)滿足以下兩個(gè)條件：(1)資源Rj分配給各進(jìn)程的資源數(shù)目不能大于Wj，即對(duì)于各類資源Rj的分配應(yīng)滿足：≤Wj

(2)任何一個(gè)進(jìn)程Pi對(duì)某類資源Rj的申請(qǐng)量和已分配數(shù)量之和，不應(yīng)大于該類資源的總數(shù)Wj，即

|(Pi,Rj)|+|(Rj,Pi)|≤Wj有了資源分配圖，可以按照以下算法進(jìn)行分析化簡(jiǎn)，進(jìn)一步判斷是否存在死鎖：(1)檢查圖中有無(wú)環(huán)路，如果沒(méi)有，系統(tǒng)不會(huì)發(fā)生死鎖，結(jié)束檢測(cè)；如果有環(huán)路，進(jìn)行第(2)步。(2)若環(huán)路中涉及的每個(gè)資源類中只有一個(gè)資源，系統(tǒng)一定死鎖；若每個(gè)資源類中有多個(gè)資源，進(jìn)行第(3)步。

(3)在環(huán)路中查找非阻塞且非獨(dú)立的進(jìn)程Pi，Pi應(yīng)滿足：≤Wj圖3.9死鎖檢測(cè)的流程更正化簡(jiǎn):(1)顯然圖中存在一個(gè)環(huán)，聯(lián)系著進(jìn)程T1、T2、T3、T4和資源R1、R2。(2)R1和R2中各有兩個(gè)資源。(3)進(jìn)程T3和T4是非阻塞的，可以把連接它們的有向邊去掉，系統(tǒng)狀態(tài)如圖3.10所示；進(jìn)程T1和T2申請(qǐng)的資源都可以得到滿足，它們也都可以置成孤立結(jié)點(diǎn)，該圖化簡(jiǎn)完畢。因此該系統(tǒng)不會(huì)死鎖。圖3.10化簡(jiǎn)后的資源分配圖2．臨時(shí)資源的死鎖檢測(cè)系統(tǒng)中有許多臨時(shí)性資源，使用這些資源時(shí)的方法與我們以上講到的方法稍有不同。上面提到進(jìn)程要及時(shí)釋放資源，而占有的是臨時(shí)性資源時(shí)，進(jìn)程就可以不必釋放它。諸如信號(hào)、消息和郵件等，沒(méi)有限定的單元數(shù)，也沒(méi)有釋放的工作，所以單純地用化簡(jiǎn)資源分配圖的方法是行不通的。上面的資源分配和回收關(guān)系不能清楚地表示這種情況，所以我們對(duì)資源分配圖進(jìn)行重新定義：(1)圓表示一個(gè)進(jìn)程。(2)方塊表示一個(gè)資源類，其中的圓點(diǎn)表示該類型資源中的單個(gè)資源。(3)由資源類指向進(jìn)程的箭頭表示該進(jìn)程產(chǎn)生這種資源，一個(gè)箭頭可表示產(chǎn)生一到多個(gè)資源，每個(gè)資源類至少有一個(gè)生產(chǎn)者進(jìn)程。(4)由進(jìn)程指向資源的箭頭表示該進(jìn)程申請(qǐng)這種資源，一個(gè)箭頭只表示申請(qǐng)一個(gè)資源。第1、2、4點(diǎn)基本同前圖3.11臨時(shí)性資源分配圖3．死鎖的解除一旦系統(tǒng)檢測(cè)出有死鎖出現(xiàn)，系統(tǒng)將通過(guò)改變某些進(jìn)程的狀態(tài)解除死鎖。以下介紹解除死鎖的一些方法：(1)重新啟動(dòng)。這是一種比較粗暴的方法，也是操作系統(tǒng)常用的方法，雖然實(shí)現(xiàn)簡(jiǎn)單，但會(huì)使之前的工作全部白費(fèi)，造成很大的損失和浪費(fèi)。(2)撤消進(jìn)程。在死鎖時(shí)，系統(tǒng)可以撤消造成死鎖的進(jìn)程，解除死鎖。(3)剝奪資源。在死鎖時(shí)，系統(tǒng)可以保留進(jìn)程，只剝奪死鎖進(jìn)程占有的資源，直到解除死鎖。選擇被剝奪資源的進(jìn)程的方法和選擇被撤消的進(jìn)程的方法相同。(4)進(jìn)程回退。在死鎖時(shí)，系統(tǒng)可以根據(jù)保留的歷史信息，讓死鎖的進(jìn)程從當(dāng)前狀態(tài)向后退回到某種狀態(tài)，直到死鎖解除。3.7其他相關(guān)問(wèn)題3.7.1兩階段加鎖一個(gè)加鎖單位究竟取多大的問(wèn)題稱為鎖的粒度.

粒度越合適,加鎖就可以越精確,也就能實(shí)現(xiàn)更大的并發(fā)度(例如,并不因?yàn)槟硞€(gè)進(jìn)程正在使用文件的開(kāi)頭就阻塞另一個(gè)試圖使用該文件末尾的進(jìn)程).

另一方面,鎖分得越細(xì)致,也就越需要更多的鎖,這樣的開(kāi)銷也就越大,也就更容易導(dǎo)致死鎖.

兩階段加鎖法

恰好在需要或不再需要鎖時(shí)去請(qǐng)求或釋放鎖可能會(huì)導(dǎo)致不一致和死鎖.因此,許多用加鎖方法實(shí)現(xiàn)的事務(wù)都采用所謂的兩階段加鎖法.

在兩階段加鎖法中,進(jìn)程在增長(zhǎng)階段先請(qǐng)求它需要的所有鎖,然后在收縮階段釋放它們.

如果進(jìn)程直到收縮階段才試圖更新文件,那么對(duì)因請(qǐng)求鎖而造成的失敗的處理僅僅是釋放掉所有的鎖,等待一段時(shí)間后再全部重新開(kāi)始.

此外,可以證明(Eswaran等,1976)如果所有的事務(wù)都使用兩階段加鎖法,那么通過(guò)交錯(cuò)事務(wù)進(jìn)行的所有調(diào)度都是串行的.這也是兩階段加鎖法廣泛使用的原因.3.7.2饑餓 產(chǎn)生饑餓的主要原因是：在一個(gè)動(dòng)態(tài)系統(tǒng)中，對(duì)于每類系統(tǒng)資源，操作系統(tǒng)需要確定一個(gè)分配策略，當(dāng)多個(gè)進(jìn)程同時(shí)申請(qǐng)某類資源時(shí)，由分配策略確定資源分配給進(jìn)程的次序。有時(shí)資源分配策略可能是不公平的，即不能保證等待時(shí)間上界的存在。在這種情況下，即使系統(tǒng)沒(méi)有發(fā)生死鎖，某些進(jìn)程也可能會(huì)長(zhǎng)時(shí)間等待．當(dāng)?shù)却龝r(shí)間給進(jìn)程推進(jìn)和響應(yīng)帶來(lái)明顯影響時(shí)，稱發(fā)生了進(jìn)程饑餓，當(dāng)饑餓到一定程度的進(jìn)程所賦予的任務(wù)即使完成也不再具有實(shí)際意義時(shí)稱該進(jìn)程被餓死。舉個(gè)例子，當(dāng)有多個(gè)進(jìn)程需要打印文件時(shí)，如果系統(tǒng)分配打印機(jī)的策略是最短文件優(yōu)先，那么長(zhǎng)文件的打印任務(wù)將由于短文件的源源不斷到來(lái)而被無(wú)限期推遲，導(dǎo)致最終的饑餓甚至餓死。3.8多處理機(jī)系統(tǒng)中的調(diào)度3.8.1多處理機(jī)(MPS,MultiProcessorSystem)的類型緊密耦合MPS(TightlyCoupled)通過(guò)高速總線或高速交叉開(kāi)關(guān)相連；將主存劃分為若干能獨(dú)立訪問(wèn)的存儲(chǔ)器模塊；

松弛耦合MPS(LooselyCoupled)通過(guò)通道或通信線路實(shí)現(xiàn)多臺(tái)計(jì)算機(jī)之間的互連；每臺(tái)計(jì)算機(jī)有各自的存儲(chǔ)器和I/O設(shè)備；每臺(tái)計(jì)算機(jī)能夠獨(dú)立工作，有需要時(shí)可通過(guò)通信線路與其他計(jì)算機(jī)交換信息，以及協(xié)調(diào)它們之間的工作。根據(jù)系統(tǒng)中所有處理機(jī)是否相同，可將MPS分成以下兩類：對(duì)稱多處理機(jī)系統(tǒng)非對(duì)稱多處理機(jī)系統(tǒng)3.8.2MPS系統(tǒng)中進(jìn)程分配方式對(duì)稱多處理機(jī)系統(tǒng)中的進(jìn)程分配方式對(duì)稱，所有處理器都是相同的，因而可把所有的處理器作為一個(gè)處理器池(ProcessPool),由調(diào)度程序或基于處理器的請(qǐng)求，將任何一個(gè)進(jìn)程分配給池中的任何一個(gè)處理器去處理。在進(jìn)行分配時(shí)，可采用以下兩種方式之一:靜態(tài)分配（StaticAssignment）

每一個(gè)進(jìn)程從開(kāi)始執(zhí)行直到完成，都被固定地分配到一個(gè)處理器上去執(zhí)行；須為每一處理器設(shè)置一個(gè)專用的就緒隊(duì)列；動(dòng)態(tài)分配（DynamicAss