2 进程管理.ppt

第二章 进程管理 重点和难点： 前趋图和程序执行 进程的定义和特征 进程的基本状态及转换 进程的同步与通信 线程的概念 前趋图（Procedence Graph）：一个有向无循环图，图中的每个结点可用于表示一条语句，一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前趋关系“ ” S1 S2， S2 S3 ， S3 S2 ， 显然这种前驱关系是不可能满足的，S3的执行要依赖于S2的执行结果，S2的执行结果又要依赖于S3的执行结果，这种程序是不可能执行下去的。 注意：前趋图中不存在循环。 2.1.2 程序顺序执行及其特征 一个较大的程序通常都是由若干个程序段组成。在程序执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。 例如：在进行计算时，总是先输入用户的程序和数据，然后才能计算，计算完成后再将结果打印出来。 2、??程序顺序执行时的特征 （1）? 顺序性 处理机的操作，严格按照程序所规定的顺序执行，即只有前一操作结束后，才能执行后继操作。 （2） 封闭性（失去交换性） 程序是在封闭的环境下运行的。即程序在运行时，它独占全机资源，因而机内各资源的状态（除初始状态外），只有程序才能改变它。程序一旦开始运行，其执行结果不受外界因素的影响。 （3） 可再现性 只要程序执行时的环境和初始条件都相同，不论它是从头到尾的不停顿的执行，还是“走走停停”地执行，都将获得相同的结果。 2.1.3 程序的并发执行 例：下述四条语句的程序段画出前驱图 S1： a：＝x+2 S2： b：＝y＋4 S3： c：＝a＋b S4： d：＝c＋6 程序并发执行时的特征 间断性、失去封闭性、不可再现性 间断性 程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。(I、C、P是三个相互合作的程序，当计算程序完成Ci－1的计算后，如果输入程序I尚未完成对Ii的处理，则计算程序无法进行Ci处理，致使计算程序在停运行。) 失去封闭性 程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。 不可再现性 2.1.4 程序并发执行的条件 程序并发执行可以提高资源利用率和系统吞吐量,但却可能使并发进程失去可再现性。 必须采取措施！ 将程序中任一语句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是可以并发执行的。 例：若有两条语句Ci＝a－b和Wi＝c＋1，判断它们是否可以并发执行？ 有的同学发现，同一语句的“读集”和“写集”的交集是空集。 R（C：＝a－b）∩W（C：＝a－b）＝{Φ} W（W：＝c＋1）∩W（W：＝c＋1）={Φ} 课堂练习 例：用Bernstein条件判断以下四条语句是否两两可以并发执行。 S1： a：＝x＋y S2： b：＝z＋1 S3： C：＝a－b S4： w：＝c＋1 什么是程序？ 程序是具有特定功能的一组指令（或一组语句）的 集合，它指出了处理器执行操作的步骤。 程序本身完全是静态的概念 2.1.4 进程的特征与状态 一、进程的特征 1．动态性 动态性是进程最基本的特征。进程是有一定的生命周期的；而程序只是一组有序指令的集合，本身并无运动的含义，是静态的。 2. 并发性 这是指多个进程实体，同存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也是为了使该进程的程序能和其它进程的程序并发执行。 3.独立性 进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。没有建立进程的程序，不能作为一个独立的单位参加运行。 4.异步性 进程按各自独立的、不可预知的速度向前推进。导致程序的不可再现性 5.结构特性 从结构上看，进程是由程序段、数据段及进程控制块三部分组成。 二、进程的定义 进程有许多各式各样的定义 （1）进程是程序的一次执行 （2）进程是一个程序