[理学]第二章 进程管理1

《[理学]第二章 进程管理1》由会员分享，可在线阅读，更多相关《[理学]第二章 进程管理1（82页珍藏版）》请在金锄头文库上搜索。

1、2.1 进程概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 进程通信 2.6 线程,第二章 进程管理,重点和难点： 进程的定义和特征 进程的同步和互斥 用信号量机制解决进程同步、互斥问题,2.1 进程的概念,2.1.1 程序的顺序执行,1.程序的顺序执行,在计算机系统中只有一个程序运行时，这个程序独占系统中所有资源，其执行不受外界影响。通常一个程序可分成若干个程序段，它们必须按照某种先后次序执行，仅当前一操作执行后，才能执行后继操作。 例如：进行计算。I:输入操作 C:计算操作 P:打印操作。在进行计算时，总是先输入用户的程序和数据，然后进行计算，最后将结果打印出

2、来。,程序的顺序执行,2. 语句的顺序执行,对于一个程序段中的多条语句来说，也有一个执行顺序的问题。如果对于下述三条语句的程序段： S1： a:xy S2： b:a5 S3： c:b1 (其中S2必须在a被赋值以后才能执行；同样S3也只能在b被赋值以后才能执行),3. 程序顺序执行时的特征,（1） 顺序性 处理机的操作，严格按照程序所规定的顺序执行，即每一操作必须在上一操作结束之后开始。 （2） 封闭性 封闭环境下运行，程序独占全机资源 只有当前运行程序才能改变资源状态 程序执行结果不受外界因素的影响 （3） 可再现性 只要程序执行时的环境和初始条件都相同，不论它是从头到尾的不停顿的执行，还是

3、“走走停停”地执行，都将获得相同的结果。,程序顺序执行时的特性，将为程序员检测和校正程序的错误，带来极大的方便。,. 多道程序系统中，程序执行环境的变化,计算机能够同时处理多个具有独立功能的程序（如批 处理系统，分时系统、实时系统、网络与分布式系统）。 这样的执行环境具有三个特点： 独立性 ：逻辑上独立； 随机性 ：程序和数据输入与执行开始时间都是随机的 资源共享: 硬件资源：CPU、输入输出设备，存储器 软件资源：各种例行程序、各种共享的数据,2.1.2 前趋图,为了描述一个程序的各部分(程序段或语句)间的依赖关系，或者是一个大的计算的各个子任务间的因果关系，我们常常采用前趋图方式。,图2-

4、1(a) 九个结点的前趋图,前趋图（Procedence Graph）：是一个有向无循环图，图中的每个结点可用于表示一条语句，一个程序段或进程；结点间的有向边则表示在两结点之间存在的前趋关系 “ ” 。 如果(pi，pj) 可写成pi pj ，称pi是pj 的前趋，而pj是pi的直接后继。 关于前趋图的几个概念： 1 直接前趋 2 直接后继 3 初始结点 4 终止结点 5 结点的重量：该结点所含的程序量或结点的执行时间来计算。,存在下面的前趋关系： P1 P2，P1 P3；P1 P4；P2 P5；P3 P5；P5 P7; P4 P6，P6 P7 或表示为： PP1,P2,P3,P4,P5,P6

5、,P7 =(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,p5),(P4,P6),(P5,P7),(P6,P7),图2-1 (b) 七个结点的前趋图,!注意：前趋图中不存在循环。 S2 S3 ， S3 S2 显然这种前趋关系是不可能满足的，S3的执行要依赖于S2的执行结果，S2的执行结果又要依赖于S3的执行结果，这种程序是不可能执行下去的。,2.1.3 程序的并发执行,1.并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。 2.程序的并发执行 一组逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相

6、互重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的执行方式。,图2-2 程序并发执行时的前趋图,在对一批程序进行处理时，可以并发执行。 例如，输入、计算、打印三个程序对一批作业进行处理时，存在以下的前趋关系： Ii Ci ， Ii Ii1 ， Ci Pi ， Ci Ci+1， Pi Pi +1 对一个作业的输入计算和打印三个操作，必须顺序执行，但并不存在Pi Ii1。 Ii1和Ci及Pi1是可以并发执行的。,例：下述四条语句的程序段画出前趋图 S1： a：x+2 S2： b：y4 S3： c：ab S4： d：c6,3.程序并发执行的特征：,多道程序系统的程序执行环境变化所引起的

7、多道程序的并发执行 由于资源有限，多道程序的并发执行总是伴随着资源的共享与竞争，制约了各道程序的执行速度。 在某道程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码 例如：read（a）； read（b）； 既可以同时执行，也可以颠倒次序执行，同时执行不会改变顺序程序所具有的逻辑性质，可采用并发执行来充分利用资源。,间断性、失去封闭性、不可再现性 间断性 程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。( I、C、P是三个相互合作的程序，当计算程序完成Ci1的计算后，如果输入程序I尚未完成对Ii的处理，则计算程序无法进行Ci处理，致使计算程

8、序暂停运行。) 失去封闭性 程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。,不可再现性 程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。 例如：有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时都要做N:N+1操作；程序B每执行一次时，都要做print（N）操作，然后再将N置成“0”，程序A和B以不同的速度运行。（假定某时刻变量N的值为n）,程序并发执行不可再现性举例分析,共享初值为n的变量N的两程序段A、B,A: N:=N+1,B: Print(N); N:=0,（1）N:N1在print（N）和N:0

9、之前，此时得到的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,4 .程序并发执行的条件,程序并发执行过程可以描述为： S0 Cobegin P1；P2；Pn Coend Sn 1966年，Bernstein提出了相邻语句S1S2可以并发执行的条件。 如果并发执行的各程序段中语句或指令满足Bernstein的三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生影响。,将程序中任一语句Si划分为两个变量的集合 R（Si）a1,a2,am是语句Si在

10、执行其间必须对其进行读的变量，称为读集； 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是可以并发执行的。 ？操作系统中许多任务不满足Bernstein条件，它们不能并发执行吗？怎么办？,例：若有两条语句Ciab和Wic1，判断它们是否可以并发执行？ 解：它们的“读集”和“写集”分别为 R（C：ab）a，b R（W：c1）c W（C：ab）c W（W：c1）w R（C：ab

11、）W（Wi：c1）= R（W：c1）W（C：ab）=c,所以：两条语句不能并发执行。,进程的引入,并发、共享及多道程序环境 基于程序的概念已不能完整、有效地描述并发程序在内存中的运行状态 必须建立并发程序的新的描述和控制机制 基于程序段、数据段和进程控制块而引入进程的概念以对应程序的运行过程 进程控制块存放了进程标识符、进程运行的当前状态、程序和数据的地址以及关于该程序运行时的CPU环境信息,2.1.4 进程的特征与状态,1) 结构特征：程序段、相关的数据段、PCB构成了进程实体。 2) 动态性 ：进程是进程实体的一次执行过程。 3) 并发性：多个进程实体，同存于内存中，能在一段时间内同时运行

12、。 4) 独立性：独立运行和资源调度的基本单位。 5) 异步性 ：各自独立的、以不可预知的速度向前推进。,1.进程的特征和定义：,进程有许多各式各样的定义，其中较典型的进程定义是： （1）进程是程序的一次执行。 （2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 （3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。”,！比较进程和程序的区别： 答：（1）进程是一个动态的概念，进程的实质是程序的一次执行过程，动态性是进程的

13、基本特征，同时进程是有一定的生命期的；而程序只是一组有序指令的集合，本身并无运动的含义，是静态的。 （2） 并发性。并发性是进程的重要特征，引入进程的目的正是为了使其程序和其它程序并发执行；而程序(没有建立进程)是不能并发执行的。 （3） 独立性。是指进程是一个能独立运行、独立分配资源和独立调度的基本单位；凡未建立进程的程序，都不能作为一个独立的单位参加运行。 （4）不同的进程可以包含同一个程序，同一个程序在执行中也可以产生多个进程。,实例：,一位有一手好厨艺的计算机科学家正在为他的儿子烘制生日蛋糕。 计算机科学家-处理机(CPU)； 做蛋糕的食谱-程序（即用适当形式描述的算法）； 做蛋糕的原

14、料（如面粉，鸡蛋，糖）-输入数据； 进程：厨师阅读食谱，取来各种原料以及烘制蛋糕等一系列动作的总和。 现假设科学家的儿子跑进来，说被蜜蜂蛰了； 科学家就记录下他照着食谱做到哪儿了-保存进程当前状态； 然后拿出一本急救手册（医疗救治进程的程序），按照其中的指示处理蛰 伤-CPU进行进程切换（做蛋糕实施医疗救治）； 蛰伤处理完毕后，科学家又回来做蛋糕，从他离开时的那一步继续做下去。 关键思想：一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。单个处理机可以被若干个进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。,答：在单道程序设计环境下，CPU被一道程

15、序独占，CPU严格按该程序的指令顺序来执行，单道程序具有顺序性，封闭性和可重现性。单道程序有许多局限性，于是出现了多道程序，在多道程序环境中，有若干个程序同时运行，其具有许多新的特征，如并发性，动态性以及相互制约性等，这时程序的概念已经不能描述上述这些特征，并发程序的特征必须用新的概念来描述，所以引进了进程的概念。,在操作系统中为什么要引进进程这个概念? 它会产生什么影响?,2.进程的三种基本状态 1就绪状态（Ready） 当进程已经分配到除CPU以外的所有必要的资源后，只要能再获得处理机，就可以立即执行。这时进程的状态称为就绪状态。 2执行状态（Running）（运行状态） 指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。（在多处理机中，可能有多个进程处于执行状态） 3阻塞状态（Block）（等待状态） 进程因为发生某个事件而暂停执行时的状态（如：请求I/O、申请缓冲空间等），也就是说，进程受到阻塞，所以称这种暂停状态为阻塞状态，有时也称“等待”状态或“睡眠”状态。,进程状态间的转换 就绪执行：调度 执行阻塞：等待某个事件发生而睡眠 阻塞就绪：因等待的事件发生而唤醒 执行就绪：时间片用完,引入挂起状态的原因 终端用户的请求。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。,