第3章進程調(diào)度與死鎖預防

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

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

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

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

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

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

把輸出結(jié)果送到輸出設備上(啟動緩輸出進程完成)。

回收各種資源。

緩輸出進程(脫機)。

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

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

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

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

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

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

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

1)單道程序環(huán)境下作業(yè)調(diào)度性能的分析設有4個作業(yè)，它們的提交時刻、執(zhí)行時間如表3.1所示。作業(yè)提交時刻執(zhí)行時間18.002.0028.500.5039.000.1049.500.20(1)先來先服務調(diào)度算法。按照先來先服務思想，4個作業(yè)的執(zhí)行順序是1，2，3，4。計算該作業(yè)序列的平均周轉(zhuǎn)時間T和平均周轉(zhuǎn)系數(shù)W，如表3.2所示。表3.2計算T和W(先來先服務調(diào)度算法)作業(yè)提交時刻ts執(zhí)行時間tr/小時開始時刻tls完成時刻to周轉(zhuǎn)時間Ti/小時周轉(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)時間T=1.725小時平均周轉(zhuǎn)系數(shù)W=6.8756.9027.50(2)最短作業(yè)優(yōu)先調(diào)度算法。按最短作業(yè)優(yōu)先調(diào)度算法，該作業(yè)序列的執(zhí)行順序為1，3，4，2。由于在8.00開始執(zhí)行作業(yè)，當時僅有1，而作業(yè)2，3，4尚未到達，故作業(yè)1是最短作業(yè)。作業(yè)1執(zhí)行完成后是10.00，此時作業(yè)2，3，4均已經(jīng)到達，故選最短作業(yè)3，依此類推，平均周轉(zhuǎn)時間和平均周轉(zhuǎn)系數(shù)的計算結(jié)果如表3.3所示。表3.3計算T和W(最短作業(yè)優(yōu)先調(diào)度算法)作業(yè)提交時刻ts執(zhí)行時間tr/小時開始時刻tls完成時刻to周轉(zhuǎn)時間Ti/小時周轉(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)時間T=1.55小時平均周轉(zhuǎn)系數(shù)W=5.156.2020.60(3)最高響應比優(yōu)先調(diào)度算法。按最高響應比優(yōu)先調(diào)度算法，該作業(yè)序列的執(zhí)行順序為1，3，2，4。當作業(yè)1執(zhí)行完成時，計算作業(yè)2，3，4的響應比分別為：4，11，3.5，因此，作業(yè)1執(zhí)行完成后選中作業(yè)3執(zhí)行。按此算法求得的平均周轉(zhuǎn)時間和平均周轉(zhuǎn)系數(shù)如表3.4所示。表3.4計算T和W(最高響應比優(yōu)先調(diào)度算法)作業(yè)提交時刻ts執(zhí)行時間tr/小時開始時刻tls完成時刻to周轉(zhuǎn)時間Ti/小時周轉(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)時間T=1.625小時平均周轉(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)度性能的分析有一個具有多道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)進駐內(nèi)存后，采用以優(yōu)先數(shù)為基礎的搶占式調(diào)度算法，即作業(yè)運行時間越短，其對應產(chǎn)生的優(yōu)先數(shù)越大。如有4個作業(yè)序列，現(xiàn)已知它們的提交時刻和運行時間如表3.5所示。表3.54個作業(yè)的提交時刻和運行時間作業(yè)號提交時刻運行時間/分鐘110:0030210:0520310:1020410:2010表3.6計

算

結(jié)

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

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

110:003010:0011:20803.667210:052010:0510:25201310:102010:3510:55453.25410:201010:2510:35151.5平均周轉(zhuǎn)時間T=40分鐘平均周轉(zhuǎn)系數(shù)W=1.8541607.4173.2作業(yè)控制方式3.3.1脫機作業(yè)控制方式作業(yè)控制語言(JCL)是人們根據(jù)一個作業(yè)在運行過程中所能遇到的各種情況及狀態(tài)改變，總結(jié)出的一種表達作業(yè)控制意圖和步驟的語言。JCL包括兩種類型的語句：①表達申請功能的說明性語句；②作業(yè)控制和操作的執(zhí)行性語句。表3.7是一個151-1操作系統(tǒng)的簡單作業(yè)控制說明書，各語句含義解釋如下：表3.7151-1的作業(yè)控制說明書標號動詞參數(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)先級=65，內(nèi)存要求=2500，申請建立此作業(yè)。(2)申請外設資源：寬行打印機1臺，光電機2臺，磁帶機3臺。(3)編譯源文件A202。該文件使用ALGOL語言編寫，文件名A202經(jīng)過編譯后形成目標文件A203。(4)編譯語句正確執(zhí)行后執(zhí)行該語句，把A203裝入該作業(yè)的內(nèi)存區(qū)中。(5)按啟動點1啟動A203運行，在該程序出現(xiàn)各種事件時轉(zhuǎn)到標號36的語句執(zhí)行撤離。(6)在A203運行完畢時開始執(zhí)行本語句，完成有條件撤離該作業(yè)。(7)該語句是編譯過程中或A203程序運行過程中出現(xiàn)錯誤時轉(zhuǎn)來的，無條件撤離該作業(yè)。3.3.2聯(lián)機作業(yè)控制方式1.MS-DOS的作業(yè)控制1)?DOS命令處理程序DOS的命令處理程序處于DOS的最外層，直接面向用戶。它駐留在內(nèi)存中，在系統(tǒng)運行期間不再退出。(1)命令類型。DOS中的操作命令分成三類：內(nèi)部命令：隨裝入內(nèi)存，都集中在根目錄下的文件里。外部命令：以com和exe為后綴的文件，存在于外存中。批處理文件：由一組內(nèi)部命令或外部命令以及批處理命令組成的命令序列構(gòu)成的文件，類型名為.bat。(2)命令處理程序的組成。命令處理程序可分為三部分：非常駐部分：DOS在啟動后會自動運行autoexec.bat這個文件，該文件是一個特殊的批處理文件，由若干個命令行組成，系統(tǒng)啟動時執(zhí)行它，進行一些處理。常駐部分：包括三個中斷處理子程序(終止地址INT22H、CTRL-BREAK處理INT23H和標準錯誤處理INT24H)和一個恢復暫駐部分的程序。

暫駐部分：也稱覆蓋部分，這部分包括所有的內(nèi)部命令處理程序、批命令處理程序以及一個用來裝入并執(zhí)行外部命令的程序。2)命令處理舉例文件中存放著所有命令及執(zhí)行的入口地址，用戶輸入一個命令后，系統(tǒng)要進行識別，找到相應的處理程序，否則會提示用戶輸入的命令有誤，重新輸入。(1)內(nèi)部命令：直接由本身完成，功能簡單，使用頻繁。例如dir，cd，copy。(2)外部命令：通過運行相應的可執(zhí)行文件來完成。(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é)尾

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

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

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

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

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

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

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

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

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

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

(2)任何一個進程Pi對某類資源Rj的申請量和已分配數(shù)量之和，不應大于該類資源的總數(shù)Wj，即

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

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

粒度越合適,加鎖就可以越精確,也就能實現(xiàn)更大的并發(fā)度(例如,并不因為某個進程正在使用文件的開頭就阻塞另一個試圖使用該文件末尾的進程).

另一方面,鎖分得越細致,也就越需要更多的鎖,這樣的開銷也就越大,也就更容易導致死鎖.

兩階段加鎖法

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

在兩階段加鎖法中,進程在增長階段先請求它需要的所有鎖,然后在收縮階段釋放它們.

如果進程直到收縮階段才試圖更新文件,那么對因請求鎖而造成的失敗的處理僅僅是釋放掉所有的鎖,等待一段時間后再全部重新開始.

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

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

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