2.1.1+2.1.2_进程的概念、组成、特征

• 概念
• 理解”进程"和"程序"的区别
• 程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
• 进程（Process）：是动态的，是程序的一次执行过程。
• 当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”—— PID（Process ID，进程ID）
• 进程的信息都被保存在一个数据结构 PCB（Process Control Block）中，即进程控制块。
• 操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在 PCB 中。
• 进程控制块（PCB）
• 进程描述信息
• 进程标识符 PID
• 用户标识符 UID
• 进程控制和管理信息
• CPU、磁盘、网络流量使用情况统计⋯
• 进程当前状态：就绪态/阻塞态/运行态…
• 资源分配清单
• 正在使用哪些文件
• 正在使用哪些内存区域
• 正在使用哪些 I/O 设备
• 处理机相关信息
• 如 PSW、PC 等等各种寄存器的值（用于实现进程切换）

• 组成——一个进程由哪些部分组成
1. PCB
• 进程描述信息
• 进程控制和管理信息
• 资源分配清单
• 处理机相关信息
2. 程序段
• 程序的代码（指令序列）
3. 数据段
• 运行过程中产生的各种数据（如：程序中定义的变量）
• 注意：PCB 是给操作系统用的；程序段、数据段是给进程自己用的。
• 进程实体
• 一个进程实体（进程映像）由 PCB、程序段、数据段组成。
• 进程是动态的，进程实体（进程映像）是静态的。
• 进程实体反应了进程在某一时刻的状态（如：x++ 后，x=2）
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

• 特征——进程有哪些重要的特征
• 动态性（最基本特性）：进程是程序的一次执行过程，是动态地产生、变化和消亡的。
• 并发性：内存中有多个进程实体，各进程可并发执行。
• 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。
• 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"进程同步机制”来解决异步问题。
• 结构性：每个进程都会配置一个 PCB。结构上看，进程由程序段、数据段、PCB 组成。

2.1.3_进程的状态与转换

• 状态
1. 运行态（Running）：占有 CPU，并在 CPU 上运行。
2. 就绪态（Ready）：已经具备运行条件，但由于没有空闲 CPU，而暂时不能运行。
3. 阻塞态（Waiting/Blocked，又称等待态）：因等待某一事件而暂时不能运行。
4. 创建态（New，又称新建态）：A 进程正在被创建，操作系统为进程分配资源、初始化 PCB。
5. 终止态（Terminated，又称结束态）：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销 PCB。
• 其中，运行状态、就绪状态、阻塞状态是进程的三种基本状态。
• 进程 PCB 中，会有一个变量 state 来表示进程的当前状态。如：1 表示创建态、2 表示就绪态、3 表示运行态⋯。
• 为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的 PCB 组织起来。

• 状态间的转换



• 注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）。

• 进程的组织方式（各个进程 PCB 的组织方式）
• 链接方式
• 按照进程状态将 PCB 分为多个队列
• 操作系统持有指向各个队列的指针
• 索引方式
• 根据进程状态的不同，建立几张索引表
• 操作系统持有指向各个索引表的指针

2.1.4_进程控制

• 基本概念
• 什么是进程控制
• 定义：进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
• 简化理解：反正进程控制就是要实现进程状态转换。
• 如何实现进程控制
• 用“原语”实现，原语的执行具有“原子性”，一气呵成。
• 如何实现原语的“原子性”
• 原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。
• 可以用 “关中断指令”和“开中断指令”这两个特权指令实现原子性。
• CPU 执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。

• 进程控制相关的原语
• 进程的创建
• 创建原语
• 申请空白 PCB。
• 为新进程分配所需资源。
• 初始化 PCB。
• 将 PCB 插入就绪队列。
• 引起进程创建的事件
• 用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程。
• 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程。
• 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求。
• 应用请求：由用户进程主动请求创建一个子进程。
• 进程的终止
• 撤销原语
• 从 PCB 集合中找到终止进程的 PCB。
• 若进程正在运行，立即剥夺 CPU，将 CPU 分配给其他进程。
• 终止其所有子进程。
• 将该进程拥有的所有资源归还给父进程或操作系统。
• 删除 PCB。
• 引起进程终止的事件
• 正常结束。
• 异常结束。
• 外界干预。
• 进程的阻塞和唤醒
• 进程的阻塞
• 阻塞原语
• 找到要阻塞的进程对应的 PCB。
• 保护进程运行现场，将 PCB 状态信息设置为“阻塞态”，暂时停止进程运行。
• 将 PCB 插入相应事件的等待队列。
• 引起进程阻塞的事件
• 需要等待系统分配某种资源。
• 需要等待相互合作的其他进程完成工作。
• 进程的唤醒
• 唤醒原语
• 在事件等待队列中找到 PCB。
• 将 PCB 从等待队列移除，设置进程为就绪态。
• 将 PCB 插入就绪队列，等待被调度。
• 引起进程唤醒的事件：等待的事件发生。

• 进程的切换
• 切换原语
• 将运行环境信息存入 PCB。
• PCB 移入相应队列。
• 选择另一个进程执行，并更新其 PCB。
• 根据 PCB 恢复新进程所需的运行环境。
• 引起进程切换的事件
• 当前进程时间片到。
• 有更高优先级的进程到达。
• 当前进程主动阻塞。
• 当前进程终止。

2.1.5_1 进程通信

• 什么是进程间通信
• 进程间通信 （Inter-Process Communication, IPC）是指两个进程之间产生数据交互。

• 为什么进程通信需要操作系统支持
• 进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
• 为了保证安全，一个进程不能直接访问另一个进程的地址空间。

• 进程通信的三种方式
1. 共享存储
• 基于数据结构的共享：比如共享空间里只能放一个长度为 10 的数组。这种共享方式速度慢、限制多，是一种低级通信方式。
• 基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。
2. 消息传递
• 进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
• 两种消息传递
1. 直接通信方式：消息直接挂到接收进程的消息队列里
2. 间接通信方式：消息先发到中间体（信箱）
3. 管道通信
• “管道”是一个特殊的共享文件又名 pipe 文件。其实就是在内存中开辟一个大小固定的内存缓冲区。
1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
2. 各进程要互斥地访问管道（由操作系统实现）。
3. 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
4. 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
5. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：
1. 一个管道允许多个写进程，一个读进程（2014 年 408 真题高教社官方答案）；
2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）。
• 写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据。
• 读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据。

2.1.5_2 信号

• 信号的作用
• 信号（signal）：用于通知进程某个特定事件已经发生。进程收到一个信号后，对该信号进行处理。
• “信号” 常作为异常处理的一种配套机制。

• 实现原理——信号的发送
• 可以由一个进程给另一个进程发送信号
• 可以由操作系统内核给进程发送信号
• 一个进程也可以给自己发送信号

• 实现原理——信号的保存
• 在每个进程的 PCB 中，用两个 N bit 位向量表示待处理信号被阻塞信号。

• 实现原理——信号的处理（When）
• 当进程从内核态转用户态时（如：系统调用返回、或中断处理返回时），例行检查是否有待处理信号，如果有，就处理信号。

• 实现原理——信号的处理（How）
1. 执行操作系统为此类信号设置的缺省（默认）信号处理程序（某些信号默认忽略，不作处理）。
2. 执行进程内此类信号设置用户自定义信号处理程序（自定义信号处理程序将覆盖 ①）
• 信号处理程序运行结束后，通常会返回进程的下一条指令继续执行（除非信号处理程序将进 程阻塞或终止）。
• 一旦处理了某个信号，就将 pending 位重置为 0。
• 当同时收到多个不同类信号时，通常先处理序号更小的信号。

• 特点
• 不同的操作系统，对信号类型的定义各不相同。
• 重复收到的同类信号，将被简单地丟弃（因为仅有 1bit 记录一类待处理信号）。
• 有些信号既不能被用户自定义处理函数，也不能被阻塞。如：Linux 的 SIGKILL、SIGSTOP 信号。

2.1.6_1 线程的概念与特点

• 什么是线程，为什么要引入线程？
• 线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位。
• 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如 QQ 视频、文字聊天、传文件）。
• 引入线程后，进程只作为除 CPU 之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

• 带来的变化
• 资源分配、调度
• 传统进程机制中，进程是资源分配、调度的基本单位。
• 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。
• 并发性
• 传统进程机制中，只能进程间并发。
• 引入线程后，各线程间也能并发，提升了并发度。
• 系统开销
• 传统的进程间并发，需要切换进程的运行环境，系统开销很大。
• 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小。
• 引入线程后，并发所带来的系统开销减小。

• 线程的属性
• 线程是处理机调度的单位。
• 多 CPU 计算机中，各个线程可占用不同的 CPU。
• 每个线程都有一个线程 ID、线程控制块（TCB）。
• 线程也有就绪、阻塞、运行三种基本状态。
• 线程几乎不拥有系统资源。
• 同一进程的不同线程间共享进程的资源。
• 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预。
• 同一进程中的线程切换，不会引起进程切换。
• 不同进程中的线程切换，会引起进程切换。
• 切换同进程内的线程，系统开销很小。
• 切换进程，系统开销较大。

2.1.6_2 线程的实现方式和多线程模型

• 线程的实现方式
• 用户级线程：从用户视角能看到的线程，由线程库实现。
• 内核级线程：从操作系统视角看到的线程，由操作系统实现（内核级线程才是处理机分配的单位）。
• 组合方式：上述两种方式的结合。

• 多线程模型
• 一对一模型
• 一个用户级线程映射到一个内核级线程
• 优：各个线程可分配到多核处理机并行执行，并发度高
• 缺：线程管理都需要操作系统支持，开销大
• 多对一模型
• 多个用户级线程映射到一个内核级线程
• 优：线程管理开销小效率高
• 缺：一个线程阻塞会导致整个进程都被阻塞（并发度低）
• 多对多模型
• n 个用户级线程映射到 m 个内核级线程（n ≥ m）
• 集二者之所长

2.1.6_3 线程的状态与转换

• 线程
• 状态与转换
• 组织与控制
• 线程表（thread table）：可将多个 TCB 组织成一张线程表。
• TCB（线程控制块）

2.2.1 调度的概念、层次

• 基本概念：按某种算法选择一个进程将处理机分配给它。

• 三个层次
• 高级调度（作业调度）：按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程。
• 中级调度（内存调度）：按照某种规则，从挂起队列中选择合适的进程将其数据调回内存。
• 低级调度（进程调度）：按照某种规则，从就绪队列中选择一个进程为其分配处理机。

• 三层调度的联系、对比
• 高级调度
• 外存 → 内存（面向作业）
• 发生频率：最低
• 中级调度
• 外存 → 内存（面向进程）
• 发生频率：中等
• 低级调度
• 内存 → CPU
• 发生频率：最高

ㅤ	要做什么	调度发生在	发生频率	对进程状态的影响
高级调度 （作业调度）	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存 → 内存 （面向作业）	最低	无 → 创建态 → 就绪态
中级调度 （内存调度）	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存 → 内存 （面向进程）	中等	挂起态 → 就绪态 （阻塞挂起 → 阻塞态）
低级调度 （进程调度）	按照某种规则，从就绪队列中选择一个进程其分配处理机	内存 → CPU	最高	就绪态 → 运行态

• 补充知识
• 为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态”
• 七状态模型：在五状态模型的基础上加入了“就绪挂起"和“阻塞挂起"两种状态。

2.2.2_1+2.2.4进程调度的时机、切换与过程、方式

• 时机
• 什么时候需要进程调度？
• 主动放弃
• 进程正常终止。
• 运行过程中发生异常而终止。
• 主动阻塞（如等待 I/O）。
• 被动放弃
• 分给进程的时间片用完。
• 有更紧急的事情需要处理（如 I/O 中断）。
• 有更高优先级的进程进入就绪队列。
• 什么时候不能进行进程调度？
• 在处理中断的过程中。
• 进程在操作系统内核程序临界区中。
• 原子操作过程中（原语）。

• 切换与过程
• 狭义的"调度“和“切换”的区别。
• 切换过程
• 对原来运行进程各种数据的保存。
• 对新的进程各种数据的恢复。
• 重要结论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高。

• 方式
• 非剥夺调度方式（非抢占式）：只能由当前运行的进程主动放弃 CPU。
• 剥夺调度方式（抢占式）：可由操作系统剥夺当前进程的 CPU 使用权。

2.2.2_2 调度器和闲逛进程

• 调度器/调度程序（scheduler）
• 让谁运行？——调度算法
• 运行多长时间？——时间片大小
• 调度时机——什么事件会触发“调度程序”？
• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O 中断发生（可能唤醒某些阻塞进程）
• 两种调度策略
• 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作。
• 抢占式调度策略，每个时钟中断或 k 个时钟中断会触发调度程序工作。

• 闲逛进程
• 调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程（idle）。
• 闲逛进程的特性
• 优先级最低。
• 可以是 0 地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）。
• 能耗低。

2.2.3 调度的目标（调度算法的评价指标）

• CPU 利用率
• 也有题目会让我们计算某设备的利用率

• 系统吞吐量

• 周转时间

• 等待时间
• 进程/作业 等待被服务的时间之和。
• 平均等待时间即各个 进程/作业 等待时间的平均值。

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

2.2.5_1 调度算法：先来先服务、最短作业优先、最高响应比优先

• 先来先服务（FCFS）
• 算法思想：主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）。
• 算法规则：按照作业/进程到达的先后顺序进行服务。
• 用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。
• 是否可抢占：非抢占式的算法。
• 优缺点
• 优点：公平、算法实现简单。
• 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即 FCFS 算法对长作业有利，对短作业不利（Eg：排队买奶茶）。
• 是否会导致饥饿：不会。

• 短作业优先（SJF）
• 算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间。
• 算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）。
• 用于作业/进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称 “短进程优先（SPF, Shortest Process First）算法”。
• 是否可抢占：SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本一一最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）。
• 优缺点
• 优点：“最短的”平均等待时间、平均周转时间。
• 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
• 是否会导致饥饿：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称力“饿死”。

• 高响应比优先 （HRRN）
• 算法思想：要综合考虑作业/进程的等待时间和要求服务的时间。
• 算法规则
• 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。
• （响应比 ≥ 1）
• 用于作业/进程调度：即可用于作业调度，也可用于进程调度。
• 是否可抢占：非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。
• 优缺点
• 综合考虑了等待时间和运行时间（要求服务时间）。
• 等待时间相同时，要求服务时间短的优先（SJF 的优点）。
• 要求服务时间相同时，等待时间长的优先（FCFS 的优点）。
• 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。
• 是否会导致饥饿：不会。

2.2.5_2 调度算法：时间片轮转、优先级、多级反馈队列

• 时间片轮转调度算法 （RR）
• 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
• 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
• 用于作业/进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。
• 是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知 CPU 时间片己到。
• 优缺点
• 优点：公平；响应快，适用于分时操作系统。
• 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
• 是否会导致饥饿：不会。
• 补充：时间片太大或太小分别有什么影响。

• 优先级调度算法
• 算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
• 算法规则：调度时选择优先级最高的作业/进程。
• 用于作业/进程调度：既可用于作业调度，也可用于进程调度。甚至，还会用于在 I/O 调度中。
• 是否可抢占：抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
• 优缺点
• 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
• 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。
• 是否会导致饥饿：会。

• 多级反馈队列调度算法
• 算法思想：对其他调度算法的折中权衡。
• 算法规则
1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2. 新进程到达时先进入第1级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时己经是在最下级的队列，则重新放回该队列队尾。
3. 只有第 k 级队列为空时，才会 k+1 级队头的进程分配时间片。
• 用于作业/进程调度：用于进程调度。
• 是否可抢占：抢占式的算法。在 k 级队列的进程运行过程中，若更上级的队列（1~k-1 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾。
• 优缺点
• 对各类型进程相对公平（FCFS的优点）；
• 每个新到达的进程都可以很快就得到响应（RR的优点）；
• 短进程只用较少的时间就可完成（SPF的优点）；
• 不必实现估计进程的运行时间（避免用户作假）；
• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）。
• 是否会导致饥饿：会。

算法	是否可抢占	优点	缺点	是否会导致饥饿	补充
时间片轮转	抢占式	公平，适用于分时系统	频繁切换有开销，不区分优先级	不会	时间片太大或太小有何影响？
优先级调度	有抢占式的，也有非抢占式的。注意做题时的区别	区分优先级，适用于实时系统	可能导致饥饿	会	动态/静态优先级。 各类型进程如何设置优先级？如何调整优先级？
多级反馈队列	抢占式	平衡优秀	一般不说它有缺点，不过可能导致饥饿	会	ㅤ

2.2.5_3 调度算法：多级队列调度算法

• 系统中按进程类型设置多个队列，进程创建成功后插入某个队列

• 队列之间可采取固定优先级，或时间片划分
• 固定优先级：高优先级空时低优先级进程才能被调度。
• 时间片划分：如三个队列分配时间 50%、40%、10%。

• 各队列可采用不同的调度策略，如：
• 系统进程队列采用优先级调度
• 交互式队列采用 RR
• 批处理队列采用 FCFS

2.2.6 多处理机调度

• 需考虑两个目标
• 负载均衡：尽可能让每个 CPU 都同等忙碌
• 处理机亲和性：尽量让一个进程调度到同一个 CPU 上运行，以发挥 CPU 中缓存的作用（Cache）

• 方案一：公共就绪队列
• 所有 CPU 共享同一个就绪进程队列。每个 CPU 时运行调度程序，从公共就绪队列中选择一个进程运行（每个 CPU 访问公共就绪队列时需要上锁，确保互斥）。
• 优点：可以天然地实现负载均衡。
• 缺点：各个进程可能会频繁地换 CPU 运行，“亲和性”不好。
• 如何提升处理机亲和性
• 软亲和：由进程调度程序尽量保证“亲和性”。
• 硬亲和：由用户进程通过系统调用，主动要求操作系统分配固定的 CPU，确保“亲和性”。
• 软亲和 与 硬亲和可混用。

• 方案二：私有就绪队列
• 每个 CPU 有一个私有的就绪进程队列。每个 CPU 时运行调度程序，从私有就绪队列中选择一个进程运行。
• 优点：天然地实现了“处理机亲和性”。
• 如何实现负载均衡
• 推迁移（push）：一个特定的系统程序周期性检查每个处理器的负载，如果负载不平衡，就从忙碌 CPU 的就绪队列中“推”一些就绪进程到空闲 CPU 的就绪队列。
• 拉迁移（pull）：如果一个 CPU 负载很低，就从其他高负载 CPU 的就绪队列中“拉”一些就绪进程到自己的就绪队列。

2.3.1 同步与互斥的基本概念

• 进程同步
• 并发性带来了异步性，有时需要通过进程同步解决这种异步问题。
• 有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。

• 进程互斥
• 对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源。
• 四个部分
1. 进入区：检查是否可进入临界区，若可进入，需要”上锁”
2. 临界区：访问临界资源的那段代码
3. 退出区：负责"解锁"
4. 剩余区：其余代码部分
• 需要遵循的原则
• 空闲让进：临界区空闲时，应允许一个进程访问。
• 忙则等待：临界区正在被访问时，其他试图访问的进程需要等待。
• 有限等待：要在有限时间内进入临界区，保证不会饥饿。
• 让权等待：进不了临界区的进程，要释放处理机，防止忙等。

2.3.2_1 进程互斥的软件实现方法

• 单标志法
• 在进入区只做“检查”，不”上锁”
• 在退出区把临界区的使用权转交给另一个进程（相当于在退出区既给另一进程”解锁"，又给自己”上锁"）
• 主要问题：不遵循"空闲让进"原则

• 双标志先检查
• 在进入区先“检查"后”上锁"，退出区”解锁”
• 主要问题：不遵循"忙则等待"原则

• 双标志后检查
• 在进入区先"加锁“后“检查”，退出区"解锁”
• 主要问题：不遵循“空闲让进、有限等待"原则，可能导致“饥饿”

• Peterson 算法
• 在进入区"主动争取一主动谦让一检查对方是否想进、己方是否谦让”
• 主要问题：不遵循“让权等待"原则，会发生”忙等”

2.3.2_2 进程互斥的硬件实现方法

• 中断屏蔽方法
• 使用"开/关中断"指令实现
• 优点：简单高效
• 缺点：只适用于单处理机；只适用于操作系统内核进程

• TestAndSet（TS 指令/TSL 指令）
• old 记录是否已被上锁； 再将 lock 设为 true； 检查临界区是否已被上锁 （若已上锁，则循环重复前几步）
• 优点：实现简单；适用于多处理机环境；
• 缺点：不满足“让权等待”

• Swap 指令（XCHG 指令）：逻辑上同 TSL

2.3.3_互斥锁

• 解决临界区最简单的工具就是互斥锁（mutex lock）。

• 互斥锁的主要缺点是忙等待。

• 需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如 TSL 指令、Swap 指令、单标志法。

• 特性
• 需忙等，进程时间片用完才下处理机，违反“让权等待”。
• 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低。
• 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区。
• 不太适用于单处理机系统，忙等的过程中不可能解锁。

2.3.4_1 信号量机制

• 整型信号量
• 用一个整数型变量作为信号量，数值表示某种资源数。
• 整型信号量与普通整型变量的区别：对信号量只能执行 初始化、P(wait)、V(signal) 三种操作。
• 整型信号量存在的问题：不满足让权等待原则。

• 记录型信号量
• S.value 表示某种资源数，S.L 指向等待该资源的队列。
• P 操作中，一定是先 S.value--，之后可能需要执行 block 原语。
• V 操作中，一定是先 S.value++，之后可能需要执行 wakeup 原语。
• 注意：要能够自己推断在什么条件下需要执行 block 或 wakeup。
• 可以用记录型信号量实现系统资源的"申请”和"释放"。
• 可以用记录型信号量实现进程互斥、进程同步。

• 注：若考试中出现 R(S)、V(S)的操作，除非特别说明，否则默认 S 为记录型信号量。

2.3.4_2 用信号量实现进程互斥、同步、前驱关系

• 实现进程互斥
• 分析问题，确定临界区。
• 设置互斥信号量，初值为 1。
• 临界区之前对信号量执行 P 操作。
• 临界区之后对信号量执行 V 操作。

• 实现进程同步
• 分析问题，找出哪里需要实现 ”一前一后” 的同步关系。
• 设置同步信号量，初始值为 0。
• 在”前操作”之后执行 V 操作。
• 在“后操作”之前执行 P 操作。

• 实现进程的前驱关系
• 分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题。
• 为每一对前驱关系设置同步信号量，初值为 0。
• 在每个“前操作”之后执行 V 操作。
• 在每个“后操作”之前执行 P 操作。
• 前驱关系问题，本质上就是多级同步问题。

• 除了互斥、同步问题外，还会考察有多个资源的问题，有多少资源就把信号量初值设为多少。申请资源时进行 P 操作，释放资源时进行 V 操作即可。

2.3.5_1_1 生产者-消费者问题

• 问题描述
• 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）。
• 生产者、消费者共享一个初始为空、大小为 n 的缓冲区。
• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（缓冲区没满 → 生产者生产）
• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。（缓冲区没空 → 消费者消费）

• PV 操作题目的解题思路
1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少）

• 生产者消费者问题是一个互斥、同步的综合问题。

• 对于初学者来说最难的是发现题目中隐含的两对同步关系。

• 有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的“一前一后问题”，因此也需要设置两个同步信号量。

• 易错点：实现互斥和实现同步的两个 P 操作的先后顺序（死锁问题）

2.3.5_1_2 多生产者-多消费者问题

• 问题描述
• 桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用 PV 操作空现下述过程。

• 解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。

• 在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。

• 比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
• 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果。
• 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果。

• 正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象内 一对“事件的前后关系”
• 盘子变空事件 → 放入水果事件。
• “盘子变空事件”既可由儿子引发，也可由女儿引发：“放水果事件”既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。

2.3.5_2 读者-写者问题

• 问题描述
• 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
• 因此要求
1. 允许多个读可以同时对文件执行读操作；
2. 只允许一个写者往文件中写信息；
3. 任一写者在完成写操作之前不允许其他读者或写者工作；
1. 写者执行写操作前，应让已有的读者和写者全部退出。

• 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。

• 其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。

• 另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自 然应该想到用互斥信号量。

• 最后，还要认真体会我们是如何解决“写进程饥饿”问题的。

• 绝大多数的考研 PV 操作大题都可以用之前介绍的几种生产者-消费者问题的思想来解决，如果遇到更复杂的问题，可以想想能否用读者写者问题的这几个思想来解决。

2.3.5_3 哲学家进餐问题

• 一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

• 哲学家进餐问题的关键在于解决进程死锁。

• 这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。

• 如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

• 可以参考哲学家就餐问题解决死锁的三种思路。

2.3.6 管程

• 为什么要引入管程：解决信号量机制编程麻烦、易出错的问题。

• 组成
• 共享数据结构。
• 对数据结构初始化的语句。
• 一组用来访问数据结构的过程（函数）。

• 基本特征
• 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据。
• 每次仅允许一个进程在管程内执行某个内部过程。

• 补充
• 各进程必须互斥访问管程的特性是由编译器实现的。
• 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。

2.4.1 死锁的概念

• 什么是死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进。

• 死锁、饥饯、死循环的区别
• 死锁：至少是两个进程一起死锁，死锁进程处于阻塞态。
• 饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪。
• 死循环：可能只有一个进程发生死循环，死循环的进程可上处理机。
• 死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的。

• 死锁产生的必要条件
• 互斥条件：对必须互斥使用的资源的争抢才会导致死锁。
• 不剥夺条件：进程保持的资源只能主动祥放，不可强行剥夺。
• 请求和保持条件：保持着某些资源不放的同时，请求别的资源。
• 循环等待条件
• 存在一种进程资源的循环等待链。
• 循环等待末必死锁，死锁一定有循环等待。

• 什么时候会发生死锁：对不可剥夺资源的不合理分配，可能导致死锁。

• 死锁的处理策略
• 预防死锁：破坏死锁产生的四个必要条件
• 避免死锁：避免系统进入不安全状态（银行家算法）
• 死锁的检测和解除：允许死锁发生，系统负责检测出死锁并解除。

2.4.2 死锁的处理策略—预防死锁

• 破坏互斥条件
• 将临界资源改造为可共享使用的资源（如 SPOOLing 技术）。
• 缺点：可行性不高,很多时候无法破坏互斥条件。

• 破坏不剥夺条件
• 方案一，申请的资源得不到满足时，立即释放拥有的所有资源。
• 方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）。
• 缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿。

• 破坏请求和保持条件
• 运行前分配好所有需要的资源，之后一直保持。
• 缺点：资源利用率低；可能导致饥饿。

• 破坏循环等待条件
• 给资源编号，必须按编号从小到大的顺序申请资源。
• 缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦。

2.4.3 死锁的处理策略—避免死锁

• 数据结构
• 长度为 的一维数组 表示还有多少可用资源。
• 矩阵 表示各进程对资源的最大需求数。
• 矩阵 表示已经给各进程分配了多少资源。
• 矩阵表示各进程最多还需要多少资源。
• 用长度为 的一位数组 表示进程此次申请的各种资源数。

• 银行家算法步骤
1. 检查此次申请是否超过了之前声明的最大需求数。
2. 检查此时系统剩余的可用资源是否还能满足这次请求。
3. 试探着分配，更改各数据结构。
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态。

• 安全性算法步骤
• 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
• 不断重复上述过程，看最终是否能让所有进程都加入安全序列。

• 系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

2.4.4 死锁的处理策略—检测和解除

• 如何检测
• 数据结构：资源分配图
• 两种结点
• 进程结点
• 资源结点
• 两种边
• 进程结点 → 资源结点（请求边）
• 资源节点 → 进程结点（分配边）
• 死锁检测算法
• 依次消除与不阻塞进程相连的边，直到无边可消。
• 注：所谓不阻塞进程是指其申请的资源数还足够的进程。
• 死锁定理：若资源分配图是不可完全简化的，说明发生了死锁。

• 如何解除
• 资源剥夺法。
• 撤销进程法（终止进程法）。
• 进程回退法。