第3章 处理器管理课件

第3章处理器管理3.1多道程序设计3.2进程概述3.3进程的描述3.4进程的创建和撤消3.5进程队列与管理3.6中断技术3.7处理器调度3.1.1什么是多道程序设计1、多道程序设计和多道系统让多个计算问题同时装入一个计算机系统的主存储器并行执行，这种程序设计技术称为“多道程序设计”，这种计算机系统称为“多道程序设计系统”或简称“多道系统”。2、采用多道程序设计技术应注意的问题：（1）存储保护：在多道程序设计的系统中，必须提供必要的手段使得在主存储器中的各道程序只能访问规定的区域，这样的工作称为存储保护。实现存储保护是为了避免各道程序的相互干扰，使得每道程序在执行时都不会破坏其他各道的程序和数据，特别是当某道程序发生错误时也不致于影响其它程序。（2）程序浮动在多道程序设计系统中，要求每道程序存放在主存的任何区域都能正确执行，甚至在执行的过程中，当程序的存储区域被改变，也要求其执行不受影响，即程序可以随机地从主存的一个区域移动到另一个区域，移动后仍丝毫不影响它的执行，这种技术称为“程序浮动”。3.1.1什么是多道程序设计（3）资源的分配和调度任何一个装入主存储器的程序仅当占用了处理器后才能执行。程序运行时又可能要求使用外围设备。如果多道程序设计的系统里只配置了一个处理器，则多个程序就要竞争处理器。系统必须进行合理的调度，决定哪一个程序可以占用处理器，哪一道程序应该释放处理器。如果一个程序要求使用另一个程序正在使用的外围设备，则必须等待。当外围设备工作结束时，由系统决定分配给哪个程序使用。所以，在多道程序设计的系统中必须对各资源按一定的策略进行分配和调度。

3、实现多道程序设计的基本要求（1）采用“存储保护”的方法保证各道程序互不侵犯；（2）采用“程序浮动”技术让程序能灵活地改变存放区域且能正确（3）必须对各种资源按一定的策略进行分配和调度。3.1.2为什么要采用多道程序设计1、程序的顺序执行:一个计算问题往往要依照一定的顺序执行，执行的顺序是由编制的程序确定的。3.1.2为什么要采用多道程序设计2、程序的并行执行处理器与外围设备并行工作3、多道并行执行3.1.2为什么要采用多道程序设计3.1.2为什么要采用多道程序设计

显然，对具有处理器与外设并行工作能力的计算机系统来说，采用多道程序设计技术后，能提高整个系统的效率，具体表现在：（“单道”系统一次只允许一个作业装入计算机的主存储器运行，在执行时不能使输入／输出设备和处理器同时工作，也无法充分利用CPU。）

(1)提高了处理器的利用率；

(2)充分利用了外围设备资源；

(3)发挥了处理器同外围设备之间，以及外围设备之间的并行工作能力。多道程序设计的实质就是充分利用硬件的并行工作能力。所以，从总体上说，采用多道程序设计技术可有效地提高系统中资源的利用率，增加单位时间内的算题量，从而提高系统的吞吐量。3.1.3采用多道程序设计应注意的问题

3.1.3采用多道程序设计应注意的问题

(2)并行工作道数跟系统效率不成正比从表面上看，只要增加并行工作道数就可以提高效率，但实际上并行工作的道数跟系统的效率是不成正比的，一是因为主存空间的大小限制了可同时装入的程序数量；二是因为外围设备的数量是一个制约因素；三是因为多个程序同时要求使用同一资源的情况会经常发生。因此，并行工作道数的确定要根据系统配置的资源和用户对资源的要求进行综合考虑。3.2进程——概述

对多道并行执行的程序来说，有时它要占用处理器运行，有时要等待传送信息，当得到信息后又可继续执行，一个程序的执行又可能受到另一个程序的约束。所以，程序的执行实际上是走走停停的。为了能正确反映程序执行时的活动规律和状态变化，我们要引进一个新概念——进程，以便从变化的角度动态地分析和研究程序的执行。程序：程序是具有独立功能的一组指令或一组语句的集合，它指出了处理器执行操作的步骤。程序的执行必须依赖于一个实体一一数据集。程序是静态的。（火车：交通工具）进程：把一个程序在一个数据集上的一次执行称为一个进程(Process)。进行是动态的，进程包括程序和程序处理的对象（数据集），进程实现了程序的功能。（列车：正在行驶的火车）列车中的人或物即为程序执行时的数据集。3.2进程——与程序的区别与联系

程序是静止的，进程是动态的。进程包括程序和程序处理的对象(数据集)，进程能得到程序处理的结果。进程和程序并非一一对应，一个程序运行在不同的数据集上就构成不同的进程。一个进程可以执行一个或几个程序；同一个程序可能由几个进程同时执行。程序可以作为软件资源长期保存，而进程是程序的一次执行过程，是暂时的，只存在于其生命周期中。可再入程序一个能被多个用户同时调用的程序称作“可再入”的程序。可再入的程序有两个特性：

(1)可再入的程序必须是纯代码，在执行时自身不改变。

(2)要求调用者提供工作区,以保证程序能以同样的方式为各种用户服务3.2.2为什么要引入进程

1．提高资源的利用率可以把一个计算问题的程序分成多个独立执行的程序模块后，它们之间只要相互合作就可完成共同的任务。怎样才能使它们正确合作呢，操作系统把一个计算问题中每个可独立执行的程序模块的一次执行看做一个进程，如输人进程、处理进程、打印进程。通过进程的同步(进程同步的实现将在第7章中介绍)可使这些进程正确合作，从而使处理器与外围设备以及各种外围设备之间有效地并行工作，提高资源的利用率。

2、正确反映共享程序被不同用户调用时的活动规律和状态变化。通常把进程分成系统进程和用户进程，把完成操作系统功能的进程称为系统进程，完成用户功能的进行称为用户进程。3.2.3进程的属性

1、进程的动态性进程是动态的，它包含数据和运行在数据集上的程序。

2、多个不同的进程可以包含相同的程序进程与程序并非是一一对应的。一个程序运行在不同的数据集上就构成不同的进程，能得到不同的结果。例如，一个编译程序同时被多个用户调用，各个用户的源程序都是编译程序的处理对象(看做编译程序处理的数据集)，编译程序在各用户的区域里为其编译源程序，分别构成了不同的进程，能为各用户生成不同的目标程序。3．进程可以并发执行对于一个单处理器的系统来说，仍允许若干进程同时执行，即一个进程的工作没有完成之前，另一个进程也可以开始工作。这些同时执行的进程是轮流占用处理器的，把它们称为是并发执行的。4．进程有三种基本状态（1）等待态——等待某一事件(有些教材中，把等待态称为阻塞态)。（2）就绪态——等待系统分配处理器以便运行。（3）运行态——正在占用处理器运行。进程有如下的一些属性3.2.3进程的属性（1）运行态变成等待态：由于等待外设传输信息、等待主存等资源分配或等待人工干预而引起的。（2）等待态变成就绪态：等待的条件已满足，只需分配到处理器后就能运行。（3）运行态变成就绪态：时间片用完，或有更高优先级的进程来抢占处理器等；由于中断而退出处理器的进程可能变成就绪态(有时会变成等待态)。（4）就绪态变成运行态：系统按某种策略选中就绪队列中的一个进程占用处理器，此时，被选中的进程就变成了运行态。4．进程有三种基本状态3.2进程——三个特性（1）动态性：进程是程序的一次执行过程，在执行过程中进程状态不断发生变化（2）并发性：若干进程是可同时执行，它们轮流占用处理器交替运行（3）异步性：进程的执行速度取决于自身与外界原因以及能占用处理器的时间，因此不可预知的速度向前推进3.3.1进程控制块PCB（ProcessControlBlock)为了标识进程，记录进程执行时的情况，操作系统在创建进程时为每一个进程设置一个进程控制块（PCB），一般情况下进程控制块应包含四类信息：（1）标识信息：每个进程都有一个唯一的标识符，用以标识进程的存在和区分各个进程。（2）说明信息：用于说明本进程的情况，其中“进程状态”是指进程的当前状态（运行、就绪、等待）。若是等待状态需进一步说明具体的等待原因。“进程程序存放位置”指出该进程存放在哪里，“进程数据存放位置”指出进程执行时的工作区，用来存放被处理的数据集和处理结果。（3）现场信息：当进程由于某种原因让出处理器时，把与处理器有关的各种现场信息保留下来，以便该进程在重新获得处理器时能把被保留的现场信息重新置入处理器的相关寄存器中继续执行。通常被保留的信息的通用寄存器的内容、控制寄存器内容、以及记录有关系统状态和进程暂停执行时断点的程序状态字寄存器内容等。（4）管理信息：对进程进行管理和调度的信息。通常用进程优先级指出进程可以占用处理器的先后次序，“队列指针”指出处于同一状态的另一个进程的进程控制块地址，这样就可把具有相同状态的进程链接起来，便于对进程实施管理。3.3.1进程控制块PCB（ProcessControlBlock)3.4进程的创建与撤销

1、进程的创建当系统为一个程序分配一个工作区（存放程序处理的数据集）和建立一个进程控制块后就创建一个进程。进程控制块是进程存在的标识，所以，每创建一个进程就要建立一个进程控制块。一个进程刚被创建的进程，它的初始态为就绪态。操作系统依据进程控制块对进程进行控制和管理，把进程执行时的不断变化情况也记录在进程控制块中。2、进程的撤消当一个进程完成了特定的任务后，系统收回这个进程所占的工作区和取消该进程的进程控制块，就撤消了该进程。操作系统中往往设计一些能完成特定功能且不可中断的过程（称为原语）。(1)创建原语：为一个程序分配一个工作区和建立一个进程控制块，并置该进程为就绪状态（2）撤销原语：一个进程完成工作后，收回它的工作区和进程控制块（3）阻塞原语：进程运行过程中发生等待事件时，把进程状态改为等待态（4）唤醒原语：当进程等待的事件发生时，把进程的状态改为就绪态3.5进程队列与管理

1．进程队列把处于相同状态的进程链接在一起，称为“进程队列”。就绪队列和等待队列是两个基本的进程队列。

·就绪队列：由若干就绪进程按一定次序链接起来的队列。

·等待队列：等待资源或等待某些事件的进程排成的队列。2．进程的队列管理一个进程排入到指定的队列中称为入队。一个进程从所在的队列中退出称为出队。系统中负责进程入队和出队的工作称为队列管理。无论单向链接还是双向链接，为了解决入队和出队问题，首先都要找到该队列的队首指针，沿链找出要入队进程的插入位置，或找出要出队的进程，然后修改本进程的指针(入队情况)和相邻进程的有关指针值，有时要修改队首指针。3.5进程队列与管理前一进程控制块中的指针值为它的下一个进程的进程控制块地址。队列中最后一个进程的进程控制块中的指针值可以设为“0”，此外，系统还为每个队列设置一个队首指针，指出队列的第一个进程的进程控制块地址。3.5进程队列与管理在双向队列中设置两个指针：前向指针和后向指针，分别指出前一个和后一个进程的进程控制块地址，最后一个进程的进程控制块中的后向指针为“0”，队列中第一个进程的进程控制块中的前向指针值为“0”，此外，系统还为每个队列设置一个队首指针，指出队列的第一个和最后一个进程的进程控制块地址，以便双向搜索。3.5进程队列与管理1．队首进程出队队首进程出队时，只要把该进程的后继进程的前向指针值修改为“0”，把出队进程的后向指针值送入队首指针单元中。这样．原先在队列中的第二个进程就成了队首，而原来的队首进程就与队列脱钩了。2．非队首(或队尾)进程出队如果要出队的进程既不是队首进程又不是队尾进程，则可以假定进程B要出队，进程B的前一个进程是进程A，而后一个进程是进程C。这样，进程B的出队过程是：把进程B的前向指针值送入进程C的前向指针位置，把进程B的后向指针值送入进程A的后向指针位置。此时，进程A的后向指针就指向进程C，而进程C的前向指针就指向进程A，进程B就从队列中退了出来。3.5进程队列与管理3．队尾进程出队按照队尾进程的前向指针值找到它的前一个进程的进程控制块，把该进程的后向指针值修改为“0”，成为当前的队尾进程。同时把出队进程的前向指针值送入队首指针的尾指针位置，这样原先的队尾进程就退出了队列，且队首指针中的尾指针指向了当前的队尾进程。

入队如果某进程要加入到一个队列中去，若队列原先是空的，则入队的进程就成为该队列的第一个进程；若原队列非空，则应先找到入队进程应插入的位置，再根据链接要求修改相邻进程的队列指针。进程入队时，根据应插入的位置也可分成三种情况：从队首入队成为新的队首进程，从队尾入队成为新的队尾进程，插入到队列中某两个进程之问。3.6中断技术——中断和中断响应1．中断的定义当一个进程占有处理器运行时，由于自身或外界的原因(如出现了某种事件)使运行被打断，此时，操作系统将处理出现的事件，到适当的时候再让被打断的进程继续运行，这个过程称为“中断”。

·中断源：引起中断的事件。

·中断处理程序：对出现的事件进行处理的程序。2．中断的类型从中断事件的性质出发，中断可以分为两大类：①强迫性中断事件：不是正在运行的进程所期待的，而是由于外部的请求或某些意外事故而迫使正在运行的进程被打断。它包括硬件故障中断、程序性中断、外部中断和输入输出中断等。

3.6中断技术——中断和中断响应

①强迫性中断事件：硬件故障中断：由计算机硬件故障造成的，如电源电压超出规定范围，主存储器读写时发生校验错等。程序性中断：由执行到程序的某条指令时出现的问题引起的中断，如，使用了非法操作码，地址越界，除数为“0”，定点溢出等。外部中断：由各种外部事件引起的中断，如用户从终端上输入了一条命令，设备的定时时钟时间已到，操作员从控制台上发出控制信号等。输入输出中断：由输入/输出控制系统的事件所引起的中断，如外围设备在执行信息传输操作时出现了故障，外围设备完成了一次信息的传输操作等。强迫性中断是随机的，断点可能会发生在任何位置。②自愿性中断事件：它是由正在运行的进程执行一条访管指令用以请求系统调用而引起的中断，这种中断也称“访管中断”。自愿性中断的断点是确定的

3．中断响应处理器每执行一条指令后，硬件的中断装置将立即检查有无中断事件发生。若有中断事件发生，则暂停现行进程的执行，而让操作系统的中断处理程序占用处理器，这一过程称为“中断响应”。在中断响应过程中，中断装置要做以下3项工作：

(1)检查是否有中断事件发生判别自愿性中断，只要检查操作码是否为“访管指令”。判别强迫性中断，要检查中断寄存器的内容，若为O，则无中断；若非0，则表示有中断事件发生。

(2)若有中断发生，保护断点信息每个程序都有一个程序状态字(PSW)，用于表示程序的执行状态，如基本状态、中断码和中断屏蔽位等内容。处理器设有一个“程序状态字寄存器”，用来存放当前运行程序的PSW。程序状态字可分为当前PSW、旧：PSW和新PSW。当出现中断事件后，把被中断进程的PSW保存为旧PSW之后，即完成了断点信息保护。

(3)启动操作系统的中断处理程序中断装置通过“交换PSW”过程完成此项任务，即把出现的中断事件存放到当前的PSW中断码位置，然后把该“当前PWS”保存为“旧PSW”，最后再把操作系统中断处理程序的“新PSW”送到程序状态字寄存器中，成为“当前PSW”送入程序状态字寄存器，处理器就按这个新PSW控制处理该事件的中断处理程序的执行。

3.6中断技术——中断和中断响应4．中断处理操作系统的中断处理程序对中断事件进行处理时，大致要做3方面的工作：

(1)保护被中断进程的现场信息把中断时的通用、控制寄存器内容及旧PSW保存到被中断进程的进程控制块中。

(2)分析中断原因根据旧PSW的中断码可知发生中断的具体原因。

(3)处理发生的中断事件中断处理程序在分析引起中断的原因后，要对其分别处理，在有些情况下把具体的处理交给适当的例行程序模块去做。3.6中断技术——中断和中断响应3.6中断技术——中断优先级和中断屏蔽1．中断优先级中断装置按预定的顺序来响应同时出现的中断事件，这个预定的顺序称为“中断优先级”。中断优先级是按中断事件的重要性和紧迫程度来确定的，是在硬件设计时固定的。一般情况下，优先级的高低顺序依次为：硬件故障中断、自愿性中断、程序性中断、外部中断和输入输出中断。2．中断的屏蔽为了防止优先级低的中断事件处理打断优先级高的中断事件的处理，以及避免复杂的中断引起多重嵌套处理，计算机系统采用了中断屏蔽技术，以程序状态字中的中断屏蔽标志位的设置封锁相应事件的响应。通常，中断处理程序只屏蔽比自己级别低的事件，并且不能屏蔽自愿性中断。3.7处理器调度采用批处理操作系统和分时操作系统的计算机系统都属于多道程序设计系统。在这样的系统中，往往同时有多个计算问题(作业)请求处理。它们都因要使用系统资源而会发生竞争。因此，如何对资源进行管理和分配是操作系统中的一个重要问题。处理器调度担负着对处理器的分配工作，它将决定谁能先占用处理器，一次能占用处理器多长时问。我们把在批处理操作系统控制下的作业称批处理作业，把若干个用户作业组织成作业流，让它们成批进入计算机系统，且把它们存放在磁盘上的专用区域中等待处理。在操作系统中，我们把磁盘上用来存放作业信息的专用区域称为输入井，把在输入井中等待处理的作业称为后备作业。3.7处理器调度

任何作业只有被装入主存储器后才能执行。当输入井中等待处理的作业不能全部同时被装入主存储器时，应怎样从中选择一部分作业呢?这就必须根据系统设计时确定的允许并行工作的道数和一定的规则(或称算法)，从后备作业中选取若干作业，让它们进入主存储器，使它们有机会去获得处理器执行。我们把这项从输入井中选取后备作业装入主存储器的工作称为作业调度。不同的计算机系统可以采用不同的规则来进行作业调度。但不管怎样都必须遵循作业调度的下列必要条件：系统现有的尚未分配的资源可以满足被选作业的资源要求。只有这样才能避免进入主存储器的作业因得不到资源而无法执行的现象，才能保证系统有较高的吞吐能力。作业调度选中了一个作业且把它装入主存储器时，就为该作业创建一个用户进程。若有多个作业被装入主存储器，则就创建了多个用户进程。这些进程的初始状态都为“就绪态”。3.8处理器调度

在单处理器的计算机系统中，每一时刻只能让一个进程占用处理器。现有多个进程都要竞争处理器，怎么办呢?这时又必须按照一定的规则从就绪进程中选取一个进程，让它占用处理器。我们把这项从就绪进程中选取一个进程，让它占用处理器的工作称为进程调度。进程占用处理器时，由于各种原因会引起进程状态的变化而让出处理器。于是进程调度可以再从就绪进程中选一个进程运行，使每个被装入主存储器的作业都能有机会占用处理器执行。当一个作业完成工作而结束时，作业调度又可以从后备作业中选取作业装入主存储器且为其创建一个进程，当它被进程调度选中时便可运行。所以，作业调度与进程调度相互配合能实现多道作业的并行执行。对任何一个作业来说，只有先被作业调度选中才有机会去竞争处理器，然而仅当被进程调度选中时才能占用处理器。3.7处理器调度——作业和进程的关系作业调度与进程调度的关系处理器调度我们把在分时系统控制下的作业称为终端作业。当终端用户与系统在线路上连接后，用户输入“注册”命令，向操作系统提出执行一个作业的要求。操作系统接到命令后，首先查看当前正在工作的终端个数。如果正在工作的终端数已达到系统可以承受的最大数，则就让该用户等待。如果当前正在工作的终端数未达到最大数，则系统识别用户，然后请用户输入口令。若口令正确，则再询问该作业对系统的资源要求(主存量、外设等)。若资源能满足，则接收该终端用户的作业。所以，终端用户的注册过程实际上可看做对终端作业的作业调度。操作系统为注册成功的终端作业创建一个进程。当有多个终端作业进入系统时，仍由进程调度来决定当前可占用处理器的进程。当终端作业执行结束，不再需要使用终端时，用户可输入“注销”命令请求退出系统。系统就收回该用户所占的资源，且在终端上显示“退出时间”、“使用系统时间”等，以使用户了解应付的费用。这时，如果有用户在等待使用系统，则可接收一个新的终端作业。批处理作业的调度算法·公平牲——对用户公平，不能无故或无限制地拖延一个作业的执行。·平衡资源使用——尽可能地使系统资源都处于忙碌。·极大的流量——在单位时间内为尽可能多的作业服务，保证计算机系统的吞吐能力。一个理想的调度算法应该是既提高系统效率又能使进入系统的作业及时得到计算结果。两个在批处理处理系统中常用的衡量指标：作业调度算法——先来先服务算法原则：按照作业进入输入井的先后次序来挑选作业先进入的、资源能满足的作业优先被挑选。例题：有一个多道程序设计系统，设供用户使用的主存为100KB①②③④⑤作业调度算法——先来先服务算法执行顺序:A-B-D-C-E作业调度算法——计算时间短的作业优先算法用户对自己的作业计算时间预先作一个估计，作业调度时，优先选择计算时间且资源能得到满足的作业。能降低作业的平均周转时间，提高系统的吞吐能力。作业名进入输入井时间需要计算时间（分钟）主存需求量（KB）装入主存时间开始执行时间执行结束时间周转时间A10.142(0.7)1510.110.110.80.7B10.330(0.5)6010.310.811.31.0C10.524(0.4)5011.311.912.31.8D10.624(0.4)1010.611.311.71.1E10.712(0.2)2011.311.711.91.2平均周转时间：（0.7+1.0+1.8+1.1+1.2)/5=1.16执行顺序:A-B-D-E-C作业调度算法——响应比高者优先算法定义：响应比=等待时间/计算时间采用高响应比者优先算法时，必须先计算出输入井中资源能得到满足的所有作业的响应比，然后从中选择响应比最高者优先装入主存。例如，某单道程序设计系统中有三个作业A、B、C，它们到达输入井的时问及需要的计算时间如表所示。作业名到达输入井时间需计算时间（小时）A8：501.5B9：000.4C9：301.0

由于进行作业调度时间是在作业全部到达输入井后，即在9：30开始进行调度，此时作业A、B、C分别等待了40分钟、30分钟和0分钟，因而响应比为：A：40/90=4/9，B：30/24=5/4，C：0/60=0B的响应比最高，优先选择B装入主存储器执行。作业B结束后，重新计算响应比：A：64/90=32/45，B：24/60=2/5作业A的响应比高于作业C的响应比，选择A执行作业名到达输入井时间需计算时间（小时）A8：501.5B9：000.4C9：301.0作业调度算法——响应比高者优先算法作业调度算法——优先级调度与均衡调度算法

优先级调度算法：为每一个作业确定一个优先级，资源能满足且优先级高的作业优先被选取，当几个作业有相同的优先级时，再按照先来先服务的原则进行调度。怎样确定作业的优先级呢?一种方法是由用户来提出自己作业的优先级。这种方法会造成有的用户为了自己的作业尽快被选中执行而盲目提高作业的优先级。为了防止这种现象，系统可规定优先级越高收费也越高，以作限制。另一种方法是由操作系统根据作业的缓急程度、作业估计的计算时间、作业的类型、资源申请情况等因素综合考虑。分析这些因素在实现系统没计目标中的影响，决定各因数的比例，综合得出作业的优先级。有的系统还可以根据作业在输入井中的等待时间动态地改变其优先级，以缩短作业的周转时问和平均周转时问。

均衡调度算法根据作业对资源的要求进行分类，作业调度从各类作业中去挑选，尽可能地使得使用不同资源的作业同时执行。这样不仅可使系统的各种资源都在被使用，而且可以减少作业等待使用相同资源的时间，从而加快作业的执行。进程调度——先来先服务算法进程调度的职责就是按选定的进程调度算法从就绪队列中选择一个进程，让它占用处理器。常用的进程调度算法有以下4种：

(1)先来先服务调度算法该算法按进程进入就绪队列的先后次序选择可以占用处理器的进程。当运行时间长的进程先就绪时，系统效率会受到影响。例:进程名需要处理器时间执行顺序等待时间执行顺序等待时间A3msA0msC0msB3msB3msB24msC24msC6msA27ms进程调度算法——优先数调度算法(2)优先数调度算法对每个进程都确定一个优先数，该算法总是让优先数最高的进程先使用处理器；然后再对具有相同优先数的进程按先来先服务的次序分配处理器。系统常以任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以是固定的，也可以随进程的执行过程动态变化。一个高优先数的进程占用处理器后，系统处理该进程时有两种方法：一是“非抢占式”，另一种是“可抢占式”。前者使此进程占用处理器后一直运行到结束，除非本身主动让出处理器