21-前趨圖和程序執(zhí)行課件

第二章進(jìn)程的描述與控制2.1前趨圖和程序執(zhí)行（理解）2.2進(jìn)程的描述（重點(diǎn)）2.3進(jìn)程控制（重點(diǎn)）2.4進(jìn)程同步（重點(diǎn)、難點(diǎn)）2.5經(jīng)典進(jìn)程的同步問題（重點(diǎn)、難點(diǎn)）2.6進(jìn)程通信（編程掌握）2.7線程（編程掌握）第二章進(jìn)程的描述與控制2.1前趨圖和程序執(zhí)行（理1應(yīng)用的提出:同時(shí)進(jìn)行多個(gè)任務(wù)的需求舉例編輯文檔運(yùn)行程序網(wǎng)上瀏覽CD音樂欣賞問題：單處理機(jī)如何同時(shí)執(zhí)行多個(gè)任務(wù)？進(jìn)程的引入應(yīng)用的提出:同時(shí)進(jìn)行多個(gè)任務(wù)的需求舉例編輯文檔問題：單處理機(jī)2右圖給出了7個(gè)結(jié)點(diǎn)的前驅(qū)圖。在該圖中，存在下面一些前驅(qū)關(guān)系：P1→P2，P1→P3，┅，P4→P6，P6→P7，或表示為：P＝{P1，P2，P3，P4，P5，P6，P7}P＝{(P1，P2),，P1，P3)，┅，(P5，P7),(P6，P7)}1234756具有7個(gè)結(jié)點(diǎn)的前驅(qū)圖1前趨圖提示:前趨圖中不存在循環(huán)圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程不存在前驅(qū)關(guān)系的程序之間才能并發(fā)執(zhí)行2.1前趨圖和程序執(zhí)行右圖給出了7個(gè)結(jié)點(diǎn)的前驅(qū)圖。在該圖中，存在下面一些前驅(qū)關(guān)系：32程序的順序執(zhí)行及其特征a.程序的順序執(zhí)行程序是指令（或語句）的集合，指令之間是順序關(guān)系，是一個(gè)靜態(tài)的概念,僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。2程序的順序執(zhí)行及其特征a.程序的順4

假定用I、C和P分別表示輸入、計(jì)算和輸出操作（也可以為語句），可以有下圖的順序關(guān)系。

I1C1P1I2C2P2S1S3S2a=10；b=a+8；Print（b）；S1：S2：S3：假定用I、C和P分別表示輸入、計(jì)算和輸出操作5再如例1:t輸入：計(jì)算：輸出：I1C1P1I2C2P2I3C3P3

t0t1t2t3t4t5t6t7t8t9t10三個(gè)程序順序執(zhí)行Δt程序1：I1C1P1程序2：程序3：I2C2P2I3C3P39個(gè)Δt

再如例1:t輸入：I1C1P1I2C2P2I3C3P36b.程序順序執(zhí)行具有如下3個(gè)特點(diǎn)：

順序性；處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。

封閉性；程序獨(dú)占全機(jī)資源,程序執(zhí)行結(jié)果不受外界因素的影響。

可再現(xiàn)性；只要輸入的初始條件相同，則無論何時(shí)重復(fù)執(zhí)行該程序都會(huì)得到相同的結(jié)果。

程序順序執(zhí)行的特性為程序員檢測和校正程序錯(cuò)誤帶來很大的方便！b.程序順序執(zhí)行具有如下3個(gè)特點(diǎn)：順序性；處理機(jī)的操73程序的并發(fā)執(zhí)行及其特征a.程序的并發(fā)執(zhí)行

對(duì)于例1中的任意程序，存在著Ii→Ci→Pi這樣的前驅(qū)關(guān)系，因而對(duì)一個(gè)用戶程序的輸入、計(jì)算和打印這三個(gè)操作，必須順序執(zhí)行。

但在多道環(huán)境下，并不存在，或并不要求Pi→Ii+1關(guān)系，即Ii、Cj和Pk（i≠j≠k）之間并不存在前驅(qū)關(guān)系，因而在對(duì)一批程序處理時(shí)，可使它們并發(fā)執(zhí)行。這就產(chǎn)生了并發(fā)操作。3程序的并發(fā)執(zhí)行及其特征a.程序的并發(fā)執(zhí)行8

輸入：計(jì)算：輸出：

t0t1t2t3t4t5t6ΔttI1三個(gè)程序并發(fā)執(zhí)行的前驅(qū)圖I2I3C1C2C3P1P2P3時(shí)間:5個(gè)Δt并發(fā)并發(fā)并發(fā)前驅(qū)關(guān)系執(zhí)行順序輸入：9

程序內(nèi)保持Ii→Ci→Pi程序邏輯順序性。

存在Ii→Ii+1；Ci→Ci+1;Pi→Pi+1;表明系統(tǒng)資源競爭帶來順序性前驅(qū)關(guān)系。

不同程序之間

Ii+2、Ci+1和Pi，沒有前驅(qū)關(guān)系，說明可以并發(fā)執(zhí)行，這是系統(tǒng)的并發(fā)性，提高(9-5)/9x100%=44%。I1I2I3C1C2C3P1P2P3問：CPU某一時(shí)刻只能執(zhí)行輸入、計(jì)算、打印三個(gè)程序中的一個(gè)，如何理解并發(fā)？？？程序內(nèi)保持Ii→Ci→Pi程序邏輯順序性。存在I10例2：兩個(gè)程序A和B共享一個(gè)變量N(當(dāng)前值為n)。

程序A：

┅N=N+1;┅程序B：┅print(N)；N=0;┅在處理機(jī)上執(zhí)行關(guān)于N的3條指令，由于并發(fā)性，有理由假定3個(gè)可能的執(zhí)行序列：①

N=N+1;

print(N);N=0;(完全順序A→B)

②

print(N);N=0;

N=N+1;(完全順序B→A)

③

print(N);

N=N+1;N=0;(B,A交替運(yùn)行)n＋1，n＋1，0，最終N的結(jié)果為

0

n，0，1，最終N的結(jié)果為

1

n，1，0，最終N的結(jié)果為

0

計(jì)算結(jié)果與并發(fā)程序的執(zhí)行速度有關(guān)例2：兩個(gè)程序A和B共享一個(gè)變量N(當(dāng)前值為n)。程11b.程序并發(fā)執(zhí)行時(shí)的特征

2)失去封閉性:多個(gè)程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個(gè)程序來改變，致使程序的運(yùn)行失去了封閉性。1)間斷性:任意程序不可能一直占有CPU3)不可再現(xiàn)性:程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也導(dǎo)致失去了可再現(xiàn)性。b.程序并發(fā)執(zhí)行時(shí)的特征1)間斷性:任意程序不可能一直占12(1)程序是一個(gè)靜態(tài)概念，而進(jìn)程是一個(gè)動(dòng)態(tài)概念

程序是指令的有序集合，它作為一個(gè)靜態(tài)的實(shí)體而存在，可以作為程序文件被長久保存。程序一旦執(zhí)行進(jìn)程就會(huì)被創(chuàng)建，該進(jìn)程因調(diào)度而執(zhí)行，因得不到資源而暫停執(zhí)行，因執(zhí)行結(jié)束而撤銷，因而具有生命期，是一個(gè)動(dòng)態(tài)的實(shí)體，是暫時(shí)的。4進(jìn)程與程序的關(guān)系(2)

進(jìn)程具有并行特性，而程序沒有。(1)程序是一個(gè)靜態(tài)概念，而進(jìn)程是一個(gè)動(dòng)態(tài)概念4進(jìn)程與程序13

程序：進(jìn)程的1：n聯(lián)系通過多次執(zhí)行，一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程；例如:打開多個(gè)WORD文件。

進(jìn)程：程序的1：n聯(lián)系通過調(diào)用關(guān)系，一個(gè)進(jìn)程可以包括多個(gè)程序。例：在WORD中插入BMP圖象、EXCEL表格等。(3)

進(jìn)程與程序之間存在多對(duì)多的聯(lián)系。

進(jìn)程：程序的1：n聯(lián)系(3)

進(jìn)程與程序之間存145實(shí)例介紹：Linux系統(tǒng)創(chuàng)建進(jìn)程(1)進(jìn)程創(chuàng)建——fork

在Linux系統(tǒng)中，用戶或系統(tǒng)可以使用系統(tǒng)調(diào)用fork來創(chuàng)建一個(gè)新的進(jìn)程。fork的函數(shù)原形為：

格式：intfork()返回值：=0 創(chuàng)建成功，從子進(jìn)程返回；>0 創(chuàng)建成功，從父進(jìn)程返回，其值為子進(jìn)程的PID號(hào)； =-1創(chuàng)建失敗。

5實(shí)例介紹：Linux系統(tǒng)創(chuàng)建進(jìn)程15

由于fork（）調(diào)用執(zhí)行后，從父進(jìn)程和子進(jìn)程返回的值不同，因而用戶能夠在程序中使用分支結(jié)構(gòu)將父子進(jìn)程需要執(zhí)行的不同程序分開。應(yīng)用程序的框架結(jié)構(gòu)如下：main(){ intp; //存放子進(jìn)程pid號(hào) while((p=fork())==-1); //創(chuàng)建子進(jìn)程直到成功為止

if(p==0) //返回值=0表示子進(jìn)程返回 { /*此處插入子進(jìn)程程序段*/ } else //返回值>0表示父進(jìn)程返回 { /*此處插入父進(jìn)程程序段*/ }}由于fork（）調(diào)用執(zhí)行后，從父進(jìn)程和子進(jìn)程返16……..Beforefork()After……..forkfork執(zhí)行前一個(gè)控制流進(jìn)入內(nèi)核fork模塊。。。。Beforefork()After………。。。。Beforefork()After………forkfork執(zhí)行后調(diào)用后，從fork返回兩個(gè)控制流父進(jìn)程子進(jìn)程……..forkfork執(zhí)行前一個(gè)控制流進(jìn)入內(nèi)核fork模塊17

#include<stdio.h>main(){intp1,p2while((p1=fork())==-1);

if(p1==0)

printf(“b”);elseprintf(“a”);}輸出結(jié)果是什么？？#include<stdio.h>輸出結(jié)果是什么？？18[例]父進(jìn)程創(chuàng)建子進(jìn)程P1、P2，父子進(jìn)程分別輸出字符a、b和c。#include<stdio.h>main(){ intp1,p2; while((p1=fork())==-1); //創(chuàng)建子進(jìn)程1，直至創(chuàng)建成功

if(p1==0) //子進(jìn)程P1返回輸出’b’ putchar('b'); else //父進(jìn)程返回 { while((p2=fork())==-1); //創(chuàng)建子進(jìn)程2

if(p2==0) //子進(jìn)程P2返回輸出’c’ putchar('c'); else putchar('a'); //父進(jìn)程返回輸出’a’ }}[例]父進(jìn)程創(chuàng)建子進(jìn)程P1、P2，父子進(jìn)程分別輸出字符a、19該程序多次運(yùn)行后，輸出的結(jié)果可能會(huì)是：abc、acb、bca、cba、bac或cab等隨機(jī)結(jié)果中的任意一種。每次運(yùn)行后都會(huì)產(chǎn)生父子3個(gè)進(jìn)程，所以有3個(gè)字符輸出。其中系統(tǒng)屏幕輸出進(jìn)程的輸出[humingqing@BitLinuxchap3]$顯示會(huì)跟隨在父進(jìn)程輸出’a’之后。

該程序多次運(yùn)行后，輸出的結(jié)果可能會(huì)是：20第二章進(jìn)程的描述與控制2.1前趨圖和程序執(zhí)行（理解）2.2進(jìn)程的描述（重點(diǎn)）2.3進(jìn)程控制（重點(diǎn)）2.4進(jìn)程同步（重點(diǎn)、難點(diǎn)）2.5經(jīng)典進(jìn)程的同步問題（重點(diǎn)、難點(diǎn)）2.6進(jìn)程通信（編程掌握）2.7線程（編程掌握）第二章進(jìn)程的描述與控制2.1前趨圖和程序執(zhí)行（理21應(yīng)用的提出:同時(shí)進(jìn)行多個(gè)任務(wù)的需求舉例編輯文檔運(yùn)行程序網(wǎng)上瀏覽CD音樂欣賞問題：單處理機(jī)如何同時(shí)執(zhí)行多個(gè)任務(wù)？進(jìn)程的引入應(yīng)用的提出:同時(shí)進(jìn)行多個(gè)任務(wù)的需求舉例編輯文檔問題：單處理機(jī)22右圖給出了7個(gè)結(jié)點(diǎn)的前驅(qū)圖。在該圖中，存在下面一些前驅(qū)關(guān)系：P1→P2，P1→P3，┅，P4→P6，P6→P7，或表示為：P＝{P1，P2，P3，P4，P5，P6，P7}P＝{(P1，P2),，P1，P3)，┅，(P5，P7),(P6，P7)}1234756具有7個(gè)結(jié)點(diǎn)的前驅(qū)圖1前趨圖提示:前趨圖中不存在循環(huán)圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程不存在前驅(qū)關(guān)系的程序之間才能并發(fā)執(zhí)行2.1前趨圖和程序執(zhí)行右圖給出了7個(gè)結(jié)點(diǎn)的前驅(qū)圖。在該圖中，存在下面一些前驅(qū)關(guān)系：232程序的順序執(zhí)行及其特征a.程序的順序執(zhí)行程序是指令（或語句）的集合，指令之間是順序關(guān)系，是一個(gè)靜態(tài)的概念,僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。2程序的順序執(zhí)行及其特征a.程序的順24

假定用I、C和P分別表示輸入、計(jì)算和輸出操作（也可以為語句），可以有下圖的順序關(guān)系。

I1C1P1I2C2P2S1S3S2a=10；b=a+8；Print（b）；S1：S2：S3：假定用I、C和P分別表示輸入、計(jì)算和輸出操作25再如例1:t輸入：計(jì)算：輸出：I1C1P1I2C2P2I3C3P3

t0t1t2t3t4t5t6t7t8t9t10三個(gè)程序順序執(zhí)行Δt程序1：I1C1P1程序2：程序3：I2C2P2I3C3P39個(gè)Δt

再如例1:t輸入：I1C1P1I2C2P2I3C3P326b.程序順序執(zhí)行具有如下3個(gè)特點(diǎn)：

順序性；處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。

封閉性；程序獨(dú)占全機(jī)資源,程序執(zhí)行結(jié)果不受外界因素的影響。

可再現(xiàn)性；只要輸入的初始條件相同，則無論何時(shí)重復(fù)執(zhí)行該程序都會(huì)得到相同的結(jié)果。

程序順序執(zhí)行的特性為程序員檢測和校正程序錯(cuò)誤帶來很大的方便！b.程序順序執(zhí)行具有如下3個(gè)特點(diǎn)：順序性；處理機(jī)的操273程序的并發(fā)執(zhí)行及其特征a.程序的并發(fā)執(zhí)行

對(duì)于例1中的任意程序，存在著Ii→Ci→Pi這樣的前驅(qū)關(guān)系，因而對(duì)一個(gè)用戶程序的輸入、計(jì)算和打印這三個(gè)操作，必須順序執(zhí)行。

但在多道環(huán)境下，并不存在，或并不要求Pi→Ii+1關(guān)系，即Ii、Cj和Pk（i≠j≠k）之間并不存在前驅(qū)關(guān)系，因而在對(duì)一批程序處理時(shí)，可使它們并發(fā)執(zhí)行。這就產(chǎn)生了并發(fā)操作。3程序的并發(fā)執(zhí)行及其特征a.程序的并發(fā)執(zhí)行28

輸入：計(jì)算：輸出：

t0t1t2t3t4t5t6ΔttI1三個(gè)程序并發(fā)執(zhí)行的前驅(qū)圖I2I3C1C2C3P1P2P3時(shí)間:5個(gè)Δt并發(fā)并發(fā)并發(fā)前驅(qū)關(guān)系執(zhí)行順序輸入：29

程序內(nèi)保持Ii→Ci→Pi程序邏輯順序性。

存在Ii→Ii+1；Ci→Ci+1;Pi→Pi+1;表明系統(tǒng)資源競爭帶來順序性前驅(qū)關(guān)系。

不同程序之間

Ii+2、Ci+1和Pi，沒有前驅(qū)關(guān)系，說明可以并發(fā)執(zhí)行，這是系統(tǒng)的并發(fā)性，提高(9-5)/9x100%=44%。I1I2I3C1C2C3P1P2P3問：CPU某一時(shí)刻只能執(zhí)行輸入、計(jì)算、打印三個(gè)程序中的一個(gè)，如何理解并發(fā)？？？程序內(nèi)保持Ii→Ci→Pi程序邏輯順序性。存在I30例2：兩個(gè)程序A和B共享一個(gè)變量N(當(dāng)前值為n)。

程序A：

┅N=N+1;┅程序B：┅print(N)；N=0;┅在處理機(jī)上執(zhí)行關(guān)于N的3條指令，由于并發(fā)性，有理由假定3個(gè)可能的執(zhí)行序列：①

N=N+1;

print(N);N=0;(完全順序A→B)

②

print(N);N=0;

N=N+1;(完全順序B→A)

③

print(N);

N=N+1;N=0;(B,A交替運(yùn)行)n＋1，n＋1，0，最終N的結(jié)果為

0

n，0，1，最終N的結(jié)果為

1

n，1，0，最終N的結(jié)果為

0

計(jì)算結(jié)果與并發(fā)程序的執(zhí)行速度有關(guān)例2：兩個(gè)程序A和B共享一個(gè)變量N(當(dāng)前值為n)。程31b.程序并發(fā)執(zhí)行時(shí)的特征

2)失去封閉性:多個(gè)程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個(gè)程序來改變，致使程序的運(yùn)行失去了封閉性。1)間斷性:任意程序不可能一直占有CPU3)不可再現(xiàn)性:程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也導(dǎo)致失去了可再現(xiàn)性。b.程序并發(fā)執(zhí)行時(shí)的特征1)間斷性:任意程序不可能一直占32(1)程序是一個(gè)靜態(tài)概念，而進(jìn)程是一個(gè)動(dòng)態(tài)概念

程序是指令的有序集合，它作為一個(gè)靜態(tài)的實(shí)體而存在，可以作為程序文件被長久保存。程序一旦執(zhí)行進(jìn)程就會(huì)被創(chuàng)建，該進(jìn)程因調(diào)度而執(zhí)行，因得不到資源而暫停執(zhí)行，因執(zhí)行結(jié)束而撤銷，因而具有生命期，是一個(gè)動(dòng)態(tài)的實(shí)體，是暫時(shí)的。4進(jìn)程與程序的關(guān)系(2)

進(jìn)程具有并行特性，而程序沒有。(1)程序是一個(gè)靜態(tài)概念，而進(jìn)程是一個(gè)動(dòng)態(tài)概念4進(jìn)程與程序33

程序：進(jìn)程的1：n聯(lián)系通過多次執(zhí)行，一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程；例如:打開多個(gè)WORD文件。

進(jìn)程：程序的1：n聯(lián)系通過調(diào)用關(guān)系，一個(gè)進(jìn)程可以包括多個(gè)程序。例：在WORD中插入BMP圖象、EXCEL表格等。(3)

進(jìn)程與程序之間存在多對(duì)多的聯(lián)系。

進(jìn)程：程序的1：n聯(lián)系(3)

進(jìn)程與程序之間存345實(shí)例介紹：Linux系統(tǒng)創(chuàng)建進(jìn)程(1)進(jìn)程創(chuàng)建——fork

在Linux系統(tǒng)中，用戶或系統(tǒng)可以使用系統(tǒng)調(diào)用fork來創(chuàng)建一個(gè)新的進(jìn)程。fork的函數(shù)原形為：

格式：intfork()返回值：=0 創(chuàng)建成功，從子進(jìn)程返回；>0 創(chuàng)建成功，從父進(jìn)程返回，其值為子進(jìn)程的PID號(hào)； =-1創(chuàng)建失敗。

5實(shí)例介紹：Linux系統(tǒng)創(chuàng)建進(jìn)程35

由于fork（）調(diào)用執(zhí)行后，從父進(jìn)程和子進(jìn)程返回的值不同，因而用戶能夠在程序中使用分支結(jié)構(gòu)將父子進(jìn)程需要執(zhí)行的不同程序分開。應(yīng)用程序的框架結(jié)構(gòu)如下：main(){ intp; //存放子進(jìn)程pid號(hào) while((p=fork())==-1); //創(chuàng)建子進(jìn)程直到成功為止

if(p==0) //返回值=0表示子進(jìn)程返回 { /*此處插入子進(jìn)程程序段*/ } else //返回值>0表示父進(jìn)程返回 { /*此處插入父進(jìn)程程序段*/ }}由于fork（）調(diào)用執(zhí)行后，從父進(jìn)程和子進(jìn)程返36……..