第3章处理机管理

1、第第3 3章章 处理机管理处理机管理本章学习目标本章学习目标在多道程序环境下，程序不能独立运行。作为资源分配和在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的。所以，本章的主要问题是：于进程而体现的。所以，本章的主要问题是： 进程的概念进程的概念进程的实体、状态及状态的演变进程的实体、状态及状态的演变进程的控制与调度进程的控制与调度进程之间的关系进程之间的关系进程的通信进程的通信线程线程死锁问题及解决死锁问题及解决返回本章首页返回本章首页第第3章章 处理机管理处理机管理第第3 3

2、章章 处理机管理处理机管理3.1 进程的定义和特征进程的定义和特征 3.1.1 3.1.1 进程的引入进程的引入3.1.2 3.1.2 进程的定义进程的定义3.1.3 3.1.3 进程的进程的特征特征返回本章首页返回本章首页第第3 3章章 处理机管理处理机管理3.1.1 进程的引入进程的引入 在多道程序系统中，程序并不能独立运行。独立在多道程序系统中，程序并不能独立运行。独立运行和资源分配的基本单位是进程。用进程的观点运行和资源分配的基本单位是进程。用进程的观点来研究操作系统，可深入地了解和把握系统内部的来研究操作系统，可深入地了解和把握系统内部的动态活动，这就是所谓研究操作系统进程的观点。动

3、态活动，这就是所谓研究操作系统进程的观点。 进程也是对操作系统进行设计的一个重要概念。进程也是对操作系统进行设计的一个重要概念。 下一页下一页第第3 3章章 处理机管理处理机管理3.1.1 进程的引入进程的引入1程序的顺序执行及其特性程序的顺序执行及其特性2程序的并发执行和资源共享程序的并发执行和资源共享3程序的并发执行特性程序的并发执行特性 下一页下一页第第3 3章章 处理机管理处理机管理 一个程序由若干个程序段组成，而这些程序段的一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。的顺序执行。 例

4、如：例如： 下一页下一页I1P1O1I2P2O21程序的顺序执行及其特性程序的顺序执行及其特性第第3 3章章 处理机管理处理机管理1.1.顺序性顺序性 处理机严格按照程序所规定的顺序执行，即每个操处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。作必须在下一个操作开始之前结束。2. 2. 资源独占资源独占 程序在执行过程中独占全机资源，资源状态的改变程序在执行过程中独占全机资源，资源状态的改变只与本程序有关而与外界环境无关。只与本程序有关而与外界环境无关。3. 3. 结果无关性结果无关性 程序执行的结果与初始条件有关，而与执行速度无程序执行的结果与初始条件有关，而与执

5、行速度无关。即只要程序的初始条件相同，它的执行结果是相关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行同的，不论它在什么时间执行，也不管计算机的运行速度。速度。第第3 3章章 处理机管理处理机管理 顺序程序以上的执行特性可归结为顺序程序以上的执行特性可归结为封闭性封闭性和和可再现性可再现性。 所谓所谓封闭性封闭性就是指程序一旦运行，就不受外就是指程序一旦运行，就不受外界环境的影响，其运行结果与环境以外的事情界环境的影响，其运行结果与环境以外的事情无关；无关； 所谓所谓可再现性可再现性就是指程序重复运行时，只要就是指程序重复运行时，只要初始条件相同，必

6、将获得相同的结果。初始条件相同，必将获得相同的结果。第第3 3章章 处理机管理处理机管理图3.2 程序的并发执行有向图 下一页下一页P3I11I2I3 3I4 4P1 1P2P4 4o1 o2 2o3 3o4 42程序的并发执行和资源共享程序的并发执行和资源共享第第3 3章章 处理机管理处理机管理3程序的并发执行特性程序的并发执行特性 无论是操作系统自身的程序还是用户程序，通常无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并发执行的程序总是存在一些相对独立、但又能并发执行的程序段。由于这些程序段可以被多个用户作业调用，段。由于这些程序段可以被多个用户作业调用，因此可在同

7、一时间间隔内发生。这样一来，某个因此可在同一时间间隔内发生。这样一来，某个程序段可能对应多个程序段可能对应多个“计算计算”，于是程序与，于是程序与“计计算算”已不具有一一对应关系了。这些已不具有一一对应关系了。这些“并发程序并发程序”就构成了一个就构成了一个“并发环境并发环境”。下一页下一页第第3 3章章 处理机管理处理机管理程序并发执行特征：程序并发执行特征：（1 1）失去封闭性）失去封闭性 例：观察者例：观察者/ /报告者报告者 (2) (2) 程序和机器执行程序的活动不再一一程序和机器执行程序的活动不再一一 对应对应 (3) 并发程序间的相互制约并发程序间的相互制约 第第3 3章章 处理

8、机管理处理机管理观察者：观察者： 报告者：报告者：begin beginbegin begin repeat repeat repeat repeat wait a car go through deley a time wait a car go through deley a time N=N+1N=N+1； Print N Print N ； N=0 N=0 ； until until until untilend endend end初始初始N=nN=n时不同执行序列：时不同执行序列： N=N+1N=N+1； Print N Print N； Print N Print N ； Pri

9、nt N Print N ； N=0 N=0 ； N=N+1 N=N+1 ； N=0 N=0 ； N=N+1 N=N+1 ； N=0 N=0 ；结果各不相同结果各不相同: : 打印打印n+1n+1，N=0N=0； 打印打印n n，N=1N=1； 打印打印n n，N=0N=0；第第3 3章章 处理机管理处理机管理 资源共享是现代操作系统的另一基本特性。所谓资源共享是资源共享是现代操作系统的另一基本特性。所谓资源共享是指系统中的硬件资源和软件资源不再为单个用户程序所独占，指系统中的硬件资源和软件资源不再为单个用户程序所独占，而由几道用户程序共同使用。这样，这些资源的状态不再取决而由几道用户程序共同

10、使用。这样，这些资源的状态不再取决于一道程序，而是由多道程序的活动所决定。这就从根本上打于一道程序，而是由多道程序的活动所决定。这就从根本上打破了一道程序封闭于一个系统中执行的局面。破了一道程序封闭于一个系统中执行的局面。 程序并发执行和资源共享之间互为依存条件。一方面，资程序并发执行和资源共享之间互为依存条件。一方面，资源共享是以程序并发执行为条件的，因为若系统不允许程序并源共享是以程序并发执行为条件的，因为若系统不允许程序并发，也就不存在资源共享问题；另一方面，若系统不能对共享发，也就不存在资源共享问题；另一方面，若系统不能对共享资源进行有效管理，也就降低了程序并发执行的效果。资源进行有效

11、管理，也就降低了程序并发执行的效果。 第第3 3章章 处理机管理处理机管理程序的制约方式有如下两种程序的制约方式有如下两种 ：（1）间接制约方式。）间接制约方式。这是由于竞争相同资源而引起的，得到资源的程序段可以投这是由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行用资源时再继续运行 。（2）直接制约方式。）直接制约方式。这通常是在那些逻辑上相关的程序段之间发生的。一般是由这通常是在那些逻辑上相关的程序段之间发生的。一般是由于各种程序段要求共享信息引起的于各种程序段要求共享

12、信息引起的 。如。如, ,进程之间的合作进程之间的合作第第3 3章章 处理机管理处理机管理由于程序在并发执行时，各次执行的结果不同，所以用由于程序在并发执行时，各次执行的结果不同，所以用“程序程序”这个概念已无法描述程序的并发执行，所以必须这个概念已无法描述程序的并发执行，所以必须引入新的概念引入新的概念进程来描述程序的并发执行。进程这一进程来描述程序的并发执行。进程这一术语最早由麻省理工学院著名的操作系统术语最早由麻省理工学院著名的操作系统MULTICSMULTICS中提出。中提出。 进程定义：进程定义：“可并发执行的程序在一个数据集合上的运可并发执行的程序在一个数据集合上的运行过程行过程”

13、。(1) (1) 进程是程序的一次执行。进程是程序的一次执行。(2) (2) 进程是可以和别的计算并发执行的计算。进程是可以和别的计算并发执行的计算。(3) (3) 进程是一个具有一定独立功能的程序在某个数据集上进程是一个具有一定独立功能的程序在某个数据集上的一次执行活动，它可以和同样的其它程序共行。的一次执行活动，它可以和同样的其它程序共行。(4) (4) 进程是一个程序及数据在处理机上顺序执行时所发生进程是一个程序及数据在处理机上顺序执行时所发生的活动。的活动。(5) (5) 进程是程序在一个数据集上的运行过程，是系统可调进程是程序在一个数据集上的运行过程，是系统可调度的实体。度的实体。第

14、第3 3章章 处理机管理处理机管理3.1.3 3.1.3 进程的特征进程的特征 进程的特征进程的特征: :动态性：动态性：动态性是进程的最基本特征，它是程序执行过动态性是进程的最基本特征，它是程序执行过程，它是有一定的生命期。它由创建而产生、由调度而程，它是有一定的生命期。它由创建而产生、由调度而执行，因得不到资源而暂仃，并由撤消而死亡。而程序执行，因得不到资源而暂仃，并由撤消而死亡。而程序是静态的，它是存放在介质上一组有序指令的集合，无是静态的，它是存放在介质上一组有序指令的集合，无运动的含义。运动的含义。第第3 3章章 处理机管理处理机管理并发性：并发性：并发性是进程的重要特征，同时也是并

15、发性是进程的重要特征，同时也是OSOS的重要特的重要特征。并发性指多个进程实体同存于内存中，能在一段时间征。并发性指多个进程实体同存于内存中，能在一段时间内同时运行。而程序是不能并发执行。内同时运行。而程序是不能并发执行。独立性：独立性：进程是一个能独立运行的基本单位，即是一个独进程是一个能独立运行的基本单位，即是一个独立获得资源和独立调度的单位，而程序不作为独立单位参立获得资源和独立调度的单位，而程序不作为独立单位参加运行。加运行。异步性：异步性：进程按各自独立的不可预知的速度向前推进，即进程按各自独立的不可预知的速度向前推进，即进程按异步方式进行，正是这一特征，将导致程序执行的进程按异步方

16、式进行，正是这一特征，将导致程序执行的不可再现性，因此不可再现性，因此OSOS必须采用某种措施来限制各进程推进必须采用某种措施来限制各进程推进序列以保证各程序间正常协调运行。序列以保证各程序间正常协调运行。结构特征：结构特征：从结构上，进程实体由程序段、数据段和进程从结构上，进程实体由程序段、数据段和进程控制块三部分组成，控制块三部分组成，UNIXUNIX中称为中称为“进程映象进程映象”。第第3 3章章 处理机管理处理机管理3.2 进程的描述进程的描述 返回本章首页返回本章首页3.2.1 3.2.1 进程的表示进程的表示3.2.2 3.2.2 进程的基本调度状态及其转换进程的基本调度状态及其转

17、换 第第3 3章章 处理机管理处理机管理 进程组成：进程组成： 程序程序 + + 数据数据 + + PCBPCB 进程控制块进程控制块 （PCBPCBProcess Control BlockProcess Control Block） 进程与进程与PCBPCB是一一对应的是一一对应的 为了刻画进程的动态变化，通常把进程表示为由程序为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成。程序部分描述进程本段、私有数据块和进程控制块组成。程序部分描述进程本身所要完成的功能，而身所要完成的功能，而“私有数据块私有数据块”是接受程序规定操是接受程序规定操作的一组存储单元的内容，

18、是操作的对象。进程控制块是作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系统时（运行），进在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个进程程控制块就标识了这个进程 下一页下一页3.2.1 3.2.1 进程的表示进程的表示第第3 3章章 处理机管理处理机管理在进程控制块中，主要包含下列在进程控制块中，主要包含下列4 4方面的信息。方面的信息。1) 1) 进程标识符进程标识符这是用来唯一标识一个进程的信息。通常有以下两种标识符。这是用来唯一标识一个进程的信息。通常有以下两种标识符。(1) (1) 外部标识符。这由进程创建者提供，通常由字

19、母、数字组成。外部标识符。这由进程创建者提供，通常由字母、数字组成。外部标识符便于记忆，如计算进程、打印进程等，以便用户外部标识符便于记忆，如计算进程、打印进程等，以便用户( (进程进程) )访问该进程时使用。访问该进程时使用。(2) (2) 内部标识符。在所有操作系统中都为每一进程赋予一个唯一内部标识符。在所有操作系统中都为每一进程赋予一个唯一的整数，作为进程的内部标识符。的整数，作为进程的内部标识符。2) 2) 处理机状态信息处理机状态信息这是指一个原在执行的进程，因某种原因而被暂停执行瞬间的处这是指一个原在执行的进程，因某种原因而被暂停执行瞬间的处理机映象。其中包括：理机映象。其中包括：

20、(1) 通用寄存器信息。通用寄存器信息。 （2） 指令计数器信息指令计数器信息(3) (3) 程序状态字程序状态字PSW PSW (4) (4) 用户栈指针。用户栈指针。第第3 3章章 处理机管理处理机管理3) 3) 进程的调度信息进程的调度信息这主要是指与进程调度和进程对换有关的信息，包括以下这主要是指与进程调度和进程对换有关的信息，包括以下4 4点。点。(1) (1) 进程状态。指明进程当前所处的状态，如就绪、阻塞等。这进程状态。指明进程当前所处的状态，如就绪、阻塞等。这是调度进程或进程对换的依据。是调度进程或进程对换的依据。(2) (2) 进程优先级。用于描述进程使用处理机的优先级别，一

21、般用进程优先级。用于描述进程使用处理机的优先级别，一般用优先数来表示。优先级高的进程可优先获得处理机。优先数来表示。优先级高的进程可优先获得处理机。(3) (3) 其它调度信息。如进程已等待其它调度信息。如进程已等待CPUCPU的时间总和、进程已执行的时间总和、进程已执行的时间总和等，这与所采用的进程调度算法有关。的时间总和等，这与所采用的进程调度算法有关。(4) (4) 事件。这是指进程由执行状态转变为阻塞状态所等待发生的事件。这是指进程由执行状态转变为阻塞状态所等待发生的事件，也就是阻塞的原因。事件，也就是阻塞的原因。第第3 3章章 处理机管理处理机管理4) 4) 进程控制信息进程控制信息

22、(1) (1) 程序和数据集的地址。它是指该进程实体中程序和数据集所程序和数据集的地址。它是指该进程实体中程序和数据集所在的存储地址在的存储地址( (内存或外存内存或外存) )，以便当调度到该进程时，能定位到，以便当调度到该进程时，能定位到其程序和数据。其程序和数据。(2) (2) 同步和通信机制。它是指实现进程同步和进程通信时所必须同步和通信机制。它是指实现进程同步和进程通信时所必须的机制，如消息队列指针、信号量等，这些信息可能全部或部分的机制，如消息队列指针、信号量等，这些信息可能全部或部分存放于存放于PCBPCB中。中。(3) (3) 链接指针。为了有效地管理所有进程，在系统中要组成各种

23、链接指针。为了有效地管理所有进程，在系统中要组成各种进程队列，以及在有些操作系统中，采用树结构方式来管理进程，进程队列，以及在有些操作系统中，采用树结构方式来管理进程，这都需要有相应的链接指针。这都需要有相应的链接指针。(4) (4) 资源清单。这是一张列出除资源清单。这是一张列出除CPUCPU以外的，进程所需的全部资以外的，进程所需的全部资源及已经分配到资源的清单。源及已经分配到资源的清单。第第3 3章章 处理机管理处理机管理下一页下一页第第3 3章章 处理机管理处理机管理 进程控制块是进程存在的标志，当系统或父进进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一

24、个进程创建一个进程时，实际上就是为其建立一个进程控制块。程控制块。 进程控制块既能标识进程的存在，又能刻画出进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真进程的动态特征，它是一个进程仅有的被系统真正感知的部分。正感知的部分。进程控制块的作用：进程控制块的作用：返回本节目录返回本节目录第第3 3章章 处理机管理处理机管理PCBPCB的组织形式的组织形式PCBPCB组织的目标：便于调度和管理进程组织的目标：便于调度和管理进程 方法有三：方法有三： （1 1）线性表：简单，但进程多时查找速度慢！）线性表：简单，但进程多时查找速度慢！ （2 2）索引表：相同状态的进

25、程）索引表：相同状态的进程PCBPCB组织在同一张表格中，组织在同一张表格中，如就绪进程索引表，阻塞进程索引表如就绪进程索引表，阻塞进程索引表 （3 3）链接表：相同状态的进程）链接表：相同状态的进程PCBPCB按优先数排成一个或多按优先数排成一个或多个队列，如就绪队列，不同事件的阻塞队列个队列，如就绪队列，不同事件的阻塞队列第第3 3章章 处理机管理处理机管理 PCB1 ReadyPCB1 Ready就绪表就绪表 PCB2 BlockedPCB2 Blocked就绪表起始地址就绪表起始地址 PCB3 RunningPCB3 Running PCB4 BlockedPCB4 Blocked某阻

26、塞表某阻塞表 PCB5 ReadyPCB5 Ready某阻塞表起始地址某阻塞表起始地址 PCB6 ReadyPCB6 Ready第第3 3章章 处理机管理处理机管理第第3 3章章 处理机管理处理机管理3.2.2 进程的基本调度状态及其转换进程的基本调度状态及其转换 （1）运行状态：进程正在处理机上运行的状态，该进程）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用户程序正在处理已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。机上运行。（2）阻塞状态：进程等待某种事件完成（例如，等待输）阻塞状态：进程等待某种事件完成（例如，等待输入入/输出操作的完成）

27、而暂时不能运行的状态，处于该状输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。机，它也不能运行。（3）就绪状态：该进程运行所需的一切条件都得到满足，）就绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入而必须等待分配处理机资源，一旦获得处理机就立即投入运行。运行。下一页下一页第第3 3章章 处理机管理处理机管理下一页下一页 第第3 3

28、章章 处理机管理处理机管理三个基本状态之间可能转换和转换原因如下：三个基本状态之间可能转换和转换原因如下： 就绪态就绪态运行态：当处理机空闲时，进程调度程序必将运行态：当处理机空闲时，进程调度程序必将处理机分配给一个处于就绪态的进程处理机分配给一个处于就绪态的进程 ，该进程便由就绪态转换，该进程便由就绪态转换为运行态。为运行态。 运行态运行态阻塞态：处于运行态进程在运行过程中需要等阻塞态：处于运行态进程在运行过程中需要等待某一事件发生后（例如因待某一事件发生后（例如因I IO O请求等待请求等待I IO O完成后），才能完成后），才能继续运行，则该进程放弃处理机，从运行态转换为阻塞态。继续运行

29、，则该进程放弃处理机，从运行态转换为阻塞态。 阻塞态阻塞态就绪态：处于阻塞态的进程，若其等待的事件就绪态：处于阻塞态的进程，若其等待的事件已经发生，于是进程由阻塞态转换为就绪态。已经发生，于是进程由阻塞态转换为就绪态。 运行态运行态就绪态：处于运行状态的进程在其运行过程中，就绪态：处于运行状态的进程在其运行过程中，因分给它的处理机时间片已用完，而不得不让出（被抢占）处因分给它的处理机时间片已用完，而不得不让出（被抢占）处理机，于是进程由运行态转换为就绪态。理机，于是进程由运行态转换为就绪态。而阻塞态而阻塞态运行态和就绪态运行态和就绪态阻塞态这二种状态转换阻塞态这二种状态转换不可能发生。不可能发

30、生。返回本节目录返回本节目录第第3 3章章 处理机管理处理机管理在一个多道程序设计的系统中，各进程状态转换会互相影在一个多道程序设计的系统中，各进程状态转换会互相影响。例如系统中一个运行态的进程响。例如系统中一个运行态的进程A A发生发生I/OI/O请求后要等待请求后要等待I/OI/O完成，它的状态也由运行态转换为阻塞态，此时进程完成，它的状态也由运行态转换为阻塞态，此时进程调度程序就会按照一定的算法，在就绪队列中选一个进程调度程序就会按照一定的算法，在就绪队列中选一个进程B B，将处理机分给它，该将处理机分给它，该B B进程的状态也由就绪态转换为运进程的状态也由就绪态转换为运行态。如一个进程

31、行态。如一个进程C C等待的事件完成，则它的状态由阻塞等待的事件完成，则它的状态由阻塞态转换为就绪态，它也从阻塞队列中抽出插入就绪队列中。态转换为就绪态，它也从阻塞队列中抽出插入就绪队列中。如进程如进程 C C从阻塞态转换为就绪态时，有一个进程从阻塞态转换为就绪态时，有一个进程D D在在CPUCPU上上运行。而系统采用抢占式调度算法，进程运行。而系统采用抢占式调度算法，进程C C的优先级又高的优先级又高于正在于正在CPUCPU上运行的进程上运行的进程D D的优先级，则要发行抢占调度。的优先级，则要发行抢占调度。即接下去的操作时由进程调度程序将正在运行的进程即接下去的操作时由进程调度程序将正在运

32、行的进程D D由由运行态转换为就绪态，插入就绪队列。运行态转换为就绪态，插入就绪队列。第第3 3章章 处理机管理处理机管理处于运行态进程处于运行态进程: :如系统有一个处理机，则在任何一时刻，如系统有一个处理机，则在任何一时刻，最多只有一个进程处于运行态。最多只有一个进程处于运行态。处于就绪态进程处于就绪态进程: :一般处于就绪态的进程按照一定的算法一般处于就绪态的进程按照一定的算法（如先来的进程排在前面，或采用优先权高的进程排在前（如先来的进程排在前面，或采用优先权高的进程排在前面）排成一个就绪队列。面）排成一个就绪队列。处于阻塞态进程处于阻塞态进程: :处于阻塞态的进程排在阻塞队列中。由处

33、于阻塞态的进程排在阻塞队列中。由于等待事件原因不同，阻塞队列也按事件分成几个队列。于等待事件原因不同，阻塞队列也按事件分成几个队列。第第3 3章章 处理机管理处理机管理例：一个只有一个处理机的系统中，例：一个只有一个处理机的系统中，OSOS的进程有运行、就绪、阻塞三的进程有运行、就绪、阻塞三个基本状态。假如某时刻该系统中有个基本状态。假如某时刻该系统中有1010个进程并发执行，在略去调度个进程并发执行，在略去调度程序所占用时间情况下试问：程序所占用时间情况下试问：这时刻系统中处于运行态的进程数最多有几个？最少这时刻系统中处于运行态的进程数最多有几个？最少有几个？有几个？这时刻系统中处于就绪态的

34、进程数最多有几个？最少这时刻系统中处于就绪态的进程数最多有几个？最少有几个？有几个？这时刻系统中处于阻塞态的进程数最多有几个？最少这时刻系统中处于阻塞态的进程数最多有几个？最少有几个？有几个？解：因为系统中只有一个处理机，所以某时刻处于运行态的进程数最解：因为系统中只有一个处理机，所以某时刻处于运行态的进程数最多只有一个。而最少可能为多只有一个。而最少可能为0 0，此时其它，此时其它1010个进程一定全部排在各阻个进程一定全部排在各阻塞队列中，在就绪队列中没有进程。而某时刻处于就绪态的进程数最塞队列中，在就绪队列中没有进程。而某时刻处于就绪态的进程数最多只有多只有9 9个，不可能出现个，不可能

35、出现1010个情况，因为一旦个情况，因为一旦CPUCPU有空，调度程序马上有空，调度程序马上调度，当然这是在略去调度程序调度时间时考虑。处于阻塞态的进程调度，当然这是在略去调度程序调度时间时考虑。处于阻塞态的进程数最少是数最少是0 0个。个。第第3 3章章 处理机管理处理机管理3.3 进程控制进程控制 3.3.1 原语原语 3.3.2 进程控制原语进程控制原语 返回本章首页返回本章首页第第3 3章章 处理机管理处理机管理3.4.1 原语原语 在操作系统中，某些被进程调用的操作，例如队列操作、在操作系统中，某些被进程调用的操作，例如队列操作、对信号量的操作、检查启动外设等操作，一旦开始执行就不对

36、信号量的操作、检查启动外设等操作，一旦开始执行就不能被中断，否则就会出现操作错误，造成系统混乱。原语就能被中断，否则就会出现操作错误，造成系统混乱。原语就是为实现这些操作而设置的。是为实现这些操作而设置的。 原语（原语（Primitive)Primitive)是由若干条指令组成，用来实现某个是由若干条指令组成，用来实现某个特定的操作，通过一段不可分割的或不可中断的程序实现其特定的操作，通过一段不可分割的或不可中断的程序实现其功能。功能。具有原子性：要么执行，要么不执行具有原子性：要么执行，要么不执行进程通过调用原语实现进程管理！进程通过调用原语实现进程管理！下一页下一页第第3 3章章 处理机管

37、理处理机管理3.3.2 进程控制原语进程控制原语1 1创建原语创建原语2 2撤消原语撤消原语3 3阻塞原语阻塞原语4 4唤醒原语唤醒原语 5. 挂起原语挂起原语 6. 激活原语激活原语返回本节目录返回本节目录新建完成第第3 3章章 处理机管理处理机管理Create:Create:为被建进程建立一个为被建进程建立一个PCBPCB，并初始化并初始化Procedure Create(n,S0,k0,M0,R0) Create(n,S0,k0,M0,R0)begini:= Get Internal Name(n); /n: i:= Get Internal Name(n); /n: 进程外部名进程外部

38、名Id(i) := n;Id(i) := n; /i: PCB /i: PCB内部标示号内部标示号Priority(i) := k0;Priority(i) := k0; /k0: /k0:进程优先数进程优先数Cpustate(i) := S0;Cpustate(i) := S0; /S0:CPU /S0:CPU初始状态初始状态Main Store(i) := M0;Main Store(i) := M0; / /主存初始占有情况主存初始占有情况Resources(i) := R0;Resources(i) := R0; / /其它资源初始占有其它资源初始占有情况情况Status(i) :=

39、Readys;Status(i) := Readys; / /进程初始状态置为挂进程初始状态置为挂起就绪起就绪Parent(i) := CALLER;Parent(i) := CALLER; / /父进程名父进程名Insert(RL,i);Insert(RL,i); / /把把i i插入就绪队列插入就绪队列end第第3 3章章 处理机管理处理机管理Destroy(n):Destroy(n):撤消指定标识符的进撤消指定标识符的进程及其所有子进程程及其所有子进程Procedure Destroy(n)Procedure Destroy(n)beginbeginSched := false;Sche

40、d := false;i:= Search Internal Name(n);i:= Search Internal Name(n); KILL(i);KILL(i);if Sched = true if Sched = true then SCHEDULER; then SCHEDULER; end end 注：注：SchedSched 标志是否需要调用处理机调度程序。标志是否需要调用处理机调度程序。第第3 3章章 处理机管理处理机管理KILL(i):KILL(i):杀死所有属于杀死所有属于i i的子进程并释的子进程并释放所有资源放所有资源 Procedure KILL(i) KILL(i)

41、 begin if Status(i) = Running Status(i) = Running then begin STOP(i); Sched := STOP(i); Sched := true end REMOVE(Queue(i),i); / REMOVE(Queue(i),i); /从进程从进程i i所在的队列中移走进程所在的队列中移走进程i i for all P all P progeny(i) progeny(i) do KILL(P);/ KILL(P);/杀死所有属于杀死所有属于i i的子进程的子进程 for all r all r progeny(i) progeny

42、(i) do /释放进程释放进程i i占用的所有资源占用的所有资源 RELEASE(r);RELEASE(r); RELEASE(PCB(i);RELEASE(PCB(i);end第第3 3章章 处理机管理处理机管理Suspend(n):Suspend(n):挂起外部名为挂起外部名为n n的进程的进程 Procedure Suspend(n) Suspend(n) begini:= Search Internal Name(n);i:= Search Internal Name(n);CASE Status(i)CASE Status(i)Blockeda:Status(i) := Block

43、eds;Blockeda:Status(i) := Blockeds;Readya: Status(i) := Readys; Readya: Status(i) := Readys; Running: Begin Running: Begin STOP(i); / STOP(i); /停止该进程停止该进程i i的运行的运行 SCHEDULER; /CPUSCHEDULER; /CPU调度程序调度程序 endendend第第3 3章章 处理机管理处理机管理Resume(n):Resume(n):激活外部名为激活外部名为n n的已的已挂起进程挂起进程Procedure Resume(n) Res

44、ume(n)begini:= Search Internal Name(n);i:= Search Internal Name(n);if Status(i) = Readys Status(i) = Readys then begin Status(i) = Readya; Status(i) = Readya; SCHEDULER; SCHEDULER; end else Status(i) = Blockeda; Status(i) = Blockeda;end第第3 3章章 处理机管理处理机管理3.4 进程调度进程调度 3.4.1 进程调度的基本概念进程调度的基本概念 3.4.2进程调

45、度进程调度所用的数据结构所用的数据结构3.4.3 进程调度方式进程调度方式 3.4.4进程调度算法进程调度算法 返回本章首页返回本章首页第第3 3章章 处理机管理处理机管理3.4.1 进程调度的基本概念进程调度的基本概念 进程调度程序的职能：进程调度程序的职能：（1）记录系统中所有进程的有关情况。）记录系统中所有进程的有关情况。 （2）确定分配处理机的原则。）确定分配处理机的原则。 （3）分配处理机给进程。）分配处理机给进程。 （4）从进程收回处理机。）从进程收回处理机。 返回本节目录返回本节目录3.4.2 进程调度所用的主要数据结构进程调度所用的主要数据结构 第第3 3章章 处理机管理处理机

46、管理剥夺式剥夺式/ /抢占方式（抢占方式（Preemptive modePreemptive mode） 剥夺式调度是指当系统按照某种原则发现一个比剥夺式调度是指当系统按照某种原则发现一个比正在运行的进程更合适、更应该占用正在运行的进程更合适、更应该占用CPUCPU的进程时，的进程时，系统将强迫处于运行状态的进程将系统将强迫处于运行状态的进程将CPUCPU的使用权交的使用权交给这个更适合的进程。常见的剥夺原则有给这个更适合的进程。常见的剥夺原则有优先权优先权原则、短进程优先原则和时间片原则原则、短进程优先原则和时间片原则。采用剥夺。采用剥夺式调度的系统能够及时处理紧急事件，它反映出式调度的系统

47、能够及时处理紧急事件，它反映出了进程的优先级特征，但这势必会带来较大的系了进程的优先级特征，但这势必会带来较大的系统开销，调度算法也会相对复杂一些。统开销，调度算法也会相对复杂一些。3.4.3 进程调度的方式进程调度的方式第第3 3章章 处理机管理处理机管理非剥夺式非剥夺式/ /非抢占方式非抢占方式 采用这种调度方式时，一旦把处理机分配给某采用这种调度方式时，一旦把处理机分配给某进程后，便让进程一直执行，直到该进程完成或发进程后，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机

48、。决不允许某进程抢占已经分配出去的处理机。 这种调度方式算法简单，系统开销也较小，但它这种调度方式算法简单，系统开销也较小，但它不能反映出进程的优先级特征。不能反映出进程的优先级特征。 第第3 3章章 处理机管理处理机管理 3.4.4 进程调度算法进程调度算法1先来先服务先来先服务First-Come-First-ServedFirst-Come-First-Served （FCFS） 这种调度算法按照进程进入就绪队列的先后顺序这种调度算法按照进程进入就绪队列的先后顺序来调度进程，到达得越早，其优先数越高。获得来调度进程，到达得越早，其优先数越高。获得处理机的进程，未遇到其他情况时，一直运行下

49、处理机的进程，未遇到其他情况时，一直运行下去，系统只需具备一个先进先出的队列，在管理去，系统只需具备一个先进先出的队列，在管理优先数的就绪队列时，这种方法是一种最常见策优先数的就绪队列时，这种方法是一种最常见策略，并且在没有其他信息时，也是一种最合理的略，并且在没有其他信息时，也是一种最合理的策略。策略。下一页下一页第第3 3章章 处理机管理处理机管理2轮转调度轮转调度 先来先服务的一个重要变形，就是轮转规则。轮转调先来先服务的一个重要变形，就是轮转规则。轮转调度算法是系统把所有就绪进程按先后次序排队，处理机总度算法是系统把所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个就绪

50、进程，并分配它一是优先分配给就绪队列中的第一个就绪进程，并分配它一个固定的时间片（如个固定的时间片（如100毫秒）。当该运行进程用完规定毫秒）。当该运行进程用完规定的时间片时，被迫释放处理机给下一个处于就绪队列中的的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，分给这个进程相同的时间片，每个运行完时第一个进程，分给这个进程相同的时间片，每个运行完时间片的进程，当未遇到任何阻塞时，就回到就绪队列的尾间片的进程，当未遇到任何阻塞时，就回到就绪队列的尾部，并等待下次转到它时再投入运行。于是，只要是处于部，并等待下次转到它时再投入运行。于是，只要是处于就绪队列中的进程，按此种算法迟早总可

51、以分得处理机投就绪队列中的进程，按此种算法迟早总可以分得处理机投入运行。入运行。下一页下一页第第3 3章章 处理机管理处理机管理3分级轮转法分级轮转法 所谓分级轮转法就是将先前的一个就绪队列，所谓分级轮转法就是将先前的一个就绪队列，根据进程的优先数不同划分两个或两个以上的就绪根据进程的优先数不同划分两个或两个以上的就绪队列，并赋给每个队列不同的优先数。以两个就绪队列，并赋给每个队列不同的优先数。以两个就绪队列为例，一个具有较高优先数，另一个具有较低队列为例，一个具有较高优先数，另一个具有较低优先数，前者称为前台队列，后者称为后台队列。优先数，前者称为前台队列，后者称为后台队列。 下一页下一页第

52、第3 3章章 处理机管理处理机管理 例如前后台系统可以建立两个就绪队列，批处理作业所例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立的进程进入建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按前台就绪队列。前台采用时间片轮转算法，进程按FCFSFCFS等策等策略排序，后台采用优先权高优先的调度算法或者短作业优先略排序，后台采用优先权高优先的调度算法或者短作业优先的调度算法。的调度算法。 对多级就绪队列调度策略有两种，一种是各就绪队列按对多级就绪队列调度策略有两种，一种是各就绪队列按进程性质赋予不同的优先权，

53、优先权高的就绪队列的进程优进程性质赋予不同的优先权，优先权高的就绪队列的进程优先被调度，例如上例中前台就绪队列的优先权比后台就绪队先被调度，例如上例中前台就绪队列的优先权比后台就绪队列的优先权高，所以前台队列中的进程优先被调度。而只有列的优先权高，所以前台队列中的进程优先被调度。而只有当优先权高的就绪队列空时，方才调度优先权其次的就绪队当优先权高的就绪队列空时，方才调度优先权其次的就绪队列进程，在上例中只有前台队列空时，才调度后台就绪队列。列进程，在上例中只有前台队列空时，才调度后台就绪队列。这样，只有较高优先权的就绪队列都空时才调度最低优先权这样，只有较高优先权的就绪队列都空时才调度最低优先

54、权就绪队列的进程。就绪队列的进程。第第3 3章章 处理机管理处理机管理4优先数法优先数法 根据已占有处理根据已占有处理 机的进程是否可被剥夺而分为优先占机的进程是否可被剥夺而分为优先占有法和优先剥夺法两种有法和优先剥夺法两种 。优先占有法的原理优先占有法的原理是：一旦某个最高优先数的就绪进程分是：一旦某个最高优先数的就绪进程分得处理机之后，只要不是其自身的原因被阻塞（如要求得处理机之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能继续运行时，就一直运行下去，直至运操作）而不能继续运行时，就一直运行下去，直至运行结束。行结束。优先剥夺法的原理优先剥夺法的原理是：当一个正在运行的进程即使其

55、时间是：当一个正在运行的进程即使其时间片未用完，无论什么时候，只要就绪队列中有一个比它的片未用完，无论什么时候，只要就绪队列中有一个比它的优先数高的进程，优先数高的进程就可以取代以前正在运优先数高的进程，优先数高的进程就可以取代以前正在运行的进程，投入运行行的进程，投入运行 。下一页下一页第第3 3章章 处理机管理处理机管理确定进程的优先数通常应考虑如下确定进程的优先数通常应考虑如下几个因素：几个因素： （1）进程类型。）进程类型。 （2）运行时间。）运行时间。 （3）作业的优先数。）作业的优先数。 （4）动态优先数。）动态优先数。 返回本节目录返回本节目录第第3 3章章 处理机管理处理机管理

56、 在多道程序的环境中，系统中的多个进程可以并发在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。综复杂的相互制约的关系。 产生这种错综复杂的相互制约关系的原因有二：产生这种错综复杂的相互制约关系的原因有二： 资源共享资源共享间接制约关系间接制约关系 进程合作进程合作直接制约关系直接制约关系3.5 进程间的

57、同步和互斥进程间的同步和互斥 第第3 3章章 处理机管理处理机管理1.1. 进程间的同步进程间的同步 2. 进程间的互斥进程间的互斥 3.5.1 进程间的同步和互斥进程间的同步和互斥 第第3 3章章 处理机管理处理机管理临界资源临界资源：某段时间仅允许一个进程使用的资源称为临界：某段时间仅允许一个进程使用的资源称为临界资源。资源。宿舍电话宿舍电话打印机打印机 电话和打印机都属于临界资源。除此之外，还有内存变电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。量、指针、数组等等也是临界资源。 几个进程若共享同一临界资源，它们必须以几个进程若共享同一临界资源，它们必须以

58、互斥互斥的方式的方式使用这个临界资源，即当一个进程正在使用临界资源且尚使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操未使用完毕时，则其他进程必须推迟对该资源的进一步操作，作，3.5.1 进程间的同步和互斥进程间的同步和互斥 第第3 3章章 处理机管理处理机管理临界区临界区( (critical section) ) 每个进程中访问临界资源的那段程序段称为每个进程中访问临界资源的那段程序段称为相对于临界资源的临界区。相对于临界资源的临界区。访问临界资源的进程互斥访问临界资源的进程互斥的进入各自的临界区。的进入各自的临界区。第第3 3章章 处理

59、机管理处理机管理a := a -1 print (a)a := a +1 print (a)P1互斥互斥P2互斥互斥If a 0then a := a +1else a:= a-1P3互斥互斥第第3 3章章 处理机管理处理机管理程 序 段1程 序 段2程 序 段n共 享 变 量第第3 3章章 处理机管理处理机管理 这种方法使用了一个物理实体，称为锁，用这种方法使用了一个物理实体，称为锁，用 W 来表示，锁有来表示，锁有两种状态，两种状态，W=0 表示锁已打开；表示锁已打开；W=1表示锁被关闭。表示锁被关闭。加锁原语用加锁原语用LOCK(W)表示，其操作为：表示，其操作为：测试测试W，若若W=1

60、，表示资源正在使用，继续反复测试；若表示资源正在使用，继续反复测试；若W=0，置置W=1(加锁加锁)。加锁原语用加锁原语用LOCK(W)可描述为可描述为L：if W=1 then go to L else W：=1；开锁原语用开锁原语用UNLOCK(W)表示，可描述为表示，可描述为 W：=0； 3. 实现临界区互斥的锁操作法实现临界区互斥的锁操作法 第第3 3章章 处理机管理处理机管理两个进程两个进程P1P1、P2P2使用如下程序实施进程的互斥：使用如下程序实施进程的互斥： 进程进程P1 P1 进程进程P2P2 LOCK(W) LOCK(W) LOCK(W) LOCK(W) S S1/1/进入