"E:\作业\大二\大二下\认知科学类脑计算\PPT\课程PPT\第9讲 复习、总结与答疑.pdf"这是老师划定的期末考试范围，不可能超出这个PDF。现在要求你参考我平时做的各个章节的笔记，依据这份期末考试PDF帮我整理一份笔记。我的各章节笔记：（第一二章）https://blog.csdn.net/2301_80226956/article/details/160799183?spm=1001.2014.3001.5501（第三章）https://blog.csdn.net/2301_80226956/article/details/160205351?spm=1001.2014.3001.5501（第四章）https://blog.csdn.net/2301_80226956/article/details/159630140?spm=1001.2014.3001.5501（第五章）https://blog.csdn.net/2301_80226956/article/details/160230032?spm=1001.2014.3001.5501（第六章）https://blog.csdn.net/2301_80226956/article/details/160251397?spm=1001.2014.3001.5501（第七章）https://blog.csdn.net/2301_80226956/article/details/162163937?spm=1001.2014.3001.5501（第八章）https://blog.csdn.net/2301_80226956/article/details/162167978?spm=1001.2014.3001.5501（第九章）https://blog.csdn.net/2301_80226956/article/details/162176444?spm=1001.2014.3001.5501

题目类型和数量可以参考"E:\作业\大二\大二下\认知科学类脑计算\PPT\课程PPT\2026春季期末试卷-操作系统 模拟题.pdf""E:\作业\大二\大二下\认知科学类脑计算\PPT\课程PPT\操作系统 期中模拟题.docx"。当然题目内容是要在期末考试PDF中的。你可以出两份卷子，然后提供两份答案。
此外，你需要再专门出一套单选专项练习(70)、填空专项练习(70)、概念题专项练习(40)以及计算题专项练习(10)、改错题专项练习(10)，注意，计算题要包括银行家算法、分段分页、各种调度算法、内存分配、页面置换等重要考点，你需要在题目上写明这道题的考点和来源章节。
你可以把这个E:\作业\大二\大二下\认知科学类脑计算\PPT\课程PPT 的最下一级（课程PPT）文件夹的名字改为“操作系统”，并在内部建立复习笔记、模拟卷与答案、专项练习及答案等文件夹。有不清楚的需求请你先问清楚我。你之前做过类似的工作，可以参考整理工作流，帮你快速获取CSDN的内容。

第一章 第二章

操作系统中的抽象概念

时间    

多个任务不能同时使用同一个时分复用的部件，但每个任务在使用时都可以得到这个部件的全部，因此需要将时间合理地分配给它们。典型的时分复用的部件是处理器，它又包括中央处理器和协处理器。

空间    

多个任务可以同时使用同一个空分复用的部件，但每个任务在使用时都无法得到这个部件的全部，因此需要将空间合理地分配给各个任务。典型的空分复用的部件是存储器，它又包括内存和外存。

原则    由需求决定。

设计    操作系统的高层次抽象描述，描述各个组件的逻辑功能。

实现    操作系统的低层次具体描述，描述各个组件的具体实施。

策略    操作系统中对资源管理的方法和政策。

机制    操作系统为实现策略使用的工具和手段。

图灵机模型

存储带TAPE   

读写头HEAD   

状态寄存器   

控制规则表    

通用图灵机

将任意图灵机及其输出作为输入的图灵机，它可以模拟任何图灵机的运行。

重要性

存储程序架构（冯・诺依曼模型）思想的原点。         
存储的程序即为其它图灵机的状态描述与转换规则。         
存储的数据即为其它图灵机所使用的数据。

处理器特权级

用户模式    执行应用程序的模式，不允许直接访问系统的敏感资源。
内核模式    执行操作系统的模式，可直接执行敏感指令和访问敏感资源。
特权指令    能对敏感资源进行操作的指令，仅能在内核模式下执行

问题一        特权级可以通过什么机制互相切换？         

方法一    中断机制         
方法二    专用指令机制  

系统调用、中断和陷阱

系统调用    

一种机制设计，允许应用程序通过受限的方法调用操作系统内核，向内核请求功能处理。

中断：不可预测 陷阱：可预测

操作系统结构演进：从简单到灵活的隔离逻辑

模式 保护域 OS角色（管理 协调） 资源调用

本质上是隔离机制从“无”到“有”、从“粗”到“细”、从“集中”到“分布”的过程

一、库结构（单核结构）：无隔离的“合作模式”

特点是“无内核/用户模式区分”，所有程序都在同一个“保护域”里运行。

• 特点        
  无区分“无内核模式与用户模式区分        
  同域：所有应用程序以及内核都在同一个保护域。         
  资源可用：应用程序可以随时对任何资源做任何操作。         
  程序合作：应用程序间为合作关系，操作系统的角色偏重协调而非管理
• 代价：一错全崩

二、宏内核结构（通用设备）：首次引入“保护域”

到了桌面电脑、必须防止程序间互相干扰。于是出现了宏内核结构，区分用户和内核

• 特点 
  有区分。         
  每个应用程序在不同域。         
  内核的所有功能位于同一个保护域。         
  应用程序必须请求内核完成敏感资源操作。         
  应用程序间为合作或竞争关系，操作系统的协调和管理并重
• 优点：程序间互相隔离，一个程序崩溃不会直接影响其他程序（比如浏览器崩溃不会让Word也崩溃）。
• 缺点：但内核有bug会挂掉。

三、微内核结构 把宏内核中的部分程序拆为守护进程

宏内核内核东西太多，崩了完蛋，拆点功能出来，变成用户态的“守护进程”。

• 隔离升级：内核只保留最基础的功能，其他功能拆为“服务进程”
  有区分，每个应用程序在不同的保护域。         
  内核除基本功能外，其它功能拆解为守护进程。         
  应用程序必须请求守护进程中的策略分配敏感资源。         
  
• 代价：程序间通信会增加开销，但换来的是极高的可靠性和灵活性。

四、外核结构：暴露硬件资源给应用程序

有些场景（如高性能计算、实时系统）对性能要求极高，连微内核的“服务进程通信”开销都嫌大。外核结构的思路更激进：内核只负责“分配硬件资源”，具体怎么用，交给应用程序自己决定。

• 去抽象化：传统内核会把硬件“抽象”成统一的接口，外核直接把硬件“暴露”给应用程序。比如，应用程序可以直接操作硬盘的扇区，不需要经过文件系统的抽象层。
  有区分，每个应用程序在不同的保护域。         
  内核仅负责硬件资源分配与管理功能。         
  应用程序必须自行分配到的硬件资源完成功能。
  去抽象化    将硬件资源直接暴露给应用程序以获得最大性能增益。

五、其他结构：虚拟机与多内核的“扩展”

• 虚拟机结构：本质是“用软件模拟硬件”，每台虚拟机跑自己的操作系统。隔离性最强（不同虚拟机完全独立），但开销也大（需要模拟硬件）。
• 多内核结构：每个核心跑一个内核实例，内核间通过通信协作。

第三章

可执行文件

第一步：程序是如何“诞生”的？

把高级语言变成机器语言：源代码 -> 编译器 -> 汇编器 -> 链接器 -> 可执行文件

编译器：翻译官
做什么：高级语言源程序（比如 main.c）翻译成汇编语言。

汇编器：组装工
做什么：接收编译器输出的汇编代码，把汇编指令“组装”成 CPU 能直接执行的机器码，生成一个目标文件（比如 main.o）

链接器：总装师
把所有“零件包”（目标文件）和“标准件库”（系统库）组装成一个完整的、可以出厂的“成品机器”（可执行文件）

解释器：它和编译型语言（C/C++）不同。像 Python、JavaScript 这类语言，它们的“搬家”过程是动态的。解释器会一边读取源代码，一边翻译一边执行，不会事先生成一个完整的 .exe 文件。

编译回填

用于解决“当前不知道目标地址，以后怎么跳转/访问”的核心技术。

1. 直接回填法 (Backpatching)（会修改.text段）

先留个空位，等知道地址后再回来补上

2. 间接地址法 (Indirect Addressing)（会修改.rwdata段）

它不直接告诉你数据在哪，而是告诉你“谁知道数据在哪”。

生成目标文件时，在.rwdata段留出一个表格，.text段中的代码对其它符号的引用均通过这个表格进行

库

大量基础功能是必备的。于是将含有这些基础功能的文件预先编译好，目标文件，使用时在生成程序的时候链接即可

静态库

目标文件的简单合集

动态库

在可执行程序被加载时，作为独立文件单独加载的库文件。它不包含在可执行文件之内；需要再加载。

外存的库共享

可执行文件中不再包含库文件。这样,库文件就只要在外存中存在—份

内存的库共享

物理地址空间中仅包含库文件的—个副本。这样,即便库文件被多个虚拟地址空间中被使用,它也只会占用—份物理内存,减少了内存用量

从运行时库到运行时环境

程序启动时加载的是一个庞大的“运行时环境”。这个环境不仅包含基础库，还自动包含了垃圾回收、虚拟机、即时编译等功能。

过程调用

开销就是序言和尾声之和。

第四章

指令流的执行：

顺序执行

优势：简单

劣势：不能被打断

合作执行

拆成几段，每一段顺序执行，主动放弃CPU占用权

特点：

自愿放弃：只有指令流主动放弃CPU或执行完毕才是交还CPU试使用权的方式
顺序确定：可以指定也可以随机

有问题：缺乏强制性，恶意程序可以长期占用

并发执行/抢占执行

允许指令流任何时刻被打断，插入新的指令流。

特点：

虽然每个任务（指令流）都觉得自己独占了一个CPU在跑，但实际上系统会在它们之间快速切换，而且你无法预知下一个轮到谁。

问题：切换时如何保留信息（上下文、状态）

☆ 从“单核”到“多核”——并发与并行的质变

• 并发：

  • 定义：逻辑上的同时发生。
  • 场景：单核CPU。
  • 原理：通过快速切换（时间片轮转），让多个任务交替执行。
  • 比喻：一个厨师（CPU）同时炒四个菜，他一会儿炒这个，一会儿炒那个，看起来像是一起熟的，其实是轮流照顾。

• 并行：

  • 定义：物理上的同时发生。
  • 场景：多核CPU。
  • 原理：多个指令流在不同的CPU核心上真正同时执行。
  • 比喻：四个厨师（4核CPU），一人拿一个锅，四个菜真正的一起炒。

逻辑关系：并发是抽象概念（逻辑），并行是具体实现（物理）。并行是并发的一种特殊形态。

指令流状态

处理器时间分配

指令流与时间：操作系统需要给指令流分配CPU使用的时间，让指令流拿着这个配额运行，但操作系统不知道程序有几条指令流，因此需要一个代理人线程，作为CPU时间的分配对象，指令流与线程对应后运行。

指令流——独立执行的指令序列，必须由线程代理
线程——CPU时间分配的对象
进程——内存空间分配的对象

线程的描述

线程的身份证——线程控制块（TCB）

TCB放在内核

时间预算
优先级
线程上下文：恢复状态的寄存器组

内核阻塞：如果一个线程因为要读写硬盘（I/O）被卡住了（内核阻塞），操作系统会直接把整个线程挂起。如果这个线程里还跑着别的指令流，那些指令流也会跟着一起“冻结”。

操作系统通过TCB来管理线程（载体），利用时间预算和优先级来决定谁先谁后，利用上下文切换来实现并发。而指令流，就是依附在线程这个载体上，实际执行逻辑的“灵魂”。

“指令流”与操作系统眼中的“线程”之间，到底该怎么连线？

关系    一对一（简单）     一对多（性能好且实用）     多对多（复杂，难以正确实现）

纤程与协程

• 协程：其实就是多对一模型下的用户态指令流。它强调“合作”，必须主动让出CPU，切换极快。
• 纤程：也是用户态指令流，但更强调“轻量”，通常由用户空间的调度器管理。

公平

正义

公平体现在该式包含了对所有任务的考虑。

正义体现在该式对越短任务的越长等待越不容忍。

调度算法

先来先服务：FCFS 公平

特点：先到先得，但要求任务短小且简单。适用于批处理系统

• 优点：简单，绝对公平。
• 缺点：对短任务极不友好。如果一个长任务排前面，后面一堆短任务都得等死。

Q:为什么说FCFS并非任何意义上的公平？
忽略了任务的大小。如果一个只需1秒的任务，因为排在需要1小时的任务后面，它就得等1小时。这对那个1秒的任务来说是极大的不公平（周转时间太长）

短作业优先：SJF 效率

特点：响应性好，适合简单的交互式系统。短任务先完成，让平均周转时间减小。

• 优点：平均等待时间最短。系统整体效率最高。
• 缺点：长任务会饿死。如果源源不断有短任务来，长任务永远轮不到。

最高响应比优先算法 HRNN

• 逻辑：响应比 = (等待时间 + 运行时间) / 运行时间。
• 解释：这个公式很妙。
  • 等待时间越长，分子越大，优先级越高（照顾老任务，防饿死）。
  • 运行时间越短，分母越小，优先级越高（照顾短任务，提效率）。
• 评价：这是FCFS和SJF的完美折中。

在线算法：线程是动态输入的，无法预测会输入什么输入，前面两种算法都是一次性输入完的

饥饿问题： 某些请求无限增加时,  另—些请求永远得不到分配

时间片轮转法 RR

• 逻辑：把CPU时间切片
• 优点：交互性极好。每个人都能在短时间内得到响应，不会觉得卡死。
• 改进版（FPRR）：结合固定优先级。重要任务优先级高，先轮转；普通任务优先级低，后轮转。

特点：让所有的线程都获得了执行机会

但是如何划分时间片呢？

太长就变成FCFS流水线了，太短切换开销太大

加权时间片轮转

高优先级的分配更多的时间片，低优先级分配更少的时间片

固定优先级时间片轮转 FPRR

复杂系统的调度

单一的调度算法各有优缺点，如何综合起来

因人而异：不同功能的线程用不同的调度算法，类型不同的线程之间也需要调度算法：

分层置疑：只有上层高优先级的线程为空时，才会向下执行其他线程

动态调整：同一个线程可能承载不同的指令流，但是在不同的阶段可能发生改变，比如计算完成后的后台计算线程计算完后想弹出交互窗口，就必须升到前台。

多级反馈队列：实时检测每个线程的行为，不合适时为其更换到合适的队列（允许队列迁移）

广义调度算法

时间维度

1. 长期调度（进程准入）：

   • 做什么：用户决定哪些程序有资格“出生”。可执行文件（.exe）加载到虚拟内存中，变成进程。

2. 中期调度（内存交换）：

   • 做什么：当内存不够用时，把暂时不运行的进程“换出”到硬盘
   • 核心：这是存储器管理的范畴，解决的是内存紧张的问题。

3. 短期调度（CPU抢占）：

   • 做什么：决定就绪队列里的哪个线程能拿到CPU的时间片。

第五章

线程的划分：按特权

内核线程（Kernel Thread）/用户线程（User Thread）是指线程运行时的CPU模式。而内核级线程（Kernel-Level Thread）/用户级线程（User-Level Thread）则是指操作系统是否知道它们的存在。
内核线程和用户线程都是内核级线程（CPU知道他们存在，且一个是在用户态下一个是在内核态下运行），而所谓的“用户级线程”则是指协程和纤程。

线程的基本操作

创建 出让(自愿放弃) 终止 同步(一个线程等待另一个线程终止) 销毁

如何分配内存

流程：分配-使用-释放

固定分区法——拿最大需求分配

内部碎片：要1MB，给100MB，剩下的99MB就白白浪费了，这就是内部碎片

多固定块法——桶分配

做不同大小的块池子。比如一个池子装1MB的块，一个池子装100MB的块。

不知道程序到底需要多少个1MB，多少个100MB。

外部碎片：如果100MB的池子空了，哪怕1MB的池子堆成山，你也无法满足100MB的请求。这叫外部碎片——内存总量够，但因为不连续、不匹配，就是没法用。

动态分区法

按需求的最大公约数切割内存，这样不会有内部碎片，但是会产生外部碎片

首次、最好、最坏适配

首次适配法（First-Fit）

逻辑：从头开始找，找到第一个能装下的空闲区就分配。

优点：简单、快。

缺点：容易在内存开头留下很多小碎片，而且不保留大块内存给未来的大请求。

最好适配法（Best-Fit）

逻辑：遍历所有空闲区，找那个“最紧凑”、最刚好能装下的。

优点：看起来最节省，试图保留大块内存。

缺点：会产生大量无法利用的极小碎片（“劫小济大”），而且遍历所有空闲区非常慢（O(n)）。

最坏适配法（Worst-Fit）

逻辑：反其道而行之，找最大的空闲区来分配。

优点：试图避免产生极小碎片，保留中等大小的块。

缺点：很快就把大块内存消耗光了，未来遇到大请求时就傻眼了（“劫大济小”）。

简单分配策略的共性问题

• 遍历开销大：每次分配都要遍历空闲列表，程序跑久了，列表越来越长，速度越来越慢。
• 策略单一：把所有请求混在一起分配，大小请求互相干扰。
• 粒度问题：太粗有内部碎片，太细有管理开销。

☆ 考点 内外部碎片

内部碎片（分多了用不完） 外部碎片（太碎了拼不起来）

程序内内部碎片

定义：已经分配给程序的内存块，但程序实际上用不到，被“浪费”在块内部的空间。

程序内外部碎片

定义：系统中空闲的内存满足需求，但由于内存不连续，无法满足大块连续内存的请求。

程序间的内部碎片

• 定义：指操作系统已经分配给某个程序，但该程序逻辑上无法利用的内存。

程序间的外部碎片

• 定义：操作系统手里还有空闲内存，但因为这些内存不连续，无法满足某个程序的大块连续内存请求。

简单分区

将物理内存切割成几个块，一个块运行一个应用程序、某个段。在链接时就决定好要放置在什么地方。

虚拟地址空间

硬件地址翻译：采用添加额外硬件的方法，使得不同应用程序中对一个地址发起的访问实际对应内存总线上的不同地址。

进程

权能：由管理者下发的许可证

保护域 ：许可证限制的空间，赋予进程合法操作资源，限制非法操作资源，实现隔离。

类比线程，是空间的分配对象。

进程是—种特殊的保护域,其特殊在它是常见保护域中最小的—种。

进程控制块（PCB）

☆ 考点 静态与动态——可执行文件与进程

一句话记住：exe 是硬盘上的 “程序文件”，进程是内存里 “正在跑的程序实例”。

核心区别

1. 存在位置不同

   • exe：硬盘 / 磁盘上的静态文件（.exe）
   • 进程：内存中运行的动态实体

2. 状态不同

   • exe：静止的代码和数据
   • 进程：活动的，占用 CPU、内存、句柄等资源

3. 数量关系

   • 一个 exe 可以启动多个进程（比如开多个微信、多个浏览器）
   • 一个进程 只对应一个正在运行的程序

4. 生命周期

   • ​​​​​exe：长期存在，删了才没

   • 进程：启动才有，关闭就消失

进程与线程与指令流

线程通过在进程里运行, 将CPU时间转化为对地址空间的—个访问操作次序 ,从而实现应用程序的功能。

进程是一个资源空间，不具备执行能力，运行的是进程中线程中的指令流。

进程可以不包含任何线程，而是等线程迁移进来

线程在进程中运行，且可以在多个进程中穿行，共享—份时间预算

关系

• 一对一关系（最常见）：

  • 模式：一个进程对应一个线程。
  • 本质：一个内存空间对应一个CPU执行流。

• 一对多关系（现代主流）：

  • 模式：一个进程对应多个线程（多线程进程）
  • 本质：多个CPU时间分配对象共享一个内存空间分配对象。

如何实现一个进程——内存隔离

【对应第三章 内存管理的进化史——减少内存浪费】

隔离的作用：操作系统给每个程序提供一个独立的虚拟地址空间，也就是进程，防止交叉访问。

权能：由管理者下发的许可证

保护域 ：许可证限制的权限空间，赋予进程合法操作资源，限制非法操作资源，实现隔离。

进程是—种特殊的保护域,其特殊在它是常见保护域中最小的—种。

如何实现内存隔离

分段

把程序的逻辑地址转换成物理地址，由段式内存管理单元（S-MMU）维护一个段表。

核心逻辑：基址 + 偏移

• 段号：告诉MMU这是哪个段（代码段？数据段？）。
• 段基址：段在物理内存里的起始位置。
• 虚拟地址（偏移量）：在这个段里跑了多远。
• 公式：物理地址 = 段基址 + 偏移量。

流程：

每次访问内存，它都要做三次检查：

1. 段存在吗？（查段号有没有）
2. 越界了吗？（偏移量有没有超过段长度？）
3. 权限对吗？

段表放哪里？

放CPU寄存器：

提供一组寄存器存放段表，进程切换时需要取出新进程的段表，拷贝到寄存器中。

优点：无需访问外部

缺点：无法支持比寄存器组数量更多的段

放内存：

CPU里只放一个指针指向它

优点：这样能支持无限的段

缺点：要访问两次内存，首先访问段表，再访问内存本身。

用快表缓存：

工作集：程序在一段时间内，频繁访问的内存。某个时刻t之前一段时间间隔T内访问内存的地址的集合WS(t, T)。某个时刻t之前最近Δ次访问内存的地址的集合WS(t, Δ)

局部模式    进程中的某个线程上的指令流的执行过程中，其访问的内存空间从一个局部迁移到另一个局部。

☆ 考点 局部性：

• 时间局部性：如果你访问了一个数据，大概率过一会儿还会访问它。
• 空间局部性：如果你访问了一个数据，大概率接下来会访问它旁边的数据。

工作流程：

1. CPU给出一个虚拟地址。
2. 查快表：快表里有没有这个段号？
   • 命中：直接拿到物理基址
   • 没命中：去内存里查段表，查到了之后，顺便把这个条目“复制”一份到快表里，以备下次使用。

段表页表段页式

1. 段表 (Segment Table) —— “按逻辑划分的隔断”

• 思想： 以“段”为单位，非常符合人类程序员写代码的逻辑。

• 怎么分： 程序被按照功能逻辑切成不同的段。

• 运作原理： 段表记录的是：段号 -> 段的物理起始地址 + 段的长度。

• 优点： 方便内存共享（两个程序可以共享同一个代码段），并且保护机制很好（代码段设为“只读”，防止程序意外修改）。

• 缺点： 会产生“外部碎片”。就像租房子，如果一个大段的程序退租了，中间空出来一大块不规则的地方，很难塞进下一个刚好适配的段，导致内存利用率下降。

2. 页表 (Page Table) —— “按物理尺寸切砖块”

基数树/桶排序

原理：

1. 把虚拟地址切分成几段（比如一级页号、二级页号、页内偏移）。
2. 一级页表（母桶）：只负责索引“区域”。如果某个区域完全没用，一级页表里对应的项就是空的，根本不需要创建二级页表。
3. 二级页表（子桶）：只有在真正用到某个区域时，才分配二级页表。

• 思想： 以“页”为单位，完全是为了物理硬件和效率优化的。

• 怎么分： 无论你的程序是代码、数据还是堆栈，统统被切成固定大小的小块（通常为 4KB 左右）。物理内存也被切成同样大小的小块（叫做“页框”）。

• 运作原理： 页表记录的是：虚拟页号 -> 物理页框号。

• 优点： 彻底解决了“外部碎片”问题。因为所有块大小一样，只要物理内存有空闲的小格子，就能把程序的页塞进去。内存利用率极高。

• 缺点： 由于切得碎，页表可能变得非常大（比如一个 4GB 的程序，页表会很大）；而且程序逻辑上想共享一段代码会比较麻烦。

---

3. 现代操作系统的终极答案：段页式 (Segmentation + Paging)

既然段表符合逻辑但浪费空间，页表节省空间但逻辑性差，那么现在的操作系统（如 Linux、Windows）是怎么做的呢？

答案是：两者结合起来用！

• 第一步（段表）： CPU 先查段表。根据逻辑结构把程序划分成各个段，获取逻辑地址。这时候，逻辑地址转换成了“线性地址”。

• 第二步（页表）： CPU 再查页表。把刚刚的“线性地址”再切成固定大小的页，映射到物理内存上。这时候，“线性地址”最终转换成了“物理地址”。

• 实际效果： 程序员依然可以享受段式带来的逻辑清晰和内存保护（段表负责权限控制）；底层物理内存又能享受页式带来的无碎片、高利用率（页表负责物理映射）。

单层存储模型

计算机上所有的存储器都被抽象成一种逻辑模型。操作系统决定哪些内容存放在哪些层次的存储器中。
数据存储的逻辑模型向最上层的存储器靠近；数据存储的物理特性向最下层的存储器靠近
存哪由OS决定

请求分页（Demand Paging）

1. 不贪心： 程序跑的时候，仅将其当前工作集调入内存。

2. 不着急： 用不到的代码，继续留在硬盘里。页表里标记为“空”。

3. 随叫随到： 一旦 CPU 碰到“空”的页，就触发“缺页中断”，操作系统立刻从硬盘把这页捞出来丢进内存。

缺页异常的处理：

0.懒加载：操作系统在启动程序时，根本不把代码全读进内存。页表里先留空，标记为“不在内存”。

1.触发缺页异常，暂停执行

2.处理缺页异常，从用户态进入内核态

3.写回换出页，如果满了要腾出空间，如果没被修改过就扔掉，否则要存入

4.读入换入页：从外存读入刚刚请求的页

5.修改页表，将存在页设为1

6.重新执行，PC不变

☆ 考点 页面置换算法

理想算法：最长前向距离（LFD/OPT） 最久要用

替换“最晚才会被再次用到”的页面

现实算法

• 先进先出（FIFO）：

  • 逻辑：谁先进来的，就先踢谁。
  • 缺陷：太傻了。最早进来的可能是主函数代码，一直被用到，结果被踢出去了。

• 最近最少使用（LRU）：最久未用

  • 逻辑：利用“时间局部性”，认为“过去很久没用的，未来大概率也不用”。踢掉那个“最久没被访问”的页面。
  • 优点：比FIFO聪明，符合程序运行规律。
  • 缺点：硬件实现成本高（需要记录每个页面的访问时间戳）。

• 最不频繁使用（LFU）：

  • 逻辑：踢掉那个“访问次数最少”的页面。
  • 缺陷：有些页面刚开始访问频繁，后来不用了，但计数器很高，导致它赖在内存里不走。

内存管理的“终极形态”——内存映射

讲完了怎么管内存，这几页提出了一个更宏大的愿景：消除内存和硬盘的界限。

• 直接把硬盘上的文件映射到进程的虚拟地址空间
• 怎么做：
  • 进程直接对着一段虚拟内存地址进行读写。
  • 硬件发现这页不在内存（缺页），触发中断。
  • 操作系统一看，哎，这页对应的是硬盘上的文件啊，于是直接从硬盘把文件内容读入内存。
  • 结果：程序员感觉像是在操作内存，实际上是在操作文件！

好处

• 高效：不用多次拷贝。
• 共享：多个进程可以映射同一个文件，共享内存。

考点☆ 具体怎么做？

硬件机制：

缺页异常

当页表中没有某个页时，产生操作系统可截获并处理的异常。

访问位A

当某个页被访问，其页表的访问位会被硬件置位。

脏位D

当某个页被实际写入（内容遭修改），其页表的脏位会被硬件置位。

给 FIFO 加点“智慧”——利用访问位 二次机会法CLOCK法

淘汰页面时找到一个访问位A不为0的页面，其余A=1都置为0.进入下一轮逃杀

利用脏位

修改过的页面需要保存再换入，时间长

改进的clock算法 三次机会法

先清除D脏位再清除A访问位

页面置换的其他考虑

抖动（Thrashing）     当被分配的页数小于当前工作集的时候，缺页率会大幅增长。
分配策略的动态性     一个进程的页数量可以是静态决定的也可以是动态调整的。
置换策略的全局性     页置换可以仅仅在一个进程内部发生，也可以在进程间发生。

进程的操作

创建 销毁 分配资源 等待 复制 设置特权 设置策略

第六章

文件：一个具备一些属性的数据记录，对外存的一种组织和抽象。可以CRUD。

属性：文件名、文件大小、创建日期、修改日期、文件权限、所有者等内容（FCB）

逻辑结构：字节流结构是最基本的结构
字节流结构    提供一个连续的存储空间，可存放任意的数据。         
记录结构    提供一系列固定大小的存储空间，可以存放多个大小固定的数据块。         
索引结构    提供一系列的键值对，可以根据键来查询值。

文件系统 将文件中的文件块按照一定的方法映射到物理设备上的物理块，提供信息管理。的软件栈称为文件系统。

文件的组织    文件系统一般以树状的方式组织文件

路径     一系列由分隔符隔开的子字符串

目录 文件路径中由分隔符隔开的子字符串，又称文件夹。每个目录都对应于一个文件组织层次

相对路径    从目录D起始，逐步查找到文件F的路径

绝对路径    某文件F相对于系统根目录的路径。

工作目录    文件路径解析的起始目录。

文件存储分配算法

文件的存储:连续分配法

将文件放置在外存上,  占据连续的物理空间。 FCB中只要记录文件的起始块号和长度,就能唯—确定 —个文件。

优点：顺序和随机读写速度都快 ,  不会出现内部碎片。
管理数据结构短小精悍, 存储介质利用率高。
存储介质损坏只影响部分数据, 数据存储可靠性好。
缺点：扩容难,  有外部碎片。

文件的存储:链接分配法（解决可扩展）

为了解决连续分配的扩容问题，把文件拆成一个个块，用指针串起来。这样文件可以随便长，但读文件时得顺着指针一个个找，速度很慢；而且指针本身占空间，一旦指针坏了，整个文件就丢了。

优点：文件长度可以随意增减,  不会产生外部碎片。
缺点：顺序读写慢,  随机读写更慢。
管理数据结构包含指针。
存储介质损坏可能会导致指针丢失,因此, 数据存储可靠性差。

分配块的大小怎么选择? 选择物理块的大小,  还是更大的单位?

文件的存储:拓展分配（综合连续和链式）

连续分配和链式分配的折中。使用链表来避免外部碎片,使用 可变长度的块来避免内部碎片。这种可变长度的连续块称为扩展  (Extent)  ,其内部包含指向下—个扩展的指针,以及本扩展的长度。 

结合前两者的优点，把文件分成“扩展块”（连续的小段），再用指针连起来。这样既减少了碎片，又比纯链接快一点，但还是没解决随机读写慢和指针损坏的问题。

优点：文件长度可以随意增减, 不会产生外部碎片;  同时扩展 大小灵活,也不会产生内部碎片。
缺点：顺序读写有—定提升,随机读写还是慢。
管理数据结构包含指针和扩展长度。
存储介质损坏可能会导致指针或扩展长度丢失,因此, 数据存储可靠性仍然差。

文件的存储:链表备份法（解决可靠性差）

为了解决链接分配的可靠性问题，把所有指针集中存到一张表（FAT表）里，单独备份。这样即使数据块坏了，只要FAT表还在，文件结构就不会崩；而且FAT表可以加载到内存，随机读写速度变快。

管理结构就和数据本身完成了解耦

数据区受损只会引起数据损坏, 不会引起文件系统崩溃

文件的存储:索引分配法（解决随机读写慢）

为了彻底解决随机读写慢的问题，给每个文件建一个“目录”（索引表），直接记录每个数据块的位置。这样找数据就像查字典，速度飞快；但索引表本身占空间，大文件需要多级索引，结构复杂。

优点：
连续和随机访问都快,抗损性能也强。
缺点：不好分配
索引预留多了, 浪费;索引预留少了,文件大小受限。

但是指针分配大了浪费 少了不够，怎么办？

文件的存储:按需分配法

像组织页表那样,将多个索引表以层次结构组织起来,每个层   次负责翻译逻辑块号的—部分, 最终得到物理块号。不使用的索   引块不创建、不填充就可以了。虽然随机访问仍然引起指针追逐,  但是追逐的次数是有限的,也即索引的层数

文件的存储:混合索引法

操作系统启动时会加载很多小文件，对小文件多级索引不核算。

文件的索引采取多级方法进行,  但索引的级数随着文件块号的增加 而增加。文件越靠前的部分, 索引的级别越少。这样, 小文件的存储效率就提高了。

混合索引法就是“把最常用的数据放在手边（直接索引），不常用的数据放在抽屉里（一级索引），极少用的庞大数据放在仓库里（二级索引）

索引分配法存储小文件浪费，比如索引2MB，数据1MB

空闲块的组织算法

文件的查找：索引节点

将FCB拆成两部分，文件名直接储存在目录文件中，而其它属性放在索引节点中。

索引节点单独使用一个线性表存放，目录文件仅储存索引节点到索引节点编号的映射。这样，移动文件时完全不需要触碰索引节点，仅需要触碰目录文件中的一行。

文件的引用

硬链接：通过某个名称访问另一个名称所属内容的形式叫做“链接”，在文件系统数据结构层面实现的链接称为硬链接

软链接：一个独立于其目标的的链接文件，该文件的内容是它指向的原文件的路径。

元文件系统：文件系统的文件系统，又叫虚拟文件系统

文件权限管理

ACL PCBA ACBA 

第七章

软件    运行、组织、管理、维护设备使用的程序。主要包括系统软件和用户软件。 

硬件    运算器、控制器、存储器、输入设备和输出设备。

输入输出设备

外设接口：数据寄存器 状态寄存器 命令寄存器

信息交换：直接 轮询 中断 成组

编地方式：独立 统一

设备分类

按用途：人机交互设备、存储 设备、通讯设备、协处理设备

按速度：告诉设备、低速设备

按传输单位：块设备、字符设备、其他设备

按物理存在性：物理设备、虚拟设备

仅在概念上存在的设备。它有着和真实设备一样的接口，并对操作做出反应。
但找不到一个物理实体和它对应。又叫逻辑设备。

数据传输方式：直接传输设备、轮询设备、中断设备、DMA设备

共享类型：共享设备、假脱机设备、独占设备

实时时钟

定时器——带上限的计数器。

两组D触发器，一组用来计数，一组用来存上限，一个比较器持续比较二者，溢出置零

定时器中断——定时器置零的时候发送中断，让OS重启计时器

软定时器——以系统定时器作为时基。每一个系统时刻检查所有软定时器看看有没有超时。

万年历——内部是一系列串联的定时器，上一级的溢出信号作为下一级定时器的输入。

机械硬盘

读写单位 簇（Cluster），连续扇区的集合。

磁道：越靠近的磁道之间的访问延迟更低，同时从内圈往外圈读访问延迟比从外圈往内圈读低

同一个磁道，从前往后读快，从后往前读慢。一个簇内部的写则最好一次写完。

缓冲（Buffer）与 缓存（Cache）的区别

1. 缓冲区（Buffer） - 速度不匹配

   • 作用：解决速度不匹配（CPU极快，硬盘极慢）和数据单位不一致的问题。

   • 核心特点：先进先出队列（FIFO）。

   • 磁盘优化：系统不会一个请求来了就立刻移动磁头，而是把请求塞进“操作缓冲区”。同一个“簇”的读写请求合并，并按照磁道位置进行重新排序。这为后面的“磁盘调度算法”做好了准备。

2. 缓存（Cache） -减少读盘

   • 作用：含有一系列簇的副本；如果操作请求命中，就免去磁盘读写

3. 缓冲池：多个缓冲区的集合，由内核各模块共享。程序需要时申请，用后释放回来，提供统一的接口并集中管理，

磁盘调度算法 - 物理上的“谁先动”

1. 先来先服务（FCFS）

• 做法：谁先来，就先去哪个磁道，不管远近。

• 缺点：磁头会疯狂左右乱跑，效率极低。

2. 最短寻道时间优先（SSTF） 

• 做法：磁头当前位置在哪，就选择距离当前位置最近的那个请求去服务。

• 缺点：如果一直有离当前位置很近的新请求到来，那么离得远的磁道（比如最外圈或最内圈）就永远得不到服务。这就叫“饥饿现象”。

3. 电梯扫描算法（SCAN 及其变种）

将队列中的请求排序，从头扫描到尾，然后再从头开始

基于回程时是否响应，以及是否扫描到底，有以下四个变种。

1. 为什么叫“循环”（Circular）？

• 普通 SCAN（电梯算法）：就像一部正常的电梯。它从一楼到顶楼，然后原路返回（下降），下降途中继续响应请求。来回都干活。

• C-SCAN（循环扫描）：它不原路返回。它只朝一个方向（比如从外向里）扫描。一旦扫到了最内侧，它“啪”的一下瞬移（或者说是绕一圈）回到最外侧的起点，重新开始从头往里扫。

也就是说，它的运动轨迹是一个“从起点到终点，然后瞬移回起点”的无限循环，所以叫 Circular（循环）。

驱动程序

直接控制设备的接口程序。

驱动程序是设备依赖的。这是由于它们直接控制设备。更换设备，就要更换驱动程序

设备号：主设备号（厂商号）用来标记厂商，次设备号（设备号）用来标记具体产品。

驱动程序的功能         

查找设备    
扫描并检测硬件改动，识别应当识别的设备。         

初始化设备    
初始化并对设备进行必要设置，注册中断ISR。         

响应设备请求    
响应设备的中断等，在设备运行中与设备交互。         

响应软件请求    
执行操作系统和应用程序下发的设备操作指示。

阻塞

在驱动程序中，如果设备无法立刻完成操作，就需要阻塞发起操作的应用程序线程

中断

为什么要把中断分成“两半”？

问题根源： 中断处理必须极其迅速。如果在处理中断时，CPU一直“关中断”（不响应新中断），那么系统就会错过其他更紧急的信号。

接口分类

按功能分类：人机交互设备接口（wxWidgets、MFC、WPF）、存储设备接口（文件系统提供的文件操作）、网络设备接口（socket）、显示设备接口（OpenGL、DirectX等图形学库）

按阻塞性分类：阻塞接口、非阻塞接口

当设备无法即时完成操作或返回消息时，线程将阻塞，直到设备返回数据。一定需要操作系统介入

当设备无法即时完成I/O操作或返回消息时，该接口将立即返回，并将当前设备状态报告给调用线程。线程可以以合适的间隔轮询此接口，直到获取到数据。不一定需要操作系统介入。

问题（1）：为什么需要非阻塞接口？一切接口都阻塞不好吗？

• 答案：如果一切接口都阻塞，一旦遇到慢速设备，线程卡死在那里。

问题（2）：阻塞接口和非阻塞接口，哪个效率高？

• 答案：“数据量小的设备，阻塞效率高；数据量大则反之。”

按同步性分类：同步接口、异步接口

第一层：核心概念——什么是“同步”与“异步”？

判断标准很简单： “发起请求后，你是自己亲自等结果，还是让别人（系统）结果出来时通知你？”

1. 同步接口（Synchronous）—— “亲自去等结果”

• 用同一个接口操作来发起I/O请求和接收I/O结果；当接口返回时，I/O结果必定已知，要么完成，要么失败。

2. 异步接口（Asynchronous）—— “我先走，结果出来了你叫我”

• 用一个接口操作来发起I/O请求，并用回调函数来接收I/O结果；发起请求的I/O接口操作返回时，请求可能还在处理中，I/O结果要等到回调函数被调用时才知道。

回调函数

（1）定义该回调函数

（2）将回调函数的函数指针和触发它的条件注册给系统

（3）系统将在满足条件时调用它，提醒应用程序某事件发生。

设备的共享 SPOOLING

通过磁盘（高速存储）来充当外设和CPU之间的缓冲，把“对设备的直接控制”替换为“对磁盘文件的读写”。IF程序不关心也不等待操作的执行完成才能继续进展，则各程序可以将请求提交到队列，设备则从队列中依次拿出请求执行。相当于将异步I/O操作转化成了一个同步I/O操作。对于每个假脱机设备，启动守护进程来管理队列和操作I/O，其他进程则把这个进程当成虚拟设备并操作它。

第八章

指令流间的关系

偏序集：（1）自反的，（2）反对称的，（3）传递性的，但集合S中至少存在一对元素之间不具备此关系

偏序的关系图就是一个有向无环图。

临界资源：

不能同时被两个指令流使用的资源。 文件 设备

临界区：

访问临界资源的程序段，临界区不能并发执行。又叫做关键区域。临界区越短越好，最好只包括访问临界资源的必要步骤。太长了就只能等着

互斥

临界资源不能并发使用的现象称为互斥。它在指令流的执行上，表现为临界区在任何时候只能最多被一个指令流执行。

伯恩斯坦(Bernstein)条件

[R(S1)∩W(S2)] ∪ [R(S2)∩W(S1)] ∪ [W(S1)∩W(S2)] = Φ， 则操作可以并发执行。

就是只能同时读。不能有一方在写。

Peterson算法（结合竞争 合作） 考点 ☆

对于指令流S0：

1. ① want[0] = 1;

   • S0举起牌子说：“我想进去！” (宣布意图)

2. ② turn = 1;

   • S0非常有礼貌，把“通行令牌”扔给S1说：“兄弟，你先，我等你。”

3. ③ while (want[1] == 1 && turn != 0) { 等待 }

   • S0检查对方S1：如果S1也举着牌子（想进来），且现在通行令牌不在我手里（turn不是0），那我就乖乖等着。否则，我就跳过等待，进入④。

我想去，如果对方也有意愿且当前轮次不是我的 我就等待

能进去的情况，要么是

（1）对方want = 0，不想要

（2）对方主动让给自己的turn，对方肯定在等待。

上述实现会出现（1）死锁，（2）活锁或者（3）饥饿吗？     

（1）不会出现死锁，如果两人都拿着 want=1 互等，最后执行 turn 的那个人会主动让出自己，另一方必定能进去，所以死锁破除。
（2）不会出现活锁，因为双方都在等待时均不放弃自己的进入意图。当一方退出（执行 ⑤ want[0]=0 时），另一方会立刻进入临界区
（3）不会出现饥饿，turn 变量就像一个交替换班的令牌。只要有人用完退出了，下次轮到对方的概率是公平的

互斥锁：自旋锁

互斥锁Lock/Mutex

一种用以控制临界区访问的互斥访问原语（原子语句，同时发生），分为加锁和解锁两个原子操作。进入临界区先加锁，退出临界区后解锁。

• 当一个线程想进临界区，但锁已经被别人拿走了。

• 阻塞锁：操作系统把这个线程挂起（放入等待队列），让CPU去干别的活。等锁空闲了，再唤醒它。（不浪费CPU，但切换有开销）。

• 自旋锁（Spin Lock）：这个线程不放弃CPU，它在原地一直打转（执行一个空的循环 while(lock==1) {}），不断地问：“锁释放了吗？锁释放了吗？...”就像陀螺一样原地高速旋转，直到锁被释放，它立刻抢到锁。

好自旋锁的三个标准

互斥访问    Mutual Exclusion（忙则等待）                 

临界区保证互斥，任何时候只有一个指令流。         

全局进展    Global Progress（空闲让进）                 

如果目前临界区没有占用，则在有指令流请求时应当满足它，不会陷入全局死锁。

局部进展（*）    Local Progress（有限等待，Bounded Waiting）                 

任何一个指令流的等待时间都是有上界的，不会陷入局部或全局活锁。上界一般是O(n)。

 硬件锁

如果我们能利用硬件功能，让①和②之间不发生调度，那也可以。

开关中断——不允许指令切换

封禁调度器的一个最简单办法就是关中断。一旦关中断，时钟中断就无法发生（此时若时钟中断到来，需要等待开中断后才发生），自然无法进行指令流或线程切换

处理器都有开关中断指令，为何这种方法仅在那些针对无内核模式的CPU的操作系统上（如FreeRTOS、RT-Thread）广泛使用？

该算法要赋予所有指令流直接开关中断的权限。一旦有恶意指令流，它关中断后不再开启，就可以得到100% CPU，可以轻易破坏线程间的时间隔离

第一部分：三大“原子指令”神仙打架（分别对应三张图）

先理解一个共同的概念：什么是“原子指令”？
通常情况下，读取变量和修改变量是两个动作，中间可能会被线程切换打断。而“原子指令”是CPU硬件提供的超能力，它保证上锁这个动作，“检查”和“修改”两个动作在一个不可分割的瞬间同时完成。要么全做，要么全不做，没有任何缝隙可以被别人插队。

这三张图分别用了三种经典的硬件原子指令来实现自旋锁：

1. SWAP / XCHG（图1）——“直接硬换”

• 指令含义：交换两个内存地址的值（完全替换）。

• 锁代码原理：

• • 

    线程自己兜里揣着一个 1（current[0]=1）。

  • 用 swap() 指令，把自己的 1 和锁变量 enter 里的值瞬间互换。

  • 结果：如果 enter 原本是 0（空闲），换回来 current 就是 0，你成功抢到锁（enter变成了你兜里的1）。如果 enter 原本是 1（别人占了），换回来 current 就是 1，说明没抢到，继续 while 循环。

2. TAS / BTS（图2）——“测试并设置”（最经典、最常用）

• 指令含义：Test-And-Set。检查一个内存位的值，如果它是0，就把它改成1，并返回旧值（0或1）。这个过程也是原子的。

• 锁代码原理：

• • 

  • bts 指令瞬间完成两件事：① 看看锁是不是1；② 把锁强行改成1。

  • 如果返回1（说明锁原本就是1，被别人占着），那继续死循环等待。

  • 如果返回0（说明锁原本是0），bts 已经把锁设成了1，说明你抢到锁了，立刻跳出 while 循环进入临界区。

3. CMPXCHG / CAS（图3）——“比较并交换”（现代高并发之王）

• 指令含义：Compare-And-Swap。判断内存里的值是不是等于我预期的旧值（old），如果是，就把它换成新值（new）；如果不等，说明被别人改了，什么都不做。也是原子操作。

• 锁代码原理：

  • 

  • 意思是：“我的期望值是0，我想把它改成1”。如果此时 enter 确实是0，那瞬间变成1，返回0（成功上锁）。如果是1，则原子指令什么都不做，返回1（说明有人抢了），继续死循环。

第二部分：结合三张图下方的“问题”——它们的致命缺陷

你可能会发现，这三张图下面的问题（问题一、问题二）几乎一模一样。这说明这三种方法有共同的优点，也有共同的致命缺点。

优点（可以回答图里的问题1和2）：

1. 不会死锁：因为 while 循环一旦抢到锁就会立刻退出，没有互相等待的闭环。

2. 不会活锁：要么抢到，要么一直抢，不存在互相谦让导致谁也进不去的情况。

3. 互斥完美：全靠CPU硬件保证一瞬间只有一个线程能成功修改 enter。

致命缺点（回答图里的问题3，以及图3的问题二）：

这三张图底部的文字都问了同一个问题：“它能保证公平进入吗？” 以及 “有什么缺点？”

答案是：大缺点！这几种锁是绝对不公平的（会导致“饥饿”）。

• 不公平（饥饿问题）：
  请看这行代码：while (条件为真) { }

  • 假设有100个线程在排队抢这把锁。一旦当前持有锁的线程释放锁（执行 enter=0）。

  • 问题来了：此时，这100个线程全都从 while 循环里醒过来，一起并发地去执行硬件原子指令抢锁。

  • 因为指令是原子的，但CPU总线带宽有限，总有一个线程会抢赢，其他99个继续转回去 while 等待。

  • 最倒霉的情况：线程A可能运气极差，连续100次抢锁都慢了一点点，被别的线程抢走了。在纯自旋锁中，没有排队机制，线程A可能永远等不到锁，导致“饥饿”。

图3底部的终极追问：“上述（自旋锁）最大的缺点是什么？”

答：是“忙等待（Busy Wait）”——也就是一直在消耗CPU算力空转！
这就是我们之前讲到的：如果临界区代码稍微长一点，或者持有锁的线程被操作系统挂起了，那么其他99个自旋的线程就会把CPU烧到100%，电脑变卡，系统整体吞吐量大幅下降。

互斥锁：阻塞锁

第一层：为什么需要阻塞锁？（顶部的“自旋的缺点”）

图里列举了自旋锁（Spinlock）的四个致命缺陷，尤其是第（1）和（2）条，是引入阻塞锁的根本原因：

1. 无谓地浪费CPU：不拿到锁就不停地 while(1) 空转。

2. 造成内存总线压力：在多核系统中，成百上千个CPU核都在疯狂地通过总线“盯着”同一个锁变量，这会挤爆内存通道的带宽，让整个系统变慢。

3. 无法在“多对一”模型中使用：这是高级并发考点。假设有很多用户线程（指令流）映射到同一个内核线程上。如果一个用户线程自旋等待，它霸占了整个内核线程，导致同一个内核线程上的所有其他用户线程全被卡死。

4. 不公平：没有排队机制，靠运气抢锁，容易造成某个线程永远抢不到（饥饿）。

结论：为了解决上述问题，必须引入“遇到锁被占用时，主动放弃CPU”的机制。

第二层：阻塞锁是如何工作的？（中间的“阻塞锁”段落）

看图中间那段文字，它的核心逻辑就是“让权等待”和“排队”：

1. 立即停止执行（让出CPU）：当指令流发现锁被占用时，它绝不空转。相反，它调用操作系统内核，把自己的状态标记为“阻塞（Blocked）”，并将CPU交给别的线程去运行。

2. 进入等待队列（排排坐）：操作系统会维护一个“等待队列”。就像排队买奶茶一样，没抢到的线程按“先来后到”的顺序乖乖排在这个队列里。

3. 唤醒机制（叫号）：一旦锁的占有者释放了锁，操作系统不是把排队的所有人都叫醒（防止他们再次疯抢），而是只叫醒队列头部（排在最前面）的这一个线程，把锁直接交给它。

4. 实现公平性：这种排队和叫号的机制，彻底解决了饥饿问题，保证了绝对的公平。

---

第三层：阻塞锁的实现方式

• 可以在“线程级别”（内核空间）实现：这是操作系统内核提供的原汁原味的睡眠锁（如 Linux 的 mutex）。当线程阻塞时，整个线程陷入内核并睡大觉。

• 可以在“指令流级别”（用户空间）实现：这通常指用户级线程（协程 / Green Thread）。在这种模型下，当一个指令流阻塞时，它只是把自己停掉，不让整个线程陷入内核，而是让同一个线程上的其他用户级指令流继续跑。

🔒 自旋锁 (Spin Lock)

自旋锁的原理是“忙等待”（Busy Waiting）。当一个线程尝试获取锁时，如果锁已被其他线程持有，它不会被挂起或进入睡眠状态，而是会进入一个循环，不断地检查锁是否被释放。

• 加锁过程：

  1. 线程尝试通过原子操作（如CAS）获取锁。
  2. 如果成功，则进入临界区执行代码。
  3. 如果失败，说明锁已被占用，线程不会放弃CPU，而是在一个循环中持续重复步骤1，这个过程被称为“自旋”。

• 解锁过程：

  1. 持有锁的线程执行完临界区代码后，通过原子操作释放锁。
  2. 此时，正在自旋的其他线程在下一次循环检查时会发现锁已被释放，其中一个会成功获取锁。

• 自旋锁的优缺点：

  • 优点：

    • 无上下文切换开销：线程在无法获取锁时不会进入阻塞状态，而是持续循环检查锁状态（即“自旋”），从而避免了操作系统线程调度与状态切换的开销。

    • 适合短临界区：若持有锁的时间极短（小于一次上下文切换所需时间），自旋锁效率远高于阻塞锁。

    • 多核友好：在多核系统中，不同核心可并行自旋，提高锁竞争时的响应速度。

  • 缺点：

    • 浪费CPU资源：若锁被长时间持有，自旋线程持续占用CPU，导致系统整体效率下降。

    • 不适用于长临界区：临界区过长时，自旋锁会因持续空转而严重降低系统性能。

🛌 阻塞锁 (Blocking Lock)

阻塞锁的原理是“让权等待”（Yield and Wait）。当一个线程无法获取锁时，它会主动放弃CPU，进入阻塞（睡眠）状态，由操作系统调度器将其挂起，并切换到其他线程执行。

• 加锁过程：

  1. 线程尝试获取锁。
  2. 如果成功，则进入临界区。
  3. 如果失败，线程会向操作系统发起系统调用，请求将自己挂起。操作系统会将该线程的状态从“运行态”改为“阻塞态”，并将其放入一个等待队列中，然后调度其他线程运行。

• 解锁过程：

  1. 持有锁的线程执行完临界区代码后，释放锁。
  2. 操作系统会从等待队列中唤醒一个或多个线程，将它们的状态从“阻塞态”改为“就绪态”。
  3. 被唤醒的线程需要等待调度器再次分配CPU时间片，才能重新尝试获取锁。

• 阻塞锁的优缺点：

  • 优点：

    • 节省CPU资源：无法获取锁时线程进入阻塞状态，释放CPU给其他线程，系统资源利用率更高。

    • 适合长临界区：锁持有时间长时，阻塞机制避免无效轮询，保证系统稳定性。

  • 缺点：

    • 上下文切换开销：线程从运行态进入阻塞态，再被唤醒，涉及状态保存与恢复，带来性能损耗。

    • 调度延迟：线程唤醒需依赖操作系统调度，响应时间不如自旋锁即时。

前面是这些锁底层如何实现。接下来是如何使用这些加锁机制。

管程

管程封装了加锁解锁。

第一层：终极工具一——管程（Monitor）

• 管程看起来就像一个对象，该对象的各个成员函数均封装了加锁、访问资源、解锁三个过程。

管程的特点    

互斥性    

管程内的临界区只能由一个指令流进入并执行。         

模块化    

管程是可单独编译的程序的基本单元，一般写在一个单独的源文件内。         

封装性    

管程封装了对原始临界资源的一切操作，不向外界暴露任何接口。管程内的任何数据只能通过管程的接口访问，同时管程代码也只访问管程内部的数据。         

抽象性    

管程抽象掉了原始临界资源的细节属性，仅保留了其高层次的功能接口。

守护进程和管程的区别：

空间安全性（守护进程运行在内核，强隔离）

守护进程运行在独立的地址空间，垄断了临界资源。因此，指令流不可能得到机会亲自参与临界资源操作。

相比之下，管程只是将敏感操作藏起来，恶意指令流，还是可以强制I/O：因为I/O的代码和这些指令流在同一个地址空间。

时间安全性（管程内运行线程，消耗自己的时间片而不是代理人的时间片）

管程虽然在空间上不安全，在时间上却是安全的。

每个线程执行管程消耗的都是它自己的时间片，发起大量恶意请求只会导致自己的时间预算耗尽。

相比之下，守护进程却不是这样：因为工作都推给了守护进程，消耗的是守护进程内的I/O线程的时间片。

如果一个恶意线程向守护进程提交大量的垃圾I/O，就可以用掉该I/O线程的所有时间片，使其他线程的请求得不到执行。

如果想要守护进程的空间安全性，又要管程的时间安全性？

管程线程迁移法（管程运行在隔离空间内，线程不变，维护时间隔离）

需要访问临界资源的时候就把线程迁移到隔离管程中，访问完再离开。

时间托管法（调用者转移时间片给守护进程，解决守护进程无时间安全性的问题）

要求线程提交IO请求的时候，要求给一些时间片给守护进程，守护进程中的IO线程用这个时间片执行。（守护进程中的线程充当代理人执行）

第二层：管程内部的沟通工具——条件变量（Condition Variable）

用于解决同步的问题（消费要在生产后）

• 核心作用：它总是与一个锁配合使用：如果条件不满足，则指令流自动释放锁并加入等待    队列；而当条件满足时，等待队列头部的指令流将被唤醒并自动恢复对锁的持有。

条件变量是指令流A在拿到锁后，根据条件决定对锁的操作的，比如不满足指令流A就会调用条件变量释放锁，进入阻塞态。如果满足，当前指令流A就唤醒下一个指令流B。

• 两个核心操作：

  1. Wait（阻塞/入队）：消费者发现资源不够时，调用 Wait。关键动作：它会在睡着的瞬间，先把你手里的锁给释放掉！

  2. Signal（唤醒/出队）：当你生产了数据后，调用 Signal 去叫醒一个排队睡觉的消费者。

场景：消费者线程 A 想要从空队列里取数据。

1. 【准备阶段】：系统里已经存在了一个锁（Mutex）和一个条件变量（CV）。CV 本质上是空的队列。

2. 【第1步：拿锁】指令流 A 调用 lock()。

   • 拿到锁。注意：此时条件变量什么事都没干，它只是安静地待在那里。

3. 【第2步：检查条件】指令流 A 检查共享变量（如 queue.isEmpty()）。

   • 发现队列为空。

4. 【第3步：关键交互】指令流 A 调用 cv.wait(&lock)。

   • 此时条件变量才真正“动”起来！

   • 动作1（原子操作）：CV 帮 A 把拿到的锁给释放掉。

   • 动作2（入队）：CV 把 A 这个线程添加到自己的等待队列里（CV 内部队列现在多了 A）。

   • 动作3（阻塞）：让 A 睡去。

5. 【后续】生产者线程 B 来了：

   • 拿锁成功，往队列里放了一个数据。

   • 调用 cv.signal()。

   • 此时条件变量再次“动”起来：它去自己的等待队列里，把刚才排队的 A 叫醒。A 醒后，内核会自动让它重新去争取锁。

惊群效应

多个指令流的阻塞同时被解除，争抢同一个资源造成负载极具增大的现象。

条件变量的两种语义（Hoare vs Mesa）

Hoare语义    Hoare Semantics

条件变量的唤醒操作将保证被唤醒的线程立即得到调度并持有锁。

在这个语义下，一旦某个指令流被唤醒了，那就说明条件百分之百成立，指令流无需重复检查条件是否仍成立。

Mesa语义    Mesa Semantics

条件变量的唤醒操作仅保证被唤醒的线程进入就绪状态，需要参与锁的竞争，并不保证该线程立即得到调度。

在这个语义下，被唤醒的线程仅仅是得到了一个提醒：你的条件曾经可能满足过。要在醒来后再次检查

条件变量是的意思是“根据是否满足这个条件，执行上锁/解锁的操作”，是代理人，但是只能处理01问题。但是加上计数器就可以处理数值问题了。

阻塞锁是负责互斥的。别人用锁的时候自己要通知OS把自己加入等待队列。

1. 阻塞锁（Mutex）：最基础，负责“互斥（不让两个人同时进一间房）”。

2. 条件变量（Condition）：以“阻塞锁”为前提，加上了“同步（等待特定状态）”的功能。它必须配合阻塞锁一起用（负责在门内等纸）。

3. 信号量（Semaphore）：高级封装。它可以在内部自带计数器，可以直接当阻塞锁用，也可以当条件变量用（因为内部自带了锁 + 等待队列）。

信号量

同时具备资源计数和等待两种功能

获取操作Acquire         

也叫“P”操作。减少计数器的计数，代表从系统中拿走资源。如果系统中当前没有资源，则可以阻塞或自旋并等待。

释放操作Release         

也叫“V”操作。增加计数器的计数，代表向系统中投入资源。

死锁活锁与资源图

 

死锁

系统中有指令流发生无法自行解除的循环等待。

具体地，有如下三个条件：         

互斥条件（有争夺）

系统中存在有一定互斥性的资源。         

持有条件(不让放弃自己拿到的 且 不能夺取别人的)

指令流已获得的资源不释放，且新请求不撤销。

其中，持有条件又可以细分为如下两条：         

保持请求    指令流不主动放弃已经持有的资源。

无法剥夺    不允许指令流互相剥夺资源；非抢占。        

循环等待（你我都不让）

指令流互相循环等待资源释放，不能进展。

活锁        

指令流并未死锁，但其在多次反复尝试获取资源均失败。

死锁能自动解除吗？活锁呢？

死锁不可能自动解除。因为持有资源+循环等待，任何指令流都在等待其它指令流释放资源。

但活锁则不一定，只要指令流的执行进度发生一些细微变化，不再碰巧让对方的条件在反复重试中失败，就有可能产生进展。

三种实现结构

就是说无阻碍结构是不保证多个指令流运行时有一个人能完成的，无锁数据结构是能保证至少一个人在多个指令流中完成的，而无等待数据结构是保证所有人都能正常完成

无等待数据结构——保障至少一个指令流能进展

无锁数据结构——所有的指令流都能进展

无阻碍数据结构——无死锁

• 定义（图里的红字）：只能保障自己一个人指令流，多个指令流什么爷保证不了

• 定义（图里的红字）：保证全局进展，不保证局部进展。即无论系统中有多少个线程在竞争，至少有一个线程能保证在有限步数内完成自己的操作（整个系统的CPU不会空转）。

• 定义（图里的红字）：保障局部进展 + 全局进展。即无论系统中发生多么严重的竞争，每一个指令流，都能在有限个步骤内完成自己的操作，绝对不会出现某个线程永远重试失败（饥饿）。

资源分配图——用于研究死锁问题的有向图

图一是链式等待，不是死锁。

图二是有环路A->R1->B->R2->C->R3->R1R2

图三有死锁，R3被C请求2，只有1，无法分配，而R3被AB占用，而AB不愿意放弃自己占有的资源，A->R1->B->R2->C->R3->R1R2,导致链式依赖。

化简资源分配图

资源分配图的分析方法

1. 若某指令流的所有请求都可以得到满足，则删除其所有请求边和分配边，并将分配边上的资源归还给各个资源池。

2. 重复上述步骤，直到无可执行。

此时若所有指令流都执行结束则无死锁。若还有指令流存在（无法被化简掉），则它们一定在循环等待，此时发生死锁。 只有最后剩下的指令流是死锁的

银行家算法

• 假设线程1已经申请了 Q（进入了不安全区域的左边缘）。此时，操作系统（或调度器）绝对不能允许线程2去申请 S（进入不安全区域的下边缘）。

• 操作系统的做法：如果线程2这时候想申请 S，系统会判断“如果你现在拿了 S，你们俩就会进入红色阴影区，有死锁风险”。于是，系统会让线程2阻塞（暂停等待），直到线程1安全地拿到了 S 并释放了资源，走出红区后，才允许线程2去拿 S。

操作系统像一个交通指挥官，它会实时监控你和另一个线程的资源使用轨迹。如果发现你们接下来的步伐会导致“你拿我的，我拿你的”这种交叉等待（即跨入红色阴影区），系统就会强制按住其中一个人不让走，直到另一个人彻底跑完拿到所有资源，确保安全了，才放行。

一种用于资源分配的算法。通过检查请求仅批准那些不会让系统进入不安全状态的请求，完全避免死锁风险。

‘

如何避免死锁

鸵鸟政策    

操作系统仅提供同步工具，不负责探测和解决死锁，而是由人或其它系统服务在死锁时介入。

破坏互斥条件    

只要想办法让资源本身不互斥、不竞争，就自然不存在等待问题，就不可能死锁。

破坏保持请求    

要求指令流在无法进展时主动放弃之前获得的资源。

破坏无法剥夺    

一旦探测到有可能死锁，就强制剥夺死锁参与者的全部资源。

破坏循环等待    

阻止系统中生成可能的等待环路。

第九章

通讯的四个级别（表格解析）

表格按“开销（从极小到极高）”和“实现空间”把通讯分为了四档：

1. 指令流间（开销极低，用户空间实现）：

   • 这是什么：这是指同一线程内部，或者用户态协程（User-level Coroutines）之间的切换与通讯。

   • 为什么便宜：因为根本不需要进入操作系统内核（不需要系统调用），只需要代码自己在内存里切换一下栈指针即可。纯算数级别的快。

2. 线程间（开销低，用户或内核空间）：

   • 这是什么：同一个进程内的两个线程（比如Java里的两个Thread）共享同一块内存空间，用我们之前学的锁、信号量进行通讯。

   • 为什么算低：因为它们共享内存（不用拷贝数据），只需要把变量改一下。但如果线程因为竞争锁而阻塞了，就要陷入内核。

3. 进程间（开销高，内核空间）：

   • 这是什么：两个完全独立的程序（比如Chrome浏览器和Word文档）要互传数据。

   • 为什么贵：因为它们的内存空间是隔离的。操作系统必须把数据从A的内存复制（拷贝）到B的内存，这个拷贝动作必须由操作系统内核来执行，涉及大量内存搬运。

4. 应用程序间（开销极高，内核+中间件）：

   • 这是什么：比如A公司开发的微信和B公司开发的支付宝，要跨网络传输数据。

   • 为什么极度昂贵：这不仅要过内核（网络协议栈），还要过物理网卡、网线，甚至跨越互联网路由器。开销巨大。

（1）为什么指令流间和线程间通讯可以在用户空间实现，进程间通讯和应用程序间通讯只能在内核空间实现？     

（1）进程和应用程序间通讯必然要跨越空间边界，而跨越空间边界只有操作系统才做得到。跨越时间边界和角色边界则可以在用户模式完成，因为空间是共享的（同一个进程中）。 

（2）在实践中，为什么线程间通讯总是在内核空间实现？

（2）线程是内核管理的，其阻塞式通信就必须在内核空间实现。指令流则是用户空间管理的，其阻塞式通信可以在用户空间实现。

可靠IPC与非可靠IPC

可靠 IPC 是指通信机制能够保证数据不丢失、不重复、按顺序且无错误地从发送方送达接收方。

非可靠 IPC 是指通信机制不保证数据一定能送达，也不保证送达的顺序和完整性。（信号 共享内存）

IPC总结

管道

点对点通信工具。在Linux中，管道分为无名和有名管道。

无名管道    

用于父子进程之间点对点通讯的工具。父进程创建无名管道，Pipe然后调用fork()，父进程端使用一个端口，子进程端使用一个端口，且只能父发子收或父收子发。如果需要全双工，则只能创建两条无名管道。

读空管道 写满管道 就阻塞。

无名管道

1. fork() 的核心机制

当程序中调用 fork() 时，操作系统会复制当前进程，创建一个新的进程。
而 fork() 函数会返回两次：

1. 在父进程中：fork() 返回子进程的 PID（一个大于 0 的整数）。

2. 在子进程中：fork() 返回 0。

2. 代码逻辑详解

结合图片中的代码 if (fork() != 0) 来看：

• 当 fork() 返回值 != 0 时：

  • 意味着当前是 父进程。

  • 所以父进程会进入 if 语句块内部（执行红色的代码：close(fd[0]), write(fd[1]) 等）。

• 当 fork() 返回值 == 0 时：

  • 意味着当前是 子进程。

  • 所以子进程会跳过 if 语句块，进入 else 分支（执行蓝色的代码：close(fd[1]), read(fd[0]) 等）。

无名管道只适用于父子进程，不适用于任何进程。

有名管道

用于任意进程之间通讯的工具。任意进程均可创建有名管道，该管道将作为一个特殊文件存在。此后，进程可以读写文件进行通讯。虽然有名管道允许多个读者和写者，但多个写者之间存在写交叉的风险。

步骤 1：创建管道（通常由 P0 做）

mkfifo("/tmp/myfifo", 0777);

• 含义：在 /tmp 目录下创建一个名字叫 myfifo 的管道文件。0777 是权限，表示所有人都可以读写这个管道。

步骤 2：P0（写者）的行为 —— “只写”

fd = open("/tmp/myfifo", O_WRONLY);
write(fd, buf, len);
close(fd);
unlink("/tmp/myfifo"); // 用完后删除管道文件

• O_WRONLY（只写）：P0 打开这个管道时，告诉操作系统“我只想往里面写数据，我不读”。如果 P0 试图去读，系统会报错。

• write：把内存里 buf 中的 len 长度的数据写进去。

• unlink：数据传完了，把这个管道文件从文件系统里删掉（做好清洁）。

信号 不能传递大量数据 （非可靠IPC）

Linux系统中的一种回调函数机制，可以用来在不同进程之间或同一进程的不同线程之间发送轻量级通知。当通知被送达时，线程暂停执行原程序，转去执行信号处理例程（Signal Handler），然后再返回原程序继续执行。

执行pid的SIGUSR1这个信号，P1收到后触发调用my_handler来处理这个信号。

信号量 可跨进程 Semaphore

Linux系统提供的标准信号量接口，同时具备资源计数和等待两种功能，适用于生产者-消费者关系。

1. 代码逐行分析

sem_t semaphore;            // 1. 声明一个信号量变量
sem_init(&spin, 0, 0);      // 2. 初始化信号量

• 关键在这里：sem_init 的第三个参数是 0。这意味着，这个信号量的初始计数器是 0。这个状态意味着 “一开始没有任何资源”。

线程 T1（消费者 / 等待者）：

sem_wait(&semaphore);       // T1 执行这行时，发现计数器是 0，于是 T1 立刻被阻塞（进入睡眠），等着别人给它送资源。

线程 T0（生产者 / 发送者）：

sem_post(&semaphore);       // T0 执行这行，计数器从 0 变成 1。内核发现刚才 T1 在排队，立刻把 T1 叫醒。
// 此时 T1 醒来，sem_wait 成功返回，T1 继续往下执行。

最后：

sem_destroy(&semaphore);    // 销毁信号量，清理内核内存。

消息队列 多对多 支持

Linux提供的标准消息队列机制，可以在不同进程之间传送信息。 和管道不同，消息队列允许多个发送者和多个接收者，且收发均以消息为单位，无需考虑数据交叠的问题。为了跨越地址空间，Linux会先将消息从发送者拷贝到内核，然后再从内核拷贝到接收者。

为什么需要它？

管道是乱序混合的信息，消息队列是打包好的json

核心机制——怎么跨越“地址空间”？

“为了跨越地址空间，Linux 会先将消息从发送者拷贝到内核，然后再从内核拷贝到接收者。”

结合你之前学的知识，这就是进程间通信（IPC）开销高昂的根本原因。

• P0（进程A）写数据 -> 内存拷贝 1 -> 内核空间的缓冲区。

• P1（进程B）读数据 -> 内存拷贝 2 -> P1 的用户空间内存。

• 数据被彻底复制了两次，所以这是非常消耗性能的。

信号量+共享内存可以实现消息队列，但是消息队列不能实现信号量

1. 定义消息的结构体（图中灰色字体部分）

typedef struct msg_struct {
    long type;           // 消息类型（必须 > 0）。就像包裹上的“类别标签”
    char msg[MAXLEN];    // 实际携带的数据（比如 "Hello"）
} msg_t;

• 精髓：type 这个东西非常实用。比如你可以定义 type=1 是控制指令，type=2 是数据文件。接收方可以指定只接收 type=1 的消息。

2. P0（发送者）的流程：

msg_t msg;
msg.type = 1; // 假设我要发一个类型为 1 的消息
strcpy(msg.msg, "Hello from P0");

// 创建/获取消息队列 ID（标识符 1234）
int mqid = msgget(1234, 0777 | IPC_CREAT); 

// 发送消息！
// 参数：队列ID, 消息指针, 消息结构体大小, 0(表示阻塞发送)
msgsnd(mqid, &msg, sizeof(msg_t), 0); 

// 发送完，删除队列（释放内核资源）
msgctl(mqid, IPC_RMID, NULL); 

3. P1（接收者）的流程：

msg_t msg; // 准备一个空的接收容器

// 消息队列 P0 已经建好了，P1 这边只要知道门牌号 1234 就能打开它
int mqid = msgget(1234, 0777);

// 接收消息！
// 参数：队列ID, 接收容器, 结构体大小, 0(只接收类型为 0 的消息，即接收任意类型)
msgrcv(mqid, &msg, sizeof(msg_t), 0, 0); 

// 打印接收到的数据
printf("Received: %s", msg.msg);

共享内存 最快的IPC机制

Linux提供的地址空间共享机制，可以使两个地址空间之间共享一段物理内存（虚拟地址未必要一致）。内核不再介入数据传递（所以快）。

为什么要他？

消息队列需要两次拷贝，陷入内核态。

• 物理内存的“映射”：正常情况下，进程 A 和 进程 B 的内存是隔离的。但是通过 shmget 和 shmat，操作系统会在物理内存条上划出一块区域，把这块物理内存同时映射到进程A和进程B的逻辑地址空间中。

• 零拷贝（Zero-Copy）：

  • 在消息队列和管道中，数据需要经历：用户A -> 内核缓冲区 -> 用户B（两次内存拷贝）。

  • 在共享内存中，进程A 直接往物理内存地址写数据，进程B 直接从同一个物理内存地址读数据。没有经过内核的搬移，这就是极速的源泉。

代码逐行解析（P0 和 P1 怎么打通房间）

注意看底部的代码，这比消息队列简单得多，核心就是几个指针的操作。

1. 准备工作（通常在 P0 中执行）

int shmid;
// 申请一块 key=1234, 大小为 1024 字节的物理共享内存
shmid = shmget(1234, 1024, 0777 | IPC_CREAT); 

2. P0 和 P1 分别“上墙”（挂载到自己的地址空间）

// P0 执行：把物理内存映射到 P0 的内存中，返回一个指针 ptr
char* ptr = shmat(shmid, NULL, 0);

// P1 执行（代码里的 `<SAME AS P0>` 就是这个意思）：
// P1 也拿着同一个 shmid，挂载到自己的内存空间
char* ptr = shmat(shmid, NULL, 0);

• 重点理解：P0 里面的 ptr 和 P1 里面的 ptr，它们指向的虚拟地址数值很可能不同（比如 P0 是 0x7f1a...，P1 是 0x5c3b...）。

• 但它们指向的底层物理内存地址是同一个！（就像两个门牌号不同，但都通往同一个房间）。

3. 真正的通信（在 ... 省略的部分）

由于 ptr 已经指向了同一块物理内存，所以通信变得极简：

• 进程 P0 写数据：直接执行 sprintf(ptr, "Hello from P0");。

• 进程 P1 读数据：P1 直接执行 printf("%s", ptr);。

• 数据被“直达”了，没有内核介入，没有内存拷贝！

4. 收尾工作（解除和销毁）

// P0 和 P1 分别解除映射
shmdt(mqid); 

// 真正的销毁（一般在所有进程都用完后，由其中一个进程执行）
shmctl(mqid, IPC_RMID, NULL); 

问题一    为什么管道一般不用于跨线程通信？

管道有系统开销需要进入内核。用共享变量会更好。（除了共享变量，其他的IPC都要cp2次）

问题二    为什么线程迁移虽然跨进程，但不跨线程？

线程是在不同的进程中游走不是自己在自己身上变。