操作系统复习笔记

本笔记根据王道操作系统编写，图表部分使用开源项目Excalidraw，图片压缩使用RECOMPRESSOR

点击下载本页 Excalidraw 绘画源文件

[TOC]

一、导论

1.什么是操作系统？

操作系统（Operating System， OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。

操作系统的功能和目标：向上提供方便易用的服务

2.操作系统的特征

Ⅰ.并发

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

易混概念 “并行” 的定义 —— 指两个或多个事件在同一时刻同时发生

Ⅱ.共享

共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。

分为互斥共享和"同时"共享(宏观同时)

Ⅲ.虚拟

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。

分为时分复用(如虚拟处理器)和空分复用技术(如虚拟存储器)

Ⅳ.异步

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

3.操作系统的发展与分类

二、操作系统是如何运行的？

1.操作系统的运行机制

Ⅰ.指令

指令是处理器能识别和执行的最基本的命令
注：与linux和windows的命令行区分开，本质是交互式命令接口

指令又分为两种指令：特权指令和非特权指令

Ⅱ.状态和切换

操作系统可以使用一条特权指令，将PSW的标志位设置为“用户态”，CPU在运行程序时遇到非法事件时，会产生中断信号，强行变回内核态

2.中断和异常

中断是让操作系统由用户态转为内核态的唯一途径，如果没有中断，CPU就会一直执行一个程序直到结束。

也就是说，没有中断，就没有并发性

Ⅰ.内中断（异常、例外）

1.当前程序执行的指令是非法的(比如应用程序打算执行特权指令)，或者执行的指令参数是非法的(比如除数是0)，就会产生中断信号

2.当应用程序需要使用系统内核服务时，就会执行一条陷入指令（又叫trap指令、访管指令），会引发一个内部中断，让操作系统转向内核态，然后由中断处理程序来执行相关操作

系统调用就是通过陷入指令来完成的

注：陷入指令是用户态执行的，不是特权指令

Ⅱ.外中断（中断）

1.时钟中断：时钟部件每隔一段时间发出一个中断信号

时钟中断配合中断处理程序可以实现程序并发执行

2.I/O中断：输入输出设备发出的中断信号

Ⅲ.区别

看中断信号的产生与当前的指令是否有关，有关即是内中断，无关即是外中断。

Ⅳ.中断的基本原理

3.系统调用

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务

Ⅰ.为什么需要系统调用

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

Ⅱ.分类

Ⅲ.系统调用的过程

三、操作系统的体系

1.操作系统内核

内核是操作系统最基本、最核心的部分。 实现操作系统内核功能的那些程序就是内核程序。

2.大内核(宏内核)与微内核对比

大内核：将操作系统主要功能模块都作为操作系统内核，运行在核心态

优点：高性能

缺点：内核代码庞大，难以维护

微内核：只把最基础的功能留在内核

优点：内核功能少，结构清晰，容易维护

缺点：需要频繁切换内核态与用户态，导致性能下降

3.其他体系结构

四、操作系统的引导

操作系统的引导：计算机开机时如何启动操作系统的过程

五、虚拟机

虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（Virtual Machine, VM），每个虚拟机器都可以独立运行一个操作系统

虚拟机管理程序/虚拟机监控程序/virtual machine monitor(VMM)/Hypervisor

通过将CPU时间片划分，可以把一个单核CPU虚拟为多核CPU

六、进程

1.进程是什么？

Ⅰ.进程和程序的区别：

程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
进程（Process）：是动态的，是程序的一次执行过程，同一个程序多次执行会对应多个进程。

Ⅱ.操作系统怎么区分不同的进程？

操作系统会在创建线程时分配一个唯一的进程ID(PID)

Ⅲ.进程信息存放在哪里？

进程信息(比如进程ID，进程占用内存大小，进程占用CPU时间等等进程相关的信息)都被保存到一个数据结构PCB(Process Control Block，进程控制块)中。

Ⅳ.程序运行过程

Ⅴ.进程的组成

Ⅵ.进程的特征

2.进程的状态转换

Ⅰ.转换过程

Ⅱ.进程的状态

Ⅲ.进程的组织

3.进程控制

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

简而言之，进程控制就是要实现进程的状态转换

Ⅰ.如何实现进程控制？

使用原语进行控制

原语由若干条指令组成的程序段，用来实现特定功能，执行过程中不可被中断，是操作系统核心的组成部分（由一组程序模块构成，非进程 ），常驻内存，通常在管态下执行。

原语具有原子性(可以使用开中断指令和关中断指令这两个特权指令来实现原子性)

Ⅱ.进程控制相关的原语(理解为主,不需要强记)

• 进程的创建

• 进程的终止

• 进程的阻塞和呼唤

进程的阻塞和呼唤原语是成对出现的

• 进程的切换

Ⅲ.程序的执行过程

保存上下文:

进程切换时会把相关的寄存器的数据保存在PCB中,比如PC,IR等寄存器,恢复时再把数据重新写回

4.进程通信

Ⅰ.为什么进程通信需要操作系统来支持?

进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

Ⅱ.进程通信的类型

• 共享存储

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

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

  

  为了避免出错，各个进程对共享空间的访问是互斥的，各个进程可以通过操作系统内核提供的同步互斥工具（如P，V操作）

• 消息传递

  进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

  

  1. 直接消息传递
     
  2. 间接消息传递
     

• 管道通信

  1. “管道”是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的的缓存缓冲区

  2. 本质上是一个循环队列，遵循先进先出的原则

  3. 所以管道是一个半双工通信，某一时间只能实现单向的数据传输，如果要实现双向同时通信，需要创建两个管道。

  4. 当管道写满时，写进程将阻塞，直到读进程把数据读走；同理当管道读空时，读进程将阻塞，直到写进程往管道写入数据。

  5. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程（2014年408真题高教社官方答案）；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux的方案）。

5.信号

注意区分：

信号量（Semaphore）——实现进程间的同步、互斥
信号（Signal）——实现进程间通信（IPC，Inter Process Communication）

Ⅰ.信号是什么？

信号（signal）：用于通知进程某个特定事件已经发生。进程收到一个信号后，对该信号进行处理。

e.g.当运行一个CLI程序时，在键盘上按下Ctrl+C，操作系统会向进程发送一个SIGINT信号，程序默认对SIGINT信号的处理为终止进程

信号一般保存在进程PCB中，由2个N比特的位向量保存（待处理信号，被阻塞信号）

不少于N bit的位向量对应N种信号，blocked位向量也称信号掩码（signal mask）

Ⅱ.什么时候处理信号？

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

Ⅲ.信号怎么作用？

①执行操作系统为此类信号设置的 缺省（默认）信号处理程序（某些信号默认忽略，不作处理）
②执行进程为此类信号设置 用户自定义信号处理程序（自定义信号处理程序将覆盖①）

• 用户进程之间是可以相互发送信号的（有限制），内核进程也可以给用户进程发送信号
• 信号处理程序运行结束后，通常会返回进程的下一条指令继续执行（除非信号处理程序将进程阻塞或终止）
• 一旦处理了某个信号，就将 pending 位重置为 0
• 重复收到的同类信号，将被简单地丢弃（因为仅有 1bit 记录一类待处理信号）
• 当同时收到多个不同类信号时，通常先处理信号更小的信号。
• 部分信号不能被用户自定义，也不能被阻塞，比如Linux的SIGKILL、SIGSTOP信号

Ⅳ.信号与异常的关系

七、线程

1.导论

Ⅰ.为什么引入线程？

原本的计算机只能串行执行不同的程序，后面引入进程来让计算机可以并发执行不同程序，但是随着计算机的发展，进程也不再满足需求，于是引入了线程，让一个进程可以并发执行更多操作。

简单来说，线程其实是进程的套娃

其实线程还能再套娃，出现了协程等东西，比如Go语言的goroutine

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

注意：进程是资源分配的基本单位，线程是调度的基本单位

Ⅱ.线程的优点

线程可以理解为进程mini版

原先的进程并发需要切换不同的进程环境，系统开销很大，引入线程后，只需在同一进程内切换线程环境，系统开销减少

Ⅲ.线程的属性

Ⅳ.线程的实现和多线程模型

线程的实现：

历史背景:早期的操作系统(如:早期Unix)只支持进程，不支持线程。当时的“线程”是由线程库实现的

很多编程语言提供了强大的线程库,可以实现线程的创建、销毁、调度等功能。

内核级线程(Kernel-Level Thread,KLT,又称“内核支持的线程”)，大多数现代操作系统都实现了内核级线程,如 Windows, Linux

1. 内核级线程的管理工作由操作系统内核完成。
2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
3. 操作系统会为每个内核级线程建立相应的 TCB（Thread Control Block，线程控制块），通过 TCB 对线程进行管理。“内核级线程” 就是 “从操作系统内核视角看能看到的线程”
4. 优缺点
   优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
   缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型：

1. 一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

   优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
   缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

2. 多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

   优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
   缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

3. 多对多模型：n 用户及线程映射到 m 个内核级线程（n>=m）。每个用户进程对应 m 个内核级线程。

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

操作系统只能发现内核级线程，所以内核级线程才是处理机分配的单位

用户级线程是 “代码逻辑” 的载体
内核级线程是 “运行机会” 的载体

Ⅴ.线程的状态和转换

Ⅵ.线程的信息

线程控制块

2.处理机调度

一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是“调度”研究的问题。

Ⅰ.调度的三个层次

1. 高级调度（作业调度）

   按一定的原则从外存的作业后备队列中挑选一个作业调入内存,并创建进程。每个作业只调入一次,调出一次。作业调入时会建立PCB,调出时才撤销PCB。

2. 低级调度（进程调度/处理机调度）

   按照某种策略从就绪队列中选取一个进程,将处理机分配给它。

3. 中级调度（内存调度）

   按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

   e.g.内存不够时，可将某些进程的数据调出外存，等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态，被挂起的进程PCB会被组织成挂起队列。

Ⅱ.三种调度的比较

挂起和阻塞的区别：挂起的进程的映像在外存，阻塞的进程的映像在内存

Ⅲ.调度的时机、切换与过程、方式

1. 进程调度的时机

   

2. 进程调度的方式

   抢占式调度和非抢占式调度

   

3. 进程切换的过程

   • 核心概念区分

   类型	定义	关联关系
   狭义进程调度	从就绪队列选一个待运行进程（可是暂停的，也可是全新进程）	选进程的 “决策环节”
   进程切换	一个进程让出处理机 → 另一个进程占用处理机的实际执行过程	执行环节，狭义调度后可能触发
   广义进程调度	包含狭义调度（选进程） + 进程切换（执行切换） 两个完整步骤	完整调度流程

   • 进程切换的具体工作

   进程切换时，内核需完成 “保存旧进程状态 → 恢复新进程状态” 的闭环：

   1. 保存旧进程：将原运行进程的关键数据（程序计数器、程序状态字、数据寄存器等处理机现场信息）存入其 PCB（进程控制块）。
   2. 恢复新进程：从新进程的 PCB 中读取上述信息，恢复到处理机硬件，让新进程继续执行。
   • 关键注意点

   进程切换有性能代价：频繁调度 / 切换会导致系统把大量时间花在 “保存 - 恢复” 流程上，挤占进程实际执行时间，最终降低整体效率。

   简单说，狭义调度是 “选谁运行”，切换是 “实际换人运行”，广义调度是 “选 + 换” 的完整流程；切换要保存 / 恢复进程数据，但太频繁会拖慢系统。

Ⅳ.调度器和闲逛进程

调度器

调度器的作用是决定 “谁获得 CPU 执行权”，但 “调度对象” 取决于系统是否支持内核级线程：

• 无内核级线程 → 调度进程（进程是 CPU 调度的基本单元）。
• 有内核级线程 → 调度内核线程（内核线程直接对应 CPU 执行实体，更细粒度）。

闲逛线程

闲逛进程（idle 进程）是操作系统调度程序的“保底机制”：当系统中**无其他就绪进程 ** 时，调度器会选择运行 idle 进程，避免 CPU 空转。

作用：

• 填充 CPU 空闲：确保 CPU 永远有 “任务” 执行（哪怕是最基础的空转），维持系统调度的连续性。
• 极简运行逻辑：通常执行 “空操作” 或极低开销的指令，减少 CPU 能耗。

Ⅴ.调度的目标(评价指标)

CPU利用率

早期 CPU 造价极高 → 追求 “让 CPU 尽可能多工作”，减少空闲浪费 → 引出 “CPU 利用率” 概念。

CPU忙碌时间占总时间的比例

系统吞吐量

单位时间内完成的作业数量

周转时间

作业提交给系统到作业完成的时间间隔

它包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中,可能发生多次。

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

平均周转时间

带权周转时间

平均带权周转时间

等待时间

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

1. 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间。
2. 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

一个作业总共总共需要被 CPU 服务多久，被 I/O 设备服务多久一般是确定不变的，因此调度算法其实只会影响作业 / 进程的等待时间。当然，与前面指标类似，也有 “平均等待时间” 来评价整体性能。

响应时间

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

3.调度算法

Ⅰ.先来先服务（FCFS，first come first serve）

算法思想：从 “公平” 角度出发，类比生活中排队买东西场景，遵循先到先得逻辑

算法规则：严格按照作业 / 进程到达的先后顺序，依次提供服务

调度应用：

• 作业调度：看作业到达外存后备队列的先后
• 进程调度：看进程到达就绪队列的先后

抢占特性：属于非抢占式算法，一旦开始服务，会持续到完成

优缺点：

• 优点：公平性强，算法实现简单易懂
• 缺点：短作业 / 进程若排在长作业 / 进程后，需长时间等待，带权周转时间大，用户体验差，整体对长作业有利、短作业不利（如排队买奶茶，长订单会让后面短订单等很久 ）

饥饿问题：不会导致饥饿，因为按顺序服务，每个作业 / 进程最终都会被处理 ，不过短作业等待久，是 “慢待” 而非 “饿到不处理” 。

Ⅱ.短作业优先（SJF，shortest job first）

算法思想：

• 最少平均等待时间
• 最少平均周转时间
• 最少平均带权周转时间

算法规则：核心逻辑：“短者优先” ，优先调度要求服务时间最短的作业 / 进程，让短任务快速执行，减少整体等待时长

调度应用：

• 作业调度：选后备队列中服务时间最短的作业
• 进程调度：选就绪队列中运行时间最短的进程（此时叫 SPF ），灵活适配两种调度场景

抢占特性：

• 基础版（SJF/SPF ）：非抢占式，一旦开始执行，会运行到结束或因 I/O 等主动放弃 CPU
• 抢占式版本（SRTN ）：若新到达的作业 / 进程服务时间更短，可抢占当前 CPU ，优先执行自身

优缺点：

饥饿问题：会导致饥饿！若持续有短作业 / 进程到达，长作业 / 进程可能长期排不上队，陷入 “饥饿”；极端情况（一直没机会执行），甚至会演变成 “饿死” ，彻底无法推进。

Ⅲ.高响应比优先（HRRN，highest response ratio next）

算法思想：“平衡公平与效率”：既考虑作业 / 进程的等待时间（体现公平，避免长任务一直等），又兼顾要求服务时间（类似短作业优先，让短任务快执行 ），试图调和 FCFS 和 SJF 的优缺点

算法规则：

• 核心逻辑：每次调度时，先为每个作业 / 进程计算 “响应比”，选响应比最高的执行
• 响应比公式：
  

调度应用：通用性强：既可用在作业调度（选外存后备队列的作业），也可用在进程调度（选就绪队列的进程）

抢占特性：

​ 非抢占式：只有当前作业 / 进程主动放弃 CPU（比如完成、阻塞）时，才会触发调度，重新计算响应比选 新任务

优缺点：

饥饿问题：不会导致饥饿！长作业的响应比随等待时间增长而增大，迟早会被调度，从机制上避免了 “饿死” 风险

Ⅳ.时间片轮转调度算法（RR, Round-Robin）

算法思想：
模拟现实生活的 “公平分配” 场景（如会议发言计时器），通过强制分配 CPU 时间片实现多任务轮流执行，解决 FCFS 对短任务不友好的问题。

算法规则：

1. 核心逻辑：
   • 将 CPU 时间划分为固定长度的时间片（Time Quantum）
   • 就绪队列按 FCFS 排序，队首进程获得一个时间片
   • 时间片用完时，若进程未完成，则被抢占并重新加入队尾等待
   • 若进程在时间片结束前阻塞或完成，立即触发调度
2. 时间片选择原则：

• 过长（如 > 最大进程运行时间）：退化为 FCFS
• 过短（如 1ms）：频繁进程切换，系统开销剧增
• 最佳实践：通常设为 20ms ~ 100ms

调度应用：
仅适用于进程调度（因作业无 “中断-恢复” 概念），是现代操作系统的基础调度算法。

抢占特性：
强抢占式！由时钟中断强制触发时间片结束，无论进程是否主动释放 CPU。

优缺点：

饥饿问题：
不会导致饥饿！每个进程固定获得时间片，最终必然被执行。但长任务完成时间显著增长（需多次执行-等待循环）。

Ⅴ.优先级调度算法（PSA, Priority Scheduling）

算法思想：
模拟现实中的 “VIP 优先” 场景（如机场头等舱通道），根据任务重要性动态分配资源。

算法规则：

1. 核心逻辑：

• 为每个作业/进程分配优先级（Priority Number）
• 调度时选择优先级最高的任务执行
• 优先级通常为整数，可自定义规则（如数值越小优先级越高）

2. 优先级类型：

• 静态优先级：创建时确定，终身不变（基于进程类型、内存需求等）
• 动态优先级：运行时动态调整（基于等待时间、执行历史等）

调度应用：
通用性强，​​既可用于作业调度，也可用于进程调度​​（如实时系统）。

抢占特性：

• 非抢占式：进程运行到结束才触发调度
• 抢占式（更常见）：当更高优先级任务到达时，立即抢占当前进程

优缺点：

饥饿问题：
会导致饥饿！持续存在高优先级任务时，低优先级任务可能永远不被执行（静态优先级尤其严重）。

解决方案：

• 老化（Aging）机制：随等待时间增加逐步提升优先级（如每等待 5 分钟优先级+1）

Ⅵ.多级反馈队列调度算法（MFQ, Multilevel Feedback Queue）

算法思想：
模拟现实中的 “多级服务通道”（如银行普通窗⼝ vs VIP 窗⼝），通过多队列+动态反馈平衡响应速度与吞吐量。

算法规则：

1. 队列结构：

• 创建多个独立就绪队列，每个队列赋予不同优先级和时间片
• 队列优先级：从上到下逐级降低（如 Q0 > Q1 > Q2）
• 时间片大小：从上到下逐级增大（如 Q0: 8ms, Q1: 16ms, Q2: 32ms）

2. 调度流程：

• 新进程加入：放入最高优先级队列（Q0）队尾
• 队列内调度：每个队列内采用 RR 算法
• 时间片用完处理：
  • 若在 Q_i 未完成，降级到 Q_{i+1} 队尾（优先级↓，时间片↑）
  • 在最低队列循环执行直到完成
• 阻塞后恢复：返回原队列队尾

调度应用：
主要应用于​​进程调度​​，是 UNIX、Linux 等系统的​​默认调度算法​​。

抢占特性：
​​强抢占式​​！当高优先级队列有新进程到达，或当前进程时间片用完，立即触发抢占。

优缺点：

饥饿问题：
理论不会饥饿，实际可能导致饥饿！最低优先级队列采用 RR 或 FCFS 保证最终执行。但长任务需经历多次降级，完成时间较长。

Ⅶ.各算法对比：

补充：

4.多处理机调度算法

Ⅰ.公共就绪队列（Shared Ready Queue）

核心机制：
所有CPU共享同一个位于内核区的就绪进程队列，而非每个CPU拥有独立队列。

工作流程

1. 进程选择：
   • 任一CPU空闲时，运行调度程序，从公共队列中选取优先级最高的就绪进程（如CPU1选P1，CPU4选P4）。
2. 互斥访问：
   • CPU访问公共队列前需上锁，确保多CPU操作时的数据一致性。

优点

• 天然负载均衡：
  所有CPU从同一队列取任务，繁忙CPU和空闲CPU的任务量自动均衡（如图中16个进程由多CPU共同处理）。

缺点

• 处理机亲和性差（Cache Affinity）：
  • 进程可能被任意CPU执行，频繁切换导致：
    • CPU缓存（Cache）失效，需重复加载数据。
    • 内存访问延迟增加，降低执行效率。

亲和性优化方案

• 软亲和（Soft Affinity）：
  调度程序​​优先分配进程到之前运行过的CPU​​，减少切换频率，提升缓存命中率。

Ⅱ.私有就绪队列

核心机制：
每个CPU独立维护专属就绪队列，进程仅在绑定队列中被调度。

工作流程

1. 初始分配：
   • 新进程创建时，按预设策略（如轮询、负载最低）分配到特定CPU的私有队列（如图中P1分配到CPU1队列）。
2. 本地调度：
   • CPU空闲时仅从自身队列选取优先级最高进程运行（如CPU1调度P1，CPU2调度P2），无全局竞争。
3. 跨队列迁移（可选优化）：
   • 周期性检查负载均衡，将进程从高负载CPU队列迁移至低负载CPU队列。

优点

缺点

七、同步与互斥

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

1.概念

Ⅰ.同步

读进程和写进程并发地运行,由于并发必然导致异步性,因此“写数据”和“读数据”两个操作执行的先后顺序是不确的。而实际应用中,又必须按照“写数据→读数据”的顺序来执行的。如何解决这种异步问题,就是“进程同步”所讨论的内容。

同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

Ⅱ.互斥

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问,必须互斥地进行。互斥,亦称间接制约关系。进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。

为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:

1. 空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;
2. 忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待;
3. 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿);
4. 让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。

2.进程互斥的实现方法

Ⅰ.软件实现方法

1. 单标志法：

   算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

   

   只能按P0→P1→P0→P1→ …… 这样轮流访问。这种必须“轮流访问”带来的问题是,如果此时允许进入临界区的进程是P0,而P0一直不访问临界区,那么虽然此时临界区空闲,但是并不允许P1访问。因此,单标志法存在的主要问题是:违背“空闲让进”原则。

2. 双标志先检查法：

   算法思想:设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿,比如 “flag[0]=ture” 意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区,如果没有,则把自身对应的标志flag[i]设为true,之后开始访问临界区。

   

   当两个进程并发执行时，该方法可能会导致两个进程同时进入临界区，违反了“忙则等待”的原则

3. 双标志后检查法：

   算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法,来避免上述问题。

   

   双标志后检查法虽然解决了“忙则等待”的问题,但是又违背了“空闲让进”和“有限等待”原则,会因各进程都长期无法访问临界资源而产生“饥饿”现象。

4. Peterson算法：

   算法思想:结合双标志法、单标志法的思想。如果双方都争着想进入临界区,那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。

   

   Peterson 算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、有限等待 三个原则,但是依然未遵循让权等待的原则。

   Peterson 算法相较于之前三种软件解决方案来说,是最好的,但依然不够好。

Ⅱ.硬件实现方法

1. 中断屏蔽方法

   利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况)

   

   优点:简单、高效
   缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)

2. TestAndSet指令(TS指令，或者TestAndSetLock指令,TSL指令)

   由硬件实现，逻辑模拟如下：

   

   若刚开始lock是false,则TSL返回的old值为false,while循环条件不满足,直接跳过循环,进入临界区。若刚开始lock是true,则执行TLS后old返回的值为true,while循环条件满足,会一直循环,直到当前访问临界区的进程在退出区进行“解锁”。相比软件实现方法,TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

   优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境

   缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从
   而导致“忙等”。

3. Swap指令(或者Exchange,XCHG指令)

逻辑上来看Swap和TSL并无太大区别,都是先记录下此时临界区是否已经被上锁(记录在old变量上),再将上锁标记lock设置为true,最后检查old,如果old为false则说明之前没有别的进程对临界区上锁,则可跳出循环,进入临界区。

优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。

Ⅲ.互斥锁

1. 作用：解决临界区问题的简单工具，让进程进入临界区时获锁，退出时释放锁，借助 acquire() 获锁、release() 释放锁 。
2. 原理：
   • 有布尔变量 available 标记锁是否可用。
   • acquire() ：若锁可用（available 为真 ），调用成功，且将 available 设为假（表示已被占用 ）；若锁不可用，进程会忙等待（循环判断 available ），直到锁被释放 。
   • release() ：把 available 设为真，释放锁，让其他进程有机会获取 。
   • 关键要求：acquire() 和 release() 得是原子操作，一般靠硬件机制实现，保证操作执行时不被打断 。
3. 缺点：存在忙等待问题。一个进程在临界区时，其他进程想进入得循环调用 acquire() ，若多个进程共享 CPU，会浪费 CPU 周期 。不过在多处理器系统中较适用，因一个线程可在一个处理器等待，不影响其他线程执行 。
4. 关联概念：需连续循环忙等的互斥锁，也叫自旋锁（spin lock），像 TSL 指令、swap 指令、单标志法都属于这类实现方式 。

特性：

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

Ⅳ.信号量

1. 核心作用：用户进程借助操作系统提供的一对原语操作信号量，实现进程互斥、进程同步 。
2. 信号量本质：是一个变量（可为整数或复杂记录型变量 ），用于表示系统中某种资源的数量 。比如系统只有 1 台打印机，就设初值为 1 的信号量，直观体现资源数。
3. 原语特性：
   • 是特殊程序段，执行一气呵成、不可被中断 ，靠关中断 / 开中断指令实现。
   • 解决的问题：软件方案里 “进入区操作无法一气呵成” 的隐患，用原语实现进入区、退出区操作，就能避免问题 。
4. 一对原语（P、V 操作）：
   • 包含 wait(S)（也叫 P 操作，来自荷兰语 proberen ）和 signal(S)（也叫 V 操作，来自荷兰语 verhogen ）原语，可理解为自定义函数，S 是传入的信号量参数 。

整形信号量：

1. 定义：用整数型变量做信号量，代表系统中某种资源的数量，操作仅 3 种（初始化、P 操作、V 操作 ），区别于普通整数变量 。比如 1 台打印机，设 int S = 1 表示可用打印机资源数 。

2. 原语操作：

   • wait原语（P 操作，对应 “进入区” ）：

     • 逻辑：while (S <= 0); 检查资源，不够就循环等待（忙等 ）；够的话 S = S - 1 占用资源 。
     • 优势：“检查 + 上锁” 一气呵成，避免并发、异步问题 。
     • 问题：不满足 “让权等待”，进程会忙等，浪费 CPU 。

   • signal 原语（V 操作，对应 “退出区” ）：执行 S = S + 1 ，释放资源，让其他进程有机会申请 。

3. 进程使用流程：多个进程（如 P0、P1、Pn ）需按 “wait(S)（申请资源 ）→ 临界区（用资源，如打印机 ）→ signal(S)（释放资源 ）” 的顺序，实现对共享资源（打印机 ）的互斥访问，避免冲突 。

记录型信号量：

1. 提出背景：整型信号量存在 “忙等” 缺陷（进程空转浪费 CPU ），因此设计记录型信号量，用记录型数据结构表示，包含剩余资源数和等待队列 。
2. 数据结构定义：

1 2 3 4

typedef struct { int value; // 剩余资源数，类似整型信号量的作用 struct process *L; // 等待队列，存因资源不足阻塞的进程 } semaphore;

1. 核心原语操作：
   • wait 原语（申请资源）：
     • 先执行 S.value-- ，尝试占用资源 。
     • 若 S.value < 0 ，说明资源不够，调用 block(S.L) ：让进程从 “运行态” 变 “阻塞态”，并挂到该信号量的等待队列里，不再忙等，把 CPU 让给其他进程 。
   • signal 原语（释放资源）：
     • 执行 S.value++ ，归还资源 。
     • 若 S.value <= 0 ，说明等待队列里有进程因缺资源阻塞，调用 wakeup(S.L) ：从等待队列唤醒一个进程，让它从 “阻塞态” 变 “就绪态”，重新竞争 CPU 执行 。
2. 作用：通过 “阻塞 - 唤醒” 机制，替代整型信号量的 “忙等”，更合理利用 CPU，实现进程同步与互斥，解决资源竞争问题 。

记录型信号量用结构体存资源数和等待队列，wait 申请资源不够就阻塞进程，signal 释放资源后唤醒等待进程，避免忙等，优化了信号量机制 。

信号量实现进程同步：

信号量机制实现前驱关系

生产——消费者模型实现

读者——写者模型（读写锁的实现）

有读者和写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:

1. 允许多个读者可以同时对文件执行读操作;

2. 只允许一个写者往文件中写信息;

3. 任一写者在完成写操作之前不允许其他读者或写者工作;

4. 写者执行写操作前,应让已有的读者和写者全部退出。

读优先：

写优先(公平竞争)：

3.管程

4.死锁

Ⅰ.什么是死锁？

在并发环境下,各进程因竞争资源而造成的一种互相等待对方手里的资源,导致各进程都阻塞,都无法向前推进的现象,就是“死锁”。发生死锁后若无外力干涉,这些进程都将无法向前推进。

死锁、饥饿、死循环的区别：

Ⅱ.死锁产生的条件

Ⅲ.如何预防死锁

破坏死锁产生的四个必要条件即可打破死锁

1. 破坏互斥条件

   

2. 破坏不剥夺条件

   

3. 破坏请求和保持条件

   

4. 破坏循环等待条件

   

Ⅳ.如何避免死锁

使用银行家算法获取安全序列

银行家算法通过模拟资源分配过程来判断某个请求是否会导致系统进入不安全状态。它像银行放贷一样，在分配资源前先评估这次“贷款”是否会危及系统的安全运行。

假设有 5 个进程 P0~P4，3 种资源 A/B/C：

进程	Allocation	Max	Need
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Available = [3 3 2]

现在 P1 请求 [1 0 2]，我们用银行家算法判断是否可以分配。

检查合法性：

• Need[P1] = [1 2 2]
• Request = [1 0 2] ≤ Need → 是
• Request ≤ Available？[1 0 2] ≤ [3 3 2] → 是

模拟分配后：

• Available = [3-1, 3-0, 2-2] = [2, 3, 0]
• Allocation[P1] = [3, 0, 2]
• Need[P1] = [0, 2, 0]

然后运行安全性算法，检查是否能找到一个进程执行顺序使所有进程都能完成。

若能找出一个安全序列（如 P3→P4→P1→P0→P2），则说明状态安全，允许分配。

Ⅴ.死锁的处理策略与解除

死锁的检测

死锁的解除

八、内存管理

1.内存是什么？

内存（Memory），也叫内存储器，是计算机系统中至关重要的硬件组件，是 CPU 可直接访问、用于快速存取程序和数据的物理载体 ，主要作用是临时存放 CPU 中的运算数据，以及与硬盘等外部存储器交换的数据

内存可存放数据。程序执行前需要先放到内存中才能被CPU处理 —— 缓和CPU与硬盘之间的速度矛盾

2.指令的工作原理

3.指令的装入

Ⅰ.绝对装入

Ⅱ.可重定位装入

Ⅲ.动态重定位装入

补充：程序的链接方式：

4.操作系统对内存管理的职责

5.进程的内存映像

6.连续内存分配与回收

Ⅰ.连续内存分配方式

相关概念：

内部碎片

• 定义：已分配给进程的内存分区中，因分区大小大于实际需求，导致分区内部出现的未被利用的空闲空间。
• 产生场景：常见于固定分区分配（如早期内存管理）、页式虚拟存储系统 。比如页式存储中，内存以 “页” 为单位分配，若进程实际数据小于一页大小，页内剩余空间就成内部碎片 。
• 特点：碎片属于已分配区域，归特定进程 “占有”，但进程用不上，系统也无法直接回收利用，直到进程释放该内存块。

外部碎片

• 定义：未被分配的空闲内存空间，因分散、不连续，无法满足新进程的内存申请需求（即使总空闲量足够）。
• 产生场景：多在可变分区分配（动态分配内存）、段式虚拟存储系统 出现。比如频繁分配、释放内存后，空闲空间被分割成零散小块，夹在已分配区域间，无法整合为连续大块。
• 特点：碎片属于未分配区域，但因地址不连续等，系统无法直接分配给新进程，需借助 “紧凑” 等技术（移动进程、合并空闲块 ）才能利用。

1. 单一连续分配

   

2. 固定分配

   

   

3. 动态分区分配

   动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区,而是在进程装入内存时,根据进程的大小动态地建立分区,并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

   数据结构：

   

   回收空闲空间：程序运行结束后回收空闲的内存空间需要合并相邻的内存分区

Ⅱ.动态分区分配算法

1. 首次适应算法

   算法思想：每次都从低地址开始查找,找到第一个能满足大小的空闲分区。

   如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

   优点：首次适应算法每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更有可能把高地址部分的大分区保留下来。

2. 最佳适应算法

   算法思想：由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即优先使用更小的空闲区。

   如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

   优点：类似于首次适应算法

   缺点：每次都选最小的分区进行分配,会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

3. 最坏适应算法（最大适应算法）

   算法思想：为了解决最佳适应算法的问题 —— 即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。

   如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

   缺点:每次都选最大的分区进行分配,虽然可以让分配后留下的空闲区更大,更可用,但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达,就没有内存分区可用了。

4. 邻进适应算法

   算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。

   如何实现：空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

   缺点：邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用

对比：

7.非连续内存分配与回收

Ⅰ.基本分页存储管理

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

页表占用的空间

注意:页表记录的只是内存块号,而不是内存块的起始地址!
J号内存块的起始地址 = J*内存块大小

如何实现页面地址转换

如何确定一个逻辑地址对应的页号和页面偏移量

逻辑地址如何转换为物理地址

1. 算页号 P 与页内偏移量 W：十进制手算时，(P = A / L)（整除），(W = A % L)（取余 ）；实际计算机运行靠硬件快速拆分逻辑地址二进制，得到页号、页内偏移量。
2. 越界检查：对比页号 P 和页表长度 M ，若(P ≥ M)（页号从 0 开始，(P = M)也越界），触发越界中断；否则继续。
3. 找内存块号：页表项地址 = 页表起始地址 F + 页号 P * 页表项长度 ，取出内容 b，即内存块号 。（需区分：页表长度是页表项总数；页表项长度是单个页表项存储空间；页面大小是单个页面存储空间 ）
4. 算物理地址 E：(E = b * L + W) ，用 E 访存；若内存块号、页内偏移量是二进制，二者拼接即物理地址。

快表

快表，又称联想寄存器(TLB,translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存(TLB不是内存)，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

两级页表

两级页表的地址转换

Ⅱ.基本分段存储管理

分段和分页的对比

页是信息的物理单位。分页的主要目的是为了实现离散分配,提高内存利用率。分页仅仅是系统管
理上的需要,完全是系统行为,对用户是不可见的。

段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的,用户编程时需要显式地给出段名。

页的大小固定且由系统决定。段的长度却不固定,决定于用户编写的程序。

分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

Ⅲ.段页式存储管理

分段和分页存储管理的对比

段页式存储管理地址转换

段表、页表

地址转换和访存

注意：段号和页号是隐含的(由0递增)，实际段表和页表并不包含段号和页号

实际会有快表，快表命中则无需访问段表和页表，直接获取物理地址

8.虚拟内存

Ⅰ.传统内存管理存在的问题：

一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:

1. 作业很大时，不能全部装入内存，导致大作业无法运行；
2. 当大量作业要求运行时,由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。

驻留性:一旦作业被装入内存,就会一直驻留在内存中,直至作业运行结束。事实上,在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

Ⅱ.虚拟内存的概念

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

虚拟内存的特征：

1. 多次性
   • 实现方式：分页/分段装载
   • 优势：减少初始加载负担，按需调入内存
2. 对换性（交换性）
   • 实现机制：页面置换算法（如LRU）
   • 优势：提高内存利用率，支持多道程序运行
3. 虚拟性
   • 关键技术：地址映射（逻辑地址→物理地址）
   • 效果：使系统可用内存量 > 实际物理内存量

Ⅲ.如何实现虚拟内存

Ⅳ.请求分页管理

页表机制

请求分页地址变换过程

9.页面置换算法

缺页中断不一定会发生页面置换，若还有可用的内存空间，则直接放入内存，不需要进行页面置换。

Ⅰ.最佳置换算法（OPT, Optimal Page Replacement Algorithm）

最佳置换算法（OPT）是一种理论上的理想算法，由Belady于1966年提出。它的核心思想是：
​​“当需要置换页面时，选择未来最长时间不会被访问的页面进行替换”​​，从而使得缺页率最低。

由于它需要预知未来的页面访问序列，因此在实际系统中无法实现，通常仅用于理论研究，作为衡量其他置换算法优劣的基准。

算法执行步骤

1. 维护当前内存中的页面集合（驻留集）。

2. 当发生缺页（Page Fault）时：

   • 如果内存中有空闲帧，直接载入新页面。

   • 如果内存已满，检查当前所有驻留页面的

     未来访问情况：

     • 找出未来最长时间不会被访问的页面（或根本不会再被访问的页面）。
     • 将该页面替换出去，载入新页面。

3. 记录缺页次数，用于计算缺页率。

示例

假设：

• 内存容量 = 3 帧
• 页面访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2

缺页次数 = 9 次（共15次访问，缺页率 = 9/15 = 60%）

算法用处：

• 理论最优缺页率，是所有置换算法的性能上限。
• 可用于评估其他算法（如FIFO、LRU）的优劣。

Ⅱ.先进先出置换算法（FIFO, First-In First-Out Page Replacement Algorithm）

FIFO（先进先出）是一种最简单的页面置换算法，其核心思想是：
​​“最早进入内存的页面最先被淘汰”​​，类似于队列的机制。

它假设最早加载的页面未来最不可能被使用，因此优先替换它们。虽然实现简单，但性能较差，可能会引发Belady异常（即增加内存帧数反而导致缺页率上升）。

算法执行步骤

1. 维护一个队列（或链表），记录页面的加载顺序。
2. 当发生缺页（Page Fault）时：
   • 如果内存中有空闲帧，直接载入新页面，并加入队列尾部。
   • 如果内存已满，选择队列头部的页面（最早进入的页面）进行替换，新页面加入队列尾部。
3. 记录缺页次数，用于计算缺页率。

示例

假设：

• 内存容量 = 3 帧
• 页面访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2

缺页次数 = 10 次（共15次访问，缺页率 ≈ 66.7%）

Ⅲ.最近最久未使用置换算法（LRU, Least Recently Used Page Replacement Algorithm）

LRU（最近最久未使用）是一种基于程序局部性原理的高效置换算法，其核心思想是：
​​“淘汰最长时间没有被访问的页面”​​，即优先替换“最旧”的页面。

它假设最近被访问的页面很可能在近期再次被访问，而长期未使用的页面未来也不太可能被使用。LRU是OPT算法的近似实现，性能接近最优，但实现成本较高。

算法执行步骤

1. 维护页面访问历史（通过栈、计数器或链表记录访问顺序）。
2. 当发生缺页（Page Fault）时：
   • 如果内存有空闲帧，直接载入新页面，并更新访问记录。
   • 如果内存已满，选择最久未被访问的页面替换，新页面加入访问记录。
3. 每次访问页面时（无论是否缺页），更新其访问时间戳或位置。

示例

假设：

• 内存容量 = 3 帧
• 页面访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2

缺页次数 = 9 次（共15次访问，缺页率 = 9/15 = 60%）

Ⅳ.时钟置换算法（Clock Page Replacement Algorithm）

时钟置换算法（Clock Algorithm）是 LRU（最近最久未使用）算法的近似实现，也被称为 Second-Chance Algorithm（二次机会算法）。
其核心思想是：
​​“通过一个环形链表（类似时钟指针）和访问位（Reference Bit）来模拟LRU，选择最近未被使用的页面进行替换”​​。

它 不需要精确记录访问时间，而是利用硬件支持的 访问位（R位） 来近似判断页面的使用情况，从而在 较低的开销 下实现接近LRU的性能。

关键数据结构

1. 环形链表（时钟结构）
   • 所有内存中的页面组成一个循环链表，并维护一个 “时钟指针”（当前扫描位置）。
   • 每个页面对应一个 访问位（R位），由硬件自动置位：
     • R=1：该页面最近被访问过（给予“第二次机会”）。
     • R=0：该页面最近未被访问（候选替换）。
2. 修改位（M位，可选）
   • 如果系统支持，还会记录页面是否被修改过（Dirty Bit）：
     • M=1：页面被修改过，置换时需要写回磁盘。
     • M=0：页面未被修改，可直接丢弃。

算法执行步骤

1. 初始化

   • 所有页面的 R位初始化为0，时钟指针指向任意页面。

2. 当发生缺页（Page Fault）时：

   • 扫描时钟指针指向的页面：

     • 如果 R=1：
       给予该页面“第二次机会”，将 ​​R位清零​​，并 ​​移动指针到下一个页面​​。

     • 如果 R=0：

       选择该页面进行替换：

       • 如果 M=1，需先写回磁盘再替换。
       • 如果 M=0，直接替换为新页面。
       • 新页面的 R位设为1，并移动指针到下一个位置。

3. 正常访问页面时（非缺页访问）：

   • 硬件自动将对应页面的 R位置1，表示最近被使用过。

示例

假设：

• 内存容量 = 4 帧，初始为空。
• 访问序列：A, B, C, D, A, B, E, F
• 访问位（R）初始为0，每次访问后R=1。

✅ 优点：

• 实现简单：仅需维护一个环形指针和访问位，硬件开销低。
• 性能接近LRU：通过访问位模拟页面使用频率。
• 避免Belady异常：与FIFO不同，增加内存帧数不会导致缺页率上升。
• 支持脏页优化：优先替换未修改的页面（M=0），减少磁盘I/O。

❌ 缺点：

• 不如纯LRU精确：访问位只能表示“是否被访问过”，无法记录“多久未被访问”。
• 指针扫描可能耗时：最坏情况下需遍历所有页面（如所有R=1时）。

改进版时钟置换算法

10.页面分配

Ⅰ.分配策略

• 固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程配的内存块数)

• 可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

• 可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

可变分配全局置换：只要缺页就给分配新物理块
可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块

Ⅱ.何时调入页面

Ⅲ.抖动现象

1). 定义
抖动（Thrashing）是指操作系统在内存管理中，由于页面调度过于频繁，导致系统资源大量消耗在页面置换（换入/换出）上，而实际进程执行效率显著下降的现象。具体表现为：

• 刚换出的页面马上被重新访问，需立即换入内存。
• 刚换入的页面因内存不足又被迫换出。
  这种反复的“换入→换出”循环会严重拖慢系统性能。

2). 产生原因
核心矛盾是 物理块分配不足：

• 若分配给进程的物理块（内存页框）过少，无法容纳其频繁访问的页面集合（即“工作集”），系统会不断触发缺页中断，引发抖动。
• 但物理块分配过多会降低系统并发度（内存资源浪费），需在两者间平衡。

3). 关键概念：工作集（Working Set）
由计算机科学家 Peter Denning 提出，用于动态评估进程所需的物理块数量：

• 工作集：进程在某段时间内实际活跃访问的页面集合。
• 系统通过监控工作集大小，动态调整分配给进程的物理块数，避免抖动。

Ⅳ.内存映射文件

内存映射文件（Memory-Mapped File, MMF）是一种将磁盘文件直接映射到进程虚拟地址空间的技术，使得文件数据可以像访问内存一样被读写。

• 核心思想：利用操作系统的虚拟内存管理机制，将文件内容映射到进程的地址空间，减少传统文件I/O的开销。
• 典型应用：数据库系统、大型文件处理、进程间通信（IPC）等。

1. 映射过程：
   • 进程调用系统API（如Linux的mmap()或Windows的CreateFileMapping），指定要映射的文件及访问权限（读/写）。
   • 操作系统在进程的虚拟地址空间中分配一段连续地址，并与文件的物理存储建立映射关系（页表项关联）。
   • 实际数据仍在磁盘上，但访问时会通过缺页中断自动加载到物理内存（按需加载）。
2. 数据同步：
   • 修改映射的内存区域时，操作系统会延迟写回磁盘（由脏页机制管理）。
   • 可手动调用msync()（Linux）或FlushViewOfFile()（Windows）强制同步。

优势

• 高性能：

  • 避免了传统read()/write()的系统调用和用户态-内核态数据拷贝（零拷贝技术）。
  • 利用页面缓存，频繁访问的数据驻留内存，加速读写。

• 简化编程：

  • 直接通过指针操作文件，无需维护文件句柄和缓冲区。

• 共享内存：

  • 多个进程可映射同一文件，实现高效进程间通信（IPC）。

九、文件系统

1.文件的逻辑结构

文件逻辑结构主要分为两大类：

1. 无结构文件（流式文件）
2. 有结构文件（记录式文件）

(1) 无结构文件（流式文件）

• 定义：文件是没有内部结构的字节序列，数据是连续的字节流。
• 特点：
  • 适用于文本文件、二进制文件（如源代码、图像、音频）。
  • 操作系统不关心内容，仅按字节读写。
  • 用户程序需自行解析数据（如文本文件按行读取）。
• 访问方式：
  • 顺序访问（从头到尾依次读写）。
  • 随机访问（通过偏移量跳转，如lseek()）。

示例：

• .txt 文件、.mp3 文件、.jpg 文件等。

(2) 有结构文件（记录式文件）

• 定义：文件由若干逻辑记录（Record）组成，记录是相关数据的集合（如数据库的一行）。
• 特点：
  • 适用于数据库、表格数据（如CSV、数据库表）。
  • 记录可定长或变长，需明确分隔方式。
• 常见组织形式：

示例：

• .csv 文件（记录=行，字段=列）、数据库表（如MySQL的行记录）。

顺序文件

索引文件

索引顺序文件

多级索引顺序文件

2.文件目录

文件控制块(FCB)

Ⅰ.单级文件目录结构

Ⅱ.两级目录结构

Ⅲ.多级目录结构（树形目录结构）

Ⅳ.无环图目录结构

Ⅴ.索引节点

3.文件的物理结构

Ⅰ.文件分配方式——连续分配

Ⅱ.链接分配——隐式分配

Ⅲ.链接分配——显式分配

Ⅳ.索引分配

如果索引表太大，一个索引块装不下，则需要使用：

1. 链接方案，一个索引表的最后一项指向下一个索引表
2. 多层索引，一级索引表指向二级索引表
3. 混合索引

索引分配（总结）

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表 —— 建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

若文件太大，索引表项太多，可以采取以下三种方法解决：
①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘 I/O 次数过多，查找效率低下。
②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要 K+1 次读磁盘。
③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

考点：①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；②要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB 中会存有指向顶级索引块的指针，因此可以根据 FCB 读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件 —— 顶级索引块是否已调入内存）

Ⅴ.逻辑地址 VS 物理地址

4.文件存储空间管理

1).基本目标：

• 分配文件数据所需的磁盘块（磁盘空间）。
• 管理空闲磁盘块，避免碎片过多。
• 保证文件读写高效。
• 支持文件的扩展和删除。

2).磁盘空间单位：

通常磁盘空间按“块（Block）”或“扇区（Sector）”划分管理，操作系统按块分配和管理文件空间。

3)空闲空间管理方法

1. 空闲表法（Free Table）

• 使用一个表格记录当前所有空闲磁盘块的编号。
• 分配时从表中取出空闲块；释放时将块号重新插入表中。

优点：

• 操作简单，查找快速。
• 适合空闲块数量较少、连续存储需求强的场景。

缺点：

• 表可能很大，存储开销大。
• 不适合大量小文件频繁增删的场景。

2. 空闲链表法（Free Linked List）

• 空闲块之间通过指针链接成链表。
• 分配时从头部取出一个或多个空闲块；释放时将块插入链表中。

优点：

• 节省内存空间（每个块只需一个指针）。
• 插入删除操作简单。

缺点：

• 查找特定大小的空闲空间效率低。
• 链表操作涉及大量磁盘读写。

3. 位图法（Bitmap / Bit Vector）

• 用一组位（bit）表示磁盘每个块的状态：
  • 0 表示空闲；
  • 1 表示已分配。
• 例如：0010110...。

优点：

• 占用空间小（每个块一个bit）。
• 查找连续空闲块比较方便（可用硬件支持位操作）。
• 适用于大容量磁盘。

缺点：

• 查找空闲块仍需遍历位图。
• 位图通常需放入内存，若磁盘很大，则内存消耗增加。

4. 成组链接法（Grouped Linked List）

• 空闲块分组管理，每组第一个块存储本组所有空闲块号以及下一组首块地址。
• 每次只需加载一组块的信息到内存。

优点：

• 减少对磁盘的频繁访问。
• 每次加载多个空闲块，效率高于普通链表。

缺点：

• 实现复杂。
• 当组内空闲块数量变化大时管理不方便。

对比：

5.文件的基本操作

6.文件共享

文件共享并不是复制文件，而是多个“引用”指向同一个物理数据块。操作系统通过文件系统结构（如 inode）来实现对文件数据的统一管理。

Ⅰ.软链接（符号链接，Symbolic Link / Symlink）

1. 定义：

软链接是一个特殊类型的文件，它保存的是另一个文件的路径名，就像 Windows 的快捷方式一样。

2. 特点：

• 指向文件路径，而不是文件内容。
• 可以跨文件系统挂载点使用（跨磁盘分区）。
• 若目标文件删除或移动，软链接失效（称为“悬挂链接”或“死链接”）。

3. 创建方式（Linux）：

1

ln -s /real/file.txt /path/to/link.txt

4. 示例：

1
2

real.txt → 实际文件
link.txt → 存放字符串 "/path/to/real.txt"

5. 优点：

• 灵活，支持指向目录或跨分区文件。
• 易于实现快捷方式功能。

6. 缺点：

• 一旦目标文件删除，链接就失效。

Ⅱ.硬链接（Hard Link）

1. 定义：

硬链接是文件系统级别的多个目录项（路径名）指向同一个 inode（文件节点），即多个名字共享一个文件内容和 inode。

2. 特点：

• 所有硬链接共享同一个 inode 和数据块。
• 删除其中任一链接不会删除数据，只有最后一个链接被删除后，数据才被释放。
• 不能跨文件系统、不能对目录创建硬链接（防止循环结构）。

3. 创建方式（Linux）：

1

ln /real/file.txt /path/to/hardlink.txt

4. 示例：

1
2

real.txt → inode: 1234
hardlink.txt → inode: 1234

5. 优点：

• 文件数据真正共享。
• 安全稳定，删除原始文件不影响链接。

6. 缺点：

• 不支持跨分区。
• 不适合目录（容易形成环）。

Ⅲ.对比

7.文件保护

8.文件系统的层次结构

9.文件系统的布局

1
2
3

+----------------+----------------+----------------+-----------------+---------------------+
| Boot Block     | Superblock     | Inode Table     | Data Blocks     | Free Space Mgmt     |
+----------------+----------------+----------------+-----------------+---------------------+

1

打开路径 /home/user/doc.txt

1
2
3
4
5

df -h       # 查看文件系统挂载情况
du -sh *    # 查看目录文件大小
ls -i       # 查看文件 inode 号
stat 文件名  # 查看 inode 内容
tune2fs -l /dev/sda1  # 查看 ext 系统超级块信息

10.虚拟文件系统

虚拟文件系统（Virtual File System，简称 VFS）是操作系统文件系统模块中的一个抽象层，它为用户提供了统一的文件访问接口，而屏蔽了底层各种具体文件系统的差异。

十、I/O设备

1.I/O设备基础

Ⅰ.概念：

I/O 设备(input,output) 是指用于在计算机与外部世界（包括人类用户、其他设备、网络等）之间输入或输出数据的设备。

Ⅱ.分类

按功能分类：

按数据传输方式分类：

按速度和访问特性分类：

Ⅲ.I/O 系统的基本结构

一个 I/O 系统包括：

1. 设备本身：硬件设备，如键盘、硬盘。
2. 设备控制器/适配器：连接设备与系统总线的接口，负责控制设备动作。
3. 设备驱动程序（Driver）：操作系统中的软件模块，用于与设备控制器通信。
4. I/O 接口模块：操作系统为用户程序提供统一的调用接口（如 read()、write()）。
5. 缓冲区管理：在内存中设立缓冲区提高数据传输效率。

2.I/O控制器

3.I/O控制方式

I/O（输入/输出）控制方式是指 操作系统如何管理 CPU、内存和外设之间的数据传输过程。由于 I/O 设备速度通常较慢，如果直接由 CPU 处理所有传输，将极大浪费资源，因此操作系统设计了多种高效的控制方式来提升系统性能。

Ⅰ.分类

Ⅱ.程序直接控制方式

原理

• CPU 主动轮询设备状态寄存器，直到设备准备好再进行数据传输。

特点

• CPU 全程参与，无并发能力。
• 实现简单，但效率低。
• CPU 可能会大量空转等待设备响应。

工作流程

1. CPU 发送 I/O 请求
2. 轮询设备状态，检查是否准备好
3. 若准备好，执行数据传输
4. 返回主程序

应用场景

• 早期计算机系统

• 嵌入式系统中对实时性要求不高的场景

Ⅲ.中断驱动方式（Interrupt-Driven I/O）

原理

• CPU 只负责发起 I/O 请求，设备完成后通过“中断信号”通知 CPU 进行处理。

特点

• 减少了 CPU 空转等待，提高了系统利用率。

• 需要中断机制和中断服务例程支持。

• 适用于响应速度要求高的外设（如键盘、鼠标）。

工作流程

1. CPU 发送 I/O 请求
2. 转去处理其他任务
3. 设备准备好 → 触发中断
4. CPU 响应中断，执行 ISR（中断服务程序）
5. 完成后返回原任务

优势

• 提高 CPU 效率

• 支持并发响应多个 I/O 设备（依靠中断向量）

Ⅳ.DMA 方式（Direct Memory Access）

原理

• 引入 DMA 控制器，由其直接控制设备与内存之间的数据传输，不再通过 CPU。

特点

• CPU 仅负责初始化传输参数（内存地址、字节数等）并发出指令。
• 实际传输过程中 CPU 可去执行其他任务。
• 传输完成后，DMA 控制器通过中断通知 CPU。

工作流程

1. CPU 设置 DMA 控制器参数
2. DMA 控制器接管传输，设备与内存直接交互
3. 数据传输完成后，DMA 控制器向 CPU 发中断
4. CPU 执行收尾处理

优势

• 减少 CPU 负担

• 适合 大数据量的高速传输（如硬盘、网卡）

Ⅴ.通道控制方式（Channel I/O）

原理

• 引入一类称为 I/O 通道处理器（Channel Processor） 的专用处理单元，能独立执行 I/O 指令和管理多个设备，负责整个 I/O 操作流程。

特点

• 通道控制器具有处理器能力，可执行一个叫做“通道程序”的 I/O 指令序列。
• 管理多个设备并发工作、自动调度、错误处理等，几乎不需要 CPU 干预。
• 通常用于 大型主机系统（如 IBM 370）。

工作流程

1. CPU 构造通道程序，启动通道
2. 通道控制器执行指令，控制设备
3. 设备和内存之间独立传输
4. 完成后通道通过中断通知 CPU

通道类型（IBM 分类）

Ⅵ.对比

4.I/O软件层次

Ⅰ.用户级 I/O 软件（User-Level I/O Software）

位置： 用户空间
典型代表： 标准库函数（如 C 语言的 fopen, fprintf, scanf）

功能：

• 提供对设备访问的高级接口
• 管理缓冲区、格式化、错误处理等
• 调用系统调用接口完成 I/O 请求

示例代码：

1
2
3

FILE* fp = fopen("test.txt", "r");
fgets(buffer, 100, fp);
fclose(fp);

Ⅱ.设备独立性软件（Device-Independent I/O Software）

位置： 内核空间
功能：

• 实现统一的设备访问接口（抽象设备）
• 文件名到设备的映射
• 缓冲管理、错误报告、保护访问
• 支持设备无关的系统调用：如 read(), write()

举例：

• 将用户对 "/dev/sda" 的读写请求，转换为对块设备的统一操作
• 支持不同设备都可以通过统一接口访问

Ⅲ.设备驱动程序（Device Driver）

位置： 内核空间（模块或内核内置）
作用：

• 实现与特定硬件设备的交互逻辑
• 将设备无关操作转化为设备具体命令
• 通常由设备制造商或 OS 提供

特点：

• 与设备密切相关
• 只与上层接口通信，与下层中断通信
• 适配多种外设（如鼠标驱动、打印机驱动、网卡驱动）

通俗理解：驱动程序是设备的“翻译官”。

Ⅳ.中断处理程序（Interrupt Handler）

位置： 最底层、最靠近硬件
功能：

• 响应设备中断信号
• 保存和恢复进程现场
• 唤醒等待设备的进程
• 通知上层数据已准备好

特点：

• 时间敏感、执行快
• 通常运行在内核态中断上下文
• 极少访问共享资源，防止死锁

5.假脱机技术(Spooling技术)

假脱机（Spooling，Simultaneous Peripheral Operations On-Line） 是一种 缓冲技术，用于将慢速外设的 I/O 操作与用户程序的执行解耦，使得多个用户可以同时提交输出请求，而系统将这些请求排队管理，逐一发送给外设处理。

简单来说，假脱机就是通过在磁盘或内存上建立一个“缓冲区”来暂存打印任务等 I/O 请求，从而避免用户程序因等待外设完成输出而阻塞。

Ⅰ.工作原理

1. 用户提交一个输出请求（如打印文件）。
2. 操作系统将输出数据先存放到磁盘上的一个缓冲区（假脱机队列）。
3. 系统调度一个专门的假脱机程序（Spooler），负责从该缓冲区中读取数据，并按照顺序发送到实际的慢速设备（如打印机）。
4. 用户程序无需等待设备完成输出，可以继续执行其他任务。
5. 假脱机程序独立运行，保证设备持续工作，合理排队多个请求。

Ⅱ.假脱机技术的优点

Ⅲ.假脱机与缓冲区的区别

缓冲区（Buffering） 是临时存放数据以协调生产者和消费者速度差异。

假脱机（Spooling） 是一种特殊的缓冲，通常用磁盘存储，支持多个任务的排队和顺序管理。

假脱机技术是一种 异步I/O处理机制，通过引入专用缓冲区和后台管理程序，将慢速外设操作和用户程序解耦，提高系统吞吐率和资源利用率，尤其适用于打印等输出密集型设备管理。

6.设备分配与回收

设备分配：是指操作系统根据进程请求，将系统中的外部设备分配给进程使用的过程。
设备回收：是指进程使用完设备后，操作系统将设备释放回系统资源池，以供其他进程使用。

Ⅰ.设备的分类（根据分配方式）

Ⅱ.设备分配的目标与原则

目标

• 保证设备的正确使用

• 实现进程间设备使用的有序竞争

• 提高设备利用率

• 防止死锁或饥饿现象

分配原则

1. 请求与释放配对：谁申请谁释放，避免资源泄漏
2. 按需分配：只在需要时分配，释放后立即归还
3. 互斥使用（对独占设备）：防止冲突访问
4. 公平性：使用先进先出（FIFO）等策略避免进程饥饿
5. 可恢复性：发生错误时能恢复资源或重新分配

Ⅲ.设备分配的数据结构

1. 设备表（Device Table）
   • 描述系统中每个设备的状态信息（空闲/占用）
   • 包括设备号、设备类型、状态标志、指向进程的指针等
2. 分配表 / 使用表
   • 记录当前已分配的设备及其拥有者
   • 支持根据进程查找其使用设备
3. 等待队列（Wait Queue）
   • 若设备忙，进程挂起，加入等待队列
   • FIFO 或优先级调度策略

Ⅳ.设备分配方式

Ⅴ、设备请求与释放过程

请求设备（Request()）

1. 进程提出请求，说明设备类型或编号
2. 操作系统检查设备是否空闲
   • 若空闲：立即分配
   • 若忙碌：将进程挂起，加入等待队列
3. 更新设备表和分配表

释放设备（Release()）

1. 进程完成设备使用，调用释放操作
2. 操作系统更新设备状态为空闲
3. 检查等待队列
   • 若有等待进程：唤醒一个并分配设备

Ⅵ.设备回收的几种情况

Ⅶ.防止设备相关的死锁问题

1. 资源有序分配：对资源编号，要求进程按顺序申请
2. 请求时一次性申请所有资源：避免中途阻塞
3. 设置资源等待上限：防止占有多个资源
4. 使用银行家算法：避免不安全状态
5. 强制回收策略：超时或优先级调度时回收设备

7.缓冲区管理

Ⅰ.单缓冲

Ⅱ.双缓冲

Ⅲ.循环缓冲区

Ⅳ.缓冲池

十一、磁盘

1.磁盘的结构

物理结构：

Ⅰ.基本组成

• 盘片(Platter)：圆形磁性材料盘面，通常一个磁盘包含多个盘片
• 磁头(Head)：读写数据的部件，每个盘面有一个磁头
• 磁道(Track)：盘片上的同心圆
• 扇区(Sector)：磁道上划分的弧段，是磁盘最小物理存储单元(通常512B或4KB)
• 柱面(Cylinder)：所有盘面上相同半径的磁道组成的圆柱面

Ⅱ.磁盘访问时间

• 寻道时间(Seek Time)：磁头移动到目标磁道的时间
• 旋转延迟(Rotational Latency)：等待目标扇区旋转到磁头下方的时间
• 传输时间(Transfer Time)：实际读写数据的时间

逻辑结构：

Ⅲ.分区(Partition)

• 将物理磁盘划分为多个逻辑独立的区域
• 每个分区可以安装不同的文件系统
• 分区表记录分区信息(MBR或GPT格式)

Ⅳ.文件系统组织

• 引导块(Boot Block)：存储启动操作系统的代码
• 超级块(Super Block)：包含文件系统信息(大小、空闲块等)
• 索引节点区(Inode Area)：存储文件元数据(Unix-like系统)
• 数据区(Data Area)：实际存储文件内容

2.磁盘的调度算法

Ⅰ.先来先服务(FCFS - First Come First Serve)

工作原理：

• 按照I/O请求到达的顺序进行处理
• 最简单的调度算法，公平但效率不高

示例：
假设磁头初始位置在53，请求队列：98, 183, 37, 122, 14, 124, 65, 67

移动顺序：53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
总寻道距离 = (98-53)+(183-98)+(183-37)+(122-37)+(122-14)+(124-14)+(124-65)+(67-65) = 640

优缺点：

• 优点：实现简单，公平
• 缺点：平均寻道时间长，效率低

Ⅱ.最短寻道时间优先(SSTF - Shortest Seek Time First)

工作原理：

• 总是选择离当前磁头位置最近的请求
• 类似贪心算法，局部最优选择

示例：
初始位置53，请求队列：98, 183, 37, 122, 14, 124, 65, 67

移动顺序：53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
总寻道距离 = (65-53)+(67-65)+(67-37)+(37-14)+(98-14)+(122-98)+(124-122)+(183-124) = 236

优缺点：

• 优点：比FCFS显著减少寻道时间
• 缺点：可能导致饥饿现象（某些请求长时间得不到服务）

Ⅲ.扫描算法(SCAN - 电梯算法)

工作原理：

• 磁头沿一个方向移动，处理途中所有请求
• 到达磁盘一端后，掉头反向移动
• 类似电梯运行方式

示例：
初始位置53，方向向磁道号增加方向，请求队列：98, 183, 37, 122, 14, 124, 65, 67

移动顺序：53 → 65 → 67 → 98 → 122 → 124 → 183 → (到达末端) → 37 → 14
总寻道距离 = (65-53)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)+(183-37)+(37-14) = 236

优缺点：

• 优点：公平性好，避免了饥饿现象
• 缺点：磁头可能不需要移动到最远端

Ⅳ.循环扫描算法(C-SCAN - Circular SCAN)

工作原理：

• 磁头单向移动处理请求
• 到达磁盘一端后，立即返回到另一端(不处理请求)
• 只处理一个方向上的请求

示例：
初始位置53，方向向磁道号增加方向，请求队列：98, 183, 37, 122, 14, 124, 65, 67

移动顺序：53 → 65 → 67 → 98 → 122 → 124 → 183 → (快速返回到0) → 14 → 37
总寻道距离 = (65-53)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)+(183-0)+(14-0)+(37-14) = 382

优缺点：

• 优点：为请求提供更均匀的等待时间
• 缺点：磁头移动距离可能比SCAN更长

Ⅴ.LOOK调度算法

工作原理：

• 磁头沿一个方向移动，处理途中所有请求
• 当该方向上没有更多请求时，立即掉头反向移动（而不是像SCAN那样移动到磁盘末端）
• 因此称为”LOOK” - 它会先”查看”前方是否还有请求

示例：

假设条件：

• 磁头初始位置：53
• 移动方向：初始向磁道号增加方向
• 请求队列：98, 183, 37, 122, 14, 124, 65, 67

调度过程：

1. 磁头从53开始，向增加方向移动
2. 处理路径上的请求：65 → 67 → 98 → 122 → 124
3. 到达124后，”查看”前方没有更高编号的待处理请求（183在更远处，但当前方向没有请求在124和183之间）
4. 立即掉头向减少方向移动
5. 处理路径上的请求：67(已处理) → 37 → 14

完整移动顺序：
53 → 65 → 67 → 98 → 122 → 124 → (掉头) → 37 → 14

寻道距离计算：
(65-53) + (67-65) + (98-67) + (122-98) + (124-122) + (124-37) + (37-14) = 12 + 2 + 31 + 24 + 2 + 87 + 23 = ​​181​

优点：

1. 比SCAN算法减少了不必要的磁头移动
2. 保持了SCAN的公平性特点
3. 平均响应时间优于SCAN
4. 不会导致饥饿现象

缺点：

1. 实现比FCFS和SSTF稍复杂
2. 需要维护请求队列的信息
3. 在极端负载情况下性能提升有限

3.减少磁盘延迟的方法

磁盘准备需要时间，交替编号是为了留给磁头准备，减少转到了但未准备好从而需要转动两圈的情况

4.磁盘管理

5.固态硬盘SSD