《2 进程管理》由会员分享,可在线阅读,更多相关《2 进程管理(176页珍藏版)》请在金锄头文库上搜索。
1、第二章 进程管理,重点和难点:前趋图和程序执行进程的定义和特征进程的基本状态及转换进程的同步与通信线程的概念,前趋图(Procedence Graph):一个有向无循环图,图中的每个结点可用于表示一条语句,一个程序段或进程;结点间的有向边则表示在两结点之间存在的偏序或前趋关系“ ”,2.1 进程的基本概念,关于前趋图的几个概念:1、直接前趋2、直接后继3、初始结点4、终止结点5、结点的重量:该结点所含的程序量或结点的执行时间,1. (pi,pj)2.如果(pi,pj) 可写成pi pj ,称pi是pj 的前驱,而pj是pi的直接后继。,P1,P2,P3,P4,P5,P6,P8,九个结点的前驱图
2、,P7,P9,S1 S2, S2 S3 , S3 S2 , 显然这种前驱关系是不可能满足的,S3的执行要依赖于S2的执行结果,S2的执行结果又要依赖于S3的执行结果,这种程序是不可能执行下去的。 注意:前趋图中不存在循环。,一个较大的程序通常都是由若干个程序段组成。在程序执行时,必须按照某种先后次序逐个执行,仅当前一操作执行完后,才能执行后继操作。 例如:在进行计算时,总是先输入用户的程序和数据,然后才能计算,计算完成后再将结果打印出来。,2.1.2 程序顺序执行及其特征,一、程序顺序执行,程序顺序执行时的前驱图,IiCi ,CiPi ,PiIi+1,对于一个程序段中的多条语句来说,也有一个执
3、行顺序的问题。如果对于下述三条语句的程序段:S1: a:xyS2: b:a5S3: C:b1 (其中S2必须在a被赋值以后才能执行;同样S3也只能在b被赋值 以后才能执行),S1 S2, S2S3,2、程序顺序执行时的特征,(1) 顺序性处理机的操作,严格按照程序所规定的顺序执行,即只有前一操作结束后,才能执行后继操作。(2) 封闭性(失去交换性)程序是在封闭的环境下运行的。即程序在运行时,它独占全机资源,因而机内各资源的状态(除初始状态外),只有程序才能改变它。程序一旦开始运行,其执行结果不受外界因素的影响。(3) 可再现性只要程序执行时的环境和初始条件都相同,不论它是从头到尾的不停顿的执行
4、,还是“走走停停”地执行,都将获得相同的结果。,2.1.3 程序的并发执行,程序的并发执行,一组逻辑上相互独立的程序或程序段在执行过程中,其执行时间在客观上相互重叠,即在某一段时间间隔内,一个程序段的执行,尚未结束,另一个程序段的执行已经开始的这种执行方式。,在上图中存在下述的前趋关系:,Ii1和Ci及Pi1是可以并发执行的。,Ii Ci ,Ii Ii1,Ci Pi,Ci Ci1,Pi Pi1,例:下述四条语句的程序段画出前驱图 S1: a:x+2 S2: b:y4 S3: c:ab S4: d:c6,程序并发执行时的特征,间断性、失去封闭性、不可再现性间断性程序在并发执行时,由于它们共享资源
5、或为完成某一项任务而合作,致使在并发程序之间存在相互制约的关系。(I、C、P是三个相互合作的程序,当计算程序完成Ci1的计算后,如果输入程序I尚未完成对Ii的处理,则计算程序无法进行Ci处理,致使计算程序在停运行。)失去封闭性程序在并发执行时,是多个程序共享系统中的各种资源,因而这些资源的状态将由多个程序来改变,致使程序的运行失去了封闭性。,不可再现性,程序在并发执行时,由于失去了封闭性,也导致失去了可再现性。 例如:有两个循环程序A和B,它们共享一个变量N。程序A每执行一次时都要做N:N1操作;程序B每执行一次时,都要做print(N)操作,然后再将N置成“0”,程序A和B以不同的速度运行。
6、(假定某时刻变量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,2.1.4 程序并发执行的条件,程序并发执行可以提高资源利用率和系统吞吐量,但却可能使并发进程失去可再现性。必须采取措施!,如果并发执行的各程序段中语句或指令满足Bernstein提出的条件,则认为并发执行不会对执行结果的封闭性和可再现性产生影响。,1966年,Bernstein提出了相邻语句S1,S2可以并发执行的
7、条件。,将程序中任一语句Si (或一段程序)划分为两个变量的集合R(Si)和W(Si)其中R(Si)a1,a2,am是语句Si (程序)在执行其间所需参考的所有变量的集合W(Si)b1,b2,bn是语句Si (程序)在执行其间所要改变的所有变量的集合如果对于语句S1和S2,有 R(S1)W(S2) W(S1)R(S2) W(S1) W(S2)=同时成立即:R(S1)W(S2) W(S1)R(S2)W(S1) W(S2)则语句S1和S2是可以并发执行的。,例:若有两条语句Ciab和Wic1,判断它们是否可以并发执行?,解:它们的“读集”和“写集”分别为 R(C:ab)a,b;R(W:c1)c W
8、(C:ab)c ;W(Wi:c1)w,R(C:ab)W(Wi:c1)= R(W:c1)W(C:ab)=c所以:两条语句不能并发执行。,有的同学发现,同一语句的“读集”和“写集”的交集是空集。R(C:ab)W(C:ab)W(W:c1)W(W:c1)=,其实,同一语句的“读集”和“写集”也可能相同(交集不为空)例如:计数语句: xx1读集和写集相同R(xx1)W(xx1)x,课堂练习,例:用Bernstein条件判断以下四条语句是否两两可以并发执行。S1: a:xyS2: b:z1S3: C:abS4: w:c1,在操作系统中为什么要引进进程这个概念?,什么是程序?程序是具有特定功能的一组指令(或
9、一组语句)的集合,它指出了处理器执行操作的步骤。程序本身完全是静态的概念,为了 能正确反映程序执行时的活动规律和状态变化,引入了一个新的概念“进程”。它可以从变化的角度动态地研究程序的执行。,例:编译程序对多个源程序进行编译,一、进程的特征1动态性 动态性是进程最基本的特征。进程是有一定的生命周期的;而程序只是一组有序指令的集合,本身并无运动的含义,是静态的。2. 并发性 这是指多个进程实体,同存于内存中,能在一段时间内同时运行。并发性是进程的重要特征,同时也成为OS的重要特征。引入进程的目的也是为了使该进程的程序能和其它进程的程序并发执行。,2.1.4 进程的特征与状态,3.独立性 进程实体
10、是一个能独立运行的基本单位,同时也是系统中独立获得资源和独立调度的基本单位。没有建立进程的程序,不能作为一个独立的单位参加运行。4.异步性 进程按各自独立的、不可预知的速度向前推进。导致程序的不可再现性5.结构特性 从结构上看,进程是由程序段、数据段及进程控制块三部分组成。,二、进程的定义,进程有许多各式各样的定义(1)进程是程序的一次执行(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动(3)进程是程序在一个数据集合上的运行过程,是系统进行资源分配和调度的一个独立单位,进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。,1就绪状态(Ready) 当进程已经分配到除C
11、PU以外的所有必要的资源后,只要能再获得处理机,就可以立即执行。这时的进程的状态称为就绪状态。2执行状态(Running)(运行状态) 指进程已获得处理机,其程序正在执行。在单处理机系统中,只能有一个进程处于执行状态。(在多处理机中,可能有多个进程处于执行状态),三、进程的三种基本状态,3阻塞状态(Block)(等待状态) 进程因为发生某个事件而暂停执行时的状态(如请求I/O、申请缓冲空间等),也就是说,进程受到阻塞,所以称这种暂停状态为阻塞状态,有时也称“等待”状态或“睡眠”状态。进程状态间的变迁就绪执行:调度执行等待:等待某个事件发生而睡眠等待就绪:因等待的事件发生而唤醒执行就绪:时间片用
12、完,就绪,执行,阻塞,事件发生,进程调度,等待某事件,时间片完,四、挂起状态,1、引入挂起状态的原因 1)终端用户的请求 当终端用户在自己的程序运行期间,发现有可疑问题时,往往希望暂时使自己的进程静止下来。也就是说,如果进程处于执行状态,则暂停执行;如果进程处于就绪状态,则暂时不接受调度,以便研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。,2) 父进程请求 父进程常常希望考察和修改子进程,或者当要协调各子进程间的活动时,要挂起自己的子进程。3)负荷调节的需要 当实时系统中的工作负荷较重,可能影响到对实时任务的控制时,可由系统把一些不重要或不紧迫的进程挂起,以保证系统仍然能正常
13、运行。 4)操作系统的需要 操作系统有时需要挂起某些进程,检查运行中资源的使用情况及进行记帐,以便改善系统的运行性能。,2、进程状态的转换 在引入挂起状态后,又将增加从挂起状态(又称静止状态)到非挂起状态(又称活动状态)的转换。或者相反,可以有以下几种情况: 1)活动就绪 静止就绪 当进程处于未被挂起的就绪状态时,称此为活动就绪状态,表示为Readya。当用挂起原语Suspend将该进程挂起后,该进程转变为静止就绪状态。表示为Readys(处在Readys状态的进程不再被调度执行),2)活动阻塞 静止阻塞 当进程处于未被挂起的阻塞状态时,称为它处在活动阻塞状态(表示为Blockeda)。当Su
14、spend原语将它挂起后,进程便转变为静止阻塞状态(表示为Blockeds)。处于该状态的进程,在其所期待的事件出现以后,他将从静止阻塞变为静止就绪。3)静止就绪 活动就绪 处于Readys状态的进程,若用激活原语Active激活后,该进程将转变为Readya状态。4)静止阻塞 活动阻塞 处于Blockeds状态的进程,若用激活原语Active激活后,进程将转变为Blockeda状态。,执行,活动就绪,活动阻塞,静止就绪,静止阻塞,请求I/O,释放,具有挂起状态的进程状态图,五、创建状态和终止状态 1. 创建状态 是一个进程刚刚建立,拥有了自己的CPU,但进程自身还未进入主存,不能被调度运行(
15、即还没有将它送入就绪队列时的状态) 2.终止状态 当一个进程已经正常结束或异常结束,OS已经将它从就绪队列中移出,但还没有将它撤消时的状态。,建立进程 第一步为新登录的用户程序创建进程,并为它分配资源,此时进程处于创建状态。 第二步把新创建的进程送入就绪队列,一旦进程进入就绪队列,它便由创建状态转变为就绪状态。撤销进程 第一步将进程从就绪队列中移出,使它成为不可再运行的进程,这个进程就处于终止状态。 第二步在其它进程收集了该终止状态进程的有关信息之后撤消该进程。,对于一个进程来说“创建状态”和“终止状态”只有一次,五种状态间的转换如下: 1创建状态 就绪状态 当就绪队列能够接纳新的进程时,OS便把处于新状态的进程移入就绪队列,此时进程由新状态转变为就绪状态。2就绪状态 执行状态 处于就绪状态的进程,当进程调度程序为它分配了处理机后,该进程便由就绪状态变为执行状态,正在执行的进程也称为当前进程。,