前趋图和程序执行课件

第二章第二章 进程的描述与控制进程的描述与控制 2.1 2.1 前趋图和程序执行（理解）前趋图和程序执行（理解）2.2 2.2 进程的描述（重点）进程的描述（重点）2.3 2.3 进程控制（重点）进程控制（重点）2.4 2.4 进程同步（重点、难点）进程同步（重点、难点）2.5 2.5 经典进程的同步问题经典进程的同步问题 （重点、难点）（重点、难点）2.6 2.6 进程通信进程通信 （编程掌握）（编程掌握）2.7 2.7 线程（编程掌握）线程（编程掌握）第二章进程的描述与控制2.1前趋图和程序执行（理1应用的提出:同时进行多个任务的需求举例编辑文档运行程序网上浏览CD音乐欣赏问题：单处理机如何同时执行多个任务？进程的引入进程的引入应用的提出:同时进行多个任务的需求举例编辑文档问题：单处理机2右图给出了右图给出了7个结点的前驱图。个结点的前驱图。在该图中，存在下面一些前驱在该图中，存在下面一些前驱关系：关系：P1P2，P1P3，P4P6，P6P7，或表，或表示为：示为：PP1，P2，P3，P4，P5，P6，P7P(P1，P2),，P1，P3)，(P5，P7),(P6，P7)1234756具有具有7个结点的个结点的前驱图前驱图1 前趋图前趋图 提示提示:前趋图中前趋图中 不存在循环不存在循环图中的每个结点图中的每个结点可用于描述一个可用于描述一个程序段或进程程序段或进程不存在前驱关系的程序之间才能并发执行不存在前驱关系的程序之间才能并发执行2.1前趋图和程序执行前趋图和程序执行右图给出了7个结点的前驱图。在该图中，存在下面一些前驱关系：32 程序的顺序执行及其特征程序的顺序执行及其特征 a.程序的顺序执行程序的顺序执行程程序序是是指指令令（或或语语句句）的的集集合合，指指令令之之间间是是顺顺序序关关系系，是是一一个个静静态态的的概概念念,仅仅当当前前一一操操作作(程程序序段段)执执行行完完后后，才才能能执执行后继操作。行后继操作。2程序的顺序执行及其特征a.程序的顺4假定用假定用I、C和和P分别表示输入、计算和输出操作（也分别表示输入、计算和输出操作（也可以为语句），可以有下图的顺序关系。可以为语句），可以有下图的顺序关系。I1C1P1I2C2P2S1S3S2a=10；b=a+8；Print（b）；S1：S2：S3：假定用I、C和P分别表示输入、计算和输出操作5再如例再如例1:t输入：输入：计算：计算：输出：输出：I1C1P1I2C2P2I3C3P3 t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10三个程序顺序执行三个程序顺序执行t程序1：I1C1P1程序2：程序3：I2C2P2I3C3P39个个t再如例1:t输入：I1C1P1I2C2P2I3C3P36b.程序顺序执行具有如下程序顺序执行具有如下3个特点个特点：n顺序性；顺序性；处理机的操作严格按照程序所规定的顺序执行。处理机的操作严格按照程序所规定的顺序执行。n封闭性；程序独占全机资源封闭性；程序独占全机资源,程序执行结果程序执行结果不受外界因素不受外界因素的影响的影响。n可再现性；可再现性；只要输入的初始条件相同，则无论何时重复执只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。行该程序都会得到相同的结果。程序顺序执行的特性为程序员检测程序顺序执行的特性为程序员检测和校正程序错误带来很大的方便！和校正程序错误带来很大的方便！b.程序顺序执行具有如下3个特点：顺序性；处理机的操73 程序的并发执行及其特征程序的并发执行及其特征 a.程序的并发执行程序的并发执行 对于对于例例1中的任意程序，存在着中的任意程序，存在着IiCiPi这样这样的前驱关系，因而对的前驱关系，因而对一个用户程序一个用户程序的输入、计算和的输入、计算和打印这三个操作，必须顺序执行。打印这三个操作，必须顺序执行。但在但在多道环境下多道环境下，并不存在，或，并不存在，或并不要求并不要求PiIi+1关系，即关系，即Ii、Cj和和Pk（ijk）之间并不存在前驱关）之间并不存在前驱关系系，因而在对一批程序处理时，可使它们，因而在对一批程序处理时，可使它们并发执行并发执行。这就产生了并发操作这就产生了并发操作。3程序的并发执行及其特征a.程序的并发执行8输入：计算：输出：t0 t1 t2 t3 t4 t5 t6tttI1三个程序并发执行的前驱图三个程序并发执行的前驱图I2I3C1C2C3P1P2P3时间:5个t并发并发并发并发并发并发前驱关系执行顺序输入：9n程序内保持程序内保持IiCiPi程序程序逻辑顺序性。逻辑顺序性。n存在存在IiIi+1；CiCi+1;PiPi+1;表明表明系统资源竞争系统资源竞争带来带来顺序性前驱关系顺序性前驱关系。n不同程序之间不同程序之间Ii+2、Ci+1和和Pi，没有前驱关系，没有前驱关系，说明可以说明可以并发执行并发执行，这是这是系统的并发性系统的并发性，提高提高(9-5)/9x100%=44%。I1I2I3C1C2C3P1P2P3问：问：CPU某一时刻只能执行输入、某一时刻只能执行输入、计算、打印三个程序中的一个，计算、打印三个程序中的一个，如何理解并发？如何理解并发？程序内保持IiCiPi程序逻辑顺序性。存在I10例例2：两个程序：两个程序A和和B共享一个变量共享一个变量N(当前值为当前值为n)。程序程序A：N=N+1;程序程序B：print(N)；N=0;在处理机上执行关于在处理机上执行关于N的的3条指令，由于并条指令，由于并发性，有理由假定发性，有理由假定3个可能的执行序列个可能的执行序列：N=N+1;print(N);N=0;(完全顺序AB)print(N);N=0;N=N+1;(完全顺序BA)print(N);N=N+1;N=0;(B,A交替运行)n1，n1，0，最终，最终N的结果为的结果为0n，0，1，最终最终N的结果为的结果为1n，1，0，最终最终N的结果为的结果为0计算结果与并发计算结果与并发程序的程序的执行速度执行速度有关有关例2：两个程序A和B共享一个变量N(当前值为n)。程11b.程序并发执行时的特征程序并发执行时的特征 1)2)失去封闭性失去封闭性:多个程序多个程序共享系统中的各种资源共享系统中的各种资源，因，因而这些资源的状态将由多个程序来改变，致使程序的而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性运行失去了封闭性。1)间断性间断性:任意程序不可能一直占有任意程序不可能一直占有CPU3)不可再现性不可再现性:程序在并发执行时，程序在并发执行时，由于失去了封闭性，由于失去了封闭性，也导致失去了可再现性。也导致失去了可再现性。b.程序并发执行时的特征1)间断性:任意程序不可能一直占12(1)(1)程序是一个静态概念，而进程是一个动态概念程序是一个静态概念，而进程是一个动态概念 程序是指令的有序集合，它作为一个静态的实体而存在，程序是指令的有序集合，它作为一个静态的实体而存在，可以作为程序文件被长久保存。可以作为程序文件被长久保存。程序一旦执行进程就会被创建，该进程因调度而执行，程序一旦执行进程就会被创建，该进程因调度而执行，因得不到资源而暂停执行，因执行结束而撤销，因而具有生因得不到资源而暂停执行，因执行结束而撤销，因而具有生命期，是一个动态的实体，是暂时的。命期，是一个动态的实体，是暂时的。4 4 进程与程序的关系进程与程序的关系(2)(2)进程具有并行特性，而程序没有进程具有并行特性，而程序没有。(1)程序是一个静态概念，而进程是一个动态概念4进程与程序13程序：进程的程序：进程的1 1：n n联系联系通过多次执行，一个程序可以对应多个进程；通过多次执行，一个程序可以对应多个进程；例如例如:打开多个打开多个WORD文件。文件。进程：程序的进程：程序的1 1：n n联系联系通过调用关系，一个进程可以包括多个程序。通过调用关系，一个进程可以包括多个程序。例：在例：在WORD中插入中插入BMP图象、图象、EXCEL表格等。表格等。(3)(3)进程与程序之间存在多对多的联系进程与程序之间存在多对多的联系。进程：程序的1：n联系(3)进程与程序之间存145实例介绍：实例介绍：Linux系统创建进程系统创建进程(1)进程创建进程创建fork在在Linux系统中，用户或系统可以使用系统调用系统中，用户或系统可以使用系统调用fork来来创建一个新的进程。创建一个新的进程。fork的函数原形为：的函数原形为：格式格式：intfork()返回值返回值：=0创建成功，从子进程返回；创建成功，从子进程返回；0 创建成功，从父进程返回，其值为子进程的创建成功，从父进程返回，其值为子进程的PID号；号；=-1创建失败。创建失败。5实例介绍：Linux系统创建进程15 由由于于forkfork（）调调用用执执行行后后，从从父父进进程程和和子子进进程程返返回回的的值值不不同同，因因而而用用户户能能够够在在程程序序中中使使用用分分支支结结构构将将父父子子进进程程需需要执行的不同程序分开。要执行的不同程序分开。应用程序的框架结构如下：应用程序的框架结构如下：main()int p;/存放子进程存放子进程pid号号while(p=fork()=-1);/创建子进程直到成功为止创建子进程直到成功为止 if (p=0)/返回值返回值=0表示子进程返回表示子进程返回 /*此处插入此处插入子进程程序段子进程程序段*/else/返回值返回值0表示父进程返回表示父进程返回 /*此处插入此处插入父进程程序段父进程程序段*/由于fork（）调用执行后，从父进程和子进程返16.Beforefork()After.forkfork执行前执行前一个控制流进入内核一个控制流进入内核forkfork模块模块。Beforefork()After。Beforefork()Afterforkforkfork执行后执行后调用后，从调用后，从forkfork返回两个控制流返回两个控制流父进程父进程子进程子进程.forkfork执行前一个控制流进入内核fork模块17#includemain()intp1,p2while(p1=fork()=-1);if(p1=0)printf(“b”);elseprintf(“a”);输出结果是什么输出结果是什么？#include输出结果是什么？18 例例 父进程创建子进程父进程创建子进程P1P1、P2P2，父子进程分别输出字符，父子进程分别输出字符a a、b b和和c c。#includemain()int p1,p2;while (p1=fork()=-1);/创创建建子子进进程程1，直直至至创创建建成功成功 if(p1=0)/子进程子进程P1返回输出返回输出bputchar(b);else /父进程返回父进程返回 while(p2=fork()=-1);/创建子进程创建子进程2if(p2=0)/子进程子进程P2返回输出返回输出cputchar(c);else putchar(a);/父进程返回输出父进程返回输出a 例父进程创建子进程P1、P2，父子进程分别输出字符a、19该程序多次运行后，输出的结果可能会是：该程序多次运行后，输出的结果可能会是：abcabc、acbacb、bcabca、cbacba、bacbac或或cabcab等随机结果中的任意一种。等随机结果中的任意一种。每次运行后都会产生父子每次运行后都会产生父子3个进程，所以有个进程，所以有3个字符输出。个字符输出。其中其中系统屏幕输出进程的输出系统屏幕输出进程的输出humingqingBitLinuxchap3$显示会跟显示会跟随在父进程输出随在父进程输出a之后。之后。该程序多次运行后，输出的结果可能会是：20