第2章 处理器管理

处理器管理"/>

第2章 处理器管理

文章目录

• 2.1处理器状态
• • 2.1.1处理器
  • 2.1.2程序状态字
• 2.2中断技术
• • 2.2.1中断概念
  • 2.2.2中断源分类
  • 2.2.3中断和异常的响应及服务
  • 2.2.4中断事件处理原则
  • 2.2.5中断优先级和多重中断
  • 2.2.6Linux中断处理
• 2.3进程及实现
• • 2.3.1进程定义和属性
  • 2.3.2进程状态和转换
  • 2.3.3进程描述和组成
  • 2.3.4进程上下文切换与处理器状态转换
  • 2.3.5进程控制和管理
• 2.4线程及其实现
• • 2.4.1引入多线程的动机
  • 2.4.2多线程环境中的进程与线程
  • 2.4.3线程的实现
• 2.6处理器调度
• • 2.6.1处理器调度层次
  • 2.6.2选择调度算法原则⭐
  • 2.6.3作业管理与调度
  • 2.6.4低级调度功能和类型
  • 2.6.5作业调度和低级调度算法⭐
• 2.8本章小结

2.1处理器状态

2.1.1处理器

1.指令系统：每台计算机的机器指令集合称为指令系统
2.寄存器：为了实现指令功能，处理齐中设置了一组寄存器用作寻址或存放数据，变量和中间结果，个数根据处理器型号不同而异。
3.特权指令：仅在内核态下才能使用的指令，这些指令涉及改变机器状态，修改寄存器内容，启动设备I/O等，执行这些指令不仅影响运行程序自身，而且干扰其他程序及操作系统，因此只有操作系统有权调用
4.非特权指令：在目态和管态下都能工作。操作系统程序能够执行全部机器指令，而应用程序只能使用非特权指令。如果应用程序执行特权指令将会导致非法执行而产生保护中断。继而转向操作系统的“用户非法执行特权指令”的异常处理程序进行处理。
5.根据执行程序对资源和机器指令的使用权限将处理器设置成不同状态，至少需要划分两种状态，内核态和用户态。
内核态：当处理器处于内核态时，这是操作系统管理程序运行时所处的状态，可认为是处理器正在运行可信系统软件，此时全部机器指令都被允许在处理器上执行，程序可访问所有内存单元和系统资源，并具有改变处理器的能力状态的能力。
用户态：当处理器处于用户态时，他正在运行非可信应用程序，此时无法执行特权指令，且访问仅限于当前处理器上执行程序所在的地址空间，这样就能防止操作系统程序受到应用程序的侵害。
6.处理器状态及其转换：
从用户态向内核态转换：
1）程序请求操作系统服务，执行系统调用；
2）程序运行时，产生中断事件，运行程序被中断，转向中断处理程序工作。
3）程序运行时，产生异常事件，运行程序被打断，转向异常处理程序工作。
三类情况都通过中断机制发生，中断和异常是用户态到内核态转换仅有的途径，当系统中产生中断或异常，处理器作出响应且交换程序状态字，会导致处理器从用户态转向内核态，处理事件的中断或异常处理程序的程序状态字中，处理器模式位一定为“内核态”。
7.用户栈与核心栈
1）用户栈：用户进程空间中开辟的一块区域，用于保存应用程序的子程序间相互调用的参数、返回值、返回点以及子程序的局部变量。
2）核心栈：内存中属于操作系统空间的一块区域，用于保存中断现场和操作系统程序间相互调用的参数、返回值、返回点以及程序的局部变量。

2.1.2程序状态字

程序状态字（PSW）定义：程序运行时，其状态不断动态地变化，如当前处于目态还是管态，下一条要执行的指令位置是什么等等。系统将程序运行时的一组动态信息汇集在一起，称为程序状态字，并存放在处理器的一组特殊寄存器里，以方便系统控制和管理。
标志：状态标志，控制标志，系统标志
作用：PSW用来指示运行程序状态，控制指令执行顺序，并且保留和指示与运行程序有关的各种信息，主要作用是实现程序状态的保护和恢复。

2.2中断技术

2.2.1中断概念

中断定义：中断是指程序执行过程中，遇到急需处理的事件时，暂时停止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。
中断源：引起中断的原因，或者能够发出中断请求信号的来源统称为中断源。

2.2.2中断源分类

外中断：又称中断或异步中断，是指来自处理器之外的中断信号，包括时钟中断信号，键盘中断，它机中断和外部设备中断等。外中断又分为可屏蔽中断和不可屏蔽中断，各个中断具有不同的中断优先级，表示事件紧急程度，在处理高一级中断时，往往会部分或全部屏蔽低优先级中断。
内中断：又称异常或同步中断，是指来自处理器内部的中断信号，通常是由于在程序执行过程中，发现与当前指令关联的，不正常的或错误的事件。内中断可细分为：
1）访管中断（由执行系统调用引起）
2）硬件故障中断（如电源失效，奇偶校验错误，总线超时）
3）程序性异常（如非法操作，地址越界，页面故障，调式指令，除数为0和浮点溢出）
中断和异常的区别;
1）中断是由与现行指令无关的中断信号触发的(异步的)，且中断的发生与CPU处在用户模式或内核模式无关，在两条机器指令之间才可响应中断，一般来说，中断处理程序提供的服务不是为当前进程所需的；
异常是由处理器正在执行现行指令而引起的，一条指令执行期间允许响应异常，异常处理程序提供的服务是为当前进程所用的。异常包括很多方面，有出错(fault)，也有陷入(trap)等。
2 ）要求“中断”被快速处理，以便及时响应其它中断信号，所以，中断处理程序处理过程中是不能阻塞的。“
异常”处于被打断的当前进程上下文中，所提供的服务是当前进程所需要的，所以，异常处理程序处理过程中是可以阻塞的。
3）中断允许发生嵌套，但异常大多为一重；异常处理过程中可能会产生中断，但中断处理过程中决不会被异常打断。

2.2.3中断和异常的响应及服务

中断与异常需要做的四件事：
发现中断源：
保护现场：
转向处理中断/异常事件的处理程序：
恢复现场：

2.2.4中断事件处理原则

1.硬件故障中断
由硬件故障导致的中断（电源故障、主存故障、设备故障），故障排除通常需要人工干预。中断处理程序一般进行保护现场，停止设备工作，停止处理器运行，将故障信息向操作员报告，并对故障所造成的破坏进行估计和恢复。
2.程序性中断
程序错误包括：语法错误、逻辑错误和执行过程中产生的异常（定点溢出、阶码下溢、除数为0等，操作系统可以借助信号机制，将捕获的中断事件交由程序自行处理
3.I/O中断
产生I/O中断的情况：
I/O操作正常结束
I/O操作发生故障
I/O操作发生异常
设备报到或设备结束
4.访管中断
由程序执行访管指令所引起的
5.时钟中断
时钟是操作系统进行调度工作的重要工具，如让分时进程作时间片轮转、让实时进程定时发出或接收控制信号、系统定时唤醒或阻塞一个进程、对用户进程进行记账
时钟可分成绝对时钟和间隔时钟两种

2.2.5中断优先级和多重中断

1.中断优先级：以不发生中断丢失为前提，把紧迫程度相当的中断源归在同一级，紧迫程度差别大的中断源归在不同级，级别高的有优先获得响应的权力，中断装置预定的这个响应顺序称为中断优先级。
2.中断屏蔽：主机可允许或禁止某类中断的响应，如允许或禁止所有的I/O中断、外部中断、及某些程序性中断。有些中断是不能被禁止的，例如，计算机中的自愿性访管中断就不能被禁止。
3.多重中断：中断正在进行处理期间，CPU又响应新的中断事件，于是暂时停止正在运行的中断处理程序，转去执行新的中断处理程序，就叫多重中断（又称中断嵌套）。处理方法：
(1) 串行处理：禁止中断处理过程被中断
(2) 嵌套处理：允许高优先级中断中断低优先级中断
(3) 即时处理：立即响应中断

2.2.6Linux中断处理

2.3进程及实现

2.3.1进程定义和属性

1.进程定义：进程是多道程序设计操作系统的基础；
从理论角度看：是支持程序并发执行的系统机制，是对当前运行程序的活动规律的抽象；
从实践角度看：进程是一种数据结构，用来准确刻画系统动态变化的内在规律，有效地管理和调度在计算机系统主存运行的程序。
2.为什么要引入进程？
1）刻画程序的并发性
2）解决资源的共享性
3.进程具有以下属性：
动态性：有一定的生命周期
共享性：多个进程可执行同一程序，进程可以共享公共资源
独立性：是一个独立实体，有自己的虚存空间、程序计数器和内部状态，是资源分配、保护和调度的基本单位
制约性：存在制约关系
并发性：执行时间上会有所重叠

2.3.2进程状态和转换

1.进程的三态模型及其状态转换如图所示，三种状态分别是：
运行态：进程占用处理器正在运行的状态。
就绪态：进程具备运行条件，等待系统分配处理器以便运行的状态。
等待态：又称阻塞态或睡眠态，之进程不具备运行条件，正在等待某个事件完成的状态

2.七态模型
新增了四个状态：
新建态：进程被创建时的状态，尚未进入就绪队列
终止态：进程完成任务到达正常结束点，或出现无法克服的错误而异常终止，或被操作系统及有终止权的进程所终止时所处的状态。
挂起就绪态：表明进程具备运行条件，但目前在外存中，只有当它被对换到内存才能被调度执行
挂起等待态：表明进程正在等待某一个事件发生且在外存中

2.3.3进程描述和组成

1.进程映像
某时刻进程的内容及其状态集合称为进程映像，包括以下一些要素。
1）进程控制块：标志信息、现场信息、控制信息
2）进程核心栈：中断/异常现场、函数调用的参数和返回地址
3）进程程序块：进程执行的程序
4）进程数据块：私有地址空间，私有数据、用户栈（函数调用时存放栈帧、局部变量等）
进程上下文：操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文。当系统调度新进程占有处理器时，新老进程随之发生上下文切换。进程的运行被认为是在上下文中执行。
进程上下文的组成：
1）用户级上下文：由正文(程序)、数据、共享存储区、用户栈组成，占用进程的虚拟地址空间
2）寄存器上下文：程序状态字、指令计数器、栈指针、通用寄存器
3）系统级上下文：进程控制块、主存管理信息(页表或段表)、核心栈
2.进程控制块
定义：是操作系统用于记录和刻画进程状态及有关环境信息的数据结构。也是操作系统掌握进程资料的唯一结构，它包括了进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。 是进程存在的唯一标志。
标识信息：唯一地标识一个进程，包括进程标识ID、进程组标识ID、用户进程名、用户组名等
现场信息：存放进程运行时的处理器现场信息，以供恢复，包括：通用寄存器内容、控制寄存器内容及栈指针等
控制信息：用于管理和调度进程，包括：调度信息、组成信息、族系关系、通信信息、段/页表指针、辅存信息、CPU占用和使用信息、特权信息、资源清单
3.进程队列及其管理
进程队列定义：处于同一状态的所有PCB链接在一起的数据结构称为进程队列。
同一状态进程的PCB既可按先来先到的原则排成队列;也可按优先数或其它原则排成队列。
通用队列组织方式：
线性方式
链接方式
索引方式

2.3.4进程上下文切换与处理器状态转换

1.中断和异常是激活操作系统的仅有方法
进程切换：是让处于运行态的进程暂停运行，让出处理器，这时要做一次进程上下文切换，即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行
进程切换的步骤：
1）保存被中断进程的处理器现场信息
2）修改被中断进程的进程控制块的有关信息，如进程状态等
3）把被中断进程的进程控制块加入有关队列
4）选择下一个占有处理器运行的进程
5）修改被选中进程的进程控制块的有关信息
6）根据被选中进程设置操作系统用到的地址转换和存储保护信息
7）根据被选中进程恢复处理器现场
2.调度和切换时机的问题
请求调度的事件发生后，就会运行低级调度程序，低级调度程序选中新的就绪进程后，就会进行上下文切换。实际上，由于种种原因，调度和切换并不一定能一气呵成。
通常的做法是，由内核置上请求调度标志，延迟到上述工作完成后再进行调度和进程上下文切换
3.处理器状态转换
用户态→核心态
当中断或系统调用发生时，暂停正在执行的用户进程，把进程从用户状态切换到内核状态，去执行操作系统例行程序以获得服务，这就是一次状态转换，
此时，进程仍在自己的上下文中执行，仅状态发生变化，内核在被中断了的进程的上下文中对这个中断事件作处理，即使该中断可能不是此进程引起的
处理器状态转换的步骤：
1)保存被中断进程的处理器现场信息；
2)处理器从用户态切换到核心态，以便执行服务程序或中断处理程序；
3)如果处理中断，可根据规定的中断级设置中断屏蔽位；
4)根据系统调用号或中断号，从系统调用表或中断入口表找到服务程序或中断处理程序地址。
进程上下文切换和处理器状态转换示意图：

2.3.5进程控制和管理

处理器管理的一个主要工作是对进程的控制，包括：创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、终止进程和撤销进程等。这些控制和管理功能由操作系统中的原语实现。
原语：原语是在管态下执行、完成系统特定功能的过程。
原语和机器指令类似，其特点是执行过程中不允许被中断，是一个不可分割的基本单位，原语的执行是顺序的而不可能是并发的。
1.进程创建:
step 1：在进程列表中增加一项，从PCB池中申请一个空闲PCB，为新进程分配惟一的进程标识符；
step 2：为新进程的进程映像分配地址空间，以便容纳进程实体。进程管理程序确定加载到进程地址空间中的程序；
step3：为新进程分配除主存空间外的其他各种所需资源；
step 4：初始化PCB，如进程标识符、处理器初始状态、进程优先级等；
step 5：把新进程状态置为就绪态，并移入就绪进程队列；
step 6：通知操作系统的某些模块，如记账程序、性能监控程序。
2.进程撤销：
step 1：根据撤销进程标识号，从相应队列中找到并移出它；
step 2：将该进程拥有的资源归还给父进程或操作系统；
step 3：若该进程拥有子进程，先撤销它的所有子进程，以防它们脱离控制；
step 4：回收PCB，并归还到PCB池。
3.进程阻塞：
step 1：停止进程执行，保存现场信息到PCB；
step 2：修改进程PCB有关内容，如进程状态由运行态改为等待态等，并把修改状态后的进程移入相应事件的等待队列中；
step 3：转入进程调度程序去调度其他进程运行。
4.进程唤醒步骤：
step 1：从相应的等待队列中移出进程；
step 2：修改进程PCB的有关信息，如进程状态改为就绪态，并移入就绪队列；
step 3：若被唤醒进程比当前运行进程优先级高，重新设置调度标志。

2.4线程及其实现

2.4.1引入多线程的动机

1.线程：引入线程的概念是为了减少程序并发执行所付出的时空开销，使得并发粒度更细，并发性更好。
解决问题的基本思路：
把进程的两项功能：“独立分配资源” 与 “被调度分派执行” 分离开来，
进程作为系统资源分配和保护的独立单位，不需要频繁地切换；
线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换，在这种指导思想下，产生了线程的概念。
2.线程的优点：
能够快速切换：同一进程的多线程切换，只需改变堆栈和寄存器，地址空间不变；
易于实现通信：自动共享进程的内存和文件，线程可以自由访问全局数据，通信不必经过内核；
减少管理开销：线程创建和撤销无需分配和回收资源；
提高并发程度：一个进程的多个线程可以并发执行。

2.4.2多线程环境中的进程与线程

如图为多线程环境中的进程与线程：

1.多线程环境中进程的定义：
进程是操作系统中除处理器外进行的资源分配和保护的基本单位，它有一个独立的虚拟地址空间，用来容纳进程映像(如与进程关联的程序与数据)，并以进程为单位对各种资源实施保护，如受保护地访问处理器、文件、外部设备及其他进程(进程间通信)。进程可以分为两部分：资源集合和线程集合
2.多线程环境中线程的定义：
线程是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成部分，每个进程内允许包含多个并发执行的实体（控制流），这就是多线程。
3.线程的状态：
线程状态有：运行、就绪和阻塞，线程的状态转换也类似于进程。
4.线程的组成：
1）线程惟一标识符及线程状态信息；
2）未运行时保存的线程上下文；可把线程看成是进程中一个独立的程序计数器在操作；
3）核心栈，核心态下工作时，保存参数，函数调用时的返回地址等；
4）用于存放线程局部变量及用户栈的私有存储区。
线程运行在进程的上下文中,并使用进程的资源和环境。
系统调度的基本单位是线程而不是进程,每当创建一个进程时，至少要同时为该进程创建一个线程，否则该进程无法被调度执行。
5.线程的组织与应用
进程中线程多种组织方式：
第一种是调度员／工作者模式
第二种是组模式
第三种是流水线模式
6.线程管理
多线程技术利用线程包(库)提供线程原语集来支持多线程运行。

2.4.3线程的实现

1.从实现角度看，线程分成：
1）内核级线程KLT：线程的管理工作由内核完成，由内核提供的线程API来使用线程。
2）用户级线程ULT：线程的管理由应用程序完成，在用户空间里实现，内核无须感知线程的存在。
3）混合级线程：支持ULT和KLT

2.6处理器调度

2.6.1处理器调度层次

作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度。
高级调度
中级调度
低级调度
处理器的三级调度模型

处理器两级调度模型：

2.6.2选择调度算法原则⭐

1.资源利用率（△）
CPU利用率=CPU有效工作时间/CPU总的运行时间
CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间
2.吞吐率
单位时间内处理的作业数。
3.公平性
确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饥饿情况。
4.响应时间（△）
交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。
使交互式用户的响应时间尽可能短，或尽快处理实时任务。
这是分时系统和实时系统衡量调度性能的一个重要指标。
5.周转时间（△）
批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。
这是批处理系统衡量调度性能的一个重要指标。
作业周转时间与平均周转时间：

2.6.3作业管理与调度

1.作业(JOB) ：提交给操作系统计算的一个独立任务。
作业步(Job Step)：作业中包含的加工步骤。
作业组织：由用户组织，作业步由用户指定。
作业的提交、收容、执行和完成。
作业管理是为了合理地组织工作流程和方便用户解决应用问题而在操作系统中提供的管理模块，用于对作业进行组织、控制和管理。
作业管理任务：
作业组织
作业调度
运行控制
2.作业和进程的关系
作业是任务实体，进程是完成任务的执行实体;
没有作业任务，进程无事可干，没有进程，作业任务没法完成。
作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。
3.批作业的组织和管理
采用脱机控制方式，作业由程序、数据和作业说明书组成。
1)批作业的输入：SPOOLing系统成批接收作业，并存放于输入井中，然后由系统控制调度和执行。
2)批作业的建立
作业控制语言
作业说明书
作业控制块
4.作业控制块
多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。
5.JCB的主要内容：
⑴作业情况：用户名、作业名、语言名等
⑵资源需求情况：估计占用CPU时间、内存容量、设备及文件、函数库/实用程序等
⑶资源使用情况：进入时间、开始时间、已运行时间、主存地址、外设编号等
⑷作业控制信息：优先级、联机/脱机、操作顺序、出错处理等
⑸作业类型信息：CPU繁忙型、I/O繁忙型、均衡型等
6.作业生命周期状态
输入状态：
后备状态：
执行状态：
完成状态：
7.批作业的调度
(1) 选择作业：
(2) 分配资源：
(3) 创建进程：
(4) 作业控制：
(5) 后续处理：
8.作业调度与进程调度的关系

2.6.4低级调度功能和类型

第一类称剥夺式：
两种处理器剥夺原则，
一是高优先级进程/线程可剥夺低优先级进程/线程，
二是当运行进程/线程时间片用完后被剥夺。
第二类称非剥夺式：

2.6.5作业调度和低级调度算法⭐

1.先来先服务(First Come First Served，FCFS)
三个作业同时到达系统并立即进入调度：作业名（所需CPU时间）:作业1（28），作业2（9），作业3（3）。采用FCFS算法，平均作业周转时间为35。
若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。
若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。
FCFS调度算法的平均作业周转时间与作业提交的顺序有关。
2.最短作业优先(Shortest Job First，SJF)
以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。
算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。
SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。
实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。
四个作业同时到达系统并进入调度：作业名（所需CPU时间）:作业1（9），作业2（4），作业3（10），作业4（8）。
SJF作业调度顺序为作业2、4、1、3，
平均作业周转时间T=17，平均带权作业周转时间W= 1.98。
如果应用FCFS调度算法，平均作业周转时间T =19，平均带权作业周转时间
W = 2.61。
3.最短剩余时间优先 (Shortest Remaining Time First，SRTF)
SRTF算法把SJF算法改为抢占式的。一个新进程进入就绪状态，如果新进程需要的CPU时间比当前正在执行的进程剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行进程。举例如图：

4.最高响应比优先 (Highest Response Ratio First，HRRF)
FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。
响应比最高者优先算法是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。
响应比＝1+已等待时间/估计运行时间
短作业容易得到较高响应比
长作业等待时间足够长后，也将获得足够高的响应比
饥饿现象不会发生

5.优先级调度
静态优先数法
使用外围设备频繁者优先数大，这样有利于提高效率；
重要算题程序的进程优先数大，这样有利于用户；
进入计算机时间长的进程优先数大，这样有利于缩短作业完成的时间；
交互式用户的进程优先数大，这样有利于终端用户的响应时间等等
动态优先数法
①根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越低，反之，进程获得调度的可能性越大;
②根据进程等待CPU时间多少来决定,当进程在就绪队列中等待时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越高，反之，进程获得调度的可能性越小。
6.转轮调度（Round Robin)
轮转调度（Round Robin)做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度
轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备
间隔时钟
7.多级反馈队列调度
又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。
处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。
一个三级反馈队列调度策略如图所示

2.8本章小结