第4章并发控制1.ppt

《第4章并发控制1.ppt》由会员分享，可在线阅读，更多相关《第4章并发控制1.ppt（68页珍藏版）》请在优知文库上搜索。

1、1 第四章 并发处理2第四章 并发处理4.1 并发活动进程的引人 操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。34.1 并发活动进程的引人4.1.1 程序的顺序执行一、概念 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。例如：44.1 并发活动进程的引人4.1.1 程序的顺序执行 二

2、、程序顺序执行的特点1.顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性 程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。3.可再现性 程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。54.1 并发活动进程的引人4.1.2 程序的并发执行例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,.,n)。这些作业系统中执行时是对时间

3、的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如:64.1 并发活动进程的引人4.1.2 程序的并发执行 I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。74.1 并发活动进程的引人4.1.2 程序的并发执行程序并发执行（定义）若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。PQR并发执行区8程序并发执行的描述 cobegin S1;S2;S3;.;SN coend;Si(i=

4、1,2,3,.,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。co是concurrent的头两个字符。这是Dijkstra提出的。4.1 并发活动进程的引人4.1.2 程序的并发执行9假设有一个程序由S0Sn+1个语句，其中 S1Sn语句是并发执行的，程序如下：S0;cobegin S1;S2;S3;.;SN coend;Sn+1;4.1 并发活动进程的引人4.1.2 程序的并发执行104.1 并发活动进程的引人4.1.3 并发执行实行誊抄一、一个循环程序顺序执行的誊抄算法1：输入：f 输出：g while(f 不为空）input;ou

5、tput;由这个程序完成誊抄工作是不会出错的。114.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄 设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。124.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄算法：2 cobegin while(不为结束符）/*输入程序段 */input;/*从标准输入设备读入一个数据*/send;/*将读入的数据送到bufferf*/while(buffer不为空）/*输出程序段*/rec

6、eive;/*从bufferf中取数据*/output;/*送打印机输出*/coend 134.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄这两个程序段并发执行时可能出现如下情况：1、输出程序运行的速度比输入程序快时，有些输出会重复；如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。2、输入程序执行的速度比输出程序快时，有些数据会丢失；如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。144.1

7、 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄get程序负责人输入序列f中读取字符并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。154.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄 假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。这个算法是正确的。164.1 并发活动进程的引人4.1.4 与时间有关的错误假定f系列中有记录 f=(R1,R2,.,R

8、n)g=()在誊抄完成后：f=()g=(R1,R2,.,Rn)算法中的：copy：t=s put:put(t,g)get:get(s,f)174.1 并发活动进程的引人4.1.4 与时间有关的错误若程序错写成：while(誊抄未完成）cobegin copy;put;get;coend 184.1 并发活动进程的引人4.1.4 与时间有关的错误R1,R2,.,RnfstggetcopyputR2,R3,.,RnR1fstggetcopyputcopy,put,getgetR3,R4,.,RnR2R1R1fstggetcopyput194.1 并发活动进程的引人4.1.4 与时间有关的错误然后，

9、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)这就是与时间有关的错误。204.1 并发活动进程的引人4.1.5 程序并发执行的特点一、失去了程序的封闭性 如果程序执行的结果是一个与时间无关的函数，即具有封闭性。若一个程序的执行可改变另一个程

10、序的变量，象二个并发程序完成誊抄的例子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。214.1 并发活动进程的引人4.1.5 程序并发执行的特点二、程序与计算不再一一对应 在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。224.1 并发活动进程的引人4.1.5 程序并发执行的特点三、程序并发执行的相互制约 在多道程序设计的环境下，程序是并发执

11、行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。回头来，我们再看看操作系统的第三个特性：不确定性234.2 进程概念(process)4.2.1 进程的定义 在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引入新的概念进程。进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。244.2 进程概念(process)4.2.1 进程的定义进程的定义（枚举法）行为的一个规则叫做

12、程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（Ken Thompson and Dennis Ritchie)国内78年庐山会议定义：进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。254.2 进程概念(process)4.2.1 进程的定义 进程与程序的区别与联系：1、程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为

13、软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并行（并发）活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。264.2 进程概念(process)4.2.2 进程的类型在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程 系统进程起着资源管理和控制的作用。或者：执行操作系统核心代码的进程。2、用户进程 执行用户程序的进程。274.2 进程概念(process)4.2.2 进程的类型系统进程与用户进程的区别：1、系统进程被分配一个初始的资源集合

14、，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。另一种分类：计算进程，I/O进程等注意：在UNIX系统中没有这样对进程进行分类。284.2 进程概念(process)4.2.3 进程的状态一、进程的基本状态进程在系统中的活动规律是：执行 暂停 执行进程的三种基本状态：运行状态 就绪状态 等待状态（又称阻塞、挂起、睡眠）294.2 进程概念(process)4.2.3 进程的状态 一、进程的基本状态1、就绪状

15、态（Ready)存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所取的状态为就绪状态。（有多个进程处于此状态）2、运行状态(Running）当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，总只有一个进程处于此状态）3、等待状态（Wait)若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。304.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图进程的状态不是固定不变的，而是在不断变换。314.

16、2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图运行=等待：等待某事件的发生（如等待I/O完成）等待=就绪：事件已经发生（如I/O完成）运行=就绪：时间片到新建进程=就绪：新创建的进程进入就绪状态就绪=运行：当处理机空闭时，由调度（分派）程序从就绪进程队列中选择一个进程占用CPU。324.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移 在批处理系统中一个用户程序的执行的全过程称为一个作业，当作业提交给计算中心（或机房）后，由机房工作人员录入到存储设备上（如磁带、磁盘等），然后，由作业调度程序按某种调度策略将作业调入计算机系统执行，执行完成后，由作业调度程序做作业的善后处理工作，至此一个作业完成。334.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移 我们把上述对作业的操作归纳成四种状态：1、提交状态 用户将自己的程序和数据放在输入设备上，等待；2、后备状态 系统响应用户的要求，将作业带领到直接存取的后援存储器中，等待调度；3、执行状态 从作业计算开始，到计算完成为止，该作业处于执行状态。4、完成状态 从作