操作系統(tǒng)課件：調(diào)度與死鎖

調(diào)度與死鎖一個作業(yè)從提交到完成通常要經(jīng)歷多級調(diào)度4.1調(diào)度的層次在不同操作系統(tǒng)中所采用的調(diào)度層次不完全相同。有的系統(tǒng)中僅采用一級調(diào)度，而在另一些系統(tǒng)中則可能采用兩級或三級調(diào)度。

處理機的三級調(diào)度處理機的三級調(diào)度：作業(yè)調(diào)度進程調(diào)度交換調(diào)度

調(diào)度的層次運行就緒阻塞進程調(diào)度掛起阻塞掛起就緒中級調(diào)度創(chuàng)建退出作業(yè)調(diào)度4.1.1作業(yè)調(diào)度Jobscheduler作業(yè)調(diào)度又稱高級調(diào)度、宏觀調(diào)度或長程調(diào)度(Long-termscheduler)，其主要任務(wù)是按一定的原則從外存上處于后備狀態(tài)的作業(yè)中選擇一個或多個作業(yè)，給它們分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進程，以使該作業(yè)具有獲得競爭處理機的權(quán)利。作業(yè)調(diào)度的運行頻率較低，通常為幾分鐘一次。4.1.2進程調(diào)度Processscheduler進程調(diào)度又稱低級調(diào)度、微觀調(diào)度或短程調(diào)度(Short-termscheduler)，其主要任務(wù)是按照某種策略和方法從就緒隊列中選取一個進程，將處理機分配給它。進程調(diào)度的運行頻率很高，一般幾十毫秒要運行一次。

4.1.3中級調(diào)度中級調(diào)度又稱中程調(diào)度(Mediumtermscheduling)或交換調(diào)度，其功能是將內(nèi)存中暫時不用的信息移到外存，以騰出空間給內(nèi)存中的進程使用，或?qū)⑿枰男畔耐獯孀x入內(nèi)存。引入中程調(diào)度的目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。中級調(diào)度的運行頻率介于兩者之間。4.1.4調(diào)度性能評價由于操作系統(tǒng)的類型及目標(biāo)不同，因此選擇的調(diào)度策略及算法也不同。調(diào)度性能的評價準(zhǔn)則有很多評價準(zhǔn)則，下面介紹幾種主要的評價準(zhǔn)則：CPU利用率(CPUutilization)高系統(tǒng)吞吐量大。系統(tǒng)吞吐量(throughput)表示單位時間內(nèi)CPU完成作業(yè)的數(shù)量。周轉(zhuǎn)時間(turnaroundtime)短。響應(yīng)時間快。響應(yīng)時間(responsetime)是指從用戶提交請求到系統(tǒng)首次產(chǎn)生響應(yīng)所用的時間。周轉(zhuǎn)時間Turnaroundtime作業(yè)的周轉(zhuǎn)時間是指從作業(yè)提交到作業(yè)完成之間的時間間隔。平均周轉(zhuǎn)時間是指多個作業(yè)的周轉(zhuǎn)時間的平均值。ｎ個作業(yè)的平均周轉(zhuǎn)時間：T=（T1＋T2＋

…

＋Tn）／n（Ti為作業(yè)ｉ的周轉(zhuǎn)時間）帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間是指作業(yè)周轉(zhuǎn)時間與作業(yè)實際運行時間的比。平均帶權(quán)周轉(zhuǎn)時間是指多個作業(yè)的帶權(quán)周轉(zhuǎn)時間的平均值。ｎ個作業(yè)的平均帶權(quán)周轉(zhuǎn)時間：W＝（W1＋W2＋

…

＋Wn）/n（Wi為作業(yè)ｉ的帶權(quán)周轉(zhuǎn)時間）周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間例各作業(yè)感受如何?

12.91帶權(quán)周轉(zhuǎn)時間

6

30

1.5等待時間

1.2

3

3周轉(zhuǎn)時間10.2

11.2

11完成時間0.2

0.12運行時間

9

8.2

8提交時間

C

B

A作業(yè)4.2作業(yè)調(diào)度作業(yè)是用戶在一次解題或一個事務(wù)處理過程中要求計算機系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等。計算機系統(tǒng)在完成一個作業(yè)的過程中所做的一項相對獨立的工作稱為一個作業(yè)步。例如，在編制程序過程中通常要進行編輯輸入、編譯、鏈接、運行幾個作業(yè)步。

4.2.1作業(yè)的狀態(tài)及轉(zhuǎn)換作業(yè)從提交到完成要經(jīng)歷四種狀態(tài)：提交狀態(tài)：用戶作業(yè)由輸入設(shè)備向系統(tǒng)外存輸入時作業(yè)所處的狀態(tài)。后備狀態(tài)：作業(yè)輸入到外存后，系統(tǒng)為其建立了作業(yè)控制塊，并把它插入到后備作業(yè)隊列中等待調(diào)度運行。運行狀態(tài)：作業(yè)在內(nèi)存中執(zhí)行。完成狀態(tài)：作業(yè)正?；虍惓＝Y(jié)束，但作業(yè)占有的資源還未被系統(tǒng)全部回收。收容作業(yè)狀態(tài)轉(zhuǎn)換圖阻塞就緒執(zhí)行I/O請求I/O完成時間片完提交作業(yè)錄入后備作業(yè)調(diào)度進程調(diào)度運行狀態(tài)完成作業(yè)調(diào)度4.2.2作業(yè)調(diào)度作業(yè)調(diào)度程序主要完成以下工作記錄進入系統(tǒng)的各個作業(yè)情況。從后備作業(yè)中挑選一些作業(yè)投入執(zhí)行。為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。在作業(yè)運行結(jié)束或運行過程中因某種原因需要撤離時，作業(yè)調(diào)度程序還要完成作業(yè)的善后處理工作。作業(yè)控制塊為管理作業(yè)，系統(tǒng)設(shè)置了作業(yè)控制塊。系統(tǒng)通過JCB感知作業(yè)的存在，JCB是作業(yè)存在的唯一標(biāo)志。通常作業(yè)控制塊中包括的主要內(nèi)容有：資源要求。資源使用情況。作業(yè)的控制方式、類型和優(yōu)先級等。作業(yè)名、作業(yè)狀態(tài)。資源要求資源要求是指作業(yè)運行需要的資源情況，包括：估計運行時間、最遲完成時間、需要的內(nèi)存容量、外設(shè)類型及數(shù)量等。資源使用情況資源使用情況包括作業(yè)進入系統(tǒng)的時間、開始運行時間、已運行時間、內(nèi)存地址、外設(shè)臺號等。作業(yè)控制方式、類型和優(yōu)先級作業(yè)的控制方式有聯(lián)機作業(yè)控制和脫機作業(yè)控制。從不同角度出發(fā)可以對作業(yè)進行不同的分類，如終端型和批量型，作業(yè)的優(yōu)先級是指作業(yè)進入系統(tǒng)運行的優(yōu)先級別，優(yōu)先級高的作業(yè)可以優(yōu)先進入系統(tǒng)運行。作業(yè)名、作業(yè)狀態(tài)記錄作業(yè)的標(biāo)識信息及作業(yè)的當(dāng)前狀態(tài)。4.3進程調(diào)度-4.3.1進程調(diào)度的功能進程調(diào)度程序主要完成以下功能：記錄系統(tǒng)中所有進程的狀態(tài)、優(yōu)先數(shù)和資源情況。選擇獲得處理機的進程。實施處理機的分配及回收。引起進程調(diào)度的原因正在運行進程結(jié)束運行進程因某種原因阻塞，如P操作、I/O等從系統(tǒng)調(diào)用或中斷返回時，有進程進入就緒隊列且就緒隊列為空，或進程優(yōu)先級高于當(dāng)前運行進程且為剝奪調(diào)度方式時間片用完4.3.2進程調(diào)度的方式進程調(diào)度有兩種方式：搶占(Preemptive)方式非搶占(Nonpreemptive)方式搶占方式搶占方式：又稱剝奪方式、可剝奪方式。這種調(diào)度方式是指允許調(diào)度程序根據(jù)某種原則去停止正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給其他進程。搶占原則有：優(yōu)先權(quán)、時間片。

非搶占方式非搶占方式：又稱非剝奪方式、不可剝奪方式、不可搶占方式。這種調(diào)度方式是指一旦將處理機分配給某進程后，便讓該進程一直執(zhí)行，直到該進程完成或發(fā)生某事件而進入阻塞狀態(tài)，才把處理機分配給其他進程。非搶占方式中引起進程調(diào)度的因素有：進程結(jié)束、因某種原因而阻塞、執(zhí)行同步原語等。特點：簡單，系統(tǒng)開銷小，但無法處理緊急任務(wù)。4.4調(diào)度算法調(diào)度算法(SchedulingAlgorithms)是指根據(jù)系統(tǒng)資源分配策略所規(guī)定的資源分配算法。本章的算法有些適合作業(yè)調(diào)度，有些適合進程調(diào)度，有些適用于兩者。4.4.1先來先服務(wù)調(diào)度算法先來先服務(wù)算法(First-come,first-served)既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。在作業(yè)調(diào)度中：從后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源，創(chuàng)建進程，然后放入就緒隊列。進程調(diào)度中：從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或因等待某一事件而阻塞時才釋放處理機。設(shè)有4道作業(yè)，它們的提交時間及執(zhí)行時間如下表，若按先來先服務(wù)調(diào)度算法進行調(diào)度，試計算4個作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。（時間單位：小時，以十進制計算）。先來先服務(wù)調(diào)度算法例

作業(yè)提交時間估計運行時間1102210.21310.40.5410.50.3作業(yè)周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間的計算平均周轉(zhuǎn)時間T=(2.0＋2.8＋3.1＋3.3)/4=2.8平均帶權(quán)周轉(zhuǎn)時間W=(1＋2.8＋6.2＋11)/4=5.25116.22.81帶權(quán)周轉(zhuǎn)時間3.33.12.82周轉(zhuǎn)時間13.813.51312完成時間13.5131210開始時間0.30.512運行時間10.510.410.210提交時間4321作業(yè)先來先服務(wù)算法特點算法簡單，易于實現(xiàn)，但不利于短作業(yè)及I/O繁忙型作業(yè)。4.4.2短作業(yè)優(yōu)先調(diào)度算法在作業(yè)調(diào)度中，從后備隊列中選擇一個或多個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。在進程調(diào)度中，從就緒隊列中選擇一個估計運行時間最短的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或因等待某一事件而阻塞時才釋放處理機。Shortest-job-first短作業(yè)優(yōu)先調(diào)度算法例平均周轉(zhuǎn)時間T=(2.0＋1.8＋2.4＋3.6)/4=2.45平均帶權(quán)周轉(zhuǎn)時間W=(1＋6＋4.8＋3.6)/4=3.8564.83.61帶權(quán)周轉(zhuǎn)時間1.82.43.62周轉(zhuǎn)時間12.312.813.812完成時間1212.312.810開始時間0.30.512運行時間10.510.410.210提交時間4321作業(yè)短作業(yè)優(yōu)先調(diào)度算法的特點算法調(diào)度性能較好，如上例中，先來先服務(wù)短作業(yè)優(yōu)先平均周轉(zhuǎn)時間2.82.45平均帶權(quán)周轉(zhuǎn)時間5.25

3.85但對長作業(yè)不利，未考慮作業(yè)的緊迫程度，運行時間為估計。最短剩余時間優(yōu)先調(diào)度算法最短進程優(yōu)先調(diào)度算法可以是非搶占式的，也可以是搶占式的。若無特別說明，通常是指非搶占式的算法。搶占式的最短進程優(yōu)先調(diào)度算法也稱為最短剩余時間優(yōu)先調(diào)度算法(shortest-remaining-time-first)，即當(dāng)一個新進程進入就緒隊列時，若其需要的運行時間比當(dāng)前運行進程的剩余時間短，則它將搶占CPU。最短剩余時間優(yōu)先算法例時間：1.42.6712.125帶權(quán)周轉(zhuǎn)時間724417周轉(zhuǎn)時間1026517完成時間51710開始時間5948運行時間3210提交時間

D

C

B

A作業(yè)0A12B34510DA1726C最短剩余時間優(yōu)先算法例（續(xù)）平均周轉(zhuǎn)時間T=(17＋4＋24＋7)/4=13平均帶權(quán)周轉(zhuǎn)時間W=(2.125＋1＋2.67＋1.4)/4=1.81.42.6712.125帶權(quán)周轉(zhuǎn)時間724417周轉(zhuǎn)時間1026517完成時間51710開始時間5948運行時間3210提交時間

D

C

B

A作業(yè)最短平均周轉(zhuǎn)時間當(dāng)一批作業(yè)同時到達時，最短作業(yè)優(yōu)先調(diào)度算法才能獲得最短平均周轉(zhuǎn)時間。設(shè)一組作業(yè)p1、p2、…、pn，其運行時間為t1、t2、…、tn，且假定t1<t2<…<tn，則短作業(yè)優(yōu)先調(diào)度算法的總周轉(zhuǎn)時間為：t1+（t1+t2）+…+（t1+…+tn）=n*t1+（n-1）t2+…+tn最短平均周轉(zhuǎn)時間（續(xù)）可以證明：若a1≤a2≤…≤an且b1≤b2≤…≤bn，則a1bn+a2bn-1+…+anb1≤a1bi1+a2bi2+…+anbin

≤a1b1+a2b2+…+anbn

其中i1、i2、…、in是1、2、…、n的一個排列。4.4.3優(yōu)先級調(diào)度算法在作業(yè)調(diào)度中，從后備作業(yè)隊列中選擇若干優(yōu)先級高的作業(yè)調(diào)入內(nèi)存。在進程調(diào)度中，將處理機分配給就緒隊列中優(yōu)先級最高的進程。優(yōu)先級(Priority)表示進程的重要性及運行優(yōu)先性，通常用優(yōu)先數(shù)來衡量。在某些系統(tǒng)中，優(yōu)先數(shù)越大優(yōu)先級越高；而在另一些系統(tǒng)中，優(yōu)先數(shù)越大優(yōu)先級越小。按調(diào)度方式對優(yōu)先級調(diào)度算法分類非搶占式優(yōu)先級調(diào)度算法：系統(tǒng)一旦將處理機分配給就緒隊列中優(yōu)先級最高的進程后，該進程便一直運行下去，直到完成或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)才將處理機分配給另一個更高優(yōu)先級的進程。搶占式優(yōu)先級調(diào)度算法：將處理機分配給優(yōu)先級最高的進程，使之運行。在進程運行過程中，一旦出現(xiàn)了另一個優(yōu)先級更高的進程時，進程調(diào)度程序就停止原運行進程，而將處理機分配給新出現(xiàn)的高優(yōu)先級進程。

優(yōu)先級的類型優(yōu)先級分為兩種：靜態(tài)優(yōu)先級動態(tài)優(yōu)先級靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，確定之后在整個進程運行期間不再改變。確定依據(jù)有：進程類型：系統(tǒng)，用戶進程對資源的需求：執(zhí)行時間，資源數(shù)量用戶要求：緊迫程度特點：簡單易行，系統(tǒng)開銷小，但不精確。動態(tài)優(yōu)先級動態(tài)優(yōu)先級是指在創(chuàng)建進程時，根據(jù)進程的特點及相關(guān)情況確定一個優(yōu)先級，在進程運行過程中再根據(jù)情況的變化調(diào)整優(yōu)先級。確定原則有：占用CPU時間，等待時間。例：優(yōu)先數(shù)=CPU使用時間/2+基本優(yōu)先數(shù)CPU使用時間衰減函數(shù):Decay(CPU使用時間)=CPU使用時間/24.4.4時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)法(RoundRobin)：系統(tǒng)將所有就緒進程按到達時間的先后次序排成一個隊列，每次調(diào)度時把CPU分配給隊首進程，并令其執(zhí)行一個時間片。當(dāng)時間片用完時，停止該進程的執(zhí)行，將它送至就緒隊列末尾等待下一次執(zhí)行，然后再把處理機分配給就緒隊列中的新隊首進程。如此不斷循環(huán)，直至完成為止。時間片輪轉(zhuǎn)算法例設(shè)有A、B、C、D、E五個進程，其到達時間分別為0、1、2、3、4，要求運行時間依次為3、6、4、5、2，采用時間片輪轉(zhuǎn)調(diào)度算法，當(dāng)時間片大小為1和4時，試計算其平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。時間片大小為1A、B、C、D、E要求運行時間依次為3、6、4、5、2，到達時間依次為0、1、2、3、4。

1：B運行，A等待；2：A運行，CB等待；3：C運行，BDA等待；4：B運行，DAEC等待；5：D運行，AECB等待；6：A運行，ECBD等待；7：E運行，CBD等待；8：C運行，BDE等待；9：B運行，DEC等待；10：D運行，ECB等待；11：E運行，CBD等待；12：C運行，BD等待；13：B運行，DC等待；14：D運行，CB等待；15：C運行，BD等待；16：B運行，D等待；17：D運行，B等待；18：B運行，D等待；19：D運行，0：A運行；時間片為1的周轉(zhuǎn)時間平均周轉(zhuǎn)時間T=(7＋18＋14＋17+8)/5=12.8平均帶權(quán)周轉(zhuǎn)時間W=(2.33＋3＋3.5＋3.4+4)/5=3.2463.43.532.33帶權(quán)周轉(zhuǎn)時間1714187周轉(zhuǎn)時間2016197完成時間5310開始時間5463運行時間3210提交時間

D

C

B

A作業(yè)4812724

E時間片大小為4A、B、C、D、E要求運行時間依次為3、6、4、5、2，到達時間依次為0、1、2、3、4。0：A運行，BCD依次到達；3：B運行，CD等待，后E到達；7：C運行，DEB等待；11：D運行，EB等待；15：E運行，BD等待；17：B運行，D等待；19：D運行A、B、C、D、E開始時間依次為0、3、7、11、15；結(jié)束時間依次為3、19、11、20、17。時間片為4的周轉(zhuǎn)時間平均周轉(zhuǎn)時間T=(3＋18＋9＋17+13)/5=12平均帶權(quán)周轉(zhuǎn)時間W=(1＋3＋2.25＋3.4+6.5)/5=3.233.42.2531帶權(quán)周轉(zhuǎn)時間179183周轉(zhuǎn)時間2011193完成時間11730開始時間5463運行時間3210提交時間

D

C

B

A作業(yè)6.513171524

E時間片大小的選擇若時間片太大，所有進程都能在一個時間片內(nèi)完成，則時間片輪轉(zhuǎn)算法退化為先來先服務(wù)；若時間片太小，則進程調(diào)度頻繁，系統(tǒng)開銷增加。因此時間片大小選擇應(yīng)適當(dāng)。現(xiàn)代操作系統(tǒng)的時間片一般為10-100ms，上下文切換時間一般少于10us。確定時間片大小應(yīng)考慮的因素系統(tǒng)對響應(yīng)時間的要求：響應(yīng)時間=時間片*進程數(shù)。進程數(shù)一定，則時間片與系統(tǒng)響應(yīng)時間成正比。就緒隊列中的進程數(shù)目：若響應(yīng)時間固定，則時間片與就緒進程數(shù)成反比。系統(tǒng)處理能力：系統(tǒng)速度快，則時間片可以更短。時間片輪轉(zhuǎn)算法的特點及改進對偏重I/O的進程不公平。為此改進為虛擬時間片輪轉(zhuǎn)算法。虛擬時間片輪轉(zhuǎn)算法：新進程基于FCFS進入就緒隊列，進程用完時間片后也進入就緒隊列，進程因I/O阻塞進入I/O隊列，I/O完成時進程進入附加隊列，附加隊列的優(yōu)先級高于就緒隊列，當(dāng)進程從附加隊列被調(diào)度時，其運行時間不超過上次發(fā)生中斷時剩余的時間。虛擬時間片輪轉(zhuǎn)調(diào)度示意圖CPU新進程就緒隊列調(diào)度超時優(yōu)先級高附加隊列I/O隊列請求I/OI/O完成4.4.5高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法是對短作業(yè)優(yōu)先調(diào)度算法和先來先服務(wù)調(diào)度算法的一種綜合。響應(yīng)比響應(yīng)比定義如下：響應(yīng)比＝作業(yè)響應(yīng)時間/估計運行時間由于響應(yīng)時間為作業(yè)進入系統(tǒng)后的等待時間加上估計運行時間。因此響應(yīng)比＝1＋作業(yè)等待時間/估計運行時間高響應(yīng)比優(yōu)先調(diào)度算法思想在每次調(diào)度作業(yè)運行時，先計算后備作業(yè)隊列中每個作業(yè)的響應(yīng)比，然后挑選響應(yīng)比最高者投入運行。特點：有利于短作業(yè)-----等待時間相同，短作業(yè)優(yōu)先，考慮等待時間----運行時間相同，等待時間長的作業(yè)優(yōu)先運行。最高響應(yīng)比優(yōu)先算法例設(shè)有A、B、C、D、E五個進程，其到達時間分別為0、1、2、3、4，要求運行時間依次為3、6、4、5、2，采用最高響應(yīng)比優(yōu)先調(diào)度算法，試計算其平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。分析作業(yè)的調(diào)度順序A、B、C、D、E的到達時間依次為0、1、2、3、4，要求運行時間依次為3、6、4、5、20：A運行，BCD依次到達；3：rB=1+2/6，

rC=1+1/4，

rD=1；B先運行。9：rC=1+7/4，

rD=1+6/5，

rE=1+5/2；E先運行。11：rC=1+9/4，

rD=1+8/5；C先運行。由此可知作業(yè)的運行順序為A、B、E、C、D。周轉(zhuǎn)時間的計算順序A、B、E、C、D平均周轉(zhuǎn)時間T=(3＋8＋13＋17+7)/5=9.6平均帶權(quán)周轉(zhuǎn)時間W=(1＋1.33＋3.25＋3.4+3.5)/5=2.4963.43.251.331帶權(quán)周轉(zhuǎn)時間171383周轉(zhuǎn)時間201593完成時間151130開始時間5463運行時間3210提交時間

D

C

B

A作業(yè)3.5711924

E4.4.6多級隊列調(diào)度算法MultilevelQueueScheduling實現(xiàn)思想：根據(jù)作業(yè)性質(zhì)或類型不同，將進程就緒隊列分為多個，每個隊列采用不同的調(diào)度算法。例如：終端型作業(yè)為前臺作業(yè)，批處理作業(yè)為后臺作業(yè)。前臺采用時間片輪轉(zhuǎn)算法，后臺采用先來先服務(wù)，前臺作業(yè)的優(yōu)先級高。4.4.7多級反饋隊列調(diào)度算法MultilevelFeedbackQueueScheduling應(yīng)設(shè)置多個就緒隊列，并為每個隊列賦予不同的優(yōu)先級。第1個隊列的優(yōu)先級最高，第2隊列次之，其余隊列的優(yōu)先級逐次降低。每個隊列中進程執(zhí)行的時間片大小也各不相同，進程所在隊列的優(yōu)先級越高，其相應(yīng)的時間片就越短。多級反饋隊列調(diào)度算法（2）當(dāng)一個新進程進入系統(tǒng)時，首先將它放入第1個隊列的末尾，按先來先服務(wù)的原則排隊等待調(diào)度。當(dāng)輪到該進程執(zhí)行時，如能在此時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第2隊列的末尾，再同樣地按先來先服務(wù)原則等待調(diào)度執(zhí)行。如此下去，最后一個隊列中使用時間片輪轉(zhuǎn)調(diào)度算法。多級反饋隊列調(diào)度算法（3）僅當(dāng)?shù)?個隊列為空時，調(diào)度程序才調(diào)度第2隊列中的進程運行；僅當(dāng)?shù)?個至第（i－1）個隊列均為空時，才會調(diào)度第i個隊列中的進程運行。當(dāng)處理機正在為第i個隊列中的某進程服務(wù)時，若又有新進程進入優(yōu)先級較高的隊列中，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在執(zhí)行進程放回第i個隊列末尾，重新將處理機分配給新進程。多級反饋隊列調(diào)度算法示意圖就緒隊列1CPU就緒隊列2就緒隊列nCPUCPU完成完成完成多級反饋隊列調(diào)度算法例設(shè)有A、B、C、D、E五個進程，其到達時間分別為0、1、3、4、5，要求運行時間依次為3、8、4、5、7，采用多級反饋隊列調(diào)度算法，系統(tǒng)中共有3個隊列，其時間片依次為1、2和4，試計算其平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。13：EE運行，BCD等待；調(diào)度分析A、B、C、D、E到達時間依次為0、1、3、4、5，要求運行時間依次為3、8、4、5、71：B運行，A等待；2：A運行，B等待；3：C運行，BA等待；4：D運行，BAC等待；5：E運行，BACD等待；6：BB運行，ACDE等待；8：A運行，CDE等待；B等待9：CC運行，DE等待；B等待11：DD運行，E等待；BC等待15：BBBB運行，CDE等待；19：C運行，DEB等待；20：DD運行，EB等待；22：EEEE運行，B等待；0：A運行；26：B運行。周轉(zhuǎn)時間的計算平均周轉(zhuǎn)時間T=(9＋26＋17＋18+21)/5=18.25平均帶權(quán)周轉(zhuǎn)時間W=(3＋3.25＋4.25＋3.6+3)/5=3.423.64.253.253帶權(quán)周轉(zhuǎn)時間1817269周轉(zhuǎn)時間2220279完成時間4310開始時間5483運行時間4310提交時間

D

C

B

A作業(yè)32126575

E多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法能較好滿足各類用戶的需求：終端型用戶：大多能在一個時間片內(nèi)完成，響應(yīng)時間較短；短批處理作業(yè)用戶：能在前幾個隊列完成，周轉(zhuǎn)時間較短；長批處理作業(yè)用戶：依次在1～n隊列中運行，不會長時間得不到處理。4.5死鎖Deadlocks

多道程序的并發(fā)執(zhí)行可以改善系統(tǒng)的資源利用率，但也可能導(dǎo)致死鎖的發(fā)生。4.5.1死鎖的概念死鎖是指多個進程因競爭系統(tǒng)資源或相互通信而造成的一種僵局，若無外力作用，這些進程都將永遠(yuǎn)不能向前推進。死鎖例：當(dāng)兩輛車在十字路口逼近時，它們要完全停下來，且在一輛車開走之前，另一輛車不能啟動。日常生活中的死鎖例假設(shè)一條河上有一座獨木橋，若橋兩端的人相向而行……此時死鎖發(fā)生了

4.5.2死鎖產(chǎn)生的原因和必要條件死鎖產(chǎn)生的原因是與資源的使用相關(guān)。下面介紹資源分類?？蓜儕Z和非剝奪資源可剝奪資源是指某進程獲得這類資源后，該資源可以被其他進程或系統(tǒng)剝奪。如CPU，存儲器。非剝奪資源又稱不可剝奪資源，是指系統(tǒng)將這類資源分配給進程后，再不能強行收回，只能在進程使用完后主動釋放。如打印機、讀卡機。注意：競爭可剝奪資源不會產(chǎn)生死鎖！永久性資源和消耗性資源永久性資源：可順序重復(fù)使用的資源。如打印機。消耗性資源：由一個進程產(chǎn)生，被另一個進程使用短暫時間后便無用的資源，又稱為臨時性資源。如消息。競爭永久性資源和臨時性資源都可能產(chǎn)生死鎖。死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因是：競爭資源：多個進程競爭資源，而資源又不能同時滿足其需求。進程推進順序不當(dāng)：進程申請資源和釋放資源的順序不當(dāng)。競爭非剝奪資源引起的死鎖競爭非剝奪資源例。如，打印機R1和讀卡機R2供進程P1和P2共享。P1R1R2P2競爭消耗性資源引起的死鎖如消息通信按下述順序進行，則不會發(fā)生死鎖：P1：...Release(S1)；Request(S2)；...P2：...Release(S2)；Request(S1)；...若按下述順序，則可能發(fā)生死鎖：P1：...Request(S2)；Release(S1)；...P2：...Request(S1)；Release(S2)；...P1S2S1P2進程推進順序不當(dāng)引起的死鎖當(dāng)進程P1、P2共享資源A、B時，若推進順序合法則不會產(chǎn)生死鎖，否則會產(chǎn)生死鎖。合法的推進路線：①②③不合法的推進線路：④P2釋放AP2釋放BP2申請AP2申請BP1申請AP1申請BP1釋放AP1釋放B①②③④死鎖區(qū)死鎖點死鎖產(chǎn)生的必要條件互斥條件：在一段時間內(nèi)某資源僅為一個進程所占有。請求和保持條件：又稱部分分配條件、占用并等待條件。當(dāng)進程因請求資源被阻塞時，已分配資源保持不放。不剝奪條件：進程所獲得的資源在未使用完畢之前，不能被其他進程強行奪走。循環(huán)等待條件：死鎖發(fā)生時，存在一個進程資源的循環(huán)。注意死鎖是因資源競爭造成的僵局通常死鎖一般至少涉及兩個進程死鎖與部分進程及資源相關(guān)4.5.3處理死鎖的基本方法用于處理死鎖的方法主要有：忽略死鎖。這種處理方式又稱鴕鳥算法，指像鴕鳥一樣對死鎖視而不見。

預(yù)防死鎖：設(shè)置某些限制條件，通過破壞死鎖產(chǎn)生的四個必要條件之一來預(yù)防死鎖。避免死鎖：在資源的動態(tài)分配過程中，用某種方法來防止系統(tǒng)進入不安全狀態(tài)。檢測死鎖及解除：系統(tǒng)定期檢測是否出現(xiàn)死鎖，若出現(xiàn)則解除死鎖。4.5.4死鎖的預(yù)防預(yù)防死鎖。通過破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來防止發(fā)生死鎖。特點：較易實現(xiàn)，廣泛使用，但限制較嚴(yán)，資源利用率低。破壞互斥條件互斥是設(shè)備本身固有的屬性，此條件不能破壞。破壞請求和保持條件要求進程一次申請它所需的全部資源，若有足夠的資源則分配給進程，否則不分配資源，進程等待。這種方法稱為靜態(tài)資源分配法。特點：簡單、安全且易于實現(xiàn)；但資源利用率低，進程延遲運行。破壞不剝奪條件一個已獲得某些資源的進程，若新的資源請求得不到滿足，則它必須釋放已獲得的所有資源。特點：實現(xiàn)較復(fù)雜，釋放已獲得資源可能造成前一段工作的失效，重復(fù)申請和釋放資源會增加系統(tǒng)開銷，降低系統(tǒng)吞吐量。

破壞循環(huán)等待條件將所有資源按類型排隊，并賦予不同序號，要求進程均嚴(yán)格按照序號遞增的次序請求資源，同類資源一次申請完。這種方法稱為有序資源分配法。特點：比前兩種方法資源利用率高，吞吐量大。但要求資源序號相對穩(wěn)定，從而限制了新設(shè)備的增加；使用資源的順序與系統(tǒng)規(guī)定順序不同，造成資源的浪費；使用資源的次序限制用戶編程。為什么有序資源分配法可以防止死鎖1假設(shè)循環(huán)已經(jīng)出現(xiàn)并且含于環(huán)中的進程是p0、…、pn，這意味著pi正占有ri類資源，而請求ri+1類資源，設(shè)函數(shù)f能獲得資源序號，則有f（ri）<f（ri+1），故f（r0）<f（r1）<…<f（rn）<f（r0）。矛盾，原假設(shè)不成立。r1pnp0p1r0…rnr2為什么有序資源分配法可以防止死鎖2采用有序資源分配法，系統(tǒng)中的進程必須按照資源編號的升序申請資源。因此在任一時刻，系統(tǒng)中總會存在一個進程，它占有已申請資源中編號最高的資源，且它繼續(xù)請求的資源必定是空閑的，因而它可以一直向前推進直至完成。當(dāng)該進程運行完成后，即會釋放它所占有的全部資源。這樣剩余進程集合中又會存在一個進程，它占有已申請資源中編號最高的資源，且它繼續(xù)請求的資源必定是空閑的，因而它也可以一直向前推進直至完成。以此類推，最終所有進程均可運行完成，故不會發(fā)生死鎖。4.5.5死鎖的避免死鎖的避免是在資源的動態(tài)分配過程中，用某種方法防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖的發(fā)生。特點：以較弱的限制獲得較高的利用率，但實現(xiàn)有一定難度。安全狀態(tài)在避免死鎖的方法中，允許進程動態(tài)地申請資源，系統(tǒng)在進行資源分配之前，先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，便將資源分配給進程，否則進程等待。安全狀態(tài)是指系統(tǒng)能按某種順序如<P1、P2…、Pn>來為每個進程分配其所需的資源，直至最大需求，使每個進程都可以順利完成，則稱此時的系統(tǒng)狀態(tài)為安全狀態(tài)，稱序列<

P1、P2、…、Pn>為安全序列。不安全狀態(tài)若某一時刻系統(tǒng)中不存在一個安全序列，則稱此時的系統(tǒng)狀態(tài)為不安全狀態(tài)。進入不安全狀態(tài)后，便可能進而進入死鎖狀態(tài)；因此避免死鎖的本質(zhì)是使系統(tǒng)不進入不安全狀態(tài)。安全狀態(tài)例T0時刻，系統(tǒng)資源狀態(tài)如下：進程最大需求已分配需要可用

P110553

P2422P3927這時可用資源能滿足P2的需要，P2獲得運行需要的所有資源并能順利運行結(jié)束。P2運行結(jié)束的系統(tǒng)資源狀態(tài)這時可用資源能滿足P1的需要，P1獲得運行需要的所有資源并能順利運行結(jié)束。進程最大需求已分配需要可用

P110555

P2422P3927P2、P1運行結(jié)束的統(tǒng)資源狀態(tài)這時可用資源能滿足P3的需要，P3獲得運行需要的所有資源并能順利運行結(jié)束。因此存在一個安全序列<P2、P1、P3>，系統(tǒng)狀態(tài)安全。進程最大需求已分配需要可用

P1105510

P2422P3927由安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換若在T0之后，又將1個資源分配給了P3，則系統(tǒng)進入了不安全狀態(tài)：進程最大需求已分配需要可用

P110552

P2422P3936銀行家算法Banker’sAlgorithm最具代表性的死鎖避免算法是Dijkstra的銀行家算法。銀行家算法要求新進程進入系統(tǒng)時，必須說明其可能需要的每類資源最大數(shù)量

假定系統(tǒng)中有n個進程P1、P2、…、Pn

，m類資源R1、R2、…、Rm，銀行家算法中使用的數(shù)據(jù)結(jié)構(gòu)如下：1）可用資源向量Available可利用資源向量Available是一個含有m個元素的數(shù)組，其中每一個元素代表一類資源的空閑資源數(shù)目。如果Available(j)＝k，表示系統(tǒng)中現(xiàn)有空閑的Rj類資源k個。2）最大需求矩陣Max最大需求矩陣Max是一個n×m的矩陣，定義了系統(tǒng)中每個進程對m類資源的最大需求數(shù)目。如果Max(i，j)＝k，表示進程Pi需要Rj類資源的最大數(shù)目為k。3）分配矩陣Allocation分配矩陣Allocation是一個n×m的矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一個進程的資源數(shù)目。如果Allocation(i，j)＝k，表示進程Pi當(dāng)前已分到Rj類資源的數(shù)目為k。Allocationi表示進程Pi的分配向量，由矩陣Allocation的第i行構(gòu)成。4）需求矩陣Need需求矩陣Need是一個n×m的矩陣，它定義了系統(tǒng)中每一個進程還需要的各類資源數(shù)目。如果Need(i，j)＝k，表示進程Pi還需要Rj類資源k個。Needi表示進程Pi的需求向量，由矩陣Need的第i行構(gòu)成。三個矩陣間的關(guān)系：Need(i，j)＝Max(i，j)－Allocation(i，j)銀行家算法設(shè)Requesti是進程Pi的請求向量，Requesti(j)＝k表示進程Pi請求分配Rj類資源k個。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：銀行家算法描述1）如果Requesti≤Needi

，則轉(zhuǎn)向步驟2；否則出錯。2）如果Requesti≤Available，則轉(zhuǎn)向步驟3；否則Pi等待。3）試分配并修改數(shù)據(jù)結(jié)構(gòu)：

Available＝Available－Requesti

；Allocationi＝Allocationi＋Requesti；Needi＝Needi－Requesti；4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配是否安全。若安全，才正式分配；否則，試分配作廢，讓進程Pi等待。安全性算法(1)SafetyAlgorithm1）設(shè)置兩個向量Work：表示系統(tǒng)可提供給進程繼續(xù)運行的各類空閑資源數(shù)目，含有m個元素，執(zhí)行安全性算法開始時，Work＝Available。

Finish：表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成，開始時，F(xiàn)inish(i)＝false；當(dāng)有足夠資源分配給進程Pi時，令Finish(i)＝true。2）從進程集合中找到一個能滿足下述條件的進程：Finish(i)=false；Needi≤Work；如找到則執(zhí)行步驟3；否則執(zhí)行步驟4。安全性算法(2)3）當(dāng)進程Pi獲得資源后，可順利執(zhí)行直到完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work＝Work＋Allocationi；Finish(i)＝true；Gotostep2；4）若所有進程的Finish(i)都為true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。銀行家算法例假定系統(tǒng)中有5個進程P0、P1、P2、P3、P4和三種類型的資源A、B、C，數(shù)量分別為12、5、9，在T0時刻的資源分配情況如下所示。資源情況進程

MaxAllocation

Need

Available

ABC

ABC

ABC

ABCP0853110743332

P1323201122

P2903303600

P3222211011

P4533102431T0時刻的安全性利用安全性算法對T0時刻的資源分配情況進行分析，可得如下所示的T0時刻的安全性分析。

T0時刻的安全性檢查Need0：7,4,3Need1：1,2,2Need2：6,0,0Need3：0,1,1Need4：4,3,1Alloc0：1,1,0Alloc1：2,0,1Alloc2：3,0,3Alloc3：2,1,1Alloc4：1,0,2Avail332

true

true

true

truetrueFinish533201122332P112591107431149

P01149303600846

P2846102431744

P4

ABC

ABCABCABC744211011533

P3Work+Alloc

AllocNeed

Work資源情況進程T0時刻是安全的從上述分析得知，T0時刻存在著一個安全序列<P1、P3、P4、P2、P0>，故系統(tǒng)是安全的。P1請求資源P1發(fā)出請求向量Request1

(1，0，2)，系統(tǒng)按銀行家算法進行檢查：1）Request1(1，0，2)≤Need1(1，2，2)2）Request1(1，0，2)≤Available(3，3，2)3）系統(tǒng)先假定可為P1分配資源，并修改Available、Allocation1、Need1向量，由此形成的資源變化情況如下所示。

為P1試分配資源后4）再利用安全性算法檢查此時系統(tǒng)是否安全，可得如下所示的安全性分析。資源情況進程

MaxAllocation

Need

Available

ABC

ABC

ABC

ABCP0853110743

230

P1323

303

020

P2903303600

P3222211011

P4533102431P1申請資源后的安全性檢查Need0：7,4,3Need1：0,2,0Need2：6,0,0Need3：0,1,1Need4：4,3,1Alloc0：1,1,0Alloc1：3,0,3Alloc2：3,0,3Alloc3：2,1,1Alloc4：1,0,2Avail230

true

true

true

truetrueFinish533

303020

230P112591107431149

P01149303600846

P2846102431744

P4

ABC

ABCABCABC744211011533

P3Work+Alloc

AllocNeed

Work資源情況進程可以為P1分配資源從上述分析得知，可以找到安全序列<P1、P3、P4、P0、P2>，系統(tǒng)安全，可以分配。P4請求資源P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查：1）Request4(3，3，0)≤Need4(4，3，1)2）Request4(3，3，0)＞Available(2，3，0)，讓P4等待。P0請求資源P0發(fā)出請求向量Request0

(0，2，0)，系統(tǒng)按銀行家算法進行檢查：1）Request0(0，2，0)≤Need0(7，4，3)2）Request0(0，2，0)≤Available(2，3，0)3）系統(tǒng)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如下所示。

為P0試分配資源后4）再利用安全性算法檢查此時系統(tǒng)是否安全。從上表中可以看出，可用資源Available（2，1，0）已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。資源情況進程

MaxAllocation

Need

Available

ABC

ABC

ABC

ABCP0853

130

723

210

P1323303020

P2903303600

P3222211011

P45331024314.5.6死鎖的檢測及解除通過系統(tǒng)的檢測機構(gòu)及時地檢測出死鎖的發(fā)生，然后采取某種措施解除死鎖。特點：死鎖檢測和解除可使系統(tǒng)獲得較高的利用率，但是實現(xiàn)難度最大。資源分配圖

系統(tǒng)死鎖可以利用資源分配圖描述。資源分配圖(

Resource-AllocationGraph)又稱進程—資源圖，由一組結(jié)點N和一組邊E所構(gòu)成：N被分成兩個互斥的子集：進程結(jié)點子集P＝{p1，p2，…，pn}，資源結(jié)點子集R＝｛r1，r2，…，rm｝。E是邊集，它連接著P中的一個結(jié)點和R中的一個結(jié)點，e＝<pi，rj>是資源請求邊，e＝<rj，pi>是資源分配邊。

通常，用圓圈代表一個進程，用方框代表一類資源，方框中的一個點代表一類資源中的一個資源。資源分配圖例p1p2r1r2死鎖判定法則將資源分配圖簡化可以檢測系統(tǒng)狀態(tài)S是否為死鎖狀態(tài)，方法如下：在資源分配圖中，找出一個既不阻塞又非孤立的進程結(jié)點pi，進程pi獲得了它所需要的全部資源，能運行完成然后釋放所有資源。這相當(dāng)于消去pi的所有請求邊和分配邊，使之成為孤立結(jié)點。進程pi釋放資源后，可以喚醒因等待這些資源而阻塞的進程，從而可能使原來阻塞的進程變?yōu)榉亲枞M程。在進行一系列化簡后，若能消去圖中所有的邊，使所有進程都成為孤立結(jié)點，則稱該圖是可完全簡化的；若不能使該圖完全化簡，則稱該圖是不可完全簡化的。

死鎖定理可以證明：所有的簡化順序?qū)⒌玫较嗤牟豢珊喕瘓D。S為死鎖狀態(tài)的條件是當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。該條件稱為死鎖定理。資源分配圖簡化例p1p2r1r2p1p2r1r2p1p2r1r2資源分配圖簡化例2下圖是否存在死鎖？p1p2p3r1r4r2r3此圖不可完全簡化，存在死鎖。資源分配圖簡化例3下圖是否存在死鎖？p2p3p4r1r2p1此圖可以完全簡化，不存在死鎖。死鎖檢測算法中的數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available：表示m類資源中每類資源的可用數(shù)目。請求矩陣Request：表示每個進程當(dāng)前對各類資源的請求數(shù)目。分配矩陣Allocation：表示每個進程當(dāng)前已分配的資源數(shù)目。工作向量Work：表示系統(tǒng)當(dāng)前可提供資源數(shù)。進程集合L：記錄當(dāng)前已不占用資源的進程。死鎖檢測的算法Work=Available;L=<Li|Allocationi=0∩Requesti=0>forallLiLdo{if（Requesti≤Work）{Work=Work+Allocationi;L=L∪Li;}}deadlock=(L==<p1,p2,…pn>)死鎖解除一旦檢測出系統(tǒng)中出現(xiàn)了死鎖，就應(yīng)將陷入死鎖的進程從死鎖狀態(tài)中解脫出來，常用的死鎖解除方法有兩種：資源剝奪法：當(dāng)發(fā)現(xiàn)死鎖后，從其他進程那里剝奪足夠數(shù)量的資源給死鎖進程，以解除死鎖狀態(tài)。撤消進程法：最簡單的方法是撤消全部死鎖進程，使系統(tǒng)恢復(fù)到正常狀態(tài)。但這種做法付出的代價太大。另一方法是按照某種順序逐個撤消死鎖進程，直到有足夠的資源供其他未被撤消的進程使用，消除死鎖狀態(tài)為止。處理死鎖的綜合方法單獨使用處理死鎖的某種方法不能全面解決OS中遇到的所有死鎖問題。綜合解決的辦法是：將系統(tǒng)中的資源按層次分為若干類，對每一類資源使用最適合它的辦法解決死鎖問題。即使發(fā)生死鎖，一個死鎖環(huán)也只包含某一層次的資源，因此整個系統(tǒng)不會受控于死鎖。綜合方法例將系統(tǒng)的資源分為四個層次：內(nèi)部資源：由系統(tǒng)本身使用，如PCB，采用有序資源分配法。主存資源：采用資源剝奪法。作業(yè)資源：可分配的設(shè)備和文件。采用死鎖避免法。交換空間：采用靜態(tài)分配法。習(xí)題P1043（1）3（5）3（6）3（9）選擇題1在下列調(diào)度層次中，所有操作系統(tǒng)中都必須配置的調(diào)度層次是_____。A．作業(yè)調(diào)度B．進程調(diào)度

C．交換調(diào)度D．中級調(diào)度在分時操作系統(tǒng)中，進程調(diào)度經(jīng)常采用_____算法。A．先來先服務(wù)B．最高優(yōu)先權(quán)C．短進程優(yōu)先D．時間片輪轉(zhuǎn)選擇題2_____優(yōu)先權(quán)是在創(chuàng)建進程時確定的，確定之后在整個進程運行期間不再改變。A.靜態(tài)B.作業(yè)C.資源

D.動態(tài)設(shè)有四個作業(yè)同時到達，每個作業(yè)的執(zhí)行時間均為2小時，它們在一臺處理器上按單道方式運行，則平均周轉(zhuǎn)時間為_____。A.8小時

B.2.5小時C.5小時

D.1小時選擇題3現(xiàn)有3個同時到達的作業(yè)J1、J2和J3，它們的執(zhí)行時間分別是T1、T2和T3，且T1＜T2＜T3。系統(tǒng)按單道方式運行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時間是_____。A.(3T1+2T2+T3)/3B.(T1+T2+T3)/3C.(T1+2T2+3T3)/3D.T1+T2+T3

_____是指從作業(yè)提交給系統(tǒng)到作業(yè)完成的時間間隔。A.運行時間

B.等待時間C.周轉(zhuǎn)時間D.響應(yīng)時間選擇題4下述作業(yè)調(diào)度算法中，________調(diào)度算法與作業(yè)的估計運行時間有關(guān)。A.先來先服務(wù)

B.短作業(yè)優(yōu)先C.時間片輪轉(zhuǎn)D.多級隊列采用時間片輪轉(zhuǎn)法進行進程調(diào)度是為了____。A．多個終端都能得到系統(tǒng)的及時響應(yīng)

B．先來先服務(wù)C．優(yōu)先級較高的進程得到及時響應(yīng)

D．需要CPU最短的進程先做選擇題5假設(shè)就緒隊列中有10個進程，系統(tǒng)將時間片設(shè)為200ms，CPU進行進程切換要花費10ms。則系統(tǒng)開銷所占的比率約為_____。

A．1％B．5％C．10％D．20％采用資源剝奪法可以解除死鎖，還可以采用_____方法解除死鎖。A.拒絕分配新資源

B.修改信號量C.執(zhí)行并行操作D.撤消進程選擇題6要防止死鎖的發(fā)生，可以通過破壞這四個必要條件之一來實現(xiàn)，但破壞_____條件是不太實際的。A.循環(huán)等待

B.部分分配C.不可搶占D.互斥資源的有序分配策略可以破壞_____條件。A.占有且等待資源B.循環(huán)等待資源C.非搶奪資源

D.互斥使用資源選擇題7在_____的情況下，系統(tǒng)出現(xiàn)死鎖。A.計算機系統(tǒng)發(fā)生了重大故障B.有多個封鎖的進程同時存在C.若干進程因競爭資源而無休止地相互等待他方釋放已占有的資源D.資源數(shù)大大小于進程數(shù)或進程同時申請的資源數(shù)大大超過資源總數(shù)銀行家算法在解決死鎖問題中是用于_____的。A.檢測死鎖B.預(yù)防死鎖

C.避免死鎖D.解除死鎖選擇題8某系統(tǒng)中有3個并發(fā)進程，都需要同類資源4個，試問該系統(tǒng)不會發(fā)生死鎖的最少資