OS
第三部分:内存管理
3.1:内存的基本概念
一、内存的分配和回收
3.2：连续分配方式
指为一个用户程序分配一个连续的内存空间。
1.单一连续分配
- 内存分为系统区和用户区。用户区只装入一道用户程序。
- 优点：简单，无外部碎片。
- 缺点：只能用于单用户单任务系统；存在内部碎片（如果程序小于用户区大小）。
2.固定分区分配
将用户内存空间划分为若干个固定大小的分区。每个分区装入一道作业。
分区大小相等：简单，但缺乏灵活性。
分区大小不等：可以满足不同大小作业的需求。
当作业到来时，选择一个能容纳它且尚未分配的分区。
优点：实现简单，可用于多道程序系统。
缺点：
- 内部碎片：分配给作业的分区可能大于作业实际需求，多余部分无法利用。
- 分区总数固定，限制了并发执行的作业数量。
3.动态分区分配
- 不预先划分分区，在作业装入时，根据作业的实际需求动态地从可用内存中划分一块连续空间。
- 优点：没有内部碎片（理论上，如果按需分配）。
- 缺点：
- 外部碎片：随着内存分配和回收，会产生许多不连续的小空闲区，这些空闲区总和可能很大，但无法满足较大作业的需求。
- 需要复杂的分配算法和空闲区管理。
3.3：动态分区分配的算法
动态分区分配算法 (如何从空闲分区链/表中选择一个分区)：
1.首次适应算法
从空闲分区链首开始查找，选择第一个能满足大小要求的空闲分区。
- 优点：算法开销小，倾向于保留高地址的大空闲区。
- 缺点：低地址部分不断被划分，产生较多小碎片。
2.最佳适应算法
遍历整个空闲分区链，选择能满足要求且大小最小的空闲分区。
- 优点：能最好地满足当前请求，尽量保留大块空闲区。
- 缺点：算法开销大；容易产生许多难以利用的非常小的碎片。
3.最坏适应算法
遍历整个空闲分区链，选择能满足要求且最大的空闲分区，从中分割一部分给作业，剩余部分作为新的空闲分区。
- 优点：减少小碎片的产生，剩余的空闲区较大。
- 缺点：算法开销大；如果大空闲区被分割后，剩余部分不足以容纳大作业，则大作业难以分配。
4.下次适应算法
从上次查找结束的位置开始查找（而不是每次都从头开始），选择第一个能满足大小要求的空闲分区。
- 优点：算法开销介于首次适应和最佳/最坏适应之间；空闲区分布更均匀。
- 缺点：可能导致高地址的大空闲区也被分割。
碎片整理： 为了解决外部碎片问题，可以将内存中的所有作业移动到一端，使所有小空闲区合并成一个大空闲区。
- 优点：可以利用外部碎片。
- 缺点：开销大，需要动态重定位支持，且在整理期间系统性能会下降。
3.4：基本分页存储管理
页、页框:
将用户程序的逻辑地址空间和内存的物理地址空间都划分为大小相同的、固定大小的块。
- CPU(逻辑地址)空间中的块称为 页。
- 内存(物理地址)空间中的块称为 页框 或 物理块。
页和页框的大小通常是 2 的幂（如 4KB, 8KB）。
(为了能把进程信息、数据放到内存当中，操作系统一般也会把逻辑地址空间分成与页框相等的块 -> 也就是页，也就是说，进程的页面与内存的页框有一一对应的关系,并且这些页可以离散地存放在内存中不相邻的页框中。)
操作系统以页框为单位为各个进程分配内存空间
原理：
- 操作系统为每个进程维护一个页表，记录逻辑页号到物理页框号的映射关系。
- 页表通常存放在内存中且通常连续存放。（通常存在PCB当中）
- 每个页表由“页号(进程)”和“块号(内存)”组成，记录着进程页面和实际存放的内存块(或者叫页框)之间的映射关系
注意：一个页号和块号组成一个页表项，而通常只需计算记录块号所需要的空间，而页号连续存放（一个页表种各项是连续存放的，类比数组），是不占用存储空间的。另外，页号从0页开始且记录的是内存块号而非内存起始地址。J号内存块的起始地址 = J * 内存块大小
地址转换过程：
地址结构： 逻辑地址分为两部分：页号 和 页内偏移量。 物理地址分为两部分：页框号 和 页内偏移量。 页内偏移量在逻辑地址和物理地址中是相同的。
- CPU 生成逻辑地址 (P, W)。
- 用页号 P 查询进程的页表，找到对应的物理页框号 F。
- 页表的起始地址通常存放在页表基址寄存器 中。
- 页表项地址 = PTBR + P * 页表项大小。
- 如果 F 有效（即该页在内存中），则物理地址 = F * 页框大小 + W。
- 访问物理地址。
页表寄存器(PTR):存放起始地址F和页表长度M
页表项:
页表项 至少包含：
- 物理页框号。
- 有效位/存在位：指示该页是否在内存中。（详见下文中3.5上面③处）
- 其他控制位：保护位 (读/写/执行权限)、修改位、访问位等。
页表项长度：每个页表项占多大存储空间
页面大小：一个页面占多大存储空间
基本分页的优缺点：
优点
- 没有外部碎片（因为页框大小固定，任何空闲页框都可以分配）。
- 内存利用率较高。
- 易于实现内存共享（多个进程的页表项指向同一个物理页框）。
缺点
- 内部碎片：进程最后一页通常不会占满整个页框，导致页框内有部分空间浪费。
- 页表开销：每个进程都需要一个页表，页表本身占用内存空间。如果逻辑地址空间很大，页表也会很大。
- 两次内存访问：第一次访问页表，第二次访问实际数据。可以通过快表 来加速(快表只用一次访存)。
快表：依旧局部性原理
又称联想寄存器、TLB： TLB 是一个小型的、高速的相联存储器，用于缓存最近使用过的页表项。是一种访问速度比内存块很多的高速缓存，对应的内存的页表成为慢表(类比计组的Cache)。
- 当 CPU 生成逻辑地址时，首先并行查找 TLB：
算出页号和偏移量后，将页号与快表中的所有页号进行比较
- TLB 命中：如果页号在 TLB 中找到，直接获取物理页框号，无需访问内存中的页表。
- TLB 未命中：如果页号不在 TLB 中，则需要访问内存中的页表，获取页表项，并将其存入 TLB (可能会替换掉一个旧的条目)，然后进行地址转换。
多级页表：
单机页表的问题：
①页表连续存放，页表很大时占用很多页框，②且有时候没有必要让整个页表常驻内存
二级页表：
①：可以为离散分配的页表再建立一张页表，成为页目录表，或者外层/顶层页表 王道视频中的图示：
地址转化：给出逻辑地址转为内存地址，与单级页表类似
各级页表的大小不能超过一个页面,另外，在多级页表中，页表项不存储“逻辑页号”，只存储“下一级页表的物理起始地址”或“最终物理页框号”+ 控制位。
②：需要访问页面时才把页面调入内存（虚拟内存技术），同时在页表项新增标志位判断页面是否在内存中（③）
3.5：基本分段存储管理
从用户的角度出发，将程序的逻辑地址空间划分为若干个逻辑意义上独立的段，如代码段、数据段、堆栈段等。
- 每个段有自己的名字（或段号）和长度。
- 段的长度可以不同。
- 段的划分由用户或编译器决定。
原理：
- 进程的逻辑地址空间由多个段组成，这些段可以离散地存放在内存中不相邻的区域。
- 操作系统为每个进程维护一个段表，记录段号到段在内存中起始地址和长度的映射关系。
- 段表通常存放在内存中。
地址结构： 逻辑地址分为两部分：段号 和 段内偏移量。
地址转换过程：
- CPU 生成逻辑地址 (S, W)。
- 用段号 S 查询进程的段表，找到对应的段基址 (Base) 和段长 (Limit)。
- 段表的起始地址通常存放在段表基址寄存器 中。
- 段表项地址 = STBR + S * 段表项大小。
- 检查段内偏移量是否越界：
0 <= W < Limit。如果越界，产生异常。 - 如果有效，则物理地址 = Base + W。
- 访问物理地址。
段表项 至少包含：
- 段基址：该段在内存中的起始物理地址。
- 段长：该段的长度。
- 其他控制位：保护位、有效位等。
基本分段的优缺点：
优点
- 方便编程，用户可以按逻辑结构组织程序。
- 易于实现分段共享（多个进程的段表项指向同一个物理段）和分段保护（对不同段设置不同权限）。
- 段的长度可变，按需分配，没有内部碎片。
缺点
- 外部碎片：由于段长度可变，内存分配和回收后会产生外部碎片。
- 段表开销。
- 两次内存访问（可通过 TLB 优化）。
分页与分段的比较：
特性 分页 分段 划分单位 页，物理单位，大小固定 段，逻辑单位，大小可变 用户可见性 对用户透明 对用户可见（程序员需感知段的存在） 地址空间 一维逻辑地址空间 二维逻辑地址空间 (段号, 段内偏移) 碎片 内部碎片 外部碎片 共享 页共享（实现复杂，粒度小） 段共享（实现简单，粒度合适） 保护 以页为单位进行保护 以段为单位进行保护（更符合逻辑） 目的 提高内存利用率，克服物理内存限制 满足用户按逻辑模块化组织程序的需求
3.6：段页式存储管理
结合了分段和分页的优点，先将程序按逻辑结构分段，再将每个段划分为固定大小的页。
原理：
- 每个进程有一个段表，段表项指向该段的页表。
- 每个段有自己的页表。
- 内存被划分为页框。
地址结构： 逻辑地址分为三部分：段号、段内页号、页内偏移量。
地址转换过程：
- CPU 生成逻辑地址 (S, P, W)。
- 用段号 S 查询进程的段表，找到该段的页表基址和段长。
- 检查段号是否越界。
- 用段内页号 P 查询该段的页表，找到对应的物理页框号 F。
- 检查页号是否越界（相对于段长）。
- 如果有效，则物理地址 = F * 页框大小 + W。
- 访问物理地址。
段页式的优缺点：
- 优点
- 兼具分段和分页的优点：按逻辑分段，按物理分页。
- 易于实现共享和保护。
- 没有外部碎片，内部碎片仅限于每段的最后一页。
- 缺点
- 系统开销大：需要段表和页表，多次内存访问（通常至少三次，可通过 TLB 优化）。
- 硬件实现复杂。
二、内存空间的扩充
3.7：覆盖与交换
这两种技术用于在物理内存不足以容纳整个程序时，使程序能够运行。
覆盖技术：
- 主要用于早期的操作系统，由程序员手动实现。
- 将程序划分为若干功能上相对独立的模块（覆盖段）。
- 不常用的模块不常驻内存，只在需要时调入内存，覆盖掉不再需要的模块。
- 优点：可以在较小的内存空间运行较大的程序。
- 缺点:
- 需要程序员明确划分模块和覆盖关系，编程复杂。
- 覆盖结构对程序设计有很大限制。
- 增加了程序执行时间。
交换技术：
- 由操作系统自动实现。
- 将内存中暂时不能运行的整个进程（或部分）调出到外存的交换区，待需要时再调回内存。
- 用于中级调度，以提高内存利用率和系统并发度。
- 优点
- 增加了系统的并发进程数量。
- 对用户透明。
- 缺点
- 交换操作涉及大量的磁盘 I/O，开销大，影响系统性能。
- 交换单位是整个进程，粒度较大。
3.8：虚拟内存
- 传统存储方式的缺点：一次性、驻留性 -> 可用虚拟存储技术解决问题
- 实现原理：局部性原理。包括时间局部性和空间局部性
基于局部性原理，要用到的部分转入内存，暂时用不到的地方留在外存。
若内存空间不够，由OS负责将内存中赞数用不到的信息换出到外存
- 在OS管理下，似乎有一个比实际内存大得多的内存，这就是虚拟内存(实际内存并没有变)
特征:
多次性：允许被分成多次调入内存
对唤性：在作业运行时无需一直常驻内存，允许换入换出
虚拟性：逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量
如何实现？ ->
建立在离散分配的内存管理方式基础之上
主要区别：
1.程序执行时若访问的信息不在内存，则由OS负责将所需的信息从外存调入内存
2.空间不足时需要将暂时用不到的信息换到外存 -> 页/段置换功能
3.9：请求分页管理方式
是实现虚拟内存最常用的方法。
原理：
- 当进程需要访问某个页时，才将该页从外存调入内存。如果该页已在内存中，则直接访问。
- 需要硬件支持：
- 页表机制：除了物理页框号，还需要一些额外的控制位。
- 缺页中断机构。
- 地址转换机构。
页表项在请求分页中的扩展（新增的信息）：
- 有效位/存在位
1: 表示该页在内存中，页表项中的物理页框号有效。0: 表示该页不在内存中（可能在外存，也可能从未被访问过）。访问该页会产生缺页中断。
- 访问位：记录该页在一段时间内是否被访问过。用于页面置换算法。由硬件在访问时自动置 1。
- 修改位：记录该页调入内存后是否被修改过。如果被修改过，则在换出时需要写回外存；否则无需写回（如果外存中已有副本）。由硬件在写入时自动置 1。
- 保护位：读/写/执行权限。
- 外存地址：如果页不在内存中，该字段指向页在外存（如交换区）的位置。
和基本分页一样，先检查快表，在检查慢表，都没有则缺页处理
缺页中断(内中断)处理过程：
- CPU 执行指令，访问逻辑地址，通过 MMU 进行地址转换。
- MMU 查找页表，发现对应页表项的有效位为 0，产生缺页中断。
- CPU 响应中断，操作系统接管控制权。
- 保护现场：保存当前进程的 CPU 状态。
- 分析中断原因：确定是缺页中断。
- 查找所需页在外存的位置：根据页表项中的外存地址信息。
- 查找空闲页框
- 如果内存中有空闲页框，则分配一个给即将调入的页。
- 如果没有空闲页框，则需要执行页面置换算法，选择一个牺牲页将其换出到外存（如果该页被修改过，则需写回）。
- 调入所需页：启动磁盘 I/O 操作，将目标页从外存读入分配的物理页框。这是一个耗时的操作，当前进程通常会阻塞。
- 修改页表：更新调入页的页表项（设置有效位为 1，填入物理页框号，清空修改位和访问位等）。
- 恢复现场：缺页中断处理完毕，重新执行被中断的指令。
3.10：页面置换算法
当发生缺页中断且没有空闲物理页框(缺页时未必发生页面置换)时，需要选择一个内存中的页（牺牲页）将其换出，以便为新调入的页腾出空间。目标是选择一个将来最不可能被访问的页，以减少缺页次数。
最佳置换算法
- 选择将来最长时间内不会被访问的页进行置换。
- 优点：缺页率最低，是评价其他算法性能的基准。
- 缺点：无法实现，因为操作系统无法预知将来页面的访问序列。
先进先出置换算法
- 选择在内存中驻留时间最长的页进行置换。
- 维护一个包含所有在内存中页面的队列，按到达时间排序。
- 优点：实现简单。
- 缺点：性能较差，可能换出经常访问的页。会产生Belady 异常（即分配给进程的页框数增加，缺页次数反而增加的现象,只有FIFO会出现这种现象）。
最近最久未使用算法(最接近最佳置换算法)
页表项中存有自上次被访问经过的时间t，选个t最大的飞出去
- 选择过去最长时间内未被访问的页进行置换。基于局部性原理，认为最近最久未使用的页在将来也最不可能被访问。
- 优点：性能接近 OPT，是一种较好的算法。
- 缺点：实现开销大，需要记录每个页的访问时间或维护一个按访问时间排序的栈/链表。
- 硬件支持实现
- 计数器：每个页表项关联一个时间戳寄存器。每次访问页时，将当前时钟值复制到该寄存器。置换时选择时间戳最小的页。开销大。
- 栈：维护一个页号栈。页被访问时，将其移到栈顶。栈底的页是 LRU 页。开销也较大。
时钟置换算法
- 是 LRU 的一种近似实现，开销较小。
- 将内存中的页组织成一个循环队列（像一个时钟的表面），有一个指针指向其中一个页。
- 每个页表项有一个访问位。
- 算法流程
- 当需要置换页时，从指针当前位置开始顺序检查队列中的页。
- 如果当前页的访问位为 1，则将其置为 0，指针下移，继续检查下一个页（给它第二次机会）。
- 如果当前页的访问位为 0，则选择该页为牺牲页进行置换，新页放入该位置，指针下移。
- 优点：开销比 LRU 小，性能尚可。
改进的时钟算法
与4.的主要差别：只有被淘汰的页面被修改过才会被返回内存
算法差别如下：(访问位，修改位)
同时考虑
访问位 (A)和修改位 (M)
。将页分为四类：
(A=0, M=0)：最近未访问，未修改 (最佳牺牲页)。(A=0, M=1)：最近未访问，已修改 (次佳，换出前需写回磁盘)。(A=1, M=0)：最近已访问，未修改。(A=1, M=1)：最近已访问，已修改 (最不应被牺牲)。
算法会优先从类别低的页中选择牺牲页。
具体实现：可以进行多轮扫描(最多四轮)。第一轮找 (0,0)；第二轮找 (0,1) 并将扫描过的 (1,x) 页的访问位置 0；以此类推。
0,0 -> 0,1 -> 0,0 -> 0,1
最不常用算法
- 选择过去一段时间内被访问次数最少的页进行置换。
- 每个页表项需要一个访问计数器。
- 缺点：实现开销大；可能将早期频繁访问但近期不再使用的页保留在内存中。
最常用算法
- 认为访问次数最少的页可能是刚调入还未被充分使用，所以选择访问次数最多的页进行置换。
- 通常性能不佳。
3.11：页面分配策略
页面分配策略和页面置换算法的区别：
| 页面置换算法 | 页面分配策略 |
|---|---|
| 发生缺页并且内存已满此时需要将其中页面置换 | 进程创建、执行的过程中为进程分配页框 |
在请求分页系统中，需要为每个进程分配一定数量的物理页框。
页面分配策略：
页框置换范围：当发生缺页且无空闲页框时，从哪些页框中选择牺牲页。
全局置换
：可以在所有可换出页框中选择牺牲页，即使是其他进程的页框。
- 优点：能更好地利用内存，系统整体吞吐量可能更高。
- 缺点：一个进程的缺页率会受其他进程影响；难以控制单个进程的性能。
局部置换
：只能在当前缺页进程自己占有的页框中选择牺牲页。
- 优点：更容易控制单个进程的缺页率和性能。
- 缺点：可能导致某些进程即使有空闲页框也无法使用，内存利用率可能较低。
何时调页：
1.预调页：一次调入若干个相邻页面，一般只在进程开始时比较有效
2.请求调页策略：运行时发现缺页才调入内存
抖动和工作集
驻留集一般比所需页数小(虚拟内存)
抖动： 如果分配给进程的物理页框太少，导致进程频繁发生缺页中断，大部分时间都用于页面换入换出，而实际有效计算时间很少，从而导致系统性能急剧下降的现象。
产生抖动的原因：
- 同时运行的进程过多，导致每个进程分配到的页框数不足。
- 页面置换算法选择不当。
防止抖动的方法：
- 采用局部置换策略。
- 基于工作集模型进行页框分配。
- 控制并发进程的数量（如通过中级调度）。
- 选择合适的页面置换算法。
工作集模型： Denning 提出，基于局部性原理。一个进程在某段时间间隔
Δ内实际访问的页面的集合称为其在该时刻的工作集WS(t, Δ)。Δ称为工作集窗口大小。- 工作集的大小
|WS(t, Δ)|会随时间变化。 - 原理：操作系统跟踪每个进程的工作集，并为其分配足够的页框以容纳其工作集。如果一个进程的工作集中的所有页都在内存中，那么它在接下来的
Δ时间内不太可能发生缺页。 - 应用
- 页框分配：为进程分配其工作集大小的页框。如果物理内存不足以容纳所有进程的工作集，则应挂起某些进程。
- 页面置换：可以优先换出不在当前工作集中的页面。
三、地址转换
3.12：地址转换的三种方式
1.绝对装入（可跳过）
知道程序放在内存中的哪个位置，编译时由编译器则直接产生绝对的地址
-> 如程序写入地址114，则编译后起始地址为100，则直接装入214
缺点：灵活性差，只适用单道程序环境，换个电脑就跑不动了
2.可重定位
根据内存当前的情况，装入内存时对地址进行重定位
-> 写入地址39，装入时起始物理地址为100，则所有地址相关参数 + 100
缺点：作业一旦进入内存，运行期间不能再移动
3.动态重定位
装入内存后并不会把逻辑地址转换为内存地址，而是把地址转换推迟到程序真正要执行的时候才进行
这种方式需要一个重定位寄存器的支持
特点：允许程序在内存中发生移动，且可将程序分配到不连续的存储区当中
四、存储保护
3.13：存储保护的两种方式
1.上下限寄存器
在CPU中设置一堆上下限寄存器存放上下限地址，指令访问某个地址时检查是否越界
记录方式 -> 上限 : 200 下限:300
2.重定位寄存器和界地址寄存器
重定位寄存器（又称基址寄存器）存放进程起始物理地址，界地址寄存器（又称限长寄存器）存放进程的最大逻辑地址(进程的长度)
记录方式 -> 重定位:200 界地址:100
五、杂项
3.14：内存映射文件与进程的内存映像
这两个是不同的概念，但是长得有点像，纹身的网页也没提到，所以暂且放在一起当杂项简单记录
进程的内存映像：
内存映射文件：
一种允许将磁盘文件的内容直接映射到进程的虚拟地址空间的技术。映射后，可以像访问内存一样通过指针来读写文件内容，而无需使用 read() 和 write() 等文件 I/O 系统调用。
优点：
- 方便：像访问内存一样访问文件。
- 高效：对于某些操作（如随机访问、小数据量读写），可能比传统 I/O 更高效，因为它利用了虚拟内存的按需分页机制，避免了数据的多次复制。
- 共享：多个进程可以将同一个文件映射到各自的地址空间，实现共享内存。
实现： 通过系统调用（如 POSIX 的mmap()）实现。操作系统在进程的页表中建立文件页与虚拟地址页的映射。当访问这些虚拟地址时，如果对应的文件页不在内存，则发生缺页中断，由操作系统从磁盘调入。对映射区域的修改可以根据映射参数写回磁盘。
第四部分：文件管理
1.文件属性：描述文件特征的信息，通常存储在文件控制块中。
名称：用户可读的文件名。同一目录下不能重名
标识符：文件系统内部使用的唯一标签。
类型：如可执行文件、文本文件、图像文件等。
位置：指向文件在存储设备上位置的指针。
大小：文件当前的大小。
保护：对文件进行保护的访问控制信息（如读/写/执行权限）。
时间、日期和用户标识：创建时间、最后修改时间、最后访问时间、所有者等。
操作系统应该向上提供的功能
基本功能:
- 创建文件 : create调用
- 读文件: read
- 写文件:write
- 删除文件:delete
- 打开文件:open
- 关闭文件:close
2.文件的逻辑结构:
文件的逻辑结构
指文件在用户视图中的组织方式，与文件在存储介质上的物理存放方式无关。
不过算法的具体实现与逻辑结构、物理结构都有关
无结构文件 (流式文件)
：文件被看作是一系列连续的字节流或字符流。
- 操作系统不关心文件内部结构，由应用程序自行解释。
- 如文本文件、可执行文件。
- ** 优点**：简单通用。
有结构文件 (记录式文件)
文件由一系列具有相同或不同长度的记录组成。每条记录又由其中的数据项（自己定义的数据结构）组成(可把记录理解成数据)
一般来说，每条记录有一个数据项可以作为“关键字 ”
操作系统提供按记录访问的功能,
根据各条记录长度（占用的存储空间而非视图长度）是否相等，又可分为定长记录和可变长记录两种
定长记录：所有记录长度相同。
变长记录：记录长度可不同。不方便随机存储，所以出现索引与顺序索引
类型:各条记录在逻辑上如何组织
1.顺序文件：记录按顺序排列，只能按序访问（或通过模拟随机访问）。物理上相邻
串结构：记录之间的顺序与关键字无关
顺序结构：记录之间的顺序按关键组排序排列
对于链式存储（串结构）:无论是否定长，都无法实现随机存取（通过索引找到地址），每次只能从第一个记录开始依次往后查找
对于顺序存储的可变长记录:由于每个记录的长度不一样，可变长无法实现随机存取,每次只能从第一个记录开始依次往后查找
定长记录:可实现随机存取
可否快速检索某条记录：定长顺序存储若是顺序结构则可以
优缺点：
2.索引文件：为文件建立索引表，根据记录的键值通过索引快速定位记录。可解决不定长文件的存取问题
文件的记录在物理上不一定连续存放
但是索引表需要在物理上相邻
索引表本身是定长记录的顺序文件，另外 ，可以用不同的数据项建立多个索引表
缺点:索引表可能很大，空间利用率低
可以这么理解：用一个数组装入地址，这样可以按顺序访问数组的地址，而地址之间的间隔可以不同
3.索引顺序文件：将顺序文件和索引文件结合，记录顺序存储，同时建立索引。支持顺序访问和按键随机访问。
其并不会为每个记录创建一个索引表项，而是一组记录对应一个索引表项 这样在顺序查找时，可以先确定类，再去类中找（如A~F开头各十个人，先确定开头字母，再去其中找，共要找7 + 10次），而不是找70个人
索引顺序文件:定长串结构顺序文件,逻辑文件：也是顺序文件
还可以建立多级索引表：以减少索引次数
记得计算平均检索次数:
- 4.直接文件/散列文件：根据记录的键值通过散列函数直接计算出记录的物理地址。
现代操作系统大多采用无结构文件，将文件内部结构的解释交给应用程序。
3.文件目录:该如何实现
目录本身就是一种结构文件，由一条一条的记录组成，每条记录对应一个放在该目录下的文件
控制块和索引结点：
文件控制块(FCB)：操作系统为管理文件而设置的数据结构，用于存放与文件相关的所有管理信息（即文件属性）,包括文件名、物理地址、逻辑结构、物理结构等基本信息，还有存取控制信息，使用信息。FCB 是文件存在的标志。
所有文件的 FCB 集合构成了文件目录（或称为目录文件）。一个FCB就是一个文件目录项
索引结点(FCB改进 )：在类 UNIX 系统中，FCB 中的文件名等描述性信息与文件控制信息（如物理地址、权限、大小等）分离。
- 目录项：只包含文件名和指向该文件索引结点的指针。
- 索引结点：包含文件的除文件名以外的所有元数据，如文件类型、权限、所有者、时间戳、大小、指向数据块的指针等。
也就是说，目录表只包含文件名，找到文件名再去查找指针
这样的好处是，目录表可以装入更多的文件名，由于每个磁盘块的大小有限，目录项较多时需要多个次品，这样，当目录项较多时，一个磁盘可以装入更多的目录项，一次减少启动磁盘的次数（减少磁盘的I/O读入）
- 优点
- 一个文件可以有多个文件名（硬链接），都指向同一个 inode。
- 提高了目录操作的效率（目录项变小）。
- 方便文件系统检查和修复。
目录结构:
1.单极目录结构
整个系统只有一个目录表，不允许文件重名
2.两级目录结构
早期的多用户操作系统，分为主文件目录和用户文件目录,允许不同用户的文件重名
主文件目录记录用户名与文件存放位置
用户文件目录由该用户的文件FCB组成
3.多级目录结构（树形结构）
可以给自己的文件分类，可以有多个用户（存于根目录下） ,各级目录之间用"/“隔开,从根目录出发的路径称为绝对路径,也可以设置从当前目录出发的”相对路径"
用相对路径可以减少磁盘IO的次数，提升访问文件的效率
不同目录下的文件可以重名
4.无环图目录结构(方便实现文件共享)
可以用不同的文件名指向同一个文件、甚至可以指向同一个目录,这样一个用户进行更改，另一个用户也可以看到变化（而非简单的CV）
可以为每个共享节点设计一个共享计数器，单个用户删除只会让count–,只有共享计数器为0才会彻底删除
第五部分：I/O设备
1.基本概念与分类
系统将尾部设备抽王为一种特殊文件，用户可以使用与文件操作西昂同的方式对外部设备进行操作
I/O设备的组成
I/O设备由电子部件和机械部件组成
按使用特性分类:
1.人机交互类外部设备（数据传输速度慢）
2.存储设备（数据传输速度快）
3.网络通信设备(介于以上之间)
按传输速率分类
1.低速设备 2.中速设备 3.高速设备
按信息交换的单位分类:
1.块设备:传输速率较高，可以寻址，即可以随机读写一块
2.字符设备：传输速率较慢，不可寻址，在输入输出时常采用中断驱动的方式
I/O 控制方式与接口
对于控制器：
I/O控制器，也常被称为设备控制器或接口，是CPU与外部设备（如硬盘、键盘、显示器）之间的一个硬件中介。它负责处理CPU发来的命令，并管理与之相连的外设，将复杂的设备状态和信号转换为CPU能够理解的统一格式。
一个典型的I/O控制器内部包含以下三个核心部分：
- 1.控制与状态寄存器
- 2.数据缓冲寄存器
- 3.设备接口逻辑：直接连接外设。将缓冲器的数据按外设要求的格式发送出去，并接收外设传来的数据放入缓冲器。
I/O控制方式描述了操作系统如何利用I/O控制器
一个IO控制器可能对应多个设备
两种寄存器编址方式：1.内存映射I/O 2.寄存器独立编制
对于控制方式：
此事在计组中亦有记载
IO控制：指 CPU 如何管理和控制 I/O 设备的操作。
程序直接控制方式 (轮询)
CPU干预频繁，在等到IO完成的过程中CPU需要不断地轮询检查
- CPU 主动执行 I/O 指令来启动设备，并不断检测设备状态寄存器，直到 I/O 完成。
- 优点：硬件简单。软件也可实现
- 缺点：CPU 在等待 I/O 期间处于忙等待状态，CPU 利用率低。
中断驱动方式
CPU 发出 I/O 命令启动设备后，就去执行其他任务。
当 I/O 设备完成操作后，会向 CPU 发出中断请求。CPU 响应中断，转去执行中断处理程序，处理 I/O 结果。
注意：CPU会在每个指令周期末尾检查中断
- 优点：等待IO完成的过程中CPU可以切换到别的进程执行，大大提高了 CPU 利用率。
- 缺点:
- 每次 I/O 操作完成都需要中断，对于高速设备，频繁中断会消耗大量 CPU 时间。
- 每个字在IO与内存之间的数据传输仍需 CPU 参与（从设备控制器寄存器读数据到内存，或从内存写数据到寄存器）。
直接存储器存取方式
在 I/O 设备和主存之间开辟直接的数据通路。
需要 DMA(直接存储器存取) 控制器。
相比中断，数据的传送单位为“块”，不再是一个字一个字的传送。（每次读写只能是连续的块，读到内存后在内存中也是连续的）
- 过程：
- CPU 向 DMAC 发出 I/O 命令（包括要读/写的数据块的内存起始地址、磁盘地址、数据块大小、传输方向等）。 —–>CPU只需指明需要进行的操作并验收
- DMAC 接管总线控制权（或通过周期窃取方式），直接在设备和内存之间传输数据，无需 CPU 干预。
- 数据传输完成后，DMAC 向 CPU 发出中断信号。
- 优点：进一步减少了 CPU 对 I/O 操作的干预，CPU 只需在数据传输开始和结束时参与。特别适合高速块设备。
- 缺点：硬件比中断方式复杂。
PS:DMA控制器
其读入也是一个字一个字读入，但会先读到DR中
- 过程：
通道控制方式
是 DMA 方式的进一步发展，引入了通道（一种专门负责 I/O 处理的处理机）。每次可以读写一组数据快
通道：一种硬件，“减弱版”CPU,其可以识别并执行一系列通道指令
CPU 只需向通道发出 I/O 指令，指明要执行的通道程序（一组 I/O 命令）在内存中的位置。并指明要操作的是哪个IO设备，之后CPU便可以切换到其他进程了
- 通道会执行通道程序，控制多台 I/O 设备与内存进行数据交换。
- 完成后，通道向 CPU 发出中断。
- 优点：进一步解放了 CPU，实现了 CPU 与 I/O 操作的高度并行。主要用于大型机。资源利用率很高
- 缺点：硬件非常复杂，成本高
I/O软件的层次结构
I/O 软件通常组织成层次结构，以实现设备独立性和提高软件可维护性。越上面的层次越接近用户，越下面的层次越接近硬件。
中间三层棕色部分属于操作系统的内核部分
用户层 I/O 软件
- 提供给用户的库函数（如 C 标准库的
printf,scanf,fopen,fread等）。 - 将用户请求转换为对操作系统内核的系统调用。
用户层的应用程序无法用一个统一的系统调用接口来完成所有类型设备的I/O
- 提供给用户的库函数（如 C 标准库的
设备独立性软件层
又称设备无关性软件，与设备的硬件特性无关的功能几乎都在这一层实现
- 操作系统的核心 I/O 部分。
- 向上层提供统一的 I/O 接口（如对块设备和字符设备的统一抽象）。
- 负责设备命名、设备保护、提供与设备无关的块大小、缓冲技术、设备分配与回收、错误报告等。
注：其不可以直接操作硬件
设备驱动程序层
- 与特定 I/O 设备控制器直接交互。
- 将上层发来的抽象 I/O 请求（如读一个逻辑块）转换为对设备控制器的具体操作序列（如设置寄存器、启动设备）。
- 处理设备产生的中断。
- 每个设备类型通常都有一个对应的设备驱动程序。
中断处理程序
- 当中断发生时，保存 CPU 现场，分析中断原因，调用相应的设备驱动程序中的中断服务例程。
- 处理完毕后，恢复现场。
硬件层
- 包括 I/O 设备控制器和 I/O 设备本身。
- 硬件由机械部分和电子部分组成
输出/输入应用程序接口
应用程序I/O接口：你写代码时调用的那个函数 (read, write)。
输入输出应用程序的接口：操作系统教材里描述的、负责设备独立性的那个软件层次。
操作系统向应用程序提供的进行 I/O 操作的接口，通常是一组系统调用。
输入/输出应用程序接口
- 1.块设备接口：如
read block,write block。访问特定块。
如：键盘，打印机
- 2.字符设备接口：如
get char,put char。顺序读写字符。
如：磁盘
3.网络设备接口：又称网络套接字（socket）接口
如：网络控制器（网络控制器）
时钟和定时器接口：获取当前时间，设置定时器。
其他接口：如图形用户界面相关的 I/O。
这些接口通常被封装在用户库函数中，方便应用程序调用。
阻塞/非阻塞IO
设备驱动接口:
厂商按照统一规定好的标准开发驱动程序
不同的OS，对设备驱动程序的接口的标准各不相同
Saurlax
设备驱动程序是操作系统内核的一部分，它直接与特定的硬件设备控制器交互。设备独立性软件层通过一个标准的接口来调用设备驱动程序的功能。
这个接口通常定义了一组标准函数，如：
open(): 初始化设备。close(): 关闭设备。read(): 从设备读取数据。write(): 向设备写入数据。ioctl(): 执行设备特定的控制操作。strategy(): 对于块设备，用于提交一个读/写请求到设备请求队列。
设备驱动程序负责将这些通用请求转换为设备控制器能理解的具体命令序列。
I/O核心子系统：
中间棕色的三层：
I/O调度：用某种算法确定一个好的顺序来处理各个IO请求
需要实现的功能与实现位置:
用户层软件：
1.假脱机技术(SPOOLing技术）
设备独立性软件:
2.I/O调度 -> 磁盘调度算法
3.设备保护
4.设备分配与回收
5.缓冲区管理（缓冲和高速缓存）
假脱机(SPOOLing)技术：
脱机
用软件的方式实现了脱机技术，故为“假脱机” **脱机：**脱离主机的控制进行IO操作
脱机技术/输出技术： 在CPU之外，用一台独立的、相对便宜的卫星机来控制I/O设备进行数据读写，使得I/O操作与CPU计算完全分离。
也就是先将数据输入到更快速的磁带上，再从快速的磁带读数据，从而缓解了速度矛盾
假脱机
在磁盘开辟出两个存储区域“输入井”和“输出井”
在设备与井之间是内存中的输入/输出缓冲器，在I/O进程的控制下，用于暂存数据，之后再转到井中
Saurlax：
原理： 在磁盘上开辟输入井 和输出井 作为缓冲区。
- 输入过程：输入进程将用户从输入设备（如卡片机）输入的数据先存放到磁盘输入井中。当 CPU 需要输入数据时，直接从高速的输入井中读取。
- 输出过程：输出进程将用户程序的输出结果先存放到磁盘输出井中。待输出设备（如打印机）空闲时，再由专门的输出程序将输出井中的数据实际输出到设备。
组成：
- 输入井和输出井：磁盘上的存储区域。
- 输入缓冲区和输出缓冲区：内存中的缓冲区，用于暂存与井交换的数据。
- 输入进程 和 输出进程：专门负责数据与井之间传输的系统进程。
- 井管理程序：负责井中作业的排队和管理。
优点：
- 虚拟了设备：将独占设备改造成了共享设备，多个用户可以同时“使用”该设备。
- 提高了 I/O 速度：缓和了 CPU 与慢速设备的速度矛盾。
- 提高了设备利用率。
- 实现了并行操作：CPU 计算、数据从设备到井、数据从井到设备可以并行进行。
用途：
前情提要：
作用：共享打印机 > 将独占式设备“打印机”用SPOOLing技术改造成共享设备
实现：
在磁盘的输出井中为进程申请一个空闲缓冲区并将要打印数据送入
为用户进程申请一张空白的打印请求表，将打印请求填入并将此表挂到假脱机队列上
也就是说，SPOOLing技术可以将一台物理设备虚拟成逻辑上的多台设备
设备的分配与回收
**设备的固有属性：**独占设备、共享设备、虚拟设备
应考虑因素:
1.设备固有属性：独占设备（如打印机）、共享设备（如磁盘）、虚拟设备。
2.设备分配算法：先来先服务、优先级等。
3.设备分配的安全性：避免死锁（如静态分配、按序分配）。
静态分配和动态分配：
静态：进程运行前为其分配所有资源
动态：进程运行过程中动态申请设备资源
安全性
分配过程的数据结构：
设备控制表（DCT）：为每个设备配一张用于记录设备情况
控制器控制表（COCT）：每个设备控制器对应一张，OS根据其信息对控制器进行操作和管理
通道控制表（CHCT）：每个通道对应一张CHCT，操作系统根据CHCT信息对通道进行操作和管理
系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目
分配过程：
⑤设备使用完毕后，进程释放设备，系统回收设备，并唤醒等待队列中的进程（如果队列不空）。
只有设备、控制器、通道三者都分配成功是此次设备分配才算成功，之后便可启动IO设备进行数据传送
分配步骤的改进
缓冲区
缓冲：在 I/O 设备和 CPU（或内存）之间设置一个临时存储区域（缓冲区），用于暂存数据。
引入缓冲的目的：
- 缓和 CPU 与 I/O 设备之间速度不匹配的矛盾：高速 CPU 与低速 I/O 设备可以通过缓冲区协调工作。
- 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制：数据可以先批量送入缓冲区，再统一处理。
- 提高 CPU 与 I/O 设备之间的并行性：CPU 可以将数据输出到缓冲区后继续做其他事，由缓冲区将数据传给 I/O 设备。
- 解决数据粒度不匹配的问题：如发送方和接收方处理数据块大小不同。
缓冲区的实现：
缓冲区的特性：
非空时不能冲入数据，只可取出；缓冲区为空后可以冲入数据，但只有充满之后才能从缓冲区把数据传出(故而有了多缓冲)
1.单缓冲
设置一个缓冲区。
如果没有特别说明，一个缓冲区的大小就是一个块
- 输入时：设备数据 -> 缓冲区 -> 用户区。
- 输出时：用户区 -> 缓冲区 -> 设备。
- 当缓冲区满（输入）或空（输出）时，进程可能需要等待。
2.双缓冲
设置两个缓冲区。
- 一个缓冲区用于 I/O 设备操作，另一个用于 CPU 操作，两者可以并行。
- 当一个缓冲区满（输入）或空（输出）后，切换到另一个缓冲区。
- 提高了并行度，减少了等待时间。
3.循环缓冲
将多个缓冲区组织成循环队列。
- 适用于生产者-消费者模型，如输入输出流。
4.缓冲池
由系统统一管理一组缓冲区，供多个 I/O 请求共享。
按照缓冲区的使用情况可以分为：空缓冲队列、装满输入数据的缓冲队列、装满输出数据的缓冲队列
- 当进程请求 I/O 时，从缓冲池中分配一个缓冲区。
- 提高了缓冲区的利用率。
高速缓存：
与缓冲区类似，也是一块高速存储区域，但主要用于保存频繁访问的数据副本，以加快后续访问速度。
磁盘高速缓存
内存中开辟一块区域，缓存最近访问过的磁盘块。
- 当需要读磁盘块时，先检查 Cache，若命中则直接从 Cache 读取。
- 写操作可以采用写穿（同时写 Cache 和磁盘）或延迟写/回写（先写 Cache，适当时机再写回磁盘）。
与缓冲区的区别
- 缓冲区主要目的是缓和速度差异和提高并行性。
- 高速缓存主要目的是利用局部性原理，通过保存副本加快访问。
- 一个数据项可能只在缓冲区中临时存放一次，但可能在高速缓存中存放多次。
磁盘的结构
磁盘是计算机系统中常用的辅助存储设备，容量大，速度相对较快，可随机访问。
物理结构：
- 盘片：一个或多个圆形金属或玻璃盘片，双面涂有磁性材料。
- 磁道：盘片上的一系列同心圆。
- 扇区：每个磁道被划分为若干个扇形区域，是磁盘读写的最小单位（通常 512 字节或 4KB）。
- 柱面：所有盘片上半径相同的磁道构成的圆柱面。
- 磁头：每个盘面对应一个磁头，用于读写数据。所有磁头固定在同一个磁头臂上，同步移动。
磁盘地址：通常由 (柱面号, 磁头号/盘面号, 扇区号) 组成。
磁盘访问时间：
- 寻道时间：磁头从当前位置移动到目标磁道所需的时间。这是最主要的部分。
- 旋转延迟时间：等待目标扇区旋转到磁头下方所需的时间。平均为磁盘旋转半圈的时间。
- 传输时间：数据从磁盘读出或写入磁盘所需的时间。取决于数据量和磁盘转速/密度。
磁盘调度算法
一次磁盘读写操作需要的书简
T = 寻找时间 + 延迟时间 + 传输时间
- 寻找（道）时间：启动磁头臂时间s + 每跨越一个磁道的耗时m*要跨越的磁道n ->T(s) = s + m/n
- 延迟时间T(R)：通过旋转磁盘使磁头定位到目标扇区所需要的时间 设磁盘转速为r，在平均时间T(R) = 1/2r
- 传输时间T(t):从磁盘读写数据所需要经历的时间
由于转速为固有属性，所以OS只能影响寻道时间 -> 磁盘调度算法
算法
当有多个磁盘 I/O 请求等待时，磁盘调度算法决定处理这些请求的顺序，以减少总寻道时间，提高磁盘吞吐量。
假设当前磁头位置，以及一个等待访问的柱面号队列。
- 先来先服务(FCFS)
- 按请求到达的顺序处理。
- 优点：公平。
- 缺点：平均寻道时间可能很长，效率不高。
- 最短寻道时间优先(SSTF)
- 选择与当前磁头位置最近的请求进行处理。
- 优点：平均寻道时间较短，吞吐量较高。
- 缺点：可能导致“饥饿”现象（某些远离磁头的请求长时间得不到服务）。
- 扫描算法 (电梯算法SCAN)
- 磁头在一个方向上移动（如从内到外），处理沿途所有请求。到达磁盘一端后，再反向移动，处理沿途请求。
- 优点：克服了 SSTF 的饥饿问题，寻道性能较好，对各个位置的请求响应比较公平。
- 缺点：对于刚经过的位置，如果出现新请求，需要等待磁头完整往返一次。两端磁道的请求等待时间较长。
- 循环扫描算法(C-SCAN)
- SCAN 算法的改进。磁头只在一个方向上处理请求（如从内到外）。到达一端后，立即快速返回到另一端（如最内侧），然后重新开始单向扫描。
- 优点：比 SCAN 更公平，请求的等待时间更均匀。
- 缺点：返回过程不处理请求，略有浪费。
- LOOK 算法 和 C-LOOK 算法
- 是 SCAN 和 C-SCAN 的改进。磁头移动到该方向上最远的一个请求处即改变方向，而不是移动到磁盘的物理端点。
- LOOK: 磁头在两个方向上移动，到达最远请求后反向。
- C-LOOK: 磁头在一个方向上移动到最远请求后，直接跳到另一端（有请求的最内/外侧），再开始单向扫描。
- 优点：避免了不必要的磁头移动到磁盘末端，效率更高。C-LOOK 是实践中常用的算法。
减少磁盘延迟时间的方法:
问题：磁头读取一块内容（一个扇区）后，需要一段时间处理，而盘片又在不停旋转，所以如果读入几个连续的逻辑扇区，可能需要很长的“延迟时间”
1.交替编号
2.磁盘地质结构设计：（柱面号、盘面号、扇区号）
3.错位命名
磁盘管理
磁盘初始化
- 低级格式化 (物理格式化)：在磁盘上划D分磁道和扇区，写入扇区头、尾和校验码等控制信息。出厂前完成。(每个扇区可存数据量相同)
- 高级格式化 (逻辑格式化)：创建文件系统结构，如写入引导块、超级块、inode 区、根目录等。
引导块：包含引导加载程序，用于启动操作系统。
开机时计算机先运行“自举装入程序”，通过执行该程序就可以找到引导块，并将完整的自举程序读入内存，完成初始化
固态硬盘SSD
SSD 使用闪存作为存储介质，没有机械部件。
读写以页为单位（对应一个扇区）而不是块
特性：
- 优点
- 读写速度快（尤其是随机读）。
- 无寻道时间和旋转延迟。
- 低功耗，抗震动，噪音小。
- 缺点
- 单位容量价格比传统磁盘高。
- 闪存有擦写次数限制（寿命问题，但通过磨损均衡技术有所改善）。
- 写操作比读操作慢，且擦除操作更慢（通常需要先擦除整个块才能写入）。
SSD 的 I/O 调度： 由于没有寻道时间和旋转延迟，传统磁盘调度算法（如 SSTF, SCAN）对 SSD 意义不大。 SSD 的调度更多考虑闪存的特性，如：
- 磨损均衡：尽量均匀地擦写所有闪存块，延长寿命。有动态磨损均衡和静态磨损均衡。
- 垃圾回收：整理无效数据，回收可擦除的块。
- 一些 SSD 控制器内部实现了自己的调度逻辑，操作系统层面可能只需 FCFS 或简单的优先级调度。
- TRIM 命令：操作系统通知 SSD 哪些数据块已不再使用，SSD 可以在空闲时进行擦除，提高后续写入性能。