《操作系统》第2章进程管理.ppt

《《操作系统》第2章进程管理.ppt》由会员分享，可在线阅读，更多相关《《操作系统》第2章进程管理.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统原理Principles of Operating System 1第2章 进程管理 n n2.1 进程与任务n n处理机管理主要研究进程控制、进程和线程管理、处理机管理主要研究进程控制、进程和线程管理、提供进程同步机制和进程通信机制，进程调度和提供进程同步机制和进程通信机制，进程调度和死锁等死锁等。n n我们可以把进程理解为操作系统的工作单元，我们可以把进程理解为操作系统的工作单元，n n进程是正在执行的程序，进程的执行需要一定的进程是正在执行的程序，进程的执行需要一定的资源。资源。n n操作系统主要研究进程与资源的关系。操作系统主要研究进程与资源的关系。22.1.1 前趋图n n为

2、了描述一个程序的各部分(程序段或语句)间的依赖关系 n n如图所示的前趋图中，P1为初始点，P7为终止点。前趋图存在下面的前趋关系：P1P2，P1P3，P1P4，P2P5，P3P5，P3P6，P4P6，P5P7，P6P7。3n n前趋图中有两种元素：n n节点。用圆圈表示，其内涵可以是一条语句、一个程序段或进程。n n有向边。用箭头表示，表示两个节点之间存在的偏序(Partial_Order)或前趋关系(Precedence_Relation)。PiPj表示在Pj开始前Pi必须完成，即Pi是Pj的直接前趋，Pj是Pi的直接后继，前趋图中不存在循环。42.1.2 程序的顺序执行n n程序是指一个

3、按严格次序执行的操作序列，执行的次序有顺序、分支和循环；操作是数据处理的一种规则，一经启动就需要在有限时间内完成。n n一个程序中包括三部分。I:输入操作，C:计算操作，P:打印操作。这样多个程序的顺序执行次序如图所示。5顺序程序的特征如下:n n顺序性：程序的执行是按照程序结构所指定顺序性：程序的执行是按照程序结构所指定的次序进行的。的次序进行的。n n封闭性：程序在封闭的环境下执行，即程序封闭性：程序在封闭的环境下执行，即程序执行时独占全部系统资源。程序一旦开始执行，执行时独占全部系统资源。程序一旦开始执行，其计算结果不受外界因素影响，计算机的状态其计算结果不受外界因素影响，计算机的状态完

4、全由该程序的控制逻辑所决定。完全由该程序的控制逻辑所决定。n n可再现性：只要程序执行时的环境和初始条可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是尾不停顿地执行，还是“停停走走停停走走”地执行，地执行，都将获得相同的结果。程序的结果与它的执行都将获得相同的结果。程序的结果与它的执行速度无关，只要给定相同的输入，一定会得到速度无关，只要给定相同的输入，一定会得到相同的结果。相同的结果。62.1.3 程序的并发执行n n为提高系统资源的利用率和增强系统处理为提高系统资源的利用率和增强系统处理能力，在现代计

5、算机中广泛采用并行操作能力，在现代计算机中广泛采用并行操作技术和并发程序设计技巧。技术和并发程序设计技巧。n n程序的并发执行是指两个或两个以上程序程序的并发执行是指两个或两个以上程序段在执行时间上的重叠。段在执行时间上的重叠。n n每个程序的输入操作、计算操作和打印操每个程序的输入操作、计算操作和打印操作必须顺序执行。对一批程序进行同时处作必须顺序执行。对一批程序进行同时处理时，不同程序的各项操作可以并发执行。理时，不同程序的各项操作可以并发执行。7n n如图2-3所示，存在以下的前趋关系：IiCi，CiPi，IiIi+1，CiCi+1，PiPi+1。故Pi-1和Ci以及Ii+1之间可以并发

6、执行。8程序的并发执行的特征：n n间断性：程序并发执行时，处理机交替执行多个程序，间断性：程序并发执行时，处理机交替执行多个程序，间断性：程序并发执行时，处理机交替执行多个程序，间断性：程序并发执行时，处理机交替执行多个程序，每个程序都是以每个程序都是以每个程序都是以每个程序都是以“停停走走停停走走停停走走停停走走”的方式执行，可能走到中的方式执行，可能走到中的方式执行，可能走到中的方式执行，可能走到中途停下来，而且程序无法预知每次执行和暂停的时间长途停下来，而且程序无法预知每次执行和暂停的时间长途停下来，而且程序无法预知每次执行和暂停的时间长途停下来，而且程序无法预知每次执行和暂停的时间长

7、度，失去原有的时序关系。度，失去原有的时序关系。度，失去原有的时序关系。度，失去原有的时序关系。n n失去封闭性：由于程序的并发执行，打破了由一程序失去封闭性：由于程序的并发执行，打破了由一程序失去封闭性：由于程序的并发执行，打破了由一程序失去封闭性：由于程序的并发执行，打破了由一程序独占系统资源的封闭性。多个程序共享一个计算机系统独占系统资源的封闭性。多个程序共享一个计算机系统独占系统资源的封闭性。多个程序共享一个计算机系统独占系统资源的封闭性。多个程序共享一个计算机系统的多种资源，每个程序的执行都会受其他程序的影响。的多种资源，每个程序的执行都会受其他程序的影响。的多种资源，每个程序的执行

8、都会受其他程序的影响。的多种资源，每个程序的执行都会受其他程序的影响。n n失去可再现性。程序并发执行时，由于失去了封闭性。失去可再现性。程序并发执行时，由于失去了封闭性。失去可再现性。程序并发执行时，由于失去了封闭性。失去可再现性。程序并发执行时，由于失去了封闭性。由于程序每次执行的环境不同，程序执行的速度具有不由于程序每次执行的环境不同，程序执行的速度具有不由于程序每次执行的环境不同，程序执行的速度具有不由于程序每次执行的环境不同，程序执行的速度具有不可再现性。如果不采取制约措施，在不同执行环境下的可再现性。如果不采取制约措施，在不同执行环境下的可再现性。如果不采取制约措施，在不同执行环境

9、下的可再现性。如果不采取制约措施，在不同执行环境下的程序的执行结果也将失去可再现特征。程序的执行结果也将失去可再现特征。程序的执行结果也将失去可再现特征。程序的执行结果也将失去可再现特征。9程序执行是为了对输入信息进行处理，并得到相应的处理结果。为此，程序在并发执行时，必须保证程序执行结果可再现性。由于程序并发执行产生了一系列新特征，为了准确地描述并发程序的执行，必须引入进程的概念。102.1.4 进程n n进程是指程序在并发环境下的一次运行过程。进程是指程序在并发环境下的一次运行过程。n n可并发执行的程序在一个数据集合上的运行过程可并发执行的程序在一个数据集合上的运行过程 n n传统进程的

10、两个属性：传统进程的两个属性：进程是操作系统进行资进程是操作系统进行资源分配和处理机调度的基本单位。源分配和处理机调度的基本单位。n n现代操作系统引进线程之后，进程的两个属性发现代操作系统引进线程之后，进程的两个属性发生分离，进程仅是操作系统进行资源分配基本单生分离，进程仅是操作系统进行资源分配基本单位，而线程是操作系统处理机调度的基本单位。位，而线程是操作系统处理机调度的基本单位。11引入进程对操作系统的影响n n进程是计算机系统资源的使用主体，进程进程是计算机系统资源的使用主体，进程与处理机、存储器和外设等资源的分配和与处理机、存储器和外设等资源的分配和回收相对应。操作系统引入进程，可以

11、实回收相对应。操作系统引入进程，可以实现多个进程的并发执行，提高了系统资源现多个进程的并发执行，提高了系统资源的利用率，提高了系统的吞吐量。但由于的利用率，提高了系统的吞吐量。但由于每个进程配备每个进程配备PCB，增加了内存的空间开，增加了内存的空间开销。进程之间的切换、同步等需付出时间销。进程之间的切换、同步等需付出时间开销，引入进程会带来额外的时空开销，开销，引入进程会带来额外的时空开销，增加了操作系统的复杂性。增加了操作系统的复杂性。12进程的特征n n动态性动态性n n并发性并发性n n独立性独立性n n异步性异步性n n结构特征。结构特征。13n n进程的程序段描述了进程所要完成的进

12、程的程序段描述了进程所要完成的功能。如果一个程序能够被多个进程功能。如果一个程序能够被多个进程同时共享执行，那么，这个程序段就同时共享执行，那么，这个程序段就是纯代码是纯代码(pure code)，即可重入代码，即可重入代码(reentry code)形式编写的，它是指形式编写的，它是指进程执行时不可修改的部分。数据段进程执行时不可修改的部分。数据段是指进程执行时用到的数据。用户程是指进程执行时用到的数据。用户程序在此数据集合上进行操作，得到相序在此数据集合上进行操作，得到相应的结果。进程控制块包含进程的描应的结果。进程控制块包含进程的描述信息和控制信息，不同的操作系统述信息和控制信息，不同的

13、操作系统其进程控制块的内容及信息量也不相其进程控制块的内容及信息量也不相同。同。14进程和程序的比较n n程序是有序代码的集合，是一个静态的概念。进程是程序是有序代码的集合，是一个静态的概念。进程是程序是有序代码的集合，是一个静态的概念。进程是程序是有序代码的集合，是一个静态的概念。进程是程序的一次执行过程，是一个动态概念。进程不可以在程序的一次执行过程，是一个动态概念。进程不可以在程序的一次执行过程，是一个动态概念。进程不可以在程序的一次执行过程，是一个动态概念。进程不可以在计算机之间迁移，而程序通常对应着文件，可以复制。计算机之间迁移，而程序通常对应着文件，可以复制。计算机之间迁移，而程序

14、通常对应着文件，可以复制。计算机之间迁移，而程序通常对应着文件，可以复制。n n进程是一个状态变化的过程，是有生命期的。而程序进程是一个状态变化的过程，是有生命期的。而程序进程是一个状态变化的过程，是有生命期的。而程序进程是一个状态变化的过程，是有生命期的。而程序是永久的，可以长久保存。是永久的，可以长久保存。是永久的，可以长久保存。是永久的，可以长久保存。n n进程与程序的组成不同。进程由程序段、数据段和进进程与程序的组成不同。进程由程序段、数据段和进进程与程序的组成不同。进程由程序段、数据段和进进程与程序的组成不同。进程由程序段、数据段和进程控制块组成，而程序仅是代码的有序集合。程控制块组

15、成，而程序仅是代码的有序集合。程控制块组成，而程序仅是代码的有序集合。程控制块组成，而程序仅是代码的有序集合。n n进程与程序是密切相关的。通过多次执行，一个程序进程与程序是密切相关的。通过多次执行，一个程序进程与程序是密切相关的。通过多次执行，一个程序进程与程序是密切相关的。通过多次执行，一个程序可对应多个进程。但进程与它本身所运行的程序只能是可对应多个进程。但进程与它本身所运行的程序只能是可对应多个进程。但进程与它本身所运行的程序只能是可对应多个进程。但进程与它本身所运行的程序只能是一对一的关系。一对一的关系。一对一的关系。一对一的关系。n n进程更能真实地描述并发，而程序不能。进程更能真

16、实地描述并发，而程序不能。进程更能真实地描述并发，而程序不能。进程更能真实地描述并发，而程序不能。n n进程可创建其他进程，而程序并不能形成新的程序。进程可创建其他进程，而程序并不能形成新的程序。进程可创建其他进程，而程序并不能形成新的程序。进程可创建其他进程，而程序并不能形成新的程序。152.1.5 任务与多任务n n对于有多个CPU的计算机，同时在每一个CPU上执行进程称为多重处理。多重处理是针对多机系统定义的，这一点请读者注意理解。我们可以认为多重处理是多任务处理在多机系统中的一个特例，多重处理是多任务处理的子集。n n多任务是指在同一时间间隔内系统执行多个进程,这里包含多重处理和多进程

17、并发执行。任务是一个具有开始时间和完成时间的操作,任务是系统的基本工作单元，任务调度与进程调度的过程基本类似。在操作系统中，站在用户的角度上，任务可以理解为逻辑上的进程。不同的操作系统进程与任务的含义不同，在Linux系统中，进程与任务的含义是相同的。162.2 进程的状态与进程控制块进程的基本状态17进程在运行过程中主要是在就绪、执行和阻塞三种基本状态间进行转换 n n创建创建创建创建(new)(new)状态。进程正在创建过程中，但还未将它状态。进程正在创建过程中，但还未将它状态。进程正在创建过程中，但还未将它状态。进程正在创建过程中，但还未将它送入就绪队列时的状态。送入就绪队列时的状态。送

18、入就绪队列时的状态。送入就绪队列时的状态。n n就绪状态（就绪状态（就绪状态（就绪状态（ReadyReady）。进程已得到必要的资源，唯缺）。进程已得到必要的资源，唯缺）。进程已得到必要的资源，唯缺）。进程已得到必要的资源，唯缺处理机，等待处理机调度，一旦获得处理机便可立即执处理机，等待处理机调度，一旦获得处理机便可立即执处理机，等待处理机调度，一旦获得处理机便可立即执处理机，等待处理机调度，一旦获得处理机便可立即执行。将处于就绪状态的那些进程排成队列就叫就绪状态行。将处于就绪状态的那些进程排成队列就叫就绪状态行。将处于就绪状态的那些进程排成队列就叫就绪状态行。将处于就绪状态的那些进程排成队列

19、就叫就绪状态队列。队列。队列。队列。n n执行状态（执行状态（执行状态（执行状态（RunningRunning）。进程占用）。进程占用）。进程占用）。进程占用CPUCPU资源并正在资源并正在资源并正在资源并正在CPUCPU上执行，处于此状态的进程数目小于等于上执行，处于此状态的进程数目小于等于上执行，处于此状态的进程数目小于等于上执行，处于此状态的进程数目小于等于CPUCPU的数的数的数的数目。在没有其他进程可以执行时目。在没有其他进程可以执行时目。在没有其他进程可以执行时目。在没有其他进程可以执行时(如所有进程都在阻塞如所有进程都在阻塞如所有进程都在阻塞如所有进程都在阻塞状态状态状态状态)，

20、通常会自动执行系统的空闲进程。在多机系统，通常会自动执行系统的空闲进程。在多机系统，通常会自动执行系统的空闲进程。在多机系统，通常会自动执行系统的空闲进程。在多机系统中，可以有多个进程处于执行状态。而在单机系统中，中，可以有多个进程处于执行状态。而在单机系统中，中，可以有多个进程处于执行状态。而在单机系统中，中，可以有多个进程处于执行状态。而在单机系统中，仅有一个进程处于执行状态。仅有一个进程处于执行状态。仅有一个进程处于执行状态。仅有一个进程处于执行状态。18n n等待状态（等待状态（Waiting）。也称为阻塞）。也称为阻塞（Blocked)状态，在执行过程中，因等待某一状态，在执行过程中

21、，因等待某一事件而暂时无法执行。将等待同一事件的阻塞进事件而暂时无法执行。将等待同一事件的阻塞进程排一个队列就叫该事件的等待队列。程排一个队列就叫该事件的等待队列。n n退出（退出（exit)状态。当一个进程已经正常结束状态。当一个进程已经正常结束或异常结束，系统回收资源。操作系统已将它从或异常结束，系统回收资源。操作系统已将它从就绪队列中移出，正在将它撤消。就绪队列中移出，正在将它撤消。19进程的状态变迁机制 n n提交(Admit)：完成一个新进程的创建过程，新进程进入就绪状态。由于性能、内存、进程总数等原因，系统会限制并发进程总数。n n调度(Dispatch)：按调度算法从就绪进程队列

22、中选择进程，进入执行状态。n n释放(Release)：由于进程完成或异常终止进程运行，进入退出状态。状态变迁图中只画出了执行状态到退出状态间的释放转换。但实际上，还存在从就绪状态或阻塞状态到退出状态的释放转换。执行到退出的转换可分为正常退出(exit)和异常退出(abort)。20n n超时超时(Timeout)(Timeout)：由于用完时间片或高优先级进程就由于用完时间片或高优先级进程就绪等原因导致进程暂停执行。绪等原因导致进程暂停执行。分配的时间片用完而发生分配的时间片用完而发生时钟中断，或一个刚进入就绪队列的进程，其优先级高时钟中断，或一个刚进入就绪队列的进程，其优先级高于处于执行状

23、态的进程的优先级而抢占处理机，于是进于处于执行状态的进程的优先级而抢占处理机，于是进程从执行状态到就绪状态的转变。程从执行状态到就绪状态的转变。n n等待事件等待事件(Event Wait)(Event Wait)：进程要求的事件未出现而进：进程要求的事件未出现而进入阻塞。可能的原因包括：申请系统服务或资源、通信、入阻塞。可能的原因包括：申请系统服务或资源、通信、I/OI/O操作等。操作等。n n事件发生事件发生(Event Occurs)(Event Occurs)：进程等待的事件发生。例：进程等待的事件发生。例如，操作完成、申请成功等。进程从等待状态转变为就如，操作完成、申请成功等。进程从

24、等待状态转变为就绪状态，重新等待处理机调度。绪状态，重新等待处理机调度。n n操作系统中多个进程的并发执行是通过两套循环完成。操作系统中多个进程的并发执行是通过两套循环完成。一是通过调度与超时二种状态变迁原因的循环。二是通一是通过调度与超时二种状态变迁原因的循环。二是通过调度、等待事件和事件发生三种状态变迁原因的循环。过调度、等待事件和事件发生三种状态变迁原因的循环。21进程控制块n n所谓进程控制块（Process Control Block，PCB）是由操作系统维护，用来记录进程相关信息的数据结构。每个进程在操作系统中都有对应的进程控制块。操作系统依据进程控制块对进程进行控制和管理，进程控

25、制块中的内容会随进程的推进而动态改变。进程控制块通常不能由应用程序自身的代码来直接访问，而要通过系统调用进行访问。22进程之间的上下文切换n n在多进程并发执行中，将CPU切换到另一个进程需要保存原来进程的关联状态并装入新进程的关联状态。这一任务称为上下文切换当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调度要执行的新进程的已保存的关联状态。上下文切换时间是系统额外开销，因为切换时系统并不能做什么有用的工作。n n操作系统越复杂，上下文切换所要做的工作就越多。上下文切换问题可能会成为操作系统性能的瓶颈，我们可以采用线程减少或避免上下文切换时间，降低操作系统开销。232

26、.3 进程控制n n链接方式24索引方式252.3.3 进程控制原语n n创建进程的典型事件n n批处理系统中的作业调度。n n用户登录。n n用户启动应用程序。n n由操作系统创建的系统服务。n n创建新的进程。26撤消原语n n撤消进程的典型事件：n n正常结束：进程完成了程序的执行任务。n n异常结束：出错或故障结束，有算术运算出错、I/O故障等。n n被干预结束：包括操作员或操作系统干预结束、被父进程请求结束、父进程本身要结束而其子孙进程跟随结束。27阻塞原语n n阻塞原语具体的操作过程是：查找到该被阻塞进阻塞原语具体的操作过程是：查找到该被阻塞进阻塞原语具体的操作过程是：查找到该被阻

27、塞进阻塞原语具体的操作过程是：查找到该被阻塞进程的程的程的程的PCBPCB，剥夺其处理机，将其状态改为阻塞状，剥夺其处理机，将其状态改为阻塞状，剥夺其处理机，将其状态改为阻塞状，剥夺其处理机，将其状态改为阻塞状态，转进程调度。根据阻塞事件的类型将该阻塞态，转进程调度。根据阻塞事件的类型将该阻塞态，转进程调度。根据阻塞事件的类型将该阻塞态，转进程调度。根据阻塞事件的类型将该阻塞进程插入到相应阻塞队列中。阻塞原语的算法描进程插入到相应阻塞队列中。阻塞原语的算法描进程插入到相应阻塞队列中。阻塞原语的算法描进程插入到相应阻塞队列中。阻塞原语的算法描述述述述:n nvoid block(WQr)void

28、 block(WQr)n ni=*EP;/*i=*EP;/*取得调用者进程的取得调用者进程的取得调用者进程的取得调用者进程的PCB*/PCB*/n nstop(i);/*stop(i);/*剥夺剥夺剥夺剥夺CPU*/CPU*/n ni.status=”blocked”/*i.status=”blocked”/*将进程将进程将进程将进程i i的状态置为阻塞的状态置为阻塞的状态置为阻塞的状态置为阻塞状态状态状态状态*/*/n ni.state=WQr;/*i.state=WQr;/*填入所在队列的首指针填入所在队列的首指针填入所在队列的首指针填入所在队列的首指针*/*/n ninsert(WQr)

29、;/*insert(WQr);/*插入相应阻塞队列插入相应阻塞队列插入相应阻塞队列插入相应阻塞队列*/*/n nscheduler;/*scheduler;/*进程调度进程调度进程调度进程调度*/*/n n 28唤醒原语n n因事件发生，进程从阻塞状态转换到就绪状态，用唤醒因事件发生，进程从阻塞状态转换到就绪状态，用唤醒因事件发生，进程从阻塞状态转换到就绪状态，用唤醒因事件发生，进程从阻塞状态转换到就绪状态，用唤醒原语完成。唤醒原语对原语完成。唤醒原语对原语完成。唤醒原语对原语完成。唤醒原语对PCBPCB进行修改来实现其功能，在进行修改来实现其功能，在进行修改来实现其功能，在进行修改来实现其功

30、能，在被唤醒的阻塞队列中，找到队首进程。并将该进程从阻被唤醒的阻塞队列中，找到队首进程。并将该进程从阻被唤醒的阻塞队列中，找到队首进程。并将该进程从阻被唤醒的阻塞队列中，找到队首进程。并将该进程从阻塞队列移出，插入到就绪队列中，再将该进程状态改为塞队列移出，插入到就绪队列中，再将该进程状态改为塞队列移出，插入到就绪队列中，再将该进程状态改为塞队列移出，插入到就绪队列中，再将该进程状态改为就绪状态。对于可抢占式进程调度，还可引起进程调度，就绪状态。对于可抢占式进程调度，还可引起进程调度，就绪状态。对于可抢占式进程调度，还可引起进程调度，就绪状态。对于可抢占式进程调度，还可引起进程调度，以便让高优

31、先权进程迅速进入执行状态。唤醒原语算法以便让高优先权进程迅速进入执行状态。唤醒原语算法以便让高优先权进程迅速进入执行状态。唤醒原语算法以便让高优先权进程迅速进入执行状态。唤醒原语算法描述为：描述为：描述为：描述为：n nvoid wakeup(WQr)void wakeup(WQr)n ni=remove(WQr);/*i=remove(WQr);/*查找并得到查找并得到查找并得到查找并得到PCB(n)PCB(n)，从阻塞队列，从阻塞队列，从阻塞队列，从阻塞队列wQrwQr中移出中移出中移出中移出n*/n*/n ni.status=”ready”;/*i.status=”ready”;/*置进程置进程置进程置进程i i的状态为就绪状态的状态为就绪状态的状态为就绪状态的状态为就绪状态*/*/n ni.state=RQ;/*i.state=RQ;/*填入所在队列的首指针填入所在队列的首指针填入所在队列的首指针填入所在队列的首指针*/*/n ninsert(RQinsert(RQ，i);/*i);/*插入就绪队列插入就绪队列插入就绪队列插入就绪队列RQ*/RQ*/n nscheduler;/*scheduler;/*进程调度进程调度进程调度进程调度*/*/n n 29