第三章作業(yè)、處理機(jī)調(diào)度

第三章處理機(jī)管理教學(xué)內(nèi)容:1、調(diào)度的類型和模型、調(diào)度算法2、多處理機(jī)調(diào)度3、線程與進(jìn)程的區(qū)別4、進(jìn)程的通信5、管程機(jī)制6、死鎖

在多道程序系統(tǒng)中，一個作業(yè)從提交到執(zhí)行通常要經(jīng)歷多級調(diào)度，系統(tǒng)的運(yùn)行性能在很大程度上取決于調(diào)度。CPU調(diào)度使得多個進(jìn)程有條不紊地共享一個CPU。CPU調(diào)度為每個用戶都提供了一個虛擬處理機(jī)。一個好的調(diào)度策略對于加快作業(yè)總的周轉(zhuǎn)時間、提高單位時間內(nèi)的作業(yè)吞吐量、實現(xiàn)系統(tǒng)總的設(shè)計目標(biāo)十分重要。一、作業(yè)的狀態(tài)及其轉(zhuǎn)換§3.1分級調(diào)度進(jìn)程的三種狀態(tài)?①提交狀態(tài)：作業(yè)被提交給機(jī)房后或用戶通過終端鍵盤想計算機(jī)鍵入其作業(yè)時的狀態(tài).②后備狀態(tài)：作業(yè)的全部信息都已通過輸入機(jī)輸入，并由操作系統(tǒng)將其存在磁盤的某些分區(qū)（存放作業(yè)的輸入井）中等待運(yùn)行.③運(yùn)行狀態(tài)：作業(yè)一旦被作業(yè)調(diào)度程序選中而被送入主存中投入運(yùn)行.④完成狀態(tài)：作業(yè)完成其全部運(yùn)行，釋放出其所占用的全部資源。準(zhǔn)備退出系統(tǒng)時的作業(yè).二、作業(yè)與進(jìn)程的關(guān)系

計算機(jī)要完成一個任務(wù)實體，必須要有一個以上的執(zhí)行實體，一個作業(yè)總是由一個以上的多個進(jìn)程組成。作業(yè)是用戶向計算機(jī)提交任務(wù)的實體。

進(jìn)程是計算機(jī)為完成用戶任務(wù)實體而設(shè)置的執(zhí)行實體三、調(diào)度的層次

在多道程序環(huán)境下，操作系統(tǒng)中面對眾多進(jìn)程，為了提高調(diào)度效率，也實行分級調(diào)度。高級調(diào)度（作業(yè)調(diào)度、宏觀調(diào)度、長期調(diào)度、收容調(diào)度）按一定原則對外存輸入井上的作業(yè)進(jìn)行調(diào)度，從作業(yè)后備隊列中選擇作業(yè)進(jìn)入主存并建立進(jìn)程PCB。它決定允許哪些作業(yè)競爭系統(tǒng)資、決定哪些作業(yè)可以進(jìn)入系統(tǒng)。低級調(diào)度（進(jìn)程調(diào)度、短期調(diào)度）決定存在就緒進(jìn)程時，哪一個就緒進(jìn)程將分配到中央處理機(jī)，并且把中央處理機(jī)實際分配給這個進(jìn)程（即低級調(diào)度是將處理機(jī)分配給進(jìn)程）。

低級調(diào)度是由每秒可操作許多次的處理機(jī)調(diào)度程序執(zhí)行，處理機(jī)調(diào)度程序應(yīng)常駐存。僅有進(jìn)程調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型中級調(diào)度（交換調(diào)度、中程調(diào)度）

負(fù)責(zé)進(jìn)程在內(nèi)存和輔存對換區(qū)間的對換。一些進(jìn)程處于阻塞狀態(tài)而暫時不能運(yùn)行，中級調(diào)度將進(jìn)程暫時移到輔存對換區(qū)，對換區(qū)的進(jìn)程若其等待的事件已發(fā)生，則它們要由阻塞狀態(tài)變?yōu)榫途w，為了繼續(xù)這些進(jìn)程的繼續(xù)進(jìn)行，則由中級調(diào)度再度把它們調(diào)入內(nèi)存。一個進(jìn)程在其運(yùn)行期間有可能多次調(diào)進(jìn)調(diào)出決定允許哪些進(jìn)程競爭處理機(jī)引入中級調(diào)度后，進(jìn)程的就緒狀態(tài)分為內(nèi)存就緒(表示進(jìn)程在內(nèi)存中就緒)和外存就緒(進(jìn)程在外存中就緒)。類似地，也可把阻塞狀態(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。

具有三級調(diào)度時的調(diào)度隊列模型

作業(yè)調(diào)度的功能：按某種算法從后備隊列中挑選一個或一批作業(yè)調(diào)入內(nèi)存，并創(chuàng)建PCB。一、后備作業(yè)隊列與作業(yè)控制塊

系統(tǒng)中有若干作業(yè)在輸入井中，為了管理和調(diào)度作業(yè)，就必須記錄已進(jìn)入系統(tǒng)的各作業(yè)的情況，系統(tǒng)為每個作業(yè)設(shè)置了一個作業(yè)控制塊（JCB）。

§3.2作業(yè)的調(diào)度

作業(yè)名

作業(yè)類型

資源要求

資源使用情況

優(yōu)先級

當(dāng)前狀態(tài)

其它二、作業(yè)控制塊JCB三、作業(yè)調(diào)度應(yīng)完成的工作①按照某種調(diào)度算法從后備作業(yè)隊列中選取作業(yè)。②為被選取的作業(yè)分配內(nèi)存和外設(shè)資源（當(dāng)系統(tǒng)為動態(tài)分配外設(shè)時，作業(yè)所申請的外設(shè)只作為調(diào)度的參考因素）。因此要用到內(nèi)存分配程序和外設(shè)分配程序。

③為選中的作業(yè)建立相應(yīng)的進(jìn)程。

④為作業(yè)開始運(yùn)行做好一切準(zhǔn)備工作。如構(gòu)造和讀寫作業(yè)運(yùn)行時所需要的有關(guān)表格及建立負(fù)責(zé)其運(yùn)行控制的作業(yè)運(yùn)行控制程序。⑤在作業(yè)運(yùn)行完畢或運(yùn)行過程中因某種原因需要撤離時，作業(yè)調(diào)度程序還有完成作業(yè)的善后處理工作，如收回分配給他的全部資源，它們將從系統(tǒng)中抹去。四、作業(yè)調(diào)度目標(biāo)與轉(zhuǎn)換過程1、調(diào)度目標(biāo)

a.對所有作業(yè)應(yīng)該是公平合理

b.應(yīng)使設(shè)備有高的利用率

c.每天執(zhí)行盡可能多的作業(yè)

d.有快的響應(yīng)時間

2、作業(yè)調(diào)度的轉(zhuǎn)換過程

a.作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)

b.作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài)

后備作業(yè)隊列空按調(diào)度算法從作業(yè)中選出一作業(yè)調(diào)用存儲、設(shè)備管理程序，審核資源要求資源要求能滿足？放棄該作業(yè)否分配資源調(diào)用進(jìn)程管理程序建立進(jìn)程進(jìn)程調(diào)度否是出口作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)撤銷該作業(yè)的所有進(jìn)程及作業(yè)的JCB調(diào)用存儲管理，設(shè)備管理回收分配給該作業(yè)的全部資源調(diào)用會計程序，計算該作業(yè)的執(zhí)行費(fèi)用調(diào)度下一個作業(yè)作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài)一、低級調(diào)度的主要功能如下：(1)保存處理機(jī)的現(xiàn)場信息。在進(jìn)程調(diào)度進(jìn)行調(diào)度時，首先需要保存當(dāng)前進(jìn)程的處理機(jī)的現(xiàn)場信息，如程序計數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進(jìn)程的進(jìn)程控制塊(PCB)中的相應(yīng)單元?！?.3進(jìn)程調(diào)度(2)按照某種算法選取進(jìn)程。低級調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等，從就緒隊列中選取一個進(jìn)程，把它的狀態(tài)改為運(yùn)行狀態(tài)，并準(zhǔn)備把處理機(jī)分配給它。(3)把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。此時需為選中的進(jìn)程恢復(fù)處理機(jī)現(xiàn)場，即把選中進(jìn)程的進(jìn)程控制塊內(nèi),有關(guān)處理機(jī)現(xiàn)場的信息裝入處理器相應(yīng)的各個寄存器中，把處理器的控制權(quán)交給該進(jìn)程，讓它從取出的斷點處開始繼續(xù)運(yùn)行。

二、進(jìn)程調(diào)度中的三個基本機(jī)制

(1)排隊器。為了提高進(jìn)程調(diào)度的效率，應(yīng)事先將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個或多個隊列，以便調(diào)度程序能最快地找到它。(2)分派器(分派程序)。分派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，從就緒隊列中取出該進(jìn)程，然后進(jìn)行上下文切換，將處理機(jī)分配給它。

(3)上下文切換機(jī)制。當(dāng)對處理機(jī)進(jìn)行切換時，會發(fā)生兩對上下文切換操作。在第一對上下文切換時，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二對上下文切換時，將移出分派程序，把新選進(jìn)程的CPU現(xiàn)場信息裝入到處理機(jī)的各個相應(yīng)寄存器中。

上下文切換花去不少的處理機(jī)時間，每一次上下文切換大約需要花費(fèi)幾毫秒的時間，該時間大約可執(zhí)行上千條指令?，F(xiàn)在已有通過硬件(采用兩組或多組寄存器)的方法來減少上下文切換的時間。一組寄存器供處理機(jī)在系統(tǒng)態(tài)時使用一組寄存器供應(yīng)用程序使用。這種條件下的上下文切換只需改變指針，使其指向當(dāng)前寄存器組即可。三、進(jìn)程調(diào)度方式進(jìn)程調(diào)度可采用下述兩種調(diào)度方式。

1)非搶占方式(NonpreemptiveMode)一旦把處理機(jī)分配給某進(jìn)程后，不管運(yùn)行多長時間，都讓它運(yùn)行下去，決不會因為時鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時，才再把處理機(jī)分配給其他進(jìn)程。

在采用非搶占調(diào)度方式時，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為如下幾個：

(1)正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；

(2)執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；

(3)在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。。非搶占調(diào)度方式實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。

2)搶占方式(PreemptiveMode)允許調(diào)度程序根據(jù)某種原則去暫停某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。優(yōu)點:防止一個長進(jìn)程長時間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對響應(yīng)時間有著較嚴(yán)格要求的實時任務(wù)的需求。但比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條：(1)優(yōu)先權(quán)原則。對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程，使之執(zhí)行；或者說，允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。

(2)短作業(yè)(進(jìn)程)優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程)明顯的短時，將暫停當(dāng)前長作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行；或者說，短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長作業(yè)(進(jìn)程)的處理機(jī)。(3)時間片原則。各進(jìn)程按時間片輪流運(yùn)行，當(dāng)一個時間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時系統(tǒng)、大多數(shù)的實時系統(tǒng)，以及要求較高的批處理系統(tǒng)。§3.4調(diào)度算法一、周轉(zhuǎn)時間：作業(yè)i從提交時刻Tsi到完成時刻Tei稱為作業(yè)的周轉(zhuǎn)時間。Ti=Tei(完成時刻)-Tsi(提交時刻)

一個作業(yè)的周轉(zhuǎn)時間說明該作業(yè)在系統(tǒng)內(nèi)停留的時間包含兩部分：等待時間和執(zhí)行時間

Ti=Twi+Tri

二、平均周轉(zhuǎn)時間為（有n個作業(yè)，n>=1) n T=1/n∑Ti i=1三、帶權(quán)周轉(zhuǎn)時間Wi：

Wi=Ti(周轉(zhuǎn)時間)/Tri(執(zhí)行時間)平均帶權(quán)周轉(zhuǎn)時間為：

n W=1/n∑Wi i=1四、好的調(diào)度算法要求：CPU利用率高、吞吐量大、T和W小1、先來先服務(wù)（FCFS）調(diào)度算法將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理。優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管要求運(yùn)行時間的長短。作業(yè)進(jìn)入時刻運(yùn)行時間完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1１０：003010：30 2１０：10603１０：2040 4１０：3020

作業(yè)1:

周轉(zhuǎn)時間T1＝10:30－10:00＝30先來先服務(wù)算法分析結(jié)果301801.331102.75120611：3012：1012：30作業(yè)2:

周轉(zhuǎn)時間T2＝11:30－10:10＝80帶權(quán)周轉(zhuǎn)時間W1＝30/30＝1

帶權(quán)周轉(zhuǎn)時間W2＝80/60＝1.33作業(yè)3:

周轉(zhuǎn)時間T3＝12.10－10.20＝110

帶權(quán)周轉(zhuǎn)時間W3＝110/40＝2.75作業(yè)4:周轉(zhuǎn)時間T4＝12.30－10.30＝120

帶權(quán)周轉(zhuǎn)時間W4＝120/20＝6平均周轉(zhuǎn)時間:T＝(T1+T2+T3+T4)/4平均帶權(quán)周轉(zhuǎn)時間:W＝(W1+W2+W3+W4)/4T＝(30+80+110+120)/4=85(min)W＝(1+1.33+2.75+6)/4=2.77(min)作業(yè)號

1

2

3

4

到達(dá)時間8.008.509.009.50運(yùn)行時間2.000.500.100.20調(diào)度順序1

2

3

4作業(yè)號1

2

34到達(dá)時間8.008.509.009.50開始時間8.0010.0010.5010.60結(jié)束時間

10.0010.5010.6010.80周轉(zhuǎn)時間2.002.001.601.30加權(quán)周轉(zhuǎn)時間14

16

6.5例3-1：有下述作業(yè)序列：T1=10.00-8.00=2.00W1=2.00/2.00=1T2=10.50-8.50=2.00W2=2.00/0.50=4

T3=10.60-9.00=1.60W3=1.60/0.10=16T4=10.80-9.50=1.30W4=1.30/0.20=6.5

平均周轉(zhuǎn)時間T=（T1+T2+T3+T4）/4=1.73加權(quán)平均周轉(zhuǎn)時間W=(W1+W2+W3+W4)/4=6.88算法評價：這種算法按先來后到原則調(diào)度，比較公平，但是不利于短作業(yè)。此算法有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。

CPU繁忙型作業(yè)：指CPU進(jìn)行處理時，不需頻繁的請求I/O，而每次I/O的操作時間又很短。I/O繁忙型作業(yè)：指該類作業(yè)無需大量的CPU時間進(jìn)行計算，但要頻繁地請求I/O。2、最短作業(yè)優(yōu)先法（SJF）：該算法總是優(yōu)先調(diào)度要求運(yùn)行時間最短的作業(yè)。選中某個短作業(yè)后，就保證該作業(yè)盡可能快地完成運(yùn)行并退出系統(tǒng)，運(yùn)行中不允許被搶占。作業(yè)進(jìn)入時刻運(yùn)行時間完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1１０：0030 2１０：10603１０：2040

4１０：302010:3012:3011:3010:5030207014011.752.331平均帶權(quán)周轉(zhuǎn)時間W＝1.55(T=1+2.33+1.75+1)/4=1.52(min)平均周轉(zhuǎn)時間T=0.65(T=30+140+70+20)/4=65(min)

例3-2：有下述作業(yè)序列：作業(yè)號

1

2

3

4

到達(dá)時間8.008.509.009.50運(yùn)行時間2.000.500.100.20調(diào)度順序1

2

3

4作業(yè)號1

3

42到達(dá)時間8.009.009.508.50開始時間8.0010.0010.1010.30結(jié)束時間

10.0010.1010.3010.80周轉(zhuǎn)時間2.001.100.802.30加權(quán)周轉(zhuǎn)時間111

4

4.6周轉(zhuǎn)時間：

加權(quán)周轉(zhuǎn)時間：

T=結(jié)束時間-到達(dá)時間

T1=10.00-8.00=2.00

T2=10.80-8.50=2.30

T3=10.10-9.00=1.10

T4=10.30-9.50=0.80

W=周轉(zhuǎn)時間+運(yùn)行時間

W1=2.00/2.00=1

W2=2.30/0.50=4.6

W3=1.10/0.10=11

W4=0.80/0.20=4

平均周轉(zhuǎn)時間：

T=(T1+T2+T3+T4)/4=1.55

加權(quán)平均周轉(zhuǎn)時間：

W=(1+4.6+11+4)/4=5.15算法評價：優(yōu)點:有利于短作業(yè)。給定的時限內(nèi)可以完成更多的作業(yè)，增加系統(tǒng)的吞吐量，改善調(diào)度性能。缺點：（1）對長作業(yè)不利。

（2）完全沒考慮作業(yè)的緊迫程度，不能保證緊迫作業(yè)會得到及時處理。

（3）由于作業(yè)的長短只根據(jù)用戶提供的估計執(zhí)行時間而定,而用戶又有可能會有意無意的縮短其作業(yè)的估計執(zhí)行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。五、高優(yōu)先權(quán)優(yōu)先調(diào)度算法1．優(yōu)先權(quán)調(diào)度算法的類型常用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為進(jìn)程調(diào)度算法，還用于實時系統(tǒng)中。當(dāng)把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時，該算法是把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程，這時，又可進(jìn)一步把該算法分成如下兩種。

1)非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中。

2)搶占式優(yōu)先權(quán)調(diào)度算法系統(tǒng)把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。*:在采用這種調(diào)度算法時，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。2．優(yōu)先權(quán)的類型

(1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，且在進(jìn)程的整個運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，如，0～7或0～255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)，只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。

確定進(jìn)程優(yōu)先權(quán)的依據(jù)：

1)進(jìn)程類型。系統(tǒng)進(jìn)程(如接收進(jìn)程、對換進(jìn)程、磁盤I/O進(jìn)程)的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。

2)進(jìn)程對資源的需求。如進(jìn)程的估計執(zhí)行時間及內(nèi)存需要量的多少，對這些要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)。

3)用戶要求。是由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來確定優(yōu)先權(quán)的。

靜態(tài)優(yōu)先權(quán)法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進(jìn)程)長期沒有被調(diào)度的情況。因此，僅在要求不高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。

(2)動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊列的進(jìn)程將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)。采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機(jī)。在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運(yùn)行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高，則長作業(yè)在等待一定的時間后，必然有機(jī)會分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為：3、最高相應(yīng)比作業(yè)優(yōu)先算法（HRN）R=（等待時間+要求服務(wù)時間）/要求服務(wù)時間

=響應(yīng)時間/要求服務(wù)時間

R=（等待時間+要求服務(wù)時間）/要求服務(wù)時間=響應(yīng)時間/要求服務(wù)時間

(1)如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。

(2)當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。

(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)。該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會使長作業(yè)長期得不到服務(wù)。因此，該算法實現(xiàn)了一種較好的折衷。當(dāng)然，在利用該算法時，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計算，這會增加系統(tǒng)開銷。例3-3：有下述作業(yè)序列：作業(yè)序列號

1

2

3

4到達(dá)時間8.008.509.009.50運(yùn)行時間2.000.500.100.20在8.00這一時刻只有作業(yè)1到達(dá)所以先運(yùn)行。因為此調(diào)度算法是非搶占式的，所以一直到作業(yè)1運(yùn)行完，在時刻10.00才決定下一個作業(yè)，而此時作業(yè)2，3，4都已到達(dá)，則分別對它們進(jìn)行響應(yīng)比計算。

RP2=4，RP3=11，RP4=3.5

作業(yè)3作業(yè)2作業(yè)4調(diào)度順序

1

2

3

4作業(yè)號

1

3

2

4到達(dá)時間8.009.008.509.50開始時間8.0010.0010.1010.60結(jié)束時間10.0010.1010.6010.80周轉(zhuǎn)時間2.000加權(quán)周轉(zhuǎn)時間

1114.26.5平均周轉(zhuǎn)時間T=(T1+T2+T3+T4)/4=1.625加權(quán)平均周轉(zhuǎn)時間W=(W1+W2+W3+W4)/4=5.64、時間片輪轉(zhuǎn)調(diào)度算法（RR）（1）基于時間片的輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)法主要用于進(jìn)程調(diào)度。q=1和q=4時的進(jìn)程運(yùn)行情況

q=1和q=4時進(jìn)程的周轉(zhuǎn)時間

例：

進(jìn)

程

P1

P2

P3

下一個CPU周期

24

3

3

解：若取時間片=4，則輪轉(zhuǎn)法執(zhí)行情況如下：

T2=7，T3=10完成，T1=30。平均周轉(zhuǎn)時間：T=(T1+T2+T3）/3=（7+10+30）/3=16

：

P1P1P1P1P1P1P2P3047101418222630①當(dāng)時間片很大時，每個進(jìn)程得到比完成該進(jìn)程多的處理機(jī)時間，此時輪轉(zhuǎn)調(diào)度模式退化為先進(jìn)先出模式。②當(dāng)時間片非常小時，上下文轉(zhuǎn)換開銷就成了決定因素，系統(tǒng)性能降低，大多數(shù)時間都消耗在處理機(jī)的轉(zhuǎn)換上，只有少許用在用戶的計算上。

這個最佳的時間片值是多少呢？顯然，它將隨系統(tǒng)而異。隨負(fù)載而異，同時也隨進(jìn)程異。時間片的選取是實現(xiàn)各種調(diào)度算法的關(guān)鍵之處，而時間片的額定通常應(yīng)考慮終端數(shù)目，處理機(jī)能力、各終端任務(wù)的急迫程度、外存?zhèn)鬏斔俣鹊确矫娴囊蛩?。時間片輪轉(zhuǎn)法亦可應(yīng)用于批處理系統(tǒng)的處理機(jī)調(diào)度。時間片的更新：

每當(dāng)一輪調(diào)度開始時，系統(tǒng)便根據(jù)就緒隊列中已有進(jìn)程數(shù)目計算一次值。作為新一輪調(diào)度的時間片。這種方法得到的時間片是隨就緒隊列中的進(jìn)程數(shù)變化的。（2）多級反饋隊列調(diào)度算法

1)應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。

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

2)當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運(yùn)行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當(dāng)一個長作業(yè)(進(jìn)程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運(yùn)行。

3)僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?～(i-1)隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊列中為某進(jìn)程服務(wù)時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。(3)多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。

1)終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)(進(jìn)程)在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。

2)短批處理作業(yè)用戶。對于很短的批處理型作業(yè)，開始時像終端型作業(yè)一樣，如果僅在第一隊列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時間。對于稍長的作業(yè)，通常只需在第二隊列和第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。

3)長批處理作業(yè)用戶。對于長作業(yè)，它將依次在第1，2，…，n個隊列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。5、四種調(diào)度算法的優(yōu)、缺點：

例：

進(jìn)程

下一個CPU周期

P1

9

P2

3

P3

6

1）FCFS調(diào)度算法：

T1=9

T2=12

T3=18平均周轉(zhuǎn)時間T=(T1+T2+T3)/3=13

W1=1

W2=4

W3=3加權(quán)周轉(zhuǎn)時間W=(W1+W2+W3)/3=2.7

P1P2P30912182）SJF調(diào)度算法：0P2P3P13918T1=18T2=3T3=9

平均周轉(zhuǎn)時間T=（T1+T2+T3）/3=10

W1=2

W2=1W3=1.5

加權(quán)周轉(zhuǎn)時間W=(W1+W2+W3)/3=1.5當(dāng)時間片=4：

T1=18T2=7

T3=17

平均周轉(zhuǎn)時間T=（T1+T2+T3）/3=14

W1=2

W2=2.3W3=2.9加權(quán)周轉(zhuǎn)時間W=(W1+W2+W3)/3=2.4

P2P3P1011154P1717P3183）時間片調(diào)度算法（RR算法）：當(dāng)時間片=3：

T1=18T2=6

T3=15

平均周轉(zhuǎn)時間T=（T1+T2+T3）/3=13

W1=2

W2=2

W3=2.5加權(quán)周轉(zhuǎn)時間W=(W1+W2+W3)/3=2.2

P2P3P109123P161518P3P13）時間片調(diào)度算法（RR算法）：

T1=9

T2=12

T3=18平均周轉(zhuǎn)時間T=(t1+T2+T3)/3=13

W1=1W2=4

W3=3

加權(quán)周轉(zhuǎn)時間W=(W1+W2+W3)/3=2.7P1P2P30912184）HRN調(diào)度算法：

算

法

T

W

FIFO

13

2.7

SJF

10

1.5

時間片(4)

14

2.4

HRN

13

2.7

什么是多處理機(jī)系統(tǒng)多處理機(jī)操作系統(tǒng)的分類多處理機(jī)系統(tǒng)調(diào)度策略§3.5多處理機(jī)調(diào)度一、多處理機(jī)系統(tǒng)：是一個具有兩個或多個處理機(jī)能相互進(jìn)行通信以協(xié)同一個大的給定問題求解的計算機(jī)系統(tǒng)。使用多處理機(jī)系統(tǒng)的主要原因：

1、提高系統(tǒng)吞吐量。多處理機(jī)操作系統(tǒng)提高資原分配和管理，進(jìn)程和處理機(jī)管理，內(nèi)存和數(shù)據(jù)集保護(hù)以及文件系統(tǒng)等功能。

2、提高系統(tǒng)的可靠性在發(fā)生故障時能使用；還能提供系統(tǒng)結(jié)構(gòu)重組的能力，以支持系統(tǒng)的降級使用。因此，多處理機(jī)的調(diào)度策略也必須考慮到降級使用和結(jié)構(gòu)重組問題。特點：1）有兩個或多個處理機(jī)2）共享主存或高速通信網(wǎng)絡(luò)3）共享輸入輸出子系統(tǒng)4）有單一完整的操作系統(tǒng)5）各級硬件和軟件相互作用

廣義的計算機(jī)系統(tǒng)的一個共同的特點是有n個處理器(n>1),能做到真正的并行處理,也就是能同時執(zhí)行n條指令主要功能：●進(jìn)程分配●更好的利用多機(jī)硬件●資源在處理機(jī)之間的分配●改善程序的響應(yīng)時間●處理機(jī)的負(fù)載平衡●處理機(jī)間的協(xié)調(diào)和同步●因處理機(jī)故障引起的系統(tǒng)重組

廣義上說，使用多處理機(jī)協(xié)調(diào)工作，來完成用戶所要求任務(wù)的計算機(jī)系統(tǒng)。這包擴(kuò)了并行處理系統(tǒng)（parallelprocessingsystem），例如數(shù)據(jù)流機(jī)(dataflowmachine)和細(xì)胞陣列處理機(jī)(Celluararrayprocessors)等，也包擴(kuò)了在物理上分散且通過不同的物理傳輸媒體傳輸數(shù)據(jù)的機(jī)算機(jī)網(wǎng)絡(luò)系統(tǒng)和計算機(jī)網(wǎng)絡(luò)為基礎(chǔ)的，對用戶透明的分布式系統(tǒng)，以及在同一的計算機(jī)系統(tǒng)里共享內(nèi)存的多處理機(jī)系統(tǒng)。

二、多處理機(jī)操作系統(tǒng)：

指哪些用來并行執(zhí)行用戶的幾個程序，以提高系統(tǒng)的吞吐率、提高系統(tǒng)可靠性的多處理機(jī)操作系統(tǒng)。這種系統(tǒng)由共享公共內(nèi)存和外設(shè)的n(n>1)個CPU組成。

從概念上說，在多處理機(jī)系統(tǒng)中的各進(jìn)程的行為與在單機(jī)系統(tǒng)下的行為相同。多處理環(huán)境下，進(jìn)程可在各處理機(jī)間進(jìn)行透明遷移，從而由進(jìn)程上下文切換等帶來的系統(tǒng)開銷將使多處理機(jī)操作系統(tǒng)的復(fù)雜度大大增加。另外，由于多處理機(jī)系統(tǒng)并行地執(zhí)行用戶的幾個程序（進(jìn)程），這又帶來了多處理機(jī)條件下的并發(fā)執(zhí)行問題。三、多處理機(jī)操作系統(tǒng)

主從式（master-slaveconfiguration）獨立監(jiān)控系統(tǒng)(Separatesupervisor)

移動式監(jiān)控系統(tǒng)(floatingsupervisor)(1)主從式指定一臺特定的處理機(jī)為主處理機(jī)，由它負(fù)責(zé)對全系統(tǒng)的執(zhí)行進(jìn)行控制。主處理器上執(zhí)行操作系統(tǒng)程序，以控制其它從處理機(jī)的狀態(tài)，并為從處理機(jī)分配任務(wù)。DECsystem10，Cyber170以及多處理機(jī)UNIX系統(tǒng)MPX都是主從式結(jié)構(gòu)。

在主從式操作系統(tǒng)中，如果從處理機(jī)需要主處理機(jī)提供服務(wù)時,它們采用硬件中斷方式中斷處理機(jī)上執(zhí)行的進(jìn)程以要求主處理機(jī)提供服務(wù)。這種結(jié)構(gòu)的操作系統(tǒng)一般重組功能較差，因為只有主處理機(jī)上執(zhí)行操作系統(tǒng)程序。如果主處理機(jī)失敗或發(fā)生不可恢復(fù)的錯誤時，整系統(tǒng)將會癱瘓。(2)獨立監(jiān)控系統(tǒng)獨立監(jiān)控系統(tǒng)的監(jiān)控程序在每個處理機(jī)上執(zhí)行,每個處理機(jī)為自己的需要提供服務(wù)又互相通報執(zhí)行情況.一般來說,每個監(jiān)控程序能重新裝入或在不同的處理機(jī)上復(fù)制獨立的副本.

獨立監(jiān)控系統(tǒng)不像主從結(jié)構(gòu)那樣易于崩潰,但其監(jiān)控程序在各處理機(jī)中的副本會占去大量的內(nèi)存.(3)移動式監(jiān)控系統(tǒng)移動式監(jiān)控系統(tǒng)把監(jiān)控程序根據(jù)需要從一個處理機(jī)移到另一個處理機(jī)上.使所有資原有比較均衡的負(fù)載.

移動式監(jiān)控系統(tǒng)的處理機(jī)調(diào)度以及服務(wù)請求沖突等大都采用優(yōu)先級的方式來解決。所以移動式監(jiān)控系統(tǒng)是一種效率最高,實現(xiàn)也最難的多處理操作系統(tǒng)。四、多處理機(jī)系統(tǒng)調(diào)度策略調(diào)度目標(biāo)是：以最高的可靠性，使用最少的處理機(jī)在最短的時間內(nèi)完成最多的可以并行完成的進(jìn)程。調(diào)度評價：調(diào)度程序的目的：是根據(jù)給定的執(zhí)行時間和相互關(guān)系，確定出一個最佳的執(zhí)行順序。多處理機(jī)的調(diào)度有兩種評價模型：（1）確定性模型、（2）隨機(jī)性模性確定性模型只用來確定給定進(jìn)程的執(zhí)行順序，而隨機(jī)性模性則常被用來研究動態(tài)調(diào)度技術(shù)。確定性模型：進(jìn)程調(diào)度執(zhí)行之前，估計出這些被調(diào)度進(jìn)程所需的執(zhí)行時間，以及這些進(jìn)程之間的相互關(guān)系。動態(tài)調(diào)度：在一個特定的時刻，將進(jìn)程分配到一個特定的處理機(jī)上執(zhí)行。隨機(jī)模型中的進(jìn)程執(zhí)行時間是一個具有平均值和標(biāo)準(zhǔn)偏移值的隨機(jī)變量。

五、多處理機(jī)系統(tǒng)與單機(jī)調(diào)度的區(qū)別

1、多處理機(jī)調(diào)度與單機(jī)調(diào)度的主要區(qū)別涉及兩個資源分配問題：（1）存放程序或數(shù)據(jù)的存儲器分配及如何訪問他們的問題。

在多機(jī)系統(tǒng)中，由于各進(jìn)程在物理上也同時執(zhí)行而不是單機(jī)系統(tǒng)那樣的交叉執(zhí)行，這些在物理上同時執(zhí)行的進(jìn)程可能同時訪問物理存儲器的同一地址。處理機(jī)對同一存儲塊的訪問必須是順序的。各進(jìn)程同時訪問物理存儲器上的同一地址是不允許的。

2、將等待執(zhí)行的就緒進(jìn)程分配到哪一個處理機(jī)上執(zhí)行的問題。

在單機(jī)系統(tǒng)中，由于只有一個處理機(jī)，在調(diào)度程序中選取了某個就緒狀態(tài)的進(jìn)程之后，不須再選擇處理機(jī)。而在多機(jī)系統(tǒng)中，為了盡量做到讓各處理機(jī)負(fù)荷平衡，可能會會將處理機(jī)在進(jìn)程之間進(jìn)行多次切換。如果被切換進(jìn)程正在執(zhí)行其臨界區(qū)部分或系統(tǒng)中進(jìn)程數(shù)目相當(dāng)多，這種頻繁的上下文轉(zhuǎn)換將會使系統(tǒng)效率大大下降。為了解決進(jìn)程對處理機(jī)的分配問題，在有的多出理機(jī)系統(tǒng)中采用了局部就緒對列的方法限制進(jìn)程的轉(zhuǎn)移。

局部就緒對列：就是把處于就緒狀態(tài)的進(jìn)程分成不同的組，并使每一組進(jìn)程和一個處理機(jī)對應(yīng)起來。優(yōu)點：每個處理機(jī)只執(zhí)行其對應(yīng)就緒對列中的進(jìn)程。各個就緒對列中的進(jìn)程不斷發(fā)生橫向轉(zhuǎn)移。減少了調(diào)度程序的開銷。缺點：處理機(jī)的使用率卻因此下降。例如：系統(tǒng)中某個局部就緒對列中因等待進(jìn)程較多而使得對應(yīng)的處理機(jī)十分繁忙，而另外的處理機(jī)則因就緒對列為空而處于空閑狀態(tài)。進(jìn)程的定義進(jìn)程的參考定義有如下幾種：1、進(jìn)程是程序的一次執(zhí)行；2、進(jìn)程=PCB+程序+數(shù)據(jù)；3、進(jìn)程是一個可擁有資源的獨立實體，同時又是一個可以獨立調(diào)度的基本單位?！?.6進(jìn)程控制PCB程序段私有數(shù)據(jù)塊進(jìn)程結(jié)構(gòu)三要素:

進(jìn)程名

當(dāng)前狀態(tài)

優(yōu)先數(shù)

現(xiàn)場保留區(qū)

指示處于同一狀態(tài)進(jìn)程的鏈指針

資源清單

進(jìn)程起始地址

家族關(guān)系

其他進(jìn)程控制塊一、進(jìn)程控制祖先進(jìn)程用戶進(jìn)程系統(tǒng)進(jìn)程用戶進(jìn)程用戶進(jìn)程進(jìn)程家族樹任務(wù):對系統(tǒng)中的全部進(jìn)程實施有效管理表現(xiàn):進(jìn)程的創(chuàng)建、撤消、狀態(tài)轉(zhuǎn)換二、原語：

操作系統(tǒng)的核心，由若干條指令組成，用以實現(xiàn)某個特定操作。不可中斷的系統(tǒng)程序。在管態(tài)下運(yùn)行、常駐內(nèi)存目的:實現(xiàn)進(jìn)程的通信和控制三、原語和系統(tǒng)調(diào)用的區(qū)別：（1）相同點：被進(jìn)程調(diào)用（2）不同點：原語是通過在其執(zhí)行過程中關(guān)閉中斷實現(xiàn)，一般由系統(tǒng)進(jìn)程調(diào)用；系統(tǒng)調(diào)用是在目態(tài)下執(zhí)行的進(jìn)程調(diào)用，并借助中斷進(jìn)入管態(tài)程序，最后轉(zhuǎn)交給相應(yīng)的系統(tǒng)進(jìn)程實現(xiàn)功能；原語有不可中斷性進(jìn)程控制原語及進(jìn)程的狀態(tài)轉(zhuǎn)換運(yùn)行就緒阻塞進(jìn)程調(diào)度I/O完成時間片用完等待I/O完成創(chuàng)建進(jìn)程撤銷進(jìn)程喚醒進(jìn)程阻塞進(jìn)程結(jié)束開始進(jìn)程控制原語創(chuàng)建原語撤銷原語阻塞原語喚醒原語

置狀態(tài)為“阻塞”插入等待隊列停止程序運(yùn)行釋放PCB釋放內(nèi)存釋放所有資源申請空白PCB填PCB置狀態(tài)為“就緒”插入就緒隊列置狀態(tài)為“就緒”插入就緒隊列進(jìn)程的屬性：1、可擁有資源的獨立單位；2、可以獨立調(diào)度和分配的基本單位。并發(fā)執(zhí)行的先提條件：1、創(chuàng)建進(jìn)程2、撤消進(jìn)程3、進(jìn)程切換四、線程引入線程的目的：為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統(tǒng)具有更好的并發(fā)性?！M(jìn)程線程1線程2線程3進(jìn)程1

分配處理機(jī)資源分配線程：是進(jìn)程中的一個實體，是被系統(tǒng)獨立調(diào)度的基本單位。線程有進(jìn)程的三個基本狀態(tài)。進(jìn)程和線程的區(qū)別：1、調(diào)度同一進(jìn)程中線程的切換不會引起進(jìn)程切換2、并發(fā)性進(jìn)程之間或進(jìn)程內(nèi)的多個線程間都可并發(fā)執(zhí)行3、擁有資源進(jìn)程擁有資源而線程可以訪問其隸屬進(jìn)程的資源（代碼段、數(shù)據(jù)段等）4、系統(tǒng)開銷進(jìn)程切換開銷大于線程切換的開銷§3.7進(jìn)程通信臨界資源和臨界區(qū)同步與互斥兩個經(jīng)典的同步/互斥問題其他同步例子管程消息緩沖一、進(jìn)程通信概述:進(jìn)程通信：指進(jìn)程間的信息交換過程按進(jìn)程間通信的規(guī)模和方式的不同，分為低級通信和高級通信。低級通信：進(jìn)程間只傳遞狀態(tài)和整數(shù)值（控制信息），包括進(jìn)程互斥和同步所采用的信號量及管程機(jī)制。缺點：傳送信息量小，效率低；編程復(fù)雜，易出錯高級通信：進(jìn)程間通信時能夠傳送任意數(shù)量的數(shù)據(jù)。主要包括共享存儲區(qū)、共享文件、消息傳遞（分為消息緩沖和信箱方式）。獨立進(jìn)程：在并發(fā)（多任務(wù)）環(huán)境下，一個進(jìn)程不受到其他進(jìn)程的影響。協(xié)作進(jìn)程：在并發(fā)（多任務(wù)）環(huán)境下，一個進(jìn)程受到其他進(jìn)程的影響，該進(jìn)程和影響他的進(jìn)程都稱為協(xié)作進(jìn)程。影響的關(guān)系有互斥、同步、通信。二、臨界資源和臨界區(qū)臨界資源:criticalresource（某段時間內(nèi)只允許一個進(jìn)程使用的資源）臨界區(qū):criticalsection（必須互斥執(zhí)行的程序段是相對于臨界資源的臨界區(qū)）程序1Y=Y+1output程序2Y=Y+2output內(nèi)存共享區(qū)Ypcb1pcb2使用臨界區(qū)應(yīng)遵循以下準(zhǔn)則：（1）空閑則入：其他進(jìn)程均不處于臨界區(qū)；（2）忙則等待：已有進(jìn)程處于臨界區(qū)；（3）有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能“死等”（4）讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）三、同步與互斥基本概念同步工具硬件指令信號量與P、V操作并發(fā)程序共享資源問題的解決基本概念同步進(jìn)程之間的一種通信方式，有時序上的制約關(guān)系，或者說是進(jìn)程之間為了協(xié)同工作而存在的一種等待關(guān)系?；コ膺M(jìn)程之間對臨界資源的一種競爭關(guān)系，排他性地對資源的訪問方式。進(jìn)程同步：進(jìn)程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系，是進(jìn)程之間的直接制約關(guān)系。在多道環(huán)境下，這種進(jìn)程間在執(zhí)行次序上的協(xié)調(diào)必不可少。進(jìn)程互斥：保證每次只有一個進(jìn)程使用臨界資源。主要用于資源共享，是進(jìn)程之間的間接制約關(guān)系。軟件的忙等互斥方案

PiRepeatwhileturn<>idoskipcriticalsection(臨界區(qū))turn=jremainsection(其余代碼)Untilfalse

PjRepeatwhileturn<>jdoskipcriticalsection(臨界區(qū))turn=i//強(qiáng)制輪流

remainsection(其余代碼)Untilfalse（1）算法1Turn=i時Pi進(jìn)入臨界區(qū)，Turn=j時Pj進(jìn)入臨界區(qū)缺點：強(qiáng)制兩個進(jìn)程輪流進(jìn)入臨界區(qū)，造成資源利用不充分（2）算法2Pi:Repeat1Whileflag[j]doskip;3flag[i]:=ture;5criticalsection(臨界區(qū))flag[i]:=flase;Untilfalse

Pj:Repeat2

Whileflag[i]doskip;4flag[j]:=ture;6

criticalsection(臨界區(qū))flag[j]:=flase;Untilfalse

缺點：兩個進(jìn)程同時進(jìn)入臨界區(qū)（3）算法3：Pi:Repeat1flag[i]:=ture；3Whileflag[j]doskip;criticalsection(臨界區(qū))flag[i]:=flase;Untilfalse

Pj:Repeat2

flag[j]:=ture;

4

Whileflag[i]doskip;criticalsection(臨界區(qū))flag[j]:=flase;Untilfalse

缺點：兩個進(jìn)程無限期等待（4）算法4(petersun算法)，只針對雙進(jìn)程：Pi:Repeatflag[i]:=ture；turn:=j;While(flag[j]andturn=j)doskip;criticalsection(臨界區(qū))flag[i]:=flase;Untilfalse

LOCK和UNLOCK(低級通信原語)設(shè)公共變量x代表某個臨界資源的狀態(tài)

0資源可用

x=1資源正在使用四、同步工具進(jìn)程進(jìn)入臨界資源的操作:1:檢查X的值.X=1,表示資源正在使用,返回繼續(xù)進(jìn)行檢查;X=0,表示資源可以使用,X:=1(關(guān)鎖);2:進(jìn)入臨界區(qū),訪問臨界資源;3:釋放臨界資源,X:=0(開鎖).測試X:=1進(jìn)入臨界區(qū)退出臨界區(qū)X:=0返回X:=0X:=1繼續(xù)測試同步機(jī)制：用于控制進(jìn)程之間的同步與互斥。硬件指令：test-and-set（lock）功能表示如下：關(guān)鎖源語Lock(X)L:IfX=1thengotoLelseX:=1;開鎖源語UnLock(X)X:=0程序1初始化lock=0程序的其它部分代碼開鎖lock=0test-and-set（lock）訪問臨界資源代碼程序的其它部分lock=1lock=0程序2初始化lock=0程序的其它部分代碼開鎖lock=0test-and-set（lock）訪問臨界資源代碼程序的其它部分lock=1lock=0應(yīng)用舉例五、P/V操作、信號量P/V操作由P操作原語和V操作原語組成，意義是：在一個整型變量S上定義了兩個操作。信號量：整型變量S稱為信號量，僅能由P、V操作修改的整型變量。整型值S隊列指針NextP操作P操作：申請資源操作(1)

S:=S-1；(2)

如果S≥0，則表示有資源，該進(jìn)程繼續(xù)執(zhí)行；如果S<0，則表示已無資源，執(zhí)行原語的進(jìn)程被置成阻塞狀態(tài)，并使其在S信號量的隊列中等待，直至其他進(jìn)程在S上執(zhí)行V操作釋放它為止。

V操作：釋放資源操作(1)

S:=S+1；(2)

如果S>0，則該進(jìn)程繼續(xù)執(zhí)行；如果S≤0，則釋放S信號量隊列的排頭等待者并清除其阻塞狀態(tài)，即從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行V(S)者繼續(xù)執(zhí)行。

V操作注意:一、一個正在執(zhí)行P/V操作的進(jìn)程，不允許任何其它進(jìn)程中斷它的操作，既保證同時只有一個進(jìn)程對信號量S實施P或V操作。二、S>0:表示某類資源的可用數(shù)量；

S<0:表示無資源分配給請求的進(jìn)程，S的絕對值等于等待隊列的進(jìn)程數(shù)目。進(jìn)程A………P(S)將一項移入對列V(S)………..進(jìn)程B………P(S)從對列移出一項V(S)………..例(互斥)：對列的移出與加入(S=1)例(同步):進(jìn)程A:將信息輸入到緩沖區(qū)B1進(jìn)程B:從緩沖區(qū)B1中輸出信息S1:緩沖區(qū)B1中是否有可供處理的信息處理S1=0S2:緩沖區(qū)B1中的信息是被進(jìn)程B取走S2=0進(jìn)程A………讀消息到B1V(S1)P(S2)………..進(jìn)程B………P(S1)將B1內(nèi)容輸出到B2V(S2)………..S1=1喚醒BS2<0:阻塞A(B1滿)S1<0:阻塞BS1=0:輸出信息喚醒A兩個經(jīng)典的同步/互斥問題生產(chǎn)者/消費(fèi)者問題1、需輸出打印文件的用戶進(jìn)程和打印機(jī)管理進(jìn)程相對于打印機(jī)的管理進(jìn)程用戶進(jìn)程（生產(chǎn)著）、打印機(jī)管理進(jìn)程（消費(fèi)者）2、需讀入一磁盤文件的用戶進(jìn)程和磁盤管理進(jìn)程相對于磁盤管理進(jìn)程：用戶進(jìn)程（消費(fèi)者）、磁盤管理進(jìn)程（生產(chǎn)著）生產(chǎn)者/消費(fèi)者問題模型的抽象化與進(jìn)程分析生產(chǎn)者進(jìn)程臨界資源消費(fèi)者進(jìn)程信號量的設(shè)置Mutex=1 臨界資源Empty=n 空緩沖區(qū)的數(shù)目Full=0 滿緩沖區(qū)的數(shù)目滿空ij

環(huán)形緩沖區(qū)生產(chǎn)者/消費(fèi)者算法描述：varmutex，empty，full：psemaphore；i,j，goods：integer；buffer：array[0…n-1]ofitem；procedureproducer；生產(chǎn)者進(jìn)程

beginwhiletruedobeginproducenextproduct；

P(empty)；P(mutex)；

buffer(i):=product；i:=(i+1)mod(n)；

V(mutex)；V(full)；

endend；procedureconsumer；消費(fèi)者進(jìn)程

beginwhiletruedobegin

P(full)；

P(mutex)；

goods：=buffer(j)；

j:=(j+1)mod(n)；

V(mutex)；

V(empty)；

consumeproduct；

endend；beginseminitial(mutex.v，1；empty.v，n；full.v，0)；i：=j：=0；

cobeginproducer；

consumer；

coendend并發(fā)進(jìn)程文件寫者進(jìn)程讀者進(jìn)程讀者進(jìn)程...信號量的設(shè)置mutex=1臨界資源1wrt=1臨界資源2讀者計數(shù)器readcount寫者進(jìn)程互斥信號量互斥寫者互斥readcount讀者與寫者問題注意：對所有讀者，readcount是共享變量，要互斥訪問讀者與寫者問題算法描述

（無寫進(jìn)程時讀者可訪問、不考慮同時進(jìn)入、優(yōu)先考慮寫入）:Varmutex，wrt,psemaphore；readcount：integer；beginseminit(mutex.v，1；wrt.v，1)；Readcount：=0；cobeginprocedurereader；begin

P(mutex);readcount:=readcount+1；

ifreadcount=1thenP(wrt)；

V(mutex)；

readingisperforming；

P(mutex);readcount:=readcount-1；

ifreadcount=0thenV(wrt)；

V(mutex)；endprocedurewriter；

begin

P(wrt)；

writingisperforming；

V(wrt)；

end

coendend；開（關(guān)）鎖、P/V操作缺點：（1）臨界段操作的代碼以及進(jìn)入和退出臨界段的開（關(guān)）鎖操作代碼都要用戶編寫；（2）所有同步原語操作都分散在用戶編寫的各程序代碼中，由進(jìn)程來執(zhí)行，系統(tǒng)無法有效控制和管理這些同步原語操作（無法檢錯、糾錯）；（3）用戶在編程時發(fā)生的不正確使用同步原語的操作會帶來死鎖的后果。P（Mutex）臨界段P（Mutex）V（Mutex）臨界段P（Mutex）六、管程把分散的各同類臨界區(qū)集中起來。并為每個可共享資源設(shè)立一個專門的機(jī)構(gòu)來統(tǒng)一管理各進(jìn)程對該資源的訪問，這個專門機(jī)構(gòu)稱為管程。優(yōu)點：1、便于系統(tǒng)管理共享資源；2、保證互斥訪問。Hansen在并發(fā)PASCAL語言中首先引入管程，將它作為語言中的一個并發(fā)數(shù)據(jù)結(jié)構(gòu)類型。管程主要由兩部分組成l

局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)l

局部于該管程的若干過程，每個過程完成關(guān)于上述數(shù)據(jù)的某種規(guī)定操作。局部于管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)只能被該管程內(nèi)的過程所訪問。局部于管程內(nèi)的過程只能訪問該管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)管程的組成:對臨界資源的互斥實現(xiàn)方法（編譯）：管程每次只允許一個進(jìn)程訪問該管程內(nèi)的某個過程。避免死鎖：進(jìn)程訪問管程內(nèi)的某個過程被阻塞時，應(yīng)立即退出。條件變量：每個獨立的條件變量是和進(jìn)程需要等待的某種原因(或說條件)相聯(lián)系的，當(dāng)定義一個條件變量時，系統(tǒng)就建立一個相應(yīng)的等待隊列。關(guān)于條件變量有兩種操作：wait(x)和signal(x).其中x為條件變量。Wait（）：把調(diào)用者進(jìn)程掛在與x相應(yīng)的等待隊列上Signal（）：喚醒相應(yīng)等待隊列上的一個進(jìn)程生產(chǎn)者/消費(fèi)者管程描述producer:beginrepeat produceanitem; ringbuffer.put(item);untilfalse;endconsumer:begin repeat ringbuffer.get(item); consumetheitem; untilfalseendmonitorringbuffer；varrbuffer：array[0..n-1]ofitem；

k，nextempty，nextfull：integer；

empty，full：condition；procedureentryput(varproduct：item)；

beginifk=nthenwait(empty)；

rbuffer[nextempty]:=product；

k:=k+1；

nextempty:=（nextempty+1)mod（n）；

signal(full)；

end；procedureentryget(vargoods：item)；

begin

ifk=0thenwait(full)；

goods：=rbuffer[nextfull]；

k:=k-1；

nextfull:=(nextfull+1)mod（n）；

signal(empty)；

end；begink:=0；

nextempty：=0；nextfull：=0；end；滿空消息：進(jìn)程之間以不連續(xù)的成組方式發(fā)送的信息。消息緩沖區(qū)：包含有指向發(fā)送進(jìn)程的指針、指向消息接受進(jìn)程的指針、指向下一個消息緩沖區(qū)的指針、消息長度、消息內(nèi)容等信息的一個緩沖區(qū)。是進(jìn)程通信的基本單位。七、消息緩沖PCB(B):mq消息隊列mutex互斥指針sm同步指針Sender:ASize:5Text:HelloNptr:receive(b):發(fā)送者：A

長度：5

正文：Hellob

0:send(B,a):發(fā)送者：A

長度：5

正文：Helloa發(fā)送接收發(fā)送與接收消息過程進(jìn)程A進(jìn)程BReceive和sendProceduresend(receiver,a)Begin getbuf(a,size,i); i.sender:=a.sender; i.size:=a.size; i.text:=a.text; i.next:=0; getid(PCB,receiver,j);

P(j.mutext); insert(j.mq,i);

V(j.mutext);

V(j.sm);EndProcedurereceive(b)Begin

P(j.sm);

P(j.mutext); remove(j.mq,i);

V(j.mutext); b.sender:=i.sender; b.size:=i.size; b.text:=i.text; putbuf(i);End死鎖的原因和必要條件預(yù)防死鎖資源獨占(靜態(tài)分配）資源順序分配資源受控動態(tài)分配（避免死鎖）發(fā)現(xiàn)死鎖（死鎖檢測）解除死鎖八、死鎖

進(jìn)程P1

進(jìn)程P2

： ： 申請文件F 申請磁帶機(jī)Tr1

：申請磁帶機(jī)T … … r2:申請文件F

釋放磁帶機(jī)T …

釋放文件F 釋放文件F … 釋放磁帶機(jī)T

…死鎖例子簡單的死鎖例子FTP2P1請求已分配請求配分已進(jìn)程資源圖產(chǎn)生死鎖的原因和必要條件：原因：系統(tǒng)資源不足、進(jìn)程推進(jìn)順序不合適；必要條件互斥條件不剝奪條件請求和保持條件環(huán)路等待條件預(yù)防死鎖1、資源獨占靜止分配方法，預(yù)先分配所有資源給請求進(jìn)程，而且在請求的進(jìn)程在獲取資源運(yùn)行后一直處于獨占資源的狀態(tài)。（破壞互斥）缺點：資源利用率低、使用不方便。2、資源順序分配法對系統(tǒng)提供的資源按編號順序申請或釋放（破壞環(huán)路等待）缺點：資源利用率低、使用不方便?！?L2L1LjLmax申請釋放3、資源受控動態(tài)分配分配給要運(yùn)行的進(jìn)程所需要資源的最大申請量，動態(tài)分配。缺點：事先獲取資源的最大需求量。

資源

R1R2…Rj…RmP1a11a12…a1j…a1mP2a21a22…a2j…a2m…………………Piai1ai2…aij…aim…………………Pnan1an2

…anj…anm進(jìn)程死鎖檢測（發(fā)現(xiàn)）：資源分配表

進(jìn)程資源P1P

2…P

j…P

nR1

b11b21…b1j…bn1R2b12b22…b2j…bm2…………………Rjb1jb2j…bij…bnj…………………Rm

bm1bm2

…bmj…bmn進(jìn)程等待表:等待資源計數(shù)器C:引起相應(yīng)進(jìn)程被阻塞的資源數(shù)目。C1，C2，…….Cn未阻塞隊列L：未阻塞的進(jìn)程。檢測算法如下:(1)把未阻塞(Ci=0)的進(jìn)程Pi記錄在L表中(其全部資源請求已得到滿足的進(jìn)程)；(2)從L表中選擇一進(jìn)程，根據(jù)資源分配表S釋放分配給該進(jìn)程的所有資源；(3)由進(jìn)程等待表W依次檢查和修改需要該進(jìn)程釋放資源的每一個進(jìn)程的等待計數(shù)器Cj；(4)若Cj=0，則表示該進(jìn)程所請求的資源已得到滿足，不再阻塞，將Pj記入L表中；(5)再從L表中選取另一進(jìn)程，重復(fù)上述操作；(6)若所有的進(jìn)程都記入L表中，則系統(tǒng)初始狀態(tài)為非死鎖狀態(tài)，否則為死鎖狀態(tài)。避免死鎖：始終處于安全狀態(tài)。在避免死鎖方法中，允許進(jìn)程動態(tài)申請資源，系統(tǒng)在分配資源前，先計算資源分配的安全性。若安全則將資源分配給進(jìn)程，否則進(jìn)程等待。安全狀態(tài)：系統(tǒng)能按照某種順序（p2、p2、p3…）為進(jìn)程分配所需的資源，直至最大需求，使每個進(jìn)程都可以順利完成。此時系統(tǒng)處于安全狀態(tài)，（p2、p2、p3…）為安全序列。不安全狀態(tài)：若某一時刻中，系統(tǒng)不存在一個安全序列，則稱此時系統(tǒng)為不安全狀態(tài)。

進(jìn)入不安全狀態(tài)后，便可能進(jìn)入死鎖狀態(tài)。避免死鎖的本質(zhì)：系統(tǒng)不進(jìn)入不安全狀態(tài)。避免死鎖----安全狀態(tài)例

T0時刻系統(tǒng)資源狀態(tài)如下進(jìn)程最大需求已分配需求可用P1

553P2422…P392710避免死鎖進(jìn)程最大需求已分配需求可用P1

555P2422…P392710避免死鎖進(jìn)程最大需求已分配需求可用P1

5510P2422…P392710避免死鎖進(jìn)程最大需求已分配需求可用P1

5510P2422…P392710安全序列<p2、p2、p3>避免死鎖

---由安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)移

若在T0之后，又將一個資源分給了P3進(jìn)程最大需求已分配需求可用P1

552P2422…P393610利用銀行家算法避免死鎖

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個。

(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。

(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。

(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。上述三個矩陣間存在下述關(guān)系：Need[i,j]=Max[i,j]-Allocation[i,j]銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti[j]=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1)如果Requesti[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯，因為它所需要