并发处理

第四章并发处理主讲：张玉宏[e-mail]24.1并发活动——进程的引入•操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。•要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念－－进程。34.1.1程序的顺序执行•一个程序由若干个程序段组成，而这些程序段的执行必须按照严格的先后次序顺序地执行，即只有当一个操作结束后，才能开始后继操作。•这种程序执行的方式就称为程序的顺序执行。4例：讨论单道系统的工作情况•用户作业的处理，通常分为如下三段：①首先输入用户的程序和数据②然后进行计算③最后打印计算结果5例：讨论单道系统的工作情况•这三个顺序执行的操作分别设为—I：输入操作C：计算操作P：输出操作6顺序程序设计的特点•传统的程序设计方法是顺序程序设计(SequentialProgramming)，即把一个程序设计成一个顺序执行的程序模块。顺序程序设计具有如下的特点：•1.执行的顺序性。•一个程序在顺序处理器上的执行是严格按序的，即每个操作必须在下一个操作开始之前结束。7顺序程序设计的特点•2.环境的封闭性。•程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。8顺序程序设计的特点•3.计算过程的可再现性。•程序执行的结果与初始条件有关，而与执行时间（执行速度）无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。•这样当程序中出现了错误时，往往可以重现错误，以便进行分析。9顺序程序设计的特点•顺序程序设计的顺序性、封闭性和再现性给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。104.1.2程序的并发执行•例：讨论在多道批处理系统中，对大量作业的处理在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,...,n)。对作业1、作业2、…，作业n的处理：•作业1：I1C1P1作业2：I2C2P2┇┇作业n：InCnPn11批量作业执行的先后次序124.1.2程序的并发执行•这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。•也就是说，I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，I2、C2、P2的执行也必须严格按照I2，C2，P2的顺序，而C1与I2，P1与C2、I3是可以同时执行的。13讨论•(1)哪些程序段的执行必须是顺序的？为什么？•(2)哪些程序段的执行可以是并行的？为什么?14并发执行的条件•并发进程的无关性是进程的执行与时间无关的一个充分条件。该条件在1966年首先由Bernstein提出，又称之为Bernstein条件.假设:•R(pi)={a1，a2，…，an}，表示程序pi在执行期间引用的变量集；即要读的变量集合•W(pi)={b1，b2，…，bm}，表示程序pi在执行期间改变的变量集。即要写的变量集合•若两个进程的程序p1和p2能满足Bernstein条件、即引用变量集与改变变量集交集之和为空集.15并发执行的条件•Bernstein条件条件：任意两个程序P(i)和P(j)，有：•R(pi)W(pj)=;•W(pi)R(pj)=;•W(pi)W(pj)=;•前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。16并发执行的条件•例如，有如下四条语句：•S1:a:=x+y•S2:b:=z+1•S3:c:=a-b•S4:w:=c+1•哪些语句能并发执行？哪些语句不能并发执行？17并发执行的条件•由分析有：•R(S1)={x，y}，R(S2)={z}，R(S3)={a，b}，R(S4)={c}；•W(S1)={a}，W(S2)={b}，W(S3)={c}，W(S4)={w}。•可见S1和S2可并发执行，因为，满足Bernstein条件。其他语句间因变量交集之和非空，并发执行可能会产生与时间有关的错误。18程序并发执行（定义）•程序并发执行：若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。19程序并发执行的描述•程序并发执行的描述•cobegin•S1;S2;S3;...;SN•coend;•其中Si(i=1,2,3,...,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。•说明：co是concurrent的头两个字符。•这是著名的荷兰计算机科学家Dijkstra提出的。20程序并发执行的描述•假设有一个程序由S0-Sn+1个语句，•其中S1-Sn语句是并发执行的，程序如下：•S0;•cobegin•S1;S2;S3;...;SN•coend;•Sn+1;•示意图如右所示：21程序并发执行的描述•由上面的程序运行先后示意图，我们所期望的效果是：•先执行S0，在执行S1，S2，…,Sn；•当S1，S2，…,Sn全部执行完毕后，在执行随后的语句Sn+122采用并发程序设计的目的•采用并发程序设计的目的是：•充分发挥硬件的并行性，消除处理器和I/O设备的互等现象，提高系统效率。•机器部件能并行工作仅仅有了提高效率的可能性，而机器部件并行工作的实现还需要软件技术去利用和发挥，这种软件技术就是并发程序设计。•并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到单处理器的系统中。234.1.3并发执行实例•顺序程序有一个很大的特性就是：运行结果具有确定性，与程序的运行时间及运行速度无关。•那么，当程序并发执行时是否还具有这个特性呢？•下面用几个例子来说明之：24并发执行实例——誊抄•设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），如何把尽快用标准输入设备把某一个文本送到标准设备输出。25并发执行实例——誊抄•设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。26并发执行实例——誊抄•以什么样的方案来解决这一誊抄问题。下面给出三种方案，请注意各个方案的提出的前提和各自的特点。27方案1：一个循环程序顺序执行的誊抄•对于这个问题的简单的解决办法就是采用循环的顺序程序，用f表示标准输入设备的纪录序列，用g表示经誊抄处理程序处理后在标准输出设备输出的序列。•用类C语言的伪代码描述如下：28方案1：一个循环程序顺序执行的誊抄•算法1：输入：f输出：g{while(f不为空）{input;output;}}•由这个程序完成誊抄工作是不会出错的。29方案1的评价•这一方案的特点是简单、正确。然而，这个方案是低效的。•因为，假定标准输入设备和输出设备的速度不一致，读卡机标定速度1000卡/分，打印机的标定速度为600行/分，那么最高的传输速度仅为375行/分。（比二者最低的速度还要低，why？）•也就是说这一方案没有能充分利用输入设备和输出设备的并行操作能力，所以系统的利用率是不高的。•为了克服这一缺点，我们提出了第二个方案。30方案2：并发程序的誊抄方案•这个方案需要设置一个缓冲区（假定缓冲区的容量为每次存放一个纪录信息）。•将方案1中的顺序程序分为两个部分：①负责将标准输入设备的信息送入缓冲区②负责从缓冲区读取信息并打印之。31方案2：并发程序的誊抄方案•这样的誊抄速度提高到600行/分，即达到了最慢的那个设备的传输速度。其方案类C算法如下：32方案2：并发程序的誊抄方案（算法2）输入：f输出：g{cobeginwhile(f不为结束符）/*输入程序段*/{input;/*从标准输入设备读入一个数据*/send;/*将读入的数据送到bufferf*/}while(buffer不为空）/*输出程序段*/{receive;/*从bufferf中取数据*/output;/*送打印机输出*/}coend}33方案2的评价•这两个程序段并发执行时可能出现如下情况：•1、输出程序运行的速度比输入程序快时，有些输出会重复；•如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又从buffer取出“A”打印，这样“A”的输出就重复了，出错。•2、输入程序执行的速度比输出程序快时，有些数据会丢失；•如输入程序送入一个字符“B”，紧接着（当输出程序还未从buffer取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。34方案2的评价•在二方案下,由于输入设备和输出设备的速度不一致,所以打印出的结果可能上乱七八糟的,它虽然提高了利用率,但不能保证正确的誊抄,也是不可取的.•那么能不能有一种方案,既能让输入和输出设备并行工作,又能保证誊抄的正确性呢?•因此提出来了第三种方案.35方案3:三个并发程序的誊抄方案•在第2个方案中,之所以不能正确的誊抄,是因为输入程序和输出程序公用了一个缓冲区.•由于这两个设备的速度不相等,即输入记录和输出记录的速度不一样,从而导致最终的输出信息的错误.36方案3:三个并发程序的誊抄方案•为此我们对第二中方案进行改进:由三个程序共同来完成这个誊抄工作,另外设置两个缓冲区s,t,各用来保持一个记录.•改进后的誊抄工作工程如下图所示:37方案3:三个并发程序的誊抄方案•图中由三个程序段,get,copy和put。其中：•get程序负责从输入序列f中读取字符，并送到缓冲区s中;•copy程序把缓冲区s中的数据复制到缓冲区t中去;•put程序从缓冲区t中取出数据打印。38方案3:三个并发程序的誊抄方案•假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一字符，然后，送个到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。这个算法是正确的。394.1.4与时间有关的错误•两个交互的并发进程，其中一个进程对另一个进程的影响常常是不可预期的，甚至无法再现。•这是因为两个并发进程执行的相对速度不可预测，交互进程的速率不仅受到处理器调度的影响，而且还受到与其交互的并发进程的影响，甚至受到与其无关的其他进程的影响，所以，一个进程的速率通常无法为另一个进程所知。404.1.4与时间有关的错误•因此，对资源的共享充满了危险，各种与时间有关的错误就可能出现，与时间有关的错误有两种表现形式：①是结果不唯一；②是永远等待。•为了说明与时间有关的错误，现观察下面的例子：41例1（结果不唯一）购买飞机票问题。•假设一个飞机订票系统有两个终端，分别运行进程Tl和T2。该系统的公共数据区•中的一些单元Aj(j=l，2，…)分别存放某月某日某次航班的余票数，Tl和T2共享Aj。飞机票售票程序如下：42例1（结果不唯一）购买飞机票问题。43例1（结果不唯一）购买飞机票问题。•由于T1和T2是两个可同时执行的并发进程，它们在同一个计算机系统中运行，共享x，因此，可能出现如下所示的运行情况。•作为并发多道程序，其有三个特点：①多道②宏观上并行③微观上串行•微观上串行的含义是多道程序轮流和分时的占有处理机，交替执行。•当这个交替执行交替的不巧的时候，就会产生与时间有关的错误。44例1（结果不唯一）购买飞机票问题。•例如，可能出现如下所示的运行情况：•T1:X1=Aj;//（T1执行此处暂停，T2执行）•T2:X2=Aj;•T2:X2=X2-1;Aj=X2;输出一张票；•//（T2执行完毕后，T1才接着执行）•T1:X1=X1-1;Aj=X1;输出一张票；45例1（结果不唯一）购买飞机票问题。•假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值却为4•