进程

进程模型

一个进程实质上代表 了某个正在执行中的程序的一个具体实例，它不仅包含了程序的代码，还涵盖了程序计数器、寄存器的 当前状态以及程序中变量的即时值。

物理层面上，CPU是通过时间分片机制在多个进程间进行快速切换，从而实现并发执行 的假象

但在任何一个给定的瞬 间仅有一个进程真正运行

一个CPU核心在任一时刻仅能执行一个线程的任务，即便是系统配置有双核心 （或更多CPU）时，每个核心也是独立地且一次仅执行一个线程。

即便程序代码相同，每个进程实例的执行均被视为独立且唯一 的

进程的创建

操作系统需要一些方式来创建进程。下面是一些创建进程的方式

系统初始化（init）
正在运行的程序执行了创建进程的系统调用（比如 fork）
用户请求创建一个新进程
初始化一个批处理工作

系统初始化

在操作系统启动过程中，系统会初始化并创建多个进程，这些进程根据其功能特性可分为不同类 别。

“前台进程”，它们的主要职责是直接与用户交互，响应用户的操作请求并完成相 应的任务

另一类则运行于后台，不直接面向特定用户进行交互，专注于执行系统级或服务级的任 务。通常被称为“守护进程” 守护进程对 于维护系统的稳定运行和提供多样化的服务至关重要。

系统调用创建

在操作系统的运行过程中，不仅限于启动阶段，新的进程也可以在后续被动态地创建。这一过程通常涉及到一个正在执行的进程通过发起特定的 系统调用来请求操作系统创建一个或多个 新的子进程，以协助完成复杂的任务或优化资源利用。

用户请求创建

了解即可

用户可以通过多种直观方式启动应用程序，包括但不限于输入特定 命令或双击桌面图标。

用户通过鼠标点击或键盘命令可以轻松地在不同窗 口之间切换，从而与不同的进程进行交互，实现多任务处理和信息管理的灵活性。

交互式系统是以人与计算机之间大量交互为特征的计算机系统，比如游戏、web浏览器，IDE 等集成开发环境。

批处理创建

在这种环境中，用户会提交一系列批处 理作业，由操作系统管理。当系统资源允许且判定能够处理更多任务时，操作系统将主动创建新进程， 并从其维护的作业队列中挑选下一个待执行作业运行

UNIX操作系统，其核心提供了一个独特的系统调用—— fork ，专门用于创建新进程。

fork调⽤--》新进程诞⽣，此时是⽗进程⼀个副本
exec系列函数调⽤--》替换静态区
exit系统函数调⽤---》结束，变成⼀具僵⼫，基础数据结构
wait系统函数调⽤--》回收资源，已经变为僵⼫态的⼦进程的资源

进程创建机制确保了父进程与其子进程各自拥有独立的地址空 间。

进程的终止

正常退出(自愿的)
错误退出(自愿的)
严重错误(非自愿的)
被其他进程杀死(非自愿的)

正常退出

这种终止行为通常由特定的系统调用触发，以通知操作系统该进程已完成任务并 准备释放其占用的资源。

除了由系统调用触发的终止外，许多面向用户的软件应用程序也提供了用户可操作的界面元素（如 图标、按钮或菜单项），允许用户自愿终止进程。

错误退出

进程终止的第二个常见原因是由于运行过程中遭遇了严重错误，这些错误可能源于多种因素，包括 但不限于文件缺失、权限不足或参数错误等。

这种终 止是立即且不可逆转的

严重错误

进程终止的第三个主要原因源于程序内部错误，这些错误通常由编程疏忽、逻辑错误或运行时异常 引起。这些错误能够导致进程的运行状态变得不稳定或不可预测，进而可能触发终止过程。

像UNIX这样的操作系统中 提供了一种机制允许进程对特定 类型的错误进行捕获和处理，而不是直接终止 信号可以被视为 一种软中断，它通知进程发生了某个特定事件

被其他进程杀死

第四个导致进程终止的原因是，当某个进程（通常具有相应的权限）主动执行一个特定的操作来请 求操作系统结束另一个进程的执行。

进程的层次结构

UNIX及其衍生系 统，进程之间通过明确的父子关系形成了一种层次结构

进程状态

操作系统的核心基石在于其调度程序，这一组件位于系统架构的最底层

三态模型

1.运行态（Running State）：此状态表明进程当前正实际占用CPU的时间片进行执行。
2. 就绪态（Ready State）：就绪态的进程已准备好执行，但由于CPU资源正被其他进程占用，因此它暂时处于等待CPU时间片的状态。
3. 阻塞态（Blocked State）：阻塞态的进程因等待某个外部事件（如I/O操作完成、信号量释放等）而无法继续执行。除非该事件发生，否则即使CPU空闲，该进程也无法运行。

五态模型

七态模型

比五态多了 挂起

进程的实现

操作系统为确保进程间高效且有序的切换，精心维护着一张关键的数据结构—— 进程表（Process Table）。

中断处理和调度的详细过程可以概括为以下几个步骤：

1. 硬件压栈：中断发生时，硬件自动将程序计数器、程序状态字及必要的寄存器值压入堆栈。
2. 硬件跳转：根据中断向量中的地址，硬件跳转到相应的中断服务程序。
3. 汇编语言保存上下文：中断服务程序首先通过汇编语言代码保存当前进程的上下文环境。
4. 设置新堆栈（如果需要）：为中断服务程序或新的进程设置合适的堆栈环境。
5. C中断服务程序执行：执行中断服务程序的具体任务，如处理I/O操作。
6. 调度器决策：中断服务程序完成后，操作系统调度器决定下一个要运行的进程。
7. C至汇编代码转移：控制权从C语言中断服务程序返回至汇编代码，准备切换进程。
8. 汇编语言恢复上下文并启动进程：汇编代码为新进程恢复上下文环境，并启动其执行。

进程线程区别

都有调度能力

线程

特点

资源共享

轻量级与高效性

性能提升

调度线程的大致逻辑

调度线程负责不断地从某个请求源（如网络）接收新的工作请求，并将这些请求分配给空闲的工作 线程处理。这里使用了一个无限循环来持续监听和分发请求。

经典的线程模型

而“多线程”这一术语，则特指在单个进程内部，多个线程并 行执行、共享资源并协同工作的模式

每个线程都被赋予了访问进程地址空间内任意内存地址的能力。

多 线程程序时，必须采取额外的同步和协调机制，以确保线程间的正确交互和数据一致性。使用互斥锁、信号量、条件变量等同步原 语，以及合理的线程调度策略，来避免数据竞争和其他并发问题。

线程可以处于以下几种状态：运行中、阻塞、就绪 终止

每个线程都会有自己的堆栈

thread_join 函数便是一种常用的同 步机制，它允许一个线程（称为等待线程）暂停执行，直至另一个特定线程（被等待线程）退出

线程实现

在用户空间中实现线程；
在内核空间中实现线程；
在用户和内核空间中混合实现线程

• 在用户空间管理线程的场景下，每个进程都需维护一个 专属的“线程表”

在用户空间实现线程的优势

避免了内核调用的开销，省去了上下文切换的步骤，也无需对CPU缓存进行不必要的刷新
用户空间线程允许每个进程根据其特定需求定制调度算法

在用户空间实现线程的劣势

违背了允许线程进行阻塞调用而不影响同进程内的其他线程。

进程间通信

主要面临以下三大挑战：

1. 消息传递机制。实现一种可靠的通信协议或机制
2. 同步与互斥：如何确保多个进程（或线程）在访问共享资源时不会相互干扰， 从而避免数据竞争和不一致性。
3. 数据顺序与同步：关于数据处理的顺序性。在分布式系统或并发环境中，确保数 据按照正确的顺序被处理至关重要

临界区

进程中对共享资源进行操作的代码段定义为 临界区域/ 临界区

为了有效规避这一问题，核心策略在于确保一个或 多个进程不会在同一时间对同一共享资源（包括但不限于共享内存、共享文件等）进行读写操作。

互斥（Mutual Exclusion）的机制，即当一个进程正在使用某共享资源时，其他进程 必须被阻止访问该资源

确保并发访问的效率和正确 性，我们还需要考虑以下四个重要条件：

互斥条件：在任何时候，两个或多个进程不能同时处于其临界区内

前进条件（无假设条件）：即系统应能在任何CPU配置下都能正常工 作。这意味着并发控制机制应当是通用的，不依赖于特定的硬件条件。

有限等待条件：位于临界区外的进程不应被无限期地阻塞等待进入临界区

无忙等条件：进程在临界区外等待时，不应占用CPU进行无意义的循环检查。以减少CPU资源的浪费

解决竞态

忙则等待是互斥性的体现

忙等互斥

忙等互斥 = 为了实现互斥，进程在临界区外死循环空转占着 CPU，直到能进为止。

可能引发优先级反转（Priority Inversion Problem）：高优先级进程被低优先级进程阻塞，导致高优先级进程无限等待。

✅ 优点：

• 实现简单，不需要操作系统的阻塞 / 唤醒机制
• 上下文切换开销小，适合临界区执行时间很短的场景

❌ 缺点：

• 不满足 “让权等待”，会浪费 CPU 资源
• 可能导致优先级反转（低优先级进程一直占着 CPU，高优先级进程拿不到锁）

屏蔽中断

在单处理器系统上，最简单的解决方案 让进程在进入临界区之前屏蔽所有中断，并在离开临界区后 重新启用它们。

硬件层面 代价较大

锁变量

软件层面

违反了互斥原则。

原子性指的是一个操作（或一组操作）在执行过程中，要么全部完成，要么完全不执行，不 会停留在中间某个状态。

. 不可分割性
. 一致性保证
. 可见性

锁变量不具备原子性

这通常通过硬件提供的原子指令或操作系统提 供的同步原语来实现，如**测试并设置TAS、比较并交换CAS（硬件原子指令） 可以实现原子性

严格轮询法

单标志+忙等待

用 自旋锁(spinlock)（TAS/CAS 实现），它是一种特殊类型的忙等待锁，适用于等待 时间非常短的场景。

三大缺陷：

1. 违背空闲让进
2. 可能导致饥饿（对方进程挂了，你永远进不去）
3. 忙等待，不释放 CPU

Peterson解法

互斥进入临界区 不会饥饿

缺点是等待时会一直占用 CPU

双标志+忙等待

遵循空闲让进、忙则等待、有限等待 未遵循让权等待

主要思想 只要“对方也想进”，并且“最后一次谦让是让给对方的”，自己就一直等

「有限等待」的证明逻辑

每个进程在enter_region里都会把turn让给对方，对方执行完leave_region会把interested设为FALSE，此时等待的进程的while条件会自动解除，最多等 1 次对方执行，不会出现饥饿。

TSL指令、XCHG指令

XCHG 指令主要用在Intel x86架构

TSL 执行的两个核心步骤（原子操作）

读取并锁定：读取内存地址LOCK的值，加载到寄存器RX；同时将该地址强制写为非零值（通常是 1，标记为 “已加锁”）

总线锁定：执行期间锁定内存总线，其他 CPU 无法访问该内存地址，防止并发修改

✅ 空闲让进：锁空闲时，进程可通过 TSL 指令直接获取锁✅ 忙则等待：锁被占用时，进程循环等待，不会同时进入临界区

✅ 有限等待：锁被释放后，等待的进程可立即获取锁，不会饥饿

❌ 让权等待：进程等待时循环空转，不释放 CPU，属于忙等

睡眠与唤醒

核心思想：条件不满足时，进程主动放弃 CPU，进入阻塞状态，由其他进程显式唤醒。

优点：避免 CPU 空转，解决优先级反转问题，提升系统效率。

问题：唤醒丢失（Lost Wakeup）：唤醒信号在目标进程进入睡眠前就发出，导致信号被忽略，双方永久阻塞。

睡眠与唤醒原语

原语是硬件的

sleep原语

• 为了不允许它们进入关键区之前会阻塞，而不是浪费CPU时间，最简单的是sleep和wakeup。
• sleep是一个能够造成调用者阻塞的系统调用，会暂停直到其他进程唤醒它。

wakeup原语

• wakeup调用一个参数，为要唤醒的进程。

生产者-消费者问题

• 两个进程共享一个公共的固定大小的缓存区

• 一个是生产者（producer），将信息放入缓存区，另一个是消费者（consumer），会从缓存区中取出。

  同步问题：

  生产者不能往满的缓冲区写

  消费者不能从空的缓冲区读

  互斥问题：

  缓冲区是共享资源，同一时间只能有一个进程操作（写 / 读），否则会出现数据覆盖、重复消费等问题

  睡眠与唤醒存在信号丢失问题 问题的核心在于： 唤醒操作可能发生在目标线程实际进入等待状态之前，导致唤醒信号被忽略。

信号量

信号量本质是带等待队列的整型计数器，把 “唤醒信号” 变成可累积、可保存的资源计数，从根源规避丢失

信号量的 value 本质上是当前可用资源的数量

P 操作（也叫 wait/down）：申请资源 是减 不够就睡 资源如果抢完了要加入等待队列

void down(semaphore *s) {
    s->value--;         // 信号量减1（申请资源）
    if (s->value < 0) { // 如果减完小于0，说明没资源了
        进程阻塞，加入该信号量的等待队列;
    }
}

如果 s->value <= 0（减完小于 0）

这里的负数值的绝对值 = 等待队列里的进程数（考研考点）

V 操作（也叫 signal/up）：释放资源 是加 有等就醒

void up(semaphore *s) {
    s->value++;         // 信号量加1（释放资源）
    if (s->value <= 0) { // 如果加完后还有进程在等
        唤醒等待队列里的一个进程;
    }
}

信号量	初值	作用	P/V 操作的意义
mutex	1	互斥访问缓冲区	down 加锁，up 解锁
empty	N（缓冲区大小）	同步：控制生产者写入	down 申请空槽，up 释放空槽
full	0	同步：控制消费者读取	down 申请数据，up 释放数据

关键考点：P 操作的顺序（先同步后互斥！）

生产者：P(empty)  → p(mutex)->insert数据->v(mutex)-> V(full)
消费者：P(full) ->  p(mutex)->读取数据->v(mutex) →  V(empty)

整型信号量（纯整数，循环等待，理论用）

记录型信号量（带等待队列，实际用）

互斥量

互斥量（mutex）就是一种特殊的信号量！

确保同一时间只有一个线程 / 进程进入临界区

它是只能取 0 或 1的信号量，专门用来做互斥锁。sy

特性	互斥量（Mutex）	信号量（Semaphore）
核心用途	专门解决互斥问题（保护临界区）	解决同步 + 互斥（可用于生产者 - 消费者、资源计数）
状态数	只有两种：锁定 / 解锁	可以是任意非负整数（初值可设置）
谁能解锁	必须由持有锁的线程解锁（否则会出错）	任何线程都可以执行 V 操作（释放信号量）
用途限制	只能实现互斥，不能直接实现同步	既能实现互斥（如 mutex=1），也能实现同步

互斥量 + 条件变量（考研经典组合）

核心函数（考研常考）

函数	作用
pthread_cond_init()	初始化条件变量
pthread_cond_wait()	等待条件成立（自动释放互斥量，阻塞线程）
pthread_cond_signal()	唤醒一个等待的线程
pthread_cond_broadcast()	唤醒所有等待的线程

互斥量 vs 自旋锁：互斥量获取失败会阻塞（让出 CPU），自旋锁会忙等（占用 CPU）

易错点

互斥量必须由持有锁的线程解锁，否则会导致死锁

pthread_cond_wait()会自动释放互斥量，被唤醒后会重新获取锁

条件变量需要用while`循环判断条件，防止虚假唤醒

Futexes

全称：Fast Userspace Mutex（快速用户空间互斥锁）

条件变量

专门用来 “等条件” 的队列,是配合互斥量一起使用的同步工具，专门解决 “线程需要等某个条件成立，才能继续往下执行” 的问题。

管程

管程是操作系统中高级同步机制

管程（Monitor）是一种编程语言级别的同步原语

管程 = 封装共享数据 + 自动互斥访问的过程，相当于 “自带互斥锁的对象”。

管程作用：封装共享数据与操作过程，自动实现互斥，配合条件变量实现同步，解决信号量手动 P/V 易出错的问题

互斥性（核心）

管程内部的所有过程，同一时间只能有一个进程 / 线程执行。其他试图进入的进程会被阻塞，直到当前进程退出管程。

signal 操作的两种实现方式(就是唤醒操作)

类型	signal 后的行为	唤醒线程的执行时机	核心问题
Hoare（霍尔）	发送信号的线程立即让出管程	被唤醒的线程立刻执行	上下文切换频繁，效率低；但被唤醒时条件一定满足
Hansen（汉森，也叫 Mesa 管程）	发送信号的线程继续执行	被唤醒的线程需要等待发送线程退出管程，才能再次进入	被唤醒后条件可能被其他线程改变，必须用 while 循环重新判断条件（而不是if）

对比项	信号量 (P/V)	管程
互斥实现	程序员手动写 down/up	系统自动保证，无需手动控制
同步实现	信号量本身	依赖条件变量 wait/signal
易用性	难，易出错（漏写、顺序错）	简单，安全性高
适用范围	线程、进程都可用	仅同进程内多线程
层次	底层原语（操作系统）	高层封装（编程语言）

C、Pascal 以及多数主流编程语言并不直接支持 管程

消息传递

消息传递（Message Passing）是进程间通信（IPC）的一种机制，它不依赖共享内存，而是通过发送和接收消息来实现进程间的数据交换与同步。

核心系统调用：send()（发送消息）、receive()（接收消息）

载体：内核信箱、消息队列、管道

特点：解耦性强，发送者和接收者不需要共享内存，也不需要直接访问同一资源，因此特别适合分布式系统或跨网络通信。

send(dest_id, &msg_buffer)
参数：目标进程 ID、消息缓冲区指针
发送方把消息放入接收方的消息队列 / 信箱中，若接收方阻塞等待消息，则会被唤醒

receive(src_id, &recv_buffer)
参数：源进程 ID、接收缓冲区指针
语义：若没有消息可接收，调用进程会被阻塞，直到消息到达；也可设置为非阻塞，直接返回错误码

消息传递系统的设计要点

可靠性问题：消息丢失与重复

消息丢失：网络传输中消息可能丢失，导致接收方一直阻塞等待。

• 解决方法：确认机制（ACK）：接收方收到消息后发送确认，发送方超时未收到确认则重发。

消息重复：重发机制可能导致接收方收到重复消息。

• 解决方法：序列号（Sequence Number）：每条消息带唯一序号，接收方通过序号判断是否为重复消息并忽略。

编址方式

基于进程地址的编址：每个进程有唯一 ID，直接按 ID 发送消息。优点简单直观，缺点是进程迁移 / 重启时需更新映射关系。

基于信箱（Mailbox）的编址：引入信箱作为中间层，消息发送到信箱中，接收方从信箱取消息。优点解耦性强，支持消息缓存；缺点是信箱满时发送方会被阻塞

特性	消息传递（Message Passing）	共享内存 + 信号量
通信方式	发送 / 接收消息，不共享内存	直接访问共享内存，需同步控制
解耦性	强，发送者和接收者无需知道对方状态	弱，需依赖同一共享资源
适用场景	分布式系统、跨网络通信	同一主机内进程通信
同步实现	消息队列 / 信箱自带同步	需手动使用信号量 / 管程实现同步
数据一致性	消息传递过程保证数据副本一致	需额外处理数据竞争和同步
可靠性	需额外处理消息丢失、重复	无需考虑网络传输问题

管道（Pipe）

管道是半双工的通信通道，本质是内核开辟的一块缓冲区，连接两个进程，实现数据单向流动

单工 数据只能固定一个方向传，永远不能反向。

半双工 通道支持双向传输，但同一时刻只能往一个方向传

全双工 同一时刻，两个方向可以同时传数据，收发互不

​ 干 扰

对比维度	无名管道（Pipe）	有名管道（FIFO / 命名管道）
文件标识	无文件名、无磁盘目录项	有独立文件名，磁盘存在目录项
适用进程	仅有亲缘关系进程（父子、兄弟）	无亲缘限制，任意进程均可使用
创建方式	系统调用 pipe()	命令 mkfifo / 系统调用 mkfifo()
访问方式	fork 继承文件描述符	像普通文件一样 open 打开
生命周期	所有关联进程关闭端口后，管道自动销毁	管道文件永久存在，需手动删除
通信方向	半双工（单向数据流）	半双工（单向数据流）
数据形式	字节流、无消息边界、FIFO	字节流、无消息边界、FIFO
存储位置	数据仅存内核缓冲区，不落地磁盘	元信息存磁盘，数据仍在内核缓冲区
打开阻塞特性	创建即拥有读写端，无额外打开阻塞	单独读 / 单独写打开会阻塞，必须读写两端配对打开
典型使用场景	父子进程、兄弟进程简易通信	不同用户 / 无关联进程跨进程通信

屏障

屏障（Barrier）是一种多线程同步工具

核心作用：保证所有线程在继续执行下一个阶段前，都处于完全相同的进度，避免 “有的线程跑太快，有的还没准备好” 导致的数据不一致。

避免锁：读-复制-更新

读操作全程无锁，写操作先复制再更新，版本切换瞬间完成，读操作永远看不到数据中间状态，专门优化读多写少场景的性能

调度

• 当一个计算机是多道程序设计系统时，会频繁的有很多进程来同时竞争CPU时间片

调度的本质：操作系统决定哪个就绪进程 / 线程获得 CPU 执行权的过程，核心是CPU 资源分配策略

进程调度与线程调度的区别：现代 OS 以线程为调度基本单位，线程更轻量，切换开销更小，能提升系统响应速度。

作业调度 磁盘->内存
进程调度 内存->cpu

进程行为分类

区分依据：CPU 时间占比，而非 I/O 时间长短

类型	核心特征	典型场景	线程数设置原则
CPU 密集型（计算密集型）	长时间占用 CPU，I/O 操作极少	科学计算、大规模数据处理、算法训练	线程数≈CPU 核心数（避免上下文切换开销）
I/O 密集型	大部分时间等待 I/O（磁盘 / 网络），CPU 利用率低	网络通信、数据库操作、文件读写	线程数 = CPU 核心数 /(1 - 阻塞系数)（阻塞系数 0.8~0.9，充分利用 CPU 空闲时间）

何时调度

创建新进程时 决定是运行父进程还是子进程

进程退出 / 终止时 从就绪进程中选择其他进程运行 若无就绪进程，调度空闲进程

进程阻塞时 阻塞在I/O、信号量或其他原因 阻塞是进程主动放弃 CPU

当I/O中断发生时，可以做调度策略 这是被动触发的调度时机

时钟中断触发时：抢占式调度中，时钟中断（如 50Hz/60Hz）触发时间片检查，判断是否剥夺当前进程 CPU。 这个时机只存在于抢占式调度中

场景	触发方式	是否一定发生调度	核心原因
进程创建	主动（系统调用）	不一定	新进程是否需要抢占父进程
进程终止	主动（系统调用）	一定	当前进程消失，CPU 必须换人
进程阻塞	主动（系统调用）	一定	当前进程需要等待事件，主动放弃 CPU
I/O 中断	被动（硬件中断）	不一定	唤醒的进程是否需要抢占当前进程
时钟中断	被动（硬件中断）	不一定（仅抢占式）	当前进程时间片是否用完

空闲进程

定义：操作系统内核为避免 CPU 空闲而设计的特殊进程（Windows：System Idle Process；Linux：idle 进程 / 0 号进程），并非用户创建的真实进程。

特点：永远存在 优先级最低 不占用实际资源

核心作用：

• 当无其他就绪进程时，占用 CPU 时间，避免 CPU 进入完全空闲状态；
• 维持系统稳定，减少 CPU 空转能耗；
• 任务管理器中显示的 CPU 占用率，实际是空闲进程占用率，值越高表示 CPU 越空闲。

饥饿的概念

饥饿 = 系统中某些进程永远（或长期）得不到 CPU 资源，一直无法执行。 只是少数

概念	状态	原因
饥饿	CPU 一直被其他进程占用，但部分进程永远抢不到	调度算法不合理（比如只按优先级调度，不考虑等待时间）
CPU 空闲	没有任何就绪进程，CPU 只能跑空闲进程	所有进程都阻塞在 I/O/ 锁等事件上，就绪队列为空

解决饥饿的办法

老化（Aging）：进程在就绪队列里等得越久，优先级就慢慢提高，等久了的进程就能被调度了。

高响应比优先（HRRN）：不仅看作业的运行时间，还看它的等待时间，避免长作业一直被插队。

时间片轮转（RR）：所有进程轮流用 CPU，不管优先级高低，每个进程都能分到时间片，从根本上避免饥饿。

补充一个易错点

饥饿和 “死锁” 也不一样：

• 死锁：多个进程互相持有对方需要的资源，谁都不释放，大家都卡死了，谁也不运行。
• 饥饿：系统里有进程一直在运行，只是少数进程永远抢不到资源，处于 “一直等但没死” 的状态。

调度算法分类

主要是 周转时间 和响应时间

按调度策略分类

类型	核心逻辑	适用场景	关键考点
非抢占式调度	进程一旦获得 CPU，将持续运行直到主动放弃（如等待 I/O、执行完毕），不会被强制剥夺	批处理系统（任务执行时间固定、无需交互）	优点：切换开销小；缺点：长进程会阻塞短进程，系统响应性差
抢占式调度	系统可通过时钟中断、优先级判断等方式，强制剥夺当前进程 CPU，调度其他就绪进程	交互式系统（GUI、服务器）、实时系统	优点：公平性好、响应性强；缺点：上下文切换开销大

调度算法的目标

相关公式

指标	定义	计算公式	适用系统
周转时间	作业从提交到完成的总时间	周转时间 = 完成时间 - 提交 或者 到达时间	批处理
平均周转时间	所有作业周转时间的平均值	平均周转时间 = 总周转时间 / 作业数	批处理
带权周转时间	周转时间 / 实际运行时间	带权周转时间 = 周转时间 / 运行时间	批处理
平均带权周转时间	所有作业带权周转时间的平均值	平均带权周转时间 = 总带权周转时间 / 作业数	批处理
响应时间	从提交请求到首次得到响应的时间	响应时间 = 首次 CPU 时间 - 提交时间	交互式
吞吐量	单位时间内完成的作业数	吞吐量 = 完成作业数 / 总时间	批处理 / 交互式
CPU 利用率	CPU 忙的时间占总时间的比例	CPU 利用率 = CPU 运行时间 / 总时间	所有系统
截止时间	实时任务必须完成的最晚时间	题目直接给出	实时系统
响应比	衡量进程 / 作业调度优先级的综合指标，平衡等待时间与运行时间	响应比 = (等待时间 + 运行时间) / 运行时间	批处理系统（HRRN 调度算法）

批处理系统的调度

核心特征是无用户交互、批量处理作业、非抢占式调度（以 FCFS 为主）

进程行为：批处理作业多为CPU 密集型

批处理系统中常见的系统调用类型

类型	典型调用	作用	与调度的关联
I/O 系统调用	read/write/open/close	磁盘文件读写、设备操作	触发进程阻塞，是批处理中调度切换的核心诱因
进程控制调用	exit/wait	作业退出、等待子进程	进程结束后，调度器选择下一个作业执行
资源申请调用	malloc/brk/mmap	内存分配与释放	批处理作业启动时通过此类调用申请内存，分配失败会导致作业终止
文件管理调用	creat/unlink	文件创建 / 删除	批处理作业批量处理数据时频繁使用，同样会触发阻塞

SJF、SRTF 都是为了解决 FCFS 的缺点（如长作业阻塞短作业、平均周转时间长）而出现的，但它们都无法替代 FCFS 在批处理系统中的基础地位

算法	抢占性	调度判断标准	适用场景	核心优势	核心缺点
先来先服务（FCFS）	非抢占式	就绪队列中作业到达的先后顺序	早期批处理、实现简单的场景	公平、无饥饿、实现简单	对短作业不友好，“长作业阻塞短作业”（护航效应），平均周转时间长
最短作业优先（SJF）	非抢占式	就绪队列中作业的总运行时间（预估 / 已知）	批处理系统（作业运行时间已知）	能最小化平均周转时间，吞吐量高	长作业可能被短作业 “饿死”；无法动态响应新作业
最短剩余时间优先（SRTF）	抢占式	就绪队列中作业的剩余运行时间（实时计算）	动态批处理、短作业频繁到达的场景	对短作业更友好，平均周转时间比 SJF 更优	抢占带来额外的上下文切换开销；长作业仍可能被饿死

算法	抢占性	调度判断标准	调度时机	平均周转时间	饥饿问题
FCFS	非抢占式	到达顺序	进程结束 / 阻塞时	最长	无
SJF	非抢占式	总运行时间	进程结束 / 阻塞时	中等	可能（长作业）
SRTF	抢占式	剩余运行时间	进程结束 / 阻塞 / 新进程到达时	最短	可能（长作业）
高响应比优先HRRN	非抢占式	响应比 = (等待时间 + 运行时间) / 运行时间	进程结束 / 阻塞时，重新计算所有就绪进程的响应比，选择响应比最高的进程	较短（优于 FCFS，略差于 SJF/SRTF）	无（等待越久，响应比越高，长作业一定会被调度）

为什么批处理系统多采用非抢占式调度？
答：① 批处理作业多为 CPU 密集型，很少主动放弃 CPU；② 抢占会增加上下文切换开销，降低系统吞吐量和 CPU 利用率；③ 批处理用户不关心响应时间，更关注作业整体完成效率。
HRRN 为什么能避免长作业饥饿？
答：响应比公式中，等待时间越长，响应比越高，长作业等待足够久后，响应比会超过短作业，从而被调度执行。
SJF 能获得最短平均周转时间的原因是什么？
答：短作业优先被调度，减少了短作业的等待时间，而短作业的等待时间对平均周转时间的影响更大，因此整体平均周转时间最短。

交互式系统调度

时间片到了从运行态到就绪态

必背

调度算法	核心逻辑（必背）	抢占性（选择题必辨）	考研高频考点（命题核心）	优缺点（简答题必背）	适用场景
轮询调度（RR, Round-Robin）	基于固定时间片轮转：每个进程分到等长时间片，用完后移到就绪队列尾部，下一个进程按顺序执行	抢占式（时间片到点强制抢占）	1. 时间片长度的权衡（过短 / 过长的影响）2. 上下文切换开销的计算3. 公平性与响应性的平衡4. 与 FCFS 的核心差异	✅ 优点：实现简单、绝对公平、无饥饿问题、响应时间可控❌ 缺点：时间片长度难平衡、频繁切换带来额外开销	分时系统、桌面操作系统、通用交互式场景（考研最基础的交互式调度算法）
优先级调度	为每个进程分配优先级，高优先级进程优先获得 CPU 资源，优先级相同则按顺序执行	支持抢占式 / 非抢占式两种实现（考研主流考抢占式）	1. 静态优先级 vs 动态优先级的区别2. 饥饿问题的成因与解决方法（进程老化 Aging）3. I/O 密集型进程的动态优先级优化（反比优先算法）4. 与 RR 算法的结合使用	✅ 优点：适配进程重要性差异，关键任务可优先执行❌ 缺点：易出现低优先级进程饥饿，实现复杂度高于 RR	服务器系统、嵌入式实时系统、需区分任务优先级的交互场景
多级队列调度	将就绪队列拆分为多个独立队列，每个队列有固定优先级，可采用专属调度算法（如系统进程用 RR、批处理用 FCFS）	队列间抢占式（高优先级队列为空时，才调度低优先级队列）	1. 与多级反馈队列的核心差异2. 队列的优先级规则与调度逻辑3. 经典案例 CTSS 系统的核心特点	✅ 优点：不同队列适配不同类型进程需求，隔离性好❌ 缺点：进程固定分配队列无法动态调整，低优先级队列易饥饿	早期分时系统、多用户分级权限场景、需严格隔离进程类型的系统
多级反馈队列调度（MLFQ）	多级队列的升级版，进程可动态调整队列：1. 新进程从最高优先级队列开始，RR 调度2. 用完时间片未完成则降级到低优先级队列3. 因 I/O 主动放弃 CPU 则留在 / 提升队列	抢占式（高优先级队列优先调度）	1. 核心设计思想与动态调整规则2. 对短作业、I/O 密集型进程的优化逻辑3. 与 RR、多级队列的对比4. 现代操作系统的应用案例	✅ 优点：兼顾公平与效率，短作业 / I/O 密集型进程响应快，无需预估进程运行时间❌ 缺点：实现复杂，需处理队列动态调整的开销	现代通用操作系统（如 Linux 早期调度器）、通用交互式 / 分时系统（考研综合题高频考点）
最短进程优先（SPN/STR/SRTF）	优先选择预计运行时间最短的进程执行，分为非抢占式（SPN）和抢占式（SRTF）	分抢占式 / 非抢占式（交互式场景主流考抢占式 SRTF）	1. 与批处理 SJF 算法的联动与差异2. 抢占式 SRTF 的调度时机（新进程到达时触发）3. 平均周转时间的计算与对比4. 实现难点（如何预估进程运行时间）	✅ 优点：能最小化平均周转时间，对短作业极度友好❌ 缺点：需预估进程运行时间，长作业易出现饥饿	可预估进程运行时间的交互式 / 分时系统、短作业密集的交互场景

I/O密集型高优先级 cpu密集型低优先级

了解即可

调度算法	核心逻辑	核心特点	考研考查情况
保证调度（Guaranteed Scheduling）	对用户做出明确性能承诺，按进程数 / 用户数均分 CPU 资源，确保每个进程 / 用户获得约定的 CPU 时间	1. 核心逻辑：n 个进程时，每个进程获得约 1/n 的 CPU 时间2. 需跟踪每个进程的 CPU 使用时间，实现成本高	考研几乎不考，仅需知道 “按进程 / 用户数均分 CPU” 的核心思想即可
彩票调度（Lottery Scheduling）	给进程分配 “彩票”，调度时随机抽取彩票，持有中奖彩票的进程获得 CPU；优先级越高，持有的彩票越多，中奖概率越大	1. 是一种概率性调度算法，实现简单2. 支持进程间交换彩票，适配灵活的资源分配需求	考研仅在概念题中偶尔出现，无需深入研究
公平分享调度（Fair Share Scheduling）	按用户 / 用户组分配 CPU 资源，确保每个用户 / 组公平获得 CPU 时间，避免单个用户 / 组占用过多系统资源	1. 从 “进程级公平” 升级到 “用户级公平”2. 需跟踪用户 / 组的资源使用情况，实现复杂	考研几乎不考，仅需知道 “按用户 / 组分配 CPU” 的核心思想即可

实时系统中的调度

1. 实时系统

内容	核心
定义	规定时间内完成响应
特点	正确 + 准时

2. 硬实时 vs 软实时 硬必须，软尽量

3. 事件分类 周期规律，非周期随机

   4. 可调度条件（重点）

4. 符号	含义
   Cᵢ	执行时间
   Pᵢ	周期
   Cᵢ/Pᵢ	CPU占用率

结果	结论
≤1	可调度
>1	不可调度

≤1忙得过来，>1忙不过来

5. 静态 vs 动态调度 静态提前排，动态边跑边排

线程调度

对比项目	用户级线程（ULT）	内核级线程（KLT）
调度主体	用户空间线程库，内核看不到线程，内核只调度进程	操作系统内核，内核直接管理、调度单个线程
时间片分配	时间片分配给进程，进程拿到时间片后内部轮转线程；同进程线程连续执行，不能穿插其他进程线程（例：A1A2A3→B1B2B3，不能 A1B1A2B2）	时间片分配给单个线程，线程是 CPU 调度单位；不同进程线程可交叉运行：A1→B1→A2→B2
线程切换位置	用户态切换，不进内核，无系统调用、切换开销小	内核态切换，需要陷入内核，切换开销更大
阻塞表现	单个线程调用阻塞系统调用 → 整个进程全部阻塞（内核只识别进程阻塞）	单个线程阻塞，同进程其余线程不受影响，仍可调度运行
多核 CPU	一个进程同一时刻只能占 1 个 CPU 核心，多线程无法并行，只能并发	同进程多线程可分派到多个 CPU 核心，真正多核并行
OS 改动	无需修改操作系统内核，线程库在用户层实现	需要操作系统内核原生支持线程管理

用户：内核管进程、用户管线程，一堵全堵、不能多核并行；

内核：内核管线程、分片到线程，单堵单停、多核自由并行