操作系统（2）
操作系统二
第四章 存储器管理
（内存分配：分配和去配，地址映射：抽象和映射，内存保护：隔离和共享，内存扩充：存储扩充）
1、3、5 重要，2、4 自学
存储器的层次结构
多结构的存储器系统
存储器的六层结构
- CPU 寄存器
- 主存储器：高速缓存、主存储器、磁盘缓存（内存中，不是个独立的设备）
- 辅存储器：固定磁盘、可移动磁盘
可执行存储器：寄存器 + 主存储器
辅存属于设备管理和文件管理范畴
主存储器与寄存器
主存储器：保存进程运行时的程序和数据
寄存器：存放处理运行时的数据
高速缓存与磁盘缓存
高速缓存：备份主存中较常用的数据，减少处理机对主存的访问次数
磁盘缓存：暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数
程序的装入和链接
自学
程序在系统中运行，需要先装入内存，然后经过以下过程：
- 编译：由编译程序编译形成若干个目标模块（将高级语言翻译为机器语言）
- 链接：将模块与库函数链接在一起，形成完整的装入模块
- 装入：由装入程序将装入模块装入内存
程序的链接
重点：何时完成模块的调入
静态链接方式
- 在程序运行前完整链接。需要拷贝全部模块。
- 在外存完成链接
- 需要解决的问题
- 对每个模块相对地址进行修改
- 变换外部调用符号
装入时动态链接
- 边装入边链接（装入时，当发生外部模块调用事件时才去调入）
- 在内存完成链接
- 优点
- 便于修改和更新（修改模块时不需要重新打开装入模块）
- 便于实现模块的共享（时分复用）
运行时动态链接
Run-time Dynamic Linking
- 对某些模块的链接推迟到执行时链接
- 链接实际运行用到的模块，节省内存（因为并不是所有模块都会被运行，如错误处理模块）
程序的装入
重点：何时完成逻辑地址到物理地址的转换
术语
逻辑地址：装入程序的地址都是从 0 开始
物理地址：主存中一系列存储信息的物理单元的地址
重定位：逻辑地址（相对地址）到物理地址（绝对地址）的映射
绝对装入方式
(Absolute Loading Mode)
- 程序编译时直接产生物理地址
- 适用单道系统
可重定位装入方式
也叫静态重定位 Relocation Loading Mode
- 装入时根据内存情况对指令地址和数据地址进行相应偏移（加个偏移量）
- 地址变换在装入时一次完成，不再改变；要求一次性分配作业的全部内存空间；无需硬件支持
- 属于静态重定位
动态运行时装入方式
Dynamic Run-time Loading
- 装入内存后仍然是逻辑地址，地址转换推迟到执行时进行
- 绝对地址的转换有硬件支持（重定位寄存器）
- 支持程序在内存中浮动；不要求占用连续空间
连续分配存储管理方式
单一连续分配
为一个用户程序分配一个连续的内存空间
用于单用户、单任务的操作系统中。
将内存划分为
- 系统区
- 用户区
用户区内存由一道程序独占
适合绝对装入方式
固定分区分配
将用户内存划分多个分区，每个分区一道程序独占
划分分区的方法
分区大小相等
分区大小不相等
内存分配
将分区按大小排队（一般由小到大），建立分区使用表（起址、大小、状态）
程序装入时，由内存分配程序检索分区使用表，找到符合要求的分区，并进行标记
特点
使用分区说明表标识分区分配状态
适合静态重定位装入方式
会造成内碎片（属于某程序但未被使用的碎片）
动态分区分配
根据进程实际需要动态地分配内存
会存在外碎片（不属于任何程序的碎片）
分配中的数据结构
- 空闲分区表：序号、起址、大小
- 空闲分区链表：双向链表，状态信息、分区大小、指针
步骤
- 从空闲分区表中找一个足以容纳改作业的空闲区
- 若这个分区比较大，则一分为二
- 一部分分配给作业，另一部分仍作为空闲区留在表内
分区分配操作
分配内存
回收内存
碎片问题
不修改程序即可进行紧凑，需要硬件支持
紧凑：通过移动内存中作业的位置，把多个小分区拼成大分区的方法
动态重定位及其分区分配算法
以下三节为连续分配存储管理方式的分配算法
基于顺序搜索的动态分区分配算法 ☆
首次适应
(first fit, FF)
- 空闲分区按起址递增次序排列，从头开始直至找到第一个满足要求的空闲分区
- 内存低端会留下小的空闲区，高端有大的空闲区
- 优点：算法简单，保留高地址大空闲区
- 缺点：外碎片，查找效率低
循环首次适应
(下次适应，next fit, NF)
- 从上次分配的位置之后开始查找
- 优点：减少查找开销，空闲分区分布均匀
- 缺点：缺乏大空闲分区
最佳适应
(best fit, BF)
- 搜索整个序列，找到适合条件的最小的分区进行分配
- 优点：保留大空闲分区
- 缺点：留下大量难以利用的外碎片；查找效率低
最坏适应
(worst fit, WF)
- 空闲分区按大小从大到小的次序排列，最前面的最大的空闲分区就是找到的分区
- 优点：分割后空闲块仍为较大空块，剩余空间最大化；不会出现太小的外碎片
- 缺点：缺乏大空闲分区，一段时间后就不能满足对于较大空闲区的分配要求
基于索引搜索的动态分区分配算法
快速适应
(quick fit)
步骤
- 空闲分区按容量大小进行分类
- 对于每一类具有相同容量的所有空闲空间分区，单独设立一个空闲分区链表
- 系统中存在多个空闲分区链表
- 在内存中设立一张管理索引表
- 每个表项对应一种空闲分区类型
- 记录了空闲分区链表的表头指针
- 在进行空闲分区分配时，不会对任何分区产生分割；仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可
优点
- 查找效率高，O(1)
- 保留大分区
- 无外碎片
缺点
- 归还时算法复杂，系统开销大
- 仍有一定空间浪费
伙伴系统 ☆
buddy system
将内存按 2 的幂次划分，组成若干空闲块链表；查找该链表找到能满足进程需求的最佳匹配快。适用离散分配方式
分配原则：比一半大，又占不满整块；否则一分为二
步骤
- 对不连续的空闲分区，按分区大小进行分类。对具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，即会存在 k 个空闲分区链表
- 分配时
- 设需分配长度为 n，找 2^i^ 分区链的分区，使 2^i-1^ < n < 2^i^
- 若无，找 2^i+1^ 且把它均分两块，称为伙伴；一个加入 2^i^ 分区链，一个分配
- 回收时，若已存在 2^i^ 空闲分区，则将其于伙伴合并为 2^i+1^ 分区，…..
$$
buddy_k(x)= \begin{cases}
\ x+2^k \ (if \ x \ MOD \ 2^{k+1}=0)
\\ x-2^k \ (if \ x \ MOD \ 2^{k+1}=2^k)
\end{cases}
$$优点
查找效率高
能保留大的分区
其性能取决于查找空闲分区的位置和分割、合并的时间。 时间上不及快速适应算法，但空闲分区的使用率高
哈希算法
实现快速查找
unordered_map<分区大小, 空闲分区链表>
利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数。
构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表。
分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，找到对应的空闲分区表。
优点：查找快速，减少了查询索引表表项的时间开销
动态可重定位分区分配算法
不重要
空闲分区总和大于需求但无法找到单一连续可用区间时，进行紧凑
动态重定位分区分配算法与动态分区分配算法基本相同，差别在于增加了紧凑的功能
对换技术
贮存不足的存储管理技术有：移动（紧凑）、对换、覆盖
对换 (swapping)：将内存中不能运行的进程或暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把具备运行条件的进程和数据换入内存，也称交换。
对换是改善内存利用率的有效措施，实际上就是被挂起
对换类型
- 整体对换：即处理机低级调度（进程调度），上下文切换，以进程为单位
- 页面（分段）对换：按页或段进行对换，是请求分页、请求分段存储管理的基础
对换空间的管理
外存的划分：文件区、对换区
管理方式：空闲分区表、空闲分区链
分配算法：首次适应法、循环首次适应法、最佳适应法
进程的换入换出
换出
- 选择处于阻塞状态且优先级最低的进程
- 将该进程的程序和数据传送到磁盘的对换区上
- 回收内存空间，修改该进程的 PCB
换入
- 定时查看进程状态，选择就绪的换出进程
- 将处于就绪态的，换出时间最久的进程换入内存
分页存储管理方式
连续分配方式的不足，促使人们产生了离散分配的管理思想。从而引入了“分页”分配管理的管理方式。分为：基本分页（纯分页）和支持虚存管理的请求分页管理
连续内存分配方式：单一连续分配、固定分区分配、动态分区分配、动态可重定位分区分配
离散内存分配方式：分页存储管理方式、分段存储管理方式、段页式存储管理方式
页面与物理块（页框）
分页存储管理器将逻辑地址按页分割，将物理地址按块分割；
页面
将一个进程的逻辑地址空间分成若干个大小相等的区域，称为页面或页，并加以编号，从 0 开始；页内地址从 0 开始编址
页的大小一般为 2 的整数次幂
- 页面大小
- 过小，减小内存碎片；同时页表过长，降低页面换进换出的效率
- 过大，可以减少页表长度，提高页面换进换出效率；页面碎片增多
- 页面大小
物理块
将内存的物理空间分成若干个块
在为进程分配内存时，以块为单位，将进程的若干个页装入不相邻（离散）的物理块中。（会产生页内碎片）
地址结构
将逻辑地址分为：页号 P | 位移量 W（位移量即页内偏移地址）
页表
分页系统中，将进程的每一页离散地址存储在内存的任一物理块中；系统为每个进程设立一张页表。
✔️ 页表实现从页号到物理块号的映射
页表存放在内存中
实际上，页表并没有页号项，因为它是递增的，不需要记录
页表的表项有：物理块号（表现为指向页框的指针）和存取控制字段
每一个表目称为页描述子
地址变换机构
作用：实现从逻辑地址到物理地址的转换
基本的地址变换机构
页表设置一个页表寄存器（PTR），存放：
- 页表在内存中的始址（用来找到页表）
- 页表的长度（即页的个数，用来判断越界中断）
过程
- 逻辑地址分割后产生页号和偏移量
- 通过页表寄存器中页表长度和目标页号的比较，判断是否越界中断
- 如无中断则通过页表始址查询页表得到物理块号
- 页号 * 页表项长度 + 页表始址 = 该页号在页表中的位置（存储着对应的物理块号）
- 结合偏移量得到物理地址
每次存 / 取要两次访问内存（访问页表、访问内存找到物理地址）
具有快表的地址变换机构
联想寄存器 / 快表 / TLB：一个具有并行查询能力的特殊高速缓冲寄存器（不在内存）
过程：先查快表再查页表
一些计算
已知逻辑地址和页面大小，求其页号和页内地址
逻辑地址到物理地址
内存访问的有效时间
设访问内存时间为 t ，快表查询时间为 λ ，命中率为 a ：
- 不使用快表：$EAT=t+t=2t$
- 使用快表： $EAT=aλ+(1−a)(λ+t)+t$
两级和多级页表
- 多级页表直将需要的页表调入内存
- 不同被调入的页表离散存储在内存空间中
- 外层页表偏移页号指向内层页表地址，最后指向内存空间
反置页表
存进程标识和页号，以物理块号为下标的顺序表
逻辑地址：PID + 页号 + 页内偏移
内存中只有一张表
现代计算机系统允许一个进程逻辑地址空间远大于分配的内存空间。此时采用物理块号向页号反向查表更能节省页表的占用空间。在整个反置页表检索进程标识符和页号，找到匹配的页表项则将该项的物理块号（即下标）和页偏移地址合并作为物理地址。如果查不到，则表明该页号缺页，需要检索外部页表，并进行调页。
例
分段存储管理方式
程序按照逻辑关系天然地划分为段
引入
分页的意义
使内存的离散分配成为可能，提高内存利用率
分段的意义
- 方便编程：每个段始址为 0，转移直观
- 信息共享：段可以包含完整逻辑，方便共享
- 信息保护：段整体作为保护对象
- 动态增长：数据段的动态增加
- 动态链接：分段是动态链接的前提
分段基本原理
分段：分段地址划分决定了段的最大个数和每个段的最大内存长度（参考子网划分）
段表：记录段长和基址（在内存中的起始地址）
地址变换机构：同分页地址变换机构
分页和分段的区别
- 页是信息的物理单位，对用户透明；段是信息的逻辑单位，满足用户需要
- 页的大小由系统决定；段的大小由信息性质划分
- 分页的用户程序地址空间是一维的；分段的用户程序地址空间有二维（段页也是二维）
信息共享
分段易于实现程序和数据的共享
不同进程需要共享一个段（可重入代码），只需要相同基址即可
段页式存储管理方式
基本原理
将用户程序分为若干个段，再把每个段分成若干个页
逻辑地址：段号 | 段内页号 | 页内地址
段表：存放页表大小和页表始址
地址变换过程
段页式存储管理方式中，访问一条指令或数据需要访问三次内存
本章结构
存储器管理：
- 连续分配方式：
- 单一连续分配
- 分区式分配
- 固定分区分配
- 动态分区分配
- 基于顺序搜索的动态分区分配：FF、NF、BF、WF
- 基于索引搜索的动态分区分配：QF、Buddy、Hash
- 动态可重定位分区分配
- 离散分配方式：虚拟的必要条件
- 分页存储管理
- 基本分页存储管理
- 请求分页存储管理（虚拟存储器）
- 分段存储管理
- 基本分段存储管理
- 请求分段存储管理（虚拟存储器）
- 段页式存储管理
- 分页存储管理
第五章 虚拟存储器
虚拟存储器概述
将一个作业完整地装入内存可能发生的情况：
- 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行；
- 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。
虚存容量由主存辅存的容量之和确定
局部性原理
局部性原理是虚拟内存有效性的前提
- 时间局部性（短时间多次访问同一处）
- 空间局部性（短时间访问临近地址）
传统存储器的特征
- 一次性：作业一次性全部装入内存
- 驻留性：作业完整驻留在内存
虚存技术以 cpu 时间和外存空间换取昂贵的内存空间
虚拟存储器的定义和特征
定义：具有请求调入和置换功能，能从逻辑上对内存容量扩充的存储器系统
特征
- 多次性：一个作业的程序和数据允许多次调入内存
- 对换性：允许作业的程序和数据在运行时被换进换出
- 虚拟性：能从逻辑上扩充内存容量
请求分页存储管理方式
分页请求系统 = 分页存储 + 请求调页 + 页面置换
硬件支持
请求分页的页表机制
页表项除了物理块号外，添加状态位、访问字段、修改位和外存地址
缺页中断机构
（特殊的中断响应机构）
每当要访问的页面不在内存中时，就会产生一个缺页中断，请求系统将之调入内存
与一般中断的区别
缺页中断发生在指令执行期并立即响应。普通中断在微操作内不响应
执行一条指令可能发生多次缺页中断 (copy A to B 最高可达六次)
地址变换机构
添加缺页中断、页面写入或置换的过程
请求分页中的内存分配
最小物理块数确定
保证进程正常运行所需的最小物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式
取决于一次指令最多发生的缺页中断数
内存分配策略
分配策略：固定分配和可变分配
置换策略：全局置换和局部置换
- 固定分配局部置换：进程内存大小固定，置换被分配的页
- 可变分配全局置换：缺页即获得新的页面，直至内存占满开始置换
- 可变分配局部置换：置换被分配的页，若缺页太多增加内存大小
物理块分配算法
- 平均分配：进程平均分配内存
- 按比例分配：进程按需求占比分配
- 优先权分配：考虑紧迫程度（可分配内存分两部分，一部分按比例、，一部分按优先级）
页面调入策略
何时调入
- 预调页：一次性调入若干相邻的页
- 请求调页：一次只调入一页
何处调入
有足够的对换区空间：全部从对换区调入，提高调页速度（需要提前将有关文件从文件去拷贝至对换区）
缺少足够的对换区空间
- 不会修改的文件从文件区调入；
- 可能被修改的文件，在换出时放到对换区，之后调入都从对换区调入
UNIX 方式
- 未运行文件从文件区调入
- 曾运行过但被换出的文件被放入对换区，下次调入时从对换区调入
- 页面共享时无需从对换区调入
调入过程
缺页率
影响缺页率的因素
- 页面大小
- 进程分配物理块数
- 页面置换算法
- 程序固有特性
页面置换算法 ⭐
最佳置换算法 OPT
置换了 6 次，缺页了 9 次
先进先出置换 FIFO
总是淘汰最先进入内存的页面；建立替换指针始终指向最老的页面
现象：页框数越多，缺页次数反而增加
最近最久未使用 LRU
Least Rencently Used
移位寄存器值最小的被替换
硬件支持
寄存器
具有最小值的寄存器所对应的页面，就是最近最久未使用的页面
栈
最少使用 LFU
移位寄存器 pop_count 最小的被替换
最近未使用 NRU（简单 CLOCK 置换）
置换最近未使用的页面
页表设置访问位，指针连成循环链表
改进 CLOCK 置换
页表设置访问位、修改位；访问位优先权高
页面缓冲算法 PBA
（不考）
Page Buffering Algorithm，是对 FIFO 的发展
影响请求分页存储管理的因素：页面置换算法，磁盘写回频率，内存读入频率
系统保留一片空闲物理块用以降低经常缺页的进程的缺页率：
- 空闲页面链表：将进程换下的未修改页面暂存。减少读入频率
- 修改页面链表：将进程换下的修改页面暂存。减少读入频率；成批写入，减少写回频率
访问内存的有效时间
设访问/更新快表时间 λ，访问内存需要时间 t ，缺页中断时间 ε
- 页面在快表中： EAT=λ+t（查快表 → 访内存查值）
- 页面在页表中： EAT=λ+t+λ+t（查快表 → 访内存查页表 → 更新快表 → 访内存查值）
- 缺页：EAT=λ+t+ε+λ+t（快表 → 页表 → 中断 → 更新快表 → 访内存查值）
设命中率 a，缺页率 f ，则平均访问时间：
EAT=a(λ+t)+(1−a)((1−f)(2λ+2t)+f(2λ+2t+ε))=(2−a)(λ+t)+εf(1−a)EAT=a(λ+t)+(1−a)((1−f)(2λ+2t)+f(2λ+2t+ε))=(2−a)(λ+t)+εf(1−a)
2，1，0，2
抖动和工作集
多道程序度与抖动
抖动：在请求分页存储管理中，反复出现从主存中刚换出一页根据请求马上又换入的现象，调用页面时间甚至比程序实际运行的时间还多
表现：随着进程数增多，处理机利用率先增大后减小
产生原因：系统中运行进程太多，分配给每一个进程的物理块太少，进程内存分配无法满足正常运行的基本需求
工作集
工作集：某段时间间隔 $\Delta$ 里进程实际要访问的页面集合
记录工作集，置换不在工作集内的页面，过去某时段内作为其将来时段的近似
预防抖动的办法
局部置换
不允许进程扩展页数，将抖动限制在一些进程上（效果差）
引入工作集算法
比较各进程工作集大小和实际得到的内存，再决定是否增加进程
L = S 准则
使缺页平均间隔 = 调页平均时间
挂起
选择进程暂停
请求分段存储管理方式
请求分段中的硬件支持
请求段表机制
- 段名、段长、段基址
- 存取方式：控制读写执行，实行逻辑保护
- 访问字段：访问频繁程度
- 修改位：是否被修改
- 存在位：是否在内存中
- 增补位：该段是否在运行中发生了动态增长
- 外存始址：盘块号
缺段中断机构
地址变换机构
分段的共享与保护
共享
段表中增加进程计数 count（参考 shared_ptr）
每个进程存取控制字段独立
每个进程使用自己的段号访问
共享：count++，增加表项；回收：count–，删除表项
保护
越界检查：检查段长
存取控制检查：检查读写执行权限
环保护机构：为段设置编号，高编号不允许调用低编号的段
第六章 输入输出系统
概念考核
IO 系统的功能、模型、接口
IO 系统：用于管理诸如打印机扫描仪等 IO 设备，和诸如磁盘驱动器等存储设备
IO 系统的基本功能
- 方便用户使用（隐藏性）
- 隐藏物理设备细节：IO 设备是怎么进行读写的
- 与设备的无关性：允许用户和 OS 适应不同的 IO 设备，即插即用
- 提高 CPU 和 IO 设备利用率（效率）
- 提高 CPU 和 IO 设备利用率：设备间的独立性 ==> CPU-IO 并行、IO-IO 并行
- 控制 IO 设备：独立进行 IO 而无需 CPU 干预，向上层提供统一接口
- 方便用户共享，保证系统有条不紊运行（正确性）
- 确保对设备的正确共享：对独占设备（打印机）和共享设备（磁盘）的管理
- 错误处理：处理电气偶然性错误
IO 系统的层次结构
- 用户层软件：属于应用程序
- 向用户提供交互接口、库函数
- 产生 IO 请求、格式化 IO、Spooling
- 设备独立性软件：属于 IO 系统
- 实现用户程序和设备驱动程序的统一接口、设备命名保护分配释放、分配存储空间
- 映射、保护、分块、缓冲、分配
- 设备驱动程序：属于 IO 系统
- 具体实现系统对设备发出的操作指令，驱动 IO 设备工作
- 设置设备寄存器、检查设备状态
- 将上层发来的 IO 请求转化为对 IO 设备的具体命令和参数
- 中断处理程序：属于 IO 系统
- 用于保护被中断进程的 CPU 环境，在处理完毕后进行恢复
- IO 系统最底层，直接与硬件交互
- 设备控制器：属于硬件
- 执行 IO 操作
IO 系统接口
位于用户层软件和设备独立性软件之间
- 块设备接口：为磁盘等以块为基本单位提供数据传输的接口
- 流设备接口：为字符设备提供数据传输的接口
- 网络接口：为网络通信提供数据传输的接口
软硬件接口（RW/HW 接口）：位于中断处理控制器和设备控制器之间
设备控制器和 IO 设备
IO 设备：执行 IO 操作的机械部分（IO 设备）+ 控制 IO 的电子部件（IO 设备控制器）
IO 设备类型
按使用特性分类
- 存储设备
- IO 设备（输入设备、输出设备、交互设备）
按传输速率分类
- 低速设备
- 中速设备（打印机）
- 高速设备
按信息交换的单位分类
- 块设备（有结构、可寻址）
- 字符设备（无结构、不可寻址）
- 网络设备
按资源分配角度分类（共享属性）
- 独占设备（打印机）
- 共享设备（磁盘）
- 虚拟设备（将独占变成共享）
IO 设备与设备控制器的接口
- 数据信号线：外部数据 ==> 转换器 ==> 缓冲器 ==> 数据信号线 ==> 设备控制器
- 控制信号线：规定设备即将执行的操作（读 / 写）
- 状态信号线：设备在读、在写、或准备完成
设备控制器
功能
- 接收和识别命令（控制寄存器接受并译码）
- CPU、设备控制器与 IO 设备之间的数据交换
- 识别和报告设备状态（状态寄存器）
- 地址识别（地址译码器）
- 数据缓冲
- 差错控制
组成
- 设备控制器与处理机的接口
- 设备控制器与设备的接口
- IO 逻辑
内存映像 IO
内存地址和设备寄存器地址合并编址，简化设备控制器地址识别
IO 通道
一种只具备 IO 处理能力的特殊处理机，减轻 CPU 负担
通道类型
- 字节多路通道：多个设备以字节为单位轮转。适合低速设备
- 数组选择通道：一次只允许一个设备工作。适合高速设备
- 数组多路通道：两者结合
IO 通道的瓶颈问题
由于通道昂贵，独占性且数量较少，造成其为系统吞吐量的瓶颈。
解决方法：复联增加设备到主机间的通路而不增加通道
中断处理程序和中断机构
中断简介
中断是 CPU 对 IO 设备发来的中断信号的一种响应
中断是设备管理的基础：
- 外中断（广义上的中断）：CPU 暂停正在执行的程序，而执行 IO 设备的中断处理程序，事后恢复
- 内中断（陷入）：计算故障、非法指令等，来源为 CPU 内部
中断向量表：为每种设备配备中断处理程序，将程序入口地址存放在中断向量表中
中断优先级：多中断源处理方式：屏蔽中断、嵌套中断
对多中断源的处理方式
- 屏蔽（禁止）中断
- 嵌套中断
中断处理程序
进行上下文切换、对中断信号源测试、读取设备状态、修改进程状态
中断过程：
- 测定是否有未响应中断信号
- 保护被中断进程的 CPU 环境
- 查询中断向量表，转入相应的设备处理程序
- 进行中断处理
- 恢复 CPU 现场
设备驱动程序
主要任务：抽象
- 接收上层发来的抽象 IO 请求并转化为具体请求发送给设备控制器进行数据传送
- 检查 IO 请求合法性，了解 IO 设备状态，传递操作参数
- 对空闲的 IO 设备发出 IO 命令，或将请求挂在等待队列中
- 相应设备控制器的中断请求，并根据类型处理
对 IO 设备的控制方式
（轮询）程序 IO 方式
CPU 不断查询 IO 状态直至设备空闲允许 IO
中断驱动 IO 方式
设备控制器完成一字符 IO 后发送中断请求（CPU、IO 并行）
DMA 方式
一批连续数据块全部传送结束时才中断 CPU
IO 通道方式
控制多台设备与内存数据交换，完全接管 CPU
设备独立性软件
(Device Independence，也叫设备独立性软件)
设备独立性：应用程序中所用的设备，不局限于使用具体某个物理设备
设备独立性软件的主要任务
实现 OS 的物理设备独立性，可适应性和可扩展性
- 提供设备驱动程序的统一接口
- 缓冲管理：单缓冲、双缓冲、循环缓冲、公用缓冲池
- 差错控制：重试暂时性错误、记录永久性错误
- 对独立设备的分配和回收
- 独立于设备的逻辑数据块
设备分配
设备分配中的数据结构
- 设备控制表 DCT：类似 PCB，记录设备基本信息和当前状态
- 控制器控制表 COCT：记录设备控制器的基本信息和当前状态
- 通道控制表 CHCT：记录通道的基本信息和当前状态
- 系统设置表 SDT：记录系统中所有设备类型和 DCT 入口等信息
设备分配考虑的因素：
- 设备固有属性：独占、共享、虚拟（独占设备改造成可共享的虚拟设备）
- 设备分配算法：FCFS、高优先级优先
- 安全性问题：可能造成死锁
用户层的 IO 软件
系统调用和库函数
- 系统调用：应用程序取得 OS 任何服务的唯一途径，汇编级
- 库函数：对系统调用的进一步封装
假脱机系统 Spooling
作用：将一台物理 IO 设备虚拟为多台逻辑 IO 设备，从而允许多个用户共享
多道程序系统使用若干个进程接管 IO 设备的 IO，使用磁盘进行数据暂存
组成
- 输入输出井：磁盘上开辟的区域，用于接收和传输数据
- 输入输出缓冲区：内存上开辟的区域，用于缓冲 CPU 和磁盘速度差异
- 输入输出进程：管理 IO 设备、缓冲区和输入输出井的数据流动
- 井管理程序：井的创建和取消
特点
- 提高了 IO 速度：使用磁盘缓解了 CPU 和低速 IO 设备的速度差异
- 独占设备改造为共享设备：多个进程共享独占设备（如打印机）
- 实现了虚拟设备功能：多个进程认为独占了设备
缓冲区管理
缓冲区：用内存或硬件组成的小的存储区域（一般是内存）
- 缓和 CPU 和 IO 设备速度不匹配的矛盾
- 减少 CPU 中断频率
- 解决数据粒度不匹配问题
- 提高 CPU 和 IO 设备之间的并行性
缓冲区管理：组织好缓冲区，并提供获得和释放缓冲区的手段
- 单缓冲区：缓冲区被填满后需要被取用才能继续填写
- 双缓冲区（缓冲对换）：第二块缓冲区填满后才被阻塞；或同时允许输入输出的双向操作
- 环形缓冲区：n 缓冲区，采用队列的数组存储形式
- 缓冲池：缓冲池公用缓冲区以减少不同 IO 进程对内存的浪费
- 缓冲池组成：空白缓冲队列 emq、输入队列 inq、输出队列 outq
- 缓冲区工作方式：hin 收容输入、sin 提取输出、hout 收容输出、sout 提取输出
磁盘存储器的性能和调度
数据的组织格式：
- 盘片 ≠ 盘面：1 磁盘片有 1-2 个磁盘面
- 磁道 = 柱面：传统磁盘中内磁道存储密度高
- 扇区 = 盘块：一条磁道由若干扇区组成
磁盘类型：固定磁头磁盘（快），移动磁头磁盘（慢）
磁盘访问时间
磁盘访问时间 = 寻道时间 + 旋转延迟时间 + 平均访问时间
- 寻道时间： $T_s=m×n+s$（将磁头定位到目标磁道所需的时间）
- 旋转延迟时间（平均）： $T_τ=\frac{1}{2r}$（将磁头定位到目标扇区所需的时间）
- 传输时间： $T_t=\frac{b}{rN}$（读取一个扇区的时间）
平均访问时间： $T_a=T_s+T_τ+T_t$
$r$：转速，转/分
$b$：每次读/写的字节数
$N$：一条磁道上的字节数
$s$：启动磁头臂的时间（固定）
$m\times n$：跨越一个磁道的耗时 × 磁道数
磁盘调度算法
先来先服务 FCFS
效果很差，未优化，平均寻道时间长
最短寻道时间优先 SSTF
要求访问的磁道离当前磁头所在磁道最近
产生饥饿现象
扫描算法（电梯调度）SCAN
磁头由外而内扫描再由内而外扫描
同方向距离最近的优先扫描
循环扫描 CSCAN
一直同向循环扫描，避免极端情况等待时间过长
NStepSCAN
N 个队列间 FCFS，队列内 SCAN。解决高密度磁盘磁壁粘着现象（磁臂停留在某处不动）
FSCAN
N=2 的 NStepSCAN，当前队列和新增需求队列
第七章 文件管理
前三节重要
文件和文件系统
文件系统：操作系统中与管理文件有关的软件和数据。
数据的组成部分：数据项、记录、文件
- 数据项：最低级的数据组织方式
- 基本数据项：用于描述一个对象的某种属性
- 组合数据项：基本数据项的组合
- 记录：一组相关数据项的组合，用于描述对象的某方面属性
- 文件：文件系统最大的数据单位，描述一个对象集
- 有结构文件：记录项的集合
- 无结构文件：字符流
- 文件属性：类型、长度、物理位置、建立时间
- 文件名和扩展名
- 文件类型：
- 用途（系统、用户）
- 数据形式（源、目标、可执行）
- 存取属性（只执行、只读、读写）
- 组织方式（普通、目录、特殊）
文件系统的层次结构
对象及其属性（底层）：管理文件及其物理地址
对对象操纵和管理的软件集合（中间层）：管理存储，权限，共享，逻辑 → 物理转化
文件系统的接口（最高层）：向用户提供命令接口和程序接口
文件操作
基本文件操作
- 创建：分配外存空间，父目录创建目录项，目录项记录文件名和外存地址等属性
- 删除：删除父目录下对应目录项，回收外存空间
- 读：根据文件名查找目录得到外存位置
- 写：根据文件名查找目录得到外存位置
- 设置文件读写位置：文件目录项中存有读写指针
打开和关闭操作
避免在多次读写时重复检索目录
- 打开：将文件的属性从外存拷贝到内存的文件打开表表项中，并将编号返回用户
- 关闭：把文件从文件打开表表目中删除
其他文件操作
- 修改文件属性：改变文件名、拥有者、权限，查询文件状态等
- 目录操作：创建目录，删除目录，更改工作目录
- 实现文件共享，对文件进行系统操作
文件的逻辑结构
文件的逻辑结构：区别于文件的物理结构，是从用户角度出发所观察到的文件组织形式。
文件的逻辑结构管理的是记录。
按结构分类
有结构文件（记录式文件）：定长记录、不定长记录（记录长度而非文件长度）
无结构文件（流式文件）：长度以字节为单位
按组织方式分类
在用户看来，文件是什么结构
- 顺序文件：按某种顺序排列保存；定长随机访问
- 不定长查找一条记录平均检索 $\frac{N}{2}$ 次，适合定长文件
- 分类
- 串结构：按存入时间先后排序
- 顺序结构：指定某个关键字
- 缺点
- 查找修改慢
- 增删操作困难
- 索引文件：针对不定长记录建立索引表，以根据索引进行折半查找，索引速度快，适合索引文件
- 索引本身是个定长的顺序文件
- 一级索引 $\sqrt{N}$ 组，每组 $\sqrt{N}$ 条记录，平均查找次数为 $\sqrt{N}$
- 索引顺序文件：最常见，u 级顺序索引平均检索 u2N−−√uu2Nu 次
- 将记录分组，组间顺序，组内索引
- 直接文件、哈希文件
文件目录
文件目录：文件控制块的有序集合
目录文件：存放文件目录的文件（一般，一个文件目录被称为一个目录文件）
目录管理：实现按名存取、提高目录检索速度、文件共享、允许不同用户的文件重名
文件控制块 FCB
用于描述和控制文件的数据结构，一般放在磁盘上
- 基本信息：文件名、物理位置、逻辑结构、物理结构
- 存取控制信息：拥有者、核准用户、一般用户的读写执行权限
- 使用信息：建立日期、修改日期、打开状态、状态信息
索引节点 inode
减少目录文件占用的盘块数，加快检索
使用了 inode 后的文件目录只存储文件名和 inode 编号（指向索引节点的指针），通过 inode 编号可以在 inode 区找到具体的文件信息
磁盘索引节点和内存索引节点
目录结构
重点是多级目录结构
单级目录结构
整个文件系统就一张目录表，每个文件占一项
两级目录结构
主目录 MFD 记录每个用户文件目录 UFD 的信息
树形目录结构
主目录为根目录，数据为树叶，目录项可能是数据文件的 FCB 或目录文件的 FCB
- 路径名：从根目录到目标文件的路径
- 当前目录：工作目录
- 相对路径：从当前目录到目标文件的路径
- 绝对路径：从根目录到目标文件的路径
- 目录操作：创建、删除（空/非空）、改变当前目录、移动目录、链接、查找
目录查询技术
线性检索法：在每个文件目录中顺序查找目录项
Hash 方法：文件名变换为文件目录的索引值
文件共享
文件共享：允许多个用户（进程）共享同一份文件而只保留一份副本。
- 基于 DAG 的文件共享：拷贝文件的物理地址（拷贝 FCB）
- 硬链接：文件目录存同一份 inode 编号，inode 进行链接计数。删除一份不会消失
- 软链接（符号链接）：建立 LINK 文件储存被共享文件路径
文件保护
- 保护域
- 访问矩阵
- 访问控制表
- 访问权限表
第八章 磁盘存储器管理
第八章
外存的组织方式
外存的组织方式：决定了文件的物理结构
连续组织方式
（连续）每个文件分配一片连续的盘块
- 文件目录项存储第一个盘块和长度
- 优点：便于顺序访问，速度快，支持定长记录文件随机存取
- 缺点：盘块连续，预知文件大小，增删记录慢，不能动态增长，需要紧凑
链接组织方式
（离散）将文件存储到离散的盘块中
隐式链接
每个盘块存储下一个盘块的指针
- 文件目录项存储第一个盘块和最后一个盘块的指针
- 优点：离散存储，便于顺序访问
- 缺点：随机存取效率低，必须顺序存取，不支持随机查找
- 改进：多个连续盘块形成一个簇，减少指针开销并提高检索速度
显式链接
在内存中建长度为物理块数的 FAT 表，表项存放下一盘块指针，而凡是某个文件的起始盘块号都存放在文件 FCB 的“物理地址字段”中
- 优点：查找记录在内存中进行，大量减少磁盘访问，检索速度快
- 缺点：FAT 很大，占用内存空间，仍然不支持随机存储
- FAT 与 NTFS 的概念
- 优点：消除外碎片，支持文件动态增长，适合增删改
- 缺点：只适合顺序存储，可靠性差，读取时寻道次数多，额外存储空间开销大
为了地址转换的方便，FAT 表项的大小通常取半个字节的整数倍
MS-DOS 采用此方法
索引组织方式
（离散）为每个文件分配索引块（一盘块），顺序存储全部盘块号（相当于一个索引表）
单级索引组织：索引块顺序存储各盘块号，文件容量较小
- 最大文件大小计算：一个盘块块能存储的最大盘号数 × 一个盘块的大小
多级索引组织：一级索引块存储二级索引盘块号，小容量文件浪费存储空间
增量索引式组织
混合索引，全面照顾大中小型文件（考大题）
- 索引结点有 13 个地址项
- 直接地址 10 个
- 一次间址、二次间址、三次间址各 1 个
UNIX 使用此种方式
文件存储空间管理
任何文件组织方式都必须要为文件分配盘块，需要知道磁盘中哪些盘块是可供分配的。
空闲表法
（连续）存第一块空闲盘号和盘块数 → 4.3
空闲链表法
- 空闲盘块链：（离散）将空闲盘块组成链表，效率很低
- 空闲盘区链：（连续）将连续的盘块组成盘区，记录块首地址、盘块数、双向链表
位示图法
使用 1bit 标识盘块使用情况，本质是一个二维数组
成组链接法
https://blog.csdn.net/qq_45744501/article/details/116953538
（大型系统）内存常驻空闲盘块号栈（记录栈和栈顶指针，栈内存空闲盘块号）。分配到最后一个时取出栈底盘块中的有用信息替换栈后再分配；回收满了则将栈信息存入当前回收的盘块并将当前回收盘块作为新栈底。
8.3 提高磁盘 IO 速度的途径
8.4 提高磁盘可靠性的技术
8.5 数据一致性控制
（事务）