操作系统原理课件

1、第三章 进 程 管 理 1第三章第三章 进程管理进程管理 3.1 3.1 进程概述进程概述 3.2 3.2 进程控制块进程控制块 3.3 3.3 调度调度 3.4 UNIX3.4 UNIX系统的进程调度系统的进程调度 3.5 3.5 进程控制进程控制 3.6 3.6 进程的创建和图像改换进程的创建和图像改换 3.7 3.7 线程线程 3.8 Linux3.8 Linux进程管理进程管理第三章 进 程 管 理 23.1 3.1 进程概述进程概述 u程序的执行有两种方式：程序的执行有两种方式：顺序执行顺序执行和和并发执行并发执行。 顺序执行顺序执行是是单道单道批处理系统的执行方式，也批处理系统的执

2、行方式，也用于用于简单的单片机简单的单片机系统；系统； 现在的操作系统多为现在的操作系统多为并发执行并发执行，具有许多新，具有许多新的特征。引入并发执行的目的是为了提高的特征。引入并发执行的目的是为了提高资资源利用率源利用率。第三章 进 程 管 理 3程序程序：是一个在时间上严格有序的指令集合。：是一个在时间上严格有序的指令集合。程序规定了完成某一任务时，计算机所需做程序规定了完成某一任务时，计算机所需做的各种操作，以及这些操作的执行时间。的各种操作，以及这些操作的执行时间。程序的顺序执行：具有独立功能的程序程序的顺序执行：具有独立功能的程序独占独占CPUCPU直至得到最终结果的过程。直至得到

3、最终结果的过程。程序程序第三章 进 程 管 理 4程序顺序执行时的特征程序顺序执行时的特征 （1 1）顺序性）顺序性：（执行的顺序性）由于内存中每：（执行的顺序性）由于内存中每次只有一道程序，因此各个程序是按次序执次只有一道程序，因此各个程序是按次序执行的，即执行完一个以后，再执行下一个。行的，即执行完一个以后，再执行下一个。（2 2）封闭性）封闭性：独占全部资源，计算机的状态只：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定由于该程序的控制逻辑所决定（3 3）可再现性）可再现性：结果的再现性，初始条件相同：结果的再现性，初始条件相同则结果相同。则结果相同。第三章 进 程 管 理 5程

4、序的并发执行及其特征程序的并发执行及其特征 1. 程序的并发执行程序的并发执行 P1P2P3P4I1I2I3I4C1C2C3C4第三章 进 程 管 理 6程序并发执行时的特征程序并发执行时的特征 间断间断(异步异步)性性：执行的顺序性被打破，：执行的顺序性被打破，“走走停停走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；一个程序可能走到中途停下来，失去原有的时序关系； 失去封闭性失去封闭性：资源的独占性被打破，共享资源，受其：资源的独占性被打破，共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，

5、失去原有的不变特征。的数据可能被另一个程序修改，失去原有的不变特征。 失去可再现性失去可再现性：失去封闭性：失去封闭性 失去可再现性；外界失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重环境在程序的两次执行期间发生变化，失去原有的可重复特征。复特征。第三章 进 程 管 理 7不加控制的并发执行所带来的影响不加控制的并发执行所带来的影响u例：为了了解某单行道的交通流量，在路口安放一个监视器，例：为了了解某单行道的交通流量，在路口安放一个监视器，功能是有车通过该路段时，就向计算机发送一个信号。程序功能是有车通过该路段时，就向计算机发送一个信号。程序A功能：接收到监视器信号时，就在

6、计数单元功能：接收到监视器信号时，就在计数单元COUNT上加上加1；程序程序B功能：每个半个小时，打印功能：每个半个小时，打印COUNT的值，然后清零。的值，然后清零。程序程序A：While(1)A1:收到监视器信号；收到监视器信号；A2:COUNT=COUNT+1;程序程序B：While(1)B1:延迟半小时；延迟半小时；B2:打印打印COUNT的值的值;B3:COUNT=0;A1A2B1B2A1A2B3第三章 进 程 管 理 83.1.1 进程的概念进程的概念 程序本身完全是个静态的概念（程序是完成某程序本身完全是个静态的概念（程序是完成某个功能的指令的集合），而系统及其中的各个程序个功能

7、的指令的集合），而系统及其中的各个程序实际上是处于不断变化的状态，程序的概念反映不实际上是处于不断变化的状态，程序的概念反映不了这种动态性；其次，程序概念也反映不了系统中了这种动态性；其次，程序概念也反映不了系统中的并行特性。的并行特性。 综上所述，静态的程序概念已不敷使用，需要综上所述，静态的程序概念已不敷使用，需要引用一个新的概念引用一个新的概念“进程进程”。第三章 进 程 管 理 9进程的概念进程的概念u进程是进程是程序程序处于一个执行环境中在一个数据集处于一个执行环境中在一个数据集上的上的运行过程运行过程，它是系统进行，它是系统进行资源分配和调度资源分配和调度的一个的一个可并发执行可并

8、发执行的独立单位。的独立单位。第三章 进 程 管 理 10进程的特征进程的特征u（1）动态性）动态性 进程的实质是程序的一次执行过程，因进程的实质是程序的一次执行过程，因此，动态性是进程的最基本特征。动态性还表现为：此，动态性是进程的最基本特征。动态性还表现为：“它由创建而产生，由它由创建而产生，由调度调度而执行，由撤消而消而执行，由撤消而消亡亡”。可见，进程有一定的生命期，而程序只是一组。可见，进程有一定的生命期，而程序只是一组有序指令的集合，并存放于某种介质上，本身并无运有序指令的集合，并存放于某种介质上，本身并无运动的含义，因此是静态的。动的含义，因此是静态的。u（2）并发性）并发性 这

9、是指多个进程能在一段时间内同时运这是指多个进程能在一段时间内同时运行，并发性是进程的重要特征。引入进程的目的也正行，并发性是进程的重要特征。引入进程的目的也正是为了使其程序能和其他进程的程序并发执行，而程是为了使其程序能和其他进程的程序并发执行，而程序（没有建立进程）是不能并发执行的（由于程序不序（没有建立进程）是不能并发执行的（由于程序不反映执行过程）。反映执行过程）。第三章 进 程 管 理 11进程的特征进程的特征u（3）独立性）独立性 这是指进程是一个能独立运行、独立分配资这是指进程是一个能独立运行、独立分配资源和独立调度的基本单位，凡未建立进程的程序，都不能源和独立调度的基本单位，凡未

10、建立进程的程序，都不能作为一个独立的单位参加运行。只有进程有资格向系统提作为一个独立的单位参加运行。只有进程有资格向系统提出申请资源并获得系统提供的服务。出申请资源并获得系统提供的服务。u（4）异步性）异步性 这是指进程按各自独立的、不可预知的速度这是指进程按各自独立的、不可预知的速度向前推进，或说进程按异步方式运行。向前推进，或说进程按异步方式运行。u（5）结构性）结构性 为使进程能独立运行，应为之配置一个称为为使进程能独立运行，应为之配置一个称为“进程控制块进程控制块”的数据结构，简称的数据结构，简称PCB。第三章 进 程 管 理 12进程和程序的联系与区别：进程和程序的联系与区别：u（1

11、）联系。）联系。 程序是构成进程的组成部分之一，一个进程的程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序，如果没有程运行目标是执行它所对应的程序，如果没有程序，进程就失去了其实际存在的意义。序，进程就失去了其实际存在的意义。第三章 进 程 管 理 13进程和程序的联系与区别：进程和程序的联系与区别：u（2）区别。）区别。进程是程序的一次动态执行活动，而程序是进进程是程序的一次动态执行活动，而程序是进程运行的静态描述文本。程运行的静态描述文本。一个进程可以执行一个或多个程序，反之，同一个进程可以执行一个或多个程序，反之，同一程序也可被多个进程同时执行。一程序也可被多个进程同

12、时执行。 程序是一种软件资源，它可以长期保存，而进程序是一种软件资源，它可以长期保存，而进程是一次执行过程，它是暂时存在的、动态地程是一次执行过程，它是暂时存在的、动态地产生和中止的。产生和中止的。第三章 进 程 管 理 14特权指令、管态、目态特权指令、管态、目态u特权指令：只能由操作系统使用的指令。特权指令：只能由操作系统使用的指令。u非特权指令：大家（用户和操作系统）都能使用的指非特权指令：大家（用户和操作系统）都能使用的指令。令。u用户执行状态，用户执行状态，又称又称用户态，目态（目标程序态）用户态，目态（目标程序态），进程的用户程序段执行时，该程序处于用户态。用户进程的用户程序段执行

13、时，该程序处于用户态。用户态时不可直接访问受保护的态时不可直接访问受保护的OSOS代码；代码；u系统执行状态系统执行状态，又称，又称系统态，核心态，管态（管理程系统态，核心态，管态（管理程序态），序态），进程的系统程序执行时，该进程处于系统态。进程的系统程序执行时，该进程处于系统态。核心态时可以执行核心态时可以执行OSOS代码，可以访问全部进程空间。代码，可以访问全部进程空间。第三章 进 程 管 理 153.1.2 进程的组成进程的组成 u进程是在一个上下文的执行环境中执行的，这个进程是在一个上下文的执行环境中执行的，这个执行环境称为进程的映像，或称图像。执行环境称为进程的映像，或称图像。u它

14、包括处理机中各通用寄存器的值、进程的内存它包括处理机中各通用寄存器的值、进程的内存映像、打开文件的状态和进程占用资源的信息等映像、打开文件的状态和进程占用资源的信息等很多部分。很多部分。u进程映像的关键部分是存储器映像。进程映像的关键部分是存储器映像。u进程存储器映像由以下几部分组成：进程存储器映像由以下几部分组成：进程控制块进程控制块、进程执行的程序进程执行的程序（code）、）、进程执行时所用的数进程执行时所用的数据据、进程执行时使用的工作区进程执行时使用的工作区第三章 进 程 管 理 16进程的组成进程的组成第三章 进 程 管 理 171.进程控制块进程控制块u进程控制块进程控制块PCB

15、（ProcessControlBlock）是系统）是系统用于用于查询和控制进程运行查询和控制进程运行的档案，它描述进程的的档案，它描述进程的特征，记载进程的历史，决定进程的命运。特征，记载进程的历史，决定进程的命运。u由于由于PCB较大，一些系统将其分割成两部分：一较大，一些系统将其分割成两部分：一部分是部分是进程基本控制块进程基本控制块，这部分记录不管进程是，这部分记录不管进程是否在执行，操作系统都需要访问的进程控制信息，否在执行，操作系统都需要访问的进程控制信息，因此，因此，进程基本控制块要常驻内存进程基本控制块要常驻内存；u另一部分是另一部分是进程扩充控制块进程扩充控制块，当进程不处于执

16、行，当进程不处于执行状态时，操作系统就不会访问这部分信息，扩充状态时，操作系统就不会访问这部分信息，扩充控制块能对换到盘交换区中。控制块能对换到盘交换区中。第三章 进 程 管 理 182.共享正文段共享正文段u用高级语言编写的程序一般是可重入的用高级语言编写的程序一般是可重入的“纯代纯代码码”，也即是它可以被多个进程并发地执行的。，也即是它可以被多个进程并发地执行的。u共享正文段不限于包括程序，还可包括不可修改共享正文段不限于包括程序，还可包括不可修改的常数。的常数。u用户用用户用C语言所编的程序经编译后产生的代码也语言所编的程序经编译后产生的代码也是作为共享正文段装入内存的是作为共享正文段装

17、入内存的第三章 进 程 管 理 193.数据区数据区u进程执行时用到的数据，如进程执行时用到的数据，如C程序中的外部变量程序中的外部变量和静态变量；和静态变量；u如进程执行的程序为非共享程序（如用汇编语言如进程执行的程序为非共享程序（如用汇编语言编写，可以在执行时修改执行的代码和其中夹带编写，可以在执行时修改执行的代码和其中夹带的数据），则也可构成数据区的一部分。的数据），则也可构成数据区的一部分。第三章 进 程 管 理 204. 工作区工作区u进程在核心态运行时的工作区为核心栈；进程在核心态运行时的工作区为核心栈；u在用户态下运行时的工作区为用户栈；在用户态下运行时的工作区为用户栈；u在调用

18、核心的函数或用户函数时，两种栈分别用在调用核心的函数或用户函数时，两种栈分别用于传递参数、存放返回地址、保护现场以及为局于传递参数、存放返回地址、保护现场以及为局部动态变量提供存储空间。部动态变量提供存储空间。u此外，核心栈还可用于保护中断现场，用户栈还此外，核心栈还可用于保护中断现场，用户栈还用于向主程序（用于向主程序（main函数）传递命令行参数等。函数）传递命令行参数等。第三章 进 程 管 理 213.1.3 进程的状态及其变化进程的状态及其变化 u进程具有生存期，它有一个创建、活动及消亡进程具有生存期，它有一个创建、活动及消亡的过程。的过程。u进程在其活动期间可以因外部和内部的原因进进

19、程在其活动期间可以因外部和内部的原因进入入“睡眠睡眠”阶段。阶段。“睡眠睡眠”的进程会被的进程会被“唤醒唤醒”而继续先前的活动。为了完成一组特定的任务，而继续先前的活动。为了完成一组特定的任务，进程也可采用进程也可采用“克隆克隆”技术，生成一个或多个技术，生成一个或多个子进程，互相配合地工作。子进程，互相配合地工作。u进程在其整个生存期间可处于不同的状态，有进程在其整个生存期间可处于不同的状态，有一些不同的特征一些不同的特征第三章 进 程 管 理 22就绪就绪(Ready)状态状态：一个进程已经具备运行条件，但由：一个进程已经具备运行条件，但由于无于无CPU暂时不能运行的状态（当调度给其暂时不

20、能运行的状态（当调度给其CPU时，时，立即可以运行立即可以运行)。“万事俱备，只欠东风万事俱备，只欠东风”。位于。位于“就就绪队列绪队列”中中 。2) 执行状态执行状态(Running)：进程占有了包括：进程占有了包括CPU在内的全在内的全部资源，并在部资源，并在CPU上运行。上运行。 3) 阻塞状态阻塞状态(Blocked) ：也称等待态、睡眠态、封锁态、：也称等待态、睡眠态、封锁态、挂起态等。指进程因等待某种事件的发生而暂时不能挂起态等。指进程因等待某种事件的发生而暂时不能运行的状态（即使运行的状态（即使CPU空闲，该进程也不可运行）。空闲，该进程也不可运行）。处于阻塞态的进程位于阻塞队列

21、中。处于阻塞态的进程位于阻塞队列中。第三章 进 程 管 理 23运行运行Running就绪就绪Ready阻塞阻塞BlockedDispatchDispatchTimeoutTimeoutEventEventWaitWaitEventEventOccursOccurs基本状态间的转换第三章 进 程 管 理 24 在实际的操作系统中，为了管理和调度的便利，还将进在实际的操作系统中，为了管理和调度的便利，还将进程的状态进一步细分，例如，程的状态进一步细分，例如，UNIX系统系统V定义了定义了10种进程的种进程的状态：状态：#define SSLEEP 1 睡眠状态睡眠状态#define SWAIT

22、2 等待状态，该状态已被废弃等待状态，该状态已被废弃#define SRUN 3 执行状态或就绪状态执行状态或就绪状态#define SIDL 4 创建子进程状态创建子进程状态#define SZOMB 5 等待善后处理状态等待善后处理状态#define SSTOP 6 进程处于被跟踪的暂停状态进程处于被跟踪的暂停状态#define SXBRK 7 因数据段扩展时未满足的换出状态因数据段扩展时未满足的换出状态#define SXSTK 8 因栈段扩展时未满足的换出状态因栈段扩展时未满足的换出状态#define SXFRK 9 创建子进程时内存不够，父进程锁定在内创建子进程时内存不够，父进程锁定

23、在内存的状态存的状态#define SXTXT 10 因正文段扩展未满足而被换出的状态因正文段扩展未满足而被换出的状态第三章 进 程 管 理 253.2 3.2 进程控制块进程控制块 u为了掌握进程的运行状况和便于管理和控制进为了掌握进程的运行状况和便于管理和控制进程的运行，操作系统为每一个进程设置了一个程的运行，操作系统为每一个进程设置了一个数据结构数据结构进程控制块（进程控制块（PCB）。u进程控制块进程控制块是进程的控制结构，包含了进程的是进程的控制结构，包含了进程的描述信息描述信息、控制信息控制信息和和资源信息资源信息以及以及现场保护现场保护区区。第三章 进 程 管 理 261. 进程

24、控制块的作用进程控制块的作用 进程控制块是由进程控制块是由OS维护维护的用来记录的用来记录进程相关信息和管理进程进程相关信息和管理进程设置的一个专门的数据结构。设置的一个专门的数据结构。进程控制块的作用是使一个在多道程序环境下不能独立运行进程控制块的作用是使一个在多道程序环境下不能独立运行的程序的程序(含数据含数据)，成为一个能独立运行的基本单位，一个能与，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，其它进程并发执行的进程。或者说，OS是根据是根据PCB来对并发来对并发执行的进程进行控制和管理的。执行的进程进行控制和管理的。PCB是进程动态特性的集中反映。系统通过是进

25、程动态特性的集中反映。系统通过PCB感知进程的感知进程的存在，通过存在，通过PCB中所包含的各项变量的变化，掌握进程的状中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的；态以达到控制进程活动的目的；第三章 进 程 管 理 27uPCBPCB随进程的创建而填写，随进程的撤消而释放；随进程的创建而填写，随进程的撤消而释放；u系统利用系统利用PCBPCB来控制和管理进程，所以来控制和管理进程，所以PCBPCB是系统感知是系统感知进程存在的唯一标志进程存在的唯一标志u进程与进程与PCBPCB是一一对应的是一一对应的uPCBPCB结构常驻内存；系统将所有结构常驻内存；系统将所有PCBPC

26、B组织成若干个队列，组织成若干个队列，存放在操作系统中专门开辟的存放在操作系统中专门开辟的PCBPCB区内。区内。第三章 进 程 管 理 282. 进程控制块中的信息进程控制块中的信息 1) 进程标识符进程标识符 进程标识符用于惟一地标识一个进程。一个进程通常有进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：两种标识符： (1) 内部标识符内部标识符。在所有的操作系统中，都为每一个进。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。程赋予一个惟一的数字标识符，它通常是一个进程的序号。 设置内部标识符主要是为了方便系统使用。设置内部标识符主要是为

27、了方便系统使用。 (2) 外部标识符。外部标识符。它由创建者提供，通常是由字母、数字它由创建者提供，通常是由字母、数字组成，往往是由用户组成，往往是由用户(进程进程)在访问该进程时使用。为了描述在访问该进程时使用。为了描述进程的家族关系，进程的家族关系， 还应设置父进程标识及子进程标识。此还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。外，还可设置用户标识，以指示拥有该进程的用户。 第三章 进 程 管 理 29 2) 处理机状态处理机状态 处理机状态信息主要是由处理机的各种寄存器中的内容处理机状态信息主要是由处理机的各种寄存器中的内容组成的。组成的。 通用寄存器

28、通用寄存器，又称为用户可视寄存器，它们是用户程序可，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，以访问的，用于暂存信息， 在大多数处理机中，有在大多数处理机中，有 832 个通个通用寄存器，在用寄存器，在RISC结构的计算机中可超过结构的计算机中可超过 100 个；个； 指令计数器指令计数器，其中存放了要访问的下一条指令的地址；，其中存放了要访问的下一条指令的地址； 程序状态字程序状态字PSW，其中含有状态信息，如条件码、执行方，其中含有状态信息，如条件码、执行方式、式、 中断屏蔽标志等；中断屏蔽标志等； 用户栈指针用户栈指针， 指每个用户进程都有一个或若干个与之相关指每个用

29、户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。针指向该栈的栈顶。 第三章 进 程 管 理 30 3) 进程调度信息进程调度信息 在在PCB中还存放一些与进程调度和进程对换有关的信中还存放一些与进程调度和进程对换有关的信息，包括：息，包括： 进程状态进程状态，指明进程的当前状态，指明进程的当前状态， 作为进程调度和对作为进程调度和对换时的依据；换时的依据； 进程优先级进程优先级，用于描述进程使用处理机的优先级别的一，用于描述进程使用处理机的优先级别的一个整数，个整数， 优先级高的进程应优先获

30、得处理机；优先级高的进程应优先获得处理机； 进程调度所需的其它信息进程调度所需的其它信息，它们与所采用的进程调度算，它们与所采用的进程调度算法有关，比如，进程已等待法有关，比如，进程已等待CPU的时间总和、的时间总和、 进程已执进程已执行的时间总和等；行的时间总和等； 事件事件，是指进程由执行状态转变为阻塞状态所等待发生，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。的事件，即阻塞原因。 第三章 进 程 管 理 314) 进程控制信息进程控制信息 程序和数据的地址程序和数据的地址， 是指进程的程序和数据所在的内是指进程的程序和数据所在的内存或外存地存或外存地(首首)址，以便再调

31、度到该进程执行时，能从址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；中找到其程序和数据； 进程同步和通信机制进程同步和通信机制，指实现进程同步和进程通信时必，指实现进程同步和进程通信时必需的机制，需的机制， 如消息队列指针、信号量等，它们可能全部或如消息队列指针、信号量等，它们可能全部或部分地放在部分地放在PCB中；中； 资源清单资源清单，是一张列出了除，是一张列出了除CPU以外的、进程所需的以外的、进程所需的全部资源及已经分配到该进程的资源的清单；全部资源及已经分配到该进程的资源的清单； 链接指针链接指针， 它给出了本进程它给出了本进程(PCB)所在队列中的下一个所在队列中的下

32、一个进程的进程的PCB的首地址。的首地址。 第三章 进 程 管 理 32PCB的存放的存放u有些系统将进程控制块分成两个部分：有些系统将进程控制块分成两个部分： 一部分是进程无论处于什么状态，系统都可能要查一部分是进程无论处于什么状态，系统都可能要查询和处理的询和处理的 PCB 成员，这部分就要常驻内存；成员，这部分就要常驻内存； 另一部分是进程不在执行时系统就不需要访问的另一部分是进程不在执行时系统就不需要访问的 PCB成员，在内存紧张时可以将它们换到盘交换区，成员，在内存紧张时可以将它们换到盘交换区，以为其他进程腾出宝贵的内存空间。以为其他进程腾出宝贵的内存空间。u在在UNIX中，常驻内存

33、的进程中，常驻内存的进程PCB部分是部分是proc结构；结构；u在在UNIX中，非常驻内存的中，非常驻内存的 PCB 部分是进程扩充控制部分是进程扩充控制块块 user 结构；结构；第三章 进 程 管 理 333. 进程控制块的组织方式进程控制块的组织方式 u早期的早期的UNIX系统将进程的系统将进程的proc结构组成一个顺序存放的结构组成一个顺序存放的线性表线性表，系统中可以存在的最大进程数受表的大小的限制，系统中可以存在的最大进程数受表的大小的限制（如（如50个）。当要对处于某种状态的进程控制或调度时，个）。当要对处于某种状态的进程控制或调度时，就要扫描整个就要扫描整个proc表，这大大地

34、降低了系统的效率。表，这大大地降低了系统的效率。u系统系统 V 用用链式方式链式方式组织组织 PCB 队列，不同状态的进程链接队列，不同状态的进程链接成就绪队列、阻塞队列等不同的队列。为了便于系统的调成就绪队列、阻塞队列等不同的队列。为了便于系统的调度和控制，对于就绪状态进程，还可以将其分成优先级不度和控制，对于就绪状态进程，还可以将其分成优先级不同的几个就绪队列。对于阻塞进程，可根据原因不同，组同的几个就绪队列。对于阻塞进程，可根据原因不同，组成若干个队列。成若干个队列。第三章 进 程 管 理 34第三章 进 程 管 理 353.3 3.3 调度调度 3.3.1 调度概述调度概述1. 高级调

35、度高级调度(High Scheduling) 又称为作业调度或长程调度，用于决定把外存上处于又称为作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。因此有时也把作业调度称为接纳调度。在每次准备执行。因此有时也把作业调度称为接纳调度。在每次执行作业调度时，都须做出以下两个决定。执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业接纳多少个作业 ，取决于多道程序度。，取决于多道程序度。 2

36、) 接纳哪些作业接纳哪些作业 ，取决于调度算法，取决于调度算法第三章 进 程 管 理 362. 中级调度中级调度(Intermediate-Level Scheduling) u又称中程调度，它决定处于交换区中的就绪进程中哪一又称中程调度，它决定处于交换区中的就绪进程中哪一个可以调入内存，以便直接参与对个可以调入内存，以便直接参与对CPU的竞争。的竞争。u在内存资源紧张时，为了将进程调入内存，必须将内存在内存资源紧张时，为了将进程调入内存，必须将内存中处于阻塞状态的进程调至交换区，以便为调入进程腾出中处于阻塞状态的进程调至交换区，以便为调入进程腾出空间。空间。u这相当于使处于内存中的进程和处于

37、盘交换区中的进程这相当于使处于内存中的进程和处于盘交换区中的进程交换了位置，故中级调度又称为交换了位置，故中级调度又称为“对换调度对换调度”。u中级调度是为了缓解内存资源的紧张状态，在多道程序中级调度是为了缓解内存资源的紧张状态，在多道程序范畴内实现进程动态覆盖和进程级的虚拟存储器技术。范畴内实现进程动态覆盖和进程级的虚拟存储器技术。u一个进程在其运行期间可能需要经过多次中级调度。一个进程在其运行期间可能需要经过多次中级调度。第三章 进 程 管 理 373. 低级调度低级调度(Low Level Scheduling) （进程调度或短程调度）（进程调度或短程调度） 它决定驻在内存中的哪一个就绪

38、进程可以占用它决定驻在内存中的哪一个就绪进程可以占用CPU，使，使其获得实实在在的执行权力，故低级调度又可称其获得实实在在的执行权力，故低级调度又可称处理机调度处理机调度或分派调度。低级调度执行频度很高，调度算法也比较复杂，或分派调度。低级调度执行频度很高，调度算法也比较复杂，是操作系统中最活跃、最重要的调度程序，对系统的性能影是操作系统中最活跃、最重要的调度程序，对系统的性能影响也最大。响也最大。第三章 进 程 管 理 38第三章 进 程 管 理 393.3.2 进程调度策略进程调度策略u进程调度策略是指进程调度策略是指在什么情况下用什么方式在什么情况下用什么方式，在内，在内存中的就绪进程之

39、间进行切换和分配处理机。存中的就绪进程之间进行切换和分配处理机。u进程切换的方式进程切换的方式有两种：有两种：u一种是一种是不可剥夺（或不可抢占）方式不可剥夺（或不可抢占）方式，即一个进程，即一个进程在获得处理机后，除非因运行结束或进入了阻塞状在获得处理机后，除非因运行结束或进入了阻塞状态等原因自己放弃处理机，否则就可以一直运行下态等原因自己放弃处理机，否则就可以一直运行下去，不会被其他进程抢占处理机；去，不会被其他进程抢占处理机；u另一种是另一种是可剥夺方式可剥夺方式，即在某些条件下系统可以强，即在某些条件下系统可以强制剥夺正在运行中进程使用处理机的权利，将其分制剥夺正在运行中进程使用处理机

40、的权利，将其分配给系统中另一个合适的就绪进程配给系统中另一个合适的就绪进程第三章 进 程 管 理 40 在设计一个调度算法时，应考虑以下的因素。在设计一个调度算法时，应考虑以下的因素。u 针对不同的系统针对不同的系统应当考虑不同的设计目标。如应当考虑不同的设计目标。如对于批处理系统应当以提高计算机系统的运行效对于批处理系统应当以提高计算机系统的运行效率、取得最大的作业吞吐量和减少作业平均周转率、取得最大的作业吞吐量和减少作业平均周转时间为主要目标；对于交互式分时系统，应当以时间为主要目标；对于交互式分时系统，应当以能及时响应用户的请求为主要目标；对于实时系能及时响应用户的请求为主要目标；对于实

41、时系统，应当能对紧急事件做出及时处理和安全可靠统，应当能对紧急事件做出及时处理和安全可靠为头等重要的考虑因素。为头等重要的考虑因素。u 调度算法应能调度算法应能充分使用系统中各种类型的资源充分使用系统中各种类型的资源，使多个设备能并行地工作使多个设备能并行地工作第三章 进 程 管 理 41u 应当既能在某一原则下应当既能在某一原则下公平公平地对待系统中的地对待系统中的各个进程，使它们能均衡地使用处理机，也能各个进程，使它们能均衡地使用处理机，也能考虑不同类型进程具有不同的优先权利，在一考虑不同类型进程具有不同的优先权利，在一定程度下满足用户对优先级的要求，但也不能定程度下满足用户对优先级的要求

42、，但也不能造成某些低优先权的进程可能无限期地推迟任造成某些低优先权的进程可能无限期地推迟任务完成的时间。务完成的时间。u 合理的合理的系统开销系统开销第三章 进 程 管 理 423.3.3 3.3.3 进程调度算法进程调度算法 在在OS中调度的实质是一种资源分配，因而调度算法是中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。指：根据系统的资源分配策略所规定的资源分配算法。 对于不同的系统和系统目标，通常采用不同的调度算对于不同的系统和系统目标，通常采用不同的调度算法。法。 目前存在的多种调度算法中，有的算法适用于作业调目前存在的多种调度算法中，有的算法

43、适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可用度，有的算法适用于进程调度；但也有些调度算法既可用于作业调度，也可用于进程调度。于作业调度，也可用于进程调度。第三章 进 程 管 理 431. 先来先服务调度算法先来先服务调度算法 （ FCFS-First Come First Serve ） 按照作业进入系统的按照作业进入系统的先后次序先后次序进行调度，先进入进行调度，先进入系统者先调度；即启动等待时间最长的作业。系统者先调度；即启动等待时间最长的作业。l优点：实现优点：实现简单简单、公平公平l缺点：没考虑资源利用率和作业的特殊性，对短缺点：没考虑资源利用率和作业的特殊性，对短作

44、业不公平。作业不公平。第三章 进 程 管 理 44先来先服务调度算法先来先服务调度算法带权周转时间周转时间带权周转时间周转时间/请求服务时间请求服务时间第三章 进 程 管 理 45短作业短作业(进程进程)优先调度算法优先调度算法 短作业短作业(进程进程)优先调度算法优先调度算法SJ(P)F，是指对短作业，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先和进程调度。短作业优先(SJF)的调度算法，是从后备队的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它列中选择一个或若干个估计运行时间最短的作

45、业，将它们调入内存运行。而短进程优先们调入内存运行。而短进程优先(SPF)调度算法，则是从调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。事件而被阻塞放弃处理机时，再重新调度。第三章 进 程 管 理 46第三章 进 程 管 理 47 SJ(P)F调度算法也存在不容忽视的调度算法也存在不容忽视的缺点缺点： (1) 该算法对长作业不利该算法对长作业不利，如作业，如作业C的周转时间由的周转时间由10增增至

46、至16，其带权周转时间由，其带权周转时间由2增至增至3.1。更严重的是，如果有。更严重的是，如果有一长作业一长作业(进程进程)进入系统的后备队列进入系统的后备队列(就绪队列就绪队列)，由于调度，由于调度程序总是优先调度那些程序总是优先调度那些(即使是后进来的即使是后进来的)短作业短作业(进程进程)，将，将导致长作业导致长作业(进程进程)长期不被调度。长期不被调度。 (2) 该算法完全未考虑作业的紧迫程度该算法完全未考虑作业的紧迫程度，因而不能保证，因而不能保证紧迫性作业紧迫性作业(进程进程)会被及时处理。会被及时处理。 (3) 由于由于作业作业(进程进程)的长短只是根据用户所提供的估计的长短只

47、是根据用户所提供的估计执行时间而定执行时间而定的，而用户又可能会有意或无意地缩短其作的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。优先调度。 第三章 进 程 管 理 48 2. 时间片轮转法时间片轮转法 在早期的时间片轮转法中，系统将所有的就绪进程按先在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把来先服务的原则，排成一个队列，每次调度时，把CPU分分配给队首进程，并令其执行一个时间片。时间片的大小从几配给队首进程，并令其执行一个时间片。时间片的大小

48、从几ms到几百到几百ms。当执行的时间片用完时，由一个计时器发出。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。获得一时间片的处理机执行时间。第三章 进 程 管

49、理 49u时间片轮转法比较适合于时间片轮转法比较适合于交互式的分时系统交互式的分时系统，对，对于用户输入的每一条命令，系统能保证在一个不于用户输入的每一条命令，系统能保证在一个不太长的时间内对此做出响应。太长的时间内对此做出响应。u时间片轮转法是时间片轮转法是剥夺式调度算法剥夺式调度算法，因此系统需要，因此系统需要花费额外开销用于各个就绪进程间的切换。花费额外开销用于各个就绪进程间的切换。u系统的效率与时间片大小的设置有关系统的效率与时间片大小的设置有关。如时间片。如时间片设置过大，系统与用户间的交互性就差，会招致设置过大，系统与用户间的交互性就差，会招致用户的埋怨；如时间片设置太小，进程间切

50、换过用户的埋怨；如时间片设置太小，进程间切换过分频繁，系统开销就增大。分频繁，系统开销就增大。第三章 进 程 管 理 50u为了适应不同进程的运行特点，在系统中可设置为了适应不同进程的运行特点，在系统中可设置时间片大小不同的时间片大小不同的n个队列，如时间片长度可分为个队列，如时间片长度可分为10ms、50ms和和200ms等。等。u调度程序可将运行时间短、交互性强或调度程序可将运行时间短、交互性强或I/O繁忙的繁忙的进程安排在时间片小的队列，这样可以提高系统进程安排在时间片小的队列，这样可以提高系统的响应速度和减少周转时间的响应速度和减少周转时间u而对于需要连续占用处理机的进程可安排在时间而

51、对于需要连续占用处理机的进程可安排在时间片长的队列中，这样可减少进程切换的开销。片长的队列中，这样可减少进程切换的开销。u一个进程处于哪一个时间片的队列，可以在运行一个进程处于哪一个时间片的队列，可以在运行时根据它的先前运行状况加以调整。时根据它的先前运行状况加以调整。第三章 进 程 管 理 513. 优先级调度算法优先级调度算法 为了照顾紧迫型作业，使之在进入系统后便获为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权（得优先处理，引入了最高优先权（FPF）调度算法。）调度算法。 当把该算法用于作业调度时，系统将从后备队当把该算法用于作业调度时，系统将从后备队列中选择若干个

52、优先权最高的作业，装入内存。当列中选择若干个优先权最高的作业，装入内存。当用于进程调度时，该算法是把处理机分配给就绪队用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程。列中优先权最高的进程。 第三章 进 程 管 理 52 对于优先权调度算法，其关键在于：它是使用对于优先权调度算法，其关键在于：它是使用静态优先静态优先权权、还是、还是动态优先权动态优先权，以及，以及如何确定进程的优先权如何确定进程的优先权。 1) 静态优先权静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一

53、个行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，整数来表示的，例如，07或或0255中的某一整数，中的某一整数， 又把该又把该整数称为优先数。只是具体用法各异：有的系统用整数称为优先数。只是具体用法各异：有的系统用“0”表示表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。恰相反。 第三章 进 程 管 理 53确定进程优先权的依据有如下几个方面：确定进程优先权的依据有如下几个方面： 系统进程执行和完成的是系统功能，应当赋予它们比用系统进程执行和完成的是系统功能，应当赋予它们比用户进程高的优先级。户进程高

54、的优先级。 短作业的进程可以赋予较高的优先级，这样可减少作业短作业的进程可以赋予较高的优先级，这样可减少作业的平均等待时间，提高系统的吞吐量。的平均等待时间，提高系统的吞吐量。 I/O繁忙的进程只要求较短的处理机时间，让该类进程繁忙的进程只要求较短的处理机时间，让该类进程优先获得优先获得CPU。 根据用户作业的申请，系统可以分配一些进程较高的优根据用户作业的申请，系统可以分配一些进程较高的优先级，一般这意味着要提高收费标准。先级，一般这意味着要提高收费标准。 静态优先权法也很适合于实时系统，因为在实时系统静态优先权法也很适合于实时系统，因为在实时系统中计算机所处理的所有事件是预知的，故其优先级

55、可根中计算机所处理的所有事件是预知的，故其优先级可根据事件的紧迫程度事先设定据事件的紧迫程度事先设定第三章 进 程 管 理 54 2) 动态优先权动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的以随进程的推进或随其等待时间的增加而改变的，以便获得，以便获得更好的调度性能。更好的调度性能。 例如，我们可以规定，在就绪队列中的进程，随其等待时例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率间的增长，其优先权以速率a提高。提高。 当采用抢占式优先权调度算法时，如果再规定当前

56、进程当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率的优先权以速率b下降，则可防止一个长作业长期地垄断处理下降，则可防止一个长作业长期地垄断处理机。机。 第三章 进 程 管 理 554. 多级反馈队列调度算法多级反馈队列调度算法 u多级反馈队列算法是时间片轮转算法和优先级算法的多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：综合和发展。优点： 为提高系统吞吐量和缩短平均周转时间而照顾短进为提高系统吞吐量和缩短平均周转时间而照顾短进程程 为获得较好的为获得较好的I/O设备利用率和缩短响应时间而照设备利用率和缩短响应时间而照顾顾I/O型进程型进程 不必估计进程的执行时

57、间，动态调节不必估计进程的执行时间，动态调节第三章 进 程 管 理 564. 多级反馈队列调度算法多级反馈队列调度算法 (1) 应设置多个就绪队列，并为各个队列赋予不同的优应设置多个就绪队列，并为各个队列赋予不同的优先级。先级。 第一个队列的优先级最高，第二个队列次之，其余第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，行时间片的大小也各不相同，在优先权愈高的队列中，为在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小每个进程所规定的执行时间片就愈小。例如，第二个队列

58、。例如，第二个队列的时间片要比第一个队列的时间片长一倍，的时间片要比第一个队列的时间片长一倍，第，第i+1个个队列的时间片要比第队列的时间片要比第i个队列的时间片长一倍。个队列的时间片长一倍。第三章 进 程 管 理 57第三章 进 程 管 理 58 (2) 当一个新进程进入内存后，首先将它放入第一队列当一个新进程进入内存后，首先将它放入第一队列的末尾，按的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第

59、一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按二队列的末尾，再同样地按FCFS原则等待调度执行；如果原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，放入第三队列，如此下去，当一个长作业，如此下去，当一个长作业(进程进程)从第从第一队列依次降到第一队列依次降到第n队列后，在第队列后，在第n队列中便采取按时间片队列中便采取按时间片轮转的方式运行。轮转的方式运行。 第三章 进 程 管 理 59 (3) 仅当第一队列空闲时，调度程序才调度第二队列仅当第一队列空闲时，调度程序才调度第二队列

60、中的进程运行；中的进程运行； 仅当第仅当第1(i-1) 队列均空时，才会调度第队列均空时，才会调度第i队列中的进程运行。如果处理机正在第队列中的进程运行。如果处理机正在第i队列中为某进程队列中为某进程服务时，又有新进程进入优先权较高的队列服务时，又有新进程进入优先权较高的队列(第第1(i-1)中中的任何一个队列的任何一个队列)，则此时新进程将抢占正在运行进程的，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第处理机，即由调度程序把正在运行的进程放回到第i队列队列的末尾，把处理机分配给新到的高优先权进程。的末尾，把处理机分配给新到的高优先权进程。 第三章 进 程 管