操作系统小题

填空

第一章 概论

• 计算机系统是由 硬件系统 和 软件系统。
• 操作系统的基本类型主要有 批处理操作系统 、分时操作系统和实时操作系统。
• ⚠️多道程序设计技术 能充分发挥 CPU 与外设并行工作的能力，需要 中断机构 的支持；多道程序设计 特点：多道、宏观上并行、微观上串行。
• 程序 并发执行 与顺序执行相比多了些新的特征：分别是：并发、共享、不确定性（不可再现性、异步性）、失去封闭性
  • 并发执行失去了 封闭性和可再现性
  • ⭐ ⚠️ 并发进程失去封闭性和失去可再现性是指：并发进程共享变量，其执行结果与速度有关---> 并发进程共享系统的资源 看到带有失去想共享、 速度有关
    • 程序具有可再现性：并发进程的执行结果与速度无关
• 并发和共享是操作系统两个最基本的特征
• 操作系统中 不可中断 执行的操作称为：原语
• 分时操作 系统主要特征：及时性、交互性、独立性。分时操作系统是在 用户态 下执行。分时操作系统追求的目标是比较 快速响应用户 。
• 实时操作 系统两个基本特征：及时性和高可靠性
  • 实时系统比分时系统及时性更高
• 批处理操作系统 不允许用户随时干预自己程序的运行
  • 批处理操作系统 必须具有作业控制信息

第二章 进程管理

• 进程的三种基本状态：运行、阻塞、就绪

• ⚠️运行态 -> 阻塞态 (主动)，阻塞态 -> 就绪态 (被动):

• 多个程序同时装入一个计算机系统的主存中并行执行，这个程序设计技术称为：多道程序设计

• ⚠️进程由程序段、数据段、进程控制块（PCB）组成的。其中 进程控制块 是保存进程状态、控制进程转换的 标志，也是 进程存在的唯一标志。进程控制块的初始化工作包括：初始化标识符信息、初始化处理及状态信息、初始化处理机控制信息。

  • 进程 的基本特征：动态、并发 、独立、异步、结构特征。

• ⭐ 进程通信分为高级和低级，其中高级进程通信分为： 共享存储器系统、管道通信系统、消息传递系统 、客户机与服务器系统（大部分情况不用写这个）

• 若引入线程后：进程是拥有资源基本单位、 线程是独立调度基本单位 。

• 若有五个用户进程，则 处于就绪状态下进程最多有五个，最少有 0 个。若 处于用户态（即某用户程序正在运行）则处于就绪状态下的用户进程 最多有四个，最少有 0 个。

• 进程调度解决的是把 cpu 如何有效分配给进程

• ⚠️进程的同步机制遵循 空闲让进 、忙则等待、有限等待、 让权等待

• 系统中 各进程之间的逻辑上的相互制约 具有先后关系 称为 同步。互斥 是指 进程间在使用共享资源方面的约束关系

• 临界资源 的概念是 **一次仅允许一个进程 ** 访问资源，而 临界区 是指 进程中访问 临界资源 的那段 程序代码 。

• 当前信号量若大于 0 表示：可用资源数目（不要看初值）。信号量小于 0 的 绝对值为请求资源被阻塞进程的数目。⭐

• 任何一个进程 进入临界区之前调用 wait 操作，退出临界区应调用 signal 操作

• 有 m 个进程共享同一临界资源，若 使用信号量机制实现对资源的互斥访问，信号量值的变化范围：[-m+1，1]⭐ ----->(是中括号)

• 操作系统中，对信号量 s 的 wait 原语操作定义中，使 进程进入相应等待队列的等待的条件： s < 0

• 当系统采用 资源有效分配 方法 预防死锁，它破坏了产生死锁的必要条件中的 循环等待条件

• 在有 m 个进程的系统中出现死锁，死锁进程的个数 k 应该满足的条件为： 2 <= k <= m（至少需要两个进程互相等待 才能形成 循环等待【死锁】）

• ⚠️某系统有m个同类资源供n个进程共享，若每个进程最多申请k个资源(k>1),采 用银行家算法分配资源，为保证系统不发生死锁，则各进程的最大需求量之和应K<m+n

  • 解析：由公式知 m>=n(k-1)+1---> nk<= m+n-1 --->nk<m+n --->K<m+n

• 一个计算机系统有 6 台打印机，N 个进程争夺使用，每台进程要求 2 台，系统不会发生死锁，则 N 应该满足：N < 6

  • ⚠️n 个进程都需要 k 个资源，至少需要 n(k-1)+1 个资源才不会发生死锁，发生死锁的最大个数为： n(k-1)
  • ⚠️⚠️系统可用资源数为 k，进程数为 N，每个进程最大请求数为 m，只有当k > N(m-1)不会发生死锁，此时 N 满足0 <= N < k/(m-1)【向下取整】 ，不会发生死锁。当k=N(m-1)会发生死锁，此时 k 为最大值。
  • S 台同类设备，N 个并发进程分别需要 a, b, c… 台设备，则不会发生死锁的 k 的最小值为： (a-1)+(b-1)+(c-1)... +1 【要记得+1】

• （1）预防死锁：四个破坏条件之一【⚠️这里互斥条件无法破坏】。（2）避免死锁：银行家算法。 （3）死锁检测的检测与解除：资源分配图化简法。

• 死锁 产生的四个条件： 互斥条件（无法破坏）、不剥夺条件（一次性释放所有资源）、请求并保持条件（一次性申请所有资源）、循环等待条件。

• 产生死锁的根本原因： 系统资源分配不足和进程推进顺序非法

• ⚠️ 寻找某位时刻的工作集：从某时刻开始向前数n个位置（n为窗口大小）注意重复页面，工作集上只写一次

第三章 处理机调度

• 进程调度方式分为： 抢占式和非抢占式。
• 截止时间的保证 是选择 实时调度算法 的重要准则，平均周转时间短 是 批处理系统 中选择 作业调度算法的重要准则。
• 先来先调度算法 只能采用 非抢占式调度方式。时间片轮转 只能 采用抢占调度方式。
• 动态优先权时，随着 进程执行时间的增加，其 优先权降低
• 平均周转时间最短和平均等待时间最短的调度算法是短进程调度算法 ⭐ 。
• 会导致 饥饿现象 的算法为：短进程优先调度算法、优先级调度算法。
• 先来先调度算法对长作业有利，对短作业不利
• 有利于 CPU 繁忙型的作业，而不利于 I/O 繁忙型的作业是先来先调度算法。⭐

第四章 存储器管理

• 采用请求分页式的存储管理系统，地址变换过程中可能会因为 越界、缺页、访问权限错误等原因而产生中断---越界中断、缺页中断

• 存储管理 实现的功能为：主存空间的分配与保护、主存空间的地址重定位（静态重定位、动态重定位）、主存的共享和主存的扩充。

• 分区分配算法中 首次适应算法 倾向于 优先利用内存 中的 中低地址部分空闲分区（按起始地址递增），从而 保留高地址部分的大空闲区。

• 动态重定位 是 在 目标程序执行的过程 ，在 CPU 访问内存之前，由 硬件地址映射机构或重定位寄存器 来 完成指令或数据的相对地址转换为物理地址的过程。

  • 动态重定位是在程序执行时进行重定位，静态重定位是在装入内存时进行重定位⭐

• 分页存储管理把主存储器分成大小相等的许多存储块，与此对应，程序的逻辑地址也分成大小相同的页，页的大小与块的大小相等。

• 分段存储：其逻辑地址通常由两个部分组成：逻辑地址的形式为：(段号, 段内偏移量)。

  • 段首址（基址）+段内偏移量（= 物理块内偏移量） 注：段首址根据段号来得到

• ⚠️在段页式存储管理中，一个进程只有一个段表，用于管理进程的所有段；每个段都有一个独立的页表，用于管理该段内部的页

  • 若某一进程分为 5 个段，则有 1 个段表，5 个页表

• 整体对换技术通常以进程为基本单位。

• ⚠️⚠️将用户源程序变为可在内存中执行的程序通常需要：编译、链接、装入 三个步骤，其中 链接 分为 静态链接、动态链接、运行动态链接；装入分为： 绝对装入、可重定位装入（静态重定位）、动态运行装入（动态重定位）。

  • ⚠️逻辑地址的形成，发生在链接阶段
  • 逻辑地址转换为物理地址，发生在装入阶段

• 可重入程序 是通过 减少对换数量 来 改善系统性能 的。

• 采用 段页式存储管理 时，内存地址结构是 二维 的，存储管理方式中提供 一维地址 结构的是 分页存储管理。

• ⭐ 在内外部碎片中，只有⭐ 分段式存储管理、动态分区分配 会产生 外部碎片，其余 分页式存储管理、固定分区式存储管理、段页式存储管理方式会产生内部碎片。

• 在页表存储管理中，页表的 起始地址 一般存放在 页表寄存器 中⭐ 。

• 页表的作用是实现 页号到物理块号的地址映射。

• 具有对换功能的 OS，把外存分为文件区和对换区。其中 主要目标是提高进程换入换出速度的是对换区 ，采用的是 连续分配 方式------对换区是连续分配，文件区是采取非连续分配⭐ 。

  • 连续分配：单一连续分配、固定分区分配、动态分区分配
  • 非连续分配（离散分配）：分页、分段、段页、请求分页

• 请求分页存储管理：分页请求系统是在 分页系统的基础上 增加了 请求调页功能 和 页面置换功能 所形成的 页式虚拟存储系统 。

• • 请求分页系统中每个页表包含：页号、物理块号、状态位 P、访问位、修改位 M 和外存地址。

• 请求分页存储管理 中，若把 页面尺寸增加一倍 ，在程序顺序执行时， 则一般缺页中断次数为减少 (相反)⭐ 。

• 关于 缓冲技术 中是 以 空间换取时间 的技术

• 可重定位分区 分配的碎片是 内存中容量小、无法利用的小分区

• ⚠️虚拟存储器 的 基本特征 是： 多次性、对换性、虚拟性 :

• 虚拟存储器 受到的限制有 外存的容量 和 指令中表示地址的字长 ，虚拟存储管理策略可以 扩大逻辑内存容量 。

• 具有 虚拟存储 功能的管理方法是 请求分页存储管理 。

• 页面置换中，频繁的页面调度行为称为抖动。

第五章 设备管理与文件管理

• 常用设备分配技术：独占分配、共享分配、虚拟分配； I/O 设备可分为 独占、共享 、虚拟

• 设备分配程序在 分配外部设备 时，先分配 设备 ，再分配 设备控制器 ，最后 分配通道

• 设备管理中引入 缓冲机制 的主要原因是为了：缓和 cpu 和 I/O 设备速度不匹配的矛盾、减少对 cpu 的中断频率和放宽对 cpu 响应时间限制、提高 CPU 和 I/O 设备并行性

• ** 磁盘访问时间 由三部分时间组成：寻道时间、 旋转延迟、及数据块的传输时间。

• 磁盘与主机之间传递数据是以 数据块 为单位

• 磁盘空间管理方法：空闲表法、空闲链表法、位示图法和成组连接法

• ⭐ 文件在磁盘空间分配方法：顺序分配、链接分配、索引分配、混合索引分配

• 利用 SPOOLING 技术 可以将 独占设备改造成可共享的虚拟设备⭐ 。

• 实现 SPOOLING 系统 时必须在磁盘上开辟出称为 输入井 和 输出井 的专门区域，以 存放输入输出信息。

• 为 实现 CPU 与外部设备的并行工作，系统引入了 中断和通道 硬件机制。

• ⚠️常用的 I/O 控制 方式有：程序直接控制方式、中断控制方式、DMA 控制方式 和通道控制(四种)⭐ 。

  • ⚠️磁盘I/O控制主要采用DMA方式，并配合中断方式来处理控制和异常情况
  • 数据交换不经过 CPU 来完成的是：DMA 控制方式与通道控制
  • I/O 控制的主要功能 是解释用户的 I/O 系统调用、设备驱动 和中断处理(三种)⭐ 。

• ⚠️**中断处理程序通常由操作系统提供，是操作系统程序**，由处理硬件设备或软件发出的中断信号，并进行相应的处理。

• 通道 是指专用于负责 输入 ／ 输出工作（I/O）的 处理机 ，通道所执行的程序称为 通道程序 。

• 逻辑设备表(LUT)的主要功能是： 逻辑设备名映射为物理设备名

• 读 ／ 写一次磁盘所需的时间可以分解为 寻道时间 、旋转延迟时间 和数据传输时间 这三部分。

• ⚠️IO 软件层次结构（此顺序为 从上到下）：用户层 IO 软件、设备独立性软件、设备驱动程序、中断处理程序⭐ (四种)

• 一个设备驱动程序可以驱动一种类型的设备⭐

• 基本的 物理存储组织 形式有：连续分配、链接分配(显示链接、隐式链接)、索引分配 ⭐

• 索引文件大体上由 索引区 和 数据区 构成；其中 索引区 一般 按关键字的顺序存放。

• 操作系统实现按名存取进行检索 的 关键 在于解决文件名与 文件存储地址的转换⭐ 。

• 每个索引文件都至少有一张 索引表，其中的 每一个表项应包括能标识该记录的 关键字 和 该记录的存放地址

  • 每个索引文件都必须有一张 索引表，其中 每个登记项用来指出一个逻辑记录的 首地址

• 文件系统的主要目的 是 实现对文件的按名存储⭐

• 文件目录是由文件控制块构成的文件

• 顺序结构不利于文件动态增长，文件采用 直接存储方式且文件大小固定，也宜选择 顺序文件结构

简答

第二章：进程管理

介绍下什么是进程什么是线程，以及它们之间的区别和联系

• 进程:
  • 是系统进行资源分配的基本单位。拥有独立的地址空间和资源。
• 线程:
  • 是程序执行的最小单元，是 CPU 调度和分派的基本单位。
• 区别与联系：
  • 联系： 线程是进程中的一个实体。
  • 区别：
    • 进程拥有资源，线程不拥有 (共享进程资源)。
    • 进程是资源分配的基本单位，线程是 CPU 调度的基本单位。
    • 进程切换开销大，线程切换开销小。
    • 每个进程都有独立的地址空间，而同一进程内的线程共享该进程的地址空间。
  • 引入线程的意义： 提高了并发程度，提升了系统资源利用率和吞吐量。

阐述何为死锁及产生的四个条件及解决死锁方法：

• 死锁 定义：由于系统中存在一些不可剥夺资源，当两个或两个以上的进程占有自身的资源并请求其他资源时，会导致每个进程都无法向前推进，这就是死锁。

• 死锁产生的 四个条件：互斥条件（无法破坏）、不剥夺条件、请求并保持条件、循环等待条件。

• 解决死锁的方法分为：预防死锁、避免死锁、死锁的检测与解除

  • 预防死锁 的四个方法：

  • 破坏互斥条件：某些资源只能被互斥访问，某些情况保护互斥性。（不可行）

  • 破坏不剥夺条件：释放已经占用的资源。

  • 破坏请求并保持条件：一次性申请完所需的全部资源。

  • 破坏循环等待条件：采用顺序资源法，进程进行顺序推荐（资源进行有序分配）。

• 避免死锁：如银行家算法等。

• 死锁的检测与解除：如资源分配图

画出进程状态的转换图，以及状态之间转换所需要的条件。

• 就绪—> 运行：进程被调度后，活得处理机资源
• 运行—> 就绪：时间片用完后，让出处理机，进入到就绪 状态
• 运行—> 阻塞：请求某一资源或等待某一事件发生----是一个主动状态
• 阻塞—> 就绪：等待的事件已发生-------是一个被动的状态

第三章：处理机调度

何谓静态和动态优先权且确定定静态优先权的依据是什么？⭐

静态优先权和动态优先权 是两种 确定进程或任务在系统中优先级的方式，用于调度系统中的任务。

静态优先权是指在系统启动或任务被创建时，优先级被分配并 在任务的生命周期内保持不变。任务的优先级一旦设定，不会 根据系统运行时的状态或任务的行为 进行调整。

静态优先权 通常根据一下几个因素来确定：任务的重要性、任务的周期性、任务的资源需求、任务的响应时间需求来确定；

---

动态优先权是指任务的优先级在其运行过程中可根据系统的状态、任务的行为或其他因素 进行动态调整，这种方式更灵活，能够适应系统 运行时的 需求变化。

动态优先权调整基于一下几个因素：任务的等待时间、任务的剩余执行时间、任务的截止时间、系统的负载状态

背诵：

静态优先权和动态优先权-确定进程或任务的优先级的方式，用于调度系统中的任务

静态 在系统启动或任务被创建时，优先级被分配且在整个任务周期内保持不变，优先级一旦被设定，不会根据系统运行状态和任务行为进行调整

因素：任务的重要性 任务周期性 任务资源需求

动态 任务的优先级在其运行过程中会根据系统运行状态和任务行为等因素进行动态调整 这种方式更灵活 能够适用系统运行的需求变化

因素：任务等待时间、剩余执行时间、系统负载状态、任务截止时间

比较 FCFS 和 SPF 进程调度算法

比较项目	FCFS（先来先调度算法）	SPF（最短进程调度算法）
调度策略	先到先服务，不发生抢占	优先短作业，分为抢占式和非抢占式
平均等待时间	较长	较短（理论上最短）
响应时间	较差	较好，系统交互性好
公平性	高，按到达顺序	较低，长作业会产生饥饿现象
实现复杂度	简单	较复杂，需要知道进程执行时间
适用场景	批处理，负载轻系统	任务执行时间已知的场景

背诵：

fcfs 先来先调度算法—先到先服务 不会发生抢占-有利于长作业不利于短作业-平均等待时间较长-比较公平 -不会发生饥饿现象—实现复杂度简单-适用批处理负载较轻的系统

spf：短作业优先调度算法-分为抢占和非抢占-有利于短作业调度-平均等待时间最短-公平性较低-会发生饥饿现象-实现较复杂-系统交互性好-适用于任务执行时间已知的场景

什么是多级反馈队列调度算法？

多级反馈队列调度算法是一种 基于队列的进程调度方法 ，它使用多个队列来组织进程，并为每个队列分配不同的优先级。这些队列按照不同的优先级排列， 通常较高优先级的队列具有更短的时间片 ， 而较低优先级的队列具有更长的时间片 。

基本思想是，1、如果进程在当前队列内完成了任务，它将被移出队列或者保持在同一级别的队列中。2、如果它未能在当前队列的时间片内完成，会被移到较低优先级的队列中，重新排队等候。3、如果进程在较低优先级队列中长时间没有得到处理，它的优先级可能会被动态提高。

第四章：存储管理

存储管理的主要内容是：

• ① 内存空间的分配和回收
• ② 地址转换
• ③ 内存空间的扩充
• ④ 存储保护

什么是地址重定位?有哪几种地址重定位?（22 年考过）

• ① 根据内存的当前情况，将装入模块装入内存的适当位置。装入时对目标程序中指令和数据的修改过程称为重定位

• ② 分为 动态重定位：是 在目标程序执行的过程，在 CPU 访问内存之前，由 硬件地址映射机构或重定位寄存器 来完成指令或数据的 逻辑地址转换为物理地址的过程。

  • 静态重定位：是在 装入内存时 进行重定位，将程序中所有的逻辑地址（相对地址）映射为物理地址的过程
  • ⭐ 把逻辑地址转化为物理地址的过程称为： 地址重定位

⭐ 分页式、段式、段页式访问内存次数及其过程

• 在页式存储管理中，访问指令或数据时，首先要访问内存中的页表，查找到指令或数据所在页面对应的页表项，然后根据页表项查找访问指令或数据所在的内存页面。需要访问内存 2 次。 若系统中有快表，则在快表命中时，只需要访问内存 1 次 。

• 段式存储管理同理，需要访问内存 2 次。 若系统中有快表，则在快表命中时，只需要访问内存 1 次。

• 段页式存储管理，首先要访问内存中的段表，然后访问内存中的页表，最后访问指令或数据所在的内存页面，需要访问内存 3 次。

• 对于比较复杂的情况，如多级页表，若页表划分为 N 级，则需要访问内存 N+1 次。

请求分页存储管理的主要特点是什么?实现该方案的关键技术是什么?

请求分页存储系统 是在 分页系统的基础上 增加了 请求调页功能 和 页面置换功能 所形成的 页式虚拟存储系统。

过程：它通过调页功能和页面置换功能陆续把即将运行的页面调入内存，同时把暂不运行的页面换出到外村上，为了实现请求调页和页面置换功能，系统必须提供必要的硬件和软件支持

关键技术：页表机制、缺页中断机制、地址变换机制

试叙述页式系统的地址变换步骤(带快表)。⭐ （六步）

• ① 根据逻辑地址计算页号、页内偏移量。

• ② 检查页号合法性

• ③ 查快表 (TL😎

  • 若命中，则查找页号对应的物理页框号即物理块号，直接进行 ⑤
  • 如果快表未命中，则进行 ④ （查慢表）

• ④ 查页表，找到页面存放的物理块号，并将查到的页表项更新到快表中。 （更新快表）

• ⑤ 根据内存块号和块内偏移量（= 页内偏移量）得到物理地址（生成物理地址）

• ⑥ 根据物理地址访问内存单元

背诵：

1 分解逻辑地址 页号、页内偏移----在快表中查页号是否有有对应的物理块号-------若快表未命中，则访问页表查找页号对应的物理快号—将找到的页表项更新到快表中--------使用页框号和页面偏移 d 生产物理地址----使用生成的物理地址访问物理内存

试给出段页式系统的地址变换过程⭐ 。(带有联想存储器)

• ① 由逻辑地址得到段号、页号、页内偏移量
• ② 根据逻辑地址中段号、页号查找快表
  • 若找不到，则进行 ③。
  • 若找到，则进行 ⑦
• ③ 段号与段表寄存器中的段长度比较，检查是否越界
• ④ 由段表始址、段号找到对应段表项
• ⑤ 根据段表中记录的页表长度，检查页号是否越界
• ⑥ 由段表中的页表地址、页号得到查询页表，找到相应页表项
• ⑦ 找到页面存放的内存块号、页内偏移量得到最终的物理地址
• ⑧ 根据物理地址访问内存单元

为实现分页式虚拟存储，页表中至少应含有哪些内容?

• 页表 中至少应包含以下基本内容：**页号、物理块号、 状态位 P、访问字段 A、修改位 M 和外存地址 **。这些信息共同支持了 分页式虚拟存储系统的地址转换、内存管理和访问控制功能。

虚拟存储器的特征是什么?虚拟存储器的容量主要受到哪两方面的限制?

• 特征： 多次性、对换性、虚拟性 、离散性。虚拟内存受指令中表示 地址的字长 和 外存 容量限制

第五章：设备管理与文件管理

⭐🌟文件的目录结构都有哪些，请详细介绍一下每种目录结构的优缺点。。

• 单级目录结构： 实现简单，按名存取；但查找速度慢，不允许重名。

• 两级目录结构： 解决了多用户文件重名问题，可在目录上实现访问限制；但缺乏灵活性，不能分类。

• 树形目录结构： 方便分类，层次清晰，易于管理和保护；但查找文件需按路径逐级访问，影响查询速度。

• 无环图目录结构： 方便实现文件共享；但系统管理复杂。

IO 软件层次结构和各结构作用：⭐

（从上到下）用户层 IO 软件、设备独立性软件、设备驱动程序、中断处理程序

• 用户层 IO 软件：提供系统调用与库函数
• ⚠️设备独立性软件：为用户提供简单、统一的调用接口
• 设备驱动程序：设置设备寄存器，检查设备状态
• 中断处理程序：进行中断处理

有几种 I/O 控制方式？各有何特点?

I/O 控制方式有：程序直接控制方式、中断控制方式、DMA 控制方式、通道控制方式

I/O 控制方式及其优缺点：

• 程序直接控制方式： 硬件要求低但 CPU 利用率极低，仅适用于简单系统。

  • 适用于打印机等低速设备

• 中断控制方式：实现了 CPU 与设备并行工作，但频繁中断会消耗大量 CPU 时间。

  • 适合设备产生随机性，要求设备需要异步处理

• DMA (直接内存访问)方式：仅在传输开始和结束时需要 CPU 介入，大幅减少中断次数。

  • 适合设备：磁盘、固态硬盘、高速设备

• 通道控制方式： 通道是专门的 I/O 处理器，可控制多个设备。实现 CPU、通道、设备三者并行工作，但硬件成本高。

  • 适合设备：复杂，最牛皮的也是成本最高

简述中断处理的过程。

• 保护被中断进程的现场
• 分析中断原因，转入相应的中断处理程序
• 执行相应的中断处理程序，进行中断处理
• 唤醒被阻塞的驱动程序进程 (可选)
• 恢复被中断进程的现场

I/O 中引入缓冲的主要原因是什么?⭐

• 解决 CPU 和 I/O 设备速度不匹配的矛盾。
• 减少 CPU 的 I/O 等待时间。
• 减少对 cpu 的中断频率和放宽对 cpu 响应时间限制
• 提高 CPU 和 I/O 设备并行性

什么是 I/O 通道?为什么要引入通道?

• I/O 通道是指专门负责输入/输出的处理机。
• I/O 通道方式是 DMA 方式的发展，可以进一步减少 CPU 的干预同时，可以实现 CPU、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

I/O 调度的主要任务有哪些?

I/O 调度就是确定一个好的顺序来执行，I/O 请求需要 I/O 调度来改善系统整体性能，使进程之间公平地共享设备访问，减少 I/O 完成所需要的平均等待时间

在 FAT 文件系统中，文件分配表（FAT）有什么作用？

FAT 文件系统中的文件分配表（FAT）负责跟踪和管理文件在磁盘上的存储位置，支持文件的 连续和非连续存储，管理磁盘空间，导航文件的读写操作，并在文件删除时回收磁盘空间。 FAT 表是 FAT 文件系统的核心组件，确保文件数据能够被有效管理和访问。

⚠️SPOOLing 系统的特点是什么?

• ① 提高了 I/O 的速度，缓和了 CPU 和 I/O 设备之间的速度不匹配的矛盾;
• ② 将独占设备改造为共享设备
• ③ 实现了虚拟设备功能。

操作系统应用题

单道多道CPU利用率

单道程序CPU利用率=CPU运行时间/总运行时间（全部相加）=40/80

多道程序CPU利用率=CPU运行时间/并行运行时间=45/80

分析：A在适用CPU或者设备时，B若使用相同设备必须等待，A和B交叉使用

作业调度七种算法

核心计算公式

周转时间：完成时间-到达时间

⚠️等待时间：周转时间-运行时间------短作业平均等待时间最短

带权周转时间：周转时间/服务时间

平均周转时间和平均带权周转时间：取平均值

先来先服务算法(FCFS)

短作业优先算法(SJF)

注：不同到达时间， 先到达的作业优先执行 ，当执行完的时候看其他几个作业是否到达，如果剩下作业都到达按照短作业优先”

非抢占

抢占

• 基于最短剩余时间(SRTN)

注：当 D 执行到第八秒的时候，D 还剩 2 秒要小于 E 服务时间 4 秒故还是先执行完 D 再执行 E

优先级别调度算法

⭐ 高响应比调度算法(HRRN)

响应比 = 1+ 等待时间 / 服务时间

​ ⚠️：带权周转时间：周转时间/服务时间

注：等待时间为调度时间减去到达时间（单位：分钟），先算出第一次调度优先级，当计算第二次调度作业时第二次调度的开始时间要变为第一次调度开始时间再加上最先调度作业的服务时间

（第二次调度时间开始为 10：40，等待时间 = 开始时间 - 到达时间）

时间片轮转调度算法（RR）

不同到达时间

将准备序列调入到cpu是从靠左边开始调，添加到就绪队列是从右边开始添加

解题思路：当不再加入新任务时，即此时时间来到第四秒结束，此时序列为 BDAEC，后一直按照此序列重复下去，若某一作业当满足服务时间后，去除该作业，其他作业继续重复，直到全部满足。

当 q(时间片)为 4 的时候为最大服务时间则不会执行时间片轮转改为先来先服务算法（FCFS）

相同到达时间

解题思路：相同到达时间即一直重复 ABCDE，若某一作业当满足服务时间后，去除该作业，其他作业继续重复，直到全部满足

当 q(时间片)为 4 的时候为最大服务时间则不会执行时间片轮转改为先来先服务算法（FCFS）

最早截止时间算法（EDF）

• 抢占
  • 【实时调度算法之最早截止时间优先调度算法（抢占）】https😕 /www.bilibili.com/video/BV1zD421n7Rs?vd_source = c8b64e308ba0a6999b868fdf4177d69f
• 非抢占
  • 【实时调度算法之最早截止时间优先调度算法（非抢占）】https😕 /www.bilibili.com/video/BV1Tt421E7i3?vd_source = c8b64e308ba0a6999b868fdf4177d69f

注：开始执行时间 > 最早截止时间则该任务不能被调度

⭐ 最低松弛度优先算法(LLF)

⭐ 松弛度=任务必须完成时间（下一次到达开始时间）-任务本身运行时间-当前时间

发生任务切换（抢占）只有两种情况：

• 新任务执行完
• 新到达任务的松弛度为 0 时 则切换此任务
  • 若不为 0 则继续之前上一次未执行完的任务
• 若松弛度相等时，则谁先早来先执行谁

【实时调度算法之最低松弛度优先算法】https😕 /www.bilibili.com/video/BV17M4m1X7MT?vd_source

pv 操作考代码

⭐ 银行家算法

【操作系统银行家算法例题讲解】https😕 /www.bilibili.com/video/BV1gK411x7Ra?vd_source

1. Need 矩阵是怎样的？

• Need = Max - allocation

2. 系统是否处于安全状态？如安全，请给出一个安全序列。

• 建立表格：

  work	allocation	need	work+allocation

• work(available) >= need 满足安全

3. 若从进程 P1 发来一个请求(0,4,2,0)，这个请求能否立刻被满足？如安全，请给出一个安全序列。

• 解：第一步：p2 发出的请求向量 request（），系统按银行家算法进行检查----->（看是否小于等于）

  • request 2()<= need2()

  • request 2()<= available()

• 第二步：系统假定可为 p2 分配资源，并修改 p2进程 available、allocation、need 的值

  • Available = available - request ----> 可用-请求

  • ⚠️Allocation = allocation + request -----> 分配+请求

  • Need = need - request ----> 需要-请求

• 第三步此时再进行安全性检查，并判断

  • 存在安全序列

  • 由于不存在满足需求的进程，所以系统不可以将资源分配给它。

动态分区分配算法（连续分配）

• 首次适应
  • 从头部开始查找，找到第一个能满足大小的空闲分区
• 最佳适应
  • 将空闲分区按容量进行从 小到大排序，选满足的第一个空闲分区
• 最坏适应
  • 将空闲分区按容量进行 从大到小排序，选满足的第一个空闲分区
• 邻近适应（循环首次适应）
  • 从上次查找结束的位置开始检索
  • 算法开销小，但会使高地址的大分区被用完

分区回收？？？？

【【操作系统】【考研真题】2017 年第 25 题【动态分区存储管理】分区分配与回收】https😕 /www.bilibili.com/video/BV1Zd4y127Bd?vd_source=c8b64e308ba0a6999b868fdf4177d69f

【「操作系统题目」动态分区分配和回收算法】https😕 /www.bilibili.com/video/BV1Ap4y167A9?vd_source=c8b64e308ba0a6999b868fdf4177d69f

基本分页存储管理（非连续分配）

⭐ ⭐ 逻辑地址、物理地址转换

• 逻辑地址位数可根据逻辑空间大小来计算，若逻辑空间大小为 2^10B，则逻辑地址位数为 10 位

• 页内偏移地址 = 块内偏移地址

• 页面大小 = 页框大小

  • 页面大小可根据 页内偏移量位 数来计算，**【若页内偏移量为 5 位，则页面大小为 2^5 = 32B】， 页面数量由页号位数决定（这里通过计算算出来的页号位数不一定要完全和总逻辑地址-页内偏移地址得出来的页号位数一样） **

• 页框大小是根据块内偏移量，物理块数量由块号位数决定--------类比页内偏移数量与页号

• 求物理地址

  • 十进制

    • ⚠️用逻辑地址除以页面大小 --> 结果为页号，余数为偏移地址。 （十进制计算）

    • ⭐⭐物理地址 = 块号 * 页面大小+块内偏移地址（页内偏移地址）

  • 十六进制

    • 先将逻辑地址转换为二进制地址，根据页面大小，确定页内偏移位数，从而确定页号位数（16位-页内偏移位数）
    • 根据页号位数和二进制地址将页号转成十进制，找到对应的物理块号
    • 将找到的物理块号转换成二进制和后面的块内偏移地址（同页内偏移地址）拼接起来，再转成十六进制

注：若页号大于题中所给的则会产生越界中断，缺少则会产生缺页中断；高位就从左往右数，低位是从右往左

⚠️⭐ 基本分页中访问有效时间 EAT

访问一个内存（逻辑地址）的平均耗时（ 页面平均访问时间 ），其中：λ 表示查找快表所需时间，a 表示命中率，t 表示访问一次内存所需时间

• 先查快表再查慢表：
  • 一级页表：EAT = a*(t+λ) + (2t+λ)*(1-a)= 2t+λ - t*a
  • 二级页表：EAT = a *(t+λ)+(3t+λ)*(1-a)= 3t+λ - 2t * a
  • n 级页表：EAT = a *(t+λ)+[(n+1)t+λ)]*(1-a)=(n+1)*t+λ - n*a*t
    • 核心：命中是快表时间+一次内存时间，未命中是两次内存时间+一次快表时间
    • 【若要考虑更新快表时间，则上述 λ 均变为 2λ，2λ 变为 3λ】
• 快表和慢表同时查询时间为：
  • 同时查询EAT = (λ+t)* a + (t+t)*(1-a)
    • 核心：命中是快表时间+一次内存时间，未命中是两次内存时间
• 未采用快表查询时间为访问内存两次：t+t

解：

• 若采用先查快表再查慢表方式为：λ = 1，t = 100，a = 90% 则 EAT = 2 * 100 + 1- 100 * 90% = 111us
• 若采用快表和慢表同时查询的方式所需时间为：（1+100）* 0.9 + (100+100)* 0.1 = 110.9us
• 若未采用快表机制则时间为：100+100 = 200us

⭐ 二级页表（多级页表）

多级页表中，各级页表大小不能超过一个页面

• 二级页表大小 = 页面大小 = 块大小
• 页表项个数 = 页面大小 / 页表项大小 = 2^页表项位数
• ⭐ 几级页表个数 = 页号总位数 / 每页页表项位数 （向上取整 => 大于等于）
  • 一级页表中，页表项位数 = 页号位数 ，若是在多级页表中 2^页表项位数 = 页面大小 / 页表项大小

解：逻辑地址空间大小 = 2^16 * 2^10 = 2^26B ，则逻辑地址位数为 26 位。

因为页大小为 2^10B，则页内偏移量位为 10 位。

页表项个数 = 2^10 / 2 = 2^9B，故页表项位数为 9 位即页号位为 9 位。

综上，页目录位 = 26-10-9 = 7 位，故页目录个数为 2^7 = 128 个

解：页面大小为 4KB = 2^12B，则页内偏移量位数为 12 位，则页号位数为 48-12 = 36 位

页表项大小为 B8 = 2^3B，则每个页面页表项个数为 2^12 / 2^3 = 2^9，则页表项位数为 9 位。

故几级页表 = 36 /9 = 4 级 答案选 C

段页式存储管理

按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）

• 对用户：逻辑地址结构划分为段号、段内地址
• 对系统：逻辑地址结构划分划分为段号、页号、页内地址（页内偏移量）三部分组成

其中：段长决定段内地址位数、段号的位数决定了每个进程最多可以分几段、页号的位数决定了每个段最大有多少页，页内偏移量决定了页面的大小、内存块的大小是多少

⚠️ ⚠️请求分页中访问内存的有效时间

（λ 为查找快表的时间，t 为访问内存的时间）

• 被访问页在内存中，且对应的页表项在快表中：EAT = λ + t
• 被访问页在内存中，其对应的页表项不在快表中时，EAT = λ + t + λ + t = 2( λ + t )
• 被访问页不在内存中，假设缺页中断为 s，则 EAT = λ + t + s + λ + t = s + 2( λ + t )
• ⭐ ⭐ 考虑快表的命中率为 a 和缺页率为 f 时，设缺页中断时间为 p，λ 为查找快表的时间，则：

$$\large{ \mathbf{ EAT = λ + at + (1-a)[t+f(p + λ + t ) + (1-f)( λ + t )]}}$$

• ⭐ 如果不考虑命中率，仅考虑缺页率 f，设缺页中断时间为 p ，则 EAT = t + f(p + t) + (1 - f)t

• ⭐ ⭐ 如果不考虑命中率，仅考虑缺页率 f，且考虑页面修改率 a，设缺页中断时间为 Pmiss：EAT =(1−f)⋅t+f⋅(Pmiss+t)

  • 修改的概率为 n，未修改页面处理时间为 T1，修改页面处理时间为 T2 则 Pmiss = [(1-n) ⋅T1+n⋅T2] 完整式子为：

$$\mathbf{EAT =(1−f)⋅t+f⋅ [(n⋅T2+(1-n) ⋅T1)+t]}$$

例 1：不考虑快表和其命中率，考虑置换率

解 式子也可以写成：

$$\pmb{(1-p)*1 + p [(0.7*20+(1-0.7)*8)+1]}$$

页面置换算法（请求分页）

页面失效次数 = 缺页次数为：刚开始新插入元素的列数 + 发生置换的列数

最佳置换算法 OPT（淘汰未来最远出现的）

• 选择的被淘汰页面是以后 永不使用的，或者长时间不再被访问（未来最远出现） 的页面
• 性能最好，但该算法无法实现

⭐ 先进先出置换算法 FIFO

• 1、淘汰在 内存中停留时间最长 的页面 2、实现容易，但性能稍差，而且 belady 异常会发生在算法中 3、没有基于局部性原理
• ⭐ **淘汰最早进入内存页面 ===> 根据装入内存时间 **

⭐ 最久未使用置换算法 LRU（淘汰过去最远的）

• 1、性能最接近 OPT 算法，但需要硬件支持，开销大 2、基于局部性原理
• ⚠️⭐ **淘汰最长时间未被访问 ===> 根据最小的上次访问时间 **

😒 tar:Clock 置换算法

• 某页刚进入内存或发生置换的时候，该页其访问位 置为 1。
• 若需 淘汰 某个页面时，只需 检查访问位是否为 0，若访问位置为 0（最先访问）将此页换出，并将新换新页，访问位 置为 1，同时指针下移。
• 如果 访问位为 1，将其置为 0 不置换新页，指针下移。
• 若 不需要淘汰页面（或者不发生缺页）指针不动，并将该页访问位置为 1

注：若上一次指针所在位置刚好为 1，则下一次淘汰页面时，先将上一次指针所在的访问位置为 0，后指针下移

【Clock 置换算法原理+例题讲解】https😕 /www.bilibili.com/video/BV1LZ421z7vJ?vd_source = c8b64e308ba0a6999b868fdf4177d69f

⭐ 改进型 CLOCK 置换算法

• ⚠️改进型 CLOCK 从上一次的位置开始扫描，首先寻找未被访问和未修改的页面，（读位和修改位都为 0）因此最先淘汰该页面。

  • 增加了修改位 M，未修改为 0，已修改为 1
  

  例题：

⭐ 混合索引分配相关习题

注意：

• 实际占用空间大小 = 文件实际大小+间接索引项大小+地址项数量（一般为 i node 数据结构）（含直接、间接）

• 占用盘块数量为：文件长度/磁盘块大小 + 间接索引块数量（含一级、二级…）

• ⭐ 占用多少盘块、占用多少空间该类题目的解题思路

  • 文件占用多少盘块数：文件总长度 / 每个数据块的大小 记为 a：
  • 每个盘块可以存储多少个盘块号（根据盘块大小以及每个盘块号的大小 两个相除 记为 b）
  • 直接地址项：每个直接地址项可以直接指向一个盘块。因此，n 个直接地址项可以指向 n 个盘块。
  • 一级地址项：使用一个间接索引块，共可记录 a 个盘块
  • 二级地址项：通过一个索引表的索引表来指向多个盘块，此时所需索引块数为：1+ ┍ (a - n -b ) / b ┑ （符号『 为向上取证 ）
  • 总共需要：文件长度/磁盘块大小 + 间接索引块数量 === > a + 1 + 1+ ┍ (a - n -b ) / b ┑

【解答】https😕 /www.bilibili.com/video/BV18P411J7Z1?vd_source

​ 最后将占用的数据块、直接索引指向的数据块、一/二级地址所需要的索引块相加

解答：

⚠️如果问需要访问磁盘次数：取决于访问的数据块在索引结构中的位置，如果访问文件占用数据块在二次间接地址索引中，则需要访问磁盘三次（二级+1），分别是：第一次从二级间接地址中获取索引结点表地址（一级），第二次从索引结点表中获取索引块地址，第三次从索引块中获取所访问的最终文件的地址。

磁盘调度算法

• FCFS：磁头移动顺序为默认顺序
• SSTF：磁头移动顺序为：选择与当前磁头所在磁道距离最近的磁道

---

先进行从大到小排序

---

• ⚠️SCAN（电梯调度算法）：先将磁头当前所在磁道与其他磁头序列进行从大到小排序，根据磁头移动方向选择朝哪边移动，到达尽头后朝反方向移动（已访问的磁头不会再次访问）

• 磁盘磁道是越往里磁盘号越大，如果磁头是从里向外移动即为朝小的方向移动，如果是从外向里即为朝大的方向移动

  • 注：一般昨天若题目中没标明最大最小柱面号，则按照 look 的算法进行计算得出结果

• LOOK：同 SCAN 算法一样，LOOK 算法只需走到该方向上最后一个请求就会转换方向

• ⚠️C-SCAN（循环电梯调度算法）：类似与 SCAN 算法，到磁盘尽头（最小柱面号）后直接返回到磁盘另一端（最大柱面号） （单向移动）

• C-LOOK：同 C-SCAN 算法一样，只需走到该方向上最后一个请求（即请求的尽头）就会跳转到另一端开始位置（序列另一端）