计算机系统概述

操作系统概念

  • OS是计算机系统最基础的系统软件，管理软硬件资源、控制程序执行，改善人机界面，合理组织计算机工作流程，为用户使用计算机提供良好运行环境
  • OS是计算机系统的公共软件基础设施，所有应用程序共用OS服务，且OS内核是反应式reactive机制(中断驱动的)

操作系统类型

从操作控制方式来看

批处理系统主要解决效率问题，分时系统主要解决多用户交互问题，实时系统主要解决响应时间问题。

  • 批处理操作系统
    • 用户将作业交给系统操作员，系统操作员将许多用户的作业组成一批作业，之后输入到计算机中，在系统中形成一个自动转接的连续的作业流，然后启动操作系统，系统自动、依次执行每个作业。最后由操作员将作业结果交给用户
    • 成批处理作业
    • 作业控制语言与作业说明书
    • 脱机工作方式
    • 追求系统效率与吞吐量
  • 分时操作系统
    • 一台主机连接了若干个终端，每个终端有一个用户在使用。用户交互式地向系统提出命令请求，系统接受每个用户的命令，采用时间片轮转方式处理服务请求，并通过交互方式在终端上向用户显示结果。用户根据上步结果发出下道命。分时操作系统将CPU的时间划分成若干个片段，称为时间片。操作系统以时间片为单位，轮流为每个终端用户服务。每个用户轮流使用一个时间片而使每个用户并不感到有别的用户存在。分时系统具有多路性、交互性、“独占”性和及时性的特征。多路性指，伺时有多个用户使用一台计算机，宏观上看是多个人同时使用一个CPU，微观上是多个人在不同时刻轮流使用CPU。交互性是指，用户根据系统响应结果进一步提出新请求(用户直接干预每一步)。“独占”性是指，用户感觉不到计算机为其他人服务，就像整个系统为他所独占。及时性指，系统对用户提出的请求及时响应
    • 用户通过终端直接控制程序执行
    • 交互式工作方式
    • 交互型、友善型、快速相应
    • 今天最常见的计算机操作方式
  • 实时操作系统
    • 使计算机能及时响应外部事件的请求在规定的严格时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致地工作的操作系统。实时操作系统要追求的目标是：对外部请求在严格时间范围内做出反应，有高可靠性和完整性
    • 事件驱动，有较高时间要求
    • 实时操作系统的分类
      • 过程控制系统
      • 信息查询系统
      • 事务处理系统
    • 过程控制系统的处理步骤：数据采集、加工处理、操作控制、反馈处理

从操作系统的运行方式看，可以把它分成：联机模型、脱机模型和实时模型。

  • 联机模型：用户直接与计算机系统交互，命令行界面或图形界面，用户输入，系统即时响应。
  • 脱机模型：用户不直接与计算机交互，提交作业后由系统自动处理，如早期批处理系统。
  • 实时模型：系统能及时响应外部事件，在规定时间内完成任务，如工业控制、航空系统。

系统调用

image-20250603164026923

处理器管理

中断、异常与系统异常

  • 狭义的中断指来源于处理器外的中断事件，即与当前运行指令无关的中断事件，如I/O中断、时钟中断、外部信号中断等
  • 异常指运行指令引起的中断事件，如地址异常、算术异常、处理器硬件故障等
  • 系统异常指执行陷入指令而触发系统调用引起的中断事件，如请求设备、请求I/O、创建进程等

进程印象

进程映像 Process Image

  • 某一时刻进程的内容及其执行状态集合：
    • 进程控制块(PCB):保存进程的标识信息、状态信息和控制信息
    • 进程程序块：进程执行的程序空间
    • 进程数据块：进程处理的数据空间，包括数据、处理函数的用户栈和可修改的程序
    • 核心栈：进程在内核模式下运行时使用的堆栈，中断或系统调用使用

image-20250609225614162

中断驱动操作系统的核心证据（结合状态转换）

1. 运行态 → 等待态（转换①）：由“同步中断”触发

  • 触发事件：进程在运行态主动执行系统调用（如 read(), write(), wait()）或发生异常（如访问无效内存）。
  • 中断类型：系统调用/异常（陷阱/故障）。
  • 中断作用：
    • 强制 CPU 从用户态陷入内核态。
    • 操作系统接管控制权，检查请求或错误。
    • 将进程状态从 运行态 改为 等待态（因为需要等待 I/O 完成或资源可用）。
    • 调度器被触发：选择另一个就绪态进程投入运行。
  • 为何是中断驱动：没有进程的主动请求（系统调用）或硬件/软件错误（异常），操作系统无法知道何时需要阻塞该进程。中断是状态转换的唯一触发器。

2. 等待态 → 就绪态（转换②）：由“异步中断”触发

  • 触发事件：进程等待的外部事件完成（如磁盘 I/O 完成、网络数据到达、定时器超时、信号量可用）。
  • 中断类型：硬件中断（设备完成通知） 或 软件中断（内核事件通知）。
  • 中断作用：
    • 设备控制器或内核发出中断信号。
    • 中断处理程序识别事件来源（如哪个磁盘完成了哪个 I/O 请求）。
    • 找到等待该事件的阻塞态进程。
    • 将其状态从 等待态 改为 就绪态（资源已满足，可被调度）。
  • 为何是中断驱动 & 关键约束解释：
    • 阻塞态进程自身无法主动唤醒自己（它不在 CPU 上运行）。
    • 必须依赖外部事件完成时产生的中断，由操作系统将其移回就绪队列。
    • 这解释了图中 “不可能有等待态→运行态的跳转” 的约束——唤醒必须经过 等待态 → 就绪态 → 运行态 的路径，而 等待态 → 就绪态 这一步只能由中断驱动。

3. 运行态 → 就绪态（转换④）：由“时钟中断”或“高优先级中断”触发

  • 触发事件：
    • (a) 时间片耗尽：进程已用完分配给它的 CPU 时间。
    • (b) 更高优先级进程就绪：一个更高优先级的进程从等待态变为就绪态（由中断触发）。
  • 中断类型：
    • (a) 时钟中断 (Timer Interrupt)：周期性硬件中断。
    • (b) 硬件中断/软件中断：通常是触发另一个进程从等待态→就绪态的那个中断，该中断处理程序随后可能发现更高优先级进程就绪。
  • 中断作用：
    • 在中断处理流程中，操作系统检查当前运行进程：
      • 若时间片用完，将其状态从 运行态 改为 就绪态。
      • 若有更高优先级进程就绪，抢占当前进程，将其状态改为 就绪态。
    • 调度器被触发：选择下一个进程（可能是原进程或新进程）投入运行。
  • 为何是中断驱动：运行态进程不会主动放弃 CPU（除非它自己阻塞）。操作系统必须依赖外部中断（尤其是周期性的时钟中断）才能强制收回 CPU 控制权，实现公平调度和抢占。

4. 就绪态 → 运行态（转换③）：在“中断处理路径”中由调度器触发

  • 触发事件：CPU 空闲（即没有进程在运行态），或发生了抢占（转换④）。
  • 如何发生：
    • 当操作系统在处理任何中断（系统调用、异常、时钟中断、设备中断）后，如果导致当前运行进程离开运行态（变为就绪态或等待态），或者中断唤醒了某个就绪态进程，调度器就会在中断返回路径中被调用。
    • 调度器从就绪队列中选择最高优先级的进程。
    • 将其状态从 就绪态 改为 运行态，并恢复其上下文执行。
  • 为何是中断驱动：
    • 调度决策几乎总是发生在中断处理上下文中（系统调用返回前、时钟中断处理中、I/O 中断处理后）。
    • 没有中断的发生，操作系统就没有机会运行调度器来切换进程。
    • 这解释了图中 “不可能有就绪态向等待态的跳转” 的约束——进程进入等待态必须主动请求或发生异常（即转换①，发生在运行态），就绪态进程尚未运行，不可能发出此类请求。

image-20250609213209530

经典五状态进程模型

image-20250514013636840

七状态

在这里插入图片描述

画多级反馈队列的模型图、阐述多级反馈的原理，比RR的优点、缺陷、以及改进方法

image-20250609230108078

原理

  • 建立多个不同优先级的就绪进程队列

  • 多个就绪进程队列之间按照优先数调度

  • 高优先级的就绪进程，分配的时间片短

  • 单个就绪进程队列中的进程的优先数和时间片相同，按照先来先服务算法调度

与纯轮转（RR）调度算法相比的优点

  1. 更好的响应时间： 这是 MLFQ 最显著的优点。交互式进程（短作业）会被优先执行（在高优先级队列的小时间片 RR 下），用户感觉系统更“灵敏”。纯 RR 对所有进程一视同仁，长作业会阻塞短作业的快速响应。
  2. 更好的短作业周转时间： 短作业能快速在高优先级队列完成，周转时间接近 SJF。纯 RR 中，短作业需要和长作业一样排队轮转多次。
  3. 适应性/区分对待不同进程： MLFQ 能自动识别并优待短作业和 I/O 密集型（交互式）作业，惩罚长时间占用 CPU 的作业。纯 RR 对所有进程行为无差别。
  4. 减少长作业上下文切换开销 (在低优先级队列)： 沉降到低优先级队列的长作业，运行更大的时间片（或 FCFS），减少了不必要的上下文切换次数。纯 RR 使用单一小时间片，长作业会导致大量上下文切换。
  5. 综合性能更好： 通过优先级和反馈机制，MLFQ 在吞吐量、周转时间、响应时间等指标上通常能取得比单一 RR 更好的平衡和整体性能，更接近实际系统的需求。

多级反馈队列的缺陷

  1. 参数配置复杂且关键：
    • 队列数量： 设置多少级队列？
    • 各级时间片大小： 每级的时间片取多大？Q0 太小会导致过多上下文切换；太大则损害响应时间。
    • 升级频率： 多久将所有进程提升一次优先级？太频繁，长作业会抢占太多资源，损害短作业性能；太不频繁，长作业可能饥饿。
    • 降级策略： 用完一个时间片降一级？还是连续用完多个才降？
    • I/O后入队策略： 进程因 I/O 阻塞后唤醒，是放回原队列？还是提升到更高队列？这极大影响 I/O 密集型进程的响应速度。没有放之四海而皆准的最优配置。
  2. 存在进程“欺骗”调度器的可能性 (Gaming the Scheduler)：
    • 一个 CPU 密集型进程可以在其时间片用完前（例如在 99% 的时候）故意发起一个极短的 I/O 操作（例如写入一个字节到虚拟设备），然后立即唤醒。这样它看起来像一个 I/O 密集型进程，可能被放回或提升到高优先级队列，从而获得远超其公平份额的 CPU 时间。
  3. 长作业的响应时间波动： 长作业大部分时间在低优先级队列，响应时间较差。虽然周期性提升能保证它最终运行，但用户交互体验可能不佳（比如在低优先级时运行一个后台编译任务，前台编辑器会卡顿）。
  4. 实现复杂度： 比纯 RR 或 FCFS 复杂得多，需要维护多个队列、管理优先级升降逻辑、计时等。

改进方法

针对上述缺陷，研究者提出了多种改进方案：

  1. 更智能的时间片分配与降级策略：
    • 基于历史预测： 记录进程过去使用 CPU 时间片的历史（例如指数平均），预测其下一个 CPU 突发的长度，据此动态调整其初始进入的队列或分配的时间片大小。
    • 更精细的降级： 不是用完一次时间片就降一级，而是根据进程连续用完时间片的次数或累计使用 CPU 时间来决定降级速度。例如，一个进程连续用完 3 个 Q0 的时间片才被降到 Q1。
  2. 优化优先级提升（防饥饿）机制：
    • 基于等待时间提升： 不再简单地周期性全局提升所有进程，而是跟踪每个进程在低优先级队列中的等待时间。如果一个进程在低优先级队列等待了“过长”时间（超过某个阈值），则单独提升该进程的优先级（一级或直接到最高级）。这更精确，避免了不必要的全局提升对高优先级短作业的干扰。Solaris 的 TS/IA 调度器使用了类似思想。
    • 区分提升： 只提升那些在低优先级队列中确实有在等待的进程，忽略正在运行或阻塞的进程。
  3. 防止“欺骗”策略：
    • 记录真实 CPU 使用时间： 调度器维护进程实际消耗的 CPU 时间总量（而不是根据时间片次数判断）。当一个进程从阻塞中唤醒时，根据其累计消耗的 CPU 时间来决定放入哪个队列。累计消耗 CPU 时间长的进程，即使它频繁进行短 I/O，也会被放入较低的队列。这大大增加了“欺骗”的成本和难度。FreeBSD 的 ULE 调度器采用了类似方法。
    • 惩罚频繁短 I/O： 如果检测到一个进程在非常短的时间间隔内反复进行 I/O（可能是在故意放弃 CPU），可以延缓其重新入队的优先级提升幅度或速度。
  4. 区分进程类型 (可选)：
    • 允许用户或管理员给进程设置一个初始的“优先级提示”或“类别”（如“交互式”、“批处理”、“实时”），调度器可以据此决定进程初始进入的队列或调整其升降级的敏感度。但这增加了用户的负担，且与 MLFQ 自适应的初衷略有违背。
  5. 动态调整参数：
    • 系统可以根据整体负载情况（如平均队列长度、CPU 利用率、平均响应时间等）动态调整一些参数（如升级频率、各级时间片大小），以适应不同的工作负载。但这本身也是一个复杂的问题。

设备管理

I/O软件的实现

I/O中断处理程序

  • 进程请求I/O操作时，通常被阻塞
  • 数据传输结束后产生I/O中断
  • CPU响应请求并转入中断处理程序

设备驱动程序

  • 从独立于设备的软件中接收I/O请求
  • 把用户提交的逻辑I/O请求转化为物理I/O操作的启动和执行
  • 监督设备是否正确执行，访问数据缓冲区，进行必要的纠错处理
  • 设备驱动程序的层次
    • 每个设备驱动程序原则只处理一种设备或者一类紧密相关的设备
    • 设备驱动程序可以分层实现

独立于设备的I/O软件

  • 执行适用于所有设备的常用I/O功能，并向用户层软件提供一致性接口；包括：
    • 设备命名：通过路径名寻址设备
    • 设备保护：用户是否有权访问设备
    • 提供与设备无关的数据单位：字符/块
    • 缓冲技术：调整CPU与I/O速度不匹配
    • 分配和状态跟踪：分配设备
    • 错误处理/报告：驱动无法处理的错误

用户空间的I/O软件

  • 库函数：一部分I/O软件可以使用库函数实现，放在操作系统内核之外，运行时与应用程序链接
  • 虚拟设备软件：用一类设备模拟另一类设备的仿真I/O软件

I/O缓冲

目的

  • 解决CPU与设备之间速度不匹配的矛盾
  • 协调逻辑记录大小和物理记录大小不一致的问题
  • 提高CPU和设备的并行性
  • 减少I/O操作对CPU的中断次数
  • 放宽对CPU中断响应时间的要求

文件管理

  • 建立文件
    • 所需参数：文件名、设备类（号）、文件属性及存取控制信息
    • 处理流程：在相应设备上建立一个文件目录项，为文件分配第一个物理块，在活动文件表中申请一个项，登记有关目录信息，并返回一个文件句柄
  • 撤销文件
    • 所需参数：文件名，设备类（号）
    • 处理流程：若文件没有关闭，先关闭文件；若为共享文件，进行联访处理；在目录文件中删去相应目录项；释放文件占用的文件存储空间
  • 打开文件
    • 所需参数：文件名、设备类（号）、打开方式
    • 返回：文件描述符
    • 处理流程：在主存活动文件表中申请一个项，返回一个文件句柄；跟据文件名查找目录文件，把目录信息复制到活动文件表相应栏；按存取控制说明检查访问的合法性；若打开的是共享文件，则应有相应处理
  • 关闭文件
    • 所需参数：文件句柄
    • 处理流程：将活动文件表中该文件的“当前使用用户数”减1;若此值为0,则收回此活动文件表；完成“推迟写”;若活动文件表目内容已被改过，则应先将表目内容写回文件存储器上相应表目中，以使文件目录保持最新状态
  • 读/写文件
    • 所需参数：文件句柄、用户数据区地址、读写的记录或字节个数
    • 处理流程：按文件句柄从活动文件表中找到该文件的目录项信息；根据目录项指出的该文件的逻辑和物理组织方式，把相关逻辑记录转换成物理块
  • 定位文件
    • 所需参数：文件句柄，定位指针
    • 处理流程：根据文件句柄查找活动文件表，权限与状态检查，计算新文件位置，边界校验，更新活动文件表返，回结果

并发程序设计

image-20250610165408491

image-20250610165428109

计算题

多道程序设计

在一台处理机上并发运行多个程序

指让多个程序同时进入计算机的主存储器，交替使用处理器，进行计算

特点：

  • CPU与外部设备充分并行
  • 外部设备之间充分并行
  • 发挥CPU的使用效率
  • 提高单位时间的算题量
  • 但是，单道程序的运算时间会增加

多道程序系统的实现

  • 为进入内存执行的程序建立管理实体：进程
  • OS应能管理与控制进程程序的执行OS协调管理各类资源在进程间的使用
  • 处理器的管理和调度
  • 主存储器的管理和调度
  • 其他资源的管理和调度

多道程序系统的实现要点

  • 如何使用资源：调用操作系统提供的服务例程(如何陷入操作系统)
  • 如何复用CPU:调度程序(在CPU空闲时让其他程序运行)
  • 如何使CPU与I/O设备充分并行：设备控制器与通道(专用的I/O处理器)
  • 如何让正在运行的程序让出CPU:中断(中断正在执行的程序，引入OS处理)

image-20250603171001457

值得注意的是，同一个程序的三个计算过程得严格按顺序来，如上例不能出现先I/O后计算的错误。倘若A结束了I/O要计算，B正在占用CPU，那B得把设备腾出来还给A

CPU调度算法

调度算法

  • FCFS（先来先服务） 非抢占
  • SPN （最短进程优先）非抢占
  • SRT（最短剩余时间优先）抢占
  • HRRF（最高响应比优先） 抢占
  • RR（时间片轮转） 抢占
  • Feedback（多级反馈调度） 抢占//RR + 优先级

FCFS

  • 当某个进程就绪时，都加入就绪队列(ready queue)
  • 当前正在运行的进程停止执行时，选择在就绪队列到存在时间最长的进程运行

image-20250515215300620

  • 一个短进程可能不得不等待很长时间才能获得执行
  • 偏袒计算为主的进程
    • I/O多的进程不得不等待计算为主的进程做完

SPN Shortest Process Next

  • 非抢占式调度
  • 选择所需处理时间最短的进程
  • 短进程将会越过长进程，优先获得调度

image-20250515220041613

问题在于只要持续不断地提供更短的进程，长进程就有可能饿死

SRT Shortest Remaining Time

HRRN Highest Response Ratio Next

image-20250515220418371

image-20250515220431536

RR 时间片轮转 Round-Robin

  • 基于时钟做抢占式调度
  • 以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列中，然后基于FCFS策略选择下一个就绪进程运行

image-20250515220614936

image-20250515220703708

Feedback 多级反馈调度

image-20250515220741868

image-20250515220942412

img

eg

image-20250603172340601

注意题干支持四道程序同时运行

周转时间是作业完成时间减去作业提交时刻，而不是完成时间减去开始执行时间

image-20250603195221517

这里的等待时间=周转时间 - 运行时间

时间片轮转要注意未运行完的进程在用完自己的时间片后要立刻再push进栈

以及倘若在自己的时间片时间用完前就已经完成程序运行，那就立刻释放CPU

image-20250603205902477

image-20250603205930421

image-20250603205947113

注意这里主存是最先适应算法且不允许移动

注意这里的时间片轮转法是简化成共用CPU

死锁避免银行家算法，死锁检测

系统形成死锁的四个必要条件

  • 互斥条件(mutual exclusion):系统中存在临界资源，进程应互斥地使用这些资源
  • 占有和等待条件(hold and wait):进程请求资源得不到满足而等待时，不释放已占有的资源
  • 不剥夺条件(no preemption):已被占用的资源只能由属主释放，不允许被其它进程剥夺
  • 循环等待条件(circular wait):存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程永远等待

image-20250603200658759

Allocation是已分配的

Claim是需要的

Available是系统可用的

CurrentAvail是现在可用的

C~ki~ - A~ki~ = Claim~i~ - Allocation~i~指目前还需资源

CurrentAvail +allocation = CurrentAvail + Allocation

图和表示的内容

连续分配，分区分配：适配算法，伙伴系统

可变分区方式的内存分配

  • 首次适应法：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
  • 最佳适应算法：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。
  • 最坏适应分配算法：要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。
  • 循环首次适应算法：该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头(链首)开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。

image-20250529130418758

伙伴系统

image-20250603203943417

image-20250603204002234

地址转换计算：分页管理方式；分段管理方式。

页表 把主存分成一块一块的页框，把页框放进页里，所以虚拟地址位数决定页表项数

反置页表 物理地址中存虚拟页框，所以物理地址位数决定页表项数

慢表（Page）：页表、段表存放在主存中，收到虚拟地址后要先访问主存，査询页表、段表，进行虚实地址转换

快表（TLB）：提高变换速度→用高速缓冲存储器存放常用的页表项

image-20250603210934141

页式存储管理中的地址

  • 页式存储管理的逻辑地址由页号和单元号组成
    • 页号+单元号
  • 物理地址由页框号和单元号组成
    • 页框号+单元号
  • 地址转换通过查页表完成

image-20250519192140043

image-20250603210954194

页面置换算法 抖动现象 工作集

缺页中断率

  • 假定进程P共n页，系统分配页框数m个
  • P运行中成功访问次数为S,不成功访问次数为F,总访问次数A=S+F
  • 缺页中断率定义为：f=F/A
  • 缺页中断率是衡量存储管理性能和用户编程水平的重要依据

页面调度算法

  • OPT页面调度算法 Optimal Page Replacement
    • 理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页

image-20250519203653762

  • 先进先出FIFO页面调度算法
    • 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页(常驻的除外)

Belady现象：

在分页式虚拟存储器管理中，发生缺页时的置换算法采用FIFO（先进先出）算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

image-20250519203709707

  • 最近最少用LRU页面调度算法
    • 淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到

image-20250519203736942

  • 最不常用LFU页面调度算法
    • 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
  • 时钟CLOCK页面调度算法
    • 采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
    • 队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
    • 使用页引用标志位

image-20250519203802623

局部页面替换算法

  • 局部最佳页面替换算法 滑动窗口

image-20250519204215662

image-20250519204229466

image-20250519204257935

这个工作集向前看，这个区间为闭区间，这个淘汰只要是在我看的区间没有，就立刻淘汰，不一定是得页框放满了

  • 工作集置换算法

image-20250519204346268

image-20250519204402900

image-20250519204416977

image-20250519204427853

这个工作集向后看，这个区间为闭区间，这个淘汰只要是在我看的区间没有，就立刻淘汰，不一定是得页框放满了

image-20250603212613398

image-20250603212633830

磁盘调度算法

  • 先进先出 FIFO

    • 按顺序处理请求
    • 对于所有进程是公平的

  • 优先级

  • 后进先出

    • 把设备资源提供给最近的用户，会导致磁头臂在一个顺序文件中移动时移动得很少，甚至不移动
    • 利用这种局部性可以提高吞吐量，减少队列长度

  • 最短服务时间优先 SSTF Shortest Seek Time First

    • 选择使磁头臂从当前位置开始移动最少的磁盘I/O请求，因此SSTF策略总是选择导致最小寻道时间的请求
    • 总是选择最小寻道时间并不能保证平均寻道时间最小，但是，它的性能比FIFO更好

  • 扫描 SCAN

    • 要求磁头臂仅仅沿一个方向移动，并在途中满足所有为完成的请求，直到它到达这个方向上的最后一个磁道

    • 接着反转服务方向，沿着相反方向扫描，同样按顺序完成所有请求

  • Look 电梯调度算法
    • 要求磁头臂仅仅沿一个方向移动，并在途中满足所有为完成的请求，直到在这个方向上没有其他请求为止
    • 接着反转服务方向，沿着相反方向扫描，同样按顺序完成所有请求

  • 循环扫描 C-SCAN

    • 把扫描限定在一个方向
    • 当访问到沿某个方向的最后一个磁道时，磁头臂返回到磁盘相反方向磁道的末端，并再次开始扫描

  • N-step-SCAN

    • 进程重复请求同一磁道会垄断整个设备，“造成磁头臂的粘性”，采用分布扫描可避免这类问题
    • 把磁盘请求队列分成长度为N的子队列，每一次用SCAN处理一个子队列
    • 在处理一个队列时，新请求必须添加到其他某个队列中
    • 如果在扫描的最后剩下的请求数小于N，则它们全部将在下一次扫描时处理
    • 当N很大时，N-step-SCAN的性能接近SCAN，当N=1时，实际是FIFO

  • FSCAN

    • 使用两个子队列
    • 当开始扫描时，所有请求都在一个队列中，而另一个队列为空
    • 在扫描过程中，所有新到的请求都被放入另一个队列中
    • 因此，对新请求的服务延迟到处理完成所有老请求之后

image-20250603214357787

文件系统的计算

image-20250604113639725

空闲块的管理：位示图

  • 使用若干字节构成一张表，表中每一字位对应一个物理块，字位的次序与块的相对次序一致。字位为“1”表示相应块已占用，字位为“0”状态表示该块空闲
  • 其主要优点是，可以把位示图全部或大部分保存在主存中，再配合现代计算机都具有的位操作指令，可实现高速物理块分配和去配

位示图 磁盘空间的管理

在给文件分配空间时，是以磁盘的盘块为基本单位分配的，必须记录磁盘可用于分配的盘块(即空闲盘块)，以及提供磁盘分配和回收的手段

image-20250516161353367

image-20250603214413220

注意看这里说的以扇区为分配单位

image-20250603214429224

只需要不严谨的求解就好

image-20250603214445366

这个得好好看

PV操作、管程

详细见笔记中专门整理的《PV和管程》

补充：

image-20250603214538344

image-20250603214518681