操作系统原理课件第四章并发处理1并发活动--进程的引入-文档资料

第四章并发处理操作系统的两大重要特性是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等等。要解决这些问题，用程序的概念已经不能描述其在内存中运行的状态，必须引入新的概念－－进程。4.1并发活动－－进程的引入4.1并发活动－－进程的引入4.1.1程序的顺序执行一、概念一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。例如：4.1并发活动－－进程的引入4.1.1程序的顺序执行二、程序顺序执行的特点1.顺序性处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。3.可再现性程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。4.1并发活动－－进程的引入4.1.2程序的并发执行例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,...,n)。这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2，I3与P1是可以同时执行的。4.1并发活动－－进程的引入4.1.2程序的并发执行例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。4.1并发活动－－进程的引入4.1.2程序的并发执行程序并发执行（定义）若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。PQR并发执行区4.1并发活动－－进程的引入4.1.2程序的并发执行程序并发执行的描述cobeginS1;S2;S3;...;SNcoend;Si(i=1,2,3,...,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。co是concurrent的头两个字符。这是Dijkstra提出的。4.1并发活动－－进程的引入4.1.2程序的并发执行假设有一个程序由S0～Sn+1个语句，其中S1～Sn语句是并发执行的，程序如下：S0;cobeginS1;S2;S3;...;SN;coendSn+1;4.1并发活动－－进程的引入4.1.3并发执行实例－－誊抄一、一个循环程序顺序执行的誊抄算法1：输入：f输出：g{while(f不为空）{input;output;}}由这个程序完成誊抄工作是不会出错的。4.1并发活动－－进程的引入4.1.3并发执行实行－－誊抄二、两个程序并发执行完成誊抄设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。4.1并发活动－－进程的引入4.1.3并发执行实行－－誊抄二、两个程序并发执行完成誊抄算法：2{cobeginwhile(不为结束符）/*输入程序段*/{input;/*从标准输入设备读入一个数据*/send;/*将读入的数据送到bufferf*/}while(buffer不为空）/*输出程序段*/{receive;/*从bufferf中取数据*/output;/*送打印机输出*/}coend}4.1并发活动－－进程的引入4.1.3并发执行实行－－誊抄这两个程序段并发执行时可能出现如下情况：1、输出程序运行的速度比输入程序快时，有些输出会重复；如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。2、输入程序执行的速度比输出程序快时，有些数据会丢失；如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。4.1并发活动－－进程的引入4.1.3并发执行实行－－誊抄三、三个并发执行程序的誊抄get程序输入数据并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。4.1并发活动－－进程的引入4.1.3并发执行实行－－誊抄三、三个并发执行程序的誊抄假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。这个算法是正确的。4.1并发活动－－进程的引入4.1.4与时间有关的错误假定f系列中有记录f=(R1,R2,...,Rn)g=()在誊抄完成后：f=()g=(R1,R2,...,Rn)算法中的：copy≡t=sput≡put(t,g)get≡get(s,f)4.1并发活动－－进程的引入4.1.4与时间有关的错误若程序错写成：while(誊抄未完成）{cobegincopy;put;get;coend}初始状态：f=(R1,R2,...,Rn)s=()t=()g=()首先执行了get(s,f)f=(R1,R2,...,Rn)s=R1,t=(),g=()假设第一次循环时执行顺序为copy、put、get;f=(R1,R2,...,Rn)s=R2,t=R1,g=(R1)4.1并发活动－－进程的引入4.1.4与时间有关的错误然后，第二次循环时，copy,put,get三个程序段并发执行，就有六种组合：1、copy;put;get导致结果：g=(R1,R2)2、copy;get;put导致结果：g=(R1,R2)3、put;copy;get导致结果：g=(R1,R1)4、put;get;copy导致结果：g=(R1,R1)5、get;copy;put导致结果：g=(R1,R3)6、get;put;copy导致结果：g=(R1,R1)这就是与时间有关的错误。4.1并发活动－－进程的引入4.1.5程序并发执行的特点一、失去了程序的封闭性如果程序执行的结果是一个与时间无关的函数，即具有封闭性。若一个程序的执行可改变另一个程序的变量，象二个并发程序完成誊抄的例子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。4.1并发活动－－进程的引入4.1.5程序并发执行的特点二、程序与计算不再一一对应在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。4.1并发活动－－进程的引入4.1.5程序并发执行的特点三、程序并发执行的相互制约在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。