一、进程与线程

1、进程的概念与特征

（1）进程的定义

• 进程是程序的一次执行过程

• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动

• 进程是具有独立功能的程序在一个数据集合上运行的过程

• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

• 为什么引入进程：
• 为了使多道程序并发执行，提高资源利用率和系统吞吐量
• 为了可以对并发执行的程序加以描述和控制，实现操作系统的并发性和共享性

（2）进程的特征

• 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的【最基本的特征】

• 并发性：内存中有多个进程实体，各进程可并发执行

• 独立性：进程是能独立运行、获得资源、独立接受调度的基本单位

• 异步性：各进程按各自独立的、不可预知的速度向前推进【操作系统要提供“进程同步机制”来解决异步问题】

（3）进程与程序的区别

• 进程：是动态的，是程序的一次执行过程【如：可同时启动多次 QQ】

• 程序：是静态的，就是存放在磁盘里的可执行文件【如：QQ.exe】

• 同一个程序多次执行会对应多个进程

（4）进程的组成

• 一个进程实体（进程映像）由 PCB、程序段、数据段组成

• 进程是动态的，进程实体是静态的

• 进程实体反映了进程在某一时刻的状态

• 定义：
• PCB 是进程实体的一部分，是进程存在的唯一标志
• 进程创建时，操作系统为它新建一个 PCB，该结构常驻内存

• 包含：
1. 进程描述信息：
• 进程标识符 PID：标识各个进程，每个进程都有一个并且唯一的标识号
• 用户标识符 UID：进程归属的用户，用户标识符主要为共享和保护服务
2. 进程控制和管理信息：
• 进程当前状态：描述进程状态信息，作为 CPU 调度的依据
• 进程优先级：描述进程抢占 CPU 的优先级
• 代码运行入口地址
• 程序的外存地址
• 进入内存时间
• CPU 占用时间
• 信号量使用
3. 资源分配清单：
• 有关内存地址空间和虚拟地址空间的状况
• 所打开文件的列表和所使用的输入/输出设备信息
4. 处理机相关信息【CPU 的上下文】：
• CPU 中各寄存器的值
• 当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中以便进程重新执行时，能从断点处继续执行

• 组织方式：
• 链接方式：
• 把同一状态的 PCB 链成一个队列，不同状态对应不同的队列
• 也可把处于阻塞态的进程的 PCB，根据阻塞原因，排成多个阻塞队列
• 索引方式：
• 将同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB
• 如就绪索引表，阻塞索引表

2）程序段

• 能被进程调度程序调度到 CPU 执行的程序代码段

• 程序可以被多个进程共享，即多个进程可以运行同一个程序

3）数据段

• 可以是进程对应的程序加工处理的原始数据

• 可以是程序执行时产生的中间或最终结果

2、进程的状态与转换

（1）五种状态

• 运行态 Running：该时刻进程占用 CPU

• 就绪态 Ready：进程获得了除处理机外的一切所需资源，一旦得到处理机，就可以立即运行

• 阻塞态 Blocked：该进程正在等待某一事件发生而暂停运行，如等待某个资源可用（不包括 CPU）或等待 I/O 完成

• 创建态 New：进程正在被创建时的状态

• 结束态 Exit：进程正在从系统中消失时的状态

（2）状态转换

3、进程控制

• 进程控制：主要功能是对系统中的所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能

• 原语：进程控制用的程序段【执行期间不允许中断，是一个不可分割的基本单位】
• 可以用 “关中断指令”和“开中断指令”这两个特权指令实现原子性

（1）进程的创建

1）定义及过程

• 允许一个进程创建另一个进程

• 允许子进程继承父进程所拥有的资源

• 创建原语：
• 为新进程分配一个进程标识号，申请一个空白的 PCB【PCB 是有限的】
• 为该进程分配运行时所必需的资源，如内存、文件、I/O 和 CPU 时间等
• 初始化 PCB，如标志、状态、控制、优先级信息
• 将 PCB 插入就绪队列

2）对应事件

• 用户登录：分时系统中，用户登录成功，系统会为其建立一个新的进程

• 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程

• 系统提供服务：用户向操作系统提出某些请求时，会建立一个进程处理该请求

• 用户程序的应用：由用户进程主动请求创建一个子进程

• 注意：设备分配不需要创建进程

（2）进程的终止

1）定义及过程

• 当子进程被终止时，其在父进程处继承的资源应当还给父进程

• 当父进程被终止时，该父进程的子进程就变为孤儿进程

• 终止原语：
• 查找需要终止的进程的 PCB
• 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程
• 如果其还有子进程，全部终止
• 将该进程所拥有的全部资源都归还给操作系统
• 将其从 PCB 所在队列中删除

2）对应事件

• 正常结束：进程任务完成并自己准备退出运行

• 异常结束：进程运行时发生了异常事件

• 外界干预：如操作系统干预、父进程请求或父进程终止

（3）进程的阻塞

1）定义及过程

• 当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待

• 一旦被阻塞等待，只能由另一个进程唤醒

• 阻塞原语：
• 找到将要被阻塞进程标识号对应的 PCB
• 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
• 将该 PCB 插入到阻塞队列中去

2）对应事件

• 需要等待系统系统分配某种资源

• 需要等待相互合作的其他进程完成工作

（4）进程的唤醒

1）定义及过程

• 进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成

• 处于阻塞状态的进程是绝对不可能叫醒自己

• 如果某进程正在等待 I/O 事件，需由别的进程发消息给它

• 只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它

• 唤醒原语：
• 在该事件的阻塞队列中找到相应进程的 PCB
• 将其从阻塞队列中移出，并置其状态为就绪状态
• 把该 PCB 插入到就绪队列中，等待调度程序调度

• 注意：阻塞原语和唤醒原语必须成对使用

2）对应事件

• 等待的事件发生

4、进程通信

• 进程通信：指进程之间的信息交换

• 各进程拥有的内存地址空间相互独立

• 为了保证安全，一个进程不能直接访问另一个进程的地址空间 #### （1）低级通信方式

• PV 操作 #### （2）高级通信方式 ##### 1）共享存储

• 设置一个共享内存区域，并映射到进程的虚拟地址空间

• 要互斥地访问共享空间【通信进程自己负责实现】

• 基于数据结构的共享：
• 比如共享空间里只能放一个长度为 10 的数组
• 速度慢、限制多
• 是一种低级通信方式

• 基于存储区的共享：
• 操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统
• 灵活性高、速度快
• 是一种高级通信方式

2）信息传递

• 进程间的数据交换以格式化的消息（Message）为单位

• 进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换

• 隐藏了通信实现细节，对用户透明，简化了通信程序的设计

• 应用最广泛

• 直接通信方式：发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从队列取得消息

• 间接通信方式：发送进程将消息发送给某个中间实体【信箱】

3）管道通信

• 管道只能采用半双工通信，某一时间段内只能实现单向的传输【如果要实现双向同时通信，则需要设置两个管道】

• 各进程要互斥地访问管道【由操作系统实现】

• 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程

• 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程

• 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱，解决方案：
1. 一个管道允许多个写进程，一个读进程
2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）

• 管道是一种特殊文件，可以克服使用文件通信的两个问题：
1. 限制管道的大小：管道文件是一个固定文件大小的缓冲区
2. 读进程也可能工作得比写进程快

• 管道只能由创建进程访问【子进程可继承父进程的管道，并可用它来与父进程通信】

• 从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据

5、线程和多线程模型

（1）线程的基本概念

• 线程可理解为轻量级进程

• 线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位

• 引入线程后的变化：
• 并发性：进程内的各线程之间也可以并发，从而进一步提升了系统的并发度
• 资源分配、调度：进程是资源分配的基本单位，线程是处理机调度的基本单位
• 系统开销：线程间并发，如果是同一进程内的切换，则不需要切换进程环境，系统开销小

• 多 CPU 计算机中，各个线程可占用不同的 CPU

• 每个线程都有一个唯一的标识符和一个线程控制块【记录线程执行的寄存器和栈等现场状态】

• 不同的线程可以执行相同的程序

• 线程也有就绪、阻塞、运行三种基本状态，和进程之间的转换是一样的

• 线程共享进程地址空间和资源，线程自己没有独立的地址空间

（2）线程的组成和控制

1）线程控制块 TCB

• 功能：每个线程配置一个 TCB，用于记录控制和管理线程的信息

• 组成：
• 线程标识符
• 一组寄存器，包括程序计数器、状态寄存器和通用寄存器
• 线程运行状态
• 优先级
• 线程专有存储区，线程切换时用于保存现场
• 堆栈指针，用于过程调用时保存局部变量及返回地址

2）线程的控制

• 创建线程：
• 用户程序启动时，通常仅有一个称为初始化线程的线程正在执行，其主要功能是用于创建新线程

• 终止线程：
• 通常，线程被终止后并不立即释放它所占有的资源，只有当进程中的其他线程执行了分离函数后，被终止线程才与资源分离，此时的资源才能被其他线程利用
• 被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行

（3）线程的实现方式

1）用户级线程（ULT）

• 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）

• 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预

• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在【“用户级线程”就是“从用户视角看能看到的线程”】

• 对设置了用户级线程的系统，其调度仍是以进程为单位，各个进程轮流执行一个时间片

• 优点：
• 线程切换不需要转到内核空间，节省了模式切换的开销
• 调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法
• 与操作系统平台无关，对线程管理的代码是属于用户程序的一部分

• 缺点：
• 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
• 不能发挥多 CPU 的优势，内核每次分配给一个进程的仅有一个 CPU，因此进程中仅有一个线程执行

• 形成多对一模型

2）内核级线程（KLT）

• 内核级线程的管理工作由操作系统内核完成

• 内核级线程的切换必然需要在核心态下才能完成

• 操作系统会为每个内核级线程建立相应的TCB，通过 TCB 对线程进行管理【“内核级线程”就是“从操作系统内核视角看能看到的线程”】

• 优点：
• 能发挥多 CPU 的优势，内核能同时调度同一进程的多个线程并行执行
• 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用 CPU，也可以运行其他进程中的线程
• 内核支持线程具有很小的数据结构和栈，线程切换快、开销小
• 内核本身也可采用多线程技术，可以提高系统的执行速度和效率

• 缺点：
• 同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大【用户进程的线程在用户态执行，而线程调度和管理是在内核实现】

• 形成一对一模型

3）组合方式

• 内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程

• 用户级线程通过时分多路复用内核线程实现

• 结合 KLT 和 ULT 的优点，又克服各自的不足

• 线程库：为程序员提供创建和管理线程的 API，实现方法：
• 在用户空间中提供一个没有内核支持的库【调用库内的一个函数只导致用户空间中的一个本地函数的调用】
• 实现由操作系统直接支持的内核级的一个库【调用库中的一个 API 函数通常会导致对内核的系统调用】

• 形成多对多模型 #### （4）多线程模型

• 由于用户级线程和内核级线程的连接方式不同，从而形成了三种不同的多线程模型

• 操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位 ##### 1）多对一模型

• 定义：多个用户级线程映射到一个内核级线程，且一个进程只被分配一个内核级线程

• 优点：
• 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

• 缺点：
• 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
• 任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个CPU 上运行

2）一对一模型

• 定义：一个用户级线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程

• 优点：
• 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强
• 多线程可在多核处理机上并行执行

• 缺点：
• 每创建一个用户线程，就要创建一个对应的内核线程，开销大
• 线程切换由操作系统内核完成，需要切换到核心态，线程管理的成本高，开销大

3）多对多模型

• 定义：n 用户及线程映射到 m 个内核级线程（n >= m），每个用户进程对应 m 个内核级线程。

• 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

• 用户级线程是“代码逻辑”的载体

• 内核级线程是“运行机会”的载体

• 一段“代码逻辑”只有获得了“运行机会”才能被CPU 执行

• 内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有所有内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

二、CPU 调度

1、调度的概念

（1）基本概念

• 调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将 CPU 分配给它运行，以实现进程并发地执行

• CPU 调度是多道程序操作系统的基础，是 OS 设计的核心问题

（2）调度的层次

2）中级调度（内存调度）

• 目的：提高内存利用率和系统吞吐量

• 将暂时不能运行的进程调到外存等待，设为挂起态

• 当具备运行条件且内存稍有空闲时，重新调入内存，修改状态为就绪态，挂在就绪队列上

• 是存储器管理中的对换功能

3）低级调度（进程调度）

• 从就绪队列中选取一个进程，调用频率很高

• 各种 OS 都必须配置这种调度

4）三种调度的联系

2、调度的实现

（1）调度程序（调度器）

• 调度程序：用于调度和分配 CPU 的组件

• 组成：
• 排队器：按策略将就绪进程排成一个或多个队列
• 分派器：从就绪队列中取出进程，并分配 CPU
• 上下文切换器：在对处理机进行切换时，会发生两对上下文的切换：
• 第一对：将当前进程的上下文保存到 PCB 中，再装入分派程序的上下文，以便分派程序运行
• 第二对：移出分派程序的上下文，将选新进程的 CPU 现场信息装入 CPU 的各个相应寄存器

（2）调度的时机

1. 需要进行进程调度与切换的情况：
• 当前运行的进程主动放弃处理机：
• 进程正常终止
• 运行过程中发生异常而终止
• 进程主动请求阻塞（如等待 I/O）
• 当前运行的进程被动放弃处理机：
• 分给进程的时间片用完
• 有更紧急的事需要处理（如 I/O 中断）
• 有更高优先级的进程进入就绪队列

2. 不能进行进程调度与切换的情况：
• 在处理中断的过程中【中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换】
• 进程在操作系统内核程序临界区中【内核程序临界区一般是用来访问某种内核数据结构的，若不尽快释放访问的临界资源，可能会影响到 OS 内核的其他管理工作】
• 在原子操作过程中（原语）

（3）进程调度的方式

1. 非抢占调度方式【非剥夺方式】：只允许进程主动放弃处理机
• 优点：实现简单，系统开销小，适用于早期的批处理系统
• 缺点：不适合分时和大多数的实时系统

2. 抢占调度方式【剥夺方式】：当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程
• 优点：提高系统吞吐率和响应率
• 缺点：必须遵循一定的原则（优先权、短进程优先、时间片原则等）

（4）进程的切换与过程

• 狭义的进程调度：从就绪队列中选中一个要运行的进程【这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换】

• 广义的进程调度：包含了选择一个进程和进程切换两个步骤，进程切换的过程主要完成了：
1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

• 闲逛进程：
• 在进程切换时，如果系统中没有就绪进程，就会调用闲逛进程一直运行【PID 为 0】，并在指令周期后测试中断
• 优先级最低，只要有进程就绪，就会立即让出 CPU
• 不需要 CPU 之外的资源，不会被阻塞

（5）两种线程的调度

• 用户级线程调度：
• 内核不知道线程的存在，选择一个进程，并给予时间控制
• 由进程中的调度程序决定哪个线程运行
• 线程切换在同一进程中进行，仅需少量的机器指令

• 内核级线程调度：
• 内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程
• 超过时间片，强制挂起该线程
• 需要完整的上下文切换、修改内存映像、使高速缓存失效，导致若干数量级的延迟

3、进程的上下文切换

（1）基本概念

• 进程上下文切换：
• 上下文是指某一时刻CPU寄存器和程序计数器的内容
• 完成 CPU 切换到另一个进程时，保存当前进程状态并恢复另一个进程的状态的任务
• 采用进程 PCB 表示，包括寄存器的值、进程状态和内存管理信息等
• 内核将旧进程状态保存在其 PCB 中，然后加载经调度而要执行的新进程的上下文
• 进程的运行环境发生实质性变化

• 上下文切换通常是计算密集型的，需要消耗大量的 CPU 时间

• 有些处理器提供多个寄存器组，上下文切换只需要简单改变当前寄存器组的指针，不需要用到磁盘和主存

（2）上下文切换的场景

• 某个进程时间片耗尽时

• 进程在系统资源不足时，要等到资源满足后才可以运行

• 进程通过 sleep 将自己主动挂起

• 有优先级更高的基础运行时

• 发送硬件中断时

（3）上下文切换的流程

1. 挂起一个进程，保存 CPU 上下文，包括 PC 和其他寄存器

2. 更新 PCB 信息

3. 把进程的 PCB 移到相应的队列（如就绪队列，阻塞队列）

4. 加载另一个进程执行，更新其 PCB

5. 跳转到新进程 PCB 中的 PC 所指向的位置执行

6. 恢复处理机上下文

（4）上下文切换和模式切换

• 模式切换时，CPU 逻辑上可能还在执行同一进程

• 上下文切换只能发生在内核态【多任务 OS 的一个必需特性】

• 用户态与内核态之间的切换为模式切换【没有改变当前的进程】

（5）调度和切换的区别

• 先有资源的调度，才有进程的切换

• 调度：决定资源分配给哪个进程的行为；是一种决策行为

• 切换：实际分配的行为；是一种执行行为

4、调度的目标

（1）CPU 利用率

• $CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$

• $利用率=\frac{忙碌的时间}{总时间}$ 注意：计算作业完成时间时，要注意 CPU 与设备、设备与设备之间时可以并行的

（2）系统吞吐量

• 表示单位时间内 CPU 完成作业的数量

• $系统吞吐量=\frac{总共完成了多少作业}{总共花了多少时间}$

（3）周转时间

• 周转时间包括四个部分：
• 作业在外存后备队列上等待作业调度（高级调度）的时间
• 进程在就绪队列上等待进程调度（低级调度）的时间
• 进程在 CPU 上执行的时间
• 进程等待 I/O 操作完成的时间

• 后三项在一个作业的整个处理过程中，可能发生多次

• 周转时间 = 作业完成时间 − 作业提交时间

• $平均周转时间=\frac{作业1的周转时间+...+作业n的周转时间}{n}$

• $带权周转时间=\frac{作业周转时间}{作业实际运行时间}$

• $平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$

（4）等待时间

• 指进程/作业处于等待处理机状态时间之和

• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间

• 对于作业来说，等于建立进程后的等待时间 + 作业在外存后备队列中等待的时间

（5）响应时间

• 指从用户提交请求到首次产生响应所用的时间

• 在交互式系统中，一般采用响应时间作为衡量调度算法的准则之一

5、调度算法

（1）先来先服务 FCFS

1）算法思想

• 主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）

2）算法规则

• 按照作业/进程到达的先后顺序进行服务

3）用于作业/进程调度

• 用于作业调度时，考虑的是哪个作业先到达后备队列

• 用于进程调度时，考虑的是哪个进程先到达就绪队列

4）是否可抢占

• 非抢占式

5）优缺点

• 优点：
• 公平、算法实现简单
• 有利于 CPU 繁忙型作业
• 一般适用于早期批处理系统

• 缺点：
• 对长作业有利，对短作业不利【排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好】
• 不利于 I/O 繁忙型作业

6）是否会导致饥饿

• 不会

• 饥饿：某进程/作业长期得不到服务

（2）短作业优先 SJF

1）算法思想

• 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

• 每次选择当前已到达且运行时间最短的作业

2）算法规则

• 最短的作业/进程优先得到服务【要求服务时间最短】

3）用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

• 用于进程调度时称为“短进程优先（SPF, Shortest Process First）算法

4）是否可抢占

• SJF 和 SPF 是非抢占式算法

• 最短剩余时间优先算法（SRTN）是抢占式的

5）优缺点

• 优点：
• 在所有进程都几乎同时到达时，采用 SIF/SPF 调度算法的平均等待时间、平均周转时间最少
• 抢占式的 SJF/SPF 调度算法【最短剩余时间优先算法】的平均等待时间、平均周转时间最少
• 一般适用于早期批处理系统

• 缺点：
• 对短作业有利，对长作业不利
• 可能产生饥饿现象
• 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

6）是否会导致饥饿

• 会

• 如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象

• 如果一直得不到服务，则称为“饿死”

（3）高响应比优先

1）算法思想

• 综合考虑作业/进程的等待时间和要求服务的时间

2）算法规则

• 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

• $响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}$

3）用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

4）是否可抢占

• 非抢占式的算法

• 因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

5）优缺点

• 等待时间相同时，要求服务时间越短，响应比越高，有利于短作业，类似于 SJF

• 要求服务时间相同时，等待时间越长，响应比越高，类似于 FCFS

• 响应比可以随等待时间的增加而提高，克服了饥饿现象

• 适用于分时操作系统

6）是否会导致饥饿

• 不会

（4）优先级

1）算法思想

• 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

2）算法规则

• 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

3）用于作业/进程调度

• 既可用于作业调度，也可用于进程调度

4）是否可抢占

• 非抢占式：直到由于自身原因而让出 CPU 时，更高优先级的进程才可运行

• 抢占式：有更高优先级的进程进入就绪队列时，立即停止正在运行的进程
• 静态优先级：
• 优先级是在创建时确立的，在运行期间保持不变
• 优点：简单易行，系统开销小
• 缺点：不够精确，可能出现优先级低的进程长时间得不到调用
• 动态优先级：
• 优先级随进程的推进或等待时间的增加而改变，以获得更好的性能
• 系统进程 > 用户进程
• 交互型进程 > 非交互型进程（前台进程>后台进程）
• I/O 型进程 > 计算型进程

5）优缺点

• 优点：
• 用优先级区分紧急程度、重要程度，适用于实时操作系统
• 可灵活地调整对各种作业/进程的偏好程度

• 缺点：
• 若源源不断地有高优先级进程到来，则可能导致饥饿

6）是否会导致饥饿

• 会

（5）时间片轮转 RR

1）算法思想

• 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

2）算法规则

• 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100 ms）

• 若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

3）用于作业/进程调度

• 用于进程调度

• 只有作业放入内存建立了相应的进程后，才能被分配处理机时间片

4）是否可抢占

• 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法

• 由时钟装置发出时钟中断来通知 CPU 时间片已到

5）优缺点

• 优点：
• 公平，响应快
• 适用于分时操作系统

• 缺点：
• 由于高频率的进程切换，因此有一定开销
• 不区分任务的紧急程度

• 若时间片足够大：所有进程都能在一个时间片内执行完毕，退化为 FCFS

• 若时间片足够小：CPU 将在进程间过于频繁的切换，使 CPU 的开销增大

6）是否会导致饥饿

• 不会

（6）多级队列

1）算法思想

• 在系统中设置多个就绪队列

• 按不同类型或性质的进程固定分配到不同的就绪队列

• 每个队列可实施不同的调度算法

• 在多 CPU 系统中，可以很方便为每个 CPU 设置一个单独的就绪队列

（7）多级反馈队列

1）算法思想

• 对其他调度算法的折中权衡

2）算法规则

1. 设置多级就绪队列，赋予每个队列不同的优先级【第 1 级队列最高，依次降低】

2. 赋予各个队列的进程运行时间片的大小各不相同【优先级越高的队列，每个进程的时间片越小】

3. 每个队列采用 FCFS 算法：
• 新进程进入内存后，首先放入第 1 级队列的队尾，等待调度
• 在第一个时间片结束时尚未完成，将其转入第 2 级队列的末尾，依次类推
• 当进程被降到第 n 级队列后，采用时间片轮转方式运行

4. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片

3）用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

4）是否可抢占

• 抢占式的算法

• 在 k 级队列的进程运行过程中，若更上级的队列（1~k-1 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾

5）优缺点

• 对各类型进程相对公平（FCFS 的优点）

• 每个新到达的进程都可以很快就得到响应（RR 的优点）

• 短进程只用较少的时间就可完成（SPF 的优点）

• 不必实现估计进程的运行时间（避免用户作假）

• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程

• 拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样I/O 型进程就可以保持较高优先级

6）是否会导致饥饿

• 会

（8）常见算法的对比

三、同步与互斥

1、基本概念

• 因为并发进程是异步的，为了协调进程之间的相互制约关系，所以引入同步互斥

• 同步【直接制约关系】：
• 指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系

• 互斥【间接制约关系】：
• 当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许访问临界资源

• 临界资源：一次仅允许一个进程使用的资源，对其访问过程分为：
• 进入区：负责实现互斥，设置标志
• 临界区：进程中访问临界资源的那段代码
• 退出区：负责实现互斥，清除标志
• 剩余区：代码中的其余部分

• 同步机制应遵循的准则：
• 空闲让进：临界区空闲，允许一个进程进入【运行进程访问空闲的临界资源】
• 忙则等待：有进程进入临界区时，其他进程需等待【两个进程不能同时进入临界资源】
• 有限等待：请求访问的进程应保证在有限时间内进入临界区，防止无限等待【进程等待进入临界区的时间是有限的】
• 让权等待【原则上遵循，非必须】：进程不能进入临界区时，应该立即释放处理器，防止进程忙等待【不能进入临界区的执行态进程立即放弃 CPU】

2、实现临界区互斥的方法

（1）软件实现方法

1）单标志法

• 设置一个公用整型变量 turn，指示允许进入临界区的进程编号

• 每次只允许一个进程进入临界区

• 违背“空闲让进”

2）双标志先检查法

• 设置一个布尔型数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿

• 违背“忙则等待”【进入区“检查”后，“上锁”前可能发生进程切换】

3）双标志后检查法

• 先“上锁”，后“检查”，避免上诉问题

• 解决“忙则等待”

• 违反“空闲让进”和“有限等待”，会导致饥饿现象

4）Peterson 算法

• 利用 flag 解决互斥访问问题，利用 turn 解决饥饿问题

• 违反“让权等待”

（2）硬件实现方法

1）中断屏蔽法

• 关中断：防止其他进程进入临界区

• 优点：简单、高效

• 缺点：
• 限制了 CPU 交替执行程序的能力，因此系统效率会明显降低
• 不适用于多处理机
• 只适用于操作系统内核进程，不适用于用户进程【因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险】

2）硬件指令——TestAndSet 指令（TS 指令）

• 为每个临界资源设置一个共享布尔变量 lock，表示该资源的两种状态【true 表示被占用】

• 若刚开始 lock 是 false，则 TS 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区

• 若刚开始 lock 是 true，则执行 TS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”

• 优点：
• 实现简单，TS 指令将“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作
• 适用于多处理系统

• 缺点：不满足“让权等待”原则

3）硬件指令——Swap 指令（XCHG 指令）

• 为每个临界资源设置一个共享布尔变量 lock，初值 false

• 在每个进程中设置一个局部变量 key，初值 trur，用于与 lock 交换信息

• 优点：
• 简单，容易验证其正确性
• 适用于多处理机系统
• 支持系统中有多个临界区，只需为每个临界区设立一个布尔变量

• 缺点：
• 不满足“让权等待”原则
• 从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，导致饥饿

3、互斥锁

• 是解决临界区最简单的工具

• 通常采用硬件机制实现

• 获得锁：acquire，释放锁：release，都是原子操作

• 使用互斥锁解决经典同步问题

• 优点：
• 进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高
• 适用于多处理系统

• 缺点：忙等待，违反“让权等待”

4、信号量

（1）PV 操作定义

• 信号量：表示系统中某种资源的数量

• P 操作【wait() 原语】：将信号量值 S 减 1，表示申请占用一个资源

• V 操作【signal() 原语】：将信号量值 S 加 1，表示释放一个资源，即使用完资源后归还资源

（2）信号量分类

1）整型信号量

• 该信号量被定义为一个用于表示资源数目的整型量 S

• 该机制不遵循“让权等待” 的准则【只要 s≤0，就会不断循环测试】

2）记录型信号量

• 需要一个用于代表资源数目的变量 value

• 需要一个进程链表 L，用于链接所有等待该资源的进程

• S.value 的初值表示系统中某种资源的数目

• P 操作【wait () 原语】：
• 如果 S.value<0，表示已经没有可用资源，则进程调用block原语进行自我阻塞【运行态 —> 阻塞态】，主动放弃处理机，并插入该类资源的 S.L
• 遵循“让权等待”

• 举例：当信号量的值为 2 时，表示有 2 个资源可以使用；当信号量的值为-2 的时候，表示有两个进程正在等待使用这个资源

• V 操作【signal () 原语】：
• 如果加 1 后 S.value≤0，表示仍有进程正在等待该资源，调用 wakeup 原语唤醒 S.L 中的第一个进程【阻塞态 —> 就绪态】

（3）信号量的应用

1）利用信号量实现互斥

• 互斥信号量 S 初始值=1，表示临界区只允许一个进程进入，从而实现互斥

• 把对临界资源的访问操作置于 P (S) 和 V（S）之间

• P 操作和 V 操作必须成对出现

• 缺少 P 操作：不能保证对临界资源的互斥访问

• 缺少 V 操作：导致临界资源永远得不到释放，使因等待该资源而阻塞的进程永远得不到唤醒

2）利用信号量实现同步

• 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）

• 设置同步信号量 S 的初始值 = 0

• 在“前操作”之后执行 V (S)

• 在“后操作”之前执行 P (S)

3）利用信号量实现前驱关系

• 信号量用来描述程序或语句之间的前驱关系

• 要为每一对前驱关系各设置一个同步信号量

• 在“前操作”之后对相应的同步信号量执行 V 操作

• 在“后操作”之前对相应的同步信号量执行 P 操作

5、经典同步问题【王道 25 版 p103】

（1）生产者——消费者问题

1）问题描述

• 一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区

• 进程每次从缓冲区中取出一个产品并使用

• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待

• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待

• 缓冲区是临界资源，各进程必须互斥地访问

2）问题分析

• 关系分析：
• 生产者和消费者对缓冲区的互斥访问是互斥关系
• 生产者和消费者之间相互协作，是同步关系

• 整理思路：确定 P、V 操作的大致顺序

• 信号量设置：
• 互斥信号量：mutex 初始值 1，用于控制互斥访问缓冲池
• 同步信号量：full 初始值 0，表示非空缓冲区（产品）的数量
• 同步信号量：empty 初始值 n，表示空闲缓冲区的数量

• 注意：
• 实现互斥的 P 操作一定要在实现同步的 P 操作之后
• V 操作不会导致进程阻塞，因此两个 V 操作顺序可以互换

6、管程

（1）基本概念

• 引入管程的原因：
• 信号量机制存在的问题：编写程序困难、易出错
• 管程的特性保证了互斥，程序员无须自己实现，并提供条件变量，更灵活地实现进程同步

• 管程：定义了共享数据结构和能为并发进程执行（在该数据结构上）的一组操作

• 管程的组成：
• 管程的名称
• 局部于管程内部的共享数据结构或者共享变量说明
• 对管程内的数据结构进行操作的一组过程（函数）
• 对局部于管程内部的共享数据设置初始值的语句

• 管程的基本特征：
• 局部于管程的数据只能被局部于管程的过程所访问
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程，从而实现互斥【编译器实现该特性】

（2）管程中设置的条件变量

• 定义：将一个进程进入管程后被阻塞的原因定义为条件变量 condition

• 管程中设置了多个条件变量，每个条件变量保存了一个等待队列【记录因该条件变量而阻塞的所用进程】

• 两种操作：
• x.wait：x 对应的条件不满足，将正在调用管程的进程插入到 x 条件的等待队列，并释放管程
• x.signal：唤醒一个因 x 条件而阻塞的进程

• 与信号量的相似点：
• wait/signal 类似于信号量的 P/V 操作，实现进程的阻塞/唤醒，但不能说和 PV 操作相同

• 与信号量的不同点：
• 条件变量没有值，仅实现“排队等待”功能
• 信号量有值，这个值反映了剩余资源数
• 在管程中，剩余资源数用共享数据结构记录

四、死锁

1、死锁的概念

（1）基本概念

• 死锁：指多个进程因为竞争资源而造成的一种僵局【互相等待对方手里的资源】

• 死锁的充分条件：资源分配图中每种资源只有 1 个，出现了环路

• 死锁和饥饿的共同点：都是进程无法顺利向前推进的现象

• 死锁和饥饿的不同点：
• 发生饥饿的进程可以只有 1个；发生死锁的进程必然大于等于 2 个
• 发生饥饿的进程能处于就绪态【长期得不到 CPU】，也可能处于阻塞态【长期得不到 I/O 设备】；发生死锁的进程必然处于阻塞态

（2）死锁产生的原因

1. 系统资源的竞争【空间上】：
• 系统中不可剥夺资源（磁带机、打印机等）不足以满足多个进程
• 只有对不可剥夺资源的竞争才可能产生死锁

2. 进程推进顺序非法【时间上】：
• 请求和释放资源的不当，会导致死锁
• 信号量使用不当，会导致死锁

（3）死锁产生的必要条件

（4）死锁的处理策略

• 死锁预防：破坏死锁产生的四个必要条件中的一个或几个

• 死锁避免：用某种方法防止系统进入不安全状态，从而避免死锁

• 死锁检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

2、死锁预防

1. 破坏互斥条件：
• 不可行
• 有些资源（打印机等临界资源）根本不能同时访问
• 为了系统安全，很多时候必须保护这种互斥性

2. 破坏不可剥夺条件：
• 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请
• 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺
• 缺点：
• 实现起来比较复杂
• 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU
• 反复地申请和释放资源会增加系统开销，降低系统吞吐量
• 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

3. 破坏请求并保持条件：
• 采用预先静态分配法：
• 进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行
• 一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了
• 缺点：资源利用率低，可能导致饥饿
• 改进：允许进程只获得运行初期所需的资源后，便可开始运行

4. 破坏循环等待条件：
• 采用顺序资源分配法：
• 首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源
• 同类资源（编号相同）一次申请完
• 原理分析：
• 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源
• 已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象
• 缺点：
• 不方便增加新的设备，因为可能需要重新分配所有的编号
• 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
• 必须按规定次序申请资源，用户编程麻烦

3、死锁避免

（1）系统安全状态

• 安全序列：
• 指如果系统按照这种序列分配资源，则每个进程都能顺利完成
• 只要能找出一个安全序列，系统就是安全状态
• 安全序列可能有多个

• 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利的执行下去【如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态】

• 处于不安全状态未必发生死锁

• 发生死锁时一定是处于不安全状态

（2）银行家算法

• 详见王道书 25 版 p152

• 例题

4、死锁检测和解除

（1）死锁的检测

• 资源分配图：
• 圆圈代表进程，框表示一类资源
• 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源
• 从资源到进程的有向边称为分配边，表示该类资源已有一个资源分配给该进程

• 简化资源分配图可检测系统状态是否为死锁：
• 在资源分配图中，找出既不阻塞又不是孤点的进程 Pi【即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量】
• 然后消去该进程所有请求边和分配边
• 若能消去图中所有的边，则该图可完全简化

• 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

（2）死锁的解除

1. 资源剥夺法：挂起某些死锁进程，并抢占它的资源

2. 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源

3. 进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非剥夺