一、處理機的多級調度策略第三章處理機的調度與死鎖處理機調度是操作系統的主要功能之一，它的實現策略決定了操作系統的類型，其調度算法的優劣直接影響整個系統的性能。處理機調度的任務是選出待分派的作業或進程，為之分配處理機。一般來說，處理機調度可分為三個級別，分別是高級調度、中級調度和低級調度。1、高級調度又稱作業調度，作業就是用戶程序及其所需的數據和命令的集合，作業管理就是對作業的執行情況進行系統管理的程序的集合。作業調度程序的主要功能是審查系統是否能滿足用戶作業的資源要求以及按照一定的算法來選取作業。2、引入中級調度的主要目的是為了提高內存的利用率和系統吞吐量，使得暫時不運行的進程從內存對換到外存上。3、低級調度又稱進程調度，其主要功能是根據一定的算法將CPU分派給就緒隊列中的一個進程。進程調度是操作系統中最基本的一種調度，其調度策略的優劣直接影響整個系統的性能。幾點說明：在多道批處理系統中，既有高級調度，又有低級調度，也可以采用中級調度。在分時系統中，一般沒有高級調度，只有低級調度，一般會采用中級調度在實時系統中，只有低級調度在支持多道程序的操作系統中，一般存在進程調度有的操作系統采用中級調度，有的操作系統沒有中級調度二、處理機的調度隊列模型1、僅有進程調度的處理高度隊形模型（分時系統中）2、具有兩級調度的處理機調度隊列模型（多道批處理系統中）該模型與上一模型的主要區別在于如下兩個方面：

(1)就緒隊列的形式。

(2)設置多個阻塞隊列。3、具有三級調度的處理機調度隊列模型（多道批處理和分時系統中）三、調度性能的衡量指標對批處理系統應盡量提高各種資源的利用率和增加系統的吞吐量分時系統應保證對用戶的響應時間的要求實時系統必須及時和可靠的處理衡量作業調度和進程調度性能的指標如下：（1）CPU利用率

（2）吞吐量--單位時間內CPU完成作業的數量。

（3）周轉時間--從作業提交到作業完成的時間間隔。

（4）等待時間—作業或進程從進入系統到被調度并開始執行所經歷的時間（5）響應時間--從提交第一個請求到產生第一個響應所用的時間（6）平均帶權周轉時間作業i周轉時間作業i執行時間作業總數作業調度：就是要按一定的策略選取一個或多個作業，為它們分配必需的資源（內存空間、I/O設備等），使它們能夠并發執行。作業調度的必要條件是：系統現有尚未分配的資源可以滿足該作業的資源需求。作業分類批量型作業終端型作業一、批量型作業的組織1、作業申請（作業情況、資源要求）2、作業實體（作業操作說明書、源程序或目標模塊程序、數據集合、修改信息（可沒有）3.2調度算法——作業調度二、批處理系統中作業的狀態及其轉換四種狀態：提交、后備、執行和完成3.2調度算法——作業調度三、實現作業狀態轉換的程序1、SPOOLing系統程序包括輸入程序、輸出程序、井管理程序（讀子程序、寫子程序）2、作業調度程序作業調度程序負責作業從“后備狀態”到“執行狀態”以及從“執行狀態”到“完成狀態”的轉換，作業調度程序為作業分配的是一臺虛擬的邏輯處理機。作業調度：按照某種調度算法從后備作業隊列中挑選一個/幾個作業進入內存，參加運行。同時分配資源，做好運行前的準備。3.2調度算法——作業調度3、進程調度程序進程調度程序的主要任務：實現進程從“就緒狀態”到“運行狀態”的轉變。它總是按照確定的調度算法從就緒隊列中選擇一個進程，讓它占有CPU運行，進程調度程序為作業分配的是一臺真實的物理處理機。4、交通控制程序交通控制程序負責進程狀態的轉換和進程之間的通信。3.2調度算法——作業調度四、作業調度所需的數據結構及其組織1、作業控制塊2、作業后備隊列3.2調度算法——作業調度五、作業調度算法的設計原則面向用戶的準則：周轉時間短；響應時間快；截止時間的保證；優先權準則面向系統的準則：系統吞吐量高；處理機利用率好；各類資源的平衡利用3.2調度算法——作業調度六、常用的作業調度算法先來先服務調度算法（FCFS）特點：簡單容易實現，有利于長作業，但不利于短作業3.2調度算法——作業調度2、最短作業優先調度算法（SJF）特點：易于實現，會使系統平均周轉時間最短，系統吞吐量大。但忽視了作業的等待時間，不利于長作業，會出現“餓死”現象。3.2調度算法——作業調度3、響應比高者優先（HRRF）特點：算法較為復雜，每當調度作業時都需要進行響應比的計算。但它既照顧了用戶作業到來的先后，又考慮了要求系統服務時間的長短。3.2調度算法——作業調度3.2調度算法——作業調度例子：分析在多道批處理系統中，有下列1、2、3、4四個作業，提交時間分別是6.0、6.5、7.0、7.5，執行時間分別是2.0、0.5、0.1、0.2，用先來先服務調度算法和短作業調度算法進行調度，哪一種算法調度性能好些？為什么？若后備作業隊列中等待運行的同時有三個作業J1、J2、J3，已知它們各自的運行時間為a、b、c，且滿足a<b＜c，試證明采用短作業優先算法調度能獲得最小平均作業周轉時間。

3.2調度算法——進程調度一、設計進程調度程序要考慮的問題1、進程調度方式進程的調度方式是指當一個進程正在處理機上運行時，若有更高優權的進程進入就緒隊列時，如何分配CPU的方式，有下列兩種方式：（1）非剝奪方式（實時系統中不宜采用）（2）可剝奪方式搶占的原則：時間片原則優先權原則短進程優先原則2、引起進程重新調度的時機（1）現運行進程任務完成或出現異常（2）現運行進程在運行中雙提出了新的資源申請（3）現運行進程由于執行某些原語，如P操作原語、阻塞原語等（4）在分時系統中，如果現運行進程給定的時間片用完（5）在采用可剝奪方式的調度方式時，當有更高優先權的進程進入就緒隊列時，要引重新高度3.2調度算法——進程調度3、進程調度算法的選擇進程調度算法選擇的準則CPU利用率、吞吐量、等待時間、響應時間4、進程隊列的組織出隊：一個進程從所在隊列退出入隊：一個進程排入指定的隊列隊列管理：系統負責進程入隊和出隊的工作PCB的組織有3種方式：3.2調度算法——進程調度（1）線性表方式（如右圖）（2）鏈接表方式對具有相同狀態的進程，分別各自鏈接起來組成進程PCB鏈隊列：運行隊列、就緒隊列、阻塞隊列、空閑隊列（3）索引表方式對具有相同狀態的進程，分別設置各自的PCB索引表，表明PCB在PCB表中的地址3.2調度算法——進程調度二、常用的進程調度算法1、優先級調度算法優先級的確定方法：（1）按進程的類型系統進程高于用戶進程、前臺作業高于后臺（2）按資源使用的要求資源要求少，優先級高（3）按用戶要求的優先權由用戶確定作業優先級優先級算法：靜態優先級算法：系統在創建進程時就確定了它的優先級，該優先級在進程的整個生存期內不再變化。動態優先級算法：進程的優先級根據進程的某些動態特性可以調整，即系統在進程生存期內經常修改各進程的優先級。一般根據進程占有CPU時間的長短及就緒進程等待CPU的時間長短來確定。3.2調度算法——進程調度3.2調度算法——進程調度3.2調度算法——進程調度2、時間片輪轉調度算法通過時間片輪轉，提高進程并發性和響應時間特性，從而提高資源利用率。將系統中所有的就緒進程按照FCFS原則，排成一個隊列。每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。在一個時間片結束時，發生時鐘中斷。調度程序據此暫停當前進程的執行，將其送到就緒隊列的末尾，并通過CPU現場切換執行當前的隊首進程。進程可以未使用完一個時間片，就出讓CPU（如阻塞）。時間片輪轉法：固定時間片可變時間片：根據系統的當前負載情況，每當一輪開始時調整時間片的大小，此時間片值作為這一輪的時間片保持不變，在此輪中新到達的就緒進程暫不進入就緒隊列，等待下一輪一并進入。3.2調度算法——進程調度【時間片長度變化的影響】：過長－>退化為FCFS算法，進程在一個時間片內都執行完，響應時間長。過短－>用戶的一次請求需要多個時間片才能處理完，CPU現場切換次數增加，響應時間長。【對響應時間的要求】：

T(響應時間)=N(進程數目)*q(時間片)【時間片長度的影響因素】：就緒進程的數目：數目越多，時間片越小（當響應時間一定時）。系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使響應時間，平均周轉時間和平均帶權周轉時間延長。3.2調度算法——進程調度3.2調度算法——進程調度3.2調度算法——進程調度3、多隊列輪轉調度算法將系統內進程按各自屬性分為若干類，每一類組織一個就緒隊列，并為每一個就緒隊列規定一個調度優先級，且還可以為不同的隊列規定不同的調度算法。多隊列算法首先將CPU分配給高優先級隊列中的進程。只有當高優先級隊列為空時，再將CPU分配給較低優先級隊列中的進程。各隊列需采用的調度算法也應根據系統設計目標而具體確定。例：分時批處理系統中，前臺作業（終端）、后臺作業（批處理作業）3.2調度算法——進程調度4、多級反饋隊列調度算法設置多個就緒隊列，分別賦予不同的優先級，隊列1的優先級最高，其他逐級降低。每隊列分配不同的時間片，規定優先級越低則時間片越長。新進程就緒后，先投入隊列1的末尾，按FCFS算法調度。若一個時間片未能執行完，則降低投入到隊列2的末尾；依此類推，降低到最后的隊列，則按“時間片輪轉”算法調度直到完成。進程由于等待事件而放棄CPU后,進入等待隊列,一旦等待的事件發生,則回到原來的就緒隊列。僅當較高優先級的隊列為空，才調度較低優先級的隊列中的進程執行。如果進程執行時有新進程進入較高優先級的隊列，則搶先執行新進程，并把被搶先的進程投入原隊列的末尾。3.2調度算法——進程調度進程調度—多級反饋隊列調度算法的特點合理地考慮了分時系統平均響應時間，考慮了批處理系統短進程優先，能使I/O為主的進程優先于CPU為主的進程。這種調度算法能適用于同時支持分時、實時、批處理的通用操作系統。3.2調度算法——進程調度5、實時調度算法實時調度的基本要求：保證計算機在規定的時間內對外部事件的請求作出響應。強實時系統：計算機對事件的響應必須在規定的時間內（最終期限）弱實時系統：允許偶爾的失誤實時調度策略（動態調度和靜態調度）靜態調度：進程的調度順序是預先規定好的動態調度：進程的調度順序是動態變化的且在運行時決定等級單調算法：它根據各個進程的觸發事件的發生順序給每個進程賦予一個優先權，運行時，調度者總是運行優先權最高的可執行進程，調度方式可以采用搶先式。最早最終期限優先法：進程調度的優先級根據相應事件的最終期限的時間來確定，最終期限的時間越短，其優先級越高。最小松弛時間優先：系統首先為每個進程計算它可以讓出的時間（松弛時間），調度時系統選取松弛時間最小的運行。練習題：在所學的調度算法中，對所有進程和作業都是公平合理的調度算法是

A；最有利于提高系統吞吐量的作業調度算法是

B；能兼顧作業等待時間和作業執行時間調度算法是

C；最有利于提高資源的使用率、能使短作業、長作業及交互作業用戶都比較滿意的調度算法是

D；為實現人機交互作用應采用調度算法是

E；能對緊急作業進行及時處理的調度算法是

F。A—F：(1)FCFS調度算法；(2)短作業優先調度算法；

(3)時間片輪轉法；(4)多級反饋隊列調度算法；

(5)高響應比優先算法；

(6)基于優先權的剝奪調度算法。練習題：1．操作系統的主要性能參數：

A指的是單位時間內系統處理的作業量。A：（1）周轉時間；（2）處理時間；（3）消逝時間；（4）利用率；（5）生產率；（6）吞吐量。2．在所學的調度算法中，為實現人機交互作用應采用調度算法是

A。A：（1）FCFS調度算法；（2）短作業優先調度算法；（3）時間片輪轉法；（4）多級反饋隊列調度算法；（5）高響應比優先算法；（6）基于優先權的剝奪調度算法。3.時間片輪轉算法中時間片足夠大時，該算法退化為

A。

A：（1）時間片輪轉算法（2）先進先出調度算法(3)高響應比優先算法（4）短作業優先算法4.作業調度是按某種算法從磁盤輸入井的

A中選一個作業裝入主存運行。

A：（1）就緒隊列（2）等待隊列（3）作業后備隊列（4）提交隊列5.作業調度與進程調度的主要區別是：

A。A：（1）作業調度比進程調度頻繁（2）兩種調度的算法完全不同（3）兩種調度的性能指標完全不同(4)進程調度比作業調度頻繁3.3死鎖一、死鎖的概念死鎖：指多個進程在運行的時候因為競爭資源而陷入的一種僵局，陷入這種僵局的進程，若無外力的作用將無法再向前推進。產生死鎖的原因：1、進程對資源的競爭當若干進程需求資源的總數大于系統能提供的資源數時，進程間就會出現競爭資源的現象，若管理不當就可能引起死鎖。2、資源分配策略如果按某種資源分配策略分配資源時使得某些進程各自占用了部分資源后又都在等待其他進程所占的資源，且互不相讓，則出會引起死鎖。3、并發進程執行速度并發進程執行的速度不能由進程自己來控制，如果協調不好的話也會出現循環等待資源的情況。

例：系統有打印機、讀卡機各一臺，被進程P、Q共享。兩個進程并發執行，按以下順序請求和釋放資源：進程P A1：請求讀卡機

A2：請求打印機

A3：釋放讀卡機

A4：釋放打印機進程Q B1：請求打印機B2：請求讀卡機

B3：釋放讀卡機

B4：釋放打印機A1、A2、A3、A4、B1、B2、B3、B4B1、B2、B3、B4、A1、A2、A3、A4A1、A2、B1、B2、A3、A4、B3、B4A1、B1、A2、B2、A3、B3、A4、B4分析上面四種執行順序哪個可能會產生死鎖產生死鎖的必要條件

從以上分析可見，如果在計算機系統中同時具備下面四個必要條件時，那麼會發生死鎖。換句話說，只要下面四個條件有一個不具備，系統就不會出現死鎖。

〈1〉互斥條件。即某個資源在一段時間內只能由一個進程占有，不能同時被兩個或兩個以上的進程占有。這種獨占資源如CD-ROM驅動器，打印機等等，必須在占有該資源的進程主動釋放它之后，其它進程才能占有該資源。這是由資源本身的屬性所決定的。如獨木橋就是一種獨占資源，兩方的人不能同時過橋。

〈2〉不可搶占條件。進程所獲得的資源在未使用完畢之前，資源申請者不能強行地從資源占有者手中奪取資源，而只能由該資源的占有者進程自行釋放。如過獨木橋的人不能強迫對方后退，也不能非法地將對方推下橋，必須是橋上的人自己過橋后空出橋面（即主動釋放占有資源），對方的人才能過橋。

〈3〉占有且申請條件。進程至少已經占有一個資源，但又申請新的資源；由于該資源已被另外進程占有，此時該進程阻塞；但是，它在等待新資源之時，仍繼續占用已占有的資源。還以過獨木橋為例，甲乙兩人在橋上相遇。甲走過一段橋面（即占有了一些資源），還需要走其余的橋面（申請新的資源），但那部分橋面被乙占有（乙走過一段橋面）。甲過不去，前進不能，又不后退；乙也處于同樣的狀況。

〈4〉循環等待條件。存在一個進程等待序列{P1，P2，...，Pn}，其中P1等待P2所占有的某一資源，P2等待P3所占有的某一源，......，而Pn等待P1所占有的的某一資源，形成一個進程循環等待環。就像前面的過獨木橋問題，甲等待乙占有的橋面，而乙又等待甲占有的橋面，從而彼此循環等待。

上面我們提到的這四個條件在死鎖時會同時發生。也就是說，只要有一個必要條件不滿足，則死鎖就可以排除。解決死鎖的對策1、設計無死鎖的系統兩種途徑：預防死鎖、避免死鎖2、允許系統出現死鎖然后設法排除它加死鎖檢測手段---一旦發現死鎖能夠進行排除的死鎖解除手段二、死鎖的預防1、靜態分配資源策略每個進程在開始執行前就申請它所需要的全部資源，僅當系統能滿足進程的資源申請要求且把資源分配給進程后，該進程才能開始執行。（打破了（3）占有并申請）特點：簡單安全，資源利用率低2、按序分配資源策略把系統中所有資源排一個順序，對第一個資源給一個確定的編號，規定任何一個進程申請兩個以上資源時總是先申請編號小的資源，后申請編號大的資源。（打中〈4〉循環等待條件）

特點：可以提高資源利用率，但資源的使用與實際使用順序不一致，給用戶編制程序帶來麻煩。3、搶奪式分配資源策略僅當一個進程已經占有了某些資源又要申請新資源，而系統這時又不能滿足其他資源的要求（已被其他進程占用）必須等待時，系統才可以搶奪該進程已占有的資源。（適用于CPU、內存，不能完全防止死鎖）三、死鎖的避免1、系統的安全與不安全狀態系統能按某種進程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。★只要系統處于安全狀態，系統就不會發生死鎖★在系統處于不安全狀態下未必一定發生死鎖，但是安全狀態下的系統是一定不會發生死鎖的。我們通過一個例子來說明安全性。假定系統中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P310495223由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統把剩余3臺中的1臺分配給P3，則系統便進入不安全狀態。因為，此時也無法再找到一個安全序列，例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結果導致死鎖。現有同類資源12個供3個進程共享，假定進程所需資源和已占資源的情況如下表所示。3個進程在執行中又都提出申請一個資源的要求，回答：a.如果先滿足進程A的要求，系統將會出現什么現象？解釋之。

b.你認為應按怎樣的次序分配資源才合適？為什么？答：a.在當前狀態下，尚余2個資源可供分配，如果先滿足進程A的要求，把其中1個資源分配給A進程，此時A、B、C進程仍未擁有足夠資源完成任務。系統進入不安全狀態，隨著進程的繼續執行，剩余的1個資源無論分給哪個進程，均導至所有進程進入等告待而出現死鎖。b.根據目前的資源占用情況，應該先滿足B的要求，把剩下的2個資源分配給他，這樣，B進程可執行完畢歸還系統6個資源。這6個資源可以滿足A和C進程的資源需求，從而使系統處于安全狀態。

2、利用銀行家算法避免死鎖算法：把操作系統比作銀行家，操作系統管理的各種資源比作銀行的周轉資金，申請資源的進程比作銀行借款的主顧。銀行家占有有限的資金，他不可能滿足所有借款人的請求，但可以滿足一部分人的借款請求，等這些人歸還后，又可把這筆資金借給其他人，其原則是不能使銀行家的錢被借完，使資金無法周轉。特點：可避免死鎖，比靜態資源分配法資源利用率高

但資源分配保守，每次分配前均要花較長時間計算時間，系統開銷較大，而且必須知道每個進程對資源的最大需求量。3、區分死鎖的避免與死鎖的防止預防：是在運行之前，預先防止死鎖的產生（主要通過破壞產生死鎖的四個必要條件中任何一個來實現的）避免：是系統運行過程中注意避免死鎖的發生（要求系統每當在進程申請資源時，都應根據一定的算法判斷，僅當系統處于安全狀態時才把資源分配給進程，使系統一直處于安全狀態之中）四、死鎖的檢測和解除死鎖的檢測：系統定時運行一個檢查程序，來檢測系統中是否存在死鎖，當檢測到死鎖時再設法解除死鎖。1.資源分配圖凡屬于E中的一個邊e∈E，都連接著P中的一個結點和R中的一個結點，e={pi,rj}是資源請求邊，由進程pi指向資源rj，它表示進程pi請求一個單位的rj資源。e={rj,pi}是資源分配邊，由資源rj指向進程pi,它表示把一個單位的資源rj分配給進程pi。2、利用資源圖可以檢測系統中是否存在死鎖進程，判定死鎖的法則如下：1）如果進程資源圖中無環路，則此時系統內不存在死鎖。2）如果進程資源圖中有環路，且處于環路內的每類資源均只有一個，則此時系統內存在死鎖；處于環路內的進程就是卷入死鎖的進程。3）如果進程資源圖中有環路，但處于環路內的每類資源個數不全為一個，則此時系統內是否存在死鎖，還要化簡進程資源圖才能判定。3、進程資源的化簡過程1）找出一個既不阻塞又非孤立的進程節點Pi2）進程Pi所占有的資源全部釋放時，可喚醒等待此資源而進入阻塞的進程Pj，使原來處于阻塞的進程可能變成非阻塞進程。3）若進程資源狀態圖通過上述簡化步驟后，都成為孤立點，則該圖是可完全化簡的，并且該進程資源圖所代表的系統狀態是安全的。4、死鎖定理對于較復雜的資源狀態圖可能存在著多個非阻塞點，若我們從不同的點開始化簡是否可以得到同一個化簡圖呢？經證明：一個給定的進程資源圖的所有化簡順序將導致同一個不可化簡圖。所以我們進一步可得到如下的死鎖定理：若S是死鎖狀態的話，當且僅當S的進程資源圖是不可完全化簡的。如果得到一個可完全化簡的進程資源狀態圖，我們就稱該狀態為安全態，反之為死鎖狀態。3、死鎖的解除當死鎖檢測程序檢測到有死鎖存在時，一般采用兩種方式來解除死鎖。1）刪除法：即終止一個或幾個涉及死鎖的進程的執行，收回它們所占的資源進程再分配，以破壞循環等2）剝奪法：即從涉及死鎖的一個或幾個進程中搶奪資源，把奪來的資源再分配給卷入死鎖的其他進程，直至死鎖解除11.某系統中有10臺打印機，有三個進程P1，P2，P3分別需要8臺，7臺和4臺。若P1，P2，P3已申請到4臺，2臺和2臺。試問：按銀行家算法能安全分配嗎？請說明分配過程。系統能為進程P3分配二臺打印機。因為盡管此時10臺打印機已分配給進程P14臺，P22臺和P34臺，全部分配完，但P3已分配到所需要的全部4臺打印機，它不會對打印機再提出申請，所以它能順利運行下去，能釋放占用的4臺打印機，使進程P1，P2均可能獲得乘余的要求4臺和5臺，按銀行家算法是安全的。一臺計算機有8臺磁帶機，它們由N個進程競爭使用，每個進程可能需要3臺磁帶機。請問N為多少時，系統沒有死鎖危