考研笔记

第 2 章 名词库

这一页是复习主入口。 目标是把第 2 章的名词收全，并把每个词的边界和适用范围钉死。

每条最多四行：

  • 是：一句话定义
  • 不是：划掉最常见的错误理解
  • 易混：成对的对手是谁
  • 范围：该结论在什么条件下才成立（只在有范围限制时才出现，务必留意）

正文用 [[os-glossary-ch02#进程 (Process)|进程]] 这样的锚点链接进来，鼠标悬停即可预览。

建设进度：✅ 2.1 进程与线程　✅ 2.2 CPU 调度　✅ 2.3 同步与互斥　✅ 2.4 死锁　（第 2 章完整）

2.1.1 进程的概念和特征

多道程序设计

  • 是：内存中同时存放多道程序，使它们交替占用 CPU，以便某道程序等待 I/O 时 CPU 转去执行别的程序。
  • 不是：不等于”同时执行”。单处理机下任一时刻仍只有一道程序在 CPU 上跑。
  • 易混：它是并发的实现前提，也是本章一切复杂性（异步、互斥、死锁）的总源头。

作业 (Job)

  • 是：用户提交给系统的一个独立的计算任务，包含程序、数据和作业说明书。作业驻留在外存的后备队列中。
  • 不是：作业不是进程。作业没有 PCB、不占内存、不参与处理机调度。
  • 易混：↔ 进程。作业被高级调度选中后才被建立成进程。
  • 范围：“作业”这一概念主要用于批处理系统。交互式系统中通常直接讨论进程。

进程 (Process)

  • 是：程序在某个数据集合上的一次运行过程，是系统进行资源分配和调度的独立单位。
  • 不是：不是”正在运行的程序”这么简单——同一个程序跑两次是两个进程；一个进程也可以在生命周期中执行多个程序（exec 换掉代码段后，进程仍是原来那个）。
  • 易混：↔ 程序（静态 vs 动态）；↔ 进程实体（进程是”过程”，进程实体是”这一时刻的快照”）。
  • 范围：“进程是调度的基本单位”这句话只在未引入线程时成立。引入线程后调度单位变为线程，进程仅保留资源分配单位的身份。

程序 (Program)

  • 是：存放在外存上的一段静态指令和数据的集合。
  • 不是：不占有 CPU、不拥有资源、没有状态。
  • 易混：↔ 进程。教材”进程是程序的一次执行”里，“一次”才是重点。

进程控制块 (PCB, Process Control Block)

  • 是：操作系统为管理进程而设置的数据结构，存放进程标识、状态、调度信息、资源清单、现场信息等。PCB 是进程存在的唯一标志。
  • 不是：不在用户地址空间里，进程自己碰不到；也不是”进程的全部”，它只含管理信息，不含代码和用户数据。
  • 易混：↔ 进程实体（PCB 是进程实体的一部分）；↔ TCB。

进程实体（进程映像）

  • 是：程序段 + 相关数据段 + PCB 三者的总和，是进程在某一时刻的静态快照。
  • 不是：不是动态概念。“进程”是动态的过程，“进程映像”是按下暂停键后看到的样子。
  • 易混：↔ 进程上下文。高频对：映像强调”内存里有什么”，上下文强调”恢复执行需要什么”。

进程的五个特征

  • 是：动态性（最基本特征）、并发性、独立性、异步性、结构性。
  • 不是：最基本的特征是”动态性”而非”并发性”——这是选择题常设的陷阱。
  • 易混：↔ 下面”操作系统的四个特征”（并发、共享、虚拟、异步），两组特征分属不同主体，不要混答。

并发 (Concurrency)

  • 是：多个进程在同一时间段内都在推进。宏观上同时，微观上（单核）交替执行。
  • 不是：不是同一时刻真的一起跑。
  • 易混：↔ 并行。单核可以并发，不能并行。

并行 (Parallelism)

  • 是：多个进程在同一时刻真正同时执行，需要多个处理单元（多核/多处理机）。
  • 不是：不是并发的同义词，是并发的一个特例。
  • 易混：↔ 并发。
  • 范围：只有在多处理机或多核环境下才谈得上并行。 题干出现”单处理机”时，一切”并行”选项都可直接排除。

共享 (Sharing)

  • 是：系统资源可被内存中多个并发执行的进程共同使用。分两类：互斥共享（一段时间内只允许一个进程访问，如打印机）与同时共享（宏观上允许多进程同时访问，如磁盘、可重入代码）。
  • 不是：“同时共享”在微观上通常仍是交替访问，不是真正的同时。
  • 易混：↔ 临界资源。互斥共享的资源就是临界资源。

虚拟 (Virtuality)

  • 是：把一个物理实体变成多个逻辑实体（时分复用，如虚拟处理机），或把多个物理实体抽象成一个逻辑实体（空分复用，如虚拟内存）。
  • 不是：虚拟出来的东西没有实际物理存在，只是用户感觉上存在。
  • 易混：虚拟必须以并发为前提——没有并发就无需也无法虚拟。

异步性 (Asynchronism)

  • 是：进程以不可预知的速度向前推进——何时被调度走、等多久资源，均不确定。
  • 不是：不是”出错”，而是多道程序环境下正常且必然的现象。
  • 易混：异步性是原因，失去封闭性和失去可再现性是后果。
  • 范围：进程的相对推进速度由调度策略决定，进程自身无法控制。

封闭性

  • 是：程序独占运行时，执行结果只由初始条件决定，不受外界影响。这是单道程序才有的性质。
  • 不是：并发环境下没有封闭性。
  • 易混：↔ 可再现性。准确表述是：并发进程共享变量，其执行结果与速度有关。

可再现性

  • 是：同样的初始条件，无论运行多少次、环境如何，都得到同样的结果。
  • 不是：并发环境下不再具备。
  • 易混：封闭性是因，可再现性是果。失去封闭性必然失去可再现性，反之不必然。

2.1.2 进程的组成

链接方式 / 索引方式

  • 是：PCB 的两种组织方式。链接方式把同状态的 PCB 用指针串成队列；索引方式为每种状态建一张索引表指向对应 PCB。
  • 不是：不是二选一的对立，实际系统可混用。
  • 易混：索引方式查找快，但需额外维护索引表。

就绪队列 / 阻塞队列

  • 是：按状态组织 PCB 形成的队列。就绪队列可按优先级组织成多条；阻塞队列通常按等待事件分成多条（等打印机一条、等磁盘一条）。
  • 不是：阻塞队列不是只有一条。分开的目的是释放某资源时可直接到对应队列取队首唤醒，无须遍历筛选。
  • 易混：这正是”释放一台打印机只唤醒一个进程”能够高效实现的原因。

进程上下文 (Context)

  • 是：进程运行时 CPU 及相关寄存器的现场信息加上内核中的控制信息——即”要让该进程从断点继续执行，必须保存和恢复的全部内容”。
  • 不是：中断向量不属于进程上下文。它是全系统共享一份的固定表，不随进程切换而保存恢复。
  • 易混：↔ 进程映像。映像 = 内存里有什么；上下文 = 切换时要存什么。二者有交集但互不包含：代码段在映像不在上下文，CPU 寄存器现值在上下文不在映像。

正文段 / 数据段 / BSS 段 / 堆 / 栈

  • 是：进程地址空间的五个区域。正文段放代码和常量（只读）；数据段放已初始化的全局与静态变量；BSS 放未初始化的全局与静态变量；堆放动态分配空间（向高地址增长）；栈放局部变量、参数、返回地址（向低地址增长）。
  • 不是：BSS 不占可执行文件体积（只记录需要多大，装入时清零），但占内存。
  • 易混：教材也有粗粒度三分法（正文段/堆/栈），把两类全局变量都算进正文段。看选项给的粒度决定用哪一档。

静态数据 / BSS

  • 是：static 变量和全局变量具有静态存储期，程序启动即存在、结束才消亡。去处只看是否被初始化：初始化为非零 → 数据段；未初始化或初始化为 0 → BSS。
  • 不是：const 不一定被展开到代码中。基本类型且未取地址时编译器常做常量折叠；一旦取地址或为数组/结构体，则必须占据存储空间，通常在只读数据段（.rodata）。
  • 易混：考试层面只需记住”常量在只读区”。

2.1.3 进程的状态与转换

就绪态 (Ready)

  • 是：进程已获得除 CPU 之外的一切所需资源，只等 CPU。
  • 不是：不是”什么都没准备好”，恰恰相反——万事俱备，只欠 CPU。
  • 易混：↔ 阻塞态。判据只有一个：缺的是不是 CPU。

运行态 (Running)

  • 是：进程正在 CPU 上执行。
  • 不是：不是”恰好一个”。单处理机下运行态进程数为 0 个或 1 个，全部阻塞或死锁时为 0。
  • 易混：“至多一个” ✅ 正确 ／ “有且仅有一个” ❌ 错误。
  • 范围：“至多一个”这一结论仅限单处理机。n 个处理机下最多 n 个进程处于运行态。

阻塞态（等待态）

  • 是：进程因等待某事件（I/O 完成、获得资源、等信号）而暂时无法运行，此时即使把 CPU 给它也没用。
  • 不是：不是”被调度走了”。被调度走是就绪，不是阻塞。
  • 易混：↔ 挂起态（阻塞看等不等事件，挂起看在不在内存）。

创建态

  • 是：进程正在被创建——已申请 PCB 并填写部分信息，但资源尚未分配完毕，还不能被调度。
  • 不是：创建态的进程不在就绪队列里，不参与调度。
  • 易混：创建完成后转入就绪态，不会直接转入运行态。

结束态

  • 是：进程正在从系统中消失——已停止运行，操作系统正在回收其资源，PCB 尚未删除。
  • 不是：PCB 被删除后进程才真正不存在；结束态时 PCB 仍在。
  • 易混：僵尸进程即停留在结束态、PCB 未被父进程回收的进程。

状态转换的四条合法边

  • 是：就绪→运行（被调度，进入运行态的唯一途径）、运行→就绪（时间片到/被抢占）、运行→阻塞（主动请求得不到满足）、阻塞→就绪（被动，事件完成后被唤醒）。
  • 不是：阻塞→运行不存在；就绪→阻塞不存在。这两条是最常考的”不可能转换”。
  • 易混：运行→阻塞由进程自己调用阻塞原语（主动）；阻塞→就绪由别人执行唤醒原语（被动）。方向别记反。

挂起态 (Suspend)

  • 是：进程被换出到外存，不再占用内存。分静止就绪、静止阻塞。
  • 不是：不是阻塞的同义词。挂起看在不在内存，阻塞看等不等事件——两个维度正交。
  • 易混：由此组合出活动就绪、静止就绪、活动阻塞、静止阻塞四种（七状态模型）。

活动就绪 / 静止就绪 / 活动阻塞 / 静止阻塞

  • 是：三态与”是否在内存”两个维度的组合。活动=在内存，静止=已换出到外存。
  • 不是：静止就绪的进程不能直接被调度上 CPU，必须先被换回内存变成活动就绪。
  • 易混：静止阻塞的进程即使等待事件完成，也只能转为静止就绪，而非直接就绪可运行。

2.1.4 进程控制

原语 (Primitive)

  • 是：由若干条指令构成、完成特定功能的程序段，执行期间不可中断，具有原子性。用关中断/开中断实现。
  • 不是：不是”很快的函数”。快不快无所谓，不可分割才是本质。
  • 易混：↔ 系统调用（系统调用是接口，原语是实现手段）。
  • 范围：关中断只能屏蔽外部中断，不能屏蔽内部异常；且原语必须短，否则影响系统响应和计时精度。

进程创建

  • 是：申请空白 PCB → 为新进程分配资源 → 初始化 PCB → 插入就绪队列。四类来源：用户登录、作业调度、系统提供服务、用户程序请求。
  • 不是：不是”把程序装入内存”。在请求分页系统中代码可能等到访问时才由缺页中断调入。
  • 易混：作业调度这一项中，调度程序是常驻的发起者，被创建的是被选中的作业。

进程终止

  • 是：三类事件——正常结束（自行 exit）、异常结束（越界、保护错、非法指令、特权指令错、运行超时、算术错、I/O 故障）、外界干预（kill、父进程终止）。
  • 不是：异常结束的各项由硬件检测后报告给 OS，不是 OS 主动巡查发现的。
  • 易混：越界/保护错由 MMU 检测；非法指令/特权指令错由 CPU 译码检测；算术错由 ALU 检测；运行超时靠时钟中断；I/O 故障由设备控制器报告。

阻塞原语 / 唤醒原语

  • 是：阻塞原语保存现场、改状态、挂入等待队列并转调度；唤醒原语从等待队列摘下、改状态、挂入就绪队列。
  • 不是：唤醒不能由进程自己完成——阻塞后它一条指令都执行不了。
  • 易混：二者必须成对使用。阻塞后无人唤醒即永久等待，这是死锁与饥饿的源头。

进程切换 vs 模式切换

  • 是：进程切换 = 换掉当前运行的进程（保存 A 的现场、恢复 B 的现场、切换页表、刷新 TLB）；模式切换 = 同一进程从用户态进入内核态或返回。
  • 不是：模式切换不一定引起进程切换。系统调用进内核，处理完通常还回到原进程。
  • 易混：进程切换一定伴随模式切换，反之不成立。 这是全书最高频的边界之一。
  • 范围：进程切换只能在内核态完成，因为它要访问 PCB 和页表基址寄存器等受保护资源。

父进程 / 子进程 / 进程树

  • 是：由某进程创建出的新进程称为其子进程，创建者为父进程；由此形成层次结构即进程树。
  • 不是：Windows 不支持进程的层次结构，各进程地位相同；层次结构主要见于 UNIX/Linux。
  • 易混：fork 创建子进程（复制父进程地址空间），exec 用新程序替换当前进程的地址空间——exec 不创建新进程。

2.1.5 进程的通信

低级通信 vs 高级通信

  • 是：判据是一次能传多少信息。低级通信只能传极少量控制信息（信号量 P/V、信号），效率低且对用户不透明；高级通信能传大批量数据，由 OS 封装接口（共享存储、消息传递、管道）。
  • 不是：“低级=基于数据结构”不是指”用了什么数据结构实现”，而是指所传递的东西本身就是一个很小的数据结构，容量被其大小卡死。
  • 易混：↔ 直接/间接通信。这是两条独立的分类线：一条看数据量，一条看要不要指名收件人。

共享存储 (Shared Memory)

  • 是：两个进程各自把同一块物理内存映射进自己的地址空间，直接读写完成通信。三种方式中速度最快。
  • 不是：OS 不负责互斥。同步须由进程自己用 P/V 或锁完成。
  • 易混：↔ 管道（管道的同步由 OS 自动完成）；↔ ptrace 式内存访问（共享存储需双方合意，ptrace 是单方面侵入且需权限）。
  • 范围：教材把它细分为基于共享数据结构（容量小，属低级通信）与基于共享存储区（容量大，属高级通信）——同一个”共享存储”标题下横跨了低级与高级两档，答题时注意题干问的是哪一种。

消息传递 (Message Passing)

  • 是：以格式化的消息（消息头 + 消息体）为单位，通过 send/receive 原语交换数据，OS 负责底层传输。
  • 不是：不是”一定要走网络”。同机进程间同样使用消息传递。
  • 易混：需经内核两次拷贝（发送方→内核缓冲→接收方），因此比共享存储慢。

直接通信 vs 间接通信

  • 是：直接通信 send(P2, msg) 把消息挂到目标进程的消息缓冲队列，必须指名收件人；间接通信 send(信箱A, msg) 把消息发到信箱，谁来取都行。
  • 不是：间接通信不等于低级通信，二者是不同维度。
  • 易混：间接通信下收发双方不必知道对方，也不必同时在场——这是”解耦”的确切含义，也是与消息队列（MQ）对应的那一层语义。

信箱 (Mailbox)

  • 是：独立于收发双方的中间实体，属于消息传递中的间接通信，是高级通信。
  • 不是：不是低级通信，也不是共享存储。
  • 易混：↔ MQ。信箱是同机内由内核维护的内存结构，不具备 MQ 的跨机、持久化、重试确认等工程特性。

管道 (Pipe)

  • 是：一个固定大小的内核缓冲区，被当作特殊文件读写，半双工，一端写一端读。写满则写阻塞，读空则读阻塞。
  • 不是：管道不是共享内存。数据读走即消失，不能反复读同一位置；也没有广播语义——多个读者时一份数据只被其中一个读到。
  • 易混：↔ 共享存储（管道流式、一次性；共享存储可反复读）。tee 能一份输入送多处，靠的是用户态自行复制，恰好反证管道无广播能力。
  • 范围：管道的同步互斥由 OS 自动完成，这一点与共享存储正好相反，是最高频的一对。

匿名管道 / 命名管道 (FIFO)

  • 是：匿名管道无名字，只能用于有亲缘关系的进程（父子进程，通过 fork 继承文件描述符），即 shell 中的 |；命名管道有路径名，任意进程均可使用。
  • 不是：> 重定向不是管道——它把 stdout 换成一个文件，走的是文件系统。
  • 易混：ls | grep x 中 shell 创建的是匿名管道。

信号 (Signal)

  • 是：OS 发给进程的一种异步通知，只传递”发生了某类事件”这一语义，内容仅为一个编号。
  • 不是：不传数据，不是消息队列，不是共享内存；也不是 Qt 的 signal 或 JS 的事件——那些是纯用户态、同进程内的回调机制，内核并不知情。
  • 易混：三种处理方式为执行默认操作、捕捉并自定义处理、忽略。但 SIGKILL(9) 与 SIGSTOP(19) 不可捕捉、不可忽略，否则无法强制终止流氓进程。
  • 范围：信号在”从内核态返回用户态之前”被检测。因为信号位图在 PCB（内核空间）中，只有内核态才有资格读取；且这个时机不额外增加开销。代价是信号处理存在延迟。

2.1.6 线程和多线程模型

线程 (Thread)

  • 是：进程内的一条执行流，是调度的基本单位；同进程内的线程共享地址空间和大部分资源，各自私有程序计数器、一组寄存器、栈及 TCB。
  • 不是：线程不是资源分配的基本单位（那仍是进程）。
  • 易混：“资源分配单位 = 进程，调度单位 = 线程” 是引入线程后最核心的一句话。
  • 范围：“线程是调度的基本单位”仅在内核级线程语境下成立。用户级线程对内核不可见，内核调度的仍是进程。

线程控制块 (TCB)

  • 是：记录线程标识、现场、状态、优先级等信息的数据结构。
  • 不是：TCB 比 PCB 小得多——因为线程不拥有资源，无须记录资源清单。
  • 易混：TCB 的位置决定线程类型：在用户空间即用户级线程，在内核空间即内核级线程。

用户级线程 (ULT)

  • 是：由用户态线程库管理，内核完全不知其存在。切换无须进内核，开销极小，且调度策略可由应用自定制。
  • 不是：一个线程阻塞会导致整个进程阻塞（内核只看到进程），且无法利用多核并行（内核以进程为单位分配 CPU）。
  • 易混：↔ 内核级线程。判据：内核知不知道。
  • 范围：能引起 ULT 切换的必须是”用户态就能决定并执行”的事件（如线程同步）。系统调用、I/O 请求、异常处理都会陷入内核，内核只认进程，因此都不能引起 ULT 切换。

内核级线程 (KLT)

  • 是：由内核管理和调度，TCB 在内核中。一个线程阻塞不影响同进程其他线程，可真正并行。
  • 不是：切换开销不比 ULT 小——所有线程管理操作都要经系统调用进内核。
  • 易混：JVM 的平台线程是 1:1（一个 Java 线程对应一个内核线程）；虚拟线程是在其上做的 M:N 用户态调度。

线程库

  • 是：在用户态实现线程创建、调度、同步的函数库，是用户级线程的管理者。
  • 不是：线程库位于用户空间，内核不参与其调度决策。
  • 易混：内核级线程不依赖线程库调度，而由内核调度程序直接管理。

多线程模型

  • 是：多对一、一对一、多对多，描述用户级线程与内核级线程的映射关系。
  • 不是：多对一模型下不能并行，且一个线程阻塞则全进程阻塞。
  • 易混：一对一并发度最高但创建开销大且内核线程数有上限；多对多兼顾两者。
  • 范围：考题固定套路——问”哪种模型下一个线程阻塞会导致整个进程阻塞”，答多对一。

轻量级进程 (LWP)

  • 是：多对多模型中位于用户级线程与内核级线程之间的中间层，可视为内核支持的、供用户线程附着运行的”虚拟处理器”。
  • 不是：LWP 不是用户级线程，它由内核支持。
  • 易混：一个进程可有多个 LWP，每个 LWP 对应一个内核级线程。

套管程序 (Jacketing)

  • 是：把阻塞式系统调用改造成非阻塞式的技术，用以缓解用户级线程”一个阻塞则全进程阻塞”的缺陷。
  • 不是：它不能根本消除该缺陷，只是绕开。
  • 易混：JDK 虚拟线程把标准库阻塞点改写为非阻塞并挂起虚拟线程，思路与此一致。

线程切换 vs 进程切换

  • 是：同进程内的线程切换只需保存/恢复少量寄存器和栈指针；进程切换还须切换地址空间（换页表基址寄存器、TLB 全部失效）。
  • 不是：不同进程的线程之间切换，本质上仍是进程切换，开销并不小。
  • 易混：线程”轻”的全部来源就是不换页表、TLB 不失效。

2.2.1 调度的概念

高级调度（作业调度）

  • 是：从外存后备队列中挑选作业调入内存，为其建立 PCB，使之成为进程进入就绪队列。
  • 不是：调度程序本身是常驻的，被创建的是被选中的作业，不是调度程序自己。
  • 易混：每个作业只被调入一次、调出一次，这与低级调度的反复选中形成对照。
  • 范围：主要存在于批处理系统。分时、实时系统通常直接建立进程，无后备作业队列。

中级调度（内存调度）

  • 是：把暂时不能运行的进程换出到外存（进入挂起态），条件合适时再换回内存，以提高内存利用率和系统吞吐量。
  • 不是：换出时PCB 仍留在内存，只有程序和数据被换到外存——否则 OS 无从知道它的存在。
  • 易混：对应状态转换是”就绪↔静止就绪""阻塞↔静止阻塞”。
  • 范围：仅存在于采用了对换/虚拟存储技术的系统。

低级调度（进程调度）

  • 是：从就绪队列中选一个进程，把 CPU 分配给它。频率最高（毫秒级）。
  • 不是：不创建也不撤销进程，只在已有的 PCB 之间做选择。
  • 易混：↔ 高级调度（后者”无中生有”地创建 PCB）。
  • 范围：是唯一必不可少的调度层级，任何多道程序系统都必须有。选择题问”哪种调度必不可少”，答案恒为进程调度。

分时系统

  • 是：把 CPU 时间划分成很短的时间片轮流分配给各联机用户作业，使每个用户都感觉独占整台机器。四特征为多路性、独立性、及时性、交互性。
  • 不是：不追求平均周转时间最短，核心追求是响应时间短。
  • 易混：因此通常采用时间片轮转（RR）——只有 RR 能保证响应时间有上界。

实时系统

  • 是：要求在规定时限（deadline）内完成对外部事件的响应。分硬实时（绝对不能超时）与软实时（允许偶尔超时）。
  • 不是：不以平均性能为评价标准，在乎的是最坏情况。
  • 易混：通常采用抢占式优先级调度——紧急任务必须能立刻剥夺 CPU。

2.2.2 调度的实现

调度程序的三部分

  • 是：排队器（把就绪进程排成队列）、分派器（取出 PCB，把 CPU 交给选中进程）、上下文切换器（执行两次上下文切换）。
  • 不是：三者不是并列的算法，而是把”换人”拆成决策准备与执行两个环节。
  • 易混：调度是决策（选谁），分派是执行（怎么换过去）。考题问的是哪一环节要看清。

不能进行调度的三种情况

  • 是：① 处理中断的过程中；② 进程处于操作系统内核程序临界区中；③ **原子操作（原语）**执行过程中。
  • 不是：普通临界区是可以调度的，不要与内核程序临界区混为一谈。
  • 易混：三条的理由各不相同——中断处理中系统状态不完整；内核临界区锁住核心数据结构会导致系统卡死；原语本就处于关中断状态。

内核程序临界区 vs 普通临界区

  • 是：内核程序临界区访问内核数据结构（就绪队列、PCB 链表、内存分配表）；普通临界区访问普通临界资源（打印机、共享文件）。
  • 不是：只有内核程序临界区禁止调度。普通临界区不但可以调度，而且应该允许——否则 CPU 要陪着占用打印机的进程一起空等。
  • 易混：判据是被锁住的是内核自己的数据结构，还是外部资源。

剥夺式 vs 非剥夺式

  • 是：非剥夺（非抢占）只有当前进程主动让出才重新调度；剥夺（抢占）允许更紧迫的进程立即夺走 CPU。
  • 不是：抢占不是随意的，须遵循优先权原则、短作业优先原则或时间片原则。
  • 范围：分时系统与实时系统必须采用抢占式，否则响应时间和截止时间无法保证。

闲逛进程 (idle)

  • 是：就绪队列为空时运行的进程。优先级最低，不需要 CPU 之外的任何资源因而永不阻塞，执行能耗低的指令（如 HLT）。
  • 不是：不是空转的死循环。HLT 让 CPU 进入低功耗停机状态、停止取指，直到中断到来才唤醒。因此”CPU 一直满负荷工作”这一前提本身不成立。
  • 易混：统计”运行态进程数”时，闲逛进程通常不计入用户进程——这正是运行态可以是 0 个的由来。

上下文切换

  • 是：保存当前进程的现场并恢复新进程的现场。开销主要来自切换页表基址寄存器导致的 TLB 全部失效。
  • 不是：只能在内核态完成。权限上要读写 PCB、改页表基址寄存器（特权操作）；逻辑上决策依据是内核数据结构，用户态看不见。
  • 易混：调度 ≠ 切换。调度的结果可能仍是原进程，此时不发生切换。

处理机亲和性 (Affinity)

  • 是：让进程尽量始终在同一处理机上运行，以保留该核 Cache 与 TLB 中已有的数据。软亲和性可迁移，硬亲和性可指定 CPU 子集。
  • 不是：不是为了公平或负载均衡，恰恰相反——它与负载均衡是一对权衡。
  • 范围：多处理机调度在 408 中属低频考点，一般只考概念辨析，不涉及复杂计算。

2.2.3 调度的目标

周转时间

  • 是：完成时间 − 提交时间。包含四段：外存等待作业调度 + 内存等待进程调度 + CPU 执行 + 等待 I/O 完成。
  • 不是：不等于运行时间，恒 ≥ 运行时间。
  • 易混：↔ 响应时间。周转时间的终点是”完成”，响应时间的终点是”首次响应”。

带权周转时间

  • 是：周转时间 / 实际运行时间。用于消除作业长短差异，反映用户的相对等待感受。
  • 不是：恒 ≥ 1。算出小于 1 必定出错——这是最好用的自检点。
  • 易混：设立它的理由是周转时间的绝对值对短作业不公平：等同样久，短作业的体验差得多。

等待时间

  • 是：周转时间 − 实际运行时间，即等待处理机的时间之和。
  • 不是：不包含等待 I/O 的时间——进程做 I/O 时是在被设备服务，调度算法对此无能为力。
  • 范围：口径随对象而变。对进程指等待处理机的时间；对作业还须加上在外存后备队列上等待作业调度的时间。

响应时间

  • 是：首次产生响应的时刻 − 提交请求的时刻。
  • 不是：终点是首次响应，不是完成。一个作业可能 1ms 就有首次响应，却要 10s 才跑完。
  • 易混：这是交互式/分时系统最看重的指标，也是分时系统采用 RR 的直接原因。

系统吞吐量 / CPU 利用率

  • 是：吞吐量 = 完成作业数 / 总时间；CPU 利用率 = 有效工作时间 / 总时间。
  • 不是：吞吐量高不等于每个作业都快——长作业多则吞吐量低。
  • 易混：各指标互相冲突，不存在全面最优的算法。选算法的实质是决定牺牲哪一项。

2.2.4 进程切换

进程切换的三步

  • 是：① 保存原进程上下文（现场写回 PCB）② 更新 PCB 并转移队列 ③ 恢复新进程上下文并切换地址空间。
  • 不是：开销的大头不是保存寄存器，而是切换页表基址寄存器导致的 TLB 全部失效与 Cache 命中率骤降。
  • 易混：这正是线程”轻”的原因——同进程内线程切换不换地址空间，上述间接开销全部避免。
  • 范围：进程切换只能在内核态完成。权限上要读写 PCB、改页表基址寄存器；逻辑上决策依据是内核数据结构。故进程切换必然伴随模式切换，反之不成立。

调度 vs 切换

  • 是：调度是决策（按算法选出下一个进程）；切换是执行（保存旧现场、恢复新现场）。先有调度，后有切换。
  • 不是：“发生了调度”不等于”发生了切换”——调度的结果可能仍是原进程（如时间片到但无更合适者），此时一次切换都不做。
  • 易混：↔ 上下文切换。上下文切换是那个具体动作；进程切换是整件事，还含更新 PCB、转移队列、切换地址空间。上下文切换器会执行两次上下文切换。

2.2.5 CPU 调度算法

FCFS 先来先服务

  • 是：按到达先后排队，非抢占。最公平、实现最简单。
  • 不是：不会导致饥饿（排队就一定轮得到），但对短作业极不友好。
  • 易混：↔ 护航效应。其平均带权周转时间通常很大。

护航效应 (Convoy Effect)

  • 是：FCFS 下一个长作业排在队首，后面所有短作业被迫陪等的现象。
  • 不是：不是饥饿。护航只是”等得久”，最终仍会执行；饥饿是”可能永远轮不到”。
  • 易混：后果集中体现在短作业的带权周转时间畸高上。

SJF 短作业优先 / SPF 短进程优先

  • 是：每次选运行时间最短的，非抢占。属贪心算法，最优性可由交换论证严格证明。
  • 不是：会导致饥饿——短作业不断到来则长作业永远排不上，极端情况下饿死。
  • 范围：“平均周转时间最短”仅在①所有作业同时到达 ②非抢占 两个前提下成立。 到达时间不同时，最优者是 SRTN。这是本章最常被抽掉限定条件的结论。

SRTN 最短剩余时间优先

  • 是：SJF 的抢占版本，比较剩余运行时间。到达时间不同的一般情形下平均周转时间最小。
  • 不是：饥饿倾向比 SJF 更严重，且有抢占带来的切换开销。
  • 易混：手算时决策点多了”新进程到达”一类，最易遗漏。

HRRN 高响应比优先

  • 是：非抢占，选响应比最高者。响应比 等待时间要求服务时间。
  • 不是：不会产生饥饿——等待时间增长会推高响应比，长作业最终必被选中。这是它相对 SJF 的核心优势。
  • 易混：它是 FCFS 与 SJF 的折中：等待时间相同则短作业优先，服务时间相同则先来者优先。

RR 时间片轮转

  • 是：按到达顺序排队，每进程运行一个时间片，用完即被剥夺并排到队尾。抢占式，分时系统标配。
  • 不是：不会饥饿。n 个进程、时间片 q，则任一进程最多等待 。
  • 易混：时间片过大退化为 FCFS；过小则切换开销占比过高。一般要求切换开销不超过 1%。
  • 范围：RR 的结果依赖初始队列顺序。题目未给时按到达顺序；同时到达按题目列出顺序。另需约定：时间片用完与新进程到达同时发生时，新到达者先入队。

优先级调度

  • 是：选优先级最高者，抢占与非抢占均可。静态优先级创建后不变，动态优先级可随等待时间提升。
  • 不是：静态优先级会导致饥饿；动态优先级可缓解。
  • 易混：优先级一般规律为——系统进程 > 用户进程；前台（交互）> 后台；I/O 型 > 计算型（让 I/O 型尽快让出 CPU，使设备与 CPU 并行）。

多级队列

  • 是：设置多个就绪队列，不同队列采用不同调度算法，队列间有优先级。
  • 不是：进程被固定分配到某队列，终生不能移动。
  • 易混：↔ 多级反馈队列。区别就在能否移动。

多级反馈队列

  • 是：多级队列的改进，进程可在队列间移动。优先级从高到低、时间片从小到大；新进程入第 1 级；时间片内未完成则降入下一级；仅当前 级全空才调度第 级；更高级队列有进程到达则立即抢占，被抢占者回原队列队尾。
  • 不是：仍会产生饥饿——高优先级队列持续有进程则低级饿死。
  • 易混：它无须预知作业长度即自动偏好短作业：短作业在前几级即完成；长作业逐级下沉但时间片变大，一旦轮到可连续执行。综合性能最好。

饥饿 (Starvation)

  • 是：某进程因调度策略而长期（可能永远）得不到所需资源或 CPU。
  • 不是：不是死锁。饥饿的进程在理论上仍可能被调度到，只是概率极低；死锁则是循环等待，绝无可能自行解除。
  • 易混：只有 FCFS、HRRN、RR 三种算法不会饥饿。它们的共同点是决策依据含”等待时间”或有轮转保证。

2.2.6 多处理机调度

非对称多处理 AMP vs 对称多处理 SMP

  • 是：AMP 指定一个主处理机负责所有调度决策，其余只执行用户代码；SMP 中每个处理机都可自我调度，地位平等。
  • 不是：AMP 不需要考虑互斥（只有主处理机访问系统数据结构）；SMP 必须解决互斥——这正是多处理器系统上自旋锁不可或缺的原因。
  • 易混：SMP 是现代主流；AMP 的瓶颈在主处理机。

处理机亲和性 (Affinity)

  • 是：让进程尽量始终在同一处理机上运行，以保留该核 Cache 与 TLB 中已有的内容。软亲和性可迁移，硬亲和性可指定 CPU 子集。
  • 不是：不是为了公平。它的唯一理由是保留缓存局部性，而且它妨碍负载均衡。
  • 易混：迁移的代价本质上就是一次”更彻底的” Cache/TLB 失效，与进程切换开销同源。
  • 范围：亲和性与负载均衡互相冲突——前者要求尽量不迁移，后者要求哪里空往哪迁。实际系统靠负载差异阈值折中。亲和性保单个进程的效率，负载均衡保整体资源利用率。

负载均衡

  • 是：设法让各处理机工作量大致均等。推迁移由专门任务周期性检查后把进程推给空闲核；拉迁移由空闲核主动拉取。
  • 不是：共用一个就绪队列天然负载均衡，但队列本身成为临界资源、争用严重；每核私有队列无争用，但需额外的均衡机制。
  • 范围：多处理机调度在 408 中属低频考点，一般只考概念辨析，不涉及计算。

2.3 同步与互斥

同步 (Synchronization)

  • 是：多个进程为完成同一任务而协作，因而在执行次序上有确定的先后要求。又称直接制约关系。
  • 不是：不是”同时发生”。中文的”同步”在这里指协调次序，不是 simultaneity。
  • 易混：↔ 互斥。同步是”必须按序”，互斥是”不能同时”。
  • 范围：互斥可视为同步的特例——它只要求不重叠，不要求谁先谁后。反之不成立。

互斥 (Mutual Exclusion)

  • 是：多个进程因共享同一临界资源而互相排斥，同一时刻只允许一个进程访问。又称间接制约关系。
  • 不是：进程之间本无关系，制约是通过资源间接传递的，故称”间接”。
  • 易混：↔ 同步（直接制约，源于协作需求）。

临界资源 (Critical Resource)

  • 是：一段时间内只允许一个进程访问的资源，如打印机、共享变量。
  • 不是：不是”稀缺资源”。判据是能否被同时访问，与数量多少无关。
  • 易混：↔ 共享。互斥共享的资源就是临界资源；同时共享的资源（只读文件、可重入代码）不是。

临界区 (Critical Section)

  • 是：访问临界资源的那段代码。
  • 不是：临界区是代码，临界资源是资源。 不同进程访问同一临界资源的代码段是不同的临界区，但必须互斥执行。
  • 易混：进程访问临界资源的完整结构为进入区 → 临界区 → 退出区 → 剩余区，其中进入区与退出区由同步机制提供，另两段是进程自己的业务代码。
  • 范围：本节讨论的是普通临界区（允许调度）。内核程序临界区规则相反，禁止调度。

同步机制四准则

  • 是：① 空闲让进（空闲时应允许进入）② 忙则等待（有人在内则须等待）③ 有限等待（有限时间内能进入）④ 让权等待（进不去就释放 CPU）。
  • 不是：四条分量并不相同。违反②是致命错误（互斥失效、结果出错）；违反①③是功能缺陷（低效或饥饿）；违反④只是性能问题（忙等浪费 CPU，功能仍正确）。
  • 易混：正因为④只是性能问题，几乎所有硬件方法和自旋锁都违反④却仍被广泛使用。

单标志法

  • 是：设公用变量 turn 指示允许进入者，进程退出时把 turn 交给对方。
  • 不是：违反”空闲让进”。两进程必须严格交替进入；若一方不再进入，另一方即使面对空闲临界区也永远进不去。
  • 易混：它把”互斥”做成了”轮流”，管得太死。

双标志先检查法

  • 是：while(flag[j]); flag[i]=true; —— 先检查对方，再设置自己。
  • 不是：违反”忙则等待”，是四个软件算法中唯一会导致互斥失效的，最严重。
  • 易混：病根在于**“检查”与”上锁”之间可被中断**，两进程可同时通过检查。这正是硬件指令（TS、Swap）要把二者合并为原子操作的全部理由。

双标志后检查法

  • 是：flag[i]=true; while(flag[j]); —— 先设置自己，再检查对方。
  • 不是：互斥实现了，但违反”空闲让进”和”有限等待”——双方几乎同时置位则互相谦让，谁也进不去。
  • 易混：教材称此现象为”饥饿”，但两进程始终在忙等循环中未曾阻塞，严格说属于活锁，与死锁不同。

Peterson 算法

  • 是：flag[i]=true; turn=j; while(flag[j] && turn==j); —— 既表明意愿又主动谦让。
  • 不是：只违反”让权等待”（仍是忙等），其余三条准则全部满足。
  • 易混：能打破僵局的原因是 turn 的最终值唯一——两进程抢着赋值，最后写入的那个决定谁等待，故必有且仅有一方通过。
  • 范围：其正确性依赖内存访问的顺序一致性。现代 CPU 存在指令重排与写缓冲，实际使用必须插入内存屏障。此点超出考纲。

中断屏蔽法

  • 是：关中断; 临界区; 开中断;。与原语的实现手段相同。
  • 不是：不能给用户进程使用——开/关中断是特权指令；若允许用户关中断后不再打开，整个系统即死。
  • 范围：只适用于单处理机。关中断只关本 CPU，另一 CPU 上的进程照样能进临界区。且临界区必须很短。

TestAndSet (TS/TSL) 与 Swap (XCHG)

  • 是：两条硬件原子指令。TS 一步完成”读出旧值 + 置为 true”；Swap 一步交换两变量的值。逻辑等价。
  • 不是：不保证”有限等待”——多进程抢锁时无排队机制，谁抢到看运气，理论上可能一直抢不到。
  • 易混：二者都违反让权等待（忙等）。它们的意义在于把”检查+上锁”在硬件层面合成一步。

互斥锁 (Mutex Lock)

  • 是：提供互斥的锁，acquire() 进入前上锁，release() 退出后解锁。二者必须是原子操作，故通常用硬件机制实现。
  • 不是：教材所描述的实现（while(!available);）即自旋锁，主要缺点是忙等待。教材前文”会被阻塞”一语中的”阻塞”是”被挡住”的宽泛用法，不是进程状态意义上的阻塞态。
  • 易混：自旋锁 ⊂ 互斥锁。“互斥锁”只规定目的（提供互斥），不规定等不到时如何等待；自旋与阻塞是两种实现选择。
  • 范围：优点是无上下文切换，因此适用于多处理器 + 短临界区。 单处理机上自旋是纯浪费——持锁者此刻根本没在运行。

自旋锁 (Spin Lock)

  • 是：等不到锁时原地循环检查、不让出 CPU 的互斥锁。
  • 不是：持有自旋锁期间不能进行调度。否则其他 CPU 上的等待者会空转整个时间片；同 CPU 上更可能直接死锁（新调度上来者若也要这把锁，将永远等不到已被换下的持有者）。
  • 易混：实际系统中 spin_lock() 内部会关闭内核抢占，必要时一并关中断。这与内核程序临界区禁止调度是同一件事。
  • 范围：只需一条硬件原子指令即可实现，内核态和用户态都能用，不是操作系统专属机制。

整型信号量 vs 记录型信号量

  • 是：整型信号量只是一个整数，P 用 while(S<=0); 忙等；记录型信号量增加等待队列，P 减完为负时调用 block() 自我阻塞。
  • 不是：只有记录型信号量满足让权等待。 教材后续所有题目默认使用记录型。
  • 易混：整型信号量的值不会为负（卡在 0）；记录型可以为负。

信号量 (Semaphore)

  • 是：value（剩余资源数）+ 等待队列。P：value--，若 <0 则阻塞；V：value++，若 ≤0 则唤醒一个。
  • 不是：P 不一定阻塞（减完 ≥0 则直接通过）；V 不一定唤醒（加完 >0 说明无人等待）；V 绝不会阻塞执行者。
  • 易混：value > 0 表示尚余该数量的资源；value = 0 表示刚好分完；value < 0 时 |value| 即等待队列中的进程数（高频计算题）。
  • 范围：互斥用法初值 1、P/V 在同一进程内夹住临界区；同步用法初值 0、P/V 分处两个进程、遵循**“前 V 后 P”**；前驱关系每条边一个信号量、初值全 0。

P/V 操作的顺序纪律

  • 是：同步信号量的 P 必须在互斥信号量的 P 之前。即先确认资源到位，再进临界区。
  • 不是：若先 P(mutex) 再 P(empty)，进程会抱着互斥锁进入阻塞，对方永远拿不到锁去腾资源，死锁。
  • 易混：两个 V 的顺序可以交换，不会死锁——V 永不阻塞执行者。只有 P 的顺序是致命的。

管程 (Monitor)

  • 是：由局部共享数据结构、操作这些数据的一组过程、初始化语句和管程名组成的语言构造。三大特征：① 局部数据只能被管程内过程访问 ② 进程只能通过调用管程内过程进入 ③ 每次仅允许一个进程在管程内执行。
  • 不是：管程是语法范围，不是执行实体，不会被创建和撤销——把它当成进程来理解就会读不懂相关命题。它是被动的，只有进程调用时其代码才执行。
  • 易混：第③条的互斥由编译器自动保证，程序员无须编写任何进入区/退出区代码。这是管程相对信号量的全部优势。
  • 范围：管程需要编程语言与编译器的支持；信号量由操作系统提供，任何语言均可使用。

条件变量 (Condition Variable)

  • 是：管程内用于同步的变量，x.wait() 使调用者阻塞并释放管程使用权，x.signal() 唤醒一个在 x 上等待的进程。
  • 不是：x.wait() 若不释放管程使用权，就会把整个管程锁死——别人进不来，也就永远无法满足它等待的条件。
  • 易混：一个管程内可以有多个条件变量，分别对应不同的等待原因。

signal 与 V 的区别

  • 是：V 总是执行 value++，即使无人等待也被记录下来，将来的 P 可直接通过——有记忆。
  • 不是：x.signal() 若此刻无人在 x 上等待，什么也不做，信号直接丢失——无记忆。
  • 易混：形象说法是”V 是存钱，signal 是当面喊一嗓子”。因此管程的 wait 必须由条件驱动，不能依赖信号计数。

Hoare 语义 vs Mesa 语义

  • 是：signal 之后由谁运行的两种约定。Hoare：唤醒者立即阻塞，被唤醒者马上运行；Mesa：唤醒者继续运行，被唤醒者仅转为就绪。
  • 不是：Mesa 语义下被唤醒者真正运行时条件可能已不成立（中途可能被第三者抢走资源）。
  • 范围：Mesa 语义下 wait 必须写在 while 循环里，不能用 if；Hoare 语义才可用 if。Java 采用 Mesa 语义，这正是”wait() 必须放在 while 中”这条铁律的根源。

生产者-消费者问题

  • 是：mutex=1（互斥访问缓冲区）、empty=n（空位数）、full=0（产品数）。任何时刻 empty + full ≤ n。
  • 不是：两个 P 不可换序（先同步后互斥）；生产与消费动作必须放在临界区之外，否则无谓延长互斥时间。
  • 易混：两个 V 的顺序可以交换。

首尾负责制

  • 是：读者-写者问题的核心技巧——只有第一个到达者执行 P，只有最后一个离开者执行 V，中间的同类直接进出。
  • 不是：读者-写者中的 mutex 保护的是计数变量 count，不是文件；保护文件的是 rw。
  • 范围：该技巧有两种镜像用法——读者用它对内共享（让同类并发），写者用它对外封锁（把异类挡在门外）。

读者优先 / 读写公平 / 写者优先

  • 是：三个版本的区别在于谁能插队。读者优先：读者绕过 rw 直接 count++，写者饿死；读写公平：新增闸门 w，谁也不能插队；写者优先：写者群体用 rd 封锁读者入口，读者饿死。
  • 不是：读写公平不等于写者优先——它只保证不饿死、先到先服务，并未给写者更高优先级。
  • 易混：公平版的关键在 V(w) 的放置位置：写者写完才 V(w)（故等待期间一直堵着读者），读者登记完即 V(w)（故读者之间仍可并发）。

哲学家进餐问题

  • 是：5 人 5 筷，需同时持有左右两根才能进餐。若 5 人同时拿起左筷则形成循环等待，全体死锁。
  • 不是：三种解法分别是——① 至多允许 4 人同时取筷（5 根分给 4 人必有一人能拿满两根）② 奇偶分流（奇数先左、偶数先右，相邻两人争同一根，必有一人失败让出）③ 用 mutex 把”取两根”变成原子操作（不出现人人各持一根的中间状态）。
  • 易混：这是 死锁的经典模型，三种解法各自破坏了不同的死锁必要条件。

2.4 死锁

死锁 (Deadlock)

  • 是：多个进程各自占有一部分资源，同时又在等待其他进程占有的资源，导致全部无法向前推进的僵局。
  • 不是：不是饥饿——死锁进程等的是永远不会被释放的资源，绝无可能自行解除；饥饿进程等的资源会被释放，只是每次轮不到它。也不是死循环——死循环是单个进程的逻辑 bug，进程仍在运行态占用 CPU，不属于操作系统问题。
  • 易混：死锁至少涉及 2 个进程且都处于阻塞态；死循环 1 个进程即可且处于运行态。
  • 范围：只有对不可剥夺资源的竞争才可能死锁。 对 CPU、主存等可剥夺资源的竞争不会引起死锁，因为它们随时能被收回再分配。

死锁产生的四个必要条件

  • 是：① 互斥（资源一次只能给一个进程）② 不可剥夺（别人抢不走）③ 请求并保持（自己不放手）④ 循环等待（存在环形等待链）。
  • 不是：它们是必要条件——死锁发生则四条必然全部成立。因此破坏任意一条即可保证不死锁，这正是死锁预防的全部思路。
  • 易混：④单独看不是充分条件（见下条）。

不可剥夺条件 vs 请求并保持条件

  • 是：不可剥夺是”别人抢不走”（外部视角，描述平时）；请求并保持是”自己不放手”（自身视角，描述因新请求而阻塞时）。
  • 不是：二者虽都表现为”资源留在持有者手中”，但描述的是不同时刻——前者说的是正常使用期间，后者说的是已经卡住却仍占着不放。
  • 易混：破坏方法因此完全不同——破坏不可剥夺是申请失败即释放已有全部资源；破坏请求并保持是一次性申请全部资源（静态分配）。

循环等待条件

  • 是：存在进程-资源的环形链，链中每个进程都在等待下一个进程占有的资源。
  • 不是：有环不等于死锁。 每类资源有多个实例时，图上画得出环，系统却可能因为尚有空闲实例而未死锁。
  • 范围：每类资源只有 1 个实例时，有环 ⟺ 死锁；有多个实例时，有环只是必要不充分条件。 这正是死锁检测必须用”化简”而非”找环”的原因。

可剥夺资源 vs 不可剥夺资源

  • 是：可剥夺资源能被操作系统随时收回再分配（CPU、主存）；不可剥夺资源必须由持有者用完后主动释放（打印机、磁带机）。
  • 不是：对可剥夺资源的竞争不会产生死锁——环随时能被打破。
  • 易混：CPU 靠时间片轮转收回，主存靠对换换出，二者都不具备构成死锁的资格。

鸵鸟策略

  • 是：假装死锁不存在，发生了也不处理。
  • 不是：不是疏忽，而是经过权衡的工程选择——通用系统中死锁概率极低，预防与避免的常态代价高于偶尔重启的代价。
  • 易混：Linux、Windows 等通用操作系统实际采用的正是这一策略。

死锁预防

  • 是：事前策略，在系统设计阶段破坏四个必要条件之一，使死锁从原理上不可能发生。
  • 不是：不做运行时判断，是静态的”立法”。
  • 易混：↔ 死锁避免（动态的”每次执法时现算”）。
  • 范围：破坏”互斥条件”通常不可行——多数资源的互斥性由物理属性决定。SPOOLing 是少数可行的例子。

静态分配（预先分配）

  • 是：破坏”请求并保持”的方法——进程运行前一次性申请全部所需资源，配不齐就不投入运行，运行期间不再提新请求。
  • 不是：优点是简单安全，但资源浪费严重（最后才用的资源从一开始就被独占），且可能导致饥饿（需求种类多的进程难等到所有资源同时空闲）。

顺序资源分配法

  • 是：破坏”循环等待”的方法——给资源编号，规定必须按编号递增顺序申请，同类资源一次申请完。
  • 不是：不能保证进程不用等待，只保证等待关系不成环。若多个进程都在等同一个最大编号资源，那是普通等待或饥饿，不是死锁。
  • 易混：无环的证明——若存在环则得 ，矛盾。
  • 范围：缺点是编号难以变更（不便增加新设备）、实际使用顺序与编号不符会造成浪费、给编程带来麻烦。

死锁避免

  • 是：事中策略，每次分配前动态判断该分配是否会使系统进入不安全状态，安全才分配。代表算法是银行家算法。
  • 不是：不预设规则，是动态判断，比预防灵活、资源利用率更高。
  • 范围：进程可能长时间阻塞——它等的不是资源本身（资源可能正空闲着），而是算法的放行。因为算法按最大需求评估风险，会系统性高估危险。

安全状态 / 不安全状态 / 安全序列

  • 是：若能找出至少一个执行顺序（安全序列），使各进程能一个接一个地拿够资源、跑完、归还，则系统处于安全状态；找不出任何一个即为不安全状态。
  • 不是：安全序列不要求所有进程同时能被满足，只要求能接力推进。
  • 易混：安全 ⟹ 一定不死锁；不安全 ⇏ 一定死锁（进程未必真的把最大需求全提出来）。死锁状态 ⊂ 不安全状态。

银行家算法

  • 是：进程提出请求时，系统先做试探性分配，再执行安全性算法检查是否存在安全序列；存在则正式分配，不存在则回滚试探分配并让进程等待。
  • 不是：答题时”试探性分配""安全序列""安全/不安全状态”三个词不可省略，否则表述不完整。
  • 易混：四张表满足 Need = Max − Allocation；安全性算法中归还的是 Allocation（实际占有量）而非 Need，这是手算最常见的错处。
  • 范围：几乎无通用操作系统采用——须预知最大需求（现实中做不到）、进程与资源数动态变化、开销约 、且过于保守。数据库改用检测+回滚。

同类资源不死锁的条件

  • 是： 个进程共享 个同类资源、每个进程最多需 个时，不死锁的条件是各进程最大需求量之和 。
  • 不是：不必死记公式。回到最坏情况即可推出——人人都拿到 个、都只差 1 个、且一个空闲都不剩时死锁，故只需保证 ，整理即得。
  • 易混：验证法—— 时 不成立，确实死锁； 时 成立，剩 1 个即可启动接力。

死锁检测

  • 是：事后策略，允许死锁发生，通过资源分配图化简周期性判定，发现后再解除。
  • 不是：限制最宽松、资源利用率最高，但需承担检测开销与解除代价。
  • 易混：检测时机可以是”每次请求得不到满足时""定时""资源利用率骤降时”。

资源分配图

  • 是：圆圈为进程结点，方框为资源结点（框内圆点数 = 该类资源的实例数）。请求边 P → R（进程正在申请），分配边 R → P（已分配给该进程）。
  • 不是：两种边方向相反，不可混淆。
  • 易混：记忆抓手——箭头从谁指出，谁就是主动方：进程主动申请，资源被动地被分配出去。

资源分配图化简

  • 是：反复找出”请求都能被当前空闲实例满足”的进程，假设其运行完毕并消去它的全部边，直到无法继续。全部结点变孤立则可完全简化。
  • 不是：判断能否消去时，比较的是请求量与当前空闲实例数（总数减已分配），不是与总数比较。
  • 易混：“环是嫌疑，化简才是定罪。” 不能只靠找环判定死锁。

死锁定理

  • 是：S 为死锁状态的充分必要条件是——S 状态的资源分配图不可完全简化。
  • 不是：它是一条判定准则，因此属于检测死锁的方法，不是预防、避免或解除。
  • 易混：这个名字之所以陌生，是因为教材通常把重点放在”资源分配图化简”这个操作上；死锁定理只是给该操作的结论起的名字。会化简即掌握了死锁定理。

死锁解除的三种方法

  • 是：资源剥夺法（挂起某些死锁进程并抢占其资源）、撤销进程法（强制撤销部分或全部死锁进程）、进程回退法（回退到检查点重新执行）。
  • 不是：撤销进程法代价最大但实现最简单；进程回退法代价最小但实现最复杂——代价与复杂度恰好相反。
  • 易混：资源剥夺法须防止被挂起进程长期饥饿。选择牺牲品应综合考虑优先级、已运行时间、剩余时间、已占资源、进程类型。

附：本章高频”范围限定”清单

考试最爱在这些结论上抽掉限定条件：

结论成立范围
运行态进程至多 1 个仅单处理机
就绪队列最多 n−1 个仅单处理机，n 为进程总数
不能并行仅单核 / 多对一模型 / 用户级线程
线程是调度的基本单位仅内核级线程
进程是调度的基本单位仅未引入线程时
同步互斥由 OS 自动完成仅管道，共享存储须进程自理
一个线程阻塞则全进程阻塞仅用户级线程 / 多对一模型
进程有层次结构仅 UNIX/Linux，Windows 无
匿名管道可用仅有亲缘关系的进程
作业的概念主要用于批处理系统
高级调度存在主要用于批处理系统
中级调度存在仅采用对换/虚拟存储的系统
SJF 平均周转时间最短仅”同时到达 + 非抢占”
等待时间含外存排队仅对作业，对进程不含
必须抢占式调度仅分时、实时系统
禁止调度仅内核程序临界区，普通临界区可调度
上下文切换仅内核态可执行
流水公式 单件仅各作业各级耗时相同、每级一台设备
违反准则只是性能问题仅”让权等待”；违反”忙则等待”是致命的
中断屏蔽法可用仅单处理机、仅内核态
Peterson 算法正确仅顺序一致性内存模型，现代 CPU 需内存屏障
自旋锁划算仅多处理器 + 短临界区
持锁期间禁止调度仅自旋锁（阻塞型互斥锁本就会让出 CPU）
可省掉 mutex仅缓冲区容量为 1 时
wait 可用 if仅 Hoare 语义；Mesa 语义必须用 while
竞争会导致死锁仅不可剥夺资源；CPU、主存不会
有环 ⟺ 死锁仅每类资源 1 个实例时；多实例时有环未必死锁
顺序分配法保证的仅”无循环等待”，不保证不用等待
安全 ⟹ 不死锁成立；但不安全 ⇏ 死锁
银行家算法看 Need化简看当前请求边，两者依据不同

链接

反向链接