第2章进程概念和基本状态

1、1 1第二章 进程的描述与控制复习：复习：操作系统的基本特征：操作系统的基本特征：操作系统的主要功能：操作系统的主要功能：OS结构设计：结构设计：并发、共享、虚拟、异步并发、共享、虚拟、异步 CPU、存储管理、设备管理、文件管理、用户接口、存储管理、设备管理、文件管理、用户接口模块、层次、模块、层次、C/S、面向对象、面向对象微内核、单体内核微内核、单体内核2 2第二章 进程的描述与控制第二章第二章 进程的描述与控制进程的描述与控制 2.1 前趋图和程序执行2.2 进程的描述2.3 进程控制2.4 进程同步2.5 经典进程的同步问题2.6 进程通信2.7 线程(Threads)的基本概念2.8

2、 线程的实现3 3第二章 进程的描述与控制2.1.1 2.1.1 前趋图前趋图 所谓所谓前趋图前趋图(Precedence Graph)，是指一个，是指一个有向有向无循环图无循环图，可记为，可记为DAG(Directed Acyclic Graph)，它，它用于描述进程之间执行的先后顺序用于描述进程之间执行的先后顺序。 图中的图中的每个结点每个结点可用来表示一个进程或程序段，可用来表示一个进程或程序段，乃至一条语句，结点间的乃至一条语句，结点间的有向边有向边则表示两个结点之间则表示两个结点之间存在的偏序存在的偏序(Partial Order)或前趋关系或前趋关系(Precedence Rela

3、tion)。2.1 2.1 前趋图和程序执行前趋图和程序执行4 4第二章 进程的描述与控制进程进程(或程序或程序)之间的之间的前趋关系前趋关系可用可用“”来表示，来表示，如果进程如果进程Pi和和Pj存在着前趋关系，可表示为存在着前趋关系，可表示为(Pi，Pj)，也可写成也可写成PiPj，表示在表示在Pj开始执行之前开始执行之前Pi 必须完成必须完成。此时称此时称Pi是是Pj的直接前趋的直接前趋，而称，而称Pj是是Pi的直接后继的直接后继。 在前趋图中，把没有前趋的结点称为在前趋图中，把没有前趋的结点称为初始结点初始结点(Initial Node)，把没有后继的结点称为，把没有后继的结点称为终止

4、结点终止结点(Final Node)。此外，每个结点还具有一个重量。此外，每个结点还具有一个重量(Weight)，用于，用于表示该结点所含有的程序量或程序的执行时间。表示该结点所含有的程序量或程序的执行时间。 5 5第二章 进程的描述与控制P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P9或表示为：P=P1, P2, P3, P4, P5, P6, P7, P8, P9 =(P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6

5、, P8), (P7, P9), (P8, P9)6 6第二章 进程的描述与控制前趋图中是前趋图中是不允许有循环不允许有循环的，否则的，否则必然会产生不可能实现的前趋关系。必然会产生不可能实现的前趋关系。 它一方面要求在它一方面要求在S3开始执行之前，开始执行之前，S2必须完成，另一方面又要求在必须完成，另一方面又要求在S2开开始执行之前，始执行之前，S3必须完成。显然，这必须完成。显然，这种关系是不可能实现的。种关系是不可能实现的。S2S3，S3S27 7第二章 进程的描述与控制2.1.2 2.1.2 程序顺序执行程序顺序执行1. 1. 程序的顺序执行程序的顺序执行通常，一个通常，一个应用程

6、序应用程序由由若干个程序段若干个程序段组成，每一个程序组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。序顺序执行，仅当前一程序段执行完后，才运行后一程序段。 例如，在进行计算时，应先运行例如，在进行计算时，应先运行输入程序输入程序，用于输入用，用于输入用户的程序和数据；然后运行户的程序和数据；然后运行计算程序计算程序，对所输入的数据进行，对所输入的数据进行计算；最后才是运行计算；最后才是运行打印程序打印程序，打印计算结果。，打印计算结果。8 8第二章 进程的描述与控制即

7、使是一个程序段，也可能存在着执行顺序问题，下面即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含了三条语句的程序段：示出了一个包含了三条语句的程序段：S1: a :=x+y；S2: b :=a-5；S3: c :=b+1；其中，语句其中，语句S2必须在语句必须在语句S1后后(即即a被赋值被赋值)才能执行，语句才能执行，语句S3也只能在也只能在b被赋值后才能执行，因此，三条语句存在着这样被赋值后才能执行，因此，三条语句存在着这样的前趋关系：的前趋关系：S1S2S39 9第二章 进程的描述与控制在程序顺序执行时，具有这样三个特征：在程序顺序执行时，具有这样三个特征： 顺序性：顺序性：指

8、处理机严格地按照指处理机严格地按照程序所规定的顺序执行程序所规定的顺序执行，即，即每一操作必须在下一个操作开始之前结束；每一操作必须在下一个操作开始之前结束； 封闭性：封闭性：指程序在封闭的环境下运行，即程序运行时指程序在封闭的环境下运行，即程序运行时独占独占全机资源全机资源，资源的状态，资源的状态(除初始状态外除初始状态外)只有只有本程序才能改变它本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响；程序一旦开始执行，其执行结果不受外界因素影响； 可再现性：可再现性：指只要程序执行时的指只要程序执行时的环境和初始条件相同环境和初始条件相同，当，当程序重复执行时，不论它是从头到尾不停

9、顿地执行，还是程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走停停走走”地执行，都可获得地执行，都可获得相同的结果相同的结果。程序顺序执行。程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。的方便。10 10第二章 进程的描述与控制2.1.32.1.3程序并发执行程序并发执行1. 1. 程序的并发执行：程序的并发执行：在输入程序、计算程序和打在输入程序、计算程序和打印程序三者之间，存在着印程序三者之间，存在着IiCiPi这样的前趋关系，以至这样的前趋关系，以至对一个作业的输入、计算和打印三个程序段必须顺序执行

10、。对一个作业的输入、计算和打印三个程序段必须顺序执行。11 11第二章 进程的描述与控制对于具有下述四条语句的程序段：对于具有下述四条语句的程序段：S1: a :=x+2S2: b :=y+4S3: c :=a+bS4: d :=c+b可以看出：可以看出：S3必须在必须在a和和b被赋值后方能执行；被赋值后方能执行；S4必须在必须在S3之后执行；但之后执行；但S1和和S2则可以并发执行，因为它们彼此互不则可以并发执行，因为它们彼此互不依赖。依赖。12 12第二章 进程的描述与控制2. 2. 程序并发执行时的特征程序并发执行时的特征并发执行的程序它们并发执行的程序它们共享系统资源共享系统资源，以及

11、它们为完成同，以及它们为完成同一项任务而一项任务而相互合作相互合作，致使在这些，致使在这些并发执行的程序之间必将并发执行的程序之间必将形成相互制约形成相互制约的关系，由此会给程序并发执行带来新的特征。的关系，由此会给程序并发执行带来新的特征。(1) 间断性间断性。相互制约将导致并发程序具有。相互制约将导致并发程序具有“执行执行-暂停暂停-执行执行”这种间断性的活动规律；这种间断性的活动规律；(2) 失去封闭性失去封闭性。共享资源，这些。共享资源，这些资源的状态资源的状态也由这些也由这些程序来改变，致使其中任何一个程序在运行时，程序来改变，致使其中任何一个程序在运行时，其环境必然其环境必然受其他

12、程序受其他程序的影响。的影响。13 13第二章 进程的描述与控制(3) 不可再现性。不可再现性。失去封闭性失去封闭性 失去可再现性；在失去可再现性；在程序的两次执行期间发生变化，失去原有的可重复特征程序的两次执行期间发生变化，失去原有的可重复特征。 程序程序A： N=N+1; 程序程序B： print(N) ; N=0;假定某时刻：假定某时刻：N=n;N=N+1; print(N) ;N=0;print(N) ;N=0;N=N+1;print(N) ;N=N+1;N=0; N=n+1 n+1n=0nN=0N=1nN=n+1N=014 14第二章 进程的描述与控制14举例：计算交通流量举例：计算

13、交通流量15 15第二章 进程的描述与控制16 16第二章 进程的描述与控制2.2 2.2 进进程程的的描描述述2.2.1 2.2.1 进程的定义和特征进程的定义和特征1. 1. 进程的定义进程的定义 必须为每个进程配置一个专门的数据结构，称为必须为每个进程配置一个专门的数据结构，称为进程进程 控控制块（制块（PCB）。 利用利用PCB来描述进程的基本情况和活动过程，来描述进程的基本情况和活动过程，来控制和管理进程。来控制和管理进程。 由由程序段程序段、相关的数据段相关的数据段、PCB三部分构成了三部分构成了进程实体进程实体（进程映像），（进程映像），将进程实体简称进程。将进程实体简称进程。

14、所谓所谓创建进程创建进程，实质上就是，实质上就是创建进程的创建进程的PCB； 撤销进程撤销进程，实质上就是，实质上就是撤销进程的撤销进程的PCB17 17第二章 进程的描述与控制其中较典型的定义有：其中较典型的定义有：(1) 进程是程序的一次执行。进程是程序的一次执行。(2) 进程是一个程序及其数据在处理机上顺序执行时所进程是一个程序及其数据在处理机上顺序执行时所发生的活动。发生的活动。(3) 进程是具有独立功能的程序在一个数据集合上运行进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实

15、体的概念后，我们可以把传统在引入了进程实体的概念后，我们可以把传统OS中的中的进程定义为：进程定义为：“进程是进程实体的运行过程，是系统进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位进行资源分配和调度的一个独立单位”。 操作系统 第二章 进程管理18进程通常由三部分组成：程序、数据和进程控制进程通常由三部分组成：程序、数据和进程控制块块PCB 。创建进程，实质上就是创建进程的创建进程，实质上就是创建进程的PCBPCB； 撤销进程，实质上就是撤销进程的撤销进程，实质上就是撤销进程的PCBPCB 程程 序序 数数 据据PCB（a）PCB 程程 序序 数数 据据（b）PCB1共共享

16、享 程程 序序 数数 据据PCB2 数数 据据（c）19 19第二章 进程的描述与控制2. 2. 进程的特征进程的特征进程和程序是两个截然不同的概念，除了进程具有程序进程和程序是两个截然不同的概念，除了进程具有程序所没有的所没有的PCB结构外，还具有下面一些特征：结构外，还具有下面一些特征：(1) 动态性。动态性。(2) 并发性。并发性。(3) 独立性。独立性。(4) 异步性。异步性。 操作系统 第二章 进程管理20进程与程序的区别：1)进程是一次运行的过程，属于一种动态的概念；进程是一次运行的过程，属于一种动态的概念；而程序是而程序是指令的集合，是一个静态的概念。指令的集合，是一个静态的概念

17、。5) 一个程序也可以对应多个进程。一个程序也可以对应多个进程。当当同一程序同一程序同时运行于若同时运行于若干个干个不同的数据集合不同的数据集合上时，它将属于若干个上时，它将属于若干个不同的进程不同的进程。3)进程是有生命期的；进程是有生命期的；而程序是永久的。而程序是永久的。2)进程可以并发执行；进程可以并发执行；而程序不能。而程序不能。4)进程是系统资源分配的基本单位，进程是系统资源分配的基本单位，而程序则不行。而程序则不行。 编译程序编译程序 user1.c user2.c21 21第二章 进程的描述与控制2222第二章 进程的描述与控制2.2.2 2.2.2 进程的基本状态及转换进程的

18、基本状态及转换1. 1. 进程的三种基本状态进程的三种基本状态 进程在其生命周期内可能具有多种状态。每一进程在其生命周期内可能具有多种状态。每一个进程至少应处于三种基本状态之一。个进程至少应处于三种基本状态之一。 就绪状态、执行状态、阻塞状态就绪状态、执行状态、阻塞状态 就绪状态就绪状态(Ready)：进程已获得进程已获得除处理机外除处理机外的的所需资源所需资源，等待分配处理机资源；只要分配，等待分配处理机资源；只要分配CPU就可执行。就可执行。 2323第二章 进程的描述与控制2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换1. 1. 进程的三种基本状态进程的三种基本状态 执

19、执行状态行状态(Running)：占用处理机资源；处于此状态占用处理机资源；处于此状态的进程的数目的进程的数目小于等于小于等于CPU的数目。在没有其他进程可的数目。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执以执行时（如所有进程都在阻塞状态），通常会自动执行系统的行系统的idle进程（相当于空操作）。进程（相当于空操作）。 阻塞状态阻塞状态(Blocked)：由于进程等待某种条件（如由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行。该事件发生前即使把处理

20、机分配给该进程，也无法运行。如：等待如：等待I/O操作的完成。操作的完成。2424第二章 进程的描述与控制2. 进程状态及转换进程状态及转换就绪就绪执行执行等待等待阻塞阻塞进程进程调度调度1.时间片到时间片到2.高优先级高优先级等待某事等待某事件而睡眠件而睡眠因等待事件因等待事件发生而唤醒发生而唤醒创建创建终止终止结束结束2525第二章 进程的描述与控制3. 3. 创建状态和终止状态创建状态和终止状态1) 创建状态创建状态进程是由创建而产生进程是由创建而产生。 创建一个进程一般要创建一个进程一般要通过多个步骤通过多个步骤： 首先由进程申请一个空白首先由进程申请一个空白PCB，并向，并向PCB中

21、填中填写用于控制和管理进程的信息；写用于控制和管理进程的信息； 然后为该进程然后为该进程分配运行时所必须的资源分配运行时所必须的资源； 最后，最后，把该进程转入就绪状态把该进程转入就绪状态并插入就绪队列并插入就绪队列之中。之中。 2626第二章 进程的描述与控制3. 3. 创建状态和终止状态创建状态和终止状态1) 创建状态创建状态如果进程所需的资源尚不能得到满足，如果进程所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其比如系统尚无足够的内存使进程无法装入其中，此时中，此时创建工作尚未完成创建工作尚未完成，进程不能被调，进程不能被调度运行，于是把此时进程所处的状态称为度运行，于是

22、把此时进程所处的状态称为创创建状态。建状态。2727第二章 进程的描述与控制进程创建过程创建进程请求调用创建进程原语Creat()申请PCB、分配进程ID为进程分配资源初始化PCB将进程放进Ready队列产生新进程事件：用户登录：当合法用户登录时作业调度：批处理系统，把一个作业调度执行时。提供服务：当系统收到服务请求时。应用请求：当应用本身需要并发进程时。为新进程分配一个唯一的进程ID,并申请一个空白的PCB。为进程的程序代码、数据用户栈分配内存空间。（1）将系统分配的进程ID、父进程ID写入PCB。（2）将程序计数器指向程序的入口地址、栈指针指向栈顶。（3）设置进程状态、优先级等。2828第二章 进程的描述与控制2) 终止状态终止状态进程的终止进程的终止也要通过两个也要通过两个步骤步骤： 首先，是首先，是等待操作系统进行善后处理等待操作系统进行善后处理， 最后最后将其将其PCB清零清零，并，并将将PCB空间返还系统空间返还系统。当一个进程到达了当一个进程到达了自然结束自然结束点，或是出现了无点，或是出现了无法克服的错法克服的错误误，或是，或是被操作系统所终结被操作系统所终结，或是被其他，或是被其他有终止权的进程有终止权的进程所终结所终结，它将进入终止状态。，它将进入终止状