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

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

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

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

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

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

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

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

具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型

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

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

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

作業(yè)名

作業(yè)類(lèi)型

資源要求

資源使用情況

優(yōu)先級(jí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2)搶占方式(PreemptiveMode)允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。優(yōu)點(diǎn):防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿(mǎn)足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但比非搶占方式調(diào)度所需付出的開(kāi)銷(xiāo)較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條：(1)優(yōu)先權(quán)原則。對(duì)一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程，使之執(zhí)行；或者說(shuō)，允許優(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)程)明顯的短時(shí)，將暫停當(dāng)前長(zhǎng)作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行；或者說(shuō)，短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長(zhǎng)作業(yè)(進(jìn)程)的處理機(jī)。(3)時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)?！?.4調(diào)度算法一、周轉(zhuǎn)時(shí)間：作業(yè)i從提交時(shí)刻Tsi到完成時(shí)刻Tei稱(chēng)為作業(yè)的周轉(zhuǎn)時(shí)間。Ti=Tei(完成時(shí)刻)-Tsi(提交時(shí)刻)

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

Ti=Twi+Tri

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

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

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

作業(yè)1:

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

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

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

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

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

帶權(quán)周轉(zhuǎn)時(shí)間W4＝120/20＝6平均周轉(zhuǎn)時(shí)間:T＝(T1+T2+T3+T4)/4平均帶權(quán)周轉(zhuǎn)時(shí)間: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è)號(hào)

1

2

3

4

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

2

3

4作業(yè)號(hào)1

2

34到達(dá)時(shí)間8.008.509.009.50開(kāi)始時(shí)間8.0010.0010.5010.60結(jié)束時(shí)間

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

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

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

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

1

2

3

4

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

2

3

4作業(yè)號(hào)1

3

42到達(dá)時(shí)間8.009.009.508.50開(kāi)始時(shí)間8.0010.0010.1010.30結(jié)束時(shí)間

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

4

4.6周轉(zhuǎn)時(shí)間：

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

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

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)時(shí)間+運(yùn)行時(shí)間

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)時(shí)間：

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

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

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

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

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

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

2)搶占式優(yōu)先權(quán)調(diào)度算法系統(tǒng)把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(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)度算法時(shí)，是每當(dāng)系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程i時(shí)，就將其優(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)度算法能更好地滿(mǎn)足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。2．優(yōu)先權(quán)的類(lèi)型

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

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

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

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

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

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

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

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

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

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

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

1

2

3

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

RP2=4，RP3=11，RP4=3.5

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

1

2

3

4作業(yè)號(hào)

1

3

2

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

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

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

例：

進(jìn)

程

P1

P2

P3

下一個(gè)CPU周期

24

3

3

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

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

：

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

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

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

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

多級(jí)反饋隊(duì)列調(diào)度算法

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

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

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

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

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

例：

進(jìn)程

下一個(gè)CPU周期

P1

9

P2

3

P3

6

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

T1=9

T2=12

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

W1=1

W2=4

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

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

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

W1=2

W2=1W3=1.5

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

T1=18T2=7

T3=17

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

W1=2

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

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

T1=18T2=6

T3=15

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

W1=2

W2=2

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

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

T1=9

T2=12

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

W1=1W2=4

W3=3

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

算

法

T

W

FIFO

13

2.7

SJF

10

1.5

時(shí)間片(4)

14

2.4

HRN

13

2.7

什么是多處理機(jī)系統(tǒng)多處理機(jī)操作系統(tǒng)的分類(lèi)多處理機(jī)系統(tǒng)調(diào)度策略§3.5多處理機(jī)調(diào)度一、多處理機(jī)系統(tǒng)：是一個(gè)具有兩個(gè)或多個(gè)處理機(jī)能相互進(jìn)行通信以協(xié)同一個(gè)大的給定問(wèn)題求解的計(jì)算機(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ā)生故障時(shí)能使用；還能提供系統(tǒng)結(jié)構(gòu)重組的能力，以支持系統(tǒng)的降級(jí)使用。因此，多處理機(jī)的調(diào)度策略也必須考慮到降級(jí)使用和結(jié)構(gòu)重組問(wèn)題。特點(diǎn)：1）有兩個(gè)或多個(gè)處理機(jī)2）共享主存或高速通信網(wǎng)絡(luò)3）共享輸入輸出子系統(tǒng)4）有單一完整的操作系統(tǒng)5）各級(jí)硬件和軟件相互作用

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

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

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

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

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

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

移動(dòng)式監(jiān)控系統(tǒng)(floatingsupervisor)(1)主從式指定一臺(tái)特定的處理機(jī)為主處理機(jī)，由它負(fù)責(zé)對(duì)全系統(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ù)時(shí),它們采用硬件中斷方式中斷處理機(jī)上執(zhí)行的進(jìn)程以要求主處理機(jī)提供服務(wù)。這種結(jié)構(gòu)的操作系統(tǒng)一般重組功能較差，因?yàn)橹挥兄魈幚頇C(jī)上執(zhí)行操作系統(tǒng)程序。如果主處理機(jī)失敗或發(fā)生不可恢復(fù)的錯(cuò)誤時(shí)，整系統(tǒng)將會(huì)癱瘓。(2)獨(dú)立監(jiān)控系統(tǒng)獨(dú)立監(jiān)控系統(tǒng)的監(jiān)控程序在每個(gè)處理機(jī)上執(zhí)行,每個(gè)處理機(jī)為自己的需要提供服務(wù)又互相通報(bào)執(zhí)行情況.一般來(lái)說(shuō),每個(gè)監(jiān)控程序能重新裝入或在不同的處理機(jī)上復(fù)制獨(dú)立的副本.

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

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

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

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

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

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

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

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

進(jìn)程名

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

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

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

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

資源清單

進(jìn)程起始地址

家族關(guān)系

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

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

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

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

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

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

remainsection(其余代碼)Untilfalse（1）算法1Turn=i時(shí)Pi進(jìn)入臨界區(qū)，Turn=j時(shí)Pj進(jìn)入臨界區(qū)缺點(diǎn)：強(qiáng)制兩個(gè)進(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

缺點(diǎn)：兩個(gè)進(jìn)程同時(shí)進(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

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

LOCK和UNLOCK(低級(jí)通信原語(yǔ))設(shè)公共變量x代表某個(gè)臨界資源的狀態(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ū),訪(fǎng)問(wèn)臨界資源;3:釋放臨界資源,X:=0(開(kāi)鎖).測(cè)試X:=1進(jìn)入臨界區(qū)退出臨界區(qū)X:=0返回X:=0X:=1繼續(xù)測(cè)試同步機(jī)制：用于控制進(jìn)程之間的同步與互斥。硬件指令：test-and-set（lock）功能表示如下：關(guān)鎖源語(yǔ)Lock(X)L:IfX=1thengotoLelseX:=1;開(kāi)鎖源語(yǔ)UnLock(X)X:=0程序1初始化lock=0程序的其它部分代碼開(kāi)鎖lock=0test-and-set（lock）訪(fǎng)問(wèn)臨界資源代碼程序的其它部分lock=1lock=0程序2初始化lock=0程序的其它部分代碼開(kāi)鎖lock=0test-and-set（lock）訪(fǎng)問(wèn)臨界資源代碼程序的其它部分lock=1lock=0應(yīng)用舉例五、P/V操作、信號(hào)量P/V操作由P操作原語(yǔ)和V操作原語(yǔ)組成，意義是：在一個(gè)整型變量S上定義了兩個(gè)操作。信號(hào)量：整型變量S稱(chēng)為信號(hào)量，僅能由P、V操作修改的整型變量。整型值S隊(duì)列指針NextP操作P操作：申請(qǐng)資源操作(1)

S:=S-1；(2)

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

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

S:=S+1；(2)

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

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

S<0:表示無(wú)資源分配給請(qǐng)求的進(jìn)程，S的絕對(duì)值等于等待隊(duì)列的進(jìn)程數(shù)目。進(jìn)程A………P(S)將一項(xiàng)移入對(duì)列V(S)………..進(jìn)程B………P(S)從對(duì)列移出一項(xiàng)V(S)………..例(互斥)：對(duì)列的移出與加入(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滿(mǎn))S1<0:阻塞BS1=0:輸出信息喚醒A兩個(gè)經(jīng)典的同步/互斥問(wèn)題生產(chǎn)者/消費(fèi)者問(wèn)題1、需輸出打印文件的用戶(hù)進(jìn)程和打印機(jī)管理進(jìn)程相對(duì)于打印機(jī)的管理進(jìn)程用戶(hù)進(jìn)程（生產(chǎn)著）、打印機(jī)管理進(jìn)程（消費(fèi)者）2、需讀入一磁盤(pán)文件的用戶(hù)進(jìn)程和磁盤(pán)管理進(jìn)程相對(duì)于磁盤(pán)管理進(jìn)程：用戶(hù)進(jìn)程（消費(fèi)者）、磁盤(pán)管理進(jìn)程（生產(chǎn)著）生產(chǎn)者/消費(fèi)者問(wèn)題模型的抽象化與進(jìn)程分析生產(chǎn)者進(jìn)程臨界資源消費(fèi)者進(jìn)程信號(hào)量的設(shè)置Mutex=1 臨界資源Empty=n 空緩沖區(qū)的數(shù)目Full=0 滿(mǎn)緩沖區(qū)的數(shù)目滿(mǎn)空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)程文件寫(xiě)者進(jìn)程讀者進(jìn)程讀者進(jìn)程...信號(hào)量的設(shè)置mutex=1臨界資源1wrt=1臨界資源2讀者計(jì)數(shù)器readcount寫(xiě)者進(jìn)程互斥信號(hào)量互斥寫(xiě)者互斥readcount讀者與寫(xiě)者問(wèn)題注意：對(duì)所有讀者，readcount是共享變量，要互斥訪(fǎng)問(wèn)讀者與寫(xiě)者問(wèn)題算法描述

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

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

局部于該管程的若干過(guò)程，每個(gè)過(guò)程完成關(guān)于上述數(shù)據(jù)的某種規(guī)定操作。局部于管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)只能被該管程內(nèi)的過(guò)程所訪(fǎng)問(wèn)。局部于管程內(nèi)的過(guò)程只能訪(fǎng)問(wèn)該管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)管程的組成:對(duì)臨界資源的互斥實(shí)現(xiàn)方法（編譯）：管程每次只允許一個(gè)進(jìn)程訪(fǎng)問(wèn)該管程內(nèi)的某個(gè)過(guò)程。避免死鎖：進(jìn)程訪(fǎng)問(wèn)管程內(nèi)的某個(gè)過(guò)程被阻塞時(shí)，應(yīng)立即退出。條件變量：每個(gè)獨(dú)立的條件變量是和進(jìn)程需要等待的某種原因(或說(shuō)條件)相聯(lián)系的，當(dāng)定義一個(gè)條件變量時(shí)，系統(tǒng)就建立一個(gè)相應(yīng)的等待隊(duì)列。關(guān)于條件變量有兩種操作：wait(x)和signal(x).其中x為條件變量。Wait（）：把調(diào)用者進(jìn)程掛在與x相應(yīng)的等待隊(duì)列上Signal（）：?jiǎn)拘严鄳?yīng)等待隊(duì)列上的一個(gè)進(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；滿(mǎn)空消息：進(jìn)程之間以不連續(xù)的成組方式發(fā)送的信息。消息緩沖區(qū)：包含有指向發(fā)送進(jìn)程的指針、指向消息接受進(jìn)程的指針、指向下一個(gè)消息緩沖區(qū)的指針、消息長(zhǎng)度、消息內(nèi)容等信息的一個(gè)緩沖區(qū)。是進(jìn)程通信的基本單位。七、消息緩沖PCB(B):mq消息隊(duì)列mutex互斥指針sm同步指針Sender:ASize:5Text:HelloNptr:receive(b):發(fā)送者：A

長(zhǎng)度：5

正文：Hellob

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

長(zhǎng)度：5

正文：Helloa發(fā)送接收發(fā)送與接收消息過(guò)程進(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ù)防死鎖資源獨(dú)占(靜態(tài)分配）資源順序分配資源受控動(dòng)態(tài)分配（避免死鎖）發(fā)現(xiàn)死鎖（死鎖檢測(cè)）解除死鎖八、死鎖

進(jìn)程P1

進(jìn)程P2

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

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

釋放磁帶機(jī)T …

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

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

資源

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

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

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

T0時(shí)刻系統(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之后，又將一個(gè)資源分給了P3進(jìn)程最大需求已分配需求可用P1

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

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

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

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

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

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

(1)如果Requesti[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰?/p>