第三章處理機調度與死鎖處理機管理的工作是對CPU資源進行合理的分配使用，以提高處理機利用率，并使各用戶公平地得到處理機資源。要解決的問題WHAT：按什么原則分配CPU

—進程調度算法WHEN：何時分配CPU

—進程調度的時機HOW：如何分配CPU

—CPU調度過程（進程的上下文切換）作業是任務實體，進程是完成任務的執行實體;沒有作業任務，進程無事可干，沒有進程，作業任務沒法完成。一個作業可由多個進程組成，且必須至少有一個進程，但反過來不成立。作業概念更多地用在批處理操作系統，而進程則可以用在各種多道程序設計系統。作業是用戶向計算機提交任務的任務實體。進程是計算機為完成用戶任務而設置的執行實體，是系統分配資源的基本單位。一個作業可由多個進程組成，且必須至少有一個進程，但反過來不成立。作業和進程的關系

處理機三級調度1.高級(Long-term)調度——作業調度

作業調度用于決定把外存井上處于作業后備隊列上的哪些作業調入內存，并為它們創建進程、分配必要的資源，然后再將新創建的進程排在就緒隊列上，準備執行。在批處理系統中，作業是先駐留在外存的輸入井上的，因此需要有作業調度；在分時系統中，通過鍵盤輸入的命令和數據直接進入內存，無需作業調度。2.低級(Short-term)調度——進程調度

進程調度決定就緒隊列中哪個進程將獲得處理機，然后由分派程序執行把處理機分配給該進程的操作。進程調度是最基本的調度，任何操作系統都有進程調度。低級調度：最基本。各類0S必須具有的功能。中級調度：較完善的OS中，引入其來改善內存的利用率和提高作業的吞吐量。高級調度：批處理OS必須配置，純粹的分時或實時OS中，通常無須配置。提交狀態收容狀態完成狀態外存內存分級調度作業的狀態及其轉換就緒等待就緒等待執行輸入管理系統交換調度線程調度進程調度作業調度提交狀態：作業處于從輸入設備進入外存的過程；收容狀態：作業的全部信息被輸入到輸入井，尚未被調度執行；完成狀態：作業運行完畢，所占資源尚未被收回。作業狀態一個作業從提交給計算機系統到執行結束退出系統，一般都要經歷提交、后備、執行和完成等4個狀態。提交狀態：一個作業在其處于從輸入設備進入外部存儲設備的過程稱為提交狀態。后備狀態：也稱為收容狀態。若一個作業的全部信息已全部被輸入進輸入井，則在它還未被調度去執行之前，該作業處于后備狀態。執行狀態：作業調度程序從后備作業中選取若干個作業到內存投入運行。它為被選中作業建立進程并分配必要的資源，這時，這些被選中的作業處于執行狀態。完成狀態：當作業運行完畢，但它所占用的資源尚未全部被系統回收時，該作業處于完成狀態。調度的層次提交狀態收容狀態完成狀態外存內存就緒等待就緒等待執行輸入管理系統交換調度線程調度進程調度作業調度第1級：作業調度、宏觀調度、高級調度對外存輸入井上的大量作業進行選擇，對選擇的作業分配資源，建立相應進程。作業執行完畢時，回收資源。分級調度調度的層次提交狀態收容狀態完成狀態外存內存就緒等待就緒等待執行輸入管理系統交換調度線程調度進程調度作業調度第2級：交換調度、中級調度將處于外存交換區中的就緒狀態或等待狀態的進程調入內存，或把處于內存就緒狀態或內存等待狀態的進程交換導外存交換區。分級調度調度的層次提交狀態收容狀態完成狀態外存內存就緒等待就緒等待執行輸入管理系統交換調度線程調度進程調度作業調度第3級：進程調度、微觀調度、低級調度選取一個處于就緒狀態的進程占用處理機，之后，進行上下文切換以便建立與占用處理機進程相適應的執行環境。分級調度調度的層次提交狀態收容狀態完成狀態外存內存就緒等待就緒等待執行輸入管理系統交換調度線程調度進程調度作業調度第4級：線程調度選取一個處于就緒狀態的線程進入執行狀態。分級調度3.1.3處理機調度模型分時間片完完成CPU交互型作業等待事件活動就緒隊列靜止就緒隊列靜止阻塞隊列活動阻塞隊列事件發生作業調度后備作業隊列批量作業中級調度調入中級調度調出磁盤進程調度中級調度調出事件發生具有三級級調度的調度隊列模型作業后備狀態執行狀態完成狀態4.2.1作業調度的功能記錄系統中各作業的狀況系統為每個作業建立一個JCB記錄作業信息，系統通過JCB感知作業的存在。作業名作業類型資源要求資源使用情況優先級（數）當前狀態其它作業進入后備狀態時，系統為其建立JCB；作業進入完成狀態后，系統撤銷其JCB。作業調度1作業調度的功能記錄系統中各作業的狀況從后備隊列中選擇一部分作業投入運行（涉及調度算法）為被選中的作業做好執行前的準備（建立進程、為進程們分配系統資源）作業執行結束時的后處理作業調度2作業調度目標目標公平性：對所有作業應該是公平的利用率：應使設備有高的利用率作業量：每天執行盡可能多的作業響應時間：有快的響應時間作業調度3作業調度性能衡量面向用戶的調度性能準則周轉時間：作業從提交到完成（得到結果）所經歷的時間。周轉時間Ti=作業完成時刻(Tei)-作業提交時刻(Tsi)=作業等待時間(Twi)+作業執行時間（Tri)平均周轉時間作業調度3作業調度性能衡量面向用戶的調度性能準則帶權周轉時間帶權周轉時間Wi=Ti/Tri平均帶權周轉時間響應時間：用戶輸入一個請求（如擊鍵）到系統給出首次響應（如屏幕顯示）的時間——分時系統作業調度3作業調度性能衡量面向系統的調度性能準則吞吐量：單位時間內所完成的作業數，跟作業本身特性和調度算法都有關系——批處理系統處理機利用率：——大中型主機各種設備的均衡利用：如CPU繁忙的作業和I/O繁忙（指次數多，每次時間短）的作業搭配——大中型主機作業調度1先來先服務按照作業到達后備作業隊列（或進程進入就緒隊列）的先后次序來選擇作業（或進程）。

FCFS算法當前作業或進程占用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）最簡單的算法

FCFS特點比較有利于長作業，而不利于短作業有利于CPU繁忙的作業，而不利于I/O繁忙的作業調度算法2短作業／進程優先(SJF/SPF)調度算法

(SJF,ShortestJobFirst)

SJF算法對預計執行時間短的作業（進程）優先分派處理機。通常后來的短作業不搶先正在執行的作業

SJF優點比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間提高系統的吞吐量調度算法2短作業優先

(SJF,ShortestJobFirst)

SJF缺點對長作業非常不利，可能長時間得不到執行未能依據作業的緊迫程度來劃分執行的優先級難以準確估計作業（進程）的執行時間，從而影響調度性能調度算法先來先服務調度算法和短作業優先調度算法作業提交時間運行時間開始時間完成時間周轉時間帶權周轉時間執行順序18.002.0028.500.5039.000.1049.500.208.0010.0012110.0010.5022410.5010.6031.61610.6010.8041.36.58.0010.0012110.0010.1021.11110.1010.3030.8410.3010.8042.34.6先來先服務算法平均周轉時間t=1.725帶權平均周轉時間w=6.875短作業優先算法平均周轉時間t=1.55帶權平均周轉時間w=5.154時間片輪轉算法

(RoundRobin)

說明前兩種算法主要用于宏觀調度，說明怎樣選擇一個進程或作業開始運行，開始運行后的作法都相同，即運行到結束或阻塞，阻塞結束時等待當前進程放棄CPU本算法主要用于微觀調度，說明怎樣并發運行，即切換的方式；設計目標是提高資源利用率其基本思路是通過時間片輪轉，提高進程并發性和響應時間特性，從而提高資源利用率調度算法4時間片輪轉算法

(RoundRobin)RoundRobin算法將系統中所有的就緒進程按照FCFS原則，排成一個隊列當執行的時間片用完時，調度程序便停止該進程的執行，并將它送就緒隊列的末尾，等待分配下一時間片再執行。然后把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片保證就緒隊列中的所有進程，在一給定的時間內，均能獲得一個時間片的處理機執行時間進程可以未使用完一個時間片，就出讓CPU（如阻塞）F…DCBACPU阻塞完成超時調度算法4時間片輪轉算法

(RoundRobin)

時間片長度的確定（時間片的長度從幾個ms到幾百ms）時間片長度變化的影響過長退化為FCFS算法，進程在一個時間片內都執行完，響應時間長過短用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，響應時間長調度算法7多級反饋隊列算法(RoundRobinwithMultipleFeedback)多級反饋隊列算法（目前公認的較好的一種進程調度算法）設置多個就緒隊列，分別賦予不同的優先級，如逐級降低，隊列1的優先級最高。每個隊列執行時間片的長度也不同，規定優先級越低則時間片越長。新進程進入內存后，先投入隊列1的末尾，按FCFS算法調度；若按隊列1一個時間片未能執行完，則降低投入到隊列2的末尾，同樣按FCFS算法調度；如此下去，降低到最后的隊列，則按“時間片輪轉”算法調度直到完成；僅當較高優先級的隊列為空，才調度較低優先級的隊列中的進程執行。如果有新進程進入優先級較高的隊列，則此時新進程將搶占正在運行進程的處理機，并把被搶先的進程投入原隊列的末尾。（搶占式調度方式）調度算法多級反饋隊列

在兩道環境下有四個作業,已知它們進入系統的時間、估計運行時間,系統采用短作業優先作業調度算法，作業被調度運行后不再退出內存,當一新作業投入運行后，可按照作業運行時間長短調整作業執行的次序（可搶占式調度占用CPU）請給出這四個作業的執行時間序列，并計算出平均周轉時間及帶權平均周轉時間調度算法應用舉例最短作業優先算法執行結果最短作業優先算法執行分析過程10：00，JOB1進入，只有一作業，JOB1被調入執行，10：05，JOB2到達，最多允許兩作業同時進入，所以JOB2也被調入內存中有兩作業，哪一個執行？題目規定當一新作業運行后，可按作業運行時間長短調整執行次序即基于優先數可搶占式調度策略，優先數是根據作業估計運行時間大小來決定的，由于JOB2運行時間（20分）比JOB1少（到10：05，JOB1還需25分鐘），所以JOB2運行，而JOB1等待調度算法應用舉例最短作業優先算法執行分析過程10：10，JOB3到達輸入井，內存已有兩作業，JOB3不能馬上進入內存；10：20，JOB4也不能進入內存，10：25，JOB2運行結束，退出，內存中剩下JOB1，輸入井中有兩作業JOB3和JOB4，如何調度？作業調度算法：最短作業優先，因此JOB3進入內存，比較JOB1和JOB3運行時間，JOB3運行時間短，故JOB3運行，同樣，JOB3退出后，下一個是JOB4，JOB4結束后，JOB1才能繼續運行。調度算法應用舉例1.死瑣概念死鎖是指多個并發執行的進程因爭奪資源而出現的一種彼此都不能繼續推進的僵持局面。死鎖（Deadlock）產生死鎖的原因和必要條件2.產生死鎖的原因競爭資源進程間推進順序非法2.產生死鎖的原因競爭資源資源分為可重用資源和臨時性資源重用資源又分為可剝奪資源和非剝奪資源。可剝奪資源：CPU，存儲器非剝奪資源：打印機競爭重用資源，且數量不能滿足進程運行需要，就會陷入僵局。又如：200K的可用內存，

P1，P2都進行到第二步時，死鎖發生。P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;產生死鎖的原因和必要條件2.產生死鎖的原因進程間推進順序非法（進程的異步性特征）

進程P進程QGetA GetB…… ……GetB GetA…… ……ReleaseAReleaseB…… ……ReleaseBReleaseA37正確模式

進程P進程QGetA GetB…………ReleaseAReleaseB…… ……GetB GetA…… ……ReleaseBReleaseA

進程在申請資源時，用完一個資源釋放后再申請下一個資源。3.5產生死鎖的原因和必要條件38正確模式

進程P進程QGetA GetA…… ……GetB GetB…… ……ReleaseAReleaseA…… ……ReleaseBReleaseB兩個進程按照相同的順序申請使用資源3.5產生死鎖的原因和必要條件39產生死鎖的原因和必要條件3.產生死鎖的必要條件互斥條件Mutualexclusion一段時間內，某資源只能由一個進程占用。是臨界資源本身的固有屬性。請求和保持條件Hold-and-wait保持已經獲得資源不放，繼續提出新的資源需求。不剝奪條件Nopreemption進程已獲得資源在未使用完前不能被剝奪。環路等待條件系統一定有兩個或兩個以上的進程組成的一條環路，該環路中的每個進程都在等待著相鄰進程正占用著的資源產生死鎖的原因和必要條件處理死鎖的四種策略預防死鎖通過破除死鎖的四個必要條件之一，來防止死鎖產生。避免死鎖仔細地對資源進行動態分配，以避免死鎖發生。檢測與解除死鎖檢測系統中是否出現死鎖，若出現則解除掉。忽略該問題允許系統發生死鎖，然后解除假裝死鎖永不發生保證系統永遠不會發生死鎖預防和避免死鎖的方法預防死鎖如果能夠保證四個必要條件中至少有一個不成立，那么死鎖將不會產生。（Havender，1968）但其中的“互斥”條件不能破除。預防和避免死鎖的方法摒棄“請求和保持”條件方法規定進程在執行前要一次性地申請運行所需全部資源。只有資源全部到手，進程方可運行，否則進程等待。優點簡單、易于實現缺點資源利用率低進程運行被延遲預防和避免死鎖的方法摒棄“不剝奪”條件方法保持資源的進程申請新資源失敗時，在轉為阻塞狀態之前，必須釋放其占用的全部資源。而該進程自身則必須等到重新獲得原有資源及新資源后，才能重新運行。缺點實現復雜，代價大3.6預防和避免死鎖的方法摒棄“環路等待”條件方法1保證每個進程在任何時候只能占用一個資源。要用第二個，必須先釋放第一個。方法2對資源按類型線性排隊編號，進程對資源的請求必須按照資源序號遞增提出。缺點：1.找不出一種人人滿意的編號順序。

2.仍存在資源浪費。

3.用戶編程受到限制。4.限制新類型設備增加預防和避免死鎖的方法避免死鎖思路允許進程動態的申請資源將系統狀態分為安全狀態：不會發生死鎖不安全狀態：可能發生死鎖避免系統進入不安全狀態！做法每次進行資源分配時，首先檢測一下資源分配后系統處于何種狀態，若處于安全狀態，則正式實施本次分配；若處于不安全狀態，則不予分配，申請資源的進程阻塞。46預防死鎖的方法系統安全狀態（用于避免死鎖）安全狀態：系統能按某種進程順序(P1,P2,…，Pn)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。稱(P1,P2,…,Pn)序列為安全序列預防和避免死鎖的方法例，系統有三個進程P1、P2和P3，共用12臺磁帶機。在T0和T1時刻，系統的資源分配情況分別如下表a和b。進程最大需求已分配可用

P11053

P242P392進程最大需求已分配可用

P11052

P242P393ab預防和避免死鎖的方法結果：T0時刻系統處于安全狀態。（安全序列<P2

，P1，P3

>）P1P2P3可用5(5)2(2)2(7)35(5)4(0)2(7)15(5)2(7)510(0)2(7)02(7)109(0)312結果：T1時刻系統處于不安全狀態。P1P2P3可用5(5)2(2)3(6)25(5)4(0)3(6)05(5)3(6)449利用銀行家算法避免死鎖避免死鎖策略1.當前狀態下，某進程申請資源；2.系統假設將資源分給該進程，滿足它的需求；3.檢查分配后的系統狀態是否是安全的，如果是安全，就確認本次分配；如果系統是不安全的，就取消本次分配并阻塞該進程。（第三步又稱安全算法）避免死鎖策略也稱作銀行家算法。避免死鎖實質：在進程資源分配時，如何使系統不進入不安全狀態。預防和避免死鎖的方法預防和避免死鎖的方法利用銀行家算法避免死鎖數據結構—n個進程(P1,…,Pn)，m類資源(R1,…,Rm)可利用資源向量Available（m）Available[j]表示Rj

類資源的可用數目。最大需求矩陣Max（n×m）Max[i,j]表示進程Pi

對Rj

類資源的最大需求量。分配矩陣Allocation（n×m）Allocation[i,j]表示已分配給進程Pi

的Rj

類資源的數目。需求矩陣Need（n×m）Need[i,j]表示進程Pi

對Rj

類資源的剩余需求量Requesti

：進程Pi

的請求向量預防和避免死鎖的方法銀行家算法：進程Pi

發出資源請求RequestiRequestiNeedi?

執行安全性算法，檢查分配后的系統狀態正式分配安全狀態Requesti

Available?是

試分配：Available:=AvailableRequestiAllocationi:=Allocationi+RequestiNeedi:=Needi

Requesti是將試分配作廢；恢復原資源分配狀態；進程Pi阻塞。不安全狀態錯誤否否進程Pi阻塞3.6預防和避免死鎖的方法安全性算法Work:=Available;Finish[i]:=false(i=1,2,…,n);找一滿足下列條件的進程：Finish[i]=false且Needi

WorkWork:=Work+Allocationi;

Finish[i]:=true;找到

所有進程的Finish[i]=true？找不到是系統狀態安全不是系統狀態不安全預防和避免死鎖的方法例：系統中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，每類資源的數量分別為10、5、7，在T0時刻的資源分配情況如下表。問：P1發出請求向量Request1(1,0,2)，能否分配？ProcessMaxAllocationNeedAvailableABCABCABCABCP0753010743332P1 322200122P2 902302600P3222211011P4433002431ProcessMaxAllocationNeedAvailableP0753010743332P1 322200122P2 902302600P3222211011

P4433002431230020302結論：可以找到一個安全序列<p1,p3,p4,p2,p0>，所以安全，可以將P1申請的資源分配給它。Request1(1

,0

,2)試分配（結果見紅字）安全性算法：Work={230}Finish=

falsefalsefalsefalsefalsetrue532743true745true1047true1057true死鎖的檢測與解除死鎖的檢測資源分配圖RAG（ResourceAllo