os-第3章處理機(jī)調(diào)度和死鎖

南昌大學(xué)信息管理系

NanChangUniversityDepartmentofinformationmanager操作系統(tǒng)OperatingSystem第二部分B處理機(jī)調(diào)度與死鎖南昌大學(xué)信息管理系

NanChangUniversityDepartmentofinformationmanager3.1處理機(jī)調(diào)度的基本概念

高級調(diào)度低級調(diào)度中級調(diào)度按OS的類型分：批處理調(diào)度分時(shí)調(diào)度和實(shí)時(shí)調(diào)度多處理機(jī)調(diào)度等按調(diào)度層次分：處理機(jī)調(diào)度的基本類型：

一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一般都要經(jīng)歷4個(gè)狀態(tài)：提交、后備（收容）、執(zhí)行和完成。1）提交狀態(tài)：通過終端設(shè)備向計(jì)算機(jī)的磁盤輸入作業(yè)信息時(shí)所處的狀態(tài)。2）后備狀態(tài)：作業(yè)的全部信息已輸入到磁盤的一個(gè)專用區(qū)(輸入井)中等待作業(yè)調(diào)度時(shí)所處的狀態(tài)。3）執(zhí)行狀態(tài)：在后備作業(yè)隊(duì)列中的作業(yè)一旦被作業(yè)調(diào)度程序選中，為它分配了必要的資源，并且建立了進(jìn)程,開始處理時(shí)所處的狀態(tài)。4）完成狀態(tài)：作業(yè)完成其全部任務(wù)后，進(jìn)程撤消,做善后處理時(shí)的作業(yè)狀態(tài)稱為完成狀態(tài)。作業(yè)的狀態(tài)一、作業(yè)的狀態(tài)及其轉(zhuǎn)換

作業(yè)的狀態(tài)及其轉(zhuǎn)換執(zhí)行進(jìn)程調(diào)度

內(nèi)存

線程調(diào)度運(yùn)行等待就緒外存

就緒等待提交后備完成作業(yè)輸入作業(yè)調(diào)度

交換調(diào)度

作業(yè)調(diào)度

執(zhí)行一、高級調(diào)度（作業(yè)調(diào)度）

HighLevelScheduling

決定允許哪些作業(yè)競爭系統(tǒng)資源。也就是說，高級調(diào)度用于決定把外存上處于后備狀態(tài)的作業(yè)按照一定的算法，選取出一個(gè)作業(yè)，當(dāng)內(nèi)存空間滿足其要求時(shí)，為它分配存儲(chǔ)空間，調(diào)入內(nèi)存，創(chuàng)建該作業(yè)的進(jìn)程，再分配它所需的I/0設(shè)備及其它資源，再將新進(jìn)程排在就緒隊(duì)列上，新進(jìn)程具有了獲得處理機(jī)的資格。

外存后備狀態(tài)作業(yè)調(diào)入內(nèi)存，分配資源創(chuàng)建進(jìn)程就緒隊(duì)列在執(zhí)行作業(yè)調(diào)度時(shí)，要做以下兩步：接納多少個(gè)作業(yè)接納哪些作業(yè)二、低級調(diào)度（LowLevelScheduling）就緒隊(duì)列進(jìn)程獲得處理機(jī)

也稱進(jìn)程調(diào)度，它決定在就緒隊(duì)列中哪一個(gè)進(jìn)程將分配到處理機(jī)，并由分派程序把處理機(jī)實(shí)際分配給這個(gè)進(jìn)程。進(jìn)程調(diào)度可采用下述兩種方式：非搶占方式搶占方式

搶占原則： （1）時(shí)間片原則 （2）優(yōu)先權(quán)原則 （3）短作業(yè)優(yōu)先原則三、中級調(diào)度（IntermediateLevelScheduling）

目的：是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。四、三級調(diào)度的關(guān)系3.1.2進(jìn)程調(diào)度隊(duì)列模型1、僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型2、具有高級和低級調(diào)度的調(diào)度隊(duì)列模型3、同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型進(jìn)程完成CPU進(jìn)程調(diào)度時(shí)間片完阻塞隊(duì)列就緒隊(duì)列事件出現(xiàn)交互用戶等待事件僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型CPU進(jìn)程調(diào)度作業(yè)調(diào)度超時(shí)就緒隊(duì)列等待事件2事件2出現(xiàn)后備作業(yè)隊(duì)列具有高,低兩級調(diào)度的調(diào)度隊(duì)列模型事件n出現(xiàn)事件1出現(xiàn)等待事件n等待事件1………完成中級調(diào)度CPU進(jìn)程調(diào)度作業(yè)調(diào)度完成超時(shí)掛起就緒隊(duì)列掛起等待隊(duì)列等待隊(duì)列就緒隊(duì)列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊(duì)列中級調(diào)度具有三級調(diào)度時(shí)的調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1、面向用戶的準(zhǔn)則（1）周轉(zhuǎn)時(shí)間短（2）響應(yīng)時(shí)間快（3）截止時(shí)間的保證（4）優(yōu)先權(quán)準(zhǔn)則1、平均周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間：由等待時(shí)間、執(zhí)行時(shí)間等組成

平均周轉(zhuǎn)時(shí)間：Ti=1/n∑Ti n>=1，n為作業(yè)或進(jìn)程個(gè)數(shù)。2、帶權(quán)周轉(zhuǎn)時(shí)間

帶權(quán)周轉(zhuǎn)時(shí)間：Wi=Ti/Tr

周轉(zhuǎn)時(shí)間與執(zhí)行時(shí)間之比。

平均帶權(quán)周轉(zhuǎn)時(shí)間：W=1/n∑Wi

n為作業(yè)或進(jìn)程個(gè)數(shù)。3、響應(yīng)時(shí)間

響應(yīng)時(shí)間是從用戶通過鍵盤提交一個(gè)請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)位置的時(shí)間說直到或在屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。包括： （1）從鍵盤輸入的請求信息傳送到處理機(jī)的時(shí)間； （2）處理機(jī)對請求信息進(jìn)行處理的時(shí)間； （3）將所形成的響應(yīng)回送到終端顯示器的時(shí)間。2、面向系統(tǒng)的準(zhǔn)則（1）系統(tǒng)吞吐量高。（2）處理機(jī)利用率好。（3）各類資源的平衡利用。選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則（續(xù)）進(jìn)程調(diào)度

進(jìn)程調(diào)度的任務(wù)就是按照一定的策略負(fù)責(zé)把處理機(jī)分配給某一就緒進(jìn)程。由進(jìn)程調(diào)度程序具體實(shí)現(xiàn)處理機(jī)在進(jìn)程之間的轉(zhuǎn)換。進(jìn)程調(diào)度程序的功能具體功能包括： （1）記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況。 （2）進(jìn)行進(jìn)程上下文切換

進(jìn)程上下文實(shí)際上是進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述，進(jìn)程上下文包括計(jì)算機(jī)系統(tǒng)中與執(zhí)行進(jìn)程有關(guān)的各種寄存器的值，程序段在經(jīng)過編譯之后形成的機(jī)器指令代碼集（正文段）、數(shù)據(jù)集及各種堆棧值和PBC結(jié)構(gòu)。進(jìn)程調(diào)度的時(shí)機(jī)

進(jìn)程調(diào)度的時(shí)機(jī)與引起進(jìn)程調(diào)度的原因以及進(jìn)程調(diào)度的方式有關(guān)。 一、引起進(jìn)程調(diào)度的原因 （1）正在執(zhí)行的進(jìn)程執(zhí)行完畢。 （2）執(zhí)行中的進(jìn)程提出I/O請求后被阻塞。（3）執(zhí)行某種原語操作，比如wait(s)，block原語，wakeup原語。

（4）分時(shí)系統(tǒng)中，由于分配給該進(jìn)程的時(shí)間片已經(jīng)用完。 （5）執(zhí)行中進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來。 （6）執(zhí)行完系統(tǒng)程序后返回用戶進(jìn)程時(shí)，可看作系統(tǒng)進(jìn)程執(zhí)行完畢，從而可以調(diào)度選擇一個(gè)新的用戶進(jìn)程執(zhí)行。 以上是在不可剝奪方式下的引起進(jìn)程調(diào)度的原因，在CPU執(zhí)行方式是可剝奪時(shí)，還有一個(gè)原因。

（7）一個(gè)比正在運(yùn)行進(jìn)程的優(yōu)先數(shù)更高的進(jìn)程進(jìn)入就緒隊(duì)列，從而引起調(diào)度。 在以上所列的幾種原因之一發(fā)生的情況下，OS進(jìn)行進(jìn)程調(diào)度。進(jìn)程上下文切換

進(jìn)程上下文由正文段、數(shù)據(jù)段、硬件積存器的內(nèi)容以及有關(guān)數(shù)據(jù)結(jié)構(gòu)等組成。在發(fā)生進(jìn)程調(diào)度時(shí)系統(tǒng)要做進(jìn)程上下文切換。進(jìn)程上下文切換包括四個(gè)步驟：

（1）決定是否做上下文切換以及是否允許做上下文切換。在OS中不是每進(jìn)每刻上下文切換進(jìn)程都在檢查和分析是否可做上下文切換。在可剝奪方式中，是采用優(yōu)先級高的進(jìn)程發(fā)生信號中斷正在執(zhí)行的優(yōu)先級低的進(jìn)程，從而進(jìn)行上下文切換；在不可剝奪方式中可采用時(shí)間片方式，也可采用原語調(diào)用，調(diào)用上下文切換程序。

（2）保存當(dāng)前執(zhí)行進(jìn)程的上下文

當(dāng)前執(zhí)行進(jìn)程是指調(diào)用上下文切換程序之前的執(zhí)行進(jìn)程。上下文切換程序不能破壞“老”進(jìn)程的上下文結(jié)構(gòu)。

（3）采用進(jìn)程調(diào)度算法，從就緒隊(duì)列中選擇一個(gè)進(jìn)程。 （4）恢復(fù)或裝配所選進(jìn)程的上下文，把處理機(jī)分配給所選進(jìn)程?！?.2調(diào)度算法

在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。3.2.1先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法

1、先來先服務(wù)調(diào)度算法 先來先服務(wù)FCFS調(diào)度算法是一種最簡單的調(diào)度算法。 作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。既可用于進(jìn)程調(diào)度，也可用于作業(yè)調(diào)度

在進(jìn)程調(diào)度中，采用FCFS時(shí)每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使之投入運(yùn)行，該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后，才放棄處理機(jī)。

進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B11001101100100/100=1C21101102102-2=100100/1=100D3100102202199199/100=1.99

可見，F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè)，

FCFS調(diào)度算法不利于I/0繁忙型作業(yè)。

FCFS在一定意義上是公平合理的。

FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。先來先服務(wù)不能保證良好的響應(yīng)時(shí)間，在處理交互用戶時(shí)很少用這種方法。2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（ShortestJobFirst）SJF

短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或進(jìn)程優(yōu)先調(diào)度的算法。它們可分別用于作業(yè)調(diào)度(SJF)和進(jìn)程調(diào)度(SPF)。

二、實(shí)例

作業(yè)調(diào)度情況算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234

服務(wù)時(shí)間43524

FCFS完成時(shí)間47121418

周轉(zhuǎn)時(shí)間47-1=612-2=1014-3=1118-4=144+6+10+11+14/5=9帶權(quán)周轉(zhuǎn)時(shí)間16÷3=210÷5=211÷2=5.514÷4=3.51+2+2+5.5+3.5/5=2.8SJF完成時(shí)間46+3=913+5=184+2=69+4=13

周轉(zhuǎn)時(shí)間4818-2=166-3=313-4=94+8+16+3+9/5=8

帶權(quán)周轉(zhuǎn)時(shí)間18÷3=2.6716÷5=3.13÷2=1.59÷4=2.251+2.67+3.1+1.5+2.25/5=2.1

FCFS:只考慮等待時(shí)間，而不考慮運(yùn)行時(shí)間。

SPJ、SJF：根據(jù)作業(yè)（進(jìn)程）占用處理機(jī)時(shí)間長短而定，注重了作業(yè)運(yùn)行時(shí)間。

SJF調(diào)度算法能有效地降低作業(yè)的平均等待時(shí)間和提高系統(tǒng)的吞吐量。

SJ(P)F調(diào)度算法的缺點(diǎn)：（1）該算法對長作業(yè)非常不利。（2）該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程）會(huì)得到及時(shí)處理；（3）由于作業(yè)（進(jìn)程）的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)執(zhí)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

FCFS與SJF都屬于非剝奪調(diào)度，不適用在合理的響應(yīng)時(shí)間應(yīng)得到保證的分時(shí)環(huán)境中。FCFS與SJF屬于非剝奪調(diào)度，還是可剝奪調(diào)度？3.2.2

優(yōu)先權(quán)（級）調(diào)度算法

該算法的核心是確定作業(yè)或進(jìn)程的優(yōu)先權(quán)。一、優(yōu)先權(quán)調(diào)度算法的類型

當(dāng)用于進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，這時(shí)又可進(jìn)一步把該算法分成兩種方式：

1.非搶占式優(yōu)先權(quán)算法

2.搶占式優(yōu)先權(quán)調(diào)度算法二、優(yōu)先權(quán)類型

設(shè)計(jì)優(yōu)先權(quán)的主要原則是充分地利用處理機(jī)，使用戶進(jìn)程盡可能地并行運(yùn)行。優(yōu)先權(quán)可分為靜態(tài)優(yōu)先權(quán)和動(dòng)態(tài)優(yōu)先權(quán)。

確定作業(yè)的靜態(tài)優(yōu)先權(quán)可根據(jù)以下原則：

（1）由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先權(quán)。（2）由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先權(quán)。作業(yè)類型可由用戶約定，也可以由操作員指定。（3）作業(yè)使用資源。1).靜態(tài)優(yōu)先權(quán)進(jìn)程的靜態(tài)優(yōu)先權(quán)確定原則：（1）進(jìn)程類型。（2）進(jìn)程對資源的要求。（3）根據(jù)用戶的要求。（4）將作業(yè)的靜態(tài)優(yōu)先權(quán)作為它所屬進(jìn)程的優(yōu)先級。

靜態(tài)優(yōu)先權(quán)法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)或進(jìn)程，長期沒有被調(diào)度的情況，而且靜態(tài)優(yōu)先級一旦確定之后，直到執(zhí)行結(jié)束為止始終保持不變，從而系統(tǒng)效率較低，調(diào)度性能不高。因此，僅在要求不太高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。2).動(dòng)態(tài)優(yōu)先權(quán)

動(dòng)態(tài)優(yōu)先權(quán)把作業(yè)或進(jìn)程的靜態(tài)特性和動(dòng)態(tài)特性結(jié)合起來確定作業(yè)或進(jìn)程的優(yōu)先權(quán)，隨著作業(yè)或進(jìn)程的執(zhí)行過程，其優(yōu)先權(quán)不斷變化。

動(dòng)態(tài)優(yōu)先權(quán)的確定原則：（1）根據(jù)進(jìn)程占有CPU時(shí)間的長短來決定。（2）根據(jù)就緒進(jìn)程等待CPU的時(shí)間長短來決定。3高響應(yīng)比優(yōu)先調(diào)度算法

(HighResponse-ratioNext)

BrichHansen發(fā)展的最高響應(yīng)比優(yōu)先調(diào)度策略修正了最短作業(yè)優(yōu)先調(diào)度的某些弱點(diǎn)，特別是后者忽視長作業(yè)，優(yōu)待新的短作業(yè)的弱點(diǎn)。HRN是一種非剝奪調(diào)度優(yōu)先權(quán)的變化可描述為：

響應(yīng)比要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)==+=R

該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，也不會(huì)使長作業(yè)長期得不到服務(wù)，是介于FCFS與SJF之間的一種算法，由于每次調(diào)用前，都要先進(jìn)行響應(yīng)比的計(jì)算，這會(huì)增加系統(tǒng)的開銷。

3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

（RoundRobin）一、基本原理

系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片，當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序根據(jù)這個(gè)信號來停止該進(jìn)程的執(zhí)行，把它放到就緒隊(duì)列的末尾，等待下一次執(zhí)行；然后再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就保證就緒隊(duì)列中的所有進(jìn)程，在一個(gè)給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。

輪轉(zhuǎn)法只能調(diào)度分配可搶占的資源，而作業(yè)調(diào)度是對除了CPU之外的所有系統(tǒng)硬件資源的分配，其中包含有不可搶占資源，比如說打印機(jī)，所以作業(yè)調(diào)度不使用輪轉(zhuǎn)法,也就是說輪轉(zhuǎn)法只適用于進(jìn)程調(diào)度。

輪轉(zhuǎn)法能否用于作業(yè)調(diào)度?二、時(shí)間片大小的確定

1、系統(tǒng)對響應(yīng)時(shí)間的要求響應(yīng)時(shí)間T與用戶進(jìn)程N(yùn)和時(shí)間片q成正比，T=Nq。當(dāng)進(jìn)程數(shù)目一定時(shí)，時(shí)間片量值與系統(tǒng)響應(yīng)時(shí)間成正比。

輪轉(zhuǎn)法的性能幾乎完全取決于時(shí)間片2、就緒隊(duì)列中進(jìn)程的數(shù)目T=Nq3、系統(tǒng)的處理能力

系統(tǒng)的處理能力是必須保證用戶鍵入的常用命令能在一個(gè)時(shí)間片內(nèi)處理完畢，否則將無法保證得到滿意的響應(yīng)時(shí)間，而且會(huì)使平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間都很長。

在時(shí)間片輪轉(zhuǎn)法中，就緒進(jìn)程按照先來先服務(wù)的原則排隊(duì)，每個(gè)進(jìn)程輪流地運(yùn)行大小相等的時(shí)間片，對短作業(yè)和I/O操作較高的作業(yè)是不利的。如果有緊急進(jìn)程進(jìn)入就緒隊(duì)列，并不能得到及時(shí)響應(yīng)。2多級反饋隊(duì)列調(diào)度算法

多級反饋隊(duì)列調(diào)度算法，事先不必知道各種進(jìn)程所需的執(zhí)行時(shí)間，而且還可以滿足各種類型進(jìn)程的需要，因而是目前公認(rèn)的較好的調(diào)度算法。優(yōu)先權(quán)高一級

二級

n級

就緒隊(duì)列1

就緒隊(duì)列2就緒隊(duì)列n

（先來先服務(wù)）（先來先服務(wù)）（輪轉(zhuǎn)）

剝奪

S1至CPUS1至CPU至CPU低時(shí)間片短時(shí)間片S1<S2<S3長

在采用多級反饋隊(duì)列調(diào)度算法的系統(tǒng)中，調(diào)度算法的實(shí)施過程如下：

3、多級反饋隊(duì)列調(diào)度算法的性能1、終端型作業(yè)用戶2、對于中短批處理型作業(yè)3、長批處理作業(yè)用戶（不會(huì)長期得不到處理）

Windows2000/XP調(diào)度策略線程時(shí)間配額：是一個(gè)線程從進(jìn)入運(yùn)行狀態(tài)到Windows2000/XP檢查是否有其他優(yōu)先級相同的線程需要開始運(yùn)行之間的時(shí)間總合。１.時(shí)間配額的計(jì)算缺省時(shí)，windows2000專業(yè)版線程時(shí)間配額為6,windows2000服務(wù)器版為36。每次時(shí)鐘中斷，時(shí)鐘中斷服務(wù)例程從線程的時(shí)間配額中減少３，如果沒有剩余的時(shí)間配額，系統(tǒng)將觸發(fā)時(shí)間配額用完處理，選擇另外一個(gè)線程進(jìn)入運(yùn)行狀態(tài)。時(shí)間配額的控制在系統(tǒng)注冊表中的一個(gè)注冊項(xiàng)“HKEY_LOCAL_MACHINE\SYSTEM\CurrentConctrolSet\Control\PriorityControl\Win32PrioritySeparation”,允許用戶指定線程時(shí)間配額的相對長度（長或短）和前臺(tái)進(jìn)程的時(shí)間配額是否加長。

6４２０時(shí)間配額長度前后臺(tái)變化前臺(tái)進(jìn)程時(shí)間配額提升注冊表Win32PrioritySeparation的定義時(shí)間配額長度：１—長時(shí)間，２—短時(shí)間，0,３—缺省前后臺(tái)變化：１—改變前臺(tái)進(jìn)程時(shí)間配額，２—前后臺(tái)進(jìn)程時(shí)間配額相同，0,３—缺省前臺(tái)進(jìn)程時(shí)間配額提升:該字段是一個(gè)時(shí)間配額表索引，用于設(shè)置前后臺(tái)進(jìn)程的時(shí)間配額，前臺(tái)為第一項(xiàng)，后臺(tái)為第二項(xiàng)。在任務(wù)管理器中修改進(jìn)程優(yōu)先級類型的方法是：在“進(jìn)程”欄中用鼠標(biāo)右擊下拉菜單中的“設(shè)置優(yōu)先級”。通過注冊表來設(shè)置時(shí)間配額時(shí)，用戶可對３個(gè)字段中的內(nèi)容進(jìn)行任意組合。通過“控制面板”來設(shè)置時(shí)間配額時(shí)，用戶只有２種選擇。設(shè)置方法：從“控制面板”中的“系統(tǒng)”或“我的電腦”中的“屬性”找到“性能”設(shè)置窗口。優(yōu)化應(yīng)用的性能：短時(shí)間配額和改變前臺(tái)進(jìn)程的時(shí)間配額優(yōu)化后臺(tái)服務(wù)的性能：長時(shí)間配額和前后臺(tái)進(jìn)程的時(shí)間配額相同一.單處理器系統(tǒng)中的線程調(diào)度1.主動(dòng)切換線程可能因?yàn)檫M(jìn)入等待狀態(tài)而主動(dòng)放棄處理器的使用，等待的對象可能是事件，互斥信號量，資源信號量，I/O操作，進(jìn)程，線程，窗口消息等。２.搶先可能出現(xiàn)搶先的情況：１)高優(yōu)先級線程的等待完成，即一個(gè)線程等待的事件出現(xiàn)。２）一個(gè)線程的優(yōu)先級被增加或減少。當(dāng)線程被搶先時(shí)，它被放到相應(yīng)優(yōu)先級的就緒隊(duì)列的隊(duì)首。處于實(shí)時(shí)優(yōu)先級的線程在搶先時(shí)，時(shí)間配額被重置為一個(gè)完整的時(shí)間片；而處于動(dòng)態(tài)優(yōu)先級的線程在被搶先時(shí)，時(shí)間配額不變，重新得到處理器使用權(quán)后將運(yùn)行到剩余的時(shí)間配額用完。被搶先的線程是排在就緒隊(duì)列的隊(duì)首，而不是隊(duì)尾。3.時(shí)間配額用完是否要降低該線程的優(yōu)先級，是否要調(diào)度另一個(gè)線程線程進(jìn)入運(yùn)行狀態(tài)。４.結(jié)束調(diào)用ExitThread,TerminateThread來終止。線程優(yōu)先級提升：1）I/O操作完成。2）信號量或事件等待結(jié)束。3）前臺(tái)進(jìn)程中的現(xiàn)程完成一個(gè)等待操作。4）由于窗口活動(dòng)而喚醒圖形用戶接口線程。5）線程處于就緒狀態(tài)超過一定時(shí)間，但沒能進(jìn)入運(yùn)行狀態(tài)（處理器饑餓）優(yōu)先級提升的目的：改進(jìn)系統(tǒng)吞吐量、響應(yīng)時(shí)間等整體特性，解決線程調(diào)度策略中潛在的不公正性。3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因(Continued)所謂死鎖,是指多個(gè)進(jìn)程因競爭資源而造成的一種僵局,若無外力作用,這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn).產(chǎn)生死鎖的原因資源不足導(dǎo)致的資源競爭進(jìn)程推進(jìn)順序不合理1競爭資源引起進(jìn)程死鎖系統(tǒng)中的資源分為兩類：可剝奪資源：某進(jìn)程在獲得這類資源后，該資源可以被其他進(jìn)程或系統(tǒng)剝奪。例子：cpu和主存不可剝奪資源：系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放。例子：磁帶，打印機(jī)2競爭非剝奪性資源資源分配圖涉及非剝奪性資源死鎖的例子3臨時(shí)競爭性資源由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一短暫時(shí)間便無使用的資源。例子：中斷,信號,消息,I/O緩沖區(qū)中的信息涉及臨時(shí)競爭資源死鎖的例子P1: … receive(P2); … send(P2,M1); …P2: … receive(P1); … send(P1,M2); …2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖(續(xù)）關(guān)于死鎖的一些結(jié)論：參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。3.5.2產(chǎn)生死鎖的必要條件互斥條件指進(jìn)程對所分配到的資源進(jìn)行排他性使用,即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占有.如果此時(shí)還有其它進(jìn)程要求該資源,要求者只能阻塞,直至占有該資源的進(jìn)程用畢釋放.請求和保持條件進(jìn)程已經(jīng)保持了至少一個(gè)資源,但又提出了新的資源要求,而該資源又已被其它進(jìn)程占有,此時(shí)請求進(jìn)程阻塞,但又對已經(jīng)獲得的其它資源保持不放.死鎖的必要條件(Continued)不剝奪條件進(jìn)程已獲得的資源,在未使用完之前,不能被剝奪,只能在使用完時(shí)由自己釋放.環(huán)路等待條件在發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程-資源的環(huán)形鏈.即進(jìn)程集合{P0,P1,P2,…,Pn}中的P0正在等待一個(gè)P1占用的資源;P1正在等待P2占用的資源,……,Pn正在等待已被P0占用的資源.3.5.3處理死鎖的基本方法預(yù)防死鎖：破壞產(chǎn)生死鎖的必要條件避免死鎖:在資源動(dòng)態(tài)分配的過程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)檢測死鎖：檢測死鎖，并清除死鎖解除死鎖：將進(jìn)程從死鎖狀態(tài)中解脫出來。3.6預(yù)防死鎖的方法通過破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或多個(gè)條件,保證不會(huì)發(fā)生死鎖互斥條件由設(shè)備的固有特性所決定,應(yīng)加以保證1.摒棄“請求和保持”系統(tǒng)要求所有進(jìn)程要一次性地申請?jiān)谡麄€(gè)運(yùn)行過程需的全部資源優(yōu)點(diǎn):簡單、易于實(shí)現(xiàn)、安全缺點(diǎn):資源嚴(yán)重浪費(fèi),進(jìn)程延遲運(yùn)行3.6.1預(yù)防死鎖2.摒棄“非剝奪”條件方法:一個(gè)已經(jīng)保持了某些資源的進(jìn)程,當(dāng)它再提出新的資源請求而不能立即得到滿足時(shí),必須釋放它已經(jīng)保持的所有資源,待以后需要時(shí)再重新申請OS可以剝奪一個(gè)進(jìn)程占有的資源,分配給其他進(jìn)程適用條件資源的狀態(tài)可以很容易地保存和恢復(fù)缺點(diǎn)實(shí)現(xiàn)復(fù)雜、代價(jià)大,反復(fù)申請/釋放資源,系統(tǒng)開銷大,降低系統(tǒng)吞吐量3.摒棄“環(huán)路等待”方法系統(tǒng)把所有資源按類型進(jìn)行線性排隊(duì);所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的順序提出,從而保證任何時(shí)刻的資源分配圖不出現(xiàn)環(huán)路問題:此方法要求資源類型序號相對穩(wěn)定,不便于添加新類型的設(shè)備.易造成資源浪費(fèi),類型序號的安排只能考慮一般作業(yè)的情況,限制用戶簡單、自主地編程3.6.2系統(tǒng)安全狀態(tài)不需事先采取限制措施破壞產(chǎn)生死鎖的必要條件;在資源的動(dòng)態(tài)分配過程中,采用某種策略防止系統(tǒng)進(jìn)入不安全狀態(tài),從而避免發(fā)生死鎖如果一個(gè)新的進(jìn)程的資源請求會(huì)導(dǎo)致死鎖,則拒絕啟動(dòng)這個(gè)進(jìn)程如果滿足一個(gè)進(jìn)程新提出的一項(xiàng)資源請求會(huì)導(dǎo)致死鎖,則拒絕分配資源給這個(gè)進(jìn)程

拒絕啟動(dòng)進(jìn)程策略在啟動(dòng)一個(gè)新的進(jìn)程時(shí),首先檢查它的資源請求,僅當(dāng)

當(dāng)前所有進(jìn)程的最大資源請求量+

新進(jìn)程的請求量<=

系統(tǒng)資源量

時(shí)才啟動(dòng)新進(jìn)程.考慮所有進(jìn)程的最大請求,條件過于嚴(yán)格.系統(tǒng)的安全狀態(tài)安全狀態(tài):系統(tǒng)能按某種順序,如<P1,P2,…,Pn>,為每個(gè)進(jìn)程分配所需資源,直到最大需求,使每個(gè)進(jìn)程都可順序完成,稱系統(tǒng)處于安全狀態(tài).安全序列:上述的資源分配順序,如<P1,P2,…,Pn>.安全序列可以不唯一!不安全狀態(tài):系統(tǒng)中不存在安全序列.不安全狀態(tài)不一定是死鎖狀態(tài).只要系統(tǒng)處于安全狀態(tài),必定不會(huì)進(jìn)入死鎖狀態(tài).避免死鎖的實(shí)質(zhì):如何使系統(tǒng)不進(jìn)入不安全狀態(tài).銀行貸款問題的描述銀行有一筆數(shù)目有限的現(xiàn)金可供借貸,以及一批借貸客戶.每個(gè)客戶有各自的借款限額(最大借款額).客戶可在借款限額范圍內(nèi)一次借貸一部分現(xiàn)金,且不保證在獲得最大貸款額之前做出任何償付.如果在滿足一個(gè)客戶的一次借貸請求之后,銀行可能沒有足夠的資金以保證所有客戶最終償還所有貸款,那么銀行可以拒絕這項(xiàng)請求.例:某銀行共有資金100萬元和三個(gè)借貸客戶甲、乙、丙,他們的最大借款額分別為100,80,70(萬元).他們已借得的金額分別為10,20,50(萬元).銀行還有資金多少?各客戶還需多少資金?按目前狀況,銀行可能收回全部貸款嗎?如果乙提出借10萬,可以滿足嗎?如果丙提出借10萬,可以滿足嗎?銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

設(shè)系統(tǒng)中有m種不同資源,n個(gè)進(jìn)程Resource向量:系統(tǒng)中每種資源的總量Resource[j]:資源j的總量Available向量:系統(tǒng)中尚未分配的每種資源的總量Available[j]:尚未分配的資源j的數(shù)量Max矩陣:各個(gè)進(jìn)程對每種資源的最大需求量(進(jìn)程事先聲明)Max[i,j]:進(jìn)程i對資源j的最大需求量Allocation矩陣:當(dāng)前資源分配狀況Allocation[i,j]:進(jìn)程i獲得的資源j的數(shù)量Need矩陣:每個(gè)進(jìn)程尚需的各類資源數(shù)量Need[i,j]:進(jìn)程i尚需的資源j的數(shù)量各數(shù)據(jù)間的關(guān)系對所有的i,j(i=1,2,…,n;j=1,2,…,m),有:Resource[j]=Available[j]+(Allocation[1,j]+Allocation[2,j]+…+Allocation[n,j])Max[i,j]<=Resource[j]Allocation[i,j]<=Max[i,j]Allocation[i,j]+Need[i,j]=Max[i,j]二銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti[j]=k,表示進(jìn)程Pi需要k個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：（1）如果Requesti<=Needi,則轉(zhuǎn)向步驟(2)，否則，認(rèn)為出錯(cuò)，因?yàn)樗暾埖馁Y源已超過它所宣布的最大值；（2）如果Requesti<=Availablei,則轉(zhuǎn)向步驟(3)，否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。（3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面的數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available=Available-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才是將資源分配給進(jìn)程Pi,以完成此次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓Pi等待。三安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（1）設(shè)置兩個(gè)向量工作向量Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)目，它包含有m個(gè)元素，執(zhí)行安全算法時(shí)，Work=Available

進(jìn)程是否完成標(biāo)志finish:開始時(shí)先令finish[i]=false;當(dāng)有足夠的資源分配給進(jìn)程時(shí)，令finish[i]=true(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程

finish[i]=falseneed[i]<=work

如果找到，執(zhí)行步驟（3），否則執(zhí)行步驟（4）（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源：Work=work+Allocation[i]finish[i]=true

轉(zhuǎn)向（2）（4）如果所有進(jìn)程的finish[i]=true,則表示系統(tǒng)處于安全狀態(tài)，否則，系統(tǒng)處于不安全狀態(tài)。一個(gè)安全性計(jì)算的實(shí)例死鎖避免小結(jié)優(yōu)點(diǎn)比死鎖預(yù)防限制少無死鎖檢測中的資源剝奪,進(jìn)程重啟缺點(diǎn)必須事先聲明每個(gè)進(jìn)程請求的最大資源考慮的進(jìn)程必須是無關(guān)的,也就是說,它們執(zhí)行的順序沒有任何同步要求的限制資源數(shù)目必須是固定的在占有資源時(shí),進(jìn)程不能退出3.7死鎖的檢測與解除3.7.1死鎖的檢測系統(tǒng)必須:保存有關(guān)資源的請求和分配信息提供一種算法,以利用這些信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)1.資源分配圖資源類（資源的不同類型）:用方框表示資源實(shí)例（存在于每個(gè)資源中）:用方框中的黑圓點(diǎn)表示進(jìn)程:用圓圈中加進(jìn)程名表示分配邊：資源實(shí)例進(jìn)程的一條有向邊申請邊：進(jìn)程資源類的一條有向邊有環(huán)有死鎖有環(huán)無死鎖2.死鎖定理

如果資源分配圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中可能存在死鎖如果每個(gè)資源類中只包含一個(gè)資源實(shí)例，則環(huán)路是死鎖存在的充分必要條件資源分配圖化簡方法如下:1）找一個(gè)非孤立點(diǎn)進(jìn)程結(jié)點(diǎn)且只有分配邊，去掉分配邊，將其變?yōu)楣铝⒔Y(jié)點(diǎn)2）再把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，即將某進(jìn)程的申請邊變?yōu)榉峙溥?)進(jìn)行一系列的簡化后，若能消去圖中所有的邊，使所有的進(jìn)程結(jié)點(diǎn)都成為孤立的結(jié)點(diǎn)，則該圖是可完全簡化。否則該圖是不可完全簡化的。3.死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available(2)把不占用資源的進(jìn)程(向量Allocation:=0)記入L表中,即LiUL.(3)從進(jìn)程集合中找到一個(gè)Requesti<=Work的進(jìn)程,做如下處理:將其資源分配圖簡化,釋放資源,增加工作向量work:=work+Allocationi將它記入L表中(4)若不能把所有進(jìn)程都記入L表中,該系統(tǒng)狀態(tài)將發(fā)生死鎖.Work:=Available;L:={Li|Allocationi=0∩Requesti=0}ForallLi不屬于LdoBeginforallRequesti<=workdobeginwork:=work+AllocationiLiUL;EndEndDeadlock:=?(L={p1,p2,…pn});

3.7.2死鎖的解除方法:取消所有的死鎖進(jìn)程把每個(gè)死鎖進(jìn)程備份到前面定義的某些檢查點(diǎn),并且重新啟動(dòng)所有進(jìn)程連續(xù)取消死鎖進(jìn)程直到不再存在死鎖連續(xù)剝奪資源直到不再存在死鎖選擇取消死鎖進(jìn)程或剝奪資源時(shí)要考慮代價(jià)問題進(jìn)程和線程函數(shù)（一）CreateProcess**CreateThread****ExitProcess**ExitThread***GetCurrentProcess*GetCurrentProcessId*GetCurrentThread****GetCurrentThreadId****進(jìn)程和線程函數(shù)(二)GetExitCodeProcess*GetExitCodeThread*GetThreadPriority****OpenProcess*ResumeThread***SetThreadPriority***Sleep*CloseHandle****進(jìn)程和線程函數(shù)(三)SuspendThread***TerminateProcess**TerminateThread***ThreadProc****同步函數(shù)(一)臨界段Critical_Section類型InitializeCriticalSection*DeleteCriticalSection*EnterCriticalSection*LeaveCriticalSection*TryEnterCriticalSection*同步函數(shù)(二)互斥體(Mutex)和信號量(Semaphore)：類型是HANDLECreateMutex****ReleaseMutex****CreateSemaphore****ReleaseSemaphore****CloseHandle****同步函數(shù)(三)Wait函數(shù)WaitForMultipleObjects****WaitForMultipleObjectsEx**WaitForSingleObject****WaitForSingleObjectEx**相關(guān)頭文件:#include<winbase.h>庫文件：kernel32.lib調(diào)試函數(shù)GetLastError()TRACE宏printf()coutsprintf()2）交換調(diào)度（中級調(diào)度）（均衡調(diào)度）：按照給定的原則實(shí)現(xiàn)進(jìn)程在主存和外存交換區(qū)之間的換進(jìn)換出，以解決內(nèi)存緊張問題，特別是具有虛擬存儲(chǔ)器的系統(tǒng)中。3）進(jìn)程調(diào)度（低級調(diào)度）：按照某種策略從進(jìn)程就緒隊(duì)列中選擇一個(gè)就緒進(jìn)程，使其占有處理機(jī)運(yùn)行。處理機(jī)調(diào)度可以分為3級：1）作業(yè)調(diào)度（高級調(diào)度）：按一定原則選擇若干個(gè)后備作業(yè)調(diào)入主存，分配資源，并建立相應(yīng)的進(jìn)程，投入運(yùn)行。當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收資源。二、作業(yè)調(diào)度的功能

作業(yè)調(diào)度的主要任務(wù)：完成作業(yè)從后備狀態(tài)到運(yùn)行狀態(tài)和從運(yùn)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。1）記錄系統(tǒng)中各作業(yè)的狀況。

作業(yè)調(diào)度程序應(yīng)包括以下功能：

作業(yè)調(diào)度程序?yàn)榱颂暨x一個(gè)作業(yè)投入運(yùn)行，并且在運(yùn)行中對它實(shí)施管理，它必須掌握該作業(yè)進(jìn)入系統(tǒng)時(shí)的有關(guān)情況并隨時(shí)記錄該作業(yè)在各運(yùn)行階段的變化。為此，系統(tǒng)為每一個(gè)已進(jìn)入系統(tǒng)的作業(yè)分配一個(gè)作業(yè)控制塊JCB(JobContrlblock)。每個(gè)作業(yè)的JCB在該作業(yè)進(jìn)入后備狀態(tài)時(shí)由系統(tǒng)建立．在該作業(yè)退出系統(tǒng)時(shí)由系統(tǒng)撤消。每個(gè)作業(yè)在各階段的情況(包括分配的資源和作業(yè)狀態(tài)等)都記錄在它的JCB中。2)按一定的調(diào)度算法，從后備作業(yè)中挑選出一個(gè)或幾個(gè)作業(yè)運(yùn)行。系統(tǒng)中處于后備狀態(tài)的作業(yè)較多，幾十個(gè)甚至幾百個(gè)，處于運(yùn)行狀態(tài)的作業(yè)只是有限的幾個(gè)如最多不超過4個(gè)或8個(gè)。作業(yè)調(diào)度程序的一個(gè)重要職能就是在適當(dāng)?shù)臅r(shí)候按一定的調(diào)度原則從后備作業(yè)中挑選出若干個(gè)作業(yè)投入運(yùn)行。3)為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。為該作業(yè)建立相應(yīng)的進(jìn)程，并且為這些進(jìn)程提供所需的資源，如內(nèi)存和外部設(shè)備等。4)在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。

輸出如運(yùn)行時(shí)間、作業(yè)執(zhí)行情況等必要信息，回收該作業(yè)所占用的全部資源，撤消與該作業(yè)有關(guān)的全部進(jìn)程和該作業(yè)的作業(yè)控制塊。注：1）處理機(jī)的分配工作由進(jìn)程調(diào)度程序完成。內(nèi)存的分配和釋放工作由存貯管理程序完成。外部設(shè)備的分配和釋放工作由設(shè)備管理程序完成。三、作業(yè)控制塊2）作業(yè)調(diào)度程序只保證被選中的作業(yè)獲得使用處理機(jī)的資格，把一個(gè)作業(yè)的內(nèi)存、外設(shè)要求轉(zhuǎn)給相應(yīng)的管理程序。

作業(yè)控制塊JCB是作業(yè)存在的標(biāo)志，記錄與該作業(yè)有關(guān)的信息。作業(yè)調(diào)度算法

按作業(yè)來到的先后次序進(jìn)行調(diào)度。這種算法優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長的作業(yè)，而不管它要求運(yùn)行時(shí)間的長短。優(yōu)點(diǎn)：容易實(shí)現(xiàn)；缺點(diǎn)：沒有考慮各個(gè)作業(yè)運(yùn)行特征和資源要求的差異，系統(tǒng)效率較低。1.先來先服務(wù)調(diào)度算法（FCFS）

例：先來先服務(wù)調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)）作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周轉(zhuǎn)時(shí)間T＝1.725平均帶權(quán)周轉(zhuǎn)時(shí)間W＝6.8752.短作業(yè)優(yōu)先調(diào)度算法（SJF）

此算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè)。優(yōu)點(diǎn)：易于實(shí)現(xiàn)，效率比較高。缺點(diǎn)：只照顧短作業(yè)而不考慮長作業(yè)的利益。如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長作業(yè)長時(shí)間等待而不能運(yùn)行。例：短作業(yè)優(yōu)先調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)）作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.101.101149.500.2010.1010.300.804平均周轉(zhuǎn)時(shí)間T＝1.55平均帶權(quán)周轉(zhuǎn)時(shí)間W＝5.153.響應(yīng)比高者優(yōu)先調(diào)度算法

響應(yīng)比是指作業(yè)的響應(yīng)時(shí)間與作業(yè)估計(jì)運(yùn)行時(shí)間的比值。

選擇原則是優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等待時(shí)間長和運(yùn)行時(shí)間短的作業(yè)，它是FCFS和SJF算法的結(jié)合。響應(yīng)比＝1＋作業(yè)等待時(shí)間/執(zhí)行時(shí)間

作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.008.0010.002.00128.500.5010.1010.602.104.239.000.1010.0010.101.101149.500.2010.6010.801.306.5例：響應(yīng)比高者優(yōu)先調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì))平均周轉(zhuǎn)時(shí)間T＝1.625，平均帶權(quán)周轉(zhuǎn)時(shí)間W＝5.675

響應(yīng)比＝1＋作業(yè)等待時(shí)間/執(zhí)行時(shí)間例如：當(dāng)作業(yè)3結(jié)束時(shí)，Rp2=1＋作業(yè)等待時(shí)間/可執(zhí)行時(shí)間=1+(10.10-8.50)/0.5=1+3.2Rp4=1＋作業(yè)等待時(shí)間/可執(zhí)行時(shí)間=1+(10.10-9.50)/0.2=1+3

這種算法是根據(jù)確定的優(yōu)先數(shù)來選取作業(yè)，每次總是選擇優(yōu)先級最高的作業(yè)。4.最高優(yōu)先級優(yōu)先調(diào)度算法規(guī)定用戶作業(yè)優(yōu)先數(shù)的方法:1）由用戶自己提出作業(yè)的優(yōu)先數(shù)。有的用戶為了自己的作業(yè)盡快被系統(tǒng)選中就設(shè)法提高自己作業(yè)的優(yōu)先數(shù)，這時(shí)系統(tǒng)可以規(guī)定優(yōu)先數(shù)越高則需付出的計(jì)算機(jī)使用費(fèi)就越多，以作限制。2）由系統(tǒng)綜合有關(guān)因素來確定用戶作業(yè)的優(yōu)先數(shù)。

例如，根據(jù)作業(yè)的緩急程度、作業(yè)計(jì)算時(shí)間的長短、等待時(shí)間的多少、資源申請情況等來確定優(yōu)先數(shù)。確定優(yōu)先數(shù)時(shí)，各因素的比例應(yīng)根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)來分析這些因素在系統(tǒng)中的地位而決定。3.3進(jìn)程調(diào)度進(jìn)程調(diào)度：就是系統(tǒng)按照某種算法把CPU動(dòng)態(tài)地分配給某一就緒進(jìn)程。進(jìn)程調(diào)度工作是通過進(jìn)程調(diào)度程序來完成的。一、調(diào)度/分派結(jié)構(gòu)調(diào)度程序：將進(jìn)程插入就緒隊(duì)列，按一定原則保持隊(duì)列結(jié)構(gòu)；分派程序：將進(jìn)程從就緒隊(duì)列中移出，建立它執(zhí)行的機(jī)器狀態(tài)。進(jìn)程切換：把一個(gè)進(jìn)程讓出處理機(jī)，由另一個(gè)進(jìn)程占用處理機(jī)的調(diào)度過程稱為“進(jìn)程切換”。

分派程序首先將正在執(zhí)行的進(jìn)程的CPU現(xiàn)場信息保存在該進(jìn)程PCB的現(xiàn)場保護(hù)區(qū)中，再從被調(diào)度選中的進(jìn)程PCB的現(xiàn)場保護(hù)區(qū)中取出它的CPU現(xiàn)場信息恢復(fù)。CPU現(xiàn)場信息由程序狀態(tài)寄存器、程序計(jì)數(shù)器以及若干通用寄存器的內(nèi)容組成。1.記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況。

二、進(jìn)程調(diào)度功能

記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況，對進(jìn)程控制塊PCB的內(nèi)容作相應(yīng)的登記、修改，記錄進(jìn)程的狀態(tài)特征。2.按照一定調(diào)度策略選擇一個(gè)占有處理機(jī)的就緒進(jìn)程。

在處理機(jī)空閑時(shí)根據(jù)一定的原則選擇一個(gè)進(jìn)程去運(yùn)行，同時(shí)確定獲得處理機(jī)的時(shí)間。3.實(shí)施處理機(jī)的分配和回收(進(jìn)行進(jìn)程上下文切換)?；厥?正在運(yùn)行的進(jìn)程由于某種原因讓出處理機(jī)，該進(jìn)程的狀態(tài)改為“阻塞”，插入到相應(yīng)隊(duì)列中，保留該進(jìn)程的CPU現(xiàn)場。分配:根據(jù)調(diào)度原則選擇進(jìn)程去運(yùn)行，把選中進(jìn)程從就緒隊(duì)列中移出,改狀態(tài)為“運(yùn)行”，把CPU控制權(quán)交給被選中的進(jìn)程，將選中進(jìn)程的有關(guān)PCB現(xiàn)場信息，分別送到相應(yīng)的寄存器中。三、進(jìn)程調(diào)度時(shí)機(jī)

1）正在執(zhí)行的進(jìn)程完成其任務(wù)而運(yùn)行完畢。2）執(zhí)行中的進(jìn)程由于請求某個(gè)事件的發(fā)生，比如I/O請求，等待所需要的信號、信件的到來等而自己調(diào)用阻塞原語將自己阻塞起來，進(jìn)入相應(yīng)的等待隊(duì)列。3）在分時(shí)系統(tǒng)中，當(dāng)進(jìn)程使用完規(guī)定的時(shí)間片。4）在采用可搶占調(diào)度方式的系統(tǒng)中，當(dāng)具有更高優(yōu)先級的進(jìn)程要求使用處理機(jī)。四、進(jìn)程調(diào)度方式

1.非搶先調(diào)度方式這種方式是當(dāng)有重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，仍然讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成任務(wù)終止運(yùn)行或發(fā)生某種等待事件而進(jìn)入阻塞狀態(tài)時(shí)，才主動(dòng)放棄占有的處理機(jī)，把處理機(jī)分配給重要或緊迫的就緒進(jìn)程，以使其運(yùn)行。2.可搶先調(diào)度方式這種方式則是重要或緊迫的進(jìn)程一到，便把正在執(zhí)行的進(jìn)程占有的處理機(jī)強(qiáng)行剝奪下來，并轉(zhuǎn)給這個(gè)優(yōu)先級比它更高的重要或緊迫的就緒進(jìn)程，使其運(yùn)行。五、進(jìn)程調(diào)度算法

采用最高優(yōu)先級優(yōu)先調(diào)度算法時(shí)，系統(tǒng)對每個(gè)進(jìn)程確定一個(gè)優(yōu)先數(shù)，進(jìn)程的優(yōu)先數(shù)用于表示進(jìn)程的重要性及運(yùn)行的優(yōu)先性。調(diào)度時(shí)，系統(tǒng)把處理機(jī)分配給優(yōu)先級最高的就緒進(jìn)程。如果就緒進(jìn)程具有相同的優(yōu)先數(shù)，則再按先來先服務(wù)的次序分配處理機(jī)。

先來先服務(wù)調(diào)度算法是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來選擇進(jìn)程分配處理機(jī)。（一）最高優(yōu)先級優(yōu)先調(diào)度算法系統(tǒng)確定優(yōu)先數(shù)的方法：

1.靜態(tài)優(yōu)先數(shù)法：靜態(tài)優(yōu)先數(shù)是在創(chuàng)建進(jìn)程時(shí)系統(tǒng)為其確定的，并且在進(jìn)程的生命期內(nèi)不再改變。確定靜態(tài)優(yōu)先數(shù)的原則：1）按進(jìn)程類型。系統(tǒng)進(jìn)程的優(yōu)先級高于用戶進(jìn)程的優(yōu)先級。2）按進(jìn)程使用的資源。進(jìn)程所使用的資源越多，進(jìn)程的優(yōu)先級越低；反之，則進(jìn)程的優(yōu)先級越高。3）按進(jìn)程的估計(jì)運(yùn)行時(shí)間。進(jìn)程的估計(jì)運(yùn)行時(shí)間越長，進(jìn)程的優(yōu)先級越低；反之，則進(jìn)程的優(yōu)先級越高。4）由用戶指定。有些系統(tǒng)可以按收費(fèi)標(biāo)準(zhǔn)不同，設(shè)置不同的優(yōu)先級別，可以由用戶指定。靜態(tài)優(yōu)先級法實(shí)現(xiàn)起來比較簡單，但不能反映系統(tǒng)以及進(jìn)程在運(yùn)行過程中的動(dòng)態(tài)變化情況，系統(tǒng)管理效果顯然不佳。2.動(dòng)態(tài)優(yōu)先數(shù)法。動(dòng)態(tài)優(yōu)先數(shù)是指在系統(tǒng)創(chuàng)建進(jìn)程時(shí)，根據(jù)系統(tǒng)資源的使用情況和進(jìn)程的當(dāng)前特點(diǎn)確定一個(gè)優(yōu)先數(shù)，然后，在進(jìn)程運(yùn)行過程中再根據(jù)情況的變化動(dòng)態(tài)調(diào)整進(jìn)程的優(yōu)先數(shù)。調(diào)整進(jìn)程優(yōu)先數(shù)的原則：

1）進(jìn)程占有處理機(jī)的時(shí)間越長，則進(jìn)程的優(yōu)先級越低；進(jìn)程的等待時(shí)間越長，則進(jìn)程的優(yōu)先級越高。2）根據(jù)進(jìn)程所執(zhí)行的程序的輕重緩急程度，調(diào)整進(jìn)程的優(yōu)先數(shù)。（二）時(shí)間片輪轉(zhuǎn)調(diào)度算法

在分時(shí)系統(tǒng)中，為了滿足系統(tǒng)對響應(yīng)時(shí)間的要求，通常采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。1.簡單輪轉(zhuǎn)法(固定時(shí)間片輪轉(zhuǎn)法）

在這種調(diào)度算法中，系統(tǒng)把所有就緒進(jìn)程按到達(dá)的先后順序形成一個(gè)就緒隊(duì)列，就緒隊(duì)列中的所有進(jìn)程按時(shí)間片依次輪流獲得處理機(jī)。

時(shí)間片的大小應(yīng)根據(jù)進(jìn)程要求系統(tǒng)給出應(yīng)答的時(shí)間和進(jìn)入系統(tǒng)的進(jìn)程數(shù)來決定?？梢员硎緸椋浩渲校琿是時(shí)間片的大小，T是系統(tǒng)的響應(yīng)時(shí)間，N是進(jìn)入系統(tǒng)的進(jìn)程數(shù)。

簡單輪轉(zhuǎn)法的優(yōu)點(diǎn)是簡單、方便，但由于采用固定時(shí)間片的方式，調(diào)度欠靈活，服務(wù)質(zhì)量不夠理想?？梢酝ㄟ^以下兩個(gè)方面加以改進(jìn)：1）將固定時(shí)間片方式改為可變時(shí)間片方式；2）將單就緒隊(duì)列改為多就緒隊(duì)列。2.可變時(shí)間片輪轉(zhuǎn)法

時(shí)間片可變會(huì)給系統(tǒng)帶來好處。如果要求系統(tǒng)快速應(yīng)答，則時(shí)間片小一些，這樣可使輪轉(zhuǎn)一遍的總時(shí)間減少而可對進(jìn)程盡快應(yīng)答。如果進(jìn)程數(shù)少，則時(shí)間片可以大一些，這樣可減少進(jìn)程調(diào)度的次數(shù)，提高系統(tǒng)效率?？勺儠r(shí)間片輪轉(zhuǎn)法中，可采取如下措施調(diào)整時(shí)間片：1)固定周期輪轉(zhuǎn)法。在這種方法中，每一輪調(diào)度中所得的時(shí)間片q＇值的大小僅在這一輪調(diào)度中有效。系統(tǒng)的響應(yīng)時(shí)間T固定，在每一輪調(diào)度中，根據(jù)當(dāng)前就緒隊(duì)列中的進(jìn)程數(shù)n計(jì)算這一輪調(diào)度的時(shí)間片：q＇＝T/n，然后進(jìn)行輪轉(zhuǎn)，每個(gè)進(jìn)程可獲得這一輪的一個(gè)時(shí)間片q＇。在此期間所到達(dá)的進(jìn)程暫不進(jìn)入就緒隊(duì)列，等此次輪轉(zhuǎn)完畢再一并進(jìn)入。系統(tǒng)根據(jù)此時(shí)就緒隊(duì)列的進(jìn)程數(shù)重新計(jì)算時(shí)間片q＇，然后開始下一輪循環(huán)。2)時(shí)間片的大小取決于優(yōu)先級的高低，優(yōu)先級高的進(jìn)程分得的時(shí)間片較大，優(yōu)先級低的進(jìn)程分得的時(shí)間片較小。3)短作業(yè)的時(shí)間片較小，長作業(yè)的時(shí)間片較大。3.多級反饋輪轉(zhuǎn)法（多重時(shí)間片輪轉(zhuǎn)調(diào)度算法）

調(diào)度算法的實(shí)施過程如下：1.設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)就緒隊(duì)列賦予不同的優(yōu)先級。第一個(gè)就緒隊(duì)列的優(yōu)先級最高，第二個(gè)就緒隊(duì)列的優(yōu)先級次之，其余各個(gè)就緒隊(duì)列的優(yōu)先級逐個(gè)降低。2.賦予各個(gè)就緒隊(duì)列中進(jìn)程的時(shí)間片也各不相同，優(yōu)先級越高的就緒隊(duì)列中的進(jìn)程的時(shí)間片越小，反之，優(yōu)先級越低的就緒隊(duì)列中的進(jìn)程的時(shí)間片越大。3.當(dāng)一個(gè)新被創(chuàng)建的進(jìn)程進(jìn)入就緒隊(duì)列后，首先將它加入第一個(gè)就緒隊(duì)列的隊(duì)尾，按先來先服務(wù)的原則排隊(duì)等待調(diào)度。

當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如能在該時(shí)間片內(nèi)完成，則該進(jìn)程將被撤消；如果在一個(gè)時(shí)間片結(jié)束時(shí)該進(jìn)程尚未完成，調(diào)度程序則將該進(jìn)程轉(zhuǎn)入第二個(gè)就緒隊(duì)列的隊(duì)尾，按先來先服務(wù)的原則排隊(duì)等待調(diào)度；如果它在第二個(gè)就緒隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再以同樣的方法將它轉(zhuǎn)入第三個(gè)就緒隊(duì)列的隊(duì)尾，如此下去。4.僅當(dāng)?shù)谝粋€(gè)就緒隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?至第i–1個(gè)就緒隊(duì)列均為空時(shí)，才會(huì)調(diào)度第i個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i個(gè)就緒隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級較高的就緒隊(duì)列時(shí)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i個(gè)就緒隊(duì)列的隊(duì)尾，然后將處理機(jī)重新分配給新進(jìn)程。§3.4死鎖

一、死鎖的概念死鎖：各并發(fā)進(jìn)程彼此互相等待對方所擁有的資源，且這些并發(fā)進(jìn)程在得到對方的資源之前不會(huì)釋放自己所擁有的資源。從而造成系統(tǒng)中一些進(jìn)程處于無休止的等待狀態(tài)，在無外力作用的情況下，這些進(jìn)程永遠(yuǎn)也不能繼續(xù)前進(jìn)。我們稱這種現(xiàn)象為死鎖。例：系統(tǒng)中只有一臺(tái)輸入機(jī)R1和一臺(tái)打印機(jī)R2可供進(jìn)程P1和P2共享。進(jìn)程P1進(jìn)程P2┇┇請求資源R1請求資源R2┇┇

請求資源R2請求資源R1┇┇

釋放資源R1釋放資源R2┇┇釋放資源R2釋放資源R1

┇┇

R1R2

兩個(gè)進(jìn)程死鎖的典型情況

進(jìn)程在同步和通信的過程當(dāng)中也會(huì)產(chǎn)生死鎖。

例如，在生產(chǎn)者—消費(fèi)者問題中，若把生產(chǎn)者進(jìn)程中兩個(gè)P操作的順序顛倒如下圖所示：生產(chǎn)者進(jìn)程Pi

生產(chǎn)一個(gè)產(chǎn)品

產(chǎn)品送入緩沖區(qū)P(avail)

P(mutex)V(mutex)

V(full)

在這種情況下，當(dāng)緩沖區(qū)都已放滿了產(chǎn)品時(shí)，生產(chǎn)者仍可執(zhí)行P(mutex)操作，于是該生產(chǎn)者掌握了對緩沖區(qū)的存取控制權(quán)，當(dāng)它繼續(xù)執(zhí)行P(avail)操作時(shí)，由于沒有空緩沖區(qū)，該生產(chǎn)者被阻塞，并在avail上等待。若此時(shí)有一個(gè)消費(fèi)者到達(dá)，盡管緩沖區(qū)中有產(chǎn)品，消費(fèi)者在執(zhí)行P(full)操作時(shí)通過，但緊接著執(zhí)行P(mutex)操作時(shí)，將因緩沖區(qū)已被阻塞的生產(chǎn)者所占有，而使消費(fèi)者無法獲得緩沖區(qū)的存取控制權(quán)而被阻塞。此時(shí)，出現(xiàn)了生產(chǎn)者和消費(fèi)者之間僵死的局面，亦即發(fā)生了死鎖。二、產(chǎn)生死鎖的原因

產(chǎn)生的根本原因是系統(tǒng)能夠提供的資源數(shù)少于需要該資源的進(jìn)程數(shù)(系統(tǒng)資源不足)。1）對資源的分配策略（請求順序）不當(dāng)

；2）進(jìn)程推進(jìn)順序非法。

死鎖起因是并發(fā)進(jìn)程的資源競爭。但資源競爭并不一定產(chǎn)生死鎖。例如，在前一個(gè)例子中，進(jìn)程P1和P2的不同進(jìn)展情況將產(chǎn)生不同的結(jié)果。

P1和P2都占用R1

P1和P2都占用R2

P2的進(jìn)展

P1的進(jìn)展

占用R1占用R2釋放R1釋放R2請求R1請求R2請求R1

請求R2釋放R1

釋放R2

占用R1123占用R2下面用圖示來說明進(jìn)程P1和P2的三種可能的進(jìn)展情況：產(chǎn)生死鎖的必要條件1）互斥條件。進(jìn)程對其所要求的資源進(jìn)行排它性控制，即一次只有一個(gè)進(jìn)程可以使用一個(gè)資源。2）不剝奪條件。進(jìn)程所獲得的資源在未被釋放之前，不能被其它進(jìn)程強(qiáng)行剝奪。3）占有且等待條件。進(jìn)程每次申請它所需要的一部分資源，在進(jìn)程等待分配其它資源的同時(shí)，可以占有已分配的資源。P1P2R1R2被占有

被占有

請求請求4）環(huán)路條件。在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的循環(huán)等待鏈，三、解決死鎖問題的方法（一）死鎖的防止(預(yù)防)1．破壞互斥條件為了破壞資源使用的互斥條件，就要允許多個(gè)進(jìn)程同時(shí)訪問共享資源。但是這種方法受到資源本身固有特性的限制，對某些資源是行不通的。例如打印機(jī)，就不允許多個(gè)進(jìn)程在其運(yùn)行期間交替打印數(shù)據(jù)，打印機(jī)只能互斥使用。而文件，可能允許多個(gè)進(jìn)程對其進(jìn)行讀訪問，但只允許互斥地寫訪問。因此，互斥條件難以破壞。

死鎖的防止是通過設(shè)置某些嚴(yán)格的限制條件，以破壞產(chǎn)生死鎖的必要條件來防止死鎖的發(fā)生。

2．破壞不剝奪條件該策略規(guī)定，一個(gè)已保持了某些資源的進(jìn)程，若新的資源要求不能立即得到滿足，它必須釋放已保持的所有資源。以后再需要時(shí)重新申請。這意味著，一個(gè)進(jìn)程已占有的資源，在運(yùn)行過程中可能暫時(shí)地釋放，或說被剝奪。問題：1）這種防止死鎖的策略實(shí)現(xiàn)起來比較復(fù)雜；2）一個(gè)資源在使用一段時(shí)間后被釋放，可能會(huì)造成前階段工作的失效，即使采取某些防范措施，也還會(huì)使前后兩次運(yùn)行的信息不連續(xù)。3）該策略還可能由于反復(fù)地申請和釋放資源，使進(jìn)程的執(zhí)行無限推遲。這不僅延長了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開銷，又降低了系統(tǒng)吞吐量。3．破壞占有且等待條件----資源的靜態(tài)分配策略系統(tǒng)要求所有進(jìn)程一次性地申請其所需的全部資源。若系統(tǒng)有足夠的資源分配給該進(jìn)程時(shí)，便一次把所有其所需的資源分配給該進(jìn)程。這樣，該進(jìn)程在整個(gè)運(yùn)行期間，便不會(huì)再提出任何資源要求，從而使請求條件不成立。但在分配時(shí)只要有一種資源要求不能滿足，則已有的其它資源也全部不分配給該進(jìn)程，該進(jìn)程只能等待。由于等待期間的進(jìn)程不占有任何資源，因此，破壞了必要條件之3，防止了死鎖發(fā)生。優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)，且很安全。缺點(diǎn)：1）資源嚴(yán)重浪費(fèi)。一個(gè)進(jìn)程一次獲得其所需的全部資源且獨(dú)占，其中可能有些資源很少使用，甚至在整個(gè)運(yùn)行期間都未使用，這就嚴(yán)重地惡化了系統(tǒng)資源利用率：2）進(jìn)程延遲運(yùn)行。僅當(dāng)進(jìn)程獲得其所需全部資源后，方能開始運(yùn)行，但可能有許多資源長期被其它進(jìn)程占用，致使進(jìn)程推遲運(yùn)行，這往往要經(jīng)過很長的時(shí)延。4.破壞環(huán)路條件----有序資源分配策略對系統(tǒng)中的全部資源按類型進(jìn)行編號，編號的原則是較為緊缺的資源給以一個(gè)較大的序號。并且要求每一個(gè)進(jìn)程在申請資源時(shí)應(yīng)按照編號遞增的順序請求資源。也就是說，只要進(jìn)程提出請求資源Ri（i為系統(tǒng)資源編號），則在以后的請求中，只能請求排在Ri后面的資源，不能在申請編號低于Ri的那些資源。

對資源申請作了這樣的限制之后，在進(jìn)程資源分配圖中不可能再出現(xiàn)環(huán)路的情況。這種防止死鎖的策略較之前兩種策略，不論是資源利用率還是系統(tǒng)吞吐量，都有顯著的改善。問題：1）為系統(tǒng)中各種資源類型分配的序號．必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加；2）盡管在為資源類型分配序號時(shí)，已考慮到大多數(shù)作