調(diào)度是系統(tǒng)將計算機資源分配給進程。在單道程序環(huán)境下，只有一個進程存在，計算機的所有資源由一個進程獨占，沒有資源競爭問題。在多道程序環(huán)境下，多個進程并發(fā)運行，各進程之間存在資源的相互競爭，特別是對處理器資源的競爭，從而影響到系統(tǒng)性能。處理器調(diào)度指在多道程序環(huán)境下將處理器分配給各進程。在處理器調(diào)度中，合理的調(diào)度算法能夠提高處理器的處理能力和系統(tǒng)性能，滿足用戶需求。第3章處理機調(diào)度與死鎖2/136第3章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測和解除3.1處理器調(diào)度的層次在內(nèi)存中并發(fā)的進程之間構(gòu)成的是一種競爭使用處理器的關(guān)系。低級調(diào)度將處理器分配給進程。低級調(diào)度受到內(nèi)存中用戶作業(yè)數(shù)的影響，處理器調(diào)度不只是低級調(diào)度問題，還與內(nèi)存中能夠接納用戶作業(yè)的個數(shù)有關(guān)，與作業(yè)調(diào)度有關(guān)，作業(yè)調(diào)度為高級調(diào)度。為了減輕內(nèi)存的負擔，外存作為內(nèi)存的補充，進程可以在外存與內(nèi)存之間對換。對換到外存的進程調(diào)入內(nèi)存為中級調(diào)度，中級調(diào)度也會影響內(nèi)存中進程的調(diào)度，處理器調(diào)度與中級調(diào)度有關(guān)。3.1處理器調(diào)度的層次處理器調(diào)度劃分為3個層次：高級調(diào)度、中級調(diào)度和低級調(diào)度。進程調(diào)度是處理器調(diào)度的核心。用戶作業(yè)從提交給系統(tǒng)開始，直到運行結(jié)束退出系統(tǒng)為止，將經(jīng)歷高級調(diào)度、中級調(diào)度和低級調(diào)度。3.1.1高級調(diào)度

1．作業(yè)及作業(yè)分類

作業(yè)由一組統(tǒng)一管理和操作的進程集合構(gòu)成，是用戶要求計算機系統(tǒng)完成的一項相對獨立的工作。作業(yè)可以是完成了編譯、鏈接之后的一個用戶程序，也可以是用各種命令構(gòu)成的一個腳本。根據(jù)需要處理工作的類型，作業(yè)分為計算型作業(yè)和I/O型作業(yè)。在操作系統(tǒng)中，將需要CPU處理為主的作業(yè)稱為計算型作業(yè)；將以I/O過程為主的作業(yè)稱為I/O型作業(yè)。一般情況下，操作系統(tǒng)管理會對這兩種作業(yè)進行區(qū)別對待：I/O為主的作業(yè)，由于等待I/O過程需要更多的時間，執(zhí)行更慢；計算型為主的作業(yè)等待I/O過程需要的時間更短，執(zhí)行更快。3.1.1高級調(diào)度

作業(yè)也可以按照提交方式不同分為批處理作業(yè)和終端型作業(yè)。在多道程序環(huán)境下，用戶的批處理作業(yè)被提交到系統(tǒng)的磁盤上，以批處理后備隊列的形式進行組織，這樣的作業(yè)為批處理作業(yè)。批處理作業(yè)需要作業(yè)調(diào)度將后備隊列上的作業(yè)調(diào)度到內(nèi)存才能執(zhí)行。對終端型作業(yè)用戶通過終端登錄到系統(tǒng)，直接將作業(yè)置于內(nèi)存中。終端型作業(yè)不需要作業(yè)調(diào)度便能執(zhí)行。3.1.1高級調(diào)度（續(xù)）作業(yè)調(diào)度按照操作系統(tǒng)預(yù)先規(guī)定的作業(yè)調(diào)度策略，從磁盤的作業(yè)后備隊列中選擇作業(yè)調(diào)入內(nèi)存，為作業(yè)分配所需要的資源并建立與作業(yè)相對應(yīng)的進程。當作業(yè)運行的準備工作完成后，作業(yè)調(diào)度啟動作業(yè)運行。在作業(yè)運行結(jié)束后，作業(yè)調(diào)度歸還并釋放作業(yè)占用的資源，結(jié)束作業(yè)。作業(yè)調(diào)度也稱為高級調(diào)度或長程調(diào)度。作業(yè)調(diào)度模型如圖3.1所示。圖3.1作業(yè)調(diào)度模型提交作業(yè)后備隊列用戶作業(yè)進程就緒隊列處理器進程阻塞隊列高級調(diào)度終端交互用戶3.1.1高級調(diào)度（續(xù)）作業(yè)與進程之間存在著緊密的關(guān)系：一個作業(yè)可能由一個進程組成，運行在一個進程下；也可能由多個進程組成，運行在多個進程下。作業(yè)是計算機處理任務(wù)的實體，進程是計算機處理任務(wù)的執(zhí)行體。沒有作業(yè)，進程無事可做；沒有進程，作業(yè)不能完成。一個作業(yè)中創(chuàng)建多少個進程，有多少個進程運行由作業(yè)的擁有者根據(jù)需要決定。一個系統(tǒng)能夠接納作業(yè)的個數(shù)由系統(tǒng)的資源決定，特別是處理器和內(nèi)存資源。一個系統(tǒng)能夠接納作業(yè)的個數(shù)稱為系統(tǒng)的多道度，也稱為系統(tǒng)的多道程序度。3.1.1高級調(diào)度（續(xù)）當內(nèi)存中運行的作業(yè)太多時，會影響到系統(tǒng)的服務(wù)質(zhì)量，影響到程序的正常執(zhí)行。操作系統(tǒng)為了保證進入系統(tǒng)的用戶作業(yè)能夠順利運行，會限制系統(tǒng)的多道度。當多道度達到限值時，只有完成一個作業(yè)后另一個作業(yè)才能進入。3.1.1高級調(diào)度（續(xù)）作業(yè)調(diào)度中操作系統(tǒng)需要完成的工作：確定作業(yè)的數(shù)據(jù)結(jié)構(gòu)。操作系統(tǒng)為每個進入系統(tǒng)的作業(yè)分配一個與進程控制塊（PCB）類似的作業(yè)控制塊（JCB），作業(yè)控制塊中包括：作業(yè)的名稱、作業(yè)對資源的需求信息、作業(yè)的資源使用信息、作業(yè)的控制方式、作業(yè)類型、作業(yè)優(yōu)先級和作業(yè)狀態(tài)。作業(yè)控制塊是作業(yè)的標志，存在于作業(yè)的整個過程中，只有作業(yè)完成或退出系統(tǒng)時，作業(yè)控制塊才被撤銷。操作系統(tǒng)根據(jù)作業(yè)控制塊中的信息對作業(yè)進行調(diào)度和管理。作業(yè)名稱由用戶提供，系統(tǒng)將其寫到作業(yè)控制塊中。3.1.1高級調(diào)度（續(xù)）作業(yè)對資源的需求信息包括估計作業(yè)執(zhí)行時間、作業(yè)最遲完成時間、作業(yè)要求的內(nèi)存量、作業(yè)要求輸入輸出設(shè)備的類型和臺數(shù)、作業(yè)要求的文件量和輸出量，這些信息由用戶提供。作業(yè)的資源使用信息包括作業(yè)進入系統(tǒng)時間、作業(yè)開始執(zhí)行時間、作業(yè)已經(jīng)執(zhí)行時間、作業(yè)在內(nèi)存中的地址、作業(yè)被分配的輸入輸出設(shè)備臺號，這些信息由操作系統(tǒng)寫入。作業(yè)的控制方式分為聯(lián)機和脫機兩種，表示該作業(yè)是聯(lián)機操作還是脫機操作。作業(yè)類型分為CPU繁忙型作業(yè)和I/O繁忙型作業(yè)，或批處理輸入作業(yè)和終端作業(yè)。3.1.1高級調(diào)度（續(xù)）作業(yè)優(yōu)先級反映作業(yè)運行的緊急程度，可由用戶指定，也可由系統(tǒng)根據(jù)作業(yè)類型、作業(yè)對資源的需求、作業(yè)要求的運行時間和系統(tǒng)當前狀況動態(tài)指定。作業(yè)狀態(tài)指作業(yè)當前所處的狀態(tài)，可分為提交狀態(tài)、后備狀態(tài)、運行狀態(tài)及完成狀態(tài)。當作業(yè)運行結(jié)束時，首先釋放作業(yè)所占用的全部資源，再由作業(yè)調(diào)度程序調(diào)用存儲器管理程序收回該作業(yè)的作業(yè)控制塊空間，從而撤銷作業(yè)。確定作業(yè)的調(diào)度算法。操作系統(tǒng)調(diào)度程序在調(diào)度作業(yè)前需要確定作業(yè)的調(diào)度算法，然后再按照確定的作業(yè)調(diào)度算法從磁盤的作業(yè)后備隊列中選擇作業(yè)進入內(nèi)存。3.1.1高級調(diào)度（續(xù)）為作業(yè)分配資源。作業(yè)運行需要各種資源，包括硬件資源和軟件資源。硬件資源有內(nèi)存、處理器和各種輸入輸出設(shè)備。軟件資源有各種共享變量等。作業(yè)的資源分配策略主要考慮的是作業(yè)所包含的進程所需要的資源，在一般情況下，資源按照進程需求進行分配。資源分配中需要避免由進程之間的資源競爭而造成的死鎖等現(xiàn)象?；厥兆鳂I(yè)資源。作業(yè)完成后，作業(yè)調(diào)度程序除了要輸出相關(guān)的作業(yè)信息之外，還要回收作業(yè)所占用的全部資源，撤銷與作業(yè)相關(guān)的進程和作業(yè)控制塊。3.1.1高級調(diào)度（續(xù)）在作業(yè)調(diào)度工作中，大多數(shù)工作由作業(yè)的調(diào)度程序完成。但是，內(nèi)存和輸入輸出設(shè)備的分配和釋放不是由作業(yè)調(diào)度程序完成，而是由存儲器管理和設(shè)備管理程序完成的。作業(yè)調(diào)度程序只是將作業(yè)對內(nèi)存的要求和對設(shè)備的要求轉(zhuǎn)交給相應(yīng)的內(nèi)存管理程序和設(shè)備管理程序，由內(nèi)存管理程序和設(shè)備管理程序完成內(nèi)存和設(shè)備的分配與回收。3.1.1高級調(diào)度（續(xù)）3．作業(yè)的狀態(tài)為了更好地描述作業(yè)，可以將作業(yè)分為不同的狀態(tài)。作業(yè)的狀態(tài)包括：提交狀態(tài)、后備狀態(tài)、執(zhí)行狀態(tài)和完成狀態(tài)。提交狀態(tài):用戶將作業(yè)提交給操作系統(tǒng)，等待輸入程序和數(shù)據(jù)到磁盤。后備狀態(tài):系統(tǒng)接收輸入的用戶作業(yè)，并將其放入計算機磁盤。作業(yè)在磁盤上以后備隊列形式進行組織，等待作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)度到內(nèi)存。執(zhí)行狀態(tài):作業(yè)被調(diào)度到內(nèi)存，為作業(yè)分配資源并為其創(chuàng)建與之對應(yīng)的進程，進程獲得CPU，開始運行。3.1.1高級調(diào)度（續(xù)）完成狀態(tài):從作業(yè)的第一個進程完成開始，直到作業(yè)所有的進程完成，釋放作業(yè)所占用的資源，退出系統(tǒng)的整個進程。作業(yè)狀態(tài)及其轉(zhuǎn)換如圖3.2所示。執(zhí)行狀態(tài)就緒運行阻塞后備狀態(tài)提交狀態(tài)完成狀態(tài)圖3.2作業(yè)狀態(tài)及其轉(zhuǎn)換3.1.1高級調(diào)度（續(xù)）作業(yè)狀態(tài)的劃分比進程狀態(tài)的劃分更粗，進程是作業(yè)全部狀態(tài)中的一個階段體現(xiàn)。作業(yè)調(diào)度將作業(yè)從后備狀態(tài)轉(zhuǎn)換到內(nèi)存執(zhí)行狀態(tài)。作業(yè)執(zhí)行狀態(tài)包含作業(yè)所對應(yīng)進程的就緒、運行和阻塞狀態(tài)。在分時操作系統(tǒng)和實時操作系統(tǒng)中，終端用戶的作業(yè)直接送入到內(nèi)存，不需要作業(yè)調(diào)度。操作系統(tǒng)需要完成的功能是決定是否能夠為作業(yè)創(chuàng)建進程。分時操作系統(tǒng)和實時操作系統(tǒng)也支持批處理作業(yè)，在批處理作業(yè)存在時，也能夠完成作業(yè)調(diào)度。3.1.2中級調(diào)度

中級調(diào)度又稱為中程調(diào)度，是為了提高內(nèi)存利用率和平衡系統(tǒng)負載而采取的一種利用外存補充內(nèi)存的措施。在多進程環(huán)境下，內(nèi)存中的多個進程，其中有些進程可能需要掛起，這些進程暫時不參與對處理器的競爭。為了充分利用內(nèi)存資源，系統(tǒng)會采用進程對換的方法將進程換出到外存，將這些進程占用的內(nèi)存空間釋放，讓內(nèi)存能夠接納新的進程或使得內(nèi)存中的進程能夠更快推進。當被換出到外存中的進程掛起時間到時，又需要將這些進程換入到內(nèi)存。中級調(diào)度是在換出內(nèi)存的進程中確定需要進入內(nèi)存的進程。3.1.2中級調(diào)度

當進程需要換入內(nèi)存，而內(nèi)存資源不充足時，則系統(tǒng)需要選擇內(nèi)存中的進程換出外存，讓出內(nèi)存空間給進入內(nèi)存的進程。中級調(diào)度根據(jù)內(nèi)存中能夠接納的進程數(shù)來平衡系統(tǒng)負載，起到在一定時間內(nèi)平滑和調(diào)整系統(tǒng)負載的作用。1．低級調(diào)度低級調(diào)度又稱為進程調(diào)度、短程調(diào)度，是按照一定的調(diào)度算法從內(nèi)存的就緒進程隊列中選擇進程，為進程分配處理器。進程調(diào)度發(fā)生在內(nèi)存中的就緒進程，被調(diào)度的進程從內(nèi)存就緒到處理器中執(zhí)行的過程，該過程很短，被稱為短程調(diào)度。中級調(diào)度位于高級調(diào)度與低級調(diào)度之間，被稱為中程調(diào)度。中級調(diào)度主要用于內(nèi)存管理，特別是虛擬存儲器管理。3.1.3低級調(diào)度

作業(yè)調(diào)度發(fā)生進程位于外存與進入計算機內(nèi)存之間，經(jīng)過的過程最長，因此，作業(yè)調(diào)度被稱為長程調(diào)度。進程調(diào)度與作業(yè)調(diào)度和中級調(diào)度比較，進程調(diào)度發(fā)生的頻率最高，作業(yè)調(diào)度發(fā)生的頻率最低。3.1.3低級調(diào)度

處理器調(diào)度的三級模型如圖3.3所示。3.1.3低級調(diào)度圖3.3處理器三級調(diào)度模型進程掛起就緒隊列進程阻塞隊列進程掛起阻塞隊列進程就緒隊列完成中級調(diào)度低級調(diào)度處理器高級調(diào)度作業(yè)后備隊列交互式用戶提交用戶作業(yè)3.1.3低級調(diào)度（續(xù)）2．引起進程調(diào)度的主要原因

（1）處理器執(zhí)行的進程完成任務(wù)，處理器空閑；（2）處理器執(zhí)行的進程轉(zhuǎn)入阻塞狀態(tài)，此時處理器空閑；（3）處理器執(zhí)行的進程被其它進程搶占；（4）處理器執(zhí)行的進程被掛起。3.1.3低級調(diào)度（續(xù)）3．進程調(diào)度中的基本機制（1）排隊器。為使進程調(diào)度時能夠快速有效地找到就緒隊列中的每個進程，首先應(yīng)該按照一定的方式將進程就緒隊列排成一個或多個隊列。（2）分派程序。分派程序?qū)⒏鶕?jù)進程調(diào)度策略將所選中的進程從就緒隊列中移出，然后進行進程上下文的切換，并將處理器分配給進程。（3）上下文切換機制。上下文切換機制是指在操作系統(tǒng)分派程序的執(zhí)行下完成處理器的切換過程，實現(xiàn)進程上下文切換3.1.3低級調(diào)度（續(xù)）4．進程切換的實現(xiàn)進程切換需要完成進程上下文切換，進程狀態(tài)、進程等待時間等信息的改變。新、老進程切換如圖3.4所示。老進程新進程CPU圖3.4進程調(diào)度中的進程切換進程切換過程描述？3.1.3低級調(diào)度（續(xù)）進程切換需要完成以下工作：保存并恢復(fù)處理器信息。處理器中的寄存器保存了當前正在執(zhí)行進程的相關(guān)數(shù)據(jù)和狀態(tài)，在進程被切換時，必須將進程的這些信息保存到進程控制塊中，以便進程被處理器再次執(zhí)行時，能夠?qū)⑦M程的斷點信息從進程控制塊拷貝回處理器寄存器中，保證處理器能夠從進程的上次斷點開始繼續(xù)向前推進。處理器中寄存器信息寫到老進程的進程控制塊中，新進程的進程控制塊信息被拷貝到處理器的寄存器中。3.1.3低級調(diào)度（續(xù)）更新進程控制塊中的進程狀態(tài)、進程達到時間、進程等待時間、進程優(yōu)先級變化等信息，并將進程控制塊移到相應(yīng)的進程隊列。被切換的進程狀態(tài)從執(zhí)行改為就緒或阻塞，其進程控制塊也被插入就緒隊列或阻塞隊列。同樣，被分配處理器的進程，其狀態(tài)從就緒改為執(zhí)行，進程控制塊從就緒隊列中移出。更新存儲器管理數(shù)據(jù)結(jié)構(gòu)，維護進程的代碼段和數(shù)據(jù)段。3.1.3低級調(diào)度（續(xù)）5．進程調(diào)度中的非搶占（nonpreemptive）調(diào)度和搶占（preemptive）調(diào)度

非搶占式調(diào)度是一種通常的調(diào)度方式，在非搶占調(diào)度中，處理器分配給進程后，一直到進程結(jié)束或進程阻塞，進程才自動放棄處理器。非搶占調(diào)度存在什么問題？若執(zhí)行進程正好在執(zhí)行一個沒有資源的無限循環(huán)，則執(zhí)行進程不會放棄處理器，所有的就緒進程會永久等待，系統(tǒng)進入了一種僵持的狀態(tài)。解決方法?如果此時系統(tǒng)能夠自身定期強制執(zhí)行進程中斷，則可以避免這種僵持狀態(tài)。3.1.3低級調(diào)度（續(xù)）強制執(zhí)行進程中斷的調(diào)度方式為搶占調(diào)度方式，又稱為剝奪調(diào)度方式，是指一個進程正在處理器中運行時，操作系統(tǒng)可以根據(jù)規(guī)定的搶占原則，將已經(jīng)分配給進程的處理器從進程剝奪，并分配給其他的進程。在系統(tǒng)允許搶占調(diào)度，并滿足搶占條件的情況下，系統(tǒng)才可以采用搶占調(diào)度方式。滿足搶占條件的進程能夠搶占當前正在執(zhí)行進程的處理器。被搶占的進程狀態(tài)從執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)，其進程控制塊進入到進程就緒隊列。3.1.3低級調(diào)度（續(xù)）具有搶占的進程狀態(tài)如圖3.5所示。圖3.5進程的搶占與非搶占調(diào)度阻塞態(tài)就緒態(tài)運行態(tài)終止態(tài)搶占非搶占進程調(diào)度非搶占3.1.3低級調(diào)度（續(xù)）搶占條件也稱為搶占原則，可歸納為如下：時間片在分時系統(tǒng)中，當進程運行的時間片到時，進程會被搶占，處理器被分配給其他的就緒進程。分時操作系統(tǒng)采用了基于時間片的搶占調(diào)度方法，如UNIX操作系統(tǒng)和Linux操作系統(tǒng)。優(yōu)先級當就緒隊列上有優(yōu)先級比當前正在處理器運行的進程的優(yōu)先級高的進程時，系統(tǒng)將處理器從當前進程剝奪，優(yōu)先級高的進程得到處理器?；趦?yōu)先級的進程搶占調(diào)度被很多操作系統(tǒng)所采用，特別是實時操作系統(tǒng)。在UNIX操作系統(tǒng)中，當用戶態(tài)進程完成系統(tǒng)調(diào)用后從核心態(tài)返回用戶態(tài)繼續(xù)運行時，處理器可能被處于核心態(tài)執(zhí)行的其他進程搶占。3.1.3低級調(diào)度（續(xù)）短進程當就緒隊列中有進程的執(zhí)行時間比當前正在處理器運行的進程需要的執(zhí)行時間更短時，當前進程被搶占，系統(tǒng)將處理器分配給更短的進程。搶占是一種靈活和有效的處理進程調(diào)度方法，避免了進程永遠不放棄處理器的現(xiàn)象，也為緊急情況下的進程運行創(chuàng)造了機會。3.1.3低級調(diào)度（續(xù)）搶占帶來的問題：增加系統(tǒng)開銷進程間共享數(shù)據(jù)不一致問題在進程之間存在數(shù)據(jù)共享時，如果一個進程的數(shù)據(jù)更新尚未結(jié)束而被搶占，得到處理器的進程恰好又要讀取這部分共享數(shù)據(jù)，此時讀取的數(shù)據(jù)可能存在不一致的問題。這樣，操作系統(tǒng)必須采取一定的措施保證數(shù)據(jù)的一致性。影響操作系統(tǒng)內(nèi)核程序設(shè)計問題如果搶占發(fā)生在操作系統(tǒng)內(nèi)核程序執(zhí)行期間，如系統(tǒng)調(diào)用期間，核心程序可能正在改變核心中的重要數(shù)據(jù)時被搶占，從而造成操作系統(tǒng)核心出現(xiàn)問題，影響系統(tǒng)的穩(wěn)定性。3.1.3低級調(diào)度（續(xù)）在操作系統(tǒng)設(shè)計時應(yīng)考慮避免核心調(diào)用時被搶占的情況。如UNIX操作系統(tǒng)在設(shè)計時規(guī)定系統(tǒng)調(diào)用期間不能搶占。內(nèi)核程序執(zhí)行時不能被搶占又影響系統(tǒng)實時性，特別是在此期間系統(tǒng)不能接收中斷，造成輸入信息丟失，輸出信息被重寫。UNIX、Linux、微軟公司的Windows操作系統(tǒng)、蘋果公司的MacOS都采用了搶占調(diào)度方式。3.2評價調(diào)度算法的準則

處理器調(diào)度算法也稱為調(diào)度策略，用于控制對處理器的分配，是處理器調(diào)度中非常重要的環(huán)節(jié)。不同的調(diào)度策略，對系統(tǒng)性能的影響不同。適合操作系統(tǒng)的調(diào)度算法，能夠提高系統(tǒng)的性能。評價調(diào)度算法從系統(tǒng)性能、用戶滿意兩方面進行考慮，充分體現(xiàn)對用戶的公平性和系統(tǒng)的高效性，既保證每個用戶有合理的處理器時間，又保證系統(tǒng)的處理器利用率高。3.2評價調(diào)度算法的準則（續(xù)）評價調(diào)度算法的準則如下：處理器利用率（CPUutilization）處理器利用率為CPU有效工作時間與CPU總的運行時間之比，即：CPU利用率

=

CPU有效工作時間/CPU總的運行時間

CPU總的運行時間

=

CPU的有效工作時間

+

CPU的空閑時間思考：理想情況下CPU的利用率是多少？100%實際應(yīng)用中，總會存在進程切換等工作，而進程切換需要時間。對于輕負載系統(tǒng)，CPU的利用率大約為40%；對于重負載系統(tǒng)，CPU的利用率最高可達90%。3.2評價調(diào)度算法的準則（續(xù)）響應(yīng)時間（responsetime）響應(yīng)時間是交互環(huán)境下用戶從鍵盤提交第1個請求開始，到系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間，或者是屏幕上顯示出結(jié)果為止的時間。響應(yīng)時間

=

從終端鍵盤輸入的請求信息傳送到處理機的時間

+

處理機對請求信息的處理時間

+

生成的響應(yīng)信息回送到終端顯示器的時間對于用戶來講，希望響應(yīng)時間越短越好。3.2評價調(diào)度算法的準則（續(xù)）周轉(zhuǎn)時間（turnaroundtime）周轉(zhuǎn)時間指用戶作業(yè)提交給操作系統(tǒng)開始到作業(yè)完成為止的時間。周轉(zhuǎn)時間Ti

=

作業(yè)在后備隊列中的等待調(diào)度時間+進程在就緒隊列上等待調(diào)度的時間+進程在CPU上的運行時間

+

進程等待I/O或其他事件發(fā)生的時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間Tf

=

作業(yè)的周轉(zhuǎn)時間Ti/系統(tǒng)為作業(yè)提供的服務(wù)時間Tsi

每個用戶都希望自己作業(yè)的周轉(zhuǎn)時間越短越好，計算機系統(tǒng)管理希望所有作業(yè)的平均周轉(zhuǎn)時間越短越好，帶權(quán)周轉(zhuǎn)時間越短越好。3.2評價調(diào)度算法的準則（續(xù)）系統(tǒng)吞吐量（throughput）單位時間內(nèi)處理的進程數(shù)目為CPU的工作成效。單位時間內(nèi)完成的進程數(shù)目為系統(tǒng)的吞吐量。在處理大而長的進程時，吞吐量可能每小時只有一個；在處理小而短的進程時，吞吐量達到每秒幾十甚至上百個。在選擇處理器的調(diào)度算法時，用戶希望CPU利用率和系統(tǒng)吞吐量越大越好，響應(yīng)時間和周轉(zhuǎn)時間越小越好。對于實時系統(tǒng)，作業(yè)調(diào)度的關(guān)鍵在于能否滿足作業(yè)的實時要求，對周轉(zhuǎn)時間等指標并不特別著重。40/1363.3調(diào)度算法學(xué)習(xí)目標：熟練掌握常見的調(diào)度算法，明確各調(diào)度算法的優(yōu)缺點。學(xué)習(xí)難點：理解各調(diào)度算法的思想，將算法在實踐中靈活應(yīng)用。41/136先來先服務(wù)算法(FirstComeFirstServed)最短作業(yè)優(yōu)先算法(ShortestJobFirst)最高響應(yīng)比優(yōu)先算法(HighestResponseRatioFirst)基于時間片的調(diào)度算法

時間片輪轉(zhuǎn)(Round-Robin)

多隊列反饋調(diào)度算法(MultilevelFeedback)

3.3.1主要的調(diào)度算法42/136算法基本思想：按照作業(yè)進入系統(tǒng)的先后次序來挑選作業(yè)，先進入系統(tǒng)的作業(yè)優(yōu)先被挑選。3.3.2先來先服務(wù)算法（FirstComeFirstServed）12345cpu43/136算法基本思想：按照作業(yè)進入系統(tǒng)的先后次序來挑選作業(yè)，先進入系統(tǒng)的作業(yè)優(yōu)先被挑選。3.2.2先來先服務(wù)算法（FirstComeFirstServed）12345cpu44/136算法舉例：（單位:小時，以十進制計）作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A06B13C25D32平均周轉(zhuǎn)時間t=平均帶權(quán)周轉(zhuǎn)時間w=06616982.67914122.41416136.59.753.14=完成時間-提交時間=周轉(zhuǎn)時間/運行時間45/136算法優(yōu)缺點：算法容易實現(xiàn)；適用于作業(yè)調(diào)度和進程調(diào)度；效率不高，只顧及作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時間的長短；不利于短作業(yè)。46/136算法思想應(yīng)用：日常生活中先來先服務(wù)思想的應(yīng)用47/136思考：一批作業(yè)幾乎同時提交，(有先后順序，但相差時間可忽略)如果作業(yè)提交的次序發(fā)生改變，結(jié)果會發(fā)生變化嗎？(一個進程所需的CPU時間分別為28、9、3)48/136A(28)B(9)C(3)283740A(28)B(9)C(3)91240A(28)B(9)C(3)312403520.318.349/136算法基本思想：

SJF算法以進入系統(tǒng)的作業(yè)所要求的CPU時間為標準，總選取估計計算時間最短的作業(yè)投入運行。3.3.3最短作業(yè)優(yōu)先算法（ShortestJobFirst）12345cpu50/136算法基本思想：

SJF算法以進入系統(tǒng)的作業(yè)所要求的CPU時間為標準，總選取估計計算時間最短的作業(yè)投入運行。3.3.3最短作業(yè)優(yōu)先算法（ShortestJobFirst）12345cpu51/136算法舉例：（單位:小時，以十進制計）作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A06B13C25D32平均周轉(zhuǎn)時間t=平均帶權(quán)周轉(zhuǎn)時間w=0661811103.31116142.86852.58.752.4FCFSt=9.75w=3.14結(jié)論：SJF的平均作業(yè)周轉(zhuǎn)時間比FCFS要小，故它的調(diào)度性能比FCFS好=完成時間-提交時間=周轉(zhuǎn)時間/運行時間52/136算法優(yōu)缺點：算法容易實現(xiàn)；適用于作業(yè)調(diào)度；能有效降低作業(yè)的平均等待時間；忽視了作業(yè)等待時間，對長作業(yè)不利，有可能導(dǎo)致長作業(yè)（進程）長期不被調(diào)度（出現(xiàn)饑餓現(xiàn)象）；要精確知道一個作業(yè)的運行時間比較困難的。53/136算法思想應(yīng)用：廚師做菜次序的安排54/136課后思考：如采用最短剩余時間優(yōu)先算法SRTF（ShortestRemainingTimeFirst），情況將如何變化。作業(yè)提交時間運行時間A06B13C25D3255/136作業(yè)提交時間運行時間首次開始首次完成再次開始再次完成周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)A06B13C25D32平均周轉(zhuǎn)時間t=平均帶權(quán)周轉(zhuǎn)時間w=01144661111161131431.8312.81.57.751.5356/1363.3.4最高響應(yīng)比優(yōu)先（HighestResponseRatioFirst）優(yōu)先權(quán)的類型：靜態(tài)優(yōu)先權(quán)—在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。動態(tài)優(yōu)先權(quán)—在創(chuàng)建進程時賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變。57/136最高響應(yīng)比優(yōu)先（HighestResponseRatioFirst）響應(yīng)比概念：公式理解：等待時間相近，服務(wù)時間越短，優(yōu)先權(quán)越高SJF服務(wù)時間相近，等待時間越長，優(yōu)先權(quán)越高FCFS算法基本思想：

HRRF算法在當前作業(yè)執(zhí)行完時,計算剩余作業(yè)的響應(yīng)比，選取響應(yīng)比最高的作業(yè)投入運行。58/136舉例：以下四個作業(yè)先后到達系統(tǒng)進入調(diào)度：

開始只有作業(yè)1，被選中執(zhí)行時間20ms；作業(yè)1執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)3被選中，執(zhí)行時間5ms；作業(yè)3執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)2被選中，執(zhí)行時間15ms；作業(yè)2執(zhí)行完畢，作業(yè)4被選中，執(zhí)行時間10ms；平均作業(yè)周轉(zhuǎn)時間T=(20+15+35+35)/4=26.25平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+15/5+35/15+35/10)/4=2.4659/136算法優(yōu)缺點：

算法適用于作業(yè)調(diào)度；既考慮作業(yè)等待時間，又考慮作業(yè)的運行時間；既照顧短作業(yè)又不使長作業(yè)的等待時間過長;

計算響應(yīng)比需要耗費時間。60/136算法思想應(yīng)用：義診就醫(yī)次序安排61/136算法基本思想：

系統(tǒng)按照固定的時間片依次輪流執(zhí)行就緒隊列中的各個進程。3.3.5時間片輪轉(zhuǎn)法（Round-Robin)ABCD62/136算法舉例：有三個進程P1、P2、P3先后到達，它們分別需要20、4和2個單位時間運行完畢。假如它們按P1、P2、P3的順序執(zhí)行，且不可剝奪，則三進程各自的周轉(zhuǎn)時間、平均周轉(zhuǎn)時間是多少個時間單位。假如它們按P1、P2、P3的順序執(zhí)行，且不可剝奪，則三進程各自的周轉(zhuǎn)時間分別為20、24、26個單位時間，平均周轉(zhuǎn)時間是23.33個時間單位。63/136算法舉例：有三個進程P1、P2、P3先后到達，分別需要20、4和2個單位時間運行完畢，假如用時間片輪轉(zhuǎn)原則的剝奪調(diào)度方式，時間片為2個時間單位。則各進程的周轉(zhuǎn)時間和平均周轉(zhuǎn)時間。02468101214161820222426p1p2p3p1p2p1p1p1p1p1p1p1p1P1、P2、P3的周轉(zhuǎn)時間分別為26、10、6平均周轉(zhuǎn)時間為（26+10+6）/3=1464/136算法優(yōu)缺點：

算法主要針對分時系統(tǒng)，適用于進程調(diào)度；對用戶的響應(yīng)及時、快速；時間片的長度確定比較困難；進程切換開銷比較大。65/136算法思想應(yīng)用：駕校培訓(xùn)安排66/136回顧與總結(jié)

算法FCFSSJFHRRFRR

項目適用范圍搶占性優(yōu)點缺點作業(yè)、進程作業(yè)作業(yè)進程非搶占兩者均可非搶占搶占簡單利于短作業(yè)均衡調(diào)度響應(yīng)及時無視特殊要求易導(dǎo)致饑餓計算耗時切換開銷大67/136算法基本思想：將就緒隊列分為N級，每個就緒隊列分配給不同的時間片，隊列優(yōu)先權(quán)越高,為每個進程所規(guī)定的執(zhí)行時間片就越??；系統(tǒng)從第一級調(diào)度，當?shù)谝患墳榭諘r，系統(tǒng)轉(zhuǎn)向第二個隊列，.....當運行進程用完一個時間片，放棄CPU時，進入下一級隊列；等待進程被喚醒時，進入原來的就緒隊列；當進程第一次就緒時，進入第一級隊列。3.2.5.2多隊列反饋調(diào)度算法68/136首先系統(tǒng)中設(shè)置多個就緒隊列；每個就緒隊列分配給不同時間片，優(yōu)先級高的為第一級隊列，時間片最小，隨著隊列級別的降低，時間片加大；各個隊列按照先進先出調(diào)度算法；一個新進程就緒后進入第一級隊列；進程由于等待而放棄CPU后，進入等待隊列，一旦等待的事件發(fā)生，則回到原來的就緒隊列；當有一個優(yōu)先級更高的進程就緒時，可以搶占CPU，被搶占進程回到原來一級就緒隊列末尾；當?shù)谝患夑犃锌諘r，就去調(diào)度第二級隊列，如此類推；當時間片到后，進程放棄CPU，回到下一級隊列。算法步驟：69/136多隊列反饋調(diào)度算法模型70/1363.2.6引起進程調(diào)度的原因正在執(zhí)行的進程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；在進程通信或同步過程中執(zhí)行了某種原語操作如P操作、阻塞、掛起原語等；在可剝奪式調(diào)度中，有比當前進程優(yōu)先權(quán)更高的進程進入就緒隊列；在時間片輪轉(zhuǎn)法中，時間片完。71/1363.2.7進程調(diào)度算法其中，RQ為就緒隊列指針，EP為運行隊列指針。72/136第3章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測和解除73/1363.3實時調(diào)度

3.3.1實現(xiàn)實時調(diào)度的基本條件

提供必要的信息(就緒時間、截止時間、處理時間、資源優(yōu)先級)；系統(tǒng)處理能力強；采用搶占式調(diào)度機制；具有快速切換機制。74/1363.3.2實時調(diào)度算法的分類非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式優(yōu)先調(diào)度算法搶占式調(diào)度算法基于時鐘中斷的搶占優(yōu)先調(diào)度算法立即搶占優(yōu)先權(quán)調(diào)度算法75/136圖3-5實時進程調(diào)度76/1363.3.3.1最早截止時間優(yōu)先即EDF(EarliestDeadlineFirst)算法

圖3-6EDF算法用于非搶占調(diào)度方式3.3.3常用的幾種實時調(diào)度算法

77/1363.3.3.2最低松弛度優(yōu)先(LLF)算法

該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。該算法主要用于可搶占調(diào)度方式中。假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。

圖3-7A和B任務(wù)每次必須完成的時間78/136

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

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

類似地，可算出B1的松弛度為15ms，調(diào)度程序應(yīng)選擇B2運行。t3=30ms時，A2的松弛度已減為0，B1的松弛度為15ms，于是調(diào)度程序應(yīng)搶占B1的處理機而調(diào)度A2運行…….79/136圖3-8利用ELLF算法進行調(diào)度的情況t1=0時：A1的松弛度=必須完成時間-其本身的運行時間-當前時間

=20ms-10ms-0ms=10msB1的松弛度=必須完成時間-其本身的運行時間-當前時間

=50ms-25ms-0ms=25ms01020304050607080A1t2=10時：A2的松弛度=必須完成時間-其本身的運行時間-當前時間

=40ms-10ms-10ms=20msB1的松弛度=必須完成時間-其本身的運行時間-當前時間

=50ms-25ms-10ms=15msB1(20)t3=30時：A2的松弛度=必須完成時間-其本身的運行時間-當前時間

=40ms-30ms-10ms=0msB1的松弛度=必須完成時間-其本身的運行時間-當前時間

=50ms-5ms-30ms=15msA2t4=40時：A3的松弛度=必須完成時間-其本身的運行時間-當前時間

=60ms-10ms-40ms=10msB1的松弛度=必須完成時間-其本身的運行時間-當前時間

=50ms-5ms-40ms=5msB1(5)A3B2(15)A4B2(10)9080/136圖3-8利用ELLF算法進行調(diào)度的情況81/136第3章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測和解除82/1363.4多處理機系統(tǒng)中的調(diào)度

MPS——MultiProcessorSystem

3.4.1緊密耦合MPS和松弛耦合MPS

1.緊密耦合MPS

通過高速總線或高速交叉開關(guān)連接多個處理器，多個CPU共享主存儲器和I/O設(shè)備，系統(tǒng)中的所有資源和進程由操作系統(tǒng)統(tǒng)一控制和管理

2.松弛耦合MPS

通過通道或通信線路連接多個計算機，每個計算機都有自己的存儲器和I/O設(shè)備，都有自己的操作系統(tǒng)控制和管理本地資源和進程的運行(——計算機網(wǎng)絡(luò))83/1363.4.2對稱MPS和非對稱MPS

根據(jù)處理器是否相同來劃分。

1.對稱MPS——SMPS

系統(tǒng)中的處理器在結(jié)構(gòu)和功能上都相同。

2.非對稱MPS

系統(tǒng)中有多種類型的處理器，它們的結(jié)構(gòu)和功能各不相同。其中一個是主處理器，其余都是從處理器。84/136

一）對稱多處理器系統(tǒng)中的進程分配方式

1.靜態(tài)分配方式進程從開始執(zhí)行到執(zhí)行結(jié)束，都被固定地分配到一個處理器。每個此類系統(tǒng)一般采用主從式操作系統(tǒng)，即OS的核心駐留于主處理器中，而用戶程序則在從處理器上，進程調(diào)度由主處理器執(zhí)行。每當從處理器空閑時，就向主處理器發(fā)送一個索求進程的信號，主處理器從公用就緒隊列中進行進程調(diào)度處理器有一個專用的就緒隊列，被阻塞的進程再次就緒時，仍回到該隊列的末尾。

2.動態(tài)分配方式系統(tǒng)中可以只設(shè)置一個公共的就緒隊列，其中的進程可以分配到系統(tǒng)中的任何一個處理器。3.4.3進程分配方式85/136

二）非對稱MPS中的進程分配方式此類系統(tǒng)一般采用主從式操作系統(tǒng)，即OS的核心駐留于主處理器中，而用戶程序則在從處理器上，進程調(diào)度由主處理器執(zhí)行。每當從處理器空閑時，就向主處理器發(fā)送一個索求進程的信號，主處理器從公用就緒隊列中進行進程調(diào)度。86/136一）自調(diào)度方式

1.自調(diào)度機制在系統(tǒng)中設(shè)置一個公共的進程(線程)就緒隊列，所有的處理器空閑時，都可以自己到該隊列中取得一個進程(線程)投入運行

(1)FCFS算法

(2)最小優(yōu)先數(shù)優(yōu)先算法

(3)搶占式最小優(yōu)先數(shù)優(yōu)先算法3.4.4進程(線程)調(diào)度方式87/1362.自調(diào)度方式的特點有任務(wù)的情況下處理機不會空閑分布式調(diào)度可以沿用單處理機環(huán)境下的就緒隊列組方式織和進程調(diào)度方法多處理機互斥共享單就緒隊列引起的瓶頸重新調(diào)度時線程遷移引起的低效性線程切換頻繁88/136二）成組調(diào)度

1.基本原理把一個進程中的一組線程分配到一組處理機上執(zhí)行。其優(yōu)點是：

(1)若一組線(進)程可以并行執(zhí)行，就可以減少阻塞情況的發(fā)生，減少了切換頻率，提高了性能

(2)一次調(diào)度為一組線程分配處理機，減少了調(diào)度頻率，減少了系統(tǒng)開銷2.為應(yīng)用程序分配處理機時間的方法

1)為所有的應(yīng)用程序平均分配處理機時間

2)為所有的線程平均分配處理機時間89/136

1.基本原理為一個應(yīng)用程序的每個線程分配一個處理器，直到該應(yīng)用程序執(zhí)行完畢，才釋放為該應(yīng)用程序所分配的所有處理器。3.4.5專用處理器分配2.采用專用處理器分配方法的理由

1)專用處理器分配方式的缺點部分處理器的利用率可能不高

2)仍然采用專用處理器分配方式的原因

(1)在大規(guī)模(甚至幾百個處理器)高度并行的系統(tǒng)中，單個處理器的利用率不那么重要；

(2)避免了線程切換，加速了程序運行。90/136討論與練習(xí)91/136第3章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測和解除92/1363.5.1死鎖的概念1.死鎖例子:(deadlock)一個由于申請不同類型資源而產(chǎn)生死鎖的例子設(shè)系統(tǒng)有一臺打印機(R1)一臺掃描儀(R2)，兩進程共享這兩臺設(shè)備。用信號量S1表示R1是否可用，用信號量S2表示R2是否可用，S1、S2初值為1。

93/1363.5.1.1死鎖概念指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。即：一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現(xiàn)象稱為進程死鎖，這一組進程就稱為死鎖進程。94/136參與死鎖的進程最少是兩個；參與死鎖的進程至少有兩個已經(jīng)占有資源；參與死鎖的所有進程都在等待資源；參與死鎖的進程是當前系統(tǒng)中所有進程的子集。注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。3.5.1.2關(guān)于死鎖的一些結(jié)論95/136永久性資源：可以被多個進程多次使用（可再用資源）可搶占資源(處理機,主存)不可搶占資源(打印機,磁帶機)臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源）“申請--分配--使用--釋放”模式3.5.1.3永久性資源和臨時性資源96/1363.5.2產(chǎn)生死鎖的原因1.競爭系統(tǒng)資源當系統(tǒng)中供多個進程共享的資源數(shù)目不足以滿足諸進程的需要時,會引起進程對資源的競爭而產(chǎn)生死鎖。2.進程的推進順序不當進程在運行過程中,請求和釋放資源的順序不當,也可能造成進程死鎖。97/1361.競爭系統(tǒng)資源

若系統(tǒng)中只有一臺打印機R1和一臺讀卡機R2，可供進程P1和P2共享。若形成環(huán)路，這樣會產(chǎn)生死鎖。98/136有環(huán)有死鎖99/136有環(huán)無死鎖100/1362.進程的推進順序不當在進程P1和P2并發(fā)執(zhí)行時，按照左圖曲線①②③所示順序推進時，兩進程會順利完成，我們稱這種推進順序是合法的。若按曲線④的順序推進時，進入不安全區(qū)D內(nèi)，兩進程再推進會產(chǎn)生死鎖。P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③④③③③②②①①進程P1、P2并發(fā)執(zhí)行。資源R1、R2曲線4將進入不安全區(qū)域（進程推進順序非法）102/136互斥使用：在一段時間內(nèi)，一個資源只能由一個進程獨占使用，若別的進程也要求該資源，則須等待直至其占用者釋放；保持和等待：允許進程在不釋放其已分得資源的情況下請求并等待分配新的資源；非剝奪性：進程所獲得的資源在未使用完之前，不能被其它進程強行奪走，而只能由其自身釋放；循環(huán)等待：存在一個等待進程集合，P0正在等待一個P1占用的資源，P1正在等待一個P2占用的資源，…，Pn正在等待一個由P0占用的資源。3.5.3產(chǎn)生死鎖的必要條件103/136預(yù)防死鎖：通過設(shè)置某些限制條件，破壞產(chǎn)生死鎖的四個必要條件中的一個或者幾個，預(yù)防死鎖。避免死鎖：在資源的動態(tài)分配過程中，用某種方法防止系統(tǒng)進入不安全狀態(tài)，避免死鎖。檢測死鎖：檢測死鎖的發(fā)生，確定與死鎖有關(guān)的進程與資源，采取措施，從系統(tǒng)中將已發(fā)生的死鎖清除。解除死鎖：通過撤消和掛起一些進程，回收一些資源，分配給處于阻塞狀態(tài)的進程，使之轉(zhuǎn)為就緒狀態(tài)。3.5.4解決死鎖的基本辦法104/136第3章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測和解除105/1363.6預(yù)防死鎖的方法和避免死鎖

在系統(tǒng)設(shè)計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一。資源一次性分配；(破壞請求和保持條件)可剝奪資源；即當某進程新的資源未滿足時，釋放已占有的資源(破壞不可剝奪條件)資源有序分配法；系統(tǒng)給每類資源賦予一個編號，每一個進程按編號遞增的順序請求資源，釋放則相反(破壞環(huán)路等待條件)

3.6.1預(yù)防死鎖的方法106/136死鎖避免定義:在系統(tǒng)運行過程中，對進程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。預(yù)防死鎖的幾種策略，會嚴重地損害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意的系統(tǒng)性能來避免死鎖。由于在避免死鎖的策略中，允許進程動態(tài)地申請資源。因而，系統(tǒng)在進行資源分配之前預(yù)先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程；否則，進程等待。其中最具有代表性的避免死鎖算法是銀行家算法。

3.6.2避免死鎖107/136

安全狀態(tài)指系統(tǒng)能按某種進程順序來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。若系統(tǒng)不存在這樣一個序列，則稱系統(tǒng)處于不安全狀態(tài)。

3.6.3安全狀態(tài)與不安全狀態(tài)108/1361)安全序列概念

一個進程序列{P1，…，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj(j<i)當前占有資源量之和，系統(tǒng)處于安全狀態(tài)。

(安全狀態(tài)一定是沒有死鎖發(fā)生的)109/136

我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P3104952232)安全序列舉例安全序列（P2,P1,P3)110/136

如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。

因為，此時也無法再找到一個安全序列，例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。進程最大需求已分配可用P1P2P3104952233)由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換111/136討論與練習(xí)112/136安全狀態(tài)與不安全狀態(tài)不安全狀態(tài):不存在一個安全序列，不安全狀態(tài)一定導(dǎo)致死鎖113/1363.6.4利用銀行家算法避免死鎖

1)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

(1)可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。[?'veil?b?l]

114/136

(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max［i,j］=K，則表示進程i需要Rj類資源的最大數(shù)目為K。(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocation［i,j］=K，則表示進程i當前已分得Rj類資源的數(shù)目為K。115/136(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need［i,j］=K，則表示進程i還需要Rj類資源K個，方能完成其任務(wù)。Need［i,j］=Max［i,j］-Allocation［i,j］

116/136

設(shè)Requesti是進程Pi的請求向量，如果Requesti［j］=K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查:(1)如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認為出錯，因為它所請求的資源數(shù)已超過它所宣布的最大值;

(2)如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。2)銀行家算法117/136(3)系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值:

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。118/1363)安全性算法

(1)設(shè)置兩個向量：①工作向量Work:它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］∶=false;當有足夠資源分配給進程時，再令Finish［i］∶=true。119/136(2)從進程集合中找到一個能滿足下述條件的進程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。(4)如果所有進程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。(3)當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work［j］∶=Work［j］+Allocation［i,j］;Finish［i］∶=true;gotostep2;120/1364)銀行家算法之例

假定系統(tǒng)中有五個進程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-8T0時刻的資源分配表

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431

(1)T0時刻的安全性

資源進程WorkNeedAllocationWork+AllocationFinishABCABCABCABCp1332122200532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true122/136(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Request1(1，0，2)

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

資源進程WorkNeedAllocationWork+AllocationFinishABCABCABCABCp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true125/136

(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431系統(tǒng)按銀行家算法進行檢查：①Request4(3,3,0)≤Need

(4,3,1);②Request4(3,3,0)>Available(2,3,0)，讓P4等待。126/136(4)P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431系統(tǒng)按銀行家算法檢查：①Request0(0,2,0)≤Need

(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如下圖所示。

Request0(0，2，0)

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431128/136(5)進行安全性檢查:可用資源Available(2,1,0)已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源．如果把P0發(fā)出請求向量改為Request0(0,１,0)，系統(tǒng)是否可以將資源分配給它？？？

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431Request0(0，1，0)

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

資源進程MaxAllocationNeedAvailableABCABCABCABCP0753020733220P1322302020P2902302600P3222211011P4433002431

資源進程WorkNeedAllocationWork+AllocationFinishABCABCABCABCP0220733020240trueP1240020302542trueP3542011211753trueP4753431002755trueP27