計(jì)算機(jī)操作系統(tǒng)-第3章進(jìn)程和處理機(jī)管理課件

計(jì)算機(jī)操作系統(tǒng)劉騰紅主編ComputerOperatingSystem第3章進(jìn)程和處理機(jī)管理要求學(xué)生掌握程序的順序執(zhí)行和并發(fā)執(zhí)行；進(jìn)程的定義、特點(diǎn)及狀態(tài)變遷；進(jìn)程的管理；線程的概念、類別；進(jìn)程間的同步與互斥；進(jìn)程通信；死鎖產(chǎn)生的原因與解除方法；處理機(jī)、進(jìn)程和作業(yè)的調(diào)度方法；最后還要了解WindowsXP的進(jìn)程和線程管理。第3章進(jìn)程和處理機(jī)管理3.1進(jìn)程的基本概念

3.2進(jìn)程管理

3.3線程的概念3.4進(jìn)程間的同步與互斥3.5進(jìn)程通信

3.6死鎖3.7處理機(jī)調(diào)度3.8WindowsXP的進(jìn)程和線程管理3.1.2程序并發(fā)執(zhí)行

1.程序的并發(fā)執(zhí)行如圖3-2，I3、C2、P1是并發(fā)執(zhí)行的，則使用下面的語(yǔ)句描述：cobegin I3;C2;P1;coend;3.1進(jìn)程的基本概念I(lǐng)2C2P2I3C3P3I4C4P4I1C1P1圖3-2程序段并發(fā)執(zhí)行2.程序并發(fā)執(zhí)行的特點(diǎn)(1)失去了程序的封閉性程序之間的相互制約關(guān)系(間接關(guān)系和直接關(guān)系)導(dǎo)致程序“執(zhí)行---暫停---執(zhí)行”，即程序的執(zhí)行具有間斷性。(2)

通信性:如圖3-3(3)

獨(dú)立性3.1進(jìn)程的基本概念BCA圖3-3并發(fā)進(jìn)程間的通信3.1.3進(jìn)程描述

1.進(jìn)程定義最能反映進(jìn)程實(shí)質(zhì)的定義有：1）進(jìn)程是程序的一次執(zhí)行活動(dòng)；2）進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算；3）進(jìn)程是一個(gè)程序在對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)上的進(jìn)行的操作；

3.1進(jìn)程的基本概念1.進(jìn)程定義進(jìn)程和程序的聯(lián)系和區(qū)別:1）程序是指令的有序集合，其本身沒(méi)有任何運(yùn)行的含義，它是一個(gè)靜態(tài)的概念。進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過(guò)程，它是一個(gè)動(dòng)態(tài)的概念。2）進(jìn)程具有并行特征，能與其它進(jìn)程并行地活動(dòng)；3.1進(jìn)程的基本概念2.進(jìn)程類型

(1)系統(tǒng)進(jìn)程和用戶進(jìn)程，兩者的區(qū)別:1)系統(tǒng)進(jìn)程被分配一個(gè)初始的資源集合，其可以獨(dú)占或按最高優(yōu)先權(quán)限優(yōu)先使用這些資源。但用戶進(jìn)程必須通過(guò)系統(tǒng)服務(wù)請(qǐng)求來(lái)申請(qǐng)資源，并競(jìng)爭(zhēng)資源2）用戶進(jìn)程不能直接完成I/O操作，而系統(tǒng)進(jìn)程可以做顯示的、直接的I/O操作3）系統(tǒng)進(jìn)程在管態(tài)下運(yùn)行，而用戶進(jìn)程在目態(tài)下運(yùn)行(2)計(jì)算進(jìn)程和I/O進(jìn)程3.1進(jìn)程的基本概念3.進(jìn)程的特征和利弊特征：

1）動(dòng)態(tài)性

2）并發(fā)性

3）獨(dú)立性4）異步性/間斷性

5）結(jié)構(gòu)特征

每個(gè)進(jìn)程都有進(jìn)程控制塊PCB：其包含描述進(jìn)程和控制信息引入進(jìn)程增加開(kāi)銷：空間開(kāi)銷和時(shí)間開(kāi)銷3.1進(jìn)程的基本概念5.進(jìn)程描述——進(jìn)程控制塊PCB1)PCB的作用：標(biāo)識(shí)進(jìn)程存在的唯一實(shí)體2）進(jìn)程控制塊的內(nèi)容進(jìn)程控制塊PCB常用的信息如表3-1。3）PCB的組織方式a)鏈接方式如圖3-5b)索引方式如圖3-63.1進(jìn)程的基本概念進(jìn)程標(biāo)識(shí)符進(jìn)程當(dāng)前狀態(tài)現(xiàn)場(chǎng)保護(hù)區(qū)程序和數(shù)據(jù)地址進(jìn)程優(yōu)先級(jí)資源清單進(jìn)程通信信息互斥和同步機(jī)構(gòu)家族聯(lián)系鏈接字總鏈指針表3-1PCB信息表3-1PCB信息3.1進(jìn)程的基本概念表3-1PCB信息PCB12PCB23PCB34PCB413PCB56PCB67PCB79PCB8PCB910PCB10PCB1112PCB12iPCB13……就緒指針執(zhí)行指針等待指針空閑指針圖3-5按鏈接方式組織PCB3.1進(jìn)程的基本概念就緒指針等待指針空閑指針1234135679101112PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9PCB10PCB11PCB12PCB13索

引

表圖3-6按索引方式組織PCB3.2.1進(jìn)程創(chuàng)建原語(yǔ)創(chuàng)建原語(yǔ)描述如下：3.2進(jìn)程管理算法：create輸入：新進(jìn)程的符號(hào)名，優(yōu)先級(jí)，開(kāi)始執(zhí)行地址輸出：新創(chuàng)建進(jìn)程的內(nèi)部標(biāo)識(shí)符PID{在總鏈隊(duì)列上查找有無(wú)同名的進(jìn)程；if(有同名進(jìn)程)return（錯(cuò)誤碼）/*帶錯(cuò)誤碼返回*/在空閑PCB隊(duì)列申請(qǐng)一個(gè)空閑的PCB結(jié)構(gòu)；if(無(wú)空PCB結(jié)構(gòu))return（錯(cuò)誤碼）；/*帶錯(cuò)誤碼返回*/用參數(shù)填充PCB內(nèi)容；置進(jìn)程為就緒狀態(tài)；將新進(jìn)程的PCB插入到就緒隊(duì)列；將新進(jìn)程的PCB插入到總鏈隊(duì)列中；設(shè)置進(jìn)程的家族關(guān)系；return（新進(jìn)程PID）；}/*create(name,priority,start-addr)*/3.2.2進(jìn)程撤消原語(yǔ)撤消原語(yǔ)Kill操作如下：3.2進(jìn)程管理voidkill輸入：進(jìn)程標(biāo)識(shí)符PID輸出：無(wú){

由參數(shù)PID查找到當(dāng)前進(jìn)程的PCB；釋放本進(jìn)程所占用的資源給父進(jìn)程；將該進(jìn)程從總鏈隊(duì)列中摘除；釋放此PCB結(jié)構(gòu)；釋放所占用的資源；轉(zhuǎn)進(jìn)程調(diào)度程序；}/*kill*/3.2.3進(jìn)程等待原語(yǔ)等待原語(yǔ)操作過(guò)程如下：3.2進(jìn)程管理voidsusp(chan)輸入：chan/*等待的事件（等待原因）*/{

保護(hù)現(xiàn)行進(jìn)程CPU現(xiàn)場(chǎng)到PCB結(jié)構(gòu)中；

置該進(jìn)程為“等待/阻塞”態(tài)；

將該進(jìn)程PCB插入到等chan的等待隊(duì)列；

轉(zhuǎn)進(jìn)程調(diào)度；}/*susp(chan)*/3.2.5其他原語(yǔ)1.進(jìn)程延遲原語(yǔ)和延遲喚醒原語(yǔ)

延遲原語(yǔ)的功能是：將需要延遲的進(jìn)程PCB結(jié)構(gòu)加入到延遲隊(duì)列，當(dāng)延遲時(shí)間到來(lái)時(shí)，由延遲喚醒進(jìn)程（系統(tǒng)進(jìn)程）把它喚醒2.進(jìn)程掛起原語(yǔ)和進(jìn)程激活原語(yǔ)進(jìn)程的掛起狀態(tài)是一種靜止?fàn)顟B(tài)，它分為掛起就緒和掛起等待。3.2進(jìn)程管理3.3.1線程的概念線程是比進(jìn)程更小的活動(dòng)單位，它是進(jìn)程的一個(gè)執(zhí)行路徑。線程可以這樣描述：1）線程是進(jìn)程中的一條執(zhí)行路徑2）它有自己的私用堆棧和處理機(jī)執(zhí)行環(huán)境（尤其是處理器寄存器）3）它與父進(jìn)程共享分配給父進(jìn)程的主存4）它是由單個(gè)進(jìn)程所創(chuàng)建的眾多線程中的一個(gè)線程3.3線程的概念3.3.2線程與進(jìn)程的比較1.調(diào)度：把線程作為調(diào)度和分派的基本單位，而把進(jìn)程作為資源擁有的基本單位2.并發(fā)性：不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)線程之間也可并發(fā)執(zhí)行3.擁有資源：進(jìn)程是擁有資源的一個(gè)獨(dú)立單位，線程不擁有系統(tǒng)資源，但可訪問(wèn)隸屬于進(jìn)程的全部資源。4.系統(tǒng)開(kāi)銷：由于在創(chuàng)建或撤消進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，導(dǎo)致系統(tǒng)的開(kāi)銷將顯著地大于在創(chuàng)建或撤銷線程時(shí)的開(kāi)銷。3.3線程的概念3.4.1進(jìn)程間的制約關(guān)系1.資源共享

互斥共享和同時(shí)訪問(wèn)2.進(jìn)程合作進(jìn)程相互合作和通信，共同完成一個(gè)任務(wù)3.4.2進(jìn)程互斥1.互斥的概念互斥共享的資源：物理設(shè)備和軟件資源

相關(guān)概念:臨界區(qū)和臨界資源3.4進(jìn)程間的同步與互斥3.4.2進(jìn)程互斥2.鎖及其操作置鎖信號(hào)為1稱為上鎖原語(yǔ)（lock），置鎖信號(hào)為0稱為開(kāi)鎖原語(yǔ)(unlock)，代碼如下所示3.4進(jìn)程間的同步與互斥上鎖原語(yǔ)開(kāi)鎖原語(yǔ)voidlock(鎖變量w){

test:if(w為1)

gototest/*測(cè)試鎖位的值*/

else

w=1;/*上鎖*/

}/*lock(w)*/

voidunlock(鎖變量w){

w=0;/*開(kāi)鎖*/

}/*unlock(w)*/與圖3-7相應(yīng)的進(jìn)程互斥代碼如下：3.4進(jìn)程間的同步與互斥main(){ intw=0;//系統(tǒng)初啟時(shí)置鎖狀態(tài)

cobegin

ppa();//進(jìn)程A

ppb();//進(jìn)程B

coend}ppa()//進(jìn)程A{……;

lock(w);

進(jìn)程A的臨界區(qū)CSa；

unlock(w);

……;}ppb()//進(jìn)程B{……;

lock(w);

進(jìn)程B的臨界區(qū)CSb；

unlock(w);

……;}3.4.3信號(hào)燈和P、V操作1.信號(hào)燈的概念1965年荷蘭Dijkstra提出的進(jìn)程同步工具

信號(hào)燈表示:二元組（s,q）其中：s具有非負(fù)初值的整型變量，代表資源實(shí)體或并發(fā)進(jìn)程的狀態(tài);q是一個(gè)初始狀態(tài)為空的等待隊(duì)列3.4進(jìn)程間的同步與互斥3.4.3信號(hào)燈和P、V操作2.P、V操作原語(yǔ)系統(tǒng)一般提供P、V操作原語(yǔ)來(lái)修改信號(hào)燈的值如果信號(hào)燈用s表示，則P操作記為P（s），V操作記為V（s）1)P操作:對(duì)信號(hào)燈進(jìn)行減1操作，再根據(jù)信號(hào)燈的值對(duì)調(diào)用P操作的進(jìn)程進(jìn)行相應(yīng)處理2)V操作:對(duì)信號(hào)燈進(jìn)行加1操作

3.4進(jìn)程間的同步與互斥3.4.3信號(hào)燈和P、V操作

3.4進(jìn)程間的同步與互斥voidp(變量s)//變量s為信號(hào)燈{

s--;if(s<0){//進(jìn)程進(jìn)入相應(yīng)的等待隊(duì)列保留調(diào)用進(jìn)程CPU現(xiàn)場(chǎng)；將該進(jìn)程進(jìn)入s的等待隊(duì)列；置“等待”狀態(tài)；轉(zhuǎn)進(jìn)程調(diào)度；}}/*p(s)*/1）P操作過(guò)程voidv(變量s)//變量s為信號(hào)燈{

s++;if(s<=0){移出s等待隊(duì)列首元素；將該進(jìn)程入就緒隊(duì)列；置“就緒”狀態(tài)；}/*v(s)*/2）V操作過(guò)程3.4.3信號(hào)燈和P、V操作3.使用P、V操作實(shí)現(xiàn)進(jìn)程互斥

舉例1:說(shuō)明兩個(gè)進(jìn)程使用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥設(shè)系統(tǒng)中同類的互斥資源只有1個(gè)，則：1）信號(hào)燈的初值為1，表示資源可用，2）信號(hào)燈的值小于等于0，表示資源已經(jīng)被進(jìn)程占用，則另一進(jìn)程只能等待。相關(guān)代碼見(jiàn)下頁(yè)圖表

3.4進(jìn)程間的同步與互斥3.4進(jìn)程間的同步與互斥main(){

intmutex=1;//互斥信號(hào)燈

cobegin

pa();//進(jìn)程A

pb();//進(jìn)程B

coend}pa();//進(jìn)程A{ ……;

P(mutex)；

進(jìn)程A的臨界區(qū)CSa;V(mutex)；……;}pb();//進(jìn)程B{ ……;

P(mutex)；

進(jìn)程B的臨界區(qū)CSb;V(mutex)；……;}3.4.3信號(hào)燈和P、V操作3.使用P、V操作實(shí)現(xiàn)進(jìn)程互斥舉例2:假設(shè)系統(tǒng)中同類型的臨界資源有多個(gè)，則信號(hào)燈的初始值應(yīng)設(shè)為n信號(hào)燈mutex的值的意義如下：1）初始信號(hào)燈mutex>0，表示系統(tǒng)中同類臨界資源的數(shù)目有mutex個(gè)；2）操作中mutex>0，表示可用的同類臨界資源的數(shù)目為mutex；

3.4進(jìn)程間的同步與互斥3）操作中mutex<0，則表示臨界資源已經(jīng)用完，在等待隊(duì)列中有|mutex|個(gè)進(jìn)程。

4）mutex=0，n個(gè)臨界資源正好用完信號(hào)燈mutex取值范圍：1）如果系統(tǒng)中只有一個(gè)臨界資源，被兩個(gè)進(jìn)程共享，則信號(hào)燈mutex的取值范圍為：1、0、-1三個(gè)值。2）當(dāng)用mutex實(shí)現(xiàn)n個(gè)進(jìn)程互斥共享一個(gè)臨界資源時(shí)，其值的范圍為1～-（n-1）

3.4進(jìn)程間的同步與互斥3.4進(jìn)程間的同步與互斥PaPcPbsfPcPbPasf緩沖區(qū)buffcpiop圖3-9計(jì)算進(jìn)程和打印進(jìn)程之間的同步(a)進(jìn)程同步例1(b)進(jìn)程同步例2圖3-8進(jìn)程合作例子3.4.4進(jìn)程同步1.進(jìn)程同步概念合作進(jìn)程的兩種同步關(guān)系：1）在執(zhí)行次序上的同步；2）共享緩沖的同步

3.4.4進(jìn)程同步2.使用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步

舉例1:如圖3-8（a），設(shè)兩個(gè)同步信號(hào)燈Sb、Sc，分別表示進(jìn)程Pb、Pc是否可以開(kāi)始行，Sb、Sc的初始值均為0，表示進(jìn)程Pb、Pc還不能開(kāi)始執(zhí)行，如果為1，則進(jìn)程Pb、Pc就可以開(kāi)始執(zhí)行。進(jìn)程Pb、Pc中的P操作起測(cè)試作用，而進(jìn)程Pa中的Ｖ操作相當(dāng)于喚醒

3.4進(jìn)程間的同步與互斥圖3-8（a）中的三個(gè)進(jìn)程同步的代碼main(){

intSb=0;intSc=0;

cobegin

Pa();

Pb();

Pc();

coend}Pa()//進(jìn)程Pa

{ ……;

V(Sb);

V(Sc);}Pb()//進(jìn)程Pb{ P(Sb);

……;}Pc()//進(jìn)程Pc{ P(Sc);

……;}main(){

intSa=0;

cobegin

Pa();

Pb();

Pc(); coend}Pa()//進(jìn)程Pa

{ ……;

V(Sa);

V(Sa);}Pb()//進(jìn)程Pb{ P(Sa);

……;}Pc()//進(jìn)程Pc{ P(Sa);

……;}2.使用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步

舉例2：根據(jù)圖3-9計(jì)算進(jìn)程和打印進(jìn)程之間的同步的規(guī)則，設(shè)置兩個(gè)信號(hào)燈Sa、Sb，信號(hào)燈意義如下：1）信號(hào)燈Sa表示緩沖中有無(wú)數(shù)據(jù)，其初值為0，即緩沖中沒(méi)有數(shù)據(jù)。2）信號(hào)燈Sb用來(lái)表示緩沖區(qū)有無(wú)空位置存放計(jì)算進(jìn)程的計(jì)算結(jié)果，其初值為1，表示緩沖中有空的位置。3.4進(jìn)程間的同步與互斥計(jì)算進(jìn)程cp和打印進(jìn)程iop的同步代碼main{ intSa=0;//緩沖中沒(méi)有數(shù)據(jù)

intSb=1;//緩沖中有空位置

cobegin

cp();

iop();

coend}cp()//計(jì)算進(jìn)程{

while(計(jì)算沒(méi)有完成){

計(jì)算一個(gè)結(jié)果數(shù)據(jù)；

P(Sb);

將結(jié)果數(shù)據(jù)送到緩沖區(qū)；

V(Sa); }}iop()//打印進(jìn)程{

while(打印工作沒(méi)有完成){

P(Sa);

將結(jié)果數(shù)據(jù)從緩沖區(qū)中取出；

V(Sb);

在打印機(jī)上輸出；}}3.4.4進(jìn)程同步3.生產(chǎn)者和消費(fèi)者問(wèn)題（如圖3-10所示）解決：設(shè)置兩個(gè)信號(hào)燈full（表示緩沖中存放的產(chǎn)品的數(shù)量，初始值為0）和empty（表示緩沖中空位置的數(shù)量，初始值為n）設(shè)置一個(gè)互斥信號(hào)燈mutex，其初始值為13.4進(jìn)程間的同步與互斥c1c2ckp1p2pm圖3-10生產(chǎn)者——消費(fèi)者問(wèn)題緩沖區(qū)使用信號(hào)燈解決消費(fèi)者問(wèn)題的代碼main(){ full=0；//緩沖區(qū)中存放的產(chǎn)品數(shù)量

empty=n；//緩沖區(qū)空位置的數(shù)量

mutex=1；//對(duì)有界緩沖區(qū)進(jìn)行操作的互斥信號(hào)燈cobeginProducer()；Consumer()；coend}Producer(){

while(生產(chǎn)未完成){生產(chǎn)一個(gè)產(chǎn)品；P(empty)；P(mutex)；送一個(gè)產(chǎn)品到有界緩沖區(qū)；V(mutex)；V(full)；}}Consumer(){

while(還要繼續(xù)消費(fèi)){P(full)；P(mutex)；從有界緩沖區(qū)中取產(chǎn)品；V(mutex)；V(empty)；消費(fèi)一個(gè)產(chǎn)品；

}}3.4.4進(jìn)程同步4.讀者——寫(xiě)者問(wèn)題對(duì)共享資源的讀寫(xiě)操作的同步限制條件是：1)允許任意多的進(jìn)程同時(shí)讀；2)一次只允許一個(gè)寫(xiě)進(jìn)程進(jìn)行寫(xiě)操作；3)如果有一個(gè)進(jìn)程正在進(jìn)行寫(xiě)操作，不允許任何讀進(jìn)程進(jìn)行讀操作。設(shè)置兩個(gè)互斥信號(hào)燈Rmutex、Wmutex和一個(gè)公共計(jì)數(shù)變量Rcount解決“讀者---寫(xiě)者”問(wèn)題的同步代碼如下頁(yè)3.4進(jìn)程間的同步與互斥main(){

intRcount=0;

intRmutex=1;

intWmutex=1;cobegin

reader();

writer();coend}reader()//讀者進(jìn)程{ while(1){

P(Rmutex);

if(Rcount==0)P(Wmutex);

Rcount++;

V(Rmutex);

……;

完成讀操作;

……;

P(Rmutex);

Rcount--;

if((Rcount==0)V(Wmutex);

V(Rmutex); }}writer()//寫(xiě)者進(jìn)程{

while(1){

P(Wmutex);

完成寫(xiě)操作；

V(Wmutex); }}3.5.1進(jìn)程通信類型1)

共享存儲(chǔ)器系統(tǒng)a）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式b）基于共享存儲(chǔ)區(qū)域的通信方式2)消息系統(tǒng)進(jìn)程間的信息交換以消息或者報(bào)文為單位消息系統(tǒng)有兩種通信方式：a）直接通信方式

原語(yǔ)：send(接收者ID，消息)和receive(發(fā)送者ID，消息)3.5進(jìn)程通信b）間接通信方式如圖3-11，進(jìn)程間有中間實(shí)體（信箱）3.5進(jìn)程通信發(fā)送進(jìn)程接收進(jìn)程信箱頭信箱1信箱2圖3-11間接通信方式3)

利用共享文件（管道）的通信方式

發(fā)送進(jìn)程接收進(jìn)程圖3-12利用共享文件（管道）通信3.5.2消息系統(tǒng)---進(jìn)程直接通信例子消息緩沖區(qū)結(jié)構(gòu)：Sptr、Nptr、Size、Text消息緩沖區(qū)長(zhǎng)度=消息長(zhǎng)度+33.5進(jìn)程通信發(fā)送進(jìn)程id=5接收進(jìn)程id=5…send(m);…id:6size:5text:hello…接收進(jìn)程pcb中的hptrSptr:4Nptr:Size:3Text:byeSptr:5Nptr:nullSize:5Text:hello…receive(n,sid);…id:4size:3text:bye…發(fā)送進(jìn)程地址空間接收進(jìn)程地址空間圖3-13消息緩沖通信3.5.2消息系統(tǒng)---進(jìn)程直接通信例子發(fā)送原語(yǔ)算法描述如下：3.5進(jìn)程通信voidsend(發(fā)送區(qū)首址m){從發(fā)送區(qū)id域得接收進(jìn)程id號(hào)；以此id號(hào)得接收進(jìn)程pcb的消息隊(duì)列頭；從發(fā)送區(qū)size域得緩沖區(qū)大?。簧暾?qǐng)一個(gè)消息緩沖區(qū)area；//建立新的消息緩沖區(qū)以此大小加上緩沖區(qū)頭得area；發(fā)送進(jìn)程id送area的sptr域；緩沖區(qū)大小送area的size域；發(fā)送區(qū)的text送area的text域；置area的勾鏈字為鏈尾標(biāo)記；

p(mutex);//封鎖消息隊(duì)列將area入消息隊(duì)列；

v(mutex);//解鎖消息隊(duì)列

v(Si);//與接收進(jìn)程同步}3.5.2消息系統(tǒng)---進(jìn)程直接通信例子接收原語(yǔ)算法描述如下：3.5進(jìn)程通信voidreceive(接收區(qū)首址n，發(fā)送進(jìn)程號(hào)){p(Si);//有無(wú)消息可取p(mutex);//封鎖消息隊(duì)列在消息隊(duì)列找到發(fā)送者為sid的消息；從消息隊(duì)列中摘下此消息緩沖區(qū)area;v(mutex);//解鎖消息隊(duì)列area的sptr送接收區(qū)的id域；//將消息緩沖區(qū)的信息復(fù)制到接收區(qū)area的size送接收區(qū)的size域；area的text送接收區(qū)的text域；釋放area給存貯管理模塊；}3.6.1產(chǎn)生死鎖的原因和必要條件1.競(jìng)爭(zhēng)資源引起死鎖用資源—進(jìn)程有向圖說(shuō)明死鎖，如圖3-14

臨時(shí)性資源引起死鎖。如圖3-15所示3.6死鎖R1R2P1P2圖3-14I/O設(shè)備共享時(shí)的死鎖圖3-15進(jìn)程之間通信時(shí)的死鎖S1S3P1P2P3S22.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖圖3-14的兩種不同的進(jìn)程推進(jìn)順序：

（1）合法順序，不會(huì)產(chǎn)生死鎖P1：…;release(S1);request(S3);…P2：…;release(S2);request(S1);…P3：…;release(S3);request(S2);…

（2）非法順序，會(huì)產(chǎn)生死鎖P1：…;request(S3);release(S1);…P2：…;request(S1);release(S2);…P3：…;request(S2);release(S3);…3.6死鎖3.6.1產(chǎn)生死鎖的原因和必要條件３.產(chǎn)生死鎖的四個(gè)必要條件1)互斥條件2)不剝奪條件3)部分分配4)環(huán)路條件：存在進(jìn)程—資源的循環(huán)鏈4.解決死鎖的基本方法1）預(yù)防死鎖

；2）避免死鎖3）檢測(cè)死鎖；4）解除死鎖3.6死鎖3.6.2預(yù)防死鎖1.否定條件二---不剝奪條件規(guī)定：一個(gè)已經(jīng)占有了某些資源的進(jìn)程，若申請(qǐng)不到新的資源時(shí)，就釋放已經(jīng)占有的資源，以后再需要時(shí)重新申請(qǐng)。

缺點(diǎn)：要付出很大代價(jià)，增加了系統(tǒng)開(kāi)銷，降低系統(tǒng)吞吐量2.否定條件三---部分分配在分配資源時(shí)，只要有一個(gè)資源要求得不到滿足，則該進(jìn)程就不能得到任何資源3.6死鎖3.6.2預(yù)防死鎖2.否定條件三---部分分配缺點(diǎn)：方法簡(jiǎn)單、容易實(shí)現(xiàn)；但資源嚴(yán)重浪費(fèi)3.否定條件四---環(huán)路條件資源編號(hào)；所有進(jìn)程對(duì)資源的請(qǐng)求必須按照資源序號(hào)遞增的次序提出缺點(diǎn)：1）限制了新資源的增加；2）會(huì)發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定的順序不同的情況，造成資源浪費(fèi)；3）限制了用戶簡(jiǎn)單、自由地編程。3.6死鎖3.6.3避免死鎖通過(guò)判斷資源分配的安全性分配安全狀態(tài)：只指系統(tǒng)按照某種進(jìn)程順序（如P1、P2、…、Pn）為每個(gè)進(jìn)程分配資源，直至最大需求，每個(gè)進(jìn)程都可以順利完成。若不存在這樣的安全序列，則稱系統(tǒng)處于不安全狀態(tài)

銀行算法是Dijkstra.E.W1968年提出的一種避免死鎖的方法，滿足資源的最大需求量缺點(diǎn)：過(guò)于謹(jǐn)慎以及花費(fèi)開(kāi)銷較大3.6死鎖3.6.3避免死鎖下面用例子說(shuō)明系統(tǒng)的安全狀態(tài)和不安全狀態(tài)假如系統(tǒng)有12臺(tái)磁帶機(jī)。有三個(gè)進(jìn)程P1、P2和P3，分別要求10臺(tái)、4臺(tái)和9臺(tái)磁帶機(jī)。設(shè)在時(shí)刻T0進(jìn)程P1、P2和P3分別已經(jīng)獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)。

進(jìn)程

最大需求

已分配

可用P1 10 5 3P2 4 2P3 9 23.6死鎖3.6.4死鎖的檢測(cè)與恢復(fù)發(fā)現(xiàn)死鎖的原理：考查某一時(shí)刻系統(tǒng)狀態(tài)是否合理檢測(cè)死鎖算法的基本思想死鎖檢測(cè)的時(shí)機(jī)：1)每次分配后；2)定期檢查

排除死鎖的實(shí)用方法：1)把陷于死鎖的全部進(jìn)程一律撤消；2)逐個(gè)作廢死鎖進(jìn)程至死鎖不再存在；3)逐個(gè)強(qiáng)迫搶占資源至死鎖不再存在3.6死鎖3.7.1處理機(jī)的多級(jí)調(diào)度1.處理機(jī)調(diào)度的功能

1）確定數(shù)據(jù)結(jié)構(gòu)

2）制訂調(diào)度策略（調(diào)度原則）

3）給出調(diào)度算法

4）具體的實(shí)施處理機(jī)分派2.批處理系統(tǒng)中的處理機(jī)調(diào)度處理機(jī)調(diào)度分類：作業(yè)調(diào)度和進(jìn)程調(diào)度3.多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度4.多線程操作系統(tǒng)中的處理機(jī)調(diào)度3.7處理機(jī)調(diào)度3.7.2進(jìn)程調(diào)度進(jìn)程調(diào)度（也稱CPU調(diào)度）:按照某種調(diào)度算法從就緒隊(duì)列中選取進(jìn)程分配CPU

衡量各種調(diào)度算法性能優(yōu)劣的指標(biāo):

1）CPU利用率——主要目標(biāo)CPU利用率=CPU利用的時(shí)間/開(kāi)機(jī)運(yùn)行的總時(shí)間

2）等待時(shí)間3）響應(yīng)時(shí)間4）I/O設(shè)備的利用率5）“時(shí)空”代價(jià)3.7處理機(jī)調(diào)度3.7.2進(jìn)程調(diào)度進(jìn)程調(diào)度方式：剝奪調(diào)度和非剝奪調(diào)度下面介紹幾種常見(jiàn)的進(jìn)程調(diào)度方法1.先來(lái)先服務(wù)（Firstcomefirstservice,FCFS）2.輪轉(zhuǎn)法（RR，RoundRobin）將CPU的處理時(shí)間分成固定大小的時(shí)間片，進(jìn)程時(shí)間片內(nèi)輪轉(zhuǎn)執(zhí)行

關(guān)鍵問(wèn)題：如何確定時(shí)間片的大小

時(shí)間片q=RT/Nmax3.7處理機(jī)調(diào)度將考慮下面3個(gè)進(jìn)程，它們按1，2，3的順序處于就緒隊(duì)列中：進(jìn)程下一個(gè)CPU周期

P124P23P33

3.7處理機(jī)調(diào)度圖3-16執(zhí)行過(guò)程1圖3-17執(zhí)行過(guò)程2FCFS調(diào)度算法其他調(diào)度算法2.輪轉(zhuǎn)法設(shè)有如下4個(gè)就緒進(jìn)程：進(jìn)程下一個(gè)CPU周期

P16P23P31P47

則如圖3-18所示3.7處理機(jī)調(diào)度ATT01234567q圖3-18平均周轉(zhuǎn)時(shí)間ATT與時(shí)間片q之間的關(guān)系3.7.2進(jìn)程調(diào)度3.多級(jí)反饋輪轉(zhuǎn)法思想：不同級(jí)別的就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的為第一級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別降低，時(shí)間片加大

例如考慮由3個(gè)隊(duì)列組成的多級(jí)隊(duì)列調(diào)度。3個(gè)隊(duì)列的編號(hào)分別為0,1,2，如圖3-193.7處理機(jī)調(diào)度3.7.2進(jìn)程調(diào)度4.優(yōu)先數(shù)法（Priority）思想：按進(jìn)程的優(yōu)先級(jí)確定調(diào)度優(yōu)先權(quán)優(yōu)先級(jí)確定方法：（1）靜態(tài)法：可按進(jìn)程類型、資源的要求、用戶要求指定（2）動(dòng)態(tài)法：原則是合理地分配CPU時(shí)間、緊急的程序優(yōu)先3.7處理機(jī)調(diào)度實(shí)例解釋：假設(shè)就緒狀態(tài)有4個(gè)進(jìn)程，每個(gè)進(jìn)程所需運(yùn)行時(shí)間如下所示。進(jìn)程 所需運(yùn)行時(shí)間

1 62 33147進(jìn)程到達(dá)次序?yàn)?，2，3，4。試分別按先來(lái)先服務(wù)調(diào)度算法、短進(jìn)程優(yōu)先調(diào)度算法和時(shí)間片輪轉(zhuǎn)法(時(shí)間片分1，3，5，6)給出進(jìn)程調(diào)度順序，并計(jì)算平均等待時(shí)間。3.7處理機(jī)調(diào)度解：（1）先來(lái)先服務(wù)調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋?/p>

平均等待時(shí)間：T=1／4×(0+6+9+10)=6.25（2）短進(jìn)程優(yōu)先調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋浩骄却龝r(shí)間：T=1／4×(4+1+0+10)=3.75（3）時(shí)間片輪轉(zhuǎn)法

3.7處理機(jī)調(diào)度解：·時(shí)間片為1，進(jìn)程調(diào)度順序如下：

平均等待時(shí)間：T=1/4×((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1)=1／4×(9+6+2+10)=6.75·時(shí)間片為3，進(jìn)程調(diào)度順序如下：平均等待時(shí)間：T=1／4×((0+7)+3+6+(7+3))=1／4×(7+3+6+10)=6.53.7處理機(jī)調(diào)度解：·時(shí)間片為5，進(jìn)程調(diào)度順序如下：平均等待時(shí)間：T=1／4×((0+9)+5+8+(9+1))=1／4×(9+5+8+10)=8·時(shí)間片為6，相當(dāng)于先來(lái)先服務(wù)調(diào)度算法。其進(jìn)程調(diào)度順序和平均等待時(shí)間與先來(lái)先服務(wù)調(diào)度算法相同。總結(jié)：短進(jìn)程優(yōu)先調(diào)度算法使進(jìn)程平均等待時(shí)間最小。對(duì)于時(shí)間片輪轉(zhuǎn)法，進(jìn)程平均等待時(shí)間與時(shí)間片的大小有關(guān)。

3.7處理機(jī)調(diào)度3.8.1WindowsXP的進(jìn)程

1.WindowsXP的進(jìn)程對(duì)象2.WindowsXP的進(jìn)程TDB（任務(wù)數(shù)據(jù)庫(kù)）3.8WindowsXP的進(jìn)程和線程管理圖3-20WindowsXP的進(jìn)程對(duì)象進(jìn)程進(jìn)程ID安全描述符基本優(yōu)先級(jí)默認(rèn)處理器集合定額限制執(zhí)行時(shí)間I/O計(jì)數(shù)器VM操作計(jì)數(shù)器異常/調(diào)試端口退出狀態(tài)創(chuàng)建進(jìn)程打開(kāi)進(jìn)程查詢進(jìn)程信息設(shè)置進(jìn)程信息當(dāng)前進(jìn)程終止進(jìn)程對(duì)象類型對(duì)象體屬性服務(wù)圖3-21WindowsXP的進(jìn)程TDB私有堆棧鏈接指針狀態(tài)標(biāo)志（事件計(jì)數(shù)）優(yōu)先級(jí)……屬性名稱屬性含義進(jìn)程ID進(jìn)程的惟一標(biāo)識(shí)安全描述符描述誰(shuí)創(chuàng)建對(duì)象、誰(shuí)可以訪問(wèn)/使用對(duì)象或禁止誰(shuí)訪問(wèn)對(duì)象基本優(yōu)先級(jí)進(jìn)程中線程的基本優(yōu)先級(jí)默認(rèn)處理器集合可以運(yùn)行的進(jìn)程中線程的默認(rèn)處理器集合定額限制頁(yè)式存儲(chǔ)器及頁(yè)式文件空間，進(jìn)程可使用的處理器最大時(shí)間執(zhí)行時(shí)間進(jìn)程中的所有線程已經(jīng)執(zhí)行的時(shí)間總量I/O計(jì)數(shù)器記載進(jìn)程中線程已執(zhí)行的I/O操作數(shù)量、類型的變量VM操作計(jì)數(shù)器記載進(jìn)程中線程已執(zhí)行的虛擬存儲(chǔ)操作數(shù)量、類型的變量異常/調(diào)試端口進(jìn)程中的線程異常時(shí)，用于進(jìn)程管理器發(fā)送消息的通信信道退出狀態(tài)進(jìn)程終止的原因表3-2WindowsXP進(jìn)程對(duì)象的屬性3.8.2WindowsXP的線程1.WindowsXP的線程對(duì)象線程對(duì)象如圖3-22所示線程對(duì)象的屬性見(jiàn)表3-3。3.8WindowsXP的進(jìn)程和線程管理線程線程ID動(dòng)態(tài)優(yōu)先級(jí)基本優(yōu)先級(jí)線程處理器集合線程執(zhí)行警告狀態(tài)掛起計(jì)數(shù)器假冒標(biāo)志終止端口線程退出狀態(tài)創(chuàng)建線程打開(kāi)線程查詢線程信息當(dāng)前線程終止線程獲取上下文設(shè)置上下文掛起恢復(fù)警告線程測(cè)試線程警告寄存器終止端口對(duì)象類型對(duì)象屬性服務(wù)圖3-22WindowsXP線程對(duì)象屬性名稱屬性含義線程ID

當(dāng)線程調(diào)用一個(gè)服務(wù)程序時(shí)，標(biāo)識(shí)該線程的惟一值線程上下文

定義線程執(zhí)行狀態(tài)的一組寄存器值和其他易失的數(shù)據(jù)動(dòng)態(tài)優(yōu)先級(jí)

任何給定時(shí)刻，線程執(zhí)行優(yōu)先級(jí)基本優(yōu)先級(jí)

線程動(dòng)態(tài)優(yōu)先級(jí)的下限線程處理器集合

可以運(yùn)行的線程的處理器集合線程執(zhí)行時(shí)間

線程在用戶模式和內(nèi)核模式下執(zhí)行的時(shí)間總量警告狀態(tài)

表示線程是否將執(zhí)行一個(gè)異步過(guò)程調(diào)用的標(biāo)志掛起計(jì)數(shù)器

記載線程被掛起的次數(shù)（但未恢復(fù)）假冒標(biāo)志

允許線程代表另一進(jìn)程執(zhí)行的臨時(shí)訪問(wèn)標(biāo)志（供子系統(tǒng)使用）線程退出狀態(tài)

線程終止的原因表3-3WindowsXP線程對(duì)象的屬性2.WindowsXP的線程狀態(tài)等待完成等待完成換出的內(nèi)核堆棧換入的內(nèi)核堆棧搶先或時(shí)間片完等待對(duì)象句柄完成描述表切換選擇執(zhí)行創(chuàng)建并初始化初始化備用就緒運(yùn)行轉(zhuǎn)換終止等待圖3-23WindowsXP線程狀態(tài)轉(zhuǎn)換3.8.2WindowsXP的線程3.WindowsXP的線程控制CreateThread、ExitThread、SuspendThread、ResumeThread4.WindowsXP的線程調(diào)度

WindowsXP的調(diào)度對(duì)象是線程WindowsXP采用嚴(yán)格的搶先式動(dòng)態(tài)優(yōu)先級(jí)調(diào)度，根據(jù)優(yōu)先級(jí)和分配時(shí)間配額（quantum）進(jìn)行調(diào)度3.8WindowsXP的進(jìn)程和線程管理4.WindowsXP的線程調(diào)度3.8WindowsXP的進(jìn)程和線程管理表3-4Windows32中與線程調(diào)度相關(guān)的API函數(shù)及功能說(shuō)明與線程調(diào)度有關(guān)的API函數(shù)函數(shù)功能說(shuō)明Suspend/ResumeThread掛起/激活一個(gè)正在運(yùn)行/暫停的線程Get/SetPriorityClass讀/設(shè)置一個(gè)線程的基本優(yōu)先級(jí)類型Get/SetThreadPriority讀/設(shè)置一個(gè)線程的相對(duì)優(yōu)先級(jí)Get/SetProcessPriorityBoost讀/設(shè)置當(dāng)前進(jìn)程的默認(rèn)優(yōu)先級(jí)提升控制Get/SetThreadPriorityBoost讀/設(shè)置暫時(shí)提升線程優(yōu)先級(jí)狀態(tài)：在可調(diào)范圍內(nèi)Get/SetProcessAffinityMask讀/設(shè)置一個(gè)進(jìn)程的默認(rèn)處理器集合SetThreadAffinityMask設(shè)置線程的默認(rèn)處理器集合SetThreadIdealProcessor設(shè)置線程的首選處理器，但不限制線程在該處理器SwitchToThread當(dāng)前線程放棄一個(gè)或多個(gè)時(shí)間配額的運(yùn)行Sleep使當(dāng)前線程等待一個(gè)指定的時(shí)間段SleepEx使當(dāng)前線程進(jìn)入等待狀態(tài)3.8.3WindowsXP的進(jìn)程互斥和同步1.互斥、互斥對(duì)象與臨界區(qū)對(duì)象WindowsXP中用于互鎖變量訪問(wèn)的API函數(shù)：InterlockedExchange、InterlockedExchangePointer、InterlockedCompareExchange、InterlockedCompareExchangePointer、InterlockedExchangeAdd、InterlockedDecrement、InterlockedIncrement。3.8WindowsXP的進(jìn)程和線程管理3.8.3WindowsXP的進(jìn)程互斥和同步1.互斥、互斥對(duì)象與臨界區(qū)對(duì)象WindowsXP中與互斥對(duì)象有關(guān)的API函數(shù)：

CreateMutex、OpenMutex