并发处理PPT演示课件

第四章并发处理,主讲：张玉宏yhily,1,4.1并发活动进程的引入,操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。,4.1.1程序的顺序执行,一个程序由若干个程序段组成，而这些程序段的执行必须按照严格的先后次序顺序地执行，即只有当一个操作结束后，才能开始后继操作。这种程序执行的方式就称为程序的顺序执行。,例：讨论单道系统的工作情况,用户作业的处理，通常分为如下三段：首先输入用户的程序和数据然后进行计算最后打印计算结果,例：讨论单道系统的工作情况,这三个顺序执行的操作分别设为I：输入操作C：计算操作P：输出操作,顺序程序设计的特点,传统的程序设计方法是顺序程序设计(SequentialProgramming)，即把一个程序设计成一个顺序执行的程序模块。顺序程序设计具有如下的特点：1.执行的顺序性。一个程序在顺序处理器上的执行是严格按序的，即每个操作必须在下一个操作开始之前结束。,顺序程序设计的特点,2.环境的封闭性。程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。,顺序程序设计的特点,3.计算过程的可再现性。程序执行的结果与初始条件有关，而与执行时间（执行速度）无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。这样当程序中出现了错误时，往往可以重现错误，以便进行分析。,顺序程序设计的特点,顺序程序设计的顺序性、封闭性和再现性给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。,4.1.2程序的并发执行,例：讨论在多道批处理系统中，对大量作业的处理在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,.,n)。对作业1、作业2、，作业n的处理：作业1：I1C1P1作业2：I2C2P2作业n：InCnPn,批量作业执行的先后次序,4.1.2程序的并发执行,这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。也就是说，I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，I2、C2、P2的执行也必须严格按照I2，C2，P2的顺序，而C1与I2，P1与C2、I3是可以同时执行的。,讨论,(1)哪些程序段的执行必须是顺序的？为什么？(2)哪些程序段的执行可以是并行的？为什么?,并发执行的条件,并发进程的无关性是进程的执行与时间无关的一个充分条件。该条件在1966年首先由Bernstein提出，又称之为Bernstein条件.假设:R(pi)=a1，a2，an，表示程序pi在执行期间引用的变量集；即要读的变量集合W(pi)=b1，b2，bm，表示程序pi在执行期间改变的变量集。即要写的变量集合若两个进程的程序p1和p2能满足Bernstein条件、即引用变量集与改变变量集交集之和为空集.,并发执行的条件,Bernstein条件条件：任意两个程序P(i)和P(j)，有：R(pi)W(pj)=;W(pi)R(pj)=;W(pi)W(pj)=;前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。,并发执行的条件,例如，有如下四条语句：S1:a:=x+yS2:b:=z+1S3:c:=a-bS4:w:=c+1哪些语句能并发执行？哪些语句不能并发执行？,并发执行的条件,由分析有：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条件。其他语句间因变量交集之和非空，并发执行可能会产生与时间有关的错误。,程序并发执行（定义）,程序并发执行：若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。,程序并发执行的描述,程序并发执行的描述cobeginS1;S2;S3;.;SNcoend;其中Si(i=1,2,3,.,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。说明：co是concurrent的头两个字符。这是著名的荷兰计算机科学家Dijkstra提出的。,程序并发执行的描述,假设有一个程序由S0-Sn+1个语句，其中S1-Sn语句是并发执行的，程序如下：S0;cobeginS1;S2;S3;.;SNcoend;Sn+1;示意图如右所示：,程序并发执行的描述,由上面的程序运行先后示意图，我们所期望的效果是：先执行S0，在执行S1，S2，,Sn；当S1，S2，,Sn全部执行完毕后，在执行随后的语句Sn+1,采用并发程序设计的目的,采用并发程序设计的目的是：充分发挥硬件的并行性，消除处理器和I/O设备的互等现象，提高系统效率。机器部件能并行工作仅仅有了提高效率的可能性，而机器部件并行工作的实现还需要软件技术去利用和发挥，这种软件技术就是并发程序设计。并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到单处理器的系统中。,4.1.3并发执行实例,顺序程序有一个很大的特性就是：运行结果具有确定性，与程序的运行时间及运行速度无关。那么，当程序并发执行时是否还具有这个特性呢？下面用几个例子来说明之：,并发执行实例誊抄,设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），如何把尽快用标准输入设备把某一个文本送到标准设备输出。,并发执行实例誊抄,设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。,并发执行实例誊抄,以什么样的方案来解决这一誊抄问题。下面给出三种方案，请注意各个方案的提出的前提和各自的特点。,方案1：一个循环程序顺序执行的誊抄,对于这个问题的简单的解决办法就是采用循环的顺序程序，用f表示标准输入设备的纪录序列，用g表示经誊抄处理程序处理后在标准输出设备输出的序列。用类C语言的伪代码描述如下：,方案1：一个循环程序顺序执行的誊抄,算法1：输入：f输出：gwhile(f不为空）input;output;由这个程序完成誊抄工作是不会出错的。,方案1的评价,这一方案的特点是简单、正确。然而，这个方案是低效的。因为，假定标准输入设备和输出设备的速度不一致，读卡机标定速度1000卡/分，打印机的标定速度为600行/分，那么最高的传输速度仅为375行/分。（比二者最低的速度还要低，why？）也就是说这一方案没有能充分利用输入设备和输出设备的并行操作能力，所以系统的利用率是不高的。为了克服这一缺点，我们提出了第二个方案。,方案2：并发程序的誊抄方案,这个方案需要设置一个缓冲区（假定缓冲区的容量为每次存放一个纪录信息）。将方案1中的顺序程序分为两个部分：负责将标准输入设备的信息送入缓冲区负责从缓冲区读取信息并打印之。,方案2：并发程序的誊抄方案,这样的誊抄速度提高到600行/分，即达到了最慢的那个设备的传输速度。其方案类C算法如下：,方案2：并发程序的誊抄方案,（算法2）输入：f输出：gcobeginwhile(f不为结束符）/*输入程序段*/input;/*从标准输入设备读入一个数据*/send;/*将读入的数据送到bufferf*/while(buffer不为空）/*输出程序段*/receive;/*从bufferf中取数据*/output;/*送打印机输出*/coend,方案2的评价,这两个程序段并发执行时可能出现如下情况：1、输出程序运行的速度比输入程序快时，有些输出会重复；如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又从buffer取出“A”打印，这样“A”的输出就重复了，出错。2、输入程序执行的速度比输出程序快时，有些数据会丢失；如输入程序送入一个字符“B”，紧接着（当输出程序还未从buffer取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。,方案2的评价,在二方案下,由于输入设备和输出设备的速度不一致,所以打印出的结果可能上乱七八糟的,它虽然提高了利用率,但不能保证正确的誊抄,也是不可取的.那么能不能有一种方案,既能让输入和输出设备并行工作,又能保证誊抄的正确性呢?因此提出来了第三种方案.,方案3:三个并发程序的誊抄方案,在第2个方案中,之所以不能正确的誊抄,是因为输入程序和输出程序公用了一个缓冲区.由于这两个设备的速度不相等,即输入记录和输出记录的速度不一样,从而导致最终的输出信息的错误.,方案3:三个并发程序的誊抄方案,为此我们对第二中方案进行改进:由三个程序共同来完成这个誊抄工作,另外设置两个缓冲区s,t,各用来保持一个记录.改进后的誊抄工作工程如下图所示:,方案3:三个并发程序的誊抄方案,图中由三个程序段,get,copy和put。其中：get程序负责从输入序列f中读取字符，并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。,方案3:三个并发程序的誊抄方案,假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一字符，然后，送个到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。这个算法是正确的。,4.1.4与时间有关的错误,两个交互的并发进程，其中一个进程对另一个进程的影响常常是不可预期的，甚至无法再现。这是因为两个并发进程执行的相对速度不可预测，交互进程的速率不仅受到处理器调度的影响，而且还受到与其交互的并发进程的影响，甚至受到与其无关的其他进程的影响，所以，一个进程的速率通常无法为另一个进程所知。,4.1.4与时间有关的错误,因此，对资源的共享充满了危险，各种与时间有关的错误就可能出现，与时间有关的错误有两种表现形式：是结果不唯一；是永远等待。为了说明与时间有关的错误，现观察下面的例子：,例1（结果不唯一）购买飞机票问题。,假设一个飞机订票系统有两个终端，分别运行进程Tl和T2。该系统的公共数据区中的一些单元Aj(j=l，2，)分别存放某月某日某次航班的余票数，Tl和T2共享Aj。飞机票售票程序如下：,例1（结果不唯一）购买飞机票问题。,例1（结果不唯一）购买飞机票问题。,由于T1和T2是两个可同时执行的并发进程，它们在同一个计算机系统中运行，共享x，因此，可能出现如下所示的运行情况。作为并发多道程序，其有三个特点：多道宏观上并行微观上串行微观上串行的含义是多道程序轮流和分时的占有处理机，交替执行。当这个交替执行交替的不巧的时候，就会产生与时间有关的错误。,例1（结果不唯一）购买飞机票问题。,例如，可能出现如下所示的运行情况：T1:X1=Aj;/（T1执行此处暂停，T2执行）T2:X2=Aj;T2:X2=X2-1;Aj=X2;输出一张票；/（T2执行完毕后，T1才接着执行）T1:X1=X1-1;Aj=X1;输出一张票；,例1（结果不唯一）购买飞机票问题。,假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值却为4显然，此时出现了把同一张票卖给了两个旅客的情况，两个旅客可能各自都买到一张同天同次航班的机票，可是，Aj的值实际上只减去了1，造成余票数的不正确。特别是，当某次航班只有一张余票时，就可能把这一张票同时售给了两位旅客，这是不能允许的。,思考1：,而如果出现如下所示的运行情况：T1:X1=Aj;T1:X1=X1-1;Aj=X1;输出一张票；T2:X2=Aj;T2:X2=X2-1;Aj=X2;输出一张票；还假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值为多少？（思考之）答案：为3，没有出错。,思考2：,而如果出现如下所示的运行情况：T1:X1=Aj;T2:X2=Aj;T1:X1=X1-1;Aj=X1;输出一张票；T2:X2=X2-1;Aj=X2;输出一张票；还假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值为多少？（思考之）答案：为4，还是出现一票两买。,例2（永远等待）内存管理问题。,假定有两个并发进程borrow和return分别负责申请和归还主存资源，算法描述中，x表示现有空闲主存总量，B表示申请或归还的主存量。并发进程算法及执行描述如下：,例2（永远等待）内存管理问题。,由于borrow和return共享了表示主存物理资源的临界变量x，对并发执行不加限制会导致错误。例如，一个进程调用borrow申请主存，在执行了比较B和x的指令后，发现Bx，但在将要执行申请进程进入等待队列等主存资源时，另一个进程调用return抢先执行，归还了所借全部主存资源。这时，由于前一个进程borrow还未成为等待状态，return中的释放等主存资源的进程相当于空操作。以后当调用borrow的进程被置成等主存资源状态时，可能己经没有其他进程来归还主存资源了，从而，申请资源的进程borrow可能处于永远等待状态。,一道考研题,兄弟俩共用一个账户，每次限存或取10元，存钱与取钱的进程如下所示，由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在哥哥第三次存钱时，弟弟在取钱，请问最后的帐号上amount可能有多少钱？（南京大学2000年考题5分）：,答案：amount=20,30,10,4.1.5并发程序的特点,并发程序执行虽然提高了系统的处理能力和机器的利用率，但它也带来了一些新的问题，产生了与顺序程序不同的特征：,一、失去了程序的封闭性和可再现性,如果程序执行的结果是一个与时间无关的函数，即具有封闭性。若一个程序的执行可改变另一个程序的变量，象二个并发程序完成誊抄的例子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。例：讨论共享公共变量的两个程序，它们执行时可能产生的不同结果。设：程序A每执行一次都要做n加1的操作，程序B每隔一定时间打印出n值，并将它重新置为零。程序描述,一、失去了程序的封闭性和可再现性,例：讨论共享公共变量的两个程序，它们执行时可能产生的不同结果。设：初值n=0，程序A每执行一次都要做n加1的操作，程序B每隔一定时间打印出n值，并将它重新置为零。程序A、B并发执行。讨论n的最终值与其打印值,举例说明,n=0;,举例说明,也即上面讲述的产生与时间有关的错误结果不唯一,二、程序与计算不再一一对应,在程序顺序执行时，一个程序总是对应一个具体的计算但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的。例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。,二、程序与计算不再一一对应,三、程序并发执行的相互制约,在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的也有间接。直接的相互制约关系-公共变量间接的相互制约关系-资源共享,历史回顾,回头来，我们再看看操作系统的第三个特性：不确定性：在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到低，而是“走走停停”。,4.2.1进程的定义,在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引人新的概念进程。进程的概念来自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。,进程的定义,行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（KenThompsonandDennisRitchie)教材上给出的进程的定义：进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。,进程与程序的区别与联系：,1、程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并行（并发）活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。,4.2.2进程的类型,在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程执行操作系统核心代码的进程。系统进程起着资源管理和控制的作用。2、用户进程执行用户程序的进程。,系统进程与用户进程的区别：,1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。另一种分类：计算进程，I/O进程等注意：在UNIX系统中没有这样对进程进行分类。,4.2.3进程的状态,进程在系统中的活动规律是：执行暂停执行进程的三种基本状态：运行状态就绪状态等待状态（又称阻塞、挂起、睡眠）,进程的基本状态,1、就绪状态（Ready)存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所取的状态为就绪状态。（可有多个进程处于此状态）2、运行状态(Running）当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，某一时刻，总只有一个进程处于此状态，这也就是所谓的微观上串行。）3、等待状态（Wait)若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。,进程状态变迁图,进程的状态不是固定不变的，而是在不断变换。如下图所示：,AThree-stateProcessModel,Ready,Running,Blocked,EventOccurs,Dispatch,Time-out,EventWait,在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换就绪运行（进程调度）运行就绪（时间片到等）运行等待（服务请求，如请求I/O等）等待就绪（服务完成/事件来到）,进程状态转换：,进程转换,就绪-运行调度程序选择一个新的进程运行运行-就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态,进程转换（续1）,运行-等待当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入(IPC)等待-就绪当所等待的事件发生时，请求的服务已经完成,创建状态：创建一个新的进程终止状态：完成任务，结束进程挂起（suspend）状态进程没有占用内存空间处在挂起状态的进程映像在磁盘上（调节负载，对换）,进程的其它状态,五状态进程模型,操作系统的控制结构,操作系统作为资源管理和分配程序，其本质任务是自动控制程序的执行，并满足进程执行过程中提出的资源使用要求。因此，操作系统的核心控制结构是进程结构，资源管理的数据结构将围绕进程结构展开。在研究进程的控制结构之前，首先介绍一下操作系统的控制结构。,操作系统的控制结构,为了有效的管理进程和资源，操作系统必须掌握每一个进程和资源的当前状态。操作系统通常是通过构造一组表来管理和维护进程和每一类资源的信息。操作系统的控制表分为四类：进程控制表存储控制表I/O控制表文件控制表,操作系统的控制结构,操作系统的控制结构,进程控制表用来管理进程及其相关信息。存储控制表用来管理一级（主）存储器和二级（辅）存储器。I/O控制表用来管理计算机系统的I/O设备和通道。文件控制表用来管理文件。,进程的内存映像,当一个程序进入计算机的主存储器进行计算就构成了进程，主存储器中的进程到底是如何组成的？操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文（processcontext）。当系统调度新进程占有处理器时，新老进程随之发生上下文切换，因此，进程的运行被认为是在进程的上下文中执行的。,4.2.4进程的描述进程控制块,(1)什么是进程控制块？描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构，称为进程控制块pcb(processcontrolblock)或称为进程描述器(processdescriptor)。,4.2.4进程的描述进程控制块,系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的。,进程控制块,进程控制块PCB集中反映一个进程的动态特征。在进程并发执行时，由于资源共享，带来各进程之间的相互制约。显然，为了反映这些制约关系和资源共享关系，在创建一个进程时，应首先创建其PCB，然后才能根据PCB中信息对进程实施有效的管理和控制。当一个进程完成其功能时之后,系统则释放PCB，进程也随之消亡。一个比喻：PCB就象我们的户口。,PCB的结构,PCB的结构说明,1、进程标识符name：每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。UNIX系统中就是一个整型数。在进程创建时由系统赋予。2、进程当前状态status：说明本进程目前处于何种状态（运行、就绪、等待），作为进程调度时分配的主要依据。,PCB的结构说明,3、当前队列指针next：登记与本进程处于同一队列的下一个进程的PCB的地址。,PCB的结构说明,4、总链指针all-q-next：登记在系统总链队列中，下一个进程的pcb地址。5、执行程序开始地址start-addr：该进程的程序将从此地址开始执行。6、进程优先级priority：进程的优先级反映进程的紧迫程度，通常由用户指定和系统设置。UNIX系统采用用户设置和系统计算相结合的方式确定进程的优先级。,PCB的结构说明,7.CPU现场保护区cpustatus：当进程由于某种原因释放处理机时，CPU现场信息被保存在pcb的该区域中，以便该进程重新获得处理机后继续执行。通常被保护的信息有：工作寄存器，指令计数器以及程序状态字等。例如，我们下课，这时我要记住这次讲到什么地方，以便下次课接着讲。,PCB的结构说明,8.通信信息communicationinformation:每个进程在运行过程中和别的进程进行通信时所记录的有关信息。9.家族关系processfamily：有的系统还允许一个进程创建自己的子进程，这样会形成一个进程家族。在pcb中必须指明本进程与家族的关系，如它的子进程和父进程的标识符,PCB的结构说明,10.占有资源清单own-resource。记录进程占用系统资源的情况，不同的系统的处理差别很大，UNIX系统中就没有此项。,说明：队列指针,为了便于对进程实施管理，通常把具有相同状态的进程链接在一起，组成各种队列。例如把所有就绪的队列链在一起，称为就绪队列。把所有因等待某事件而处于等待的进程链在一起就行形成了等待（阻塞）队列。,PCB表组织方式（续）,进程队列及其管理,当发生的某个事件使一个进程的状态发生变化时，这个进程就要退出所在的某个队列而排入到另一个队列中去。一个进程从一个所在的队列中退出的事件称为出队。一个进程排入到一个指定的队列中的事件称为入队。处理器调度中负责入队和出队工作的功能模块称为队列管理模块，简称队列管理。下图给出了操作系统的队列管理和状态转换示意图。,就绪队列结构及指针,就绪队列结构及指针,等待队列结构及指针,等待队列结构及指针,运行指针,运行指针,总链队列结构及指针,系统中存在大量的进程，它们依各自的状态分别处于相应的队列中，这便于对进程实施调度。但是当进行某些管理功能时，如创建进程的功能时，就感到系统具有所有进程的总链是十分方便的。譬如检查进程名是否重叠，进入各个队列中查询是很麻烦的。,4.3.1进程控制的概念,进程是有生命周期的，产生、运行、暂停、终止。对进程的这些操作叫进程控制。进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须提供对进程实行有效管理。,进程控制,进程控制包括：进程创建、进程撤消、进程阻塞、进程唤醒。这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。,4.3.1进程控制的概念,原语的概念,原语是一种特殊的系统调用命令，它可以完成一个特定的功能，一般为外层软件所调用，其特点是原语执行时是不可中断的，所以原语操作具有原子性，它是不可再分的。在操作系统中原语作为一个基本的单位出现。,常用的进程控制原语,常用的进程控制原语有：创建原语撤消原语阻塞原语唤醒原语等,4.3.2进程创建,(1).进程创建原语的形式create(name，priority，start_addr)其中：name为被创建进程的标识符priority为进程优先级start_addr为某程序的开始地址。UNIX/Linux系统：fork(),进程创建,(2)进程创建原语的功能创建一个具有指定标识符的进程，建立进程的PCB结构。(3)进程创建原语的实现,进程创建,所谓资源池也就是pcb集合，它是在系统存储区域开辟的一片区域，用来集中存放所有的进程控制块,进程创建后队列的变化图,4.3.3进程撤销,进程完成其任务，希望终止时，调用撤消进程的系统调用（进程撤消原语）撤消进程。（相当于某人死亡后，就要去派出所消户口）在一般操作系统中进程撤消的系统调用是：killUNIX系统中是exit()。,4.3.3进程撤销,撤消进程,以下几种情况导致进程被撤消：该进程已完成所要求的功能而正常终止。由于某种错误导致非正常终止。祖先进程要求撤消某个子进程。,进程撤销,(1)进程撤消原语的形式Kill(或exit)该命令没有参数，其执行结果也无返回信息(2)进程撤消原语的功能撤消当前运行的进程。将该进程的pcb结构归还到pcb资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序。,进程撤销,进程撤销,4.3.4进程挂起,进程挂起亦称进程等待：当一个处在运行状态的进程，因等待某个事件的发生（如等待打印机）而不能继续运行时，将调用进程挂起系统调用，把进程的状态置为阻塞状态，并调用进程调度程序（等于让出处理机）。在UNIX系统中进程挂起调用格式为：sleep(chan,pri)。,4.3.4进程挂起,进程从运行状态转换成阻塞状态是由进程挂起原语实现的，因此，调用进程挂起操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变.例如，进程是因等待打印机而进入阻塞状态，则该进程将加入到等待打印机的队列。进程挂起系统调用的算法和队列变化如下。,4.3.4进程挂起,进程挂起的内部调用形式（UNIX系统）：sleep(chan,pri)其中：chan进程挂起（睡眠）的原因；pri进程被唤醒后的优先级一般调用形式：susp(chan)其中：chan进程等待的原因,4.3.4进程挂起,4.3.4进程挂起,4.3.5进程唤醒,一个正在运行的进程会因等待某事件（例如，等待打印机）的发生，由运行状态转换成阻塞状态而当它等待的事件发生后，这个进程将由阻塞状态转换成就绪状态。这种转换由进程唤醒操作完成。,4.3.5进程唤醒,(1)进程唤醒原语的形式当处于等待状态的进程所期待的事件来到时，由发现者进程唤醒。wakeup(chan)入口参数chan：进程等待的原因。(2)进程唤醒原语的功能当进程等待的事件发生时，唤醒等待该事件的所有进程或等待该事件的首进程。,4.3.5进程唤醒,调用进程唤醒操作一般在中断处理、进程通信等过程中。例如，打印机完成中断处理程序，在完成了打印完成的操作后，就去检查等待打印机的队列，若不为空，则调用进程唤醒操作，唤醒一个（或多个）等待打印机的进程。,4.3.5进程唤醒,算法：wakeup输入：chan:等待的事件（阻塞原因）输出：无找到chan的等待队列的指针；for(该队列不为空）从队列中移出一个进程；置进程状态为“就绪”，并加入到就绪队列；,4.3.5进程唤醒,按此算法，是把等待在chan事件上的所有进程唤醒，类似于UNIX系统的处理方式。也有的系统只唤醒一个等待chan事件的进程，若这样处理，等待队列就要按某种优先级排队。进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。,进程调度的基本算法,时间片轮转算法把处理机的时间分成大小相等的时间片，进程的调度按照时间片进行。,参看动画,4.4进程的相互制约关系,在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。产生这种错综复杂的相互制约关系的原因有二：资源共享进程合作,进程间的关系,进程之间有两种关系：第一种是竞争关系，从而有进程的互斥(MutualExclusion)是解决进程间竞争关系的手段。第二种是协作关系，某些进程为完成同一任务需要分工协作。进程的同步(Synchronization)是解决进程间协作关系的手段。,进程间的关系,进程的互斥(MutualExclusion)是指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。临界区管理可以解决进程互斥问题，后续课程将详细介绍临界区的解决方案。,进程间的关系,进程的同步(Synchronization)是解决进程间协作关系的手段。指一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时则等待，直到消息到达才被唤醒。不难看出，进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源。,进程间的关系,对于协作关系有如下例子：设input、process、和output三个进程分工协作完成读入数据、加工处理和打印输出任务，这是一种典型的协作关系。操作系统要确保诸进程在执行次序上协调一致：没有输入完一块数据之前不能加工处理没有加工处理完一块数据之前不能打印输出等等每个进程都要接收到它进程完成一次处理的消息后，才能进行下一步工作。,4.5.1互斥的概念,引例：宿舍固定电话的使用打印机的使用还有内存变量、指针、数组等等也是临界资源。,临界资源说明,例1：两个进程A、B共享一台打印机若不加以控制，两个进程的输出结果可能交织在一起，很难区分。,临界资源说明,例2：两个进程共享一个变量x设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2，两个进程共享一个变量x时，两种可能的执行次序：,情况B为x=10+1,说明,以前的课程也讲到了与时间有关的错误，其实就是因为共享变量，这个共享的变量就是临界资源。如果不对临界资源加以控制，那么就可能出现错误，这就是本节要解决的问题。,什么是临界资源,特点：当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。一次仅允许一个进程使用的资源称为临界资源。,哪些临界资源？,临界资源：物理设备，如输入机、打印机、磁带机等都具有这种性质。软件资源，如公用变量、数据、表格、队列等也都具有这一特点。,什么是临界区,临界区：在每个进程中，访问临界资源的那段程序能够从概念上分离出来，称为临界区或临界段。它就是进程中对公共变量(或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区。,什么是临界区,什么是临界区,什么是互斥？,互斥：在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。,例如上图所示：进程A正在执行csa段时，进程B就不能进入csb段执行。,进入临界区的准则：,进入临界区的准则：(1)每次至多有一个进程处于临界区；(2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入；(3)进程在临界区内仅逗留有限的时间。,4.5.2锁和上锁、开锁操作,解决进程互斥的最简单的办法是加锁。什么是锁用某假设变量w代表某种资源的状态，w称为“锁”。锁位值：为“0”表示资源可用为1表示资源已被占用（不可用）。在系统中为每个临界资源设置一个锁位。,4.5.2锁和上锁、开锁操作,当一个进程使用某个临界资源之前必须完成下列操作：1、考察锁位的值(是0还是1)；2、若原来的值是为“0”，将锁位置为“1”，此为上锁操作（表示占用该资源）；3、若原来值是为“1”，（该资源已被别人占用），则不改变原来的值，循环检测等待。4、当某进程使用完资源后，将锁位置为“0”，称为开锁操作，此时别的等待进程一旦检测到w的不为1了，则表示可以使用临界资源了。,4.5.2锁和上锁、开锁操作,说明,在上述简单的关锁原语中，goto语句使得lock(w)原语的进程占用处理机而等待进入互斥段（称为忙等待busywaiting)测试法，浪费CPU时间。为此，可将上述上锁原语和开锁原语做进一步修改。修改后的原语如下所示：,改进的lock和unlock算法,锁和上锁、开锁操作,设临界区的类名为w。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位keyw。keyw表示该锁定位属于类名为w的临界区。加锁后的临界区程序描述如下：lock(keyw)/上锁unlock(keyw)/开锁,经过锁处理，任何时候都不可能有两个及以上的进程进入临界去。,4.5.3用上锁原语和开锁原语实现互,假设有两个进程共享打印机，两个进程中使用打印机的程序段为临界区。为保证打印的正确，设置打印机的锁print，其初值为“0”，表示打印机可用。,4.5.3用上锁原语和开锁原语实现互斥,4.6.1信号灯的概念,前面介绍的方法虽能保证互斥，可正确解决临界区调度问题，但有明显缺点：对不能进入临界区的进程，采用忙式等待(busywaiting)测试法，浪费CPU时间。将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。,4.6.1信号灯的概念,1965年荷兰的计算机科学家Dijkstra提出了新的同步工具信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过信号量(Semaphore)展开交互。进程在某一特殊点上停止执行直到得到一个对应的信号量，通过信号量这一设施，任何复杂的进程交互要求可得到满足，这种特殊的变量就是信号量。,4.6.1信号灯的概念,信号量仅能由同步原语对其进行操作，原语是操作系统中执行时不可中断的过程、即原子操作(AtomicAction)。Dijkstra发明了两个同步原语：P操作和V操作(荷兰语中“测试(Proberen)”和“增量(Verhogen)”的头字母，此外还用的符号有：wait和signal；up和down；sleep和wakeup等。本书中采用Dijkstra最早论文中使用的符号P和V。利用信号量和P、V操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题。,信号灯的分类,信号量按其用途可分为两种：公用信号量：联系一组并发进程，相关的进程均可在此信号量上执行P和V操作。初值常常为1，用于实现进程互斥。私有信号量：联系一组并发进程，仅允许此信号量拥有的进程执行P操作，而其他相关进程可在其上施行V操作。初值常常为0或正整数，多用于并发进程同步。,信号灯的分类,信号量按其取值可分为两种：二元信号量：仅允许取值为0和1，主要用于解决进程互斥问题（非我即你，通常用一个布尔量来表示）。一般信号量：允许取值为非负整数，主要用于解决进程间的同步问题。,4.6.1信号灯的概念,信号灯的定义：信号灯是一个确定的二元组（s,q），s是一个具有非负初值的整型变量，q是一个初始状态为空的排队站。S代表资源的实体。在实际应用中应准确地说明s的意义和初值，每个信号灯都有一个队列，其初始状态为空。,4.6.2P、V操作,信号灯的值仅能由P、V操作来改变，对信号灯的P操作记为：P(S)，P操作是一个原子操作。对信号灯的V操作记为：V(S),V操作是一个原子操作。在实际操作系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。,信号量值的物理意义,信号灯是整型变量。变量值0时，表示绿灯，进程执行。变量值0:其数值代表可用的资源数量S=0：代表无资源可用，但也没有等待的进程，即也没有申请资源的进程S0:其|S|表示等待队列中想申请资源而还没有成功的进程数量,用信号灯实现进程互斥的例子,设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。试用信号灯的P、V操作实现这两个进程的互斥。设：mutex为互斥信号灯，初值为1（通过pv操作，可以解决与时间有关的错误）,五个哲学家就餐问题,下面再来看一下使用互斥信号量和PV操作解决操作系统经典的五个哲学家就餐问题。有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。,五个哲学家就餐,五个哲学家就餐问题,在这道题目中，每一把叉子都是必须互斥使用的，因此应为每把叉子设置一个互斥信号量Si，初值均为1。当一个哲学家吃通心面前必须获得自己左边和右边的两把叉子，即执行两个P操作，吃完通心面后必须放下叉子，即执行两个V操作。程序如下：,#typedefintsemaphere;semaphorechopstick5;for(inti=0;i0:其数值代表可用的资源数量S=0：代表无资源可用，但也没有等待的进程，即也没有申请资源的进程S=0,不能为负值,多缓冲的生产者消费者问题,问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。即满足如下条件：（1）消费者想接收数据时，有界缓冲区中至少有一个单元是满的。（2）生产者想发送数据时，有界缓冲区中至少有一个单元是空的。,生产者消费者的例子,例1：计算进程和打印进程计算进程cp不断产生数据，是生产者；打印进程iop不断打印数据，是消费者。例2：通信问题发消息进程send不断产生消息，是生产者；收消息进程receive不断接收消息，是消费者,多生产者-消费者问题图示,生产者与消费者,生产者：当有界缓冲区中无空位置时，要等待；向有界缓冲区放入物品后，要发消息（V操作）。消费者：当有界缓冲区中无物品时，要等待；从有界缓冲区取出物品后，要发消息（P操作）。,多缓冲区的P-C问题之间的关系,一、同步关系：对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。,多缓冲区的P-C问题之间的关系,二、互斥关系缓冲区又是个临界资源，在多个进程在生产产品时，它不允许在缓冲区的某一个单元同时存放产品也不允许多个进程同时消费缓冲区的某一个单元产品，因此，还有个互斥的问题。,多生产者-消费者问题的一般解答,信号灯设置两个同步信号灯empty:表示空缓冲区的数目，初值为有界缓冲区的大小n；full:表示满缓冲区的数目，其初值为0；一个互斥信号灯-mutex：互斥信号灯，初值为1。,同步描述,程序描述,程序描述,多生产者-消费者问题的flash动画,多生产者-消费者问题的flash动画,思考与说明,如果我们把生产者进程中的两个P操作交换次序，即那么会有什么问题吗？参见下图的程序参考：,主程序,并行程序,思考与说明,在这个问题中P操作的次序是很重要的，如果我们把生产者进程中的两个P操作交换次序，即那么就会产生与时间有关的错误。分析如下：,分析说明,在某个时刻,消费者消费的比较快，把所有的产品消费完，有:empty=n,mutex=1,full=0接着消费者进程运行到1处，使得mutex=0,运行到2处full=-10，消费者进程等待在接着生产者进程运行到3处，由于生产了一个产品，故空位置-1，empty=n-1，运行到4初,由于p(mutex)操作，mutex=mutex-1=-10表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源V(S)：表示释放一个资源。信号量的初值应该大于等于0,信号量及P、V操作讨论,2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要,信号量及P、V操作讨论（续1）,3）P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂,信号量及P、V操作讨论（续2）,回顾：哲学家就餐问题,问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,哲学家就餐问题解法（1）,#defineN5voidphilosopher(inti)while(true)思考；取forki;取fork(i+1)%5；进食；放f