计算机与操作系统-02-处理器

本文主要内容来自 SpriCoder的博客，更换了更清晰的图片并对原文的疏漏做了补充和修正。

1. 处理器管理是 STJ 操作系统的重要组成部分：
   1. 处理器负责管理、调度和分配计算机系统的重要资源，并控制程序执行
   2. 处理器管理中最重要的是处理器调度，即进程调度，也就是控制、协调进程对处理器的竞争。
2. 进程与线程：
   1. 进程是资源分配和管理的单位；
   2. 线程是处理器调度的基本单位。
3. 管态与目态：
   1. 管态又叫特权态（内核态、核心态），可以执行特权指令，执行资源管理程序、为应用程序执行提供良好运行环境的各种原语等。
   2. 目态又叫用户态（普通态），只能执行非特权指令

处理器和寄存器

处理器

上图各组件通过内部总线连接起来，构成一个不包含通用寄存器、I/O 相关寄存器、地址寄存器、数据寄存器和 Cache的示意图。

CPU 中的各组件描述

1. 算数逻辑单元：计算结束之后会将结果的标志放置到标志寄存器 Flag 中。
2. 控制单元：包含重要的指令译码器 ID，而指令是放置在指令暂存器 IR 中。
3. 程序计数器 PC：下一条指令的地址
4. 内存地址寄存器和内存数据寄存器：用来完成对内存数据的访问。

通过系统总线来访问内存中的数据，首先设置地址和数据，然后通过控制来完成数据的读取和写回。

时钟等外部信号来反应到处理器线程中来。

寄存器

用户程序可见寄存器

可以使程序员减少访问主存储器的次数，提高指令执行的效率

所有程序可使用，包括应用程序和系统程序

1. 数据（通用）寄存器：AX、BX、CX、DX 等
2. 地址寄存器：索引（SI、DI）、栈指针（SP、BP）、段地址（CS、DS、SS、ES）、页表寄存器等

控制和状态寄存器

控制和状态寄存器用于控制处理器的操作，主要是被具有特权的操作系统程序使用，以控制程序的执行

1. 程序计数器 PC：存储将取指令的地址
2. 指令寄存器 IR：存储最近使用的指令
3. 条件码 CC：CPU 为指令操作结果设置的位，标志正/负/零/溢出等结果
4. 标志位：中断位等

标志位	含义
中断位	是否有中断发生了，中断源是什么
中断允许位	表示目前是否响应中断
中断屏蔽位	中断发生了，中断响应了，我们要不要屏蔽中断
处理器模式位	现在处理器是处于何种模式
内存保护位	对这段内存是只读还是读写还是不可操作

程序状态字 PSW

PSW 既是操作系统的概念，指记录当前程序运行的动态信息，通常包含：

1. 程序计数器、指令寄存器、条件码
2. 中断字、中断允许/禁止、中断屏蔽、处理器模式、内存保护、调试控制

PSW 也是计算机系统的寄存器

1. 通常设置一组控制与状态寄存器
2. 也可以专设一个 PSW 寄存器

标志划分为三组：状态标志、控制标志和系统标志（更多见 P58）

1. 状态标志：使得一条指令的执行结果影响其后指令的执行，比如溢出等标志
2. 控制指令：控制操作系统行为，比如模式转换等。
3. 系统标志：与进程管理有关，用于保护模式。

指令与处理器模式

机器指令

机器指令是计算机系统执行的基本命令，是中央处理器执行的基本单位。

指令由一个或多个字节组成，包括操作码字段、一个或多个操作数地址字段、以及一些表征机器状态的状态字以及特征码。

指令完成各种算术逻辑运算、数据传输、控制流跳转。

指令执行过程

CPU 根据 PC 取出指令，放入 IR，并对指令译码，然后发出各种控制命令，执行微操作系列，从而完成一条指令的执行。

一种指令执行步骤如下（还有更加细分，这只是一种示例）：

1. 取指：根据 PC 从存储器或高速缓冲存储器中取指令到 IR
2. 解码：解译 IR 中的指令来决定其执行行为
3. 执行：连接到 CPU 部件，执行运算，产生结果并写回，同时在 CC 里设置运算结论标志；跳转指令操作 PC，其他指令递增 PC 值

指令执行周期与指令流水线

现在的操作系统不是顺序地完成指令执行，而是选择使用指令流水线的方式来执行指令

特权指令与非特权指令

用户程序并非能够使用全部机器指令，那些与计算机核心资源相关的特殊指令会被保护。比如：启动 I/O 指令（启动打印机，打印文件会细分成按照行打印，可能导致逻辑上的失败）、置 PC 指令（多道程序调用）等等。

核心资源相关的指令只能被操作系统程序使用（作为特权指令，不允许在用户态使用这些命令）。

特权指令

1. 只有操作系统本身可以使用的指令，在内核态才能调用的命令，不仅仅影响运行程序本身，还会干扰其他程序及操作系统。
2. 比如改变机器状态、修改寄存器值、置中断屏蔽位、加载程序状态字等。
3. 如果应用程序执行特权指令则会导致非法执行而产生保护中断，进而转向操作系统的“用户非法执行特权指令”的异常处理程序处理。

非特权指令

1. 所有的用户程序都能够使用的指令，在用户态和内核态都可以调用的命令。
2. 非特权命令在目态和管态的情况下都能工作。

处理器模式

1. 计算机通过设置处理器模式实现特权指令管理
2. 计算机一般设置 0、1、2、3 等四种运行模式（保护级别）
   • 0：内核级，操作系统内核，可以执行全部指令，包括中断处理、处理 I/O 操作等命令
   • 1：系统调用级，执行系统调用，获得特定的和受保护的程序服务
   • 2：共享库级，可以多个运行进程共享，允许调用库函数，读取但不修改相关数据。
   • 3：用户程序，只能执行非特权指令，受到的保护最少
3. 0 模式可以执行全部指令；3 模式只能执行非特权指令；其他每种运行模式可以规定执行的指令子集
4. 一般来说，现代操作系统只使用 0 和 3 两种模式，对应于内核模式和用户模式
5. 处理器模式是由处理器模式位决定的。

处理器模式切换

1. 简称模式切换，包括“用户模式 \(\to\) 内核模式”和“内核模式 \(\to\) 用户模式”的两种切换。
2. 中断、异常或系统异常等事件导致用户程序向 OS 内核切换，触发：“用户模式 \(\to\) 内核模式”，仅有以下三种方式能触发：
   1. 程序请求操作系统服务，执行系统调用
   2. 程序运行时发生异常（如发生程序性中断，或者目态执行特权指令）
   3. 程序运行时发生并响应中断（一般是 I/O 中断）
3. 我们可以认为中断和异常是用户态到内核态转换的仅有途径。
4. OS 内核处理完成后，调用中断返回指令（如 Intel 的 iret）触发：“内核模式 \(\to\) 用户模式”，操作系统将控制权转交给应用进程。

系统调用示例

栈空间

用户栈

1. 用户栈是用户进程空间中开辟的一块区域，用于保存应用程序的子程序（函数）间相互调用的参数、返回值、返回点以及子程序的局部变量。
2. 如果只有用户栈，没有核心栈，那么操作系统则很难对核心栈的数据提供相应的保护措施。

核心栈

1. 核心栈也叫系统栈或内核栈，是内存中属于操作系统空间的一块区域，其用途包含以下两种：
   1. 保存中断现场，嵌套中断
   2. 保存操作系统程序（函数）间相互调用的参数、返回值、返回点以及程序局部变量。
2. 每个进程有一个核心栈：可读可写不可执行，大小有限
3. 硬件栈指针只有一个

中断

中断、异常和系统异常

广义的中断是指程序执行过程中，遇到急需处理的事件时，暂时中止 CPU 上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。

狭义的中断指来源于处理器之外的中断事件，即与当前运行指令无关的中断事件，如 I/O 中断（为打印机结束后进行善后）、时钟中断（计算机系统计时，多一段时间就要更新系统时间）、外部信号中断（关机）等。

异常指当前运行指令引起的中断事件，如地址异常（访问其他程序的内存、读写没有权利读写的内存、虚拟地址的异常）、算术异常（数字溢出、对 0 除法）、处理器硬件故障（奇偶校验位错误）等。

来自于 CPU 内部的广义中断事件我们称之为异常，和狭义的中断构成了广义的中断。

即广义中断 = 异常（CPU 内部广义中断） + 狭义中断（CPU 外部的广义中断）。

系统异常指执行陷入指令而触发系统调用引起的中断事件，如请求设备、请求 I/O、创建进程等，与硬件无关（通过系统异常请求服务），系统异常可以被认为是异常中的一类

操作系统与中断

1. 操作系统是中断驱动的；换言之，中断是激活操作系统的唯一方式。
2. 操作系统要求计算机硬件系统为其设置相应的中断激活的硬件机制，再配合操作系统的内核程序共同完成中断驱动方式，这个是操作系统实现的最根本的基础，中断处理需要借助硬件电路。

中断源分类

由处理器、内存储器、总线等故障引起，发出或产生的中断称为硬中断，按硬中断事件的来源和实现手段可将中断划分为外中断和内中断。

外中断

外中断又称中断或异步中断，是指来自处理器之外的中断信号，包括时钟中断、键盘中断、它机中断和外部设备等。

外中断又可以分为可屏蔽中断和不可屏蔽中断，各个中断具有不同中断优先级。

内中断

内中断又称异常或同步中断，是指来自处理器内部的中断信号，通常是由于程序执行过程中，发现与当前指令相关的、不正常或错误的时间，内中断可分为：

1. 访管中断：由执行系统调用而引起
2. 硬件故障中断：如电源失效、奇偶校验错误、总线超时等
3. 程序性异常：如非法操作、地址越界、页面故障、调试指令、除数为 0 和浮点溢出等。

中断和异常区别（P60）

中断	异常
CPU 异步	CPU 同步
内核态、用户态	大部分在用户态，内核态唯一的异常是“缺页异常”
一般中断处理程序提供的服务不是当前进程需要的	是当前的进程需要的
快速处理，不可以被打断	可以被阻塞
允许嵌套	大多为一重等
不可以被异常打断	可以被中断中断

中断事件处理原则

中断源：处理器硬件故障中断事件（硬中断）

由处理器、内存储器、总线等硬件故障引起，除了极少类的校验错误可以恢复以外，是非常严重的中断。

处理原则为：保护现场，停止设备，停止 CPU，向操作员报告，等待人工干预

电脑会配置一个小电容保证尽可能较少硬件损伤

中断源：程序性中断事件

该中断处理器执行机器指令引起。

1. 除数为零、操作数溢出等算术异常：简单处理，报告用户；也可以由用户编写中断续元程序处理
2. 非法指令、用户态使用特权指令、地址越界、非法存取等指令异常：终止进程
3. 终止进程指令：终止进程
4. 虚拟地址异常：指令和数据不在内存当中，调整内存后重新执行指令

中断源：自愿性中断事件（访管中断）

处理器执行陷入指令请求 OS 服务引起；在操作系统中，它一般又被称作系统调用，比如请求分配外设、请求 I/O 等等。

处理流程是：

1. 程序执行访管指令，并通过适当方式指明系统调用号。
2. 通过中断机制进入访管中断处理程序，现场信息被保护到核心栈，按功能号实现跳转。
3. 通过系统调用入口地址表找到对应中断服务历程的入口地址
4. 执行终端服务例程

中断源：I/O 中断事件

来源于外围设备报告 I/O 状态的中断事件

1. I/O 完成：调整进程状态，释放等待进程；
2. I/O 出错：先向设备发命令索取状态字，分析产生故障的确切原因，再执行复执或请求人工干预；
3. I/O 异常：等待人工干预，如缺纸中断等待人工加纸；
4. 设备报道或设备结束：表示有设备接入可供使用或设备断开暂停使用。

狭义中断事件。

中断源：外部中断事件

由外围设备发出的信号引起的中断事件：

1. 时钟中断、间隔时钟中断：记时与时间片处理，最常见
2. 设备报到与结束中断：调整设备表
3. 键盘/鼠标信号中断：根据信号作出相应反应
4. 关机/重启动中断：写回文件，停止设备与 CPU

中断系统

中断系统是计算机系统中响应和处理中断的系统，包括硬件子系统和软件子系统两部分

1. 中断响应由硬件子系统完成
2. 中断处理由软件子系统完成

中断系统是操作系统的基础，中断系统也是软硬件协同系统的典型例子

中断响应处理与指令执行周期

在指令执行周期最后增加一个微操作，以响应中断，CPU 在完成执行阶段后，如果允许中断，则进入中断阶段

中断装置

1. 计算机系统中发现并响应中断/异常的硬件装置称为中断装置
2. 由于中断源的多样性，硬件实现的中断装置有多种，分别处理不同类型的中断
3. 这些中断装置因计算机而异，通常有：
   1. 处理器外的中断：由中断控制器发现和响应
   2. 处理器内的异常：由指令的控制逻辑和实现线路发现和响应，相应机制称为陷阱
   3. 请求 OS 服务的系统异常：处理器执行陷入指令时直接触发，相应机制称为系统陷阱

中断控制器

中断控制器：CPU 中的一个控制部件，包括中断控制逻辑线路和中断寄存器，中断控制器会记录中断是来自哪里

1. 狭义中断：（异步过程）外部设备向其发出中断请求 IRQ，在中断寄存器中设置已发生的中断
2. （同步过程）指令处理结束前，会检查中断寄存器，若有不被屏蔽的中断产生，则改变处理器内操作的顺序，引出操作系统中的中断处理程序

狭义中断是异步进程，CPU 正在做的事情和中断可能是两个不同部分

陷阱与系统陷阱

陷阱与系统陷阱：指令的逻辑和实现线路的一部分

1. 执行指令出现异常后，会根据异常情况转向操作系统的异常处理程序
2. 出现虚拟地址异常后，需要重新执行指令，往往越过陷阱独立设置页面异常处理程序
3. 执行陷入指令后，越过陷阱处理，触发系统陷阱，激活系统调用处理程序

中断程序的处理 & 中断 / 异常响应过程

中断处理程序：操作系统处理中断事件的控制程序，主要任务是处理中断事件和恢复正常操作，是一个软件过程。

中断/异常响应过程：

1. 发现中断源，提出中断请求（选择响应哪一个程序）
   1. 发现中断寄存器中记录的中断
   2. 决定这些中断是否被屏蔽
   3. 当有多个要响应的中断源时，根据规定的优先级选择一个
2. 中断当前程序的执行（保护现场）：保存当前程序的 PSW/PC 到核心栈
3. 转向操作系统的中断处理程序：处理器状态已从用户态转换至内核态。
4. 恢复现场：恢复原运行程序的 PSW，重新返回中断点，以便执行后续指令。

恢复正常操作

• 情况一：对于某些中断，在处理完毕后，直接返回刚刚被中断的进程，比如计时中断。
• 情况二：对于其他一些中断，需要中断当前进程的运行，调整进程队列，启动进程调度，选择下一个执行的进程并恢复其执行，比如请求输入输出。

两种情况都是从内核态到用户态。

中断系统处理流程

1. 硬件设计受到操作系统的要求。
2. 操作系统：大型软件系统，大型紧密结合软硬件设备的系统。

多中断的响应与处理

中断屏蔽

1. 当计算机检测到中断时，中断装置通过中断屏蔽位决定是否响应已发生的中断。
2. 有选择的响应中断：由计算机决定。
   1. 延迟或禁止某些中断的响应以避免共享数据结构受到破坏。
   2. 协调中断响应与终端处理的关系，保证优先级顺序。
   3. 防止同级中断互相干扰。
3. 计算机均配置可编程中断控制器。

中断优先级

1. 当计算机同时检测到多个中断时，中断装置响应中断的顺序。
2. 有优先度的响应中断：将紧迫程度相当的中断源归为同一级别，将紧迫程度差距较大的中断源归为不同级别。
3. 一种可能的处理次序：（对几十个人使用的大型计算机系统很合理），可以借助软硬件分别来完成实现。
   1. 处理机硬件故障中断事件
   2. 自愿性中断事件
   3. 程序性中断事件
   4. 时钟中断等外部中断事件
   5. 输入输出中断事件
   6. 重启动和关机中断事件
4. 不同类型的操作系统有不同的中断优先级：PC 做出关机操作表示放弃当前的所有的操作，所以重启动和关机中断是优先级最高的中断。

中断的嵌套处理

当计算机响应中断后，在中断处理过程中，可以再响应其他中断。

操作系统是性能攸关的程序系统，且中断响应处理有硬件要求，考虑系统效率和实现代价问题，中断的嵌套处理应限制在一定层数内，如 3 层。

中断的嵌套处理改变中断处理次序，先响应的有可能后处理。

多中断的响应与处理

决定了中断处理次序的因素：

1. 中断屏蔽可以使中断装置不响应某些中断
2. 中断优先级决定了中断装置响应中断的次序
3. 中断可以嵌套处理，但嵌套的层数应有限制
4. 中断的嵌套处理改变了中断处理的次序

多重中断处理

顺序中断处理（串行处理）

X、Y 两个中断同时发生，如下图所示，系统先响应 X，屏蔽 Y，待 X 响应完成后，系统再响应并处理 Y

嵌套中断处理（嵌套处理）

X、Y 两个中断同时发生，根据中断有限级，先响应中断 X，因为没有屏蔽 Y，则响应并处理 Y，处理 Y 完成后，再处理 X。

即时处理

在运行中断处理程序时，如果出现程序性中断事件，在一般情况下，表明此时中断程序有异常，应对其立即响应并处理。

中断处理的例子：Linux 内核处理流程

中断信号源：中断向量

1. 中断，分为所有外部设备产生的屏蔽中断请求，和硬件故障等紧迫时间引发的非屏蔽中断。
2. 异常：CPU 发出的中断信号，主要有故障、陷阱、终止和编程异常等

更多见 P66-71 页

进程及其状态

进程的提出

操作系统必须全方位地管理计算机系统中运行的程序。因此，操作系统为正在运行程序建立一个管理实体：进程

进程的概念

进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。

1. 具有一定独立功能的程序：进程是相对独立的
2. 关于某个数据集合：对于不同数据集合的操作不是同一个进程。
3. 一次运行活动：有生命周期

进程是操作系统进行资源分配和调度的一个独立单位：这只限于单线程单进程的情况下

1. 资源分配：除了 CPU 之外的资源的分配，比如内存和外设等
2. 单线程情况下，进程的资源分配和调度就是处理器的。
3. 调度特指处理器的调度

有的将进程叫做 process，Linux 以及一些企业中，把进程称为 Task。

进程可以看为可运行程序加载到内存，配合相应的数据集，在操作系统中的一个实例，程序可以多次被加载进入成为进程。

一个进程包括五个实体部分，分别是：

1. （OS 管理运行程序的）数据结构 P
2. （运行程序的）内存代码 C
3. （运行程序的）内存数据 D
4. （运行程序的）通用寄存器信息 R
5. （OS 控制程序执行的）程序状态字信息 PSW

进程的属性

1. 动态性：进程是程序在数据结合上的一次执行过程，是动态概念，同时它有生命周期，而程序是一组有序指令序列，是静态概念，所以程序作为系统中的一种资源是永久存在的。
2. 共享性：同一程序同时运行于不同数据集合上时都是不同的进程，即不同的进程可以运行相同的程序。
3. 独立性：每个进程是操作系统中的一个独立实体。有自己的虚存空间、程序计数器和内部状态.
4. 制约性：进程因共享资源或协同工作产生相互制约关系，造成进程执行速度的不可预测性，必须对进程的执行次序或相对执行速度予以协调。
5. 并发性：多个进程的执行在时间上可以重叠。

单线程结构进程和多线程结构进程

1. 单线程结构进程：进程级别，负责完成资源分配和 CPU 调度。
2. 多线程结构进程：线程级别，负责完成资源分配（进程完成）和 CPU 调度（代表一个执行流），并且一个进程中可以包含很多线程。
3. 操作系统最开始设计的时候并没有设计多线程。

进程举例

以下的程序与数据集都是内存级的。

不同时段针对同一个外存数据文件运行同一个外存程序文件意味着完全不同的（P, C, D, R, Psw）

无关进程

不同程序在不同数据集上运行：构成两个无关进程

共享数据的交往进程

不同程序在相同数据集上运行：构成两个共享数据的交往进程。

共享代码的无关进程

1. 相同代码在不同数据集上运行：构成两个共享代码的无关进程
2. 共享的代码称为可再入程序，如编辑器可再入程序是纯代码的，可再入程序必须是纯代码的

共享代码和数据的进程

可以共享代码或者共享数据

进程状态和转换

进程三态模型

只要操作系统支持多道程序设计，就必须要设计进程转换模型来管理，必须实现三个进程状态和四个跳转关系，进程状态转换一定有内核的参与。

运行被中断进程时需要找到被中断时的信息并恢复。

三种状态

1. 运行态：进程占有处理器正在运行的状态。
2. 就绪态：进程具备运行条件，等待系统分配处理器以便运行的状态，面向调度的，处理器只会挑选就绪态进程（就绪队列进程）
3. 等待态：又称阻塞态或睡眠态，指进程不具备运行条件，正在等待某个事件完成的状态，暂时被剥夺处理机会。
4. 处于运行态个数不能大于处理器个数。
5. 进程创建后一般是处于就绪态

四种状态转换

1. 运行态 \(\rightarrow\) 等待态：等待资源、I/O、信号量
2. 等待态 \(\rightarrow\) 就绪态：资源满足、I/O 结束、信号量完成
3. 运行态 \(\rightarrow\) 就绪态：运行时间片到（倒计时到，不缺少其他东西，只缺少 CPU，退回就绪态）、有更高优先权进程，低级调度问题
4. 就绪态 \(\to\) 运行态：进程被选中

以上四个状态转换，一个不能少，一个也不能多，其他的转换不存在的原因如下：

1. 没有就绪态到等待态：到等待态需要内核参与。
2. 没有等待态到运行态：等待的资源还没有就绪，无法进入运行态。

时间片与进程转换

1. 时间片用完，计算没有做完，被抢占的进程 运行态 \(\to\) 就绪态：启动内核的处理器调度算法.
2. 时间片内，用户进程发生中断或系统调用，运行态 \(\to\) 等待态
3. 时间片内，用户进程完成全部计算完成退出系统，运行态 \(\to\) 终止态，激活内核，时间片被撤销。

进程三态模型总结与扩展

1. 进程映像定义其数据结构和存储结构
2. 状态转化模型（队列模型）定义其生命周期和状态转换
3. 然后围绕以上两部分开发出相应的操作和算法
4. 进程状态和模型与信号量同样相关，后续深入讨论。

进程七态模型（P55）

stateDiagram-v2
    direction LR
    新建态 --> 就绪态 : 提交
    新建态 --> 挂起就绪态 : 提交
    运行态 --> 挂起就绪态 : 挂起
    就绪态 --> 挂起就绪态 : 挂起
    就绪态 --> 运行态 : 选中
    挂起就绪态 --> 就绪态 : 挂起结束
    运行态 --> 就绪态 : 落选
    等待态 --> 就绪态 : 等待事件结束
    等待态 --> 挂起等待态 : 挂起
    挂起等待态 --> 等待态 : 挂起结束
    运行态 --> 等待态 : 出现等待事件
    挂起等待态 --> 挂起就绪态 : 等待事件结束
    运行态 --> 终止态

新添加的状态

1. 新建态：对应于进程被创建的状态，尚未进入就绪队列，创建进程的两个步骤
   1. 为新进程分配所需资源和建立必要的管理信息
   2. 设置进程为就绪态，等待被调度执行
2. 终止态：
   1. 进程完成认为到达正常结束点
   2. 出现无法克服的错误而异常终止
   3. 操作系统及有终止权的进程所终止时所处的状态，处于终止态的进程不再被调度执行
   4. 下一步就将被系统撤销，最终从系统中消失。
3. 挂起就绪态：表明进程具备运行条件，但目前在外存中，只有它被对换到内存才能调度执行。
4. 挂起等待态：表明进程正在等待某一个事件发生且在外存中。

进程挂起的源头

随着不断创建进程，当系统资源尤其是内存资源已经不能满足进程运行的要求时，必须把某些进程挂起（suspend），对换到磁盘对换区中，释放它占有的某些资源，暂时不参与低级调度，起到平滑系统负荷的目的；也可能系统出现故障，需要暂时挂起一些进程，以便故障消除后再接触挂起并恢复进程运行。

进程挂起的原因是多种多样的。

进程挂起

进程挂起的概念

1. OS 无法预期进程的数目与资源需求，计算机系统在运行过程中可能出现资源不足的情况
2. 运行资源不足表现为性能低和死锁两种情况
3. 解决办法：剥夺某些进程的内存及其他资源，调入 OS 管理的对换区，不参加进程调度，待适当时候再调入内存、恢复资源、参与运行，这就是进程挂起
4. 挂起态与等待态有着本质区别：
   1. 进程挂起：没有任何资源
   2. 进程等待：占有已申请到的资源处于等待
5. 结束挂起状态的命令只能由操作系统和父进程发出。

进程挂起的选择与恢复

挂起的选择：

1. 一般选择等待态进程进入挂起等待态
2. 也可选择就绪态进程进入挂起就绪态
3. 运行态进程还可以挂起自己

挂起的恢复：

1. 等待事件结束后，挂起等待态进入挂起就绪态
2. 一般选择挂起就绪态进程予以恢复
3. 操作系统极其空闲才会选择调入挂起等待态的进程

挂起进程的特点

1. 进程不能被立即执行
2. 进程可能会有等待事件，但是等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件
3. 由于操作系统、父进程或进程自身阻止其运行

补充：SVR4 进程状态模型

preempted：抢占，虚线表示合为一体。

进程的描述与组成

进程的设计时要考虑进程的声明周期，从而引入三态模型

进程控制块

1. 进程控制块（Process Control Block，PCB）又称进程描述符，是 OS 用于记录和刻画进程状态及环境信息的数据结构，是进程存在的唯一标识，是操作系统刻画进程的执行状态及环境信息的数据结构，是进程动态特征的汇集，是操作系统掌握进程的唯一资料结构和进程调度的主要依据。
2. 包括标识信息、现场信息和控制信息。

标识信息

用于存放唯一标识该进程的信息

1. 系统分配的标识号
2. 系统分配的进程组标识号
3. 用户定义的进程名
4. 用户定义的进程组名

现场信息

用于存放该进程运行时的处理器现场信息

1. 用户可见寄存器内容：数据寄存器、地址寄存器
2. 控制与状态寄存器内容：PC、IR、PSW
3. 栈指针内容：核心栈与用户栈指针

控制信息

用于存放与管理、调度进程相关的信息：

1. 调度相关信息：状态、等待事件/原因、优先级
2. 进程组成信息：代码/数据地址、外存映像地址
3. 队列指引元：进程队列指针、父子兄弟进程指针
4. 通信相关信息：消息队列、信号量、锁
5. 进程特权信息：如内存访问权限、处理器特权
6. 处理器使用信息：占用的处理器、时间片、处理器使用时间/已执行总时间、记账信息
7. 资源清单信息：如正占有的资源、已使用的资源

进程映像

进程映像（Process Image）是某一时刻进程的内容及其执行状态集合：

1. 进程控制块：每个进程捆绑一个，保存进程的标识信息、现场信息和控制信息。进程创建时创建进程控制块，进程撤销时回收进程控制块，与进程一一对应。
2. 进程程序块：进程执行的程序空间，规定进程一次运行所应完成的功能。
3. 进程数据块：进程处理的数据空间，是进程的私有地址空间，包括各类私有数据、处理函数的用户栈和可修改的程序。
4. 进程核心栈：每个进程捆绑一个，进程在内核模式下运行时使用的堆栈，中断或系统过程使用，保存函数调用的参数、局部变量和返回地址等。

进程运行时如果遇到要执行操作系统内核函数，此时则保存应用程序的全部现场信息及其用户栈，使其不被内核程序破坏。而内核函数运行时使用进程的核心栈来放置工作信息。

进程映像是内存级的物理实体，又称为进程的内存映像。

进程上下文，Process context

进程的执行需要环境支持，包括 CPU 现场和 Cache 中的执行信息。在操作系统中，进程物理实体和支持进程运行的环境合称进程上下文。进程上下文刻画了进程的执行情况。

OS 中的进程物理实体和支持进程运行的环境合成进程上下文，包括以下：

1. 用户级上下文：
   1. 用户程序块（可执行的机器指令序列）
   2. 用户数据区（进程可访问的信息）
   3. 用户栈（存放函数调用过程中的信息）
   4. 用户共享内存（进程通信使用的内存区）
   5. 对换至磁盘的分段或页面仍然是用户级上下文的组成部分。
2. 寄存器上下文（存储在进程控制块中）：
   1. 处理器状态寄存器（进程当前状态）
   2. 指令计数器（下一条该执行的指令地址）
   3. PSW/栈指针（指向用户栈或核心栈当前地址）
   4. 通用寄存器等
3. 系统级上下文：
   1. PCB（Process Control Block，进程的状态）
   2. 内存区管理信息（进程页表或段表）
   3. 核心栈（进程内核态运行时的工作区）

进程的管理

概念级的 OS 进程管理软件

关键的进程管理软件包括：

1. 系统调用/中断/异常处理程序：
2. 队列管理模块：操作系统用来管理进程控制块的信息，核心程序包，是操作系统实现进程管理的核心模块
3. 进程控制程序：操作系统用于控制进程状态转换用到的程序包
4. 进程调度程序（独立进程居多）
5. 进程通信程序（多个程序包）
6. 终端登录与作业控制程序、性能监控程序、审计程序等外围程序

进程队列及其管理

进程队列分类：

1. 运行队列：通常只有一个进程
2. 等待（阻塞）队列：也是有机会被调入，他等待的资源或事件完成后，调入就绪队列。
3. 就绪队列：从就绪队列中挑选进程调入运行，按照优先级或 FCFS 的原则排队

最后通过系统调用结束处理，进程实现的队列模型不适合使用堆栈（堆栈是先进后出的）。

• 队列管理模块是操作系统实现进程管理的核心模块。
• 操作系统建立多个进程队列，包括就绪队列和等待队列。
• 按需组织为先进先出队列与优先队列。
• 队列中的进程可以通过 PCB 中的队列指引元采用单/双指引元或索引连接
• 出队和入队操作
• 进程与资源调度围绕进程队列展开

部分进程管理原语（P81）

1. 进程创建：
   1. 操作系统初始启动时会创建承担系统资源分配和控制管理的一些系统进程，同时会创建一个所有用户集成的祖先，其他用户进程实在用户程序被提价与选中运行时被创建的。
   2. 操作系统通常将创建关系通过父子进程的关系来表示。
   3. 创建原语：进程表加一项、申请 PCB（进程控制块）并初始化、生成唯一进程标识、建立进程映像、分配各种资源、移入就绪队列、通知操作系统某些模块
2. 进程撤销：
   1. 完成特定工作或出现严重错误后需要撤销，分为正常撤销和非正常撤销。
   2. 产生原因：运行结束、执行非法指令、用户态执行特权指令、时间配额到、等待时间超时、越界错误、共享内存区非法使用、程序性故障等。
   3. 撤销原语：从队列中移除、归还资源、撤销标识、回收 PCB、移除进程表项
3. 进程阻塞：
   1. 使得进程让出处理器转而等待一个事件，比如等待资源等，阻塞是同步时间。
   2. 阻塞原语：保存现场信息、修改 PCB、移入等待队列、调度其他进程执行
4. 进程唤醒：
   1. 等待时间完成时产生一个中断，激活操作系统，在系统的控制下将被阻塞进程唤醒
   2. 唤醒原语：等待队列中移出、修改 PCB、移入就绪队列（该进程优先级高于运行进程触发抢占）
5. 进程挂起：
   1. 出现引起挂起的事件时，系统或进程会利用挂起原语把指定进程或处于等待态的进程挂起。
   2. 挂起原语：修改状态并出入相关队列、收回内存等资源送至对换区。
   3. 挂起原语可以由进程自己或其他进程调起。
6. 进程激活：
   1. 当系统资源尤其是内存资源充裕或请求激活进程时，系统或相关进程会调用激活原语将指定进车行激活。
   2. 激活原语：分配内存，修改状态并出入相关队列。
   3. 激活原语只能由其他进程调用。

其他：如修改进程特权，以上是一个进程控制的流程

原语与进程控制原语（Primitive）

1. 进程控制过程中涉及对 OS 核心数据结构（进程表/PCB 池/队列/资源表）的修改，不是进程处理的所有指令都是。
2. 为防止与时间有关的错误，应使用原语
3. 原语是由若干条指令构成的完成某种特定功能的程序，执行上具有不可分割性（保证对核心资源的访问是正确的，原语涉及到的资源都是共享核心资源，只能是唯一的），进入原语区间，立刻关闭中断完成，然后再开中断响应。
4. 原语的执行可以通过关中断实现，进程控制使用的原语被称为进程控制原语，另一类常用原语是进程通信原语

进程切换与模式切换（状态转换）

进程切换

1. 进程切换指从正在运行的进程中收回处理器，让待运行进程来占有处理器运行
2. 进程切换实质上就是被中断运行进程与待运行进程的上下文切换。
3. 进程切换必然发生在内核态而非用户态。

模式切换（状态转换）

进程切换必须在操作系统内核模式下完成，这就需要用到模式切换。

模式切换又称处理器状态切换，包括：

1. 用户模式到内核模式由中断/异常/系统调用中断用户进程执行而触发
2. 内核模式到用户模式 OS 执行中断返回指令将控制权交还用户进程而触发

模式切换（状态转换）的基本工作任务

中断装置完成正向模式切换，包括：

1. 处理器模式转为内核模式
2. 保存当前进程的 PC/PSW 值到核心栈
3. 转向中断/异常/系统调用处理程序

中断返回指令完成逆向模式转换，包括：

1. 从待运行进程核心栈中弹出 PSW/PC 值
2. 处理器模式转为用户模式

进程切换的工作过程

1. （中断/异常等触发）正向模式切换并压入 PSW/PC
2. 保存被中断进程的现场信息
3. 处理具体中断/异常
4. 把被中断进程的系统堆栈指针 SP 值保存到 PCB
5. 调整被中断进程的 PCB 信息，如进程状态
6. 把被中断进程的PCB加入相关队列
7. 选择下一个占用 CPU 运行的进程
8. 修改被选中进程的 PCB 信息，如进程状态
9. 设置被选中进程的地址空间，恢复存储管理信息
10. 恢复被选中进程的 SP 值到处理器寄存器 SP
11. 恢复被选中进程的现场信息进入处理器
12. （中断返回指令触发）逆向模式转换并弹出 PSW/PC

进程切换的发生时机

进程切换一定发生在中断/异常/系统调用处理过程中，常见的情况是：

1. 阻塞式系统调用、虚拟地址异常导致被中断进程进入等待态
2. 时间片中断、I/O 中断后发现更高优先级进程，导致被中断进程转入就绪态
3. 终止用系统调用、不能继续执行的异常导致被中断进程进入终止态

内核不能执行调度和切换的情况

1. 内核正在处理中断的过程中
2. 进程运行在内核临界区
3. 内核处在需要屏蔽中断的原子操作过程中。

模式切换（状态转换）的处理器情况

1. 用户空间中，处于进程上下文，应用进程在用户态下运行，使用用户栈。
2. 内核空间中，处于进程上下文，内核代表进程在内核态下运行，使用核心栈。
3. 内核空间中，处于中断上下文，与任何进程无关，中断服务例程在内核态下处理特定中断。
4. 内核空间中，内核线程（无用户地址空间的进程）运行于内核态。

进程切换与模式切换（状态转换）

1. 一些中断/异常不会引起进程状态转换，不会引起进程切换，只是在处理完成后把控制权交回给被中断进程，处理流程是：
   1. （中断/异常触发）正向模式切换压入 PSW/PC
   2. 保存被中断进程的现场信息
   3. 处理中断/异常
   4. 恢复被中断进程的现场信息
   5. （中断返回指令触发）逆向模式转换弹出 PSW/PC
2. 比如计时中断，中断处理完成后直接恢复
3. 模式切换是进程仍在自己的上下文进行处理，仅仅是处理器状态发生了变化，内核仍然被中断进程的上下文中进行处理。

多线程技术概述

最开始设计进程的时候并没有体现线程的概念

单线程结构

传统进程是单线程结构进程

单线程结构进程的问题

单线程结构进程在并发程序设计上存在的问题：

1. 进程切换开销大：10 个人干 100 天的活动 \(\to\) 开会等活动产生的开销，进程切换要进行模式切换，然后再启动进程调度，选择一个就绪进程占用处理器，恢复现场，然后再反向进行。
2. 进程通信开销大：指令流如果分布在不同进程中，那么每次交互都需要由内核完成。
3. 限制了进程并发的粒度：如果没有线程概念，那么进程中本身不可以并发，粒度比较高
4. 降低了并行计算的效率

解决问题的思路

把进程的两项功能分离开来：

1. 独立分配资源（进程概念上），进程作为系统资源分配和保护的独立单位，不需要频繁地切换
2. 被调度分派执行（线程概念上），线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换

线程的出现会减少进程并发执行所付出的时空开销，使得并发粒度更细、并发性更好。

两项功能绑定就是单线程进程，两项功能分离就是多线程进程。

多线程结构进程

多线程环境下进程的概念

在多线程环境中，进程是操作系统中除处理器以外的资源分配和保护的独立单位。具有：

1. 用来容纳进程映像的虚拟地址空间
2. 对进程、文件和设备的存取保护机制

多线程环境下线程的概念

线程是进程能够并发执行的实体，是进程的组成单位，也是处理器调度和分派的基本单位。

1. 用来容纳进程映像的虚拟地址空间
2. 对进程、文件和设备的存取保护机制

进程是一条执行路径，有独立的程序计数器，未运行时保护线程上下文。同一个进程中的所有线程共享进程获得的主存空间和资源。它具有：

1. 线程执行状态
2. 受保护的线程上下文，当线程不运行时，用于存储现场信息
3. 独立的程序指令计数器
4. 执行堆栈
5. 容纳局部变量的静态存储器
6. 线程控制块

多线程结构进程中的进程与线程

于是，进程可以分为两部分：

1. 资源集合
2. 线程集合。

进程要支撑线程运行，为线程提供虚拟地址空间和各种资源。

进程封装管理信息，包括对指令代码、全局数据、打开的文件和信号量等共享部分的管理。

线程封装执行信息，包括状态信息、寄存器、执行栈（用户栈指针与核心栈指针）和局部变量、过程调用参数、返回值等私有部分的管理。

由于线程具有传统进程的许多特征，所以也把线程称为轻量级进程（Light Weight Process,LWP）

多线程环境下线程的状态与调度

线程状态有运行、就绪和睡眠，没有挂起状态。因为挂起和资源有关，而资源管理的单位是进程，与线程无关。

与线程状态变化有关的线程操作有：孵化、封锁、活化、剥夺、指派、结束

OS 感知线程环境下：

1. 处理器调度的对象是线程
2. 线程的存在、状态等都需要被操作系统内核感知到，进程没有三状态，或者说只有挂起状态。

OS 不感知线程环境下：

1. 处理器调度的单位仍然是进程
2. 用户空间中的用户调度程序调度线程，内核不参加线程调度。

状态转换模型：

1. 运行态 \(\to\) 终止态（撤销 Return）
2. 运行态 \(\to\) 就绪态（中断系统）
3. 运行态 \(\to\) 就绪态（时间片用完）
4. 就绪态 \(\to\) 运行态

DBMS：Client（请求方，Request）和 Server（应答，Response），Client 频繁请求，Server 频繁响应，Jacketing 避免阻塞

并发多线程程序设计的优点

1. 快速线程切换：改变堆栈和寄存器，不需要改变地址空间
2. 减少（系统）管理开销：线程的创建和撤销要简单很多
3. （线程）通信易于实现：自动共享进程的内存和文件
4. 并行程度提高
5. 节省内存空间

多线程技术的应用

1. 前台和后台工作：word 的输入和拼写检查
2. C/S 应用模式：用户和服务器，其他线程调用
3. 加快执行速度
4. 设计用户接口

KLT 与 ULT

内核级线程

线程管理的所有工作由 OS 内核来做，并提供了一个应用程序设计接口 API，供开发者使用内核级线程（KLT, Kernel-Level Threads）。

创建时：内核为其创建进程和一个基线程，线程实行过程中通过内核的创建线程原语来创建其他线程。

OS 直接调度 KLT，KLT 用于解决物理并行性问题，内核可以感知到所有的内核级线程，可以控制器其数据结构，内核调度在线程的基础上进行。

内核级线程示意图

内核级线程的特点

优点：

1. 在多处理器上内核可以同时调度同一进程的多个线程运行。
2. 进程中的某一线程被阻塞了，内核能调度同一进程的其它线程占有处理器运行，也可以运行其他进程。
3. 由于内核比较小，内核自身也可用多线程技术实现，能提高操作系统的执行速度和效率。
4. 能够解决物理并行性问题。

缺陷：

1. 应用程序线程在用户态运行，线程调度和管理在内核实现，在同一进程中，控制权从一个线程传送到另一个线程时需要模式切换，系统开销较大。
2. 线程调度开销大，线程通信开销小。

用户级线程

用户级线程（ULT, User-Level Thread）

1. 用户空间运行的线程库，提供多线程应用程序的开发和运行支撑环境。任何应用程序均需通过线程库进行程序设计，再与线程库连接后运行。
2. 线程管理的所有工作都由应用程序完成，内核没有感知到线程的存在，内核感知到的单位是进程。

用户级线程示意图

用户级线程的特点

优点：

1. 节省开销和内核资源：所有线程管理数据结构均在进程的用户空间中，线程切换不需要内核模式，能节省模式切换开销和内核的宝贵资源。
2. 允许进程按应用特定需要选择调度算法，甚至根据应用需求裁剪调度算法。
3. 可移植性好：能运行在任何 OS 上，内核在支持 ULT 方面不需要做任何工作。
4. ULT 可以解决逻辑并行性问题。

缺点：

1. 不能利用多处理器的优点，OS 调度进程，仅有一个 ULT 能执行。

2. 一个 ULT 的阻塞，将引起整个进程的阻塞：不能完成切换线程，因为内核感知不到进程中的线程的存在。

3. ULT 不能解决物理并行性问题。

Jacketing 技术

作用：把阻塞式系统调用改造成非阻塞式的：解决一个 ULT 的阻塞导致整个进程阻塞；避免进程因此从运行态 \(\rightarrow\) 阻塞态，如此的频繁切换会带来比较大的开销。

1. 当线程陷入系统调用时，执行 Jacketing 程序。
2. 由 Jacketing 程序来检查资源使用情况，以决定是否执行进程切换或传递控制权给另一个线程。

用户级线程 vs. 内核级线程

1. 受限条件下的并行：受限条件是同步关系（等待）
2. ULT 适用于解决逻辑并行性问题
3. KLT 适用于解决物理并行性问题

多线程实现的混合式策略

1. 在用户空间完成所有的线程的创建工作。
2. 单应用的多个 ULT 可以映射成一些 KLT，通过调整 KLT 数目，可以达到较好的并行效果。
3. 在混合式线程中，内核必须支持内核级多线程的建立、调度和管理，同时也允许应用程序建立、调度和管理用户级线程。
4. ULT 的切换仅在用户空间中且仅需要少量机器指令，而 KLT 需要用户态到内核态到用户态的完整上下文切换，修改内存映像，使得高速缓存失效，导致数量级的延迟。

多线程实现混合式策略的特点

1. 合并了用户级线程/内核级线程设施
2. 线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行
3. 一个应用中的多个用户级线程被映射到一些（小于等于用户级线程数目）内核级线程上
4. 程序员可以针对特定应用和机器调节内核级线程的数目，以达到整体最佳结果
5. 该方法将会结合纯粹用户级线程方法和内核级线程方法的优点，同时减少它们的缺点

线程混合式策略下的线程状态

1. KLT 的三态模型，由系统调度负责
2. ULT 的三态模型，由用户调度负责
3. 活跃态的 ULT 代表绑定 KLT 的三态
4. 活跃态的 ULT 运行时可激活用户调度，非阻塞系统调用可使用 Jacketing 启动用户调度，调整活跃态 ULT

为什么是活跃态绑定 KLT 的三态？

因为如果绑定的 KLT 不再运行，则也不再运行。活跃态代表了 KLT，可能是运行态、可运行态、阻塞态

多线程实现的各种策略总结

混合式多线程合并了内核级多线程和用户级多线程的优势，甚至可以指派到 CPU，或由操作系统绑定。

Solaris 多线程技术

包含了多种情况，上图引入了轻量级线程，将轻量级线程与内核级线程映射，原来的多线程设计是 Process 2，只有一个处理进程，允许给一个进程配置超过一个处理器。

1. Process 1：单进程单线程，内核级多线程；
2. Process 2：单进程双线程，进程映射到两个轻量级线程，相当于用户级多线程；
3. Process 3：两进程三线程，内核级多线程；
4. Process 4：两进程两线程，内核级多线程；
5. Process 5：三进程四线程，混合级线程，直接做指派意味着线程非常重要，需要单独指派。

一个进程的线程可以被分发到各个位置上并行完成，处理器只能感知进程，不能感知线程，并且只会将一个处理器分配给线程（进程？），然后用户空间将得到的处理器分配给线程。

处理器调用

处理器调度层次

1. 高级调度：又称长程调度、作业调度，决定能否加入到执行的进程池中，管理从创建进程到调度运行再到结束阶段后的善后部分的全过程。
2. 中级调度，又称平衡调度、中程调度，根据内存资源情况决定内存中所能容纳的进程数目，并完成外存和内存中的进程对换工作。
3. 低级调度：又称短程调度、进程调度/线程调度，根据某种原则决定就绪队列中哪个进程/线程获得处理器，并将处理器让出给它使用。

处理器调度层次与进程状态转换

这个说明录入各级调度和七态模型的情况，三个框分别表明不同调度层次，如上图所示。资源紧张时挂起，资源空闲时解挂

处理器调度层次与关键状态转换

高级调度

在分时操作系统中，高级调度决定：

1. 是否接受一个终端用户的连接
2. 命令能否被系统接纳并构成进程
3. 新建态进程是否加入就绪进程队列

批处理 OS 中，高级调度又称为作业调度，功能是按照某种原则从后备作业队列中选取作业进入主存，并为作业做好运行前的准备工作和完成后的善后工作

中级调度

1. 引进中级调度是为了提高内存利用率和作业吞吐量
2. 中级调度决定哪些进程被允许驻留在主存中参与竞争处理器及其他资源，起到短期调整系统负荷的作用
3. 中级调度把一些进程换出主存，从而使之进入“挂起”状态，不参与进程调度，以平顺系统的负载

低级调度

1. 低级调度：又称处理器调度、进程调度、短程调度，按照某种原则把处理器分配给就绪态进程或内核级线程
2. 进程调度程序：又称分派程序，操作系统中实现处理器调度的程序，是操作系统的最核心部分
3. 处理器调度策略的优劣直接影响到整个系统的性能，这个进程被很多操作系统称为 0 号进程，所有进程的父进程

低级调度的主要功能：

1. 负责记录进程或内核级线程的状态
2. 决定某个进程或内核级线程什么时候获得处理器以及占用时间
3. 将处理器分配给进程或内核级线程
4. 回收处理器。

综述三级调度

一般操作系统都配置了高级调度和低级调度，而功能完善的操作系统为了提高内存利用率和作业吞吐率引进了中级调度。

因此，从处理器调度的层次来讲，可以划分为三级调度模型和两级调度模型。

CPU 从进程到进程的切换

内核态进程占用时间不应该过多，应当尽量避免频繁的模式切换

1. 正向切换（从用户态转换到内核态）：Trap、系统调用、中断
2. 反向切换（从内核态转换到用户态）：ret

进程抽象

我们需要不断完善中断处理子系统，内核态是将特权指令和非特权指令混搭使用。

处理器调度算法

选择处理器调度算法的原则

在以下的五个方面进行巧妙的平衡来完成操作系统的设计。

1. 资源利用率：使得 CPU 或其他资源的使用率尽可能高且能够并行工作

\[ \begin{aligned} &\text{CPU 利用率} = \frac{\text{CPU 有效工作时间}}{\text{CPU 总运行时间}} \\ &\text{CPU 总运行时间} = \text{CPU 有效工作时间} + \text{CPU 空闲等待时间} \\ \end{aligned} \]

2. 吞吐量：单位事假内 CPU 处理作业的个数，服务器的 TPS，例如 12306 或淘宝
3. 公平性：确保每个用户每个进程获得合理的 CPU 份额或其他资源份额
4. 响应时间：
   1. 使交互式用户的响应时间尽可能小，或尽快处理实时任务
   2. 细分包含输入的程序命令传送到 CPU 时间、CPU 处理请求命令的时间、处理所形成的响应回送到终端显示器的时间。
5. 周转时间：提交给系统开始到执行完成获得结果为止的这段时间间隔称周转时间，应该使周转时间或平均周转时间尽可能短。

\[ \begin{aligned}&作业\: i \:周转时间\: t_i = 完成时刻\: t_f - 提交时刻\: t_s \\ &平均作业周转时间\:T = \frac{\sum\limits_{i=1}\limits^nt_i}{n}\\ &作业带权周转时间\:w_i = \frac{周转时间\:t_i}{运行时间\:t_k} \\ &平均带权做作业周转时间\:W =\frac{\sum\limits_{i=1}\limits^nw_i}{n} \end{aligned} \]

短程调度准则

与性能相关：

1. 面向用户：周转时间、响应时间、最后期限
2. 面向系统：吞吐量、处理器利用率

与性能无关：

1. 面向用户：可预测性
2. 面向系统：公平、强制优先级、平衡资源

低级调度的主要功能

1. 调度：实现调度策略，确定就绪态进程/线程竞争使用处理器的次序的裁决原则。
2. 分派：实现调度机制，确定如何时分复用 CPU，处理上下文切换，完成进程/线程同 CPU 的绑定以及放弃的实际工作

调度的模式

1. 抢占式（剥夺式）调度：当前正在运行的进程可能被操作系统中断，并转移到就绪态。处理器剥夺原则：
   1. 高优先级进程/线程可剥夺低优先级进程/线程。
   2. 运行进程/线程时间片用完后被剥夺。
2. 非抢占式（非剥夺式）调度：一个进程一旦处于运行态，它就不断执行直到终止，或者为等待 I/O 或请求某些操作系统服务而阻塞自己。
3. 与非抢占式调度相比，抢占式调度可能会导致较大的开销，但是可能对所有进程提供更好的服务，可以避免任何一个进程独占处理器太长时间

优先级调度算法

1. 操作系统往往无法判断进程会使用 CPU 多久，所以现代操作系统一般会使用时间片轮转来完成调度。
2. 排列论：随机过程（Stochastic Process，Markor）

根据分配给进程的优先级决定运行进程

1. 抢占式（Preemptive）优先级调度算法，出现高优先级则中断，抢占一定是从运行态到就绪态的转换，抢占点的安排可能不一样，在实时系统中将抢占点提前，不等一个进程使用完时间片，而是新进程到达就发生抢占，或者时间片用完抢占。
2. 非抢占式（non-preemptive）优先级调度算法，出现 CPU 空闲再选择。

优先级的确定准则

1. 进程负担任务的紧迫程度
2. 进程的交互性
3. 进程使用外设的频度：使用外设的优先
4. 进程进入系统的时间长短：公平性和周转的问题

调度算法分类

1. FCFS（先来先服务）非抢占
2. RR（时间片轮转）抢占
3. SPN（最短进程优先）非抢占，真正操作系统没有办法使用
4. SRT（最短剩余时间优先）抢占，真正操作系统没有办法使用
5. HRRF（最高响应比优先）非抢占，真正操作系统没有办法使用
6. Feedback（多级反馈调度）抢占

与进入系统时间相关的优先级

1. 计算时间短（作业/进程）优先
2. 剩余计算时间短进程优先：商业操作系统可以这么处理，但是别的可能有一定的问题。
3. 响应比高者（作业/进程）优先：

\[ \begin{aligned} &响应比 = \frac{等待时间 + 期待服务时间}{期待服务时间}\\ &\qquad\qquad = 1 + \frac{等待时间}{期待服务时间} \\ \end{aligned} \]

4. 先来先服务：先进队先被选择：多用于高级调度；低级调度中，以计算为主的进程过于优越

具体调度算法

优先级调度

1. 调度器总是选择优先级较高的进程，提供多个就绪队列（一组就绪队列），代表各个级别的优先级。
2. 低优先级的进程可能很难被执行到？一个进程的优先级应该随着它的时间或执行的历史而变化。
3. 如果就绪队列中出现优先级高的进程/线程，系统可以预先规定策略为非剥夺式和剥夺式策略。
4. 优先级的确定
   1. 用户给出优先级
   2. 系统综合考虑各因素，包括打开文件数、资源申请情况等等
5. 优先级确定方式
   1. 静态：生命周期内不改变，容易造成饥饿问题。
   2. 动态：生命周期内可能会发生改变，正在运行的进程逐渐降低优先级，正在等待的进程逐渐提高优先级。

FCFS 先来先服务

1. 当某个进程就绪时，就加入就绪队列（ready queue），当前正在运行的进程停止执行时，选择在就绪队列到达时间最长的进程运行
2. 平均作业周转时间与作业提交和调度顺序有关。
3. 两个弊端
   1. 一个短进程可能不得不等待很长时间才能获得执行，导致吞吐率很难提高，加权中转时间会上升，最差的情况就是计算型死循环，导致完全无法调度。
   2. 偏袒计算为主的进程：I/O 多的进程不得不等待计算为主的进程做完，因为需要等待资源，离开后需要重新排队。
4. 性能会非常差，不被现在的操作系统使用。
5. 先来先服务算法示例：

6. 平均作业周转时间\(T + \frac{3 + 7 + 9 + 12 + 12}{5} = 8.6\)
7. 平均带权作业周转时间\(T + \frac{\frac{3}{3} + \frac{7}{6} + \frac{9}{4} + \frac{12}{5} + \frac{12}{2}}{5} \approx 2.563\)

SPN 最短进程优先

1. SPN 是一种非抢占式调度，会选择处理时间最短的进程，短进程将会越过长进程，优先获得调度，又称为 SJF。

2. 平均作业周转时间 \(T = \frac{3 + 7 + 11 + 14 + 3}{5} = 7.6\)
3. 平均带权作业周转时间 \(W = \frac{\frac{3}{3} + \frac{7}{6} + \frac{11}{4} + \frac{14}{5} + \frac{3}{2}}{5} \approx 1.843\)
4. 问题：
   1. 需要预知作业所需的 CPU 运行时间
   2. 忽略了作业的等待时间：只要持续不断地提供更短的进程，长进程就有可能饿死，同样也会服务不到。
   3. 分时、实时处理仍然不理想。

SRT 最短剩余时间优先

最短剩余时间优先（Shortest Remaining Time，SRT）。

1. SRT 是一种抢占式调度，调度器总是选择预期剩余时间更短的进程
2. 当一个新进程加入就绪队列，他可能比当前运行的进程具有更短的剩余时间，只要新进程进入就绪队列，调度器就可能抢占当前正在运行的进程

3. 平均等待时间\(=\frac{(3 - 3 - 0) +(15 - 6 - 2) +(8 - 4 - 4) +(20 - 5 - 6) +(10 - 2 - 8)}{5} = 3.2\)
4. 平均周转时间\(=\frac{(3 - 0) +(15 - 2) +(8 - 4) +(20 - 6) +(10 - 8)}{5} = 7.2\)

HRRN 最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）

1. 非抢占式算法，性能略差与 SPN（SJF）
2. 选择响应比最高的进程：出发点是兼顾公平，对于短进程有利
3. 每当需要调度时，计算出所有的响应比，选择最高的。

\[ \begin{aligned} &响应比 = \frac{等待时间 + 期待服务时间}{期待服务时间}\\ &\qquad\qquad = 1 + \frac{等待时间}{期待服务时间} \\ \end{aligned} \]

时刻	A	B	C	D	E
0 时刻	\(1\)	未到	未到	未到	未到
3 时刻	完成	\(1 + \frac{1}{6} \approx 1.17\)	未到	未到	未到
9 时刻	完成	完成	\(1 + \frac{5}{4} = 2.25\)	\(1 + \frac{3}{5} = 1.6\)	\(1 + \frac{1}{2} = 1.5\)
13 时刻	完成	完成	完成	\(1 + \frac{7}{5} = 2.6\)	\(1 + \frac{5}{2} = 3.5\)
15 时刻	完成	完成	完成	\(1 + \frac{12}{5} = 3.4\)	完成

RR 时间片轮转调度算法

1. 本质也是先来先服务，但是要按照时间片来进行调度。
2. 根据各个进程进入就绪队列的时间先后轮流占有 CPU 一个时间片，基于时钟做抢占式调度。
3. 时间片中断：以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列队尾，然后基于 FCFS 策略选择下一个就绪进程运行
4. 时间片的确定：选择长短合适的时间片，一般为 10ms 到 200ms
   1. 过长则退化为先来先服务算法
   2. 过短则调度开销显著增大
5. 时间片分为单时间片、多时间片和动态时间片三种
6. 使用时间片轮转调度算法，在给一个进程分配处理器的时候，不需要知道进程需要多长时间
7. 很多的调度都会结合时间片轮转调度算法来实现
8. 如果时间片还没有用完就已经完成了进程的事务，那么就立即释放时间片，调度下一个进程进入占用新的时间片运行。

使用情况

1. 先进先出/最短时间/剩余时间/响应比优先算法，无法判断进程需要占用多长时间的 CPU
2. 有预估时间的调度，用在作业调度、云计算调度中比较合适，在低级调度中不合适

进程分类

1. 以计算为主的进程：不需要内核参与，没有从运行态到阻塞态的情况，如果出现死循环进程也必须要遵循时间片轮换，如果进程比较多，就可以淡化死循环的影响。
2. I/O（外设）频繁的进程：发生运行态到阻塞态的可能性比较大，根据各个进程进入就绪队列的时间先后轮流占用 CPU 一个时间片，时间片到即发生时间片中断。

时间片轮转调度算法示例

务必关注就绪队列。

MLFQ 多级反馈调度

多级反馈调度（Multi-level Feedback Queue，MLFQ），又称分级调度。

基本思想：

1. 建立多个不同优先级的就绪进程队列；
2. 多个就绪进程队列之间按照优先级调度；
3. 高优先级的就绪进程，分配的时间片短；
4. 单个就绪进程队列中的进程的优先级和时间片相同，按照先来先服务算法调度。

q = 1 时的多级反馈调度的示例

当一个进程第一次进入系统时，它被放置在 RQ0，当它第一次被抢占后并返回就绪状态时，它被放置在 RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。

注意：当只有 A 一个进程在运行而没有其他进程等待时，A 会始终占用处理器，直到被抢占进入下一级队列；而不是每到时间片用完时就进入下一队列。

q = 2ⁱ 时的多级反馈调度的示例

当一个进程第一次进入系统时,它被放置在 RQ0，当它第一次被强占后并返回就绪状态时，它被放置在 RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。

多级反馈调度的示意图

1. 如果没有进程竞争，那么会不会导致进程掉下去，根据具体情况分析，可能掉下去也可能没有掉下去。
2. 此时 RQ0 是 A，RQ2 是 C，当前 A 在做，那么 A 掉下来后是运行 A 还是 C，可以考虑运行 A 进程：因为掉到了 RQ1，也可以考虑运行 C 进程，具体情况要看操作系统时间中的细节
3. 刚好做完的时刻，B 同步进入也需要细规则来完善。

分级原则

外设访问、交互性、时间紧迫程度、系统效率、用户立场

现代操作系统的实现模型

1. 多个高优先级的实时进程队列，如：硬实时、网络、软实时
2. 多个分时任务的进程队列，根据基准优先级和执行行为调整
3. 队列数可能多达 32-128 个

1. 如果没做完会惩罚降级，做题目要至少画一下前几个 RQ。如果进程掉出去的同时，有新的进程进入，那么新的进程优先进入就绪队列
2. 对以计算为主的长进程不友好，就绪队列越深获得调度的机会越小
3. 不同的进程可以设置不同的时间片长度：q = 2ⁱ，i 是层数，所以第一层时间片长为 1，第二层长为 2
4. 多级队列更能够发现先到达的，时间片比较短的处理完。
5. 除了极少数的硬实时操作系统使用抢占式调度算法，绝大多数操作系统有效地组合时间片调度算法和优先级调度算法，采用分级调度算法的策略加以实现
6. 如果没有竞争不掉下去，时刻 1（根据考试具体情况决定）

彩票调度算法

1. 基本思想：为进程发放针对系统各种资源（如 CPU 时间）的彩票；当调度程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源
2. 功能比保证调度好的多，服务器和客户：客户需要调用服务器服务，则将彩票交给服务器
3. 合作进程之间的彩票交换
4. 一般不会在实时操作系统中使用，但是可以在服务器端进行使用，特别是视频点播服务器

传统 Unix 系统的调度（例）

1. 多级反馈队列，每个优先级队列使用时间片轮转
2. 每秒重新计算每个进程的优先级
3. 给每个进程赋予基本优先级的目的是把所有进程划分成固定的优先级区
4. 可控调节因子

Unix SVR4 调度算法（例）

1. 100-159 是实时部分任务

2. 60-99 是内核部分任务

3. 0-59 是分时部分任务

4. 多级反馈队列，每一个优先级都对应于一个就绪进程队列

   1. 实时优先级层次：优先级和时间片都是固定的，在抢占点执行抢占
   2. 分时优先级层次：优先级和时间片是可变的，从 0 优先级的 100ms 到 59 优先级的 10ms

Bands

优先级递减：对换、块 I/O 设备控制、文件操作、字符 I/O 设备控制、用户进程

Windows 调度算法（例）

1. 主要设计目标：基于内核级线程的可抢占式调度，向单个用户提供交互式的计算环境，并支持各种服务器程序
2. 优先级和优先级
3. 实时优先级层次（优先级为 31-16）：用于通信任务和实时任务，优先级不可变
4. 可变优先级层次（优先级为 15-0）：用于用户提交的交互式任务，优先级可动态调整
5. 多级反馈队列，每一个优先级都对应于一个就绪进程队列
6. 优先级可动态调整原则
   1. 线程所属的进程对象有一个进程基本优先级，取值范围从 0 到 15
   2. 线程对象有一个线程基本优先级，取值范围从-2 到 2
   3. 线程的初始优先级为进程基本优先级加上线程基本优先级，但必须在 0 到 15 的范围内
   4. 线程的动态优先级必须在初始优先级到 15 的范围
7. 当存在 N 个处理器时，N-1 个处理器上将运行 N-1 个最高 先级的线程，其他线程将共享剩下的一个处理器

批处理作业的调度

批处理作业的管理

1. 作业说明语言和作业说明书
2. 脱机控制方式（批处理控制方式）
3. 作业控制块 JCB
4. 作业状态
   1. 输入状态：作业正在从输入设备上预输入信息
   2. 后备状态：作业预输入结束但尚未被选中执行
   3. 执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行
   4. 完成状态：作业运行结束，正在等待缓输出
5. 作业默认所有的资源调度都是静态调度（静态分配）完成的，输出井来完成。

批处理作业的状态作业调度与进程调度

1. 作业调度：按一定的策略选取若干个作业让它们进入内存、构成进程去竞争处理器以获得运行机会
2. 用户立场：自己作业的周转时间尽可能的小
3. 系统立场：希望进入系统的作业的平均周转时间尽可能的小
4. 适当的作业调度算法必须既考虑用户的要求又有利于系统效率的提高

补充

习题（进程管理的 fork 系统调用）

1. fork 会克隆出一个新的进程，但是是同一个 PC，也就是从父进程的当前步骤开始往下做
2. 第一次 fork A \(\to\) B
3. 第二次 fork A \(\to\) C, B \(\to\) D
4. 到三次 fork A \(\to\) E, B \(\to\) F, C -> G, D -> H

阿里云平台

1. 章文嵩：Linux 集群，LVS，尽量节能
2. 使用了灵动处理器