计算机操作系统(第四版)第二章进程的概念PPT课件

.,1,进程（处理器）管理,1进程的基本概念2进程控制3进程同步4经典进程的同步问题5进程通信6线程,.,2,学习目标,在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的。所以，本章的主要问题是：进程的概念：进程的状态、进程的调度、进程控制与协作、进程的特征进程的同步：同步的概念、同步的实现进程通信,.,3,引言,处理机管理是操作系统的基本管理功能之一，它所关心的是处理机的分配问题。也就是说把CPU（中央处理机）的使用权分给某个程序，通常把这个正准备进入内存的程序称为作业，当这个作业进入内存后我们把它称为进程。处理机管理分为作业管理和进程管理两个阶段去实现处理机的分配，常常又把直接实行处理机时间分配的进程调度工作作为处理机管理的主要内容。进程通常具有三种状态：运行状态（正在使用CPU）、阻塞状态（等待输入/输出）和就绪状态（等待分配CPU）。,.,4,1.程序的顺序执行一个复杂的程序一般均含若干个程序段，并按一定先后顺序执行，每个操作必须在下一个操作开始之前结束。也即仅当前一个操作结束之后，后继操作才开始执行，此即程序的顺序执行性。例如一般程序包括输入(I)、计算(C)、输出(P)三部分，而计算须在输入完成方可开始。,进程概念的引入-程序的顺序执行和并发执行,.,5,2.程序顺序执行时的特征1)顺序性：处理机的操作是严格按照程序所规定的顺序执行的，每一操作开始都不得先于前一操作的结束。2)封闭性：程序一旦开始执行，其执行结果不受外界因素影响。3)确定性、可再现性：程序重复执行将获得相同结果。,程序的顺序执行：一个具有独立功能的程序独占处理机直至得到最终结果的过程称为程序的顺序执行。S1：a:=x+y；S2：b:=a-5；/s2必须是s1执行后再执行S3：c:=b+1；/s3必须是s2执行后再执行S1、S2、S3必须按照顺序依次执行。,优点：有利于程序的编制和调试；缺点：资源的独占性，使得系统利用率很低。,.,6,说明,顺序执行是单道批处理系统的执行方式在单道程序工作环境中，我们把一个“程序”理解为“一个在时间上按严格次序前后相继的操作序列”由于各类软件的出现及日益复杂化，使得程序设计的概念和方法有了很大的发展,.,7,前趋图,前趋图是一个有向无循环图，记为DAG(DrectedAcyclicGraph)，前趋图用来描述程序各部分间的依赖关系或一个大的计算各子部之间的因果关系。前趋图中的元素：结点：表示一个语句、程序段、进程；有向边：表示结点间的偏序关系（前趋关系）=(Pi,Pj)|PimustcompletebeforePjmaystart若(Pi,Pj)，可写成PiPj，称Pi是Pj的直接前趋，而Pj是Pi的直接后继。,.,8,前趋图示例,P2,P3,P1,P6,P7,P4,P5,7个结点的前趋图,前趋关系P1P2,P1P3P1P4,P2P5P3P5,P4P6P5P7,P6P7,在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。,前趋图中能否有循环存在？,.,9,具有循环的图,S1S2S3,S2mustcompletebeforeS3maystart,S3S2,S3mustcompletebeforeS2maystart,.,10,例：下述四条语句的程序段画出前趋图S1：a：x+2S2：b：y4S3：c：abS4：d：c6,S1,S2,S4,S3,.,11,程序的并发执行及其特征,1.程序的并发执行一组逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行，尚未结束，另一个程序段的执行已经开始的这种执行方式。程序的并发执行可分为两种:(1)在计算机系统支持并行操作时，如采用多道程序设计技术，则内存中多道程序处于并发执行状态。,.,12,2.1.2程序间并发执行,I1,P3,输入设备,处理机,打印机,t1,t2,t3,t4,t5,由于多道程序中Ii+1、Ci与Pi-1之间不存在前趋关系，程序之间可以并发执行,.,13,程序的并发执行及其特征,(2)并发执行是在某道程序的几个程序段中包含着一部分可以同时执行或顺序颠倒执行的代码.如:read(a);read(b);可以同时执行,也可颠倒次序执行。对于这样的语句,同时执行不会改变顺序程序所具有的逻辑性质.总结:一组在逻辑上互相独立的程序或程序段在执行过程中其执行时间在客观上互相重叠,即一个程序的执行尚未结束,另一个程序的执行已经开始的执行方式.,.,14,2.程序并发执行时的特征1)间断性:程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。2)失去封闭性:程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。3)不可再现性:程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。,.,15,例如：有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时都要做N：N1操作；程序B每执行一次时，都要做print（N）操作，然后再将N置成“0”，程序A和B以不同的速度运行。（假定某时刻变量N的值为n）（1）N：N1在print（N）和N：0之前，此时得到的N值分别为：n1，n1，0（2）N：N1在print（N）和N：0之后，此时得到的N值分别为：n，0，1（3）N：N1在print（N）和N：0之间，此时得到的N值分别为：n，n1，0,.,16,例：观察者/报告者,观察者：报告者：beginbeginrepeatrepeatwaitacargothroughdelayatimeN=N+1；PrintN；N=0；untiluntilendend初始N=n时不同执行序列：N=N+1；PrintN；PrintN；PrintN；N=0；N=N+1；N=0；N=N+1；N=0；结果各不相同:打印n+1，N=0；打印n，N=1；打印n，N=0；,.,17,程序的并发执行：人们在硬件上引入了通道和中断技术，使得处理器和外部设备、外部设备和外部设备之间可以并行工作。从而使系统的多个程序同时活动，并由统一的操作系统来管理，这就是多道程序系统。,在单道系统中可以用程序代表顺序执行过程，但在多道系统中，程序并行、制约等特征使程序这个静态的概念已不能描述系统的运行情况了，为此操作系统引入了一个新的概念进程。,.,18,进程的特征与状态,1.进程的定义和特征进程：是指在系统中能独立运行并作为资源分配的基本单位，是一个活动实体。简单的理解为，进程是程序在数据集合上的一次运行过程，是系统进行资源分配和调度的基本单位。进程是一个动态的概念，是一个运行过程。它不同于程序，但又依赖于程序。对不同的数据集合，依照一定的程序运行处理的每一个过程是不同的进程。,.,19,进程的特征,1)结构特征从结构上看，进程是由程序段、数据段及进程控制块三部分组成。2)动态性程序是指令的集合，进程是指令的执行过程。动态性是进程最基本的特征。,.,20,3)并发性这是指多个进程实体，同存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也是为了使该进程的程序能和其它进程的程序并发执行。4)独立性进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。没有建立进程的程序，不能作为一个独立的单位参加运行。5)异步性各进程按其各自独立的，不可预知的速度向前推进。,进程的特征,.,21,思考？,进程与程序的区别？,1）进程是程序的执行过程，是一个动态的概念；而程序是一组指令的有序集合，是一个静态的概念；2）进程有一个生命周期，而程序是永久的；3）通过多次执行，一个程序可对应多个进程；4）通过调用关系，一个进程可包括多个程序；5）进程由程序和数据组成。,.,22,作业和进程的关系,作业是用户需要计算机完成某项任务时要求计算机所做的工作的集合。一个作业的完成要经过作业提交、作业后备、作业执行和作业完成四个阶段。进程是对已提交完毕程序的执行过程的描述，是资源分配的基本单位。他们主要区别和关联如下：（1）作业是用户向计算机提交任务的实体，而进程是完成用户任务的实体；（2）一个作业可由多个进程组成，且必须至少由一个进程组成。（3）作业的概念主要用在批处理操作系统中，而进程的概念则几乎用在所有的多道程序操作系统中。,.,23,2.进程的三种基本状态1)就绪(Ready)状态当进程已经分配到除CPU以外的所有必要的资源后，只要能获得处理机，就可以立即执行。这时的进程的状态称为就绪状态。2)执行状态(Running)（运行状态）指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。（在多处理机中，可能有多个进程处于执行状态。）,.,24,3)阻塞状态(Block)（等待状态）进程因发生某个事件而暂停执行时的状态（如：请求I/O、申请缓冲空间等），也就是说，进程受到阻塞，所以称这种暂停状态为阻塞状态，有时也称“等待”状态或“睡眠”状态。,.,25,进程的特征与状态,处于就绪态进程:一般处于就绪态的进程按照一定的算法（如先来的进程排在前面，或采用优先权高的进程排在前面）排成一个就绪队列。处于运行态进程:如系统有一个处理机，则在任何一时刻，最多只有一个进程处于运行态。处于等待态进程:处于等待态的进程排在等待队列中。由于等待事件原因不同，等待队列也按事件原因可分成几个队列。,.,26,进程的基本状态转换,注意的三点：1）进程从阻塞态到执行态，必须经过就绪态；2）进程从执行态到阻塞态，一般由进程自己主动提出的；3）一个进程由执行到就绪态总是由外界事件引起的，而不是该进程自己引起的。,.,27,进程状态间的转换就绪执行：调度执行等待：等待某个事件发生而睡眠等待就绪：因等待的事件结束而唤醒执行就绪：时间片用完,练习：1、如果系统中有n个进程，则就绪队列中进程的个数最多为（）。A、n+1B、nC、n-1D、12、设系统中有关n(n2)个进程，且当前不在执行进程调度程序，试考虑下述四种情况：A、没有运行进程，有2个就绪进程，n个进程处于等待状态。B、有1个运行进程，没有就绪进程，n-1个进程处于等待状态。C、有1个运行进程，有1个就绪进程，n-2个进程处于等待状态。D、有1个运行进程，n-1个就绪进程，没有进程处于等待状态。上述情况中，不可能发生的情况是（）。,C,A,.,28,进程的状态,3创建状态和终止状态1.创建状态是一个进程刚刚建立，但还没有将它送入就绪队列时的状态2.终止状态当一个进程已经正常结束或异常结束，OS已经将它从就绪队列中移出，但还没有将它撤消时的状态。,.,29,创建,就绪,执行,终止,阻塞,许可,进程调度,中断或时间片用完,释放,I/O请求或等待某事件,I/O完成或事件发生,状态转换原因图,万事具备，只欠“东风”CPU,获得CPU正在运行,欠缺某些条件,.,30,创建,就绪,执行,终止,阻塞,进入就绪队列,分配CPU使用权,强制放弃CPU回到就绪队列,释放所有资源,进程主动放弃CPU进入阻塞等待队列,进程被释放回到就绪队列,状态转换执行图,.,31,创建,就绪,事件,动作,许可,进入就绪队列,就绪,执行,进程调度,分配CPU,执行,终止,释放,释放资源,执行,阻塞,时间片到时高优先中断,系统剥夺CPU,执行,就绪,I/O请求等待某事件,进程放弃CPU进入阻塞等待队列,阻塞,就绪,阻塞事件释放,进程进入就绪队列,.,32,4.挂起状态1.挂起状态的引入1)终端用户的需要当终端用户在自己的程序运行期间，发现有可疑问题时，往往希望暂时使自己的进程静止下来。也就是说，如果进程处于执行状态，则暂停执行；如果进程处于就绪状态，则暂时不接受调度，以便研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。,.,33,2)父进程的需求父进程常常希望考察和修改子进程，或者当要协调各子进程间的活动时，要挂起自己的子进程。3)负荷调节的需要当实时系统中的工作负荷较重，可能影响到对实时任务的控制时，可由系统把一些不重要或不紧迫的进程挂起，以保证系统仍然能正常运行。4)操作系统的需要操作系统有时需要挂起某些进程，检查运行中资源的使用情况及进行记帐，以便改善系统的运行性能。,.,34,2.进程状态的转换在引入挂起状态后，又将增加从挂起状态（又称静止状态）到非挂起状态（又称活动状态）的转换。或者相反，可以有以下几种情况：1)活动就绪静止就绪当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态。表示为Readys（处在Readys状态的进程，不再被调度执行。）,.,35,2)活动阻塞静止阻塞当进程处于未被挂起的阻塞状态时，称为它处在活动阻塞状态（表示为Blockeda）。当Suspend原语将它挂起后，进程便转变为静止阻塞状态（表示为Blockeds）。处于该状态的进程，在其所期待的事件出现以后，他将从静止阻塞变为静止就绪。,.,36,3)静止就绪活动就绪处于Readys状态的进程，若用激活原语Active激活后，该进程将转变为Readya状态。4)静止阻塞活动阻塞处于Blockeds状态的进程，若用激活原语Active激活后，进程将转变为Blockeda状态。,.,37,被调度,时间片用完,创建,许可,许可,终止,释放,.,38,正在执行的进程由于时间片用完而被暂停执行，此时进程应从执行状态变为_状态；处于静止阻塞状态的进程，在进程等待事件出现后，应转变为_状态；若进程正处于执行状态时，应终端的请求而暂停下来以便研究其运行情况，这时进程应转变为_状态，若进程已处于阻塞状态，则此时应转变为_状态。-：A.静止阻塞B.活动阻塞C.静止就绪D.活动就绪E.执行,练习：,D,C,C,A,.,39,【思考题】,1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？等待运行；就绪等待3.一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能,.,40,由三部分组成PCB、有关程序段和该程序段对其进行操作的数据集合。1)进程控制块：用于描述进程情况及控制进程运行所需的全部信息。2)程序段：是进程中能被进程调度程序在CPU上执行的程序代码段。3)数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行后产生的中间或最终数据。,进程的结构,.,41,1.进程控制块的作用,进程控制块是操作系统用于记录和刻画进程状态及有关信息的数据结构。进程控制块是进程存在的唯一标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有PCB将构成并发执行控制和维护系统工作的依据。,进程控制块,.,42,处理机状态,进程调度信息,2.进程控制块中的信息,内/外部标识符,通用寄存器,指令计数器,程序状态字PSW,用户栈指针,进程状态,进程优先级,其它信息/事件,程序和数据的地址,进程同步和通信机制,PCB中的信息,进程标识符,进程控制信息,资源清单,链接指针,.,43,为了方便管理,把处于相同状态的进程链接在一起，称为“进程队列”。,常用的组织方式有两种：链接方式（单/双向）、索引方式。,3.进程控制块的组织方式,1、链接方式具有相同状态的PCB，用其中的链接字，链接成一个队列。这样就可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按照进程优先权的大小排列，把优先权高的进程的PCB排在队列前面。进程队列：不同状态进程分别组成就绪队列、等待队列、空白队列。,.,44,.,45,(a)等待队列分开,.,46,(b)等待队列不分开,.,47,.,48,2.索引方式系统根据所有进程的状态，建立几张索引表。例如：就绪索引表、阻塞索引表。并把各索引表在内存的首地址记录在内存中的一些专用单元中。每个索引表的表目中，记录具有相同状态的某个PCB在PCB表中的地址。,.,49,.,50,当事件n发生，对应队列移进就绪队列,.,51,进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。,总结控制块的作用：,.,52,进程控制,为了防止操作系统及关键数据受到破坏，通常将处理机的状态分为管态（系统态）和目态（用户态）。管态：又叫特权态、系统态或核心态。CPU在管态下可以执行指令系统的全集。通常，操作系统在管态下运行。目态：又叫常态或用户态。机器处于目态时，程序只能执行非特权指令。用户程序只能在目态下运行，如果用户程序在目态下执行特权指令，硬件将发生中断，由操作系统获得控制，特权指令执行被禁止，这样可以防止用户程序有意或无意的破坏系统。从目态转换为管态的唯一途径是中断。,.,53,OS内核：通常将一些与硬件紧密相关的模块（中断处理程序），各种常用设备的驱动程序，以及运行频率较高的模块（时钟管理、进程调度）都安排在紧靠硬件的软件层次中，使它们常驻内存，以便提高OS的运行效率，并对它们加以特殊的保护,把这一部分称为OS内核。OS内核通常是运行在系统态的，进程控制是由OS内核中的原语来实现的。进程控制：进程控制的任务就是为作业创建进程，撤消已结束的进程，以及控制进程在运行过程中的状态转换。,.,54,原语,在操作系统中，某些被进程调用的操作，一旦开始执行就不能被中断，否则就会出现操作错误，造成系统混乱。原语就是为实现这些操作而设置的。原语：系统状态下执行的某些具有特定功能的程序段。（原语也是由若干条指令构成的，用于完成一定功能的过程。原子操作在管态下执行，常驻内存。）原语操作：一个操作中的动作要么全做，要么全不做。在操作系统中，通常把进程控制用程序段做成原语。用于进程控制的原语有：创建原语、撤销原语、阻塞原语、唤醒原语等。,.,55,进程的创建,1进程图:进程图是用来描述进程家族关系的有向树。系统初启时，首先创建一个系统总控进程，再由该总控进程创建其他系统进程，这些系统进程一旦创建便永无休止地参与并发运行，为所有的用户进程提供服务，直至系统终止。,.,56,子进程可以继承父进程的所有资源，当子进程被撤消时，应将从父进程那里获得的资源归还给父进程。撤消父进程时也必须同时撤消其所有的子进程。,.,57,2引起创建进程的事件1)用户登录：在分时系统中，用户在终端键入登录命令后，若是合法用户，系统建立一个进程，并插入就绪队列。2)作业调度：批处理系统中，作业调度程序调度到某个作业以后，就把这个作业装入内存，并分配必要的资源，创建进程，插入就绪队列。3)提供服务：运行中的用户向系统提出请求后，系统专门建立一个进程为用户服务。（打印请求）由操作系统核心（系统程序模块）创建4)应用请求：应用进程的需要，由它自己创建一个新进程，使新进程以并发运行方式完成特定任务。（输入数据并将处理结果输出到表格上）由父进程创建,.,58,1申请空白的PCB为新进程分配唯一的数字标识符，并从PCB集合中索取一个空白的PCB2为新建立的进程分配资源为新进程的程序和数据，以及用户栈、分配必要的内存空间。3初始化进程控制块初始化标识符信息:将系统中分配的标识符、父进程标识符填入新PCB中。初始化处理机状态信息。使程序计数器指向程序的入口地址，栈指针指向栈顶。初始化处理机控制信息:将进程的状态设置为就绪状态或静止就绪状态。4将新进程插入就绪队列,3进程的创建过程（creat）,.,59,入口,查PCB链表,有同名?,将PCB入就绪队列将PCB入总链,将入口信息填入PCB相应项,向系统申请一个空的PCB结构,返回,出错,有,创建原语流程图,无,有空PCB?,出错,无,有,.,60,1引起进程终止的事件1)正常结束：计算机系统中，都有一个表示进程已经运行完成的指示。（批处理，Halt。分时系统中，LogsOff）2)异常结束:越界错误、保护错、特权指令错、非法指令错、运行超时、等待超时、算术运算错、I/O故障3)外界干预:操作员或操作系统干预、父进程请求、父进程终止,进程的终止（撤销进程）,.,61,2进程终止过程1根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态2若被终止进程处于执行态，应立即终止该进程的执行，并设置调度标志为真（用于指示该进程被终止时应重新调度），然后再选择一个进程，分配处理机给它。3如果