操作系統(tǒng)第3章_3

1、1第三章、進(jìn)程管理第三章、進(jìn)程管理 3.1進(jìn)程的概念進(jìn)程的概念3.2進(jìn)程的描述進(jìn)程的描述3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換進(jìn)程狀態(tài)及其轉(zhuǎn)換3.4進(jìn)程控制進(jìn)程控制3.5進(jìn)程互斥進(jìn)程互斥3.6進(jìn)程同步進(jìn)程同步3.7進(jìn)程通信進(jìn)程通信3.8死鎖問(wèn)題死鎖問(wèn)題3.9線程線程23. 7 進(jìn)程通信進(jìn)程通信一、進(jìn)程通信：一、進(jìn)程通信：進(jìn)程之間的信息交換、數(shù)據(jù)傳送。進(jìn)程之間的信息交換、數(shù)據(jù)傳送。低級(jí)通信低級(jí)通信：少量控制信息的交換，一個(gè)少量控制信息的交換，一個(gè)/幾個(gè)字節(jié)。幾個(gè)字節(jié)。高級(jí)通信高級(jí)通信：高效、大量地傳送數(shù)據(jù)，交換信息。高效、大量地傳送數(shù)據(jù)，交換信息。 二、進(jìn)程通信方式：二、進(jìn)程通信方式：1、主從式：主從式： （終

2、端控制進(jìn)程與終端進(jìn)程）（終端控制進(jìn)程與終端進(jìn)程） 1）主進(jìn)程可自由使用從進(jìn)程的資源和數(shù)據(jù)；）主進(jìn)程可自由使用從進(jìn)程的資源和數(shù)據(jù)； 2）從進(jìn)程動(dòng)作受主進(jìn)程控制；）從進(jìn)程動(dòng)作受主進(jìn)程控制； 3）主、從進(jìn)程的關(guān)系固定。）主、從進(jìn)程的關(guān)系固定。2、會(huì)話式：會(huì)話式： （用戶(hù)進(jìn)程與磁盤(pán)管理進(jìn)程）（用戶(hù)進(jìn)程與磁盤(pán)管理進(jìn)程） 1）使用進(jìn)程要得到服務(wù)進(jìn)程的許可；）使用進(jìn)程要得到服務(wù)進(jìn)程的許可； 2）服務(wù)進(jìn)程自控地完成對(duì)使用進(jìn)程的服務(wù)；）服務(wù)進(jìn)程自控地完成對(duì)使用進(jìn)程的服務(wù)； 3）通信時(shí)二者有固定的連接關(guān)系。）通信時(shí)二者有固定的連接關(guān)系。33、共享存儲(chǔ)區(qū)方式共享存儲(chǔ)區(qū)方式： （UNIX System V)在存儲(chǔ)區(qū)中

3、劃出一塊共享存儲(chǔ)區(qū)，兩個(gè)進(jìn)程通過(guò)在存儲(chǔ)區(qū)中劃出一塊共享存儲(chǔ)區(qū)，兩個(gè)進(jìn)程通過(guò)對(duì)申請(qǐng)的共享存儲(chǔ)區(qū)讀、寫(xiě)實(shí)現(xiàn)通信。對(duì)申請(qǐng)的共享存儲(chǔ)區(qū)讀、寫(xiě)實(shí)現(xiàn)通信。4、消息或郵箱機(jī)制消息或郵箱機(jī)制：1）發(fā)送進(jìn)程和接收進(jìn)程之間有用于存放傳送消息的緩）發(fā)送進(jìn)程和接收進(jìn)程之間有用于存放傳送消息的緩沖區(qū)或郵箱；沖區(qū)或郵箱；2）發(fā)送進(jìn)程向空緩沖區(qū)或郵箱發(fā)送信息，接收進(jìn)程從）發(fā)送進(jìn)程向空緩沖區(qū)或郵箱發(fā)送信息，接收進(jìn)程從滿(mǎn)緩沖區(qū)或郵箱接收信息；滿(mǎn)緩沖區(qū)或郵箱接收信息；3）發(fā)送進(jìn)程和接收進(jìn)程之間沒(méi)有直接固定的聯(lián)系。）發(fā)送進(jìn)程和接收進(jìn)程之間沒(méi)有直接固定的聯(lián)系。4三、消息緩沖機(jī)制：三、消息緩沖機(jī)制： （直接通信方式，多對(duì)一）（直接通信

4、方式，多對(duì)一）消息緩沖區(qū)消息緩沖區(qū)：進(jìn)程通信的基本單位，記錄消息的內(nèi)容等信息，進(jìn)程通信的基本單位，記錄消息的內(nèi)容等信息，為多個(gè)進(jìn)程共享，其數(shù)據(jù)結(jié)構(gòu)描述為：為多個(gè)進(jìn)程共享，其數(shù)據(jù)結(jié)構(gòu)描述為：TYPE message buffer = recordsender_ptr;指向發(fā)送進(jìn)程的指針指向發(fā)送進(jìn)程的指針size;消息長(zhǎng)度消息長(zhǎng)度text;消息正文消息正文next_ptr;指向下一個(gè)消息緩沖區(qū)的指針指向下一個(gè)消息緩沖區(qū)的指針end56公用信號(hào)量公用信號(hào)量mutex：對(duì)消息緩沖區(qū)的的訪問(wèn)采取對(duì)消息緩沖區(qū)的的訪問(wèn)采取互斥互斥措施措施;私有信號(hào)量私有信號(hào)量Sm ：消息緩沖區(qū)無(wú)消息時(shí)，接收進(jìn)程不能接收，消

5、息緩沖區(qū)無(wú)消息時(shí)，接收進(jìn)程不能接收，同步同步措施。措施。發(fā)送進(jìn)程：發(fā)送進(jìn)程：Send(k,m)begin向系統(tǒng)申請(qǐng)一個(gè)消息緩沖區(qū)向系統(tǒng)申請(qǐng)一個(gè)消息緩沖區(qū)將發(fā)送消息將發(fā)送消息m送到新消息緩沖區(qū)送到新消息緩沖區(qū)把緩沖區(qū)鏈入接收進(jìn)程把緩沖區(qū)鏈入接收進(jìn)程 k 的消息隊(duì)列的消息隊(duì)列end 接收進(jìn)程：接收進(jìn)程：Receive(n)begin摘下消息隊(duì)列中消息摘下消息隊(duì)列中消息n把把n復(fù)制到接收區(qū)復(fù)制到接收區(qū)釋放消息緩沖區(qū)釋放消息緩沖區(qū)end P(mutex)V(mutex)V(Sm)P(Sm)P(mutex)V(mutex)7四、郵箱通信：四、郵箱通信： （間接通信方式，靈活）（間接通信方式，靈活）郵箱郵

6、箱：發(fā)送進(jìn)程和接收進(jìn)程之間設(shè)置的大小固定的私有數(shù)：發(fā)送進(jìn)程和接收進(jìn)程之間設(shè)置的大小固定的私有數(shù)據(jù)結(jié)構(gòu)（多個(gè)消息組成的隊(duì)列），由接收進(jìn)程所擁有。據(jù)結(jié)構(gòu)（多個(gè)消息組成的隊(duì)列），由接收進(jìn)程所擁有。工作條件工作條件：發(fā)送至少有一個(gè)空格，接收時(shí)至少有一個(gè)滿(mǎn)格。：發(fā)送至少有一個(gè)空格，接收時(shí)至少有一個(gè)滿(mǎn)格。特點(diǎn)特點(diǎn)：發(fā)送、接收基本無(wú)時(shí)間限制。：發(fā)送、接收基本無(wú)時(shí)間限制。缺點(diǎn)缺點(diǎn)：占用大量?jī)?nèi)存，接口多，效率低。（公用信箱）：占用大量?jī)?nèi)存，接口多，效率低。（公用信箱）8同步措施：設(shè)置一對(duì)私有信號(hào)量，記錄郵箱中空格滿(mǎn)格的數(shù)量同步措施：設(shè)置一對(duì)私有信號(hào)量，記錄郵箱中空格滿(mǎn)格的數(shù)量Deposit(m)begin lo

7、cal x選擇郵箱的一個(gè)空格選擇郵箱的一個(gè)空格x把消息把消息m放入空格放入空格x置格置格x為滿(mǎn)標(biāo)志為滿(mǎn)標(biāo)志endRemove(m)begin local x選擇郵箱的一個(gè)滿(mǎn)格選擇郵箱的一個(gè)滿(mǎn)格x取走消息取走消息m置格置格x為空標(biāo)志為空標(biāo)志endP(formnum)V(mesnum)P(mesnum)V(formnum)9實(shí)例實(shí)例1：管道：管道 P66以比特流方式傳送消息的通信管道，由文以比特流方式傳送消息的通信管道，由文件系統(tǒng)的高速緩沖區(qū)構(gòu)成。件系統(tǒng)的高速緩沖區(qū)構(gòu)成。10例：創(chuàng)建管道，父子進(jìn)程通過(guò)管道傳遞數(shù)據(jù)。例：創(chuàng)建管道，父子進(jìn)程通過(guò)管道傳遞數(shù)據(jù)。#include main()int x,f

8、d2; char buf30,s30; pipe(fd); while (x=fork()=-1) ; if (x = 0) sprintf( buf,this is an example!); write( fd1 , buf , 30 ); exit(0); else wait(0); read( fd0, s , 30 ); printf(result:%s,s); 11實(shí)例實(shí)例2：書(shū)例書(shū)例P1541、接收消息程序、接收消息程序client.c2、發(fā)送消息程序、發(fā)送消息程序server.c3、在、在msg.c中，創(chuàng)建三個(gè)子進(jìn)程：中，創(chuàng)建三個(gè)子進(jìn)程： 其中兩個(gè)調(diào)用其中兩個(gè)調(diào)用client.

9、c 另一個(gè)調(diào)用另一個(gè)調(diào)用 server.c 相互之間發(fā)送消息相互之間發(fā)送消息12接收消息程序接收消息程序client.c#include #include #include #define MSGKEY 75struct msgform long mtype; char mtext256; ;main(int argc,char *argv) struct msgform msg; int msgqid, pid, *pint; msgqid = msgget(MSGKEY,0777|IPC_CREAT); printf(msgqid = %dnn,msgqid); pid = getpid(

10、); pint = (int *)msg.mtext; *pint = pid; msg.mtype = 1; msgsnd(msgqid,&msg,sizeof(int),0); msgrcv(msgqid,(struct msgform )&msg, sizeof(msg),pid,0); pint = (int *)msg.mtext; pid = (int)*pint; printf(Client %s: receive from Server process %dn,argv1,pid);13發(fā)送消息程序發(fā)送消息程序 server.c - 1#include #inc

11、lude #include #define MSGKEY 75struct msgform long mtype; char mtext256; ;int msgqid;main() struct msgform msg; int i,*pint; int pid; extern cleanup(); for (i=0;i20;i+) signal(i,cleanup); msgqid = msgget(MSGKEY,0777|IPC_CREAT); printf(msgqid = %dnn,msgqid); 14發(fā)送消息程序發(fā)送消息程序 server.c - 2for( ; ; ) msgr

12、cv(msgqid,(struct msgform *)&msg,256,1,0); pint = (int *)msg.mtext; pid = (int)*pint; printf(Server : receive from Client process %d nn,pid); msg.mtype = pid; pint = (int *)msg.mtext; *pint = getpid(); msgsnd(msgqid, &msg,sizeof(int),0); cleanup() msgctl(msgqid,IPC_RMID,0); exit(); 15msg.c #

13、include #include #include main() int pid1,pid2,pid3; pid1 = vfork(); if (pid1 = 0) /*子進(jìn)程子進(jìn)程2001*/ printf(nClient1 process %4d :n,getpid(); execlp(/client,client,1,NULL); else pid2 = vfork(); if (pid2 = 0) /*子進(jìn)程子進(jìn)程2002*/ printf(Client2 process %4d:n,getpid(); execlp(/client,client,2,NULL); else pid3

14、= vfork(); if (pid3 = 0) /*子進(jìn)程子進(jìn)程2000*/ printf(Server3 process %4d:n,getpid(); execlp(/server,server,NULL); else printf(nThis is Parent process %4d ! n, getpid(); wait(0); wait(0); wait(0); 16子進(jìn)程子進(jìn)程2001子進(jìn)程子進(jìn)程2002子進(jìn)程子進(jìn)程2000TYPE：1TEXT：2001TYPE：1TEXT：2002TYPE： 2001TEXT： 2000TYPE： 2002TEXT： 2000消息隊(duì)列消息隊(duì)列

15、書(shū)例書(shū)例P16317控控制制臺(tái)臺(tái)D DP PK KP PD DC CP PK KC CP PP Pn nC CC CP Pe ec ch ho ob bu uf fo ou ut tb bu uf fi in nb bu uf fR RQ QS SQ QR Re ec ce ei iv ve e( (k k) )W Wr ri it te e( (y y) )S Se en nd d( (x x, ,m m) )R Re ea ad d( (x x) )U U_ _r re ec ce ei iv ve e( (m m) )S S_ _a an ns sw we er r( (a a, ,i

16、i) )實(shí)例實(shí)例3：和控制臺(tái)的通信：和控制臺(tái)的通信i18用戶(hù)進(jìn)程用戶(hù)進(jìn)程Pi CCP的接口的接口用戶(hù)進(jìn)程用戶(hù)進(jìn)程發(fā)出問(wèn)題：發(fā)出問(wèn)題：P_write(m)BeginP(rq) 把把m插入插入RQ隊(duì)列隊(duì)列V(rq) V(question)EndCCP接收問(wèn)題：接收問(wèn)題：U_receive(m)BeginP(question)P(rq) 把把m從從RQ隊(duì)列取出隊(duì)列取出V(rq)End19CCP與與DCP的接口的接口CCP向向outbuf送問(wèn)題：送問(wèn)題： outbuf_empty = 1Write(y)BeginP(outbuf_empty) copy(outbuf from y)V(outbuf_f

17、ull)EndDCP從從outbuf中接收：中接收： outbuf_full = 0Receive(k)BeginP(outbuf_full) copy(outbuf to k)V(outbuf_empty)End20DCP與顯示器的通信與顯示器的通信顯示器控制進(jìn)程顯示器控制進(jìn)程DCP： D_busy = 1初始化初始化清除清除outbuf， echo=falseBeginif (outbuf滿(mǎn)滿(mǎn)) thenreceive(k)P(D_busy)把把k送入顯示器數(shù)據(jù)緩沖區(qū)送入顯示器數(shù)據(jù)緩沖區(qū)V(D_ready)elseecho = trueechobuf中字符置入顯示器緩沖區(qū)中字符置入顯示器緩

18、沖區(qū)fiEnd顯示器動(dòng)作顯示器動(dòng)作DP： D_ready = 0Repeatif (echo = true) then 打印顯示器緩沖區(qū)中字符打印顯示器緩沖區(qū)中字符else P(D_ ready) 打印顯示器緩沖區(qū)中消息打印顯示器緩沖區(qū)中消息 V(D_ busy)Until (顯示器關(guān)機(jī)顯示器關(guān)機(jī))21KCP與鍵盤(pán)的通信與鍵盤(pán)的通信鍵盤(pán)控制進(jìn)程鍵盤(pán)控制進(jìn)程KCP： T_busy = 1初始化初始化清除清除inbuf、 echobufBegin P(T_ready) 從鍵盤(pán)數(shù)據(jù)緩沖區(qū)從鍵盤(pán)數(shù)據(jù)緩沖區(qū)x中取出字符中取出字符x.m Send(x.m) 將將x.m送入送入echobuf V(T_bus

19、y)End鍵盤(pán)動(dòng)作鍵盤(pán)動(dòng)作KP： T_ready = 0RepeatP(T_ busy)把鍵入字符送入鍵盤(pán)數(shù)據(jù)緩沖區(qū)把鍵入字符送入鍵盤(pán)數(shù)據(jù)緩沖區(qū)xV(T_ ready)Until (終端關(guān)閉終端關(guān)閉)22CCP與與KCP的接口的接口KCP向向inbuf送回答：送回答： inbuf_empty = 1Send(k)BeginP(inbuf_empty) copy(inbuf from k)V(inbuf_full)EndCCP從從inbuf中接收回答：中接收回答： inbuf_full = 0Read(x)BeginP(inbuf_full) copy(inbuf to x) V(inbuf_e

20、mpty)End23CCP 用戶(hù)進(jìn)程用戶(hù)進(jìn)程Pi的接口的接口CCP發(fā)出回答：發(fā)出回答：S_answer(a,i)BeginP(sqi) 把把a(bǔ)插入插入SQi隊(duì)列隊(duì)列V(sqi)V(answeri)End用戶(hù)進(jìn)程用戶(hù)進(jìn)程接收回答：接收回答：P_read(a)BeginP(answeri)P(sqi) 把把a(bǔ)從從SQi隊(duì)列隊(duì)列 取出取出V(sqi) End24會(huì)話控制進(jìn)程會(huì)話控制進(jìn)程CCP的動(dòng)作描述的動(dòng)作描述Local k,m,xRepeatU_receive(m)將消息將消息m的進(jìn)程標(biāo)號(hào)置入的進(jìn)程標(biāo)號(hào)置入k中中將消息將消息m解碼變換到解碼變換到xwrite(x)read(x)將將x編碼到編碼到m

21、S_answer(m,k)Until （CCP結(jié)束）結(jié)束）253. 8 死鎖問(wèn)題死鎖問(wèn)題一、死鎖的定義一、死鎖的定義指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的僵局，即各自等待對(duì)方的資指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的僵局，即各自等待對(duì)方的資源，而在得到對(duì)方資源前又不會(huì)釋放自己擁有的資源，在無(wú)外力源，而在得到對(duì)方資源前又不會(huì)釋放自己擁有的資源，在無(wú)外力作用下，各進(jìn)程將永遠(yuǎn)不能向前推進(jìn)。作用下，各進(jìn)程將永遠(yuǎn)不能向前推進(jìn)。26二、死鎖的起因二、死鎖的起因1、資源競(jìng)爭(zhēng)：、資源競(jìng)爭(zhēng)：可剝奪性資源（可剝奪性資源（CPU、內(nèi)存）、內(nèi)存）非剝奪性資源（打印機(jī)）：分配后不能強(qiáng)行收回。非剝奪性資源（打印機(jī)）：分配后不能強(qiáng)行收回。27

22、2、進(jìn)程推進(jìn)順序非法：、進(jìn)程推進(jìn)順序非法：合法合法非法非法28三、產(chǎn)生死鎖的必要條件：三、產(chǎn)生死鎖的必要條件：1、互斥條件：、互斥條件：2、不剝奪條件：、不剝奪條件：3、部分分配條件（請(qǐng)求和保持）：、部分分配條件（請(qǐng)求和保持）：4、環(huán)路條件：、環(huán)路條件：防止死鎖發(fā)生，破壞四個(gè)必要條件中的防止死鎖發(fā)生，破壞四個(gè)必要條件中的一個(gè)或多個(gè)即可（主要是第一個(gè)或多個(gè)即可（主要是第3、4 個(gè)，第個(gè)，第1、2條受資源特性的限制）。條受資源特性的限制）。29四、死鎖的排除方式四、死鎖的排除方式1、死鎖的預(yù)防、死鎖的預(yù)防2、死鎖的避免、死鎖的避免3、死鎖的檢測(cè)和恢復(fù)、死鎖的檢測(cè)和恢復(fù)301、死鎖的預(yù)防、死鎖的預(yù)防

23、 破壞四個(gè)必要條件中的一個(gè)或多個(gè)破壞四個(gè)必要條件中的一個(gè)或多個(gè)2）有序資源使用法）有序資源使用法 打破打破“環(huán)路條件環(huán)路條件”內(nèi)容：內(nèi)容：把資源編號(hào)排序，要求進(jìn)程必須按編號(hào)遞增的順序申請(qǐng)資源：把資源編號(hào)排序，要求進(jìn)程必須按編號(hào)遞增的順序申請(qǐng)資源：m個(gè)資源，個(gè)資源，R1R2i）;原理：原理：總有一個(gè)進(jìn)程占據(jù)較高序號(hào)的資源，其后申請(qǐng)的資源必空閑，從總有一個(gè)進(jìn)程占據(jù)較高序號(hào)的資源，其后申請(qǐng)的資源必空閑，從而滿(mǎn)足需要一直往前推進(jìn)，再釋放已用資源。而滿(mǎn)足需要一直往前推進(jìn)，再釋放已用資源。編號(hào)原則：編號(hào)原則：常用資源低序號(hào)，不常用資源高序號(hào)；常用資源低序號(hào)，不常用資源高序號(hào)；缺點(diǎn)：缺點(diǎn)：序號(hào)順序相對(duì)穩(wěn)定限

24、制新設(shè)備；當(dāng)一個(gè)進(jìn)程的資源使用順序和編序號(hào)順序相對(duì)穩(wěn)定限制新設(shè)備；當(dāng)一個(gè)進(jìn)程的資源使用順序和編號(hào)順序不一致時(shí)，資源閑置浪費(fèi)；限制用戶(hù)的編程自由。號(hào)順序不一致時(shí)，資源閑置浪費(fèi)；限制用戶(hù)的編程自由。1）預(yù)先靜態(tài)分配法）預(yù)先靜態(tài)分配法 打破打破“部分分配條件部分分配條件”內(nèi)容：內(nèi)容：進(jìn)程一次性申請(qǐng)和分配全部所需資源，未全部滿(mǎn)足則等待。進(jìn)程一次性申請(qǐng)和分配全部所需資源，未全部滿(mǎn)足則等待。缺點(diǎn)：缺點(diǎn)：資源嚴(yán)重浪費(fèi)；進(jìn)程延遲運(yùn)行。資源嚴(yán)重浪費(fèi)；進(jìn)程延遲運(yùn)行。312、死鎖的避免、死鎖的避免思路：思路：在動(dòng)態(tài)分配資源的過(guò)程中預(yù)測(cè)出發(fā)生死鎖的可能性，加以避免。在動(dòng)態(tài)分配資源的過(guò)程中預(yù)測(cè)出發(fā)生死鎖的可能性，加以避

25、免。判斷此次分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入判斷此次分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入“不安全狀態(tài)不安全狀態(tài)”？安全狀態(tài)安全狀態(tài)：系統(tǒng)至少存在一個(gè)安全序列不會(huì)發(fā)生死鎖。：系統(tǒng)至少存在一個(gè)安全序列不會(huì)發(fā)生死鎖。例：例：進(jìn)程進(jìn)程 需求量需求量已分配已分配空閑資源空閑資源A1053B42C92把空閑的把空閑的3個(gè)中的個(gè)中的2個(gè)分給個(gè)分給B把空閑的把空閑的3個(gè)中的個(gè)中的2個(gè)分給個(gè)分給C安全的分配：安全的分配：不安全分配：不安全分配：32銀行家算法銀行家算法基本模式：基本模式：將進(jìn)程分為若干步，每一步使用的資源固定，當(dāng)進(jìn)程每將進(jìn)程分為若干步，每一步使用的資源固定，當(dāng)進(jìn)程每一步申請(qǐng)資源時(shí)，將請(qǐng)求、分配、釋放、空閑的情況結(jié)合起一

26、步申請(qǐng)資源時(shí)，將請(qǐng)求、分配、釋放、空閑的情況結(jié)合起來(lái)計(jì)算，看是否符合分配條件。來(lái)計(jì)算，看是否符合分配條件。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：n個(gè)并發(fā)進(jìn)程個(gè)并發(fā)進(jìn)程P1Pn共享共享m個(gè)資源個(gè)資源R1Rm：可用資源向量可用資源向量Availablem: Availablej 資源資源Ri現(xiàn)有的現(xiàn)有的空閑空閑個(gè)數(shù)個(gè)數(shù)最大需求矩陣最大需求矩陣Maxn*m:Maxi,j 進(jìn)程進(jìn)程Pi對(duì)資源對(duì)資源Rj的的最大需要數(shù)最大需要數(shù)分配矩陣分配矩陣Allocationn*m: Allocationi,j 進(jìn)程進(jìn)程Pi已獲得已獲得資源資源Rj的數(shù)量的數(shù)量需求矩陣需求矩陣Needn*m:Needi,j 進(jìn)程進(jìn)程Pi還需要還需要資源

27、資源Rj的數(shù)量的數(shù)量 Needi，j = Maxi，j - Allocationi，j 333435例：五個(gè)進(jìn)程共享三類(lèi)資源例：五個(gè)進(jìn)程共享三類(lèi)資源A、B、C，每類(lèi)資源數(shù)量為，每類(lèi)資源數(shù)量為10、5、7。 時(shí)刻時(shí)刻T0的資源分配情況如下：的資源分配情況如下：MaxAllocationNeedAvaillableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 110 5 7 - 7 2 5= 3 3 236對(duì)對(duì)T0時(shí)刻進(jìn)行安全性

28、分析時(shí)刻進(jìn)行安全性分析后，可以找到一個(gè)安全序列后，可以找到一個(gè)安全序列P1，P3，P4，P2，P0，則系統(tǒng)安全。，則系統(tǒng)安全。T0WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1 3 3 21 2 22 0 05 3 2trueP3 5 3 20 1 12 1 17 4 3trueP4 7 4 34 3 10 0 27 4 5trueP2 7 4 56 0 03 0 210 4 7trueP0 10 4 77 4 30 1 010 5 7true37P1發(fā)出請(qǐng)求發(fā)出請(qǐng)求Req(1,0,2） = Need(1,2,2）及）

29、及Availlable(3,3,2）為為P1試探分配，修改試探分配，修改Availlable 、Allocation 、NeedT1時(shí)刻進(jìn)行安全性分析時(shí)刻進(jìn)行安全性分析，找到安全序列，找到安全序列P1，P3，P4，P0，P2 說(shuō)明系統(tǒng)安全，可以為說(shuō)明系統(tǒng)安全，可以為P1實(shí)施分配實(shí)施分配T1WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1 2 3 00 2 03 0 25 3 2trueP3 5 3 20 1 12 1 17 4 3trueP4 7 4 34 3 10 0 27 4 5trueP0 7 4 57 4 30

30、1 07 5 5trueP2 7 5 56 0 0 3 0 210 5 7trueT0 3 3 2 1 2 2 2 0 038P4發(fā)出請(qǐng)求發(fā)出請(qǐng)求Req(3，3，0）：）： Req(3，3，0） Availlable(2，3，0)，不能分配，等待。，不能分配，等待。P0發(fā)出請(qǐng)求發(fā)出請(qǐng)求Req(0，2，0）：）： Req(0，2，0） =Need(7，4，3) Req(0，2，0）= Availlable(2，3，0)，試探分配，修改數(shù)據(jù)：，試探分配，修改數(shù)據(jù)：AllocationNeedAvaillableA B CA B CA B CP00 3 07 2 32 1 0P13 0 20 2 0

31、P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1無(wú)法滿(mǎn)足無(wú)法滿(mǎn)足任何進(jìn)程任何進(jìn)程不能分配不能分配393、死鎖的檢測(cè)和恢復(fù)、死鎖的檢測(cè)和恢復(fù)1）死鎖的檢測(cè)：判斷死鎖是否發(fā)生？）死鎖的檢測(cè)：判斷死鎖是否發(fā)生？2）死鎖的恢復(fù)：）死鎖的恢復(fù)：終止各進(jìn)程，或逐個(gè)終止，直至先后釋放的資終止各進(jìn)程，或逐個(gè)終止，直至先后釋放的資源能夠滿(mǎn)足剩余進(jìn)程的需要。源能夠滿(mǎn)足剩余進(jìn)程的需要。403.9 線程線程一、線程的引入一、線程的引入為實(shí)現(xiàn)持續(xù)的并發(fā)執(zhí)行，引入進(jìn)程，但由于各種原因，為實(shí)現(xiàn)持續(xù)的并發(fā)執(zhí)行，引入進(jìn)程，但由于各種原因，若干進(jìn)程間會(huì)出現(xiàn)頻繁調(diào)度、切換，進(jìn)行上下文切換的開(kāi)銷(xiāo)若干進(jìn)程間會(huì)出

32、現(xiàn)頻繁調(diào)度、切換，進(jìn)行上下文切換的開(kāi)銷(xiāo)花去不少花去不少CPU時(shí)間，降低并發(fā)的效率。時(shí)間，降低并發(fā)的效率。進(jìn)程的性質(zhì)：進(jìn)程的性質(zhì)：1、是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位、是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位 PCB。2、是程序?qū)δ硞€(gè)數(shù)據(jù)集在處理機(jī)上的執(zhí)行過(guò)程。、是程序?qū)δ硞€(gè)數(shù)據(jù)集在處理機(jī)上的執(zhí)行過(guò)程。把兩個(gè)特點(diǎn)分開(kāi)，由進(jìn)程負(fù)責(zé)資源的管理，由進(jìn)程創(chuàng)建把兩個(gè)特點(diǎn)分開(kāi)，由進(jìn)程負(fù)責(zé)資源的管理，由進(jìn)程創(chuàng)建的若干個(gè)線程完成運(yùn)行的特性，線程共享所屬進(jìn)程的資源，的若干個(gè)線程完成運(yùn)行的特性，線程共享所屬進(jìn)程的資源，減少線程間切換的花銷(xiāo)。減少線程間切換的花銷(xiāo)。進(jìn)程上下文進(jìn)程上下文 進(jìn)程執(zhí)行活動(dòng)過(guò)程的靜態(tài)描述，是進(jìn)程執(zhí)

33、行所依賴(lài)的環(huán)境。進(jìn)程執(zhí)行活動(dòng)過(guò)程的靜態(tài)描述，是進(jìn)程執(zhí)行所依賴(lài)的環(huán)境。 當(dāng)系統(tǒng)調(diào)度新進(jìn)程占有處理機(jī)時(shí)，新老進(jìn)程的上下文發(fā)生轉(zhuǎn)換。當(dāng)系統(tǒng)調(diào)度新進(jìn)程占有處理機(jī)時(shí)，新老進(jìn)程的上下文發(fā)生轉(zhuǎn)換。42二、線程的概念二、線程的概念進(jìn)程內(nèi)的基本調(diào)度單位；進(jìn)程內(nèi)的基本調(diào)度單位；是相對(duì)獨(dú)立的執(zhí)行單元（子任務(wù)）；是相對(duì)獨(dú)立的執(zhí)行單元（子任務(wù)）；進(jìn)程進(jìn)程線程線程資源分配的基本單位。資源分配的基本單位。處理機(jī)調(diào)度的基本單位，與資源分配處理機(jī)調(diào)度的基本單位，與資源分配無(wú)關(guān)，多個(gè)線程共享所屬進(jìn)程的資源。無(wú)關(guān)，多個(gè)線程共享所屬進(jìn)程的資源。不同進(jìn)程有不同的虛擬地址空不同進(jìn)程有不同的虛擬地址空間，有外存掛起狀態(tài)。間，有外存掛起狀態(tài)

34、。同一進(jìn)程內(nèi)的線程共享同一地址空間，同一進(jìn)程內(nèi)的線程共享同一地址空間，無(wú)外存掛起狀態(tài)。無(wú)外存掛起狀態(tài)。進(jìn)程存在的標(biāo)志：進(jìn)程存在的標(biāo)志：進(jìn)程控制塊進(jìn)程控制塊PCB上下文切換時(shí)間長(zhǎng)上下文切換時(shí)間長(zhǎng)線程的存在標(biāo)志：線程的存在標(biāo)志：線程控制表線程控制表TCB及相關(guān)堆棧和寄存器及相關(guān)堆棧和寄存器上下文切換時(shí)間短上下文切換時(shí)間短43線程控制塊線程控制塊TCB的內(nèi)容的內(nèi)容1、線程的狀態(tài)；、線程的狀態(tài)；2、CPU現(xiàn)場(chǎng)信息現(xiàn)場(chǎng)信息:PC、PSW、通用寄存器、堆棧指針、通用寄存器、堆棧指針44三、線程的特點(diǎn)三、線程的特點(diǎn)1、由進(jìn)程所創(chuàng)建，一個(gè)進(jìn)程至少創(chuàng)建一個(gè)線程，線程也可、由進(jìn)程所創(chuàng)建，一個(gè)進(jìn)程至少創(chuàng)建一個(gè)線程，

35、線程也可以創(chuàng)建線程；以創(chuàng)建線程；2、線程不擁有資源，只共享所屬進(jìn)程的資源；、線程不擁有資源，只共享所屬進(jìn)程的資源；3、同一進(jìn)程下的線程運(yùn)行在相同的地址空間；、同一進(jìn)程下的線程運(yùn)行在相同的地址空間；4、線程之間需要互斥和同步機(jī)制；、線程之間需要互斥和同步機(jī)制；5、線程有生命期，在生命期中有狀態(tài)的變化；、線程有生命期，在生命期中有狀態(tài)的變化；6、類(lèi)似程序，但一般不是完整的程序。、類(lèi)似程序，但一般不是完整的程序。45四、線程的狀態(tài)四、線程的狀態(tài)1、就緒：就緒：具備運(yùn)行條件，只等具備運(yùn)行條件，只等CPU；2、執(zhí)行：執(zhí)行：占有占有CPU運(yùn)行；運(yùn)行；3、阻塞：阻塞：因?yàn)槟呈录尦鲆驗(yàn)槟呈录尦鯟PU，等待

36、；，等待；46五、線程的優(yōu)點(diǎn)五、線程的優(yōu)點(diǎn)1、創(chuàng)建和撤消線程、線程切換的開(kāi)銷(xiāo)小，提高了并發(fā)效率；、創(chuàng)建和撤消線程、線程切換的開(kāi)銷(xiāo)小，提高了并發(fā)效率；一個(gè)進(jìn)程的開(kāi)銷(xiāo)大約是一個(gè)線程開(kāi)銷(xiāo)的一個(gè)進(jìn)程的開(kāi)銷(xiāo)大約是一個(gè)線程開(kāi)銷(xiāo)的30倍左右倍左右.2、線程共享同一地址空間的內(nèi)存和文件，減少了通信的開(kāi)、線程共享同一地址空間的內(nèi)存和文件，減少了通信的開(kāi)銷(xiāo)；銷(xiāo)；3、減少用戶(hù)等待時(shí)間，提高系統(tǒng)響應(yīng)速度；、減少用戶(hù)等待時(shí)間，提高系統(tǒng)響應(yīng)速度；4、促使用戶(hù)設(shè)計(jì)出邊界清晰、模塊獨(dú)立性好的程序。、促使用戶(hù)設(shè)計(jì)出邊界清晰、模塊獨(dú)立性好的程序。47六、線程的使用范圍六、線程的使用范圍1、多處理機(jī)系統(tǒng)：、多處理機(jī)系統(tǒng)：用戶(hù)程序根

37、據(jù)功能劃分成不同線程，放在不同處用戶(hù)程序根據(jù)功能劃分成不同線程，放在不同處理機(jī)上運(yùn)行。理機(jī)上運(yùn)行。2、單處理機(jī)系統(tǒng)：、單處理機(jī)系統(tǒng)：1）多個(gè)用戶(hù)對(duì)文件服務(wù)器提出文件訪問(wèn)請(qǐng)求；）多個(gè)用戶(hù)對(duì)文件服務(wù)器提出文件訪問(wèn)請(qǐng)求；2）前臺(tái)和后臺(tái)的分工處理；）前臺(tái)和后臺(tái)的分工處理；3）異步處理；）異步處理；4）加快執(zhí)行速度；）加快執(zhí)行速度；5）組織復(fù)雜的工作；）組織復(fù)雜的工作；48七、線程的分類(lèi)七、線程的分類(lèi)1、用戶(hù)級(jí)線程：、用戶(hù)級(jí)線程：用戶(hù)程序在用戶(hù)空間執(zhí)行線程庫(kù)，創(chuàng)建、調(diào)度、用戶(hù)程序在用戶(hù)空間執(zhí)行線程庫(kù)，創(chuàng)建、調(diào)度、撤消線程，操作系統(tǒng)內(nèi)核只管理進(jìn)程；撤消線程，操作系統(tǒng)內(nèi)核只管理進(jìn)程；用戶(hù)級(jí)線程調(diào)度只進(jìn)行線程

38、上下文切換，不涉及用戶(hù)級(jí)線程調(diào)度只進(jìn)行線程上下文切換，不涉及處理機(jī)狀態(tài)，與內(nèi)核無(wú)關(guān)；處理機(jī)狀態(tài)，與內(nèi)核無(wú)關(guān)；2、系統(tǒng)級(jí)線程：、系統(tǒng)級(jí)線程：操作系統(tǒng)內(nèi)核進(jìn)行管理，內(nèi)核提供系統(tǒng)調(diào)用和應(yīng)操作系統(tǒng)內(nèi)核進(jìn)行管理，內(nèi)核提供系統(tǒng)調(diào)用和應(yīng)用程序接口創(chuàng)建、調(diào)度、撤消線程；用程序接口創(chuàng)建、調(diào)度、撤消線程；負(fù)責(zé)進(jìn)程和線程的調(diào)度；負(fù)責(zé)進(jìn)程和線程的調(diào)度；49例：例：Linux下的多線程程序下的多線程程序 example.c#include #include void thread(void) int i; for(i=0;i3;i+) printf(This is a pthread.n);int main(void)

39、 pthread_t id; int i,ret; ret=pthread_create(&id,NULL,(void *) thread,NULL); if(ret!=0) printf (Create pthread error!n); exit (1); for(i=0;i3;i+) printf(This is the main process.n); pthread_join(id,NULL); return (0);50相關(guān)函數(shù)相關(guān)函數(shù)函數(shù)函數(shù)pthread_create用來(lái)創(chuàng)建一個(gè)線程用來(lái)創(chuàng)建一個(gè)線程：第一個(gè)參數(shù)為指向線程標(biāo)識(shí)符的指針，第二個(gè)參數(shù)用來(lái)設(shè)置線程屬性，第一個(gè)參

40、數(shù)為指向線程標(biāo)識(shí)符的指針，第二個(gè)參數(shù)用來(lái)設(shè)置線程屬性，第三個(gè)參數(shù)是線程運(yùn)行函數(shù)的起始地址，最后一個(gè)參數(shù)是運(yùn)行函數(shù)的參數(shù)。第三個(gè)參數(shù)是線程運(yùn)行函數(shù)的起始地址，最后一個(gè)參數(shù)是運(yùn)行函數(shù)的參數(shù)。創(chuàng)建線程成功后，新創(chuàng)建的線程則運(yùn)行參數(shù)三和參數(shù)四確定的函數(shù)，創(chuàng)建線程成功后，新創(chuàng)建的線程則運(yùn)行參數(shù)三和參數(shù)四確定的函數(shù)，原來(lái)的線程則繼續(xù)運(yùn)行下一行代碼。原來(lái)的線程則繼續(xù)運(yùn)行下一行代碼。函數(shù)函數(shù)pthread_join用來(lái)等待一個(gè)線程的結(jié)束用來(lái)等待一個(gè)線程的結(jié)束：第一個(gè)參數(shù)為被等待的線程標(biāo)識(shí)符，第二個(gè)參數(shù)為一個(gè)用戶(hù)定義的指第一個(gè)參數(shù)為被等待的線程標(biāo)識(shí)符，第二個(gè)參數(shù)為一個(gè)用戶(hù)定義的指針，它可以用來(lái)存儲(chǔ)被等待線程的返

41、回值。針，它可以用來(lái)存儲(chǔ)被等待線程的返回值。這個(gè)函數(shù)是一個(gè)線程阻塞的函數(shù)，調(diào)用它的函數(shù)將一直等待到被等待這個(gè)函數(shù)是一個(gè)線程阻塞的函數(shù)，調(diào)用它的函數(shù)將一直等待到被等待的線程結(jié)束為止，當(dāng)函數(shù)返回時(shí)，被等待線程的資源被收回。的線程結(jié)束為止，當(dāng)函數(shù)返回時(shí)，被等待線程的資源被收回。編寫(xiě)運(yùn)行編寫(xiě)運(yùn)行Linux下的多線程程序，需要使用頭文件下的多線程程序，需要使用頭文件pthread.h，連接時(shí)，連接時(shí)需要使用庫(kù)需要使用庫(kù)libpthread.a。 gcc example.c -lpthread -o example51我們可能得到如下結(jié)果：我們可能得到如下結(jié)果：This is a pthread.This is a pthread.This is a pthread.This is the main process.This is the main process.This is the main process.運(yùn)行結(jié)果不一樣，是兩個(gè)線程爭(zhēng)奪運(yùn)行結(jié)果不一樣，是兩個(gè)線程爭(zhēng)奪CP