操作系統(tǒng)原理進程管理課件

第二章

進程管理進程的概念進程的控制進程同步及經(jīng)典同步問題進程間的高級通信進程與線程的區(qū)別2023/7/25

02:03操作系統(tǒng)|進程管理

22.1 前趨圖和程序執(zhí)行前趨圖的定義前趨圖（ProcedenceGraph）是一個有向無循環(huán)圖DAG（DirectedAcyclicGraph）。結點：語句、程序段或進程。初始節(jié)點終止節(jié)點邊：執(zhí)行順序。重量：程序量或執(zhí)行時間。2023/7/25

02:03操作系統(tǒng)|進程管理

31234567例：有7個結點的前趨圖。P={P1，P2，P3，P4，P5，P6，P7}→={（P1，P2），（P1，P3），（P1，P4），（P2，P5），（P3，P5），（P4，P6），（P5，P7），（P6，P7）}2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

4程序的順序執(zhí)行一個復雜的程序通?？梢苑譃槿舾沙绦蚨危⑶冶仨毎凑漳撤N先后次序來執(zhí)行。例1：輸入——計算——打印例2：語句執(zhí)行順序S1：a：=x+yS2：b：=a–5S3：c：=b+12.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

5順序執(zhí)行程序的特點：程序的順序性。程序在運行時獨占主機資源。程序的執(zhí)行結果與其執(zhí)行速度無關。程序執(zhí)行時的初始條件相同，其結果必相同。2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

6程序的并發(fā)執(zhí)行程序執(zhí)行環(huán)境獨立性，邏輯上是獨立的。隨機性：輸入和執(zhí)行開始時間都是隨機的。資源共享：資源共享導致對進程執(zhí)行速度的制約。2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

7程序的并發(fā)執(zhí)行并發(fā)執(zhí)行是指兩個程序執(zhí)行時間上是重疊的。凡是能由一組并發(fā)程序完成的任務，都能由相應的單個程序完成。例1：有一批程序，而每個程序需輸入，計算，打印三項操作。其程序段并發(fā)執(zhí)行的前趨圖:I1→I2→I3→I4→ ↘↘↘↘ C1→C2→C3→C4→ ↘↘↘↘ P1→P2→P3→P4→2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

8

例2．BeginintegerN:=0; Cobegin ProgramA:begin ProgramB:begin

L1:N:=N+1; L2:Print(N);N:=0; GotoL1； GotoL2；

End End Coend End當N=5時，如果N=N+1在print（N）和N:=0

前 中間 后打印 6 5 5執(zhí)行后N= 0 0 12.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

9例3．設有堆棧S，棧指針top，棧中存放相應的數(shù)據(jù)塊地址，程序popaddr（top）從棧中取地址，pushaddr（blk）將地址放入棧S中。voidpopaddr(top) {voidpushaddr(blk){

top--;

*top=blk; r=*top; top++; return(r)} }先執(zhí)行popaddr的top--，接著執(zhí)行pushaddr的*top=blk2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

10程序并發(fā)執(zhí)行過程及條件（Bernstein條件）

S0; Cobegin S1；S2；S3；……；Sn; Coend Sn+1;

S1、S2、……、Sn可以由同一程序段中的不同語句組成。2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

11

將任一語句劃分為兩個變量的集合R（Si）和W（Si）:

讀集R（Si）={a1，a2，……，am}

寫集W（Si）={b1，b2，……，bn}

如對語句S1和S2有：

R（S1）∩W（S2）={Ф} W（S1）∩R（S2）={Φ} W（S1）∩W（S2）={Φ}

成立，則語句S1和S2可并發(fā)執(zhí)行。2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

12例1．

語句c=a–b和w=c+1 R（c=a–b）={a,b} W（c=a–b）={c} R（w=c+1）={c} W（w=c+1）={w} R（w=c+1）∩W（c=a–b）={c}

語句c=a–b和w=c+1不能并發(fā)執(zhí)行。2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

13例2．S1:a=x+y S2:b=z+1 S3:c=a–b S4:w=a+c+1R（S1）={x,y} W（S1）={a} R（S2）={z} W（S2）= R（S3）={a,b} W（S3）={c} R（S4）={a,c} W（S4）={w}

語句S1和S2能并發(fā)執(zhí)行。語句S1和S3，S2和S3，S3和S4不能并發(fā)執(zhí)行。

S1 S3→ S4S22.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

14資源共享資源共享是指系統(tǒng)中的硬件資源和軟件資源不再由單個用戶所獨占，而為n個用戶共同使用。由系統(tǒng)進行統(tǒng)一分配（硬件）和由程序自行使用（數(shù)據(jù)集，變量、隊列等）程序并發(fā)執(zhí)行與資源共享之間互為存在條件。2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

15程序并發(fā)執(zhí)行的特點失去程序的封閉性和可再現(xiàn)性程序與計算不再一一對應程序并發(fā)執(zhí)行的相互制約執(zhí)行——暫?！獔?zhí)行2.1 前趨圖和程序執(zhí)行2023/7/25

02:03操作系統(tǒng)|進程管理

162.2 進程的概念進程的定義進程的定義:進程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進行資源分配和調度的一個獨立的基本單位。進程的特征動態(tài)性并發(fā)特征獨立特征異步特征機構特征2023/7/25

02:03操作系統(tǒng)|進程管理

17進程與程序的關系

進程 程序

概念動態(tài)實體， 靜態(tài)實體， 強調執(zhí)行過程 是指令的有序集合

特征并發(fā)性、獨立性、 無并行特征， 異步性， 是靜止的 是競爭計算機系統(tǒng) 資源的基本單位兩者聯(lián)系不同的進程可以共享同一個程序， 只要對應的數(shù)據(jù)集不同2.2 進程的概念2023/7/25

02:03操作系統(tǒng)|進程管理

18進程的組成（進程上下文）PCB程序

數(shù)據(jù)進程控制塊PCB描述信息控制信息資源管理信息CPU現(xiàn)場保護：對CPU的處理2.2 進程的概念2023/7/25

02:03操作系統(tǒng)|進程管理

19PCB的組織方式鏈接方式將具有相同狀態(tài)的PCB，用其中的鏈接字，鏈接成一個隊列。2.2 進程的概念2023/7/25

02:03操作系統(tǒng)|進程管理

20索引方式根據(jù)進程的狀態(tài)，建立索引表。2023/7/25

02:03操作系統(tǒng)|進程管理

212.3 進程狀態(tài)及其控制進程狀態(tài)一個進程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻畫了這個進程。系統(tǒng)根據(jù)PCB結構中的狀態(tài)值控制進程。就緒狀態(tài)（Ready）執(zhí)行狀態(tài)（Running）等待狀態(tài)（阻塞狀態(tài)Blocked）新（New）狀態(tài)終止狀態(tài)（TerminatedorExit）2023/7/25

02:03操作系統(tǒng)|進程管理

22掛起狀態(tài)（Suspend）把一個進程掛起使之處于靜止狀態(tài)，以便研究它的執(zhí)行情況獲對它進行修改。用戶終端需要；父進程的需要：考查、修改獲協(xié)調各子進程時；OS的需要：改善系統(tǒng)運行性能，調節(jié)負荷；對換的需要：緩和內存緊張的情況；2.3 進程狀態(tài)及其控制2023/7/25

02:03操作系統(tǒng)|進程管理

23進程狀態(tài)轉換三種基本狀態(tài)：執(zhí)行狀態(tài)（Executing）就緒狀態(tài)（Ready）阻塞狀態(tài)（Blocked）或等待（Wait）

阻塞狀態(tài)就緒狀態(tài)

執(zhí)行狀態(tài)調度I/O請求進程喚醒時間片到新狀態(tài)結束后備隊列新狀態(tài)結束狀態(tài)2.3 進程狀態(tài)及其控制2023/7/25

02:03操作系統(tǒng)|進程管理

242023/7/25

02:03操作系統(tǒng)|進程管理

25細化的進程狀態(tài)圖（增加掛起）活動阻塞執(zhí)行狀態(tài)活動就緒靜止就緒靜止阻塞調度喚醒I/O請求激活激活掛起掛起掛起喚醒2.3 進程狀態(tài)及其控制2023/7/25

02:03操作系統(tǒng)|進程管理

26活動就緒（Readya）和活動阻塞（Blockeda）靜止就緒（Readys）和靜止阻塞（Blockeds）2.3 進程狀態(tài)及其控制2023/7/25

02:03操作系統(tǒng)|進程管理

27一個狀態(tài)轉換和進程轉換的例子進程AI/O驅動中斷處理進程BI/O現(xiàn)場保護和阻塞A啟動I/O調度，恢復B現(xiàn)場I/O中斷現(xiàn)場保護中斷處理A就緒調度，恢復A現(xiàn)場退出（收回資源，調度）注：紅色表示處于“管態(tài)”2.3 進程狀態(tài)及其控制2023/7/25

02:03操作系統(tǒng)|進程管理

282.4 進程控制進程間的關系非結構系統(tǒng)（UnstructuredSystem）樹形結構系統(tǒng)（Tree-StructuredSystem）:

一個進程能創(chuàng)建另一個進程，形成進程家族。2023/7/25

02:03操作系統(tǒng)|進程管理

29操作系統(tǒng)內核（Kernel）支撐功能中斷處理時鐘管理原語操作：完成特定功能的一段程序。原語在執(zhí)行期間是不可分割的。資源管理功能進程管理存儲器管理設備管理

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

30進程的創(chuàng)建引起進程創(chuàng)建的事件用戶登錄作業(yè)調度提供服務應用請求(應用程序創(chuàng)建)創(chuàng)建過程Create()申請空白PCB：新標識和PCB為新進程分配資源：批處理型和交互型作業(yè)初始化進程控制塊新進程插入就緒隊列2023/7/25

02:03操作系統(tǒng)|進程管理

31創(chuàng)建原語（CreatePrimitive）VoidCreate(n,S0,P0,M0,R0,acc){ i=getinternalname(n); id(i)=n; priority(i)=P0; cpupstate(i)=S0; mainstore(i)=M0; resources(i)=R0; status(i)=“readys”; setaccountingdata; insert(RL,i);}

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

32進程的終止進程終止的事件正常結束：Holt指令（引發(fā)中斷）異常結束：越界錯誤保護錯非法指令錯特權指令錯運行超時等待超時算術運算錯I/O故障外界干預：人工或系統(tǒng)干預、父進程請求、父進程終止2023/7/25

02:03操作系統(tǒng)|進程管理

33撤消原語（DestroyPrimitive）Voiddestroy(n){ sched=false; i=getinternalname(n); Kill(i); Ifschedthenscheduler; }

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

34Kill過程：1、從PCB中讀出進程狀態(tài)；2、終止進程并設置調度標志為真；3、終止所有子進程；4、釋放擁有的全部資源并歸還父進程或系統(tǒng)；5、將終止進程從所在隊列（PCB）中移出2023/7/25

02:03操作系統(tǒng)|進程管理

35進程阻塞引起進程阻塞的事件1、請求系統(tǒng)服務2、啟動某種操作3、數(shù)據(jù)尚未到達4、無新工作可做阻塞原語的主要工作停止目前工作，存CPU下場到PCB中；將PCB中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”；將PCB插入相應的阻塞隊列中將CPU的控制權交下一就緒狀態(tài)的進程

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

36阻塞原語（BlockPrimitive）Void block(n){ i=getinternalname(n); stop(i); status(i)=“blockeda”; insert(WL(r),i); scheduler; }

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

37進程的喚醒進程喚醒的事件喚醒原語（WakeupPrimitive）Voidwakeup(n){ i=getinternalname(n); remove(WL(r),i); status=“ready”; insert(RL,i); scheduler; }

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

38進程的掛起（Suspend）掛起方式1、把發(fā)出本原語的進程自身掛起；2、掛起指定進程名（子進程）的進程；3、把某進程及其全部或部分子孫一起掛起。掛起操作檢查被掛起進程的狀態(tài)，根據(jù)原狀態(tài)設置掛起后的狀態(tài)把PCB復制到特定的內存區(qū)域若掛起前該進程正在執(zhí)行，則由調度程序進行重新調度。

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

39方式2掛起原語（SuspendPrimitive）Voidsuspend(n,a){ i=getinternalname(n); s=status(i); ifs=“executing”thenstop(i); a=copyPCB(i); status(i)=ifs=“blockeda”then“blockeds”; else“readys”; ifs=“executing”thenscheduler; }

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

40進程的激活進程激活過程激活原語（ActivatePrimitive）由創(chuàng)建原語創(chuàng)建的進程處于“靜止就緒“狀態(tài)，后跟一個激活原語，使之變?yōu)榛钴S就緒，就能引起CPU的重新調度。

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

41Voidactivate(n){ i=getinternalname(n); status(i)=ifstatus=“readys”then“readya”; else“blockeda”; ifstatus(i)=“readya”thenscheduler;}

2.4 進程控制2023/7/25

02:03操作系統(tǒng)|進程管理

422.5 進程同步并發(fā)引起的操作系統(tǒng)的改變操作系統(tǒng)必須記住各種活躍的進程必須為每個進程分配和釋放各種資源保護每個進程的數(shù)據(jù)和物理資源進程的結果必須與執(zhí)行速度無關2023/7/25

02:03操作系統(tǒng)|進程管理

43進程間的制約進程中的資源競爭（間接）進程間通過共享的合作（直接）進程間通過通信的合作（直接）進程間的制約臨界區(qū)臨界資源（CriticalResource）：一次僅允許一個進程使用的資源。

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

44例1：兩個進程對同一變量count訪問和修改，P1：

count+=1; P2：

count-=1;若count=5。P1：

R1=count; R1=R1+1; count=R1;P2：

R2=count; R2=R2-1; count=R2;若順序執(zhí)行P1、P2，則count=5。

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

45P1： R1=count; P1： R1=count;P2： R2=count; R1=R1+1;P1： R1=R1+1; P2： R2=count; count=R1; R2=R2–1;P2： R2=R2–1; count=R2; count=R2;P1： count=R1;若執(zhí)行順序如上， 若執(zhí)行順序如上，則count=4 則count=6。

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

46與時間有關的錯誤:理發(fā)師問題發(fā)師床X顧客床Y理發(fā)館理發(fā)椅顧客床有人喚醒顧客理發(fā)去發(fā)師床睡NY被喚醒理發(fā)師發(fā)師床有人喚醒發(fā)師理發(fā)去顧客床睡NY被喚醒顧客床有人離開NY顧客理發(fā)師讀Y 顧客讀Y

寫X 讀X

寫Y2023/7/25

02:03操作系統(tǒng)|進程管理

47cobeginprocess1;process2：coend

2.5 進程同步臨界區(qū)：不允許多個并發(fā)進程交叉執(zhí)行的一段程序process1：beginL1：entrysectionCS1;exitsectionRemainderofrocess1;GotoL1;endprocess2：beginL2：entrysectionCS2;exitsectionRemainderofrocess2;GotoL1;end2023/7/25

02:03操作系統(tǒng)|進程管理

48互斥不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為互斥。臨界區(qū)調度原則空閑讓進忙則等待有限等待讓權等待

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

49互斥的軟件實現(xiàn)算法1:

進程Pi，Pj共享臨界資源R。Turn：進程編號。算法1：共享一個公用整型變量turnvoidPi(){…… while(true){

while(turn!=i);//資源被j進程用，空轉

criticalsection

turn=j; //把資源控制權交給j remaindersection }}

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

50算法2：用數(shù)組代替算法一中的turnintflag[n]={0,0…,0};voidPi(){while(true){for(j=0;j<n;j++)if(flag[j])j=0;//資源被用，空轉

flag[i]=1;//讓i

進程獲得資源

criticalsection

flag[i]=0; //放棄資源控制權

remaindersection}}

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

51算法3：intflag[n]={0,0…,0};voidPi(){while(true){ flag[i]=1;

for(j=0;j<n;j++)if(flag[j])j=0;

criticalsection

flag[i]=0; remaindersection}}

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

52算法4：進程共享兩個公用變量boolean[]flag=newboolean[2];intturn=0;publicvoidP0(){while(true){flag[0]=true;turn=1;while(flag[1]&&turn==1)；

<criticalsection>;flag[0]=false;<remainder>;}}publicvoidP1(){while(true){flag[1]=true;turn=0;while(flag[0]&&turn==0);<criticalsection>;flag[1]=false;<remainder>；}}

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

53publicstaticvoidmain(){flag[0]=false;flag[1]=false;parbegin(P0,P1);}

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

54算法5：對臨界區(qū)S設置一個變量狀態(tài)W，W=0表示資源可用，W=1表示資源已被占用。例：BeginintegerW=0; Cogegin Begin L1：lockW; CS1; UnlockW; Remainderofprocess1; GotoL1; End Begin L2：lockW; CS2; UnlockW; Remainderofprocess2; GotoL2; End Coend End

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

55關鎖原語lockW： ifW=1then begin block(n); insert(WL,n); scheduler; end else W=1;

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

56開鎖原語unlockW：ifWL<>NULLthen begin remove(WL,q); status(q)=“ready”; insert(RL,q); end else W=0;

2.5 進程同步2023/7/25

02:03操作系統(tǒng)|進程管理

572.6 信號量機制及其應用整型信號量機制信號量(sem)sem>=0:表示可供并發(fā)進程使用的資源實體的個數(shù)sem<0:表示正在等待使用臨界區(qū)的進程數(shù)。Sem的值只能由P、V操作改變。P：wait(s)V：signal(s)按信號量數(shù)值分為二元信號量和一般信號量。2023/7/25

02:03操作系統(tǒng)|進程管理

58Wait（P）和signal（V）原語Wait(s)原語structsemaphore{intcount;QueueTypeQueue;}voidwait(s){s.count--;if(s.count<0){placethisprocessins.queue;blockthisprocess;}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

59signal原語voidsignal(s){s.count++;if(s.count<=0){removeaprocessPfroms.queue;placeprocessPonreadylist;}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

60利用信號量實現(xiàn)互斥publicclassmutualexclusion{staticfinalintn=<numberofprocesses>;semaphores=newsemaphore(1);publicvoidP(inti){while(true){wait(s);<criticalsection>;signal(s);<remainder>;}}publicstaticvoidmain(){parbegin(P(1),P(2),...,P(n));}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

61利用信號量描述前趨關系P1：S1P2：S2S1——>S2則設置信號量s=0，P1：S1；signal(s)；P2：Wait(s)；S2；

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

621234567abcdefgh例：根據(jù)前趨圖寫出可并發(fā)執(zhí)行的程序：

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

63vara,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0;begin parbegin beginS1;signal(a);signal(b);signal(c);end beginwait(a);S2;signal(d);end beginwait(b);S3;signal(e);end beginwait(c);S4;signal(f);end beginwait(d);S5;signal(g);end beginwait(e);wait(f);S6;signal(h);end beginwait(g);wait(h);S7;end parendend

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

64信號量集機制AND型信號量集機制問題引入進程A、B訪問共享數(shù)據(jù)D和E

信號量Dmutex=1，Emutex=1processA: wait(Dmutex); wait(Emutex);

processB: wait(Emutex); wait(Dmutex);

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

65A、

B交替執(zhí)行：processA: wait(Dmutex); 則Dmutex=0processB:wait(Emutex); 則Emutex=0processA: wait(Emutex); 則Emutex=-1，阻塞processB: wait(Dmutex); 則Dmutex=-1，阻塞發(fā)生死鎖。

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

66AND同步機制的思想Swait(S1,S2,…,Sn){ if(S1>=1&&S2>=1&&…&&Sn>=1) for(i=1;i<=n;i++) Si--; else{

將進程插入第i（Si<1）個等待隊列;

設置該進程的程序計數(shù)器到Swait操作的開始;}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

67Ssignal(S1,S2,…,Sn){ for(i=1;i<=n;i++){ Si++;

將所有等待Si資源的進程移到就緒隊列。

}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

68一般“信號量”機制Swait(S1,t1,d1;…;Sn,tn,dn){ if(S1>=t1&&S2>=t2&&…&&Sn>=tn) for(i=1;i<=n;i++) Si–=di; else{

將執(zhí)行進程插入第i（Si<ti）個等待隊列;

設置該進程的程序計數(shù)器到Swait操作的開始;}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

69Ssignal(S1,d1,…;Sn,dn){ for(i=1;i<=n;i++){ Si+=di;

將所有等待Si資源的進程移到就緒隊列;}}

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

70特例：

Swait(S,d,d)：一個信號量，可每次申請d個資源；

Swait(S,1,1)：記錄型信號量（S>1）或互斥信號量（S=1）；

Swait(S,1,0)：當S>=1，允許多個進程進入某臨界區(qū)；當S=0后，阻止任何進程進入臨界區(qū)。

2.6 信號量機制及其應用2023/7/25

02:03操作系統(tǒng)|進程管理

71

例2：打印進程與計算進程的同步問題

設：SA—

打印進程的私有信號量，初值為0，

當SA=1

時表示可以打印。

SB—

計算進程的私有信號量，初值為0，

當SB=0時表示可以放入計算結果。緩沖區(qū)計算打印機緩沖區(qū)打印進程計算進程SASB緩沖區(qū)緩沖區(qū)緩沖區(qū)同步的概念2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

72???

計算結果放入緩沖區(qū)；T2:signal(SA)；L1:wait（SB）；???

顯然，進程CP與進程IOP相互制約：①只有CP執(zhí)行到T2，IOP才能執(zhí)行T1。（T2T1）②只有IOP執(zhí)行到L2，CP才能執(zhí)行L1。（L2L1）計算進程與打印進程同步的模型計算進程CP打印進程IOP???T1:wait（SA）；

從緩沖區(qū)取結果；L2:signal（SB）；???SA，SB初值為02.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

73異步環(huán)境相互合作的一組并發(fā)進程，其中每一進程都能以各自獨立的，不可預知的速度向前推進。進程同步相互合作的進程之間需要交換一定的信息，當某進程未獲得其合作進程發(fā)來的信息之前，該進程等待，直到該信息到來時才被喚醒繼續(xù)執(zhí)行，從而保證諸進程的協(xié)調運行。2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

74生產(chǎn)者—消費者問題綜述問題描述通過由n個環(huán)形緩沖區(qū)構成的緩沖池，把生產(chǎn)者P1，P2，……，PM和一群消費者C1，C2，……，CK聯(lián)系起來。算法描述2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

752023/7/25

02:03操作系統(tǒng)|進程管理

76變量定義：beginVarmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

77parbeginproducer: begin repeat producenextproduct;

wait(empty); wait(mutex);

buffer(in):=nextp; in:=(in+1)modn;

signal(full); signal(mutex); untilfalse; end2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

78consumer:begin repeat

wait(full); wait(mutex);

nextc:=buffer(out); out:=(out+1)modn;

signal(empty); signal(mutex); consumetheiteminnextc; untilfalse; end parend end2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

79wait(empty) empty>=0 則數(shù)據(jù)送入緩沖區(qū)

empty<0 被阻塞（滿）signal(empty) empty>0 empty<=0 釋放一個空緩沖區(qū)，喚醒一個阻塞的生產(chǎn)者進程2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

80wait(full) full>=0 則從緩沖區(qū)取走數(shù)據(jù)

full<0 被阻塞（空）signal(full) full>0 full<=0 數(shù)據(jù)裝入緩沖區(qū)，喚醒一個 阻塞的消費者進程2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

81注意：互斥和同步信號量的原語必須成對出現(xiàn)。signal操作的次序無關緊要，但wait操作的次序不能顛倒，否則會造成死鎖。用AND信號量解決生產(chǎn)者——消費者問題2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

82用AND信號量解決生產(chǎn)者——消費者問題parbeginproducer: begin repeat producenextp; Swait(empty,mutex); buffer(in):=nextp; in:=(in+1)modn; Ssignal(mutex,full); untilfalse; end2023/7/25

02:03操作系統(tǒng)|進程管理

83哲學家進餐問題2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

84publicclassdiningphilosophers{ semaphore[]fork=newsemaphore[5](1); inti;2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

85 publicvoidphilosopher(inti){ while(true){ think();

wait(fork[i]); wait(fork[(i+1)%5]);

eat();

signal(fork[(i+1)%5]); signal(fork[i]); } }2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

86publicstaticvoidmain(){ parbegin(philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4)); }}2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

87解決死鎖的方法：至多允許四個哲學家同時進餐。僅當哲學家的左右兩支叉子均可用時，才進餐。（用AND信號量機制解決哲學家進餐問題。）奇數(shù)號哲學家先拿左邊的叉子，偶數(shù)號哲學家先拿右邊的叉子。2.7

經(jīng)典進程同步問題2023/7/25

02:03操作系統(tǒng)|進程管理

88讀者——寫者問題

讀者進程:可以同時讀一個共享資源;

寫者進程:互斥的存取共享對象;

讀寫進程同步:必須保證一個寫進程與其它進程互斥地訪問共享資源.Readcount:描述讀者數(shù)目的臨界資源.publicclassReadersAndWriters{ intreadcount; semaphorermutex=newsemaphore(1); semaphorewmutex=newsemaphore(1);2023/7/25

02:03操作系統(tǒng)|進程管理

89publicvoidreader(){

while(true){ wait(rmutex); if(readcount==0) wait(wmutex); readcount++; signal(rmutex); READUNIT(); wait(rmutex); readcount--; if(readcount==0) signal(wmutex); signal(rmutex); }}2023/7/25

02:03操作系統(tǒng)|進程管理

90publicvoidwriter(){ while(true){ wait(wmutex); WRITEUNIT(); signal(wmutex); } }2023/7/25

02:03操作系統(tǒng)|進程管理

912.8 管程機制管程的基本概念管程的定義：一個管程定義了一個數(shù)據(jù)結構和能為迸發(fā)進程所執(zhí)行(在該數(shù)據(jù)結構上)的一組操作,這組操作能同步進程和改變管程中的數(shù)據(jù)。這些數(shù)據(jù)及操作對進程是透明的，局部于管程的數(shù)據(jù)結構只能被該管程的過程訪問。管程組成：1、局部共享變量說明，2、內部對數(shù)據(jù)結構的操作，3、局部數(shù)據(jù)的置初值。 任何進程訪問共享資源，只能通過調用管程中的過程（管程名.過程名）,而管程每次只允許一個進程進入管程，從而實現(xiàn)進程互斥條件變量：2023/7/25

02:03操作系統(tǒng)|進程管理

92管程的語法說明：一個進程訪問臨界資源TYPESSU=MonitorVarbusy:boolean;nobusy:condition;definerequire,returnProcedurerequireBeginifbusythennobusy.waitbusy:=trueEnd;ProcedurereturnBeginbusy:=false;nobusy.signal;End//initializationcodeBegin busy:=false;End2023/7/25

02:03操作系統(tǒng)|進程管理

932.8 管程機制條件變量：利用管程實現(xiàn)同步時，必須設置同步原語操作（wait和signal），由管程調用實現(xiàn)阻塞和喚醒。為了區(qū)別阻塞的原因，引入條件變量（在管程中說明），由條件變量來調用Wait、Signal原語操作。

conditionVARx,y:condition

……x.wait;y.signal在管程中，y.signal操作的作用是啟動一個被阻塞的進程，但如果阻塞隊列沒有進程時，y.signal不產(chǎn)生任何操作。如果進程Q處于阻塞隊列的首部，當前進程P執(zhí)行了y.signal，管程的處理方式1、P等待，直至Q離開管程或等待另一條件；2、Q等待，直至P離開管程或等待另一條件；2023/7/25

02:03操作系統(tǒng)|進程管理

942.8 管程機制用管程解決生產(chǎn)者-消費者問題TypePC=monitorVarin,out,count:integer;Buffer:array[0,…,n-1]ofitem;Full,Empty:condition;ProcedureEntryput(item)beginifcount>=nthen Full.wait;Buffer(in):=nextp;in:=(in+1)modn;count:=count+1;IfEmpty.queuethen Empty.signalendProcedureEntryget(item)beginifcount<=0then Empty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifFull.queuethen Full.signalendBeginin:=0;out:=0;count:=0;end2023/7/25

02:03操作系統(tǒng)|進程管理

95Producer:Beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endConsumer:BeginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end2.8 管程機制2023/7/25

02:03操作系統(tǒng)|進程管理

96進程通信

進程之間的信息交換稱為進程通信。1、低級通信：（信息量少）同步與互斥的進程間通過修改信號量,其缺點:1、效率低，2、不透明。2、高級通信：（大量數(shù)據(jù)）通過操作系統(tǒng)提供的一組通信命令，高效地傳送大量數(shù)據(jù)，通信過程對用戶透明。優(yōu)點：1、數(shù)據(jù)量大，2、減少通信程序編制上的復雜性。2023/7/25

02:03操作系統(tǒng)|進程管理

97進程通信進程通訊類型共享存儲系統(tǒng)、消息傳遞系統(tǒng)、管道通信系統(tǒng)共享存儲系統(tǒng)（Shared-MemorySystem）：由通信進程共享某些數(shù)據(jù)結構或共享存儲區(qū)?；诠蚕頂?shù)據(jù)結構的通信方式：公用數(shù)據(jù)結構的設置及對進程間同步的處理，都必須由程序員管理，操作系統(tǒng)只提供共享存儲器，因此效率低，只適用少量數(shù)據(jù)傳遞。基于共享存儲區(qū)的通信方式：進程在通信前，先向系統(tǒng)申請共享存儲區(qū)（系統(tǒng)劃分）中的一個分區(qū)，并指定關鍵字（若該分區(qū)已為其它進程擁有，則向申請者返回描述符），由申請者把獲得的共享存儲分區(qū)連接到自己進程。適用于大量數(shù)據(jù)傳遞。2023/7/25

02:03操作系統(tǒng)|進程管理

98管道通信管道（pipe）指用于連接一個讀進程和一個寫進程，以實現(xiàn)它們之間通信的共享文件。例：UNIX的管道管道按FIFO方式單向傳送消息。Pipe文件寫端fd[1]讀端fd[0]2.9 進程通信管道機制必須具備:（1）互斥、（2）同步、（3）確定對方存在。2023/7/25

02:03操作系統(tǒng)|進程管理

99OS發(fā)送命令（直接通信方式）發(fā)送進程直接利用OS所提供的命令，把消息發(fā)送給目標進程。要求發(fā)送進程和接收進程必須以顯示方式提供對方的標識符。

OS通常提供以下兩類通信原語：

Send(ReceiverID,message);Receive(SenderID,message);消息傳遞通信的實現(xiàn)方法2023/7/25

02:03操作系統(tǒng)|進程管理

100信箱（間接通信方式）

間接通信方式：進程之間的通信需要通過作為共享數(shù)據(jù)結構的實體作為暫存發(fā)送進程發(fā)送給目標進程的消息。

當兩個進程間需要通信時，由發(fā)送進程創(chuàng)建一個與接收進程相連的信箱。發(fā)送進程把消息送到信箱，接收進程從信箱中取走消息。信箱頭：名稱，大小，方向，進程名等；信箱體：由若干格子組成，每一格存放一條消息。雙向信箱信箱溢出2023/7/25

02:03操作系統(tǒng)|進程管理

101信箱創(chuàng)建與撤消:系統(tǒng)提供相關原語,用于信箱的創(chuàng)建、撤消和消息的發(fā)送、接收。消息的發(fā)送和接收：必須使用共享信箱，利用通信原語進行通信。Send(mailbox,message);Receive(mailbox,message);信箱類型私用信箱：用戶創(chuàng)建,擁有者可讀，其他人只可發(fā)。公用信箱：采用輸入/輸出雙向通信鏈路，由OS創(chuàng)建。被核準進程可發(fā)、可收。共享信箱：由進程創(chuàng)建并指明共享進程名。發(fā)送進程和接受進程的對應關系：一對一、一對多、多對一、多對多。2023/7/25

02:03操作系統(tǒng)|進程管理

102通信鏈路：在發(fā)送進程和接受進程之間必須建立一條通信鏈路。一種是顯示的由“建立連接”命令（原語）請求系統(tǒng)為之創(chuàng)建，使用完后，也用顯示方式拆除。另一種是利用系統(tǒng)提供的發(fā)送命令（原語），系統(tǒng)自動建立和拆除。通信鏈路（communicationlink）顯式和隱式鏈路點-點連接通信鏈路、多點連接鏈路單向和雙向通信鏈路無容量和有容量通信鏈路消息傳遞系統(tǒng)中的若干問題2023/7/25

02:03操作系統(tǒng)|進程管理

103消息的格式：在消息傳遞系統(tǒng)中，必須具有一定的消息格式。通?？砂岩粋€消息分為消息頭和消息正文兩部份。消息頭主要包括消息在傳輸時所需的控制信息，消息正文則是實際發(fā)送數(shù)據(jù)。消息的格式有定長（短消息）和變長（長消息）兩種。2023/7/25

02:03操作系統(tǒng)|進程管理

104消息的格式2023/7/25

02:03操作系統(tǒng)|進程管理

105進程同步方式發(fā)送進程阻塞、接收進程阻塞。發(fā)送進程與接收進程之間無緩沖，兩進程平時都處于阻塞。發(fā)送進程不阻塞、接收進程阻塞。發(fā)送進程不阻塞，接收進程平時處于阻塞，由發(fā)送進程喚醒。發(fā)送進程、接收進程均不阻塞。2023/7/25

02:03操作系統(tǒng)|進程管理

106消息緩沖隊列通信機制通信原語

Send(Receiver,message); Receive(Sender,message);消息緩沖區(qū)Typemessagebuffer=record Sender； Size ；

Text ；

Next ；

end2023/7/25

02:03操作系統(tǒng)|進程管理

107PCB中有關通信的數(shù)據(jù)項TypeProcessControlblock=record … mq ；消息隊列首指針

mutex；消息隊列互斥信號量

sm ；消息隊列資源信號量

… end2023/7/25

02:03操作系統(tǒng)|進程管理

108消息緩沖通信模型send(B,a)sender:Asize:5text:Hello進程Areceive(b)sender:Asize:5text:Hello進程Bmqmutexsmsender:Asize:5text:Hellonext:0PCB(B)第一消息緩沖區(qū)發(fā)送區(qū)a接收區(qū)b進程Asend(B,a)asender:Asize:5text:Hel