第二讲进程管理之进程的基本概念还是基本概念一、前趋图(一)前趋图1、作用:为了描述进程之间执行的前后关系,我们常常采用前趋图方式。2、定义:前趋图是一个有向无循环图DAG(DirectedAcyclicGraph)。图中每个节点表示一条语句、一个程序段或进程。有向边表示在两节点之间存在的偏序或前趋关系,表示为“→”,描述为:→={(Pi,Pj)|在Pj开始前Pi必须完成}如果(Pi,Pj)∈→,也就是Pi和Pj存在偏序或前趋关系,那么可写成Pi→Pj,其中我们说Pi是Pj的直接前趋,Pj是Pi的直接后继。每个节点有一个重量,也就是权值,表示节点所含的程序量或者节点的执行时间。*从前趋图的概念我们可知,前趋图中一定没有循环。在该前趋图中:存在下面的前趋关系:P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9;或表示为:P={P1,P2,P3,P4,P5,P6,P7,P8,P9}={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}(二)程序的顺序执行程序在执行时,把一个程序分成若干个程序段,它们必须按照某种先后次序顺序执行,也就是前一个操作完成,后面的操作才能执行。前趋图如下顺序执行前趋图说明:I:输入操作C:计算操作P:打印操作;在进行计算时,总是先输入用户的程序和数据,然后进行计算,最后将结果打印出来。语句的顺序执行:语句顺序执行说明:S1,S2,S3这三条语句顺序执行。这个我们经常见到。程序顺序执行的特征:顺序性:前一操作完成,后一操作才能进行。封闭性:程序在封闭的环境下运行,即程序运行时独占全部系统资源。可再现性:只要程序执行时的环境相同,程序每次运行结果相同。(三)程序并发执行概念:程序的并发执行:一组在逻辑上互相独立的程序或程序段在执行过程中,其执行时间在客观上相互重叠。现在来理解这个概念:从两点来理解。首先,程序段在逻辑上是没有关联的。例如一个是A程序的打印程序段,一个是B程序的计算程序段。其次,这几个不关联的程序段在执行时间上是重叠的。也就是一个程序段的执行尚未结束,另一个程序段的执行已经开始的执行方式。例如A程序的打印程序段尚未执行完,B程序的计算程序段已经开始执行。★注意:并发和并行的区别:我们来仔细理解一下我们知道并发是宏观上同时,微观上分时。程序的并行执行是指一组程序按独立的、异步的速度执行。是多道程序在同一时刻执行。一般要多硬件支持实现,并行执行不等于时间上的重叠。看课本的例子讲一下,如下图说明:这里我们可以看到,第三个程序的输入I3和第二个程序的计算C2和第一个程序的打印P1,正在并发执行。并发执行的特征:1、间断性:是指程序在执行中一般是“执行—暂停执行—执行”,间断执行的。间断性产生的原因是,程序执行时的相互制约,这种制约是由于程序并发执行而产生的,因为程序在并发执行中可能会对共享资源或为同一项任务的执行而产生制约。是有点太抽象了那么看课本的例子。就明白了,程序A将使用打印机,可是它却被程序B占用。那么程序A就必须等待这个就是典型的因为共享资源而造成的间断。2、失去封闭性:封闭性是指程序运行时独占资源,只有本程序能改变它。但是在并发执行时,各程序都可共享资源,因此失去封闭性。3、不可再现性:程序并发执行时,失去可再现性。例如当两个程序共享一个变量时,可能造成不可再现性。程序的并发执行破坏了程序的可再现性。见课本例子。4、通信性:对于相互合作的程序,为了更有效地协调运行,相互之间需要进行通信。5、独立性:并发程序在运行过程中,既然是作为一个独立的运行实体,它也必然具有作为一个单位去获得资源的独立性。程序并发执行条件(Bernstein条件)程序并发执行时的不可再现性是不允许的,因此必须采取措施保证其再现性。读集:R(Pi)={a1,a2,...,am},为程序Pi在执行期间所需参考的所有变量的集合写集:W(Pi)={b1,b2,...,bn},为程序Pi在执行期间所要改变的所有变量的集合两个程序是否能并发执行,可根据Bernstein条件来判断,该条件是:R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}满足伯恩斯坦条件则能并发执行。例如:四条语句: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条件;S1和S3不可并发执行,因为R(S3)∩W(S1)={a};S2和S3不可并发执行,因为R(S3)∩W(S2)={b};S3和S4不可并发执行,因为R(S4)∩W(S3)={c}。二、进程的描述(一)概念的引入并发执行的出现后,我们要怎样描述多个作业、多个任务这样的并发活动在计算机系统内部的表现和情况呢?这样就引入的进程。(二)进程的定义和特征1、进程的定义进程定义:可并发执行的程序在一个数据集合上的运行过程。怎么理解这个概念?首先进程是一个运行过程,这样看来它是一个动态的。其次它必须具备是的物质条件是一个程序段,一个数据集合,还有后面要讲到的进程控制块。现在我们知道,进程的物质实体由三部分构成:程序段,数据段,进程控制块。再合起来理解进程的定义,简单说,进程就是程序实体的运行过程。它是系统进行资源分配和调度的一个独立单位。2、进程特征进程有5个基本特征1)动态性:进程的实质是程序的一次执行过程,因此,动态特征是进程最基本的特征。进程有一定的生命期,由创建而产生,由调度而执行,因得不到资源而暂停执行,由撤销而消亡。2)并发性:从上面可知,引入进程的目的就是为了描述程序的并发执行,其实是程序的进程的并发执行。那么我们可知,没有为之建立进程的程序是不能并发执行的,仅当为之建立一个进程后才能参加并发执行。3)独立性:进程是一个能独立运行的基本单位,同时也是系统分配资源和调度的独立单位。4)异步性:由于进程间的相互制约,使进程具有执行的间断性,即进程按各自独立的、不可预知的速度向前推进。5)结构特征:为了控制和管理进程,为每个进程设立一个进程控制块PCB。从结构上看,进程实体由程序段,数据段和进程控制块三部分组成,也叫“进程映象”。3、进程和程序区别:反复强调理解,别嫌罗嗦,每次都有新发现(1)进程是一个动态的概念。程序是一个静态的概念。(2)进程有并发性,而程序没有。这两个区别都和进程是一个动态的概念,而程序是一个静态的概念要联系起来。当程序运行,被调入内存,这时我们说进程才有意义。那么进程是程序在内存中运行的实例,是一次动态执行,在内存中多个进程,我们就可讨论其的并发性。而程序是一个静态的概念,并不是正在运行的实例而是个很宽泛的。自然我们也不讨论它的并发执行。因为它本身就是静态而不执行。(3)进程是计算机资源分配的基本单位。因为只有动态执行的东西,计算机才分配给它处理机,存储器等各种资源。如果不执行,是不会分配的。(4)不同的进程可以包含同一程序。只要该程序所对应的数据集不同。即进程和程序不是一一对应,也就是一个进程可顺序执行多个程序,一个程序可由多个进程共用作业:是用户向计算机提交任务的任务实体。(1)作业是用户向计算机提交的任务实体。在用户向计算机提交作业完成后,系统讲它放入外存中的作业等待队列等待执行。进程则是完成用户任务的执行实体。是向系统申请分配资源的基本单位。(2)一个作业由多个进程组成,必须至少由一个进程组成,反过来不是。(3)作业概念主要用于批处理系统中。(三)进程的状态及转换1、最基本的三个状态是:就绪,执行,阻塞状态。就绪状态:当进程已分配到除CPU以外的所有必要资源后,只要再能获得处理机,便可执行。此时进程是就绪状态。执行状态:进程已获得处理机,正在执行。阻塞状态:进程因发生某事件(如请求I/O,申请缓冲空间等)而暂停执行时的状态,也就是进程的执行受到阻塞。此时为阻塞状态,也叫做等待状态。进程的三种基本状态演变图如下:这个图还行,三个基本状态转换图转换图说明:进程已分配到除CPU以外的所有必要资源时,它便处于就绪状态,一旦获得CPU,便立即执行。已获得CPU的进程进入执行状态。正在执行的进程,由于发生某个事件而暂时无法执行时,便放弃处理机而进入阻塞状态。由于执行的进程变为阻塞状态后,调度程序立即把处理机分配给另一个就绪进程;因此,阻塞进程的事件消失后,进程不会立即恢复到执行状态,而转变为就绪状态,重新等待处理机。2、挂起状态1)什么是挂起状态:使正在执行的进程暂停执行;使处于就绪态的进程暂不接受调度的这种静止状态成为挂起状态。2)引入挂起状态的原因:四个原因,同学们看一下课本。3)引入挂起态后的进程状态转换:了解一下。来看下面的图,静止就是挂起具有挂起操作的进程状态演变图。知道就行(四)进程控制块PCBprocesscontrolblock1、为什么引入进程控制块?为了描述进程,即系统中需要有描述进程存在和能够反映其变化的物理实体,也就是进程的静态描述。进程的静态描述有3部分组成:PCB,程序段,与程序段相关的数据段。为了描述进程而引入PCB.2、什么是进程控制块?是进程实体的一部分,是描述和控制、管理进程的记录型数据结构,是进程存在的唯一标志。通过这个定义,我们理解PCB就是一个数据结构,作用是描述,控制和管理进程。3、PCB是感知进程存在的唯一标志在创建一个进程时,应首先创建其PCB,然后才能根据PCB中信息对进程实施有效的管理和控制。当一个进程完成其功能时之后,系统则释放PCB,进程也随之消亡。4、进程控制块的组成一般来说,根据操作系统的要求不同,进程的PCB所含的内容也会不同。但一下基本内容是必需的:1)进程描述信息:进程名或进程标识符:每个进程都有唯一的进程名或进程标识号。在识别一个进程时,进程名或进程标识号代表该进程。进程与PCB是一一对应的用户名或用户标识号:每个进程都隶属于某个用户,用户名或用户标识号有利于资源共享与保护。2)进程调度信息:进程当前状态:说明进程当前处于何种状态。进程在活动期间可分为就绪态、执行态和等待状态。进程优先级(priority):进程优先级是选取进程占有处理机的重要依据。与进程优先级有关的PCB表项还有:占有CPU时间,进程优先级偏移,占据内存时间等。3)进程控制信息:程序与数据地址:该进程的程序和数据所在位置信息。进程通信机制:用于实现进程间的通信所需的数据结构。资源清单:列出进程拥有的资源的记录。连接字:给出本进程所在队列中的下一个进程的PCB首址。4)处理机状态(CPU现场保护结构):主要是处理机各种寄存器值(通用、程序计数器PC、状态字PSW,地址包括栈指针)。作用:处理机运行时,信息放在寄存器中,当处理机被中断时,所有这些信息都必须保存在被中断进程的PCB中,以便将来该进程重新执行时,能从断点处继续执行。注意:有些课本的分类并不一样。5、进程控制块的组织方式在系统中,由于进程的状态各种各样,有的进程在执行态,有的在阻塞,有的在就绪态。进程与PCB是一一对应,因此系统中,通常有几十甚至上百个PCB。为了对这些PCB进行有效管理,需要将它们组织起来。常用的组织方式有2种:1)链接方式链接方式组织PCB图说明:链接组织方式是把处于同一状态的进程组织在一起,形成就绪队列、阻塞队列、空闲队列等。在这些不同状态的队列中,再按一定的规则进行排列。如就绪队列中按进程优先级的大小排列,2)索引方式索引方式组织PCB图说明:同一状态的进程归入一个index表(由index指向PCB),多个状态对应多个不同的index表,各状态的进程形成不同的索引表:就绪索引表、阻塞索引表