操作系统原理第四章并发处理A.ppt

上传人:牧羊曲112 文档编号:6118675 上传时间:2023-09-26 格式:PPT 页数:68 大小:649KB
返回 下载 相关 举报
操作系统原理第四章并发处理A.ppt_第1页
第1页 / 共68页
操作系统原理第四章并发处理A.ppt_第2页
第2页 / 共68页
操作系统原理第四章并发处理A.ppt_第3页
第3页 / 共68页
操作系统原理第四章并发处理A.ppt_第4页
第4页 / 共68页
操作系统原理第四章并发处理A.ppt_第5页
第5页 / 共68页
点击查看更多>>
资源描述

《操作系统原理第四章并发处理A.ppt》由会员分享,可在线阅读,更多相关《操作系统原理第四章并发处理A.ppt(68页珍藏版)》请在三一办公上搜索。

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

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

3、这些作业系统中执行时是对时间的偏序,有些操作必须在其它操作之前执行,这是有序的,但有些操作是可以同时执行的。例如:I1、C1、P1的执行必须严格按照I1,C1,P1的顺序,而P1与I2,C1与I2,I3与P1是可以同时执行的。,7,4.1 并发活动进程的引人4.1.2 程序的并发执行,例如:I1、C1、P1的执行必须严格按照I1,C1,P1的顺序,而P1与I2,C1与I2,I3与P1是可以同时执行的。,8,4.1 并发活动进程的引人4.1.2 程序的并发执行,程序并发执行(定义)若干个程序段同时在系统中运行,这些程序的执行在时间上是重迭的,一个程序段的执行尚未结束,另一个程序段的执行已经开始,

4、即使这种重迭是很小的,也称这几个程序段是并发执行的。,9,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提出的。,10,4.1 并发活动进程的引人4.1.2 程序的并发执行,假设有一个程序由S0Sn+1个语句,其中 S1Sn语句是并发执行的,程序如下:S0;cobegin S1;S2;S3;.;SN coend;Sn+1;,

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

6、/*输入程序段*/input;/*从标准输入设备读入一个数据*/send;/*将读入的数据送到bufferf*/while(buffer不为空)/*输出程序段*/receive;/*从bufferf中取数据*/output;/*送打印机输出*/coend,14,4.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄,这两个程序段并发执行时可能出现如下情况:1、输出程序运行的速度比输入程序快时,有些输出会重复;如输入送入了一个字符“A”,输出取出打印“A”,当输入还未送入新的数据,输出程序已执行,又取出“A”打印,这样“A”的输出就重复了,出错。2、输入程序执行的速度

7、比输出程序快时,有些数据会丢失;如输入程序送入一个字符“B”,紧接着(当输出程序还未取走字符“B”)又送入字符“N”,这时输出程序取走的是“N”,“B”就丢失了。,15,4.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄,get程序负责人输入序列f中读取字符并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。,16,4.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄,假设有两个缓冲区,每个缓冲区只存放一个字符,get程序负责从输入序列f中读一个字符,然后,送到缓冲区s中,copy

8、程序负责将s中的字符复制到t中,put负责从t中提取字符打印。这个算法是正确的。,17,4.1 并发活动进程的引人4.1.4 与时间有关的错误,假定f系列中有记录 f=(R1,R2,.,Rn)g=()在誊抄完成后:f=()g=(R1,R2,.,Rn)算法中的:copyt=s put put(t,g)get get(s,f),18,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=

9、R1,t=(),g=(),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 并发活动进程的引人4.1.5 程序并发执行的特点,一、失去了

10、程序的封闭性 如果程序执行的结果是一个与时间无关的函数,即具有封闭性。若一个程序的执行可改变另一个程序的变量,象二个并发程序完成誊抄的例子,程序执行的结果不仅依赖于程序的初始条件,还依赖于程序执行时的相对速度,在这种情况下就失去了程序的封闭性。教材P62介绍了两个并发程序共享变量的例子,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)教材上给出的进程的定义:进程,即是一个具有一定独立功能的程序关于某个数据集合的一次活动。,25,4.2 进程

13、概念(process)4.2.1 进程的定义 进程与程序的区别与联系:,1、程序是指令的集合,是静态的概念。进程是程序在处理机上的一次执行的过程,是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位,能与其它进程并行(并发)活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位,也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序,一个进程也可以运行多个程序。,26,4.2 进程概念(process)4.2.1 进程的定义 进程与程序的区别与联系:,例子:光盘(CD、VCD)光盘(程序)放光盘的活动(进程),27,4.2 进程概念

14、(process)4.2.2 进程的类型,在系统中同时有多个进程存在,但归纳起来有两大类:1、系统进程 系统进程起着资源管理和控制的作用。或者:执行操作系统核心代码的进程。2、用户进程 执行用户程序的进程。,28,4.2 进程概念(process)4.2.2 进程的类型,系统进程与用户进程的区别:1、系统进程被分配一个初始的资源集合,这些资源可以为它独占,也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源;2、用户进程不能直接做I/O操作,而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动,而用户进程则在用户态(目态)下活动。另一种分类:计算进程,I/O

15、进程等注意:在UNIX系统中没有这样对进程进行分类。,29,4.2 进程概念(process)4.2.3 进程的状态,一、进程的基本状态进程在系统中的活动规律是:执行 暂停 执行进程的三种基本状态:运行状态 就绪状态 等待状态(又称阻塞、挂起、睡眠),30,4.2 进程概念(process)4.2.3 进程的状态 一、进程的基本状态,1、就绪状态(Ready)存在于处理机调度队列中的那些进程,它们已经准备就绪,一旦得到CPU,就立即可以运行,这些进程所取的状态为就绪状态。(有多个进程处于此状态)2、运行状态(Running)当进程由调度/分派程序分派后,得到CPU控制权,它的程序正在运行,该进

16、程所处的状态为运行状态。(在系统中,总只有一个进程处于此状态)3、等待状态(Wait)若一个进程正在等待某个事件的发生(如等待I/O的完成),而暂停执行,这时,即使给它CPU时间,它也无法执行,则称该进程处于等待状态。,31,4.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图,进程的状态不是固定不变的,而是在不断变换。,32,4.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图,运行 等待 等待某事件的发生(如等待I/O完成)等待 就绪 事件已经发生(如I/O完成)运行 就绪 时间片到(例如,两节课时间到,下课)新建进程 就绪 新创建的进程进入就绪

17、状态就绪 运行 当处理机空闭时,由调度(分派)程序从就绪进程队列中选择一个进程占用CPU。,33,4.2 进程概念(process)4.2.3 进程的状态,三、作业、作业状态及转移 在批处理系统中一个用户程序的执行的全过程称为一个作业,当作业提交给计算中心(或机房)后,由机房工作人员录入到存储设备上(如磁带、磁盘等),然后,由作业调度程序按某种调度策略将作业调入计算机系统执行,执行完成后,由作业调度程序做作业的善后处理工作,至此一个作业完成。,34,4.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移,我们把上述对作业的操作归纳成四种状态:1、提交状态 用户将自己的

18、程序和数据放在输入设备上,等待;2、后备状态 系统响应用户的要求,将作业带领到直接存取的后援存储器中,等待调度;3、执行状态 从作业计算开始,到计算完成为止,该作业处于执行状态。4、完成状态 从作业计算完成开始,到善后处理完毕退出系统为止,称为作业完成状态。,35,4.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移,36,4.2 进程概念(process)4.2.4 进程描述,在系统中一个进程存在:进程控制块(数据结构)进程的执行程序(一个可执行文件)进程总是位于某个队列(就绪、等待某事件队列)处于某种状态(运行、就绪、等待)占用某些系统资源(内存,打开某些文件、

19、处理机、外设),37,4.2 进程概念(process)4.2.4 进程描述,进程控制块 PCB(Process Control Block)存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构,在创建时,建立PCB,并伴随进程运行的全过程,直到进程撤消而撤消。PCB就象我们的户口。,38,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,1、进程标识符 name 每个进程都必须有一个唯一的标识符,可以是字符串,也可以是一个数字。UNIX系统中就是一个整型数。在进程创建时由系统赋予。2、进程当前状态 status 说明进程当前所处的状态

20、。为了管理的方便,系统设计时会将相同的状态的进程组成一个队列,如就绪进程队列,等待进程则要根据等待的事件组成多个等待队列,如等待打印机队列、等待磁盘I/O完成队列等等。,39,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,3、当前队列指针 next 登记与本进程处于同一队列的下一个进程的PCB的地址。,40,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,4、总链指针 all-q-next5、执行程序开始地址 start-addr6、进程优先级 priority 进程的优先级反映进程的紧迫程序,通常由用户指定和系统设置。UNIX系统采用用户

21、设置和系统计算相结合的方式确定进程的优先级。,41,4.2 进程概念(process)4.2.4 进程描述进程控制块 PCB,7、CPU现场保护区 cpustatus 当进程因某种原因不能继续占用CPU时(等待打印机),释放CPU,这时就要将CPU的各种状态信息保护起来,为将来再次得到处理机恢复CPU的各种状态,继续运行。例如,我们下课,这时我要记住这次讲到什么地方,下次课接着讲。8、通信信息 communication information 是指某个进程在运行的过程中要与其它进程进行通信,该区记录有关进程通信方面的信息。,42,4.2 进程概念(process)4.2.4 进程描述进程控制

22、块 PCB,9、家族联系 process family 有的系统允许一个进程可创建自已的子进程,子进程还可以创建,一个进程往往处在一个家族之中,就需要记录进程在家族中位置的信息。10、占有资源清单 own-resource 进程占用系统资源的情况,不同的系统的处理差别很大,UNIX系统中就没有此项。,43,4.3 进程控制4.3.1 进程控制的概念,进程是有生命周期的,产生、运行、暂停、终止。对进程的这些操作叫进程控制。进程控制的职责是对系统中全部进程实施有效的管理,它是处理机管理的部分(另一部分是进程调度),当系统允许多进程并发执行时,为了实现共享、协调并发进程的关系,处理机管理必须提供对进

23、程实行有效的管理。,44,4.3 进程控制4.3.1 进程控制的概念,进程控制包括:进程创建、进程撤消、进程阻塞、进程唤醒。这些操作都要对应地执行一个特殊的程序段(操作系统核心程序),同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语(一种特殊的系统调用)。,45,4.3 进程控制4.3.1 进程控制的概念,运行状态 等待状态 进程阻塞等待状态 就绪状态 进程唤醒新建进程置为就绪状态 进程创建进程终止(消亡)进程撤消就绪状态 运行状态 进程调度,46,4.3 进程控制4.3.1 进程控制的概念,在UNIX系统中进程控制的系统调用有:fork()创建子进程 sleep()进程睡眠 ex

24、it()进程自已终止(自杀)wait()(父)等待子进程终止 wakeup()进程唤醒 在4.9节介绍。,47,4.3 进程控制4.3.2 进程创建,在UNIX系统中用户键人一个命令(如date,ps,ls),shell就创建一个进程。一个程序(可执行的)如果可分成几个程序段,并且这些程序段可并发执行,用户程序可使用创建程序的系统调用创建多个进程,每个进程执行一个程序段。例如,放VCD程序。进程创建类似于人出生后要到派出所报户口。,48,4.3 进程控制4.3.2 进程创建,进程创建系统调用:create(name,priority,start-addr)UNIX系统:fork(),49,4.

25、3 进程控制4.3.2 进程创建,50,4.3 进程控制4.3.3 进程撤消,进程完成其任务,希望终止时,调用撤消进程的系统调用(进程撤消原语)撤消进程。相当于一个人死亡后,家人要去派出所消户口。在一般操作系统中进程撤消的系统调用是:kill UNIX系统中是exit()。,51,4.3 进程控制4.3.3 进程撤消,52,4.3 进程控制4.3.3 进程撤消,53,4.3 进程控制4.3.4 进程挂起,当一个处在运行状态的进程,因等待某个事件的发生(如等待打印机)而不能继续运行时,将调用进程挂起系统调用,把进程的状态置为阻塞状态,并调用进程调度程序(等于让出处理机)。在UNIX系统中进程挂起

26、调用sleep(chan,pri)。,54,4.3 进程控制4.3.4 进程挂起,进程从运行状态转换成阻塞状态是由进程挂起原语实现的,因此,调用进程挂起操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变.例如,进程是因等待打印机而进入阻塞状态,则该进程将加入到等待打印机的队列。进程挂起系统调用的算法和队列变化如下。,55,4.3 进程控制4.3.4 进程挂起,进程挂起的内部调用形式(UNIX系统):sleep(chan,pri)其中:chan 进程挂起(睡眠)的原因;pri 进程被唤醒后的优先级 一般调用形式:susp(chan)其中:chan 进程等待的原因,56,4.3

27、 进程控制4.3.4 进程挂起,57,4.3 进程控制4.3.4 进程挂起,58,4.3 进程控制4.3.5 进程唤醒,一个正在运行的进程会因等待某事件(例如,等待打印机)的发生,由运行状态转换成阻塞状态,当它等待的事件发生后,这个进程将由阻塞状态转换成就绪状态。这种转换由进程唤醒操作完成。调用进程唤醒操作一般在中断处理、进程通信等过程中。例如,打印机完成中断处理程序,在完成了打印完成的操作后,就去检查等待打印机的队列,若不为空,则调用进程唤醒操作,唤醒一个(或多个)等待打印机的进程。,59,4.3 进程控制4.3.5 进程唤醒,进程唤醒原语的形式:wakeup(chan)其中:chan 唤醒

28、进程阻塞的原因。,60,4.3 进程控制4.3.5 进程唤醒,算法:wakeup输入:chan:等待的事件(阻塞原因)输出:无 找到chan的等待队列的指针;for(该队列不为空)从队列中移出一个进程;置进程状态为“就绪”,并加入到就绪队列;,61,4.3 进程控制4.3.5 进程唤醒,按此算法,是把等待在chan事件上的所有进程唤醒,类似于UNIX系统的处理方式。也有的系统只唤醒一个等待chan事件的进程,若这样处理,等待队列就要按某种优先级排队。进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。,62,4.3 进程控制4.3.5 进程唤醒,按此算法,是把等待在chan事件上的

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

30、许一个进程使用的资源称为临界资源。引例中的电话和打印机都属于临界资源。除此之外,还有内存变量、指针、数组等等也是临界资源。,65,4.5 进程互斥 4.5.1 互斥的概念,2、临界区:每个进程中访问临界资源的那段程序段称为临界区(临界段)。,66,4.5 进程互斥 4.5.1 互斥的概念,互斥定义:在操作系统中,当某一进程正在访问某临界区时,就不允许其它进程进入,否则就会发生(后果)无法估计的错误。我们把进程之间的这种相互制约的关系称为互斥。例如:飞机定票系统中的机票库,67,4.5 进程互斥 4.5.1 互斥的概念,进入临界区的准则:(1)每次至多有一个进程处于临界区;(2)当有若干个进程欲进入临界区时,应在有限的时间内使其进入;(3)进程在临界区内仅逗留有限的时间。,68,4.5 进程互斥 4.5.2 锁和上锁、开锁操作,解决进程互斥的最简单的办法是加锁。在系统中为每个临界资源设置一个锁位,0 表示资源可用,1 表示资源已被占用(不可用)。这样当一个进程使用某个临界资源之前必须完成下列操作:1、考察锁位的值;2、若原来的值是为“0”,将锁位置为“1”(占用该资源);3、若原来值是为“1”,(该资源已被别人占用),则转到1。当进程使用完资源后,将锁位置为“0“,称为开锁操作。,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号