操作系统第2章 进程的描述与控制new课件

《操作系统第2章 进程的描述与控制new课件》由会员分享，可在线阅读，更多相关《操作系统第2章 进程的描述与控制new课件（133页珍藏版）》请在金锄头文库上搜索。

1、内容 前趋图和程序执行 进程的描述 进程控制 线程的基本概念 举例,第二章进程的描述与控制,目的及要求 理解前趋图的作用，领会程序顺序执行和并发执行的特征； 理解和掌握进程的概念和特征、进程的基本状态及转换 了解进程控制块的作用、包含信息和组织方式； 了解操作系统内核的主要功能，领会引起进程创建、终止、阻塞、唤醒、挂起、激活的过程和各类进程控制原语的执行过程； 了解线程的基本概念，理解线程与进程的联系与区别。,第二章进程的描述与控制,重点 程序并发执行的特征； 进程的概念和特征； 进程的基本状态及其转换； 线程与进程的比较。 难点 程序的顺序执行和并发执行比较； 进程和程序的联系与区别； 线程

2、与进程的比较。,第二章进程的描述与控制,2.1.1 前趋图的定义 2.1.2 程序顺序执行 2.1.3 程序并发执行 2.1.4 程序并发执行的条件,2.1前趋图和程序执行,前趋图（Procedure Graph）是一个有向无循环图DAG (Directed Acyclic Graph)； 图中的每个结点可用于表示一条语句、一个程序段或进程； 结点间的有向边则表示在两结点之间存在的偏序(Partial Order)或前趋关系(Procedure Relation)“”， =（Pi，Pj）|Pi must complete before Pj may start 如果（Pi，Pj），可写成 Pi

3、Pj；，称Pi是Pj的前趋，而Pj是Pi的 直接后继。 在前趋图中，没有前趋的结点称为初始结点，没有后继的结点 称为终止结点。此外，每个结点还具有一个重量，它可用该结点所 含的程序量或结点的执行时间来计量。,2.1.1前趋图的定义,P1P2, P1P3，P1P4，P2P5，P3P5，P4P6, P5P7，P6P7 ，或表示为： P = P1, P2, P3, P4, P5, P6, P7 = (P1，P2) ， (P1， P3)， (P1， P4) ， (P2， P5) ， (P3， P5) ，(P4， P6) ， (P5， P7) ， (P6， P7) ,2.1.1前趋图的定义,2.1.2程

4、序顺序执行,程序顺序执行 一个较大的程序通常由若干个程序段组成。程序在执行 ，必须按照某种先后次序逐个执行，仅当前一个操作执行以后 ，才能执行后继操作。 例如在计算时，总是先输入用户的程序与数据，然后才 进行计算，计算结束在将计算结果打印出来。这里我们用节点 （Node）代表各程序段的操作，其中节点I代表输入操作，节 点C代表计算操作，节点I代表打印操作，上述各程序段的执行 ，可用前趋图表示。 S1: a:=x+y; S2: b:=a-5; S3: c:=b+1;,程序顺序执行时的特征 顺序性 处理机的操作，严格按照程序所规定的顺序执行，即只有前一操 作结束后，才能执行后继操作。 封闭性 程序

5、是在封闭的环境下运行的。即程序在运行时，它独占全机资 源，因而机内各资源的状态（除初始状态外），只有本程序才能改变 它。程序一旦开始运行，其执行结果不受外界因素的影响。 可再现任 只要程序执行时的环境和初始条件相同，当程序多次重复执行时 ，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将 获得相同的结果。 程序顺序执行时的特性，将为程序员检测和校正程序的错误，带 来极大的方便。,2.1.2程序顺序执行,2.1.3 程序并发执行,一、程序并发执行 并发环境：在计算机系统支持并行操作时，如采用多道程序设计技术，则内存中多道程序处于并发执行状态。如上述有三个程序段的作业类，虽然每个作业有前

6、趋关系的各程序段不能在系统CPU和输入输出各部件并行执行，但一个作业没有前趋关系的程序段或不同作业的程序段可以分别在CPU和各输入输出部件上并行执行。,2.1.3 程序并发执行,程序并发执行 （定义） 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。,2.1.3 程序并发执行,程序并发执行 该例的前趋关系：IiCi，IiIi+1，Ci-Pi，Ci-Ci+1, Pi-Pi+1，而Ii+1和Ci及Pi-1是重叠的，即可以并 发执行。,2.1.3 程序并发执行,对于具有下列四条语句

7、的程序段： S1: a:=x+2; S2: b:=y+4; S3: c:=a+b; S4: d:=c+8; 其前趋图如图:,程序并发执行时的特征 程序的并发执行，虽然提高了系统吞吐量，但也产生了 下述一些与顺序执行时不同的新特征： 间断性 程序在并发执行时，由于它们共享资源或为完成同一项任务而相 互合作，致使在并发程序之间形成了相互制约的关系。简言之，相互 制约将导致并发程序具有“执行一暂停执行一执行”这种间断性的活 动规律。 失去封闭性 程序在并发执行时，是多个程序共享系统中的各种资源，因而这 些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。 不可再现性 程序在并发执行时，由于

8、失去了封闭性，其计算结果与并发程序的 执行速度有关，从而导致其失去其可再现性。即程序经过多次执行后， 虽然执行的环境和初始条件都相同，但得到的结果却不同。,2.1.3 程序并发执行,2.1.3 程序并发执行,例：观察者/报告者 观察者： 报告者： begin begin repeat repeat wait a car go through delay a time N=N+1； Print N ； N=0 ； until until end end 初始N=n时不同执行序列： N=N+1； Print N； Print N ； Print N ； N=0 ； N=N+1 ； N=0 ； N=

9、N+1 ； N=0 ； N的结果各不相同: n+1，n+1，0； n，0，1； n，n+1，0；,程序的并发执行，虽然能够有效地提高资源的利用率和 系统的吞吐量，但必须采取某种措施，以使并发程序能保持“ 可再现性”。 R(Pi)=a1,a2,am,用以表示程序Pi在执行期间所需参 考的所有变量的集合，称为“读集”； W(Pi)=b1,b2,bn,用以表示程序Pi在执行期间所需 改变的所有变量的集合，称为“写集”； 若有两条语句c:=a-b和w:=c+1，则它们的“读集”和“ 写集”如下： R(c:=a-b)=a,b，W(c:=a-b)=c, R(w:=c+1)=c， W(w:=c+1)=w,

10、R(c:=a-b)W(c:=a-b)=, R(w:=c+1)W(w:=c+1)=,2.1.4 程序并发执行的条件,Bernstein条件 若两个程序P1和P2满足下列条件，它们便能并发执行，且具可再现性。 R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)= 例如：有四条语句： S1：a:=x+y S2：b:=z+1 S3：c:=a-b S4：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、 S1与S4、 S2与S4可并发执行， S1与S3

11、、 S2与S3、 S3与S4不可并发执行。,2.1.4 程序并发执行的条件,2.2.1 进程的定义与特征 2.2.2 进程状态及其转换 2.2.3 进程的挂起状态 2.2.4 进程控制块PCB,2.2进程的描述,进程的定义 由于程序在并发执行时，各次执行的结果不同，所以用“ 程序”这个概念已无法描述程序的并发执行，所以必须引入新 的概念-进程来描述程序的并发执行。 最早使用进程(process)概念进行操作系统设计的是美国 的麻省理工学院在MULTICS系统和IBM公司的CTSS/360系统上实 现的。只是CTSS/360使用了另一个术语任务(task)，但两者 的实际含义是相同的。 进程是操

12、作系统的最基本、最重要的概念之一，但迄今为止对这一概念还没有一个确切的统一的描述。,2.2.1 进程的定义与特征,进程可定义为：“可并发执行的程序在一个数据集合上的运行过程”。,2.2.1 进程的定义与特征,或者“是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。（未引入线程前） ”,进程的特征 1 动态性 （1）强调：是一个程序的执行过程 （2）有一定生命期：创建 执行 暂停 消亡 （3）在不同状态之间转换 动态性是进程的最基本特征，它是程序执行过程，它是有一定的生命期。它由创建而产生、由调度而执行，因得不到资源而暂仃，并由撤消而死亡。而程序是静态的，

13、它是存放在介质上（外存、软盘、光盘）一组有序指令的集合，无运动的含义。 一个程序-多个进程。,2.2.1 进程的定义与特征,2 并发性：并发性是进程的重要特征，同时也是OS的重要特征。并发性指多个进程实体同存于内存中，能在一段时间内同时运行。而程序是不能并发执行。 3 独立性：从定义看 资源分配 独立调度 进程是一个能独立运行的基本单位，即是一个独立获得资源和独立调度的单位;而程序不作为独立单位参加运行，必须通过建立进程才能运行。 4 异步性：进程按各自独立的不可预知的速度向前推进，即进程按异步方式进行 导致程序执行的不可再现性，因此OS必须采用某种措施来限制各进程推进序列以保证各程序间正常协

14、调运行。 5 结构特征：由定义，进程实体包括 程序段 数据段 进程控制块PCB（PROCESS CONTROL BLOCK） UNIX中称为“进程映象”。 6 进程可以创建其它进程，而程序不能.,2.2.1 进程的定义与特征,进程的三种基本状态 进程在其生命期内，由于系统中各进程之间的相互制约关系及系统的 运行环境的变化，使得进程的状态在不断地发生变化。 执行态（Excuting）：当一个进程在处理机上运行时，则称该进程处于运行状态。进程占有CPU，并在CPU上运行（如不特别强调，大都指单CPU）若CPU空闲，处理机挑选一进程执行。 就绪态（Ready）：一个进程获得了除处理机外的一切所需资源

15、，一旦得到处理机即可运行，则称此进程处于就绪状态。当调度给其CPU时，立即可以运行。 阻塞态（Blocked）又称睡眠状态、等待状态、封锁态、冻结态。一个进程正在等待某一事件发生（例如请求IO或等待IO完成或申请缓冲空间等）而暂时仃止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。（即使CPU空闲，该进程也不可运行） 例：打印机 阻塞队列,2.2.2 进程的基本状态,具有三种基本状态的进程状态图,2.2.2 进程的基本状态,进程状态的转换,三个基本状态之间可能转换和转换原因如下： 就绪态执行态：当处理机空闲时，进程调度程序必将处理机分配给一个处于就绪态的进程 ，该进程便由就

16、绪态转换为运行态。 执行态阻塞态：处于运行态的进程在运行过程中需要等待某一事件发生后（例如因IO请求等待IO完成后），才能继续运行，则该进程放弃处理机，从运行态转换为阻塞态。 阻塞态就绪态：处于阻塞态的进程，若其等待的事件已经发生，于是进程由阻塞态转换为就绪态。 执行态就绪态：处于执行态的进程在其运行过程中，因分给它的处理机时间片已用完，而不得不让出（被抢占）处理机，或者有优先级高的进程出现，进程由执行态转为就绪态。 而阻塞态运行态和就绪态阻塞态这二种状态转换不可能发生。,系统中各进程状态的分布和管理,处于运行态进程:如系统有一个处理机，则在任何一时刻，最多只有一个进程处于运行态。 处于就绪态进程:一般处于就绪态的进程按照一定的算法（如先来的进程排在前面，或采用优先权高的进程排在前面）排成一个就绪队列。 处于阻塞态进程:处于阻塞态的进程排在阻塞队列中