《进程管理-课件》由会员分享，可在线阅读，更多相关《进程管理-课件（142页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 进程管理进程管理 1 1 进程的基本概念进程的基本概念 2 2 进程控制进程控制 3 3 进程同步进程同步 4 4 经典进程同步问题经典进程同步问题 5 5 管程机制管程机制 6 6 进程通信进程通信 7 7 线程线程 1 进程的基本概念操作系统的特性之一是并发与共享，即在系统(内存)中同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。前前趋趋图图(Precedence Grap
2、h)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中每个结点可用于描述一条语句、一个程序段或进程结点间的有向边则表示在两结点之间存在的偏序或前趋关系“”，=（Pi，Pj）|Pi must complete before Pj may start 如果（Pi，Pj），可写成 PiPj；，称Pi是Pj的直接前趋，而Pj是Pi的直接后继。在前趋图中，没有前趋的结点称为初始结点(Initial Node) ，没有后继的结点称为终止结点(Final Node) 。2.1.1前趋图前趋图S1S2S3 每个结点还可具有一个重量(Weight
3、)，用于表示该结点所含有的程序量或结点的执行时间。 前趋图前趋图 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的有向图图2l示出的前趋图，存在下面的前趋关系：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前趋图前趋图一、概念 一个程
4、序由若干个程序段组成，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一(程序段)执行完后，才能执行后继操作。这种程序执行的方式就称为程序的顺序执行程序的顺序执行。 例如： 2.1.2程序的顺序执行1.顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性 程序一旦开始执行，其执行结果不受外界的影响。3.可再现性 程序执行的结果与初始条件有关，而与执行时间无关。二、程序顺序执行的特点例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,.,n)。这些作业在系统中执行时是对时间的偏序，有些操作必须在其它
5、操作之前执行，这是有序的，但有些操作是可以同时执行的。例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。图中存在下面的前趋关系：IiCi, IiIi 1, CiPi, CiCi1, PiPi1而Ii1和Ci及Pi1是重迭的 ，它们可以并发执行。2.1.3程序的并发执行及其特征并发执行时的前趋图 例如:对于具有下列四条语句的程序段：S1: a:=x+2;S2: b:=y+4;S3: c:=a+b;S4: d:=c+8;其前趋图如右图。 其中S1和S2可以并发执行。2.1.3程序的并发执行及其特征程序并发执行程序并发执行 （定义）
6、（定义） 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。2.1.3程序的并发执行及其特征程序并发执行的描述：程序并发执行的描述： parbegin S1;S2;S3;.;SN parend; Si(i=1,2,3,.,n)表示n个语句（程序段），这n个语句用parbegin和parend括起来表示这n个语句是可以并发执行的。这是Dijkstra提出的。2.1.3程序的并发执行及其特征假设有一个程序由S0Sn+1个语句，其中 S1Sn语句是并发执行的，程序如下： S0; pa
7、rbegin S1;S2;S3;.;SN parend; Sn+1;2.1.3程序的并发执行及其特征程序并发执行时的特征程序并发执行时的特征1、间断性(执行暂停执行)2、失去了程序的封闭性3、不可再现性(失去封闭性引起)2.1.3程序的并发执行及其特征 例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时， 都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。 可能出现以下三种情形： (1) N=N+1在Print(N)和N=0之前，此时得到的N值分别为n+1, n+1, 0。 (2) N=N+1在Print(
8、N)和N=0之后，此时得到的N值分别为n, 0, 1。 (3) N=N+1在Print(N)和N=0之间，此时得到的N值分别为n, n+1, 0。 结论：程序在并发执行时， 由于失去了封闭性，其计算结果与并发程序的执行速度有关，使程序执行失去可再现性。 进程的特征与状态进程的特征与状态在单道程序设计环境下，CPU被一道程序独占，CPU严格按程序的指令顺序来执行，程序具有顺序性、封闭性和可再现性特征。在多道程序设计的环境下，系统中有多个程序同时运行。此时的程序具有间断性、失去了程序的封闭性、不可再现性等特征。程序一旦运行起来，它不但与程序本身有关，而且与它运行时所处的运行环境有关，程序的活动不再
9、是静态的、封闭的，而显现出并发性、动态性以及相互制约的关系。所以用程序的概念已经不能描述上述这些特征，于是引入进程进程的概念。 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫过任务(task)。进程的特征进程的特征（1）结构特征：从结构上看，进程实体是由程序段、相关的数据段和进程控制块(PCB，process control block)三部分组成。（2）动态性：进程的实质是进程实体的一次执行过程，它有着创建、活动、暂停、终止等过程，具有一定的生命期，是动态地产生、变化和消亡的。（3）并发性：多个进程实体同存于内存中，且能在一段时
10、间内同时运行。（4）独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。（5）异步性：各个并发进程按照各自独立的、不可预知的速度向前推进。2.1.4 进程的特征与状态进程的特征与状态行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw)进程是执行中的程序。（Ken Thompson and Dennis Ritchie )教材上给出的进程的定义： 进进程程是进程实体的运行
11、过程，是系统进行资源分配和调度的一个独立单位。进程的定义1、程序是指令的集合，是静态的概念。 进程是程序在处理机上的一次执行过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并发活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。进程与程序的区别与联系进程与程序的区别与联系例子：光盘（CD、VCD）光盘（程序） 放光盘的活动（进程）进程与程序的区别与联系进程与程序的区别与联系进程在系统中的活动规律是： 执行 暂停 执行(间断
12、性)进程的三种基本状态： 就绪状态 执行状态 阻塞状态（又称等待，睡眠）进程的三种基本状态进程的三种基本状态1.就绪状态(Ready)若进程已具备了运行条件，只因CPU被别的进程占用而不能被CPU执行，则称此时进程处于就绪状态。一旦把CPU分配给它，该进程就可以运行。从宏观上讲，它是一种逻辑上的可运行状态。系统中处于就绪状态的进程可能有多个，通常将它们按某种策略（优先级）排成一个队列，称为就绪队列。 进程的三种基本状态进程的三种基本状态2.执行状态(Running）当一个进程已分配到CPU，它的程序正在被CPU执行时进程所处的状态称执行状态，也称为运行状态。对于单CPU系统而言，处于执行状态的
13、进程只可能有一个，多处理机系统中则有多个。进程的三种基本状态进程的三种基本状态3.阻塞状态(Wait)正在执行的进程因等待某种事件的发生而暂时不能运行便放弃CPU的状态称阻塞状态(等待状态)，例如，等待输入/输出、等待进程间的同步/互斥等。一旦引起等待的原因消失，进程便转为就绪状态。以便在适当的时候占用CPU。系统中处于等待状态的进程可能有多个，通常也将它们排成一个队列。有的系统按照进程不同的等待原因，把处于等待状态的进程排成多个队列。进程的三种基本状态进程的三种基本状态1就绪状态执行状态2执行状态阻塞状态3执行状态就绪状态4. 阻塞状态就绪状态时间片完时间片完进程状态的转换：进程的三种基本状
14、态的转换进程的三种基本状态的转换进程的动态性决定了它不会固定处于某个状态，系统中的进程由于各种不同的原因在以上各个状态之间变化。其状态变化及原因如图所示。 创建（新）状态和终止状态 （1）创建（新）状态：一个进程刚刚建立，但还未将它插入就绪队列时的状态。（2）终止状态：一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它撤消时的状态。进程状态的转换1创建(新)状态就绪状态2就绪状态执行状态3执行状态阻塞状态4执行状态就绪状态5执行状态终止状态 6阻塞状态就绪状态 时间片完时间片完进程状态变迁图进程状态变迁图进程的挂起状态进程的挂起状态 使正在执行的进程暂停执行；若此时用户进程
15、正处于就绪状态而未执行，则该进程暂不接受调度，我们把这种静止状态称为挂起状态挂起状态(静止状态)。引入挂起状态的原因有：1终端用户的需要终端用户在自己的程序运行期间发现有可疑问题，希望暂时使自己的程序静止下来。2父进程请求 父进程希望挂起自己的子进程，以便考查和修改子进程，或协调子进程的活动。3负荷调节的需要 当实时系统中的负载较重，影响到实时任务的执行，可挂起不重要进程，保证系统正常运行。4操作系统的需要操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记帐。带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 所谓原语原语就是计算机机器指令的延伸，它是由若干条机器指令构成
16、，并完成一种特定功能的程序段。原语操作由操作系统内核提供。为保证原语操作的正确性，还规定原语在执行期间必须一次执行完，中间不允许被中断。也就是说，原语具有原子性，即原语操作中的所有指令（动作）要么全做，要么全不做，不允许被分割。在单CPU系统中，在执行原语的过程中一般要关中断。1活动就绪静止就绪： 当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya，此时进程可被调度。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys。处于Readys状态的进程，不再被调度执行。2活动阻塞静止阻塞： 当进程处于未被挂起的阻塞状态时，称为它处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds。 处于该状态的进程，在其所期待的事件出现后，它将从静止阻塞变为静止就绪。带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 3静止就绪活动就绪： 处于Readys状态的进程，若用激活原语Active激活后，该进程将转变为 Readya状态。4静止阻塞活动阻塞： 处于Blockcds状
