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

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

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

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

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

(4)完成狀態。當作業正常運行結束或因發生錯誤而終止時，作業進入完成狀態，退出系統。作業退出的工作流程如下所述：

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

回收各種資源。

緩輸出進程(脫機)。

從輸出井上將結果輸出。作業狀態轉換過程如圖3.1所示。圖3.1批處理系統中的作業處理及狀態3.1.2作業的輸入/輸出方式

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

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

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

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

時間要求緊迫的作業獲得高優先級。“I/O繁忙”的作業獲得高優先級，以便充分發揮外設的效率。

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

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

算

結

果作業提交時刻ts執行時間tr/分鐘開始時刻tls完成時刻to

周轉時間Ti/分鐘周轉系數Wi

110:003010:0011:20803.667210:052010:0510:25201310:102010:3510:55453.25410:201010:2510:35151.5平均周轉時間T=40分鐘平均周轉系數W=1.8541607.4173.2作業控制方式3.3.1脫機作業控制方式作業控制語言(JCL)是人們根據一個作業在運行過程中所能遇到的各種情況及狀態改變，總結出的一種表達作業控制意圖和步驟的語言。JCL包括兩種類型的語句：①表達申請功能的說明性語句；②作業控制和操作的執行性語句。表3.7是一個151-1操作系統的簡單作業控制說明書，各語句含義解釋如下：表3.7151-1的作業控制說明書標號動詞參數注釋

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)作業名=A102，用戶名=ABCD，優先級=65，內存要求=2500，申請建立此作業。(2)申請外設資源：寬行打印機1臺，光電機2臺，磁帶機3臺。(3)編譯源文件A202。該文件使用ALGOL語言編寫，文件名A202經過編譯后形成目標文件A203。(4)編譯語句正確執行后執行該語句，把A203裝入該作業的內存區中。(5)按啟動點1啟動A203運行，在該程序出現各種事件時轉到標號36的語句執行撤離。(6)在A203運行完畢時開始執行本語句，完成有條件撤離該作業。(7)該語句是編譯過程中或A203程序運行過程中出現錯誤時轉來的，無條件撤離該作業。3.3.2聯機作業控制方式1.MS-DOS的作業控制1)?DOS命令處理程序DOS的命令處理程序處于DOS的最外層，直接面向用戶。它駐留在內存中，在系統運行期間不再退出。(1)命令類型。DOS中的操作命令分成三類：內部命令：隨裝入內存，都集中在根目錄下的文件里。外部命令：以com和exe為后綴的文件，存在于外存中。批處理文件：由一組內部命令或外部命令以及批處理命令組成的命令序列構成的文件，類型名為.bat。(2)命令處理程序的組成。命令處理程序可分為三部分：非常駐部分：DOS在啟動后會自動運行autoexec.bat這個文件，該文件是一個特殊的批處理文件，由若干個命令行組成，系統啟動時執行它，進行一些處理。常駐部分：包括三個中斷處理子程序(終止地址INT22H、CTRL-BREAK處理INT23H和標準錯誤處理INT24H)和一個恢復暫駐部分的程序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

兩階段加鎖法

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

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

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

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

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

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