第4章并发控制1.ppt

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

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

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

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

4、coend;Si(i=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 程序的并发执行,10,4.1 并发活动进程的引人4.1.3 并发执行实行誊抄一、一个循环程序顺序执行的誊抄,算法1：输入：f 输出：g wh

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

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

7、出程序取走的是“N”，“B”就丢失了。,14,4.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄,get程序负责人输入序列f中读取字符并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。,15,4.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄,假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。这个算法是正确的。,16,4.1 并发活动进程的引人4.1.4

8、 与时间有关的错误,假定f系列中有记录 f=(R1,R2,.,Rn)g=()在誊抄完成后：f=()g=(R1,R2,.,Rn)算法中的：copy：t=s put:put(t,g)get:get(s,f),17,4.1 并发活动进程的引人4.1.4 与时间有关的错误,若程序错写成：while(誊抄未完成）cobegin copy;put;get;coend,18,4.1 并发活动进程的引人4.1.4 与时间有关的错误,R1,R2,.,Rn,f,s,t,g,get,copy,put,R2,R3,.,Rn,R1,f,s,t,g,get,copy,put,copy,put,get,get,R3,R4,

9、.,Rn,R2,R1,R1,f,s,t,g,get,copy,put,19,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)这就是与时间有关的错误。,20,4.1 并发活动进程的引

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

11、对应多个用户源程序的情况。,22,4.1 并发活动进程的引人4.1.5 程序并发执行的特点,三、程序并发执行的相互制约 在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。回头来，我们再看看操作系统的第三个特性：不确定性,23,4.2 进程概念(process)4.2.1 进程的定义,在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引入新的概念进程。进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，

12、在IBM的OS/360/370系统中也曾叫过任务（task)。,24,4.2 进程概念(process)4.2.1 进程的定义进程的定义（枚举法）,行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（Ken Thompson and Dennis Ritchie)国内78年庐山会议定义：进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。,25,4.2 进程

13、概念(process)4.2.1 进程的定义 进程与程序的区别与联系：,1、程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并行（并发）活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。,26,4.2 进程概念(process)4.2.2 进程的类型,在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程 系统进程起着资源管理和控制的作用。或者：执行操

14、作系统核心代码的进程。2、用户进程 执行用户程序的进程。,27,4.2 进程概念(process)4.2.2 进程的类型,系统进程与用户进程的区别：1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。另一种分类：计算进程，I/O进程等注意：在UNIX系统中没有这样对进程进行分类。,28,4.2 进程概念(process)4.2.3 进程的状态,一、进程的基本状态进程在系统中的

15、活动规律是：执行 暂停 执行进程的三种基本状态：运行状态 就绪状态 等待状态（又称阻塞、挂起、睡眠）,29,4.2 进程概念(process)4.2.3 进程的状态 一、进程的基本状态,1、就绪状态（Ready)存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所取的状态为就绪状态。（有多个进程处于此状态）2、运行状态(Running）当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，总只有一个进程处于此状态）3、等待状态（Wait)若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执

16、行，这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。,30,4.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图,进程的状态不是固定不变的，而是在不断变换。,31,4.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图,运行=等待：等待某事件的发生（如等待I/O完成）等待=就绪：事件已经发生（如I/O完成）运行=就绪：时间片到新建进程=就绪：新创建的进程进入就绪状态就绪=运行：当处理机空闭时，由调度（分派）程序从就绪进程队列中选择一个进程占用CPU。,32,4.2 进程概念(process)4.2.3 进程的状态,三、作业、作业状态及转

17、移 在批处理系统中一个用户程序的执行的全过程称为一个作业，当作业提交给计算中心（或机房）后，由机房工作人员录入到存储设备上（如磁带、磁盘等），然后，由作业调度程序按某种调度策略将作业调入计算机系统执行，执行完成后，由作业调度程序做作业的善后处理工作，至此一个作业完成。,33,4.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移,我们把上述对作业的操作归纳成四种状态：1、提交状态 用户将自己的程序和数据放在输入设备上，等待；2、后备状态 系统响应用户的要求，将作业带领到直接存取的后援存储器中，等待调度；3、执行状态 从作业计算开始，到计算完成为止，该作业处于执行状态。

18、4、完成状态 从作业计算完成开始，到善后处理完毕退出系统为止，称为作业完成状态。,34,4.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移,35,4.2 进程概念(process)4.2.4 进程描述,在系统中一个进程存在：进程控制块（数据结构）进程的执行程序（一个可执行文件）进程总是位于某个队列(就绪、等待某事件队列)处于某种状态（运行、就绪、等待）占用某些系统资源（内存，打开某些文件、处理机、外设）,36,4.2 进程概念(process)4.2.4 进程描述,进程控制块 PCB(Process Control Block)存放进程的管理和控制信息的数据结构称

19、为进程控制块。它是进程管理和控制的最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。,37,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,1、进程标识符 name 每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。UNIX系统中就是一个整型数。在进程创建时由系统赋予。2、进程当前状态 status 说明进程当前所处的状态。为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等。,38,4

20、.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,3、当前队列指针 next 登记与本进程处于同一队列的下一个进程的PCB的地址。,39,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,4、总链指针 all-q-next5、执行程序开始地址 start-addr6、进程优先级 priority 进程的优先级反映进程的紧迫程序，通常由用户指定和系统设置。UNIX系统采用用户设置和系统计算相结合的方式确定进程的优先级。,40,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,7、CPU现场保护区 cpu status 当进程因

21、某种原因不能继续占用CPU时（等待打印机），释放CPU，这时就要将CPU的各种状态信息保护起来，为将来再次得到处理机恢复CPU的各种状态，继续运行。8、通信信息 communication information 进程在运行的过程中要与其它进程进行通信，该区记录有关进程通信方面的信息。,41,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,9、家族联系 process family 有的系统允许一个进程可创建自已的子进程，子进程还可以创建，一个进程往往处在一个家族之中，就需要记录进程在家族中位置的信息。10、占有资源清单 own-resource 进程占用系统资源的情

22、况。,42,4.3 进程控制4.3.1 进程控制的概念,进程是有生命周期的，产生、运行、暂停、终止。对进程的这些操作叫进程控制。进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须提供对进程实行有效的管理。,43,4.3 进程控制4.3.1 进程控制的概念,进程控制包括：进程创建、进程撤消、进程阻塞、进程唤醒。这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。,44,4.3 进程控制4.

23、3.1 进程控制的概念,运行状态 等待状态 进程阻塞等待状态 就绪状态 进程唤醒新建进程置为就绪状态 进程创建进程终止（消亡）进程撤消就绪状态运行状态 进程调度,45,4.3 进程控制4.3.1 进程控制的概念,在UNIX系统中进程控制的系统调用有：fork()创建子进程 sleep()进程睡眠 exit()进程自已终止（自杀）wait()(父）等待子进程终止 wakeup()进程唤醒 在4.9节介绍。,46,4.3 进程控制4.3.2 进程创建,在UNIX系统中用户键入一个命令（如date,ps,ls)，shell就创建一个进程。一个程序（可执行的）如果可分成几个程序段，并且这些程序段可并发

24、执行，用户程序可使用创建程序的系统调用创建多个进程，每个进程执行一个程序段。例如，放VCD程序。,47,4.3 进程控制4.3.2 进程创建,进程创建系统调用：create(name,priority,start-addr)UNIX系统：fork(),48,4.3 进程控制4.3.2 进程创建,49,4.3 进程控制4.3.3 进程撤消,进程完成其任务，希望终止时，调用撤消进程的系统调用（进程撤消原语）撤消进程。在一般操作系统中进程撤消的系统调用是：kill UNIX系统中是exit()。,50,4.3 进程控制4.3.3 进程撤消,51,4.3 进程控制4.3.3 进程撤消,52,4.3 进

25、程控制4.3.4 进程挂起,当一个处在运行状态的进程，因等待某个事件的发生（如等待打印机）而不能继续运行时，将调用进程挂起系统调用，把进程的状态置为阻塞状态，并调用进程调度程序（等于让出处理机）。在UNIX系统中进程挂起调用sleep(chan,pri)。,53,4.3 进程控制4.3.4 进程挂起,进程从运行状态转换成阻塞状态是由进程挂起原语实现的，因此，调用进程挂起操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变.例如，进程是因等待打印机而进入阻塞状态，则该进程将加入到等待打印机的队列。进程挂起系统调用的算法和队列变化如下。,54,4.3 进程控制4.3.4 进程挂起

26、,进程挂起的内部调用形式（UNIX系统）：sleep(chan,pri)其中：chan 进程挂起（睡眠）的原因；pri 进程被唤醒后的优先级 一般调用形式：susp(chan)其中：chan 进程等待的原因,55,4.3 进程控制4.3.4 进程挂起,56,4.3 进程控制4.3.4 进程挂起,57,4.3 进程控制4.3.5 进程唤醒,一个正在运行的进程会因等待某事件（例如，等待打印机）的发生，由运行状态转换成阻塞状态，当它等待的事件发生后，这个进程将由阻塞状态转换成就绪状态。这种转换由进程唤醒操作完成。调用进程唤醒操作一般在中断处理、进程通信等过程中。例如，打印机完成中断处理程序，在完成了

27、打印操作后，就去检查等待打印机的队列，若不为空，则调用进程唤醒操作，唤醒一个（或多个）等待打印机的进程。,58,4.3 进程控制4.3.5 进程唤醒,进程唤醒原语的形式：wakeup(chan)其中：chan 唤醒进程阻塞的原因。,59,4.3 进程控制4.3.5 进程唤醒,算法：wakeup输入：chan:等待的事件（阻塞原因）输出：无 找到chan的等待队列的指针；for(该队列不为空）从队列中移出一个进程；置进程状态为“就绪”，并加入到就绪队列；,60,4.3 进程控制4.3.5 进程唤醒,按此算法，是把等待在chan事件上的所有进程唤醒，类似于UNIX系统的处理方式。也有的系统只唤醒一

28、个等待chan事件的进程，若这样处理，等待队列就要按某种优先级排队。进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。,61,4.4进程的相互制约关系 4.4.1 进程竞争与合作,在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。产生这种错综复杂的相互制约关系的原因有二：资源共享 进程合作,62,4.4进程的相互制约关系4.4.2 互斥的概念,引例：宿舍电话的使用；打印机的使用；1.临界资源：一次仅允许一个进程使用的资源称为临

29、界资源。引例中的电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。,63,4.4进程的相互制约关系4.4.2 互斥的概念,2、临界区：每个进程中访问临界资源的那段程序段称为临界区（临界段）。,64,4.4进程的相互制约关系4.4.2 互斥的概念,互斥定义:在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生(后果)无法估计的错误。我们把进程之间的这种相互制约的关系称为互斥。例如：飞机定票系统中的机票库,65,4.4进程的相互制约关系4.4.2 互斥的概念,进入临界区的准则：(1)每次至多有一个进程处于临界区；(2)当有若干个进程欲进入临界

30、区时，应在有限的时间内使其进入；(3)进程在临界区内仅逗留有限的时间。,66,4.4进程的相互制约关系 4.4.2 互斥的概念,解决进程互斥的最简单的办法是加锁。在系统中为每个临界资源设置一个锁位，0 表示资源可用，1 表示资源已被占用（不可用）。这样当一个进程使用某个临界资源之前必须完成下列操作：1、考察锁位的值；2、若原来的值是为“0”，将锁位置为“1”（占用该资源）；3、若原来值是为“1”，（该资源已被别人占用），则转到1。当进程使用完资源后，将锁位置为“0“，称为开锁操作。,67,4.4进程的相互制约关系 4.4.3 进程同步的概念,看病进程：看病；要病人去化验；等待化验结果；继续看病；,化验进程：有化验单；进行化验；给出化验结果；,例1：,68,例2：司机P1 售票员P2 REPEAT REPEAT 启动 关门 正常运行 售票 到站停 开门 UNTIL FALSE UNTIL FALSE,司机启动车辆的动作必须于售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。,