四、设备管理
1、I/O软件
/O设备管理软件一般分为4层：中断处理程序、设备驱动程序、设备无关软件、用户级软件。如图。
硬件：完成具体的 I/O 操作。
中断处理程序：I/O 完成后唤醒设备驱动程序
设备驱动程序：设置寄存器，检查设备状态
设备无关 I/O 层：设备名解析、阻塞进程、分配缓冲区
用户级 I/O 层：发出 I/O 调用。
2、相关技术
（1）程序查询方式（CPU 一直处于询问、等待的过程，占用 CPU 时间最长，CPU 利用率最低）；
（2）中断方式（I/O 完成后向 CPU 发送中断请求信号，CPU 和 I/O 可以并行）；
（3）直接主存存取DMA（CPU 只做初始化，不参与具体数据传输过程）：指数据在主存与I/O设备间直接成块传送，不需要CPU干涉，只需要CPU做初始化，实际操作由DMA硬件直接执行完成。
（4）通道方式：引入通道的目的是数据传输独立于CPU。在设置通道后，CPU只需要向通道发出I/O命令，通道来执行命令，仅当通道在完成I/O指令后才向CPU发出中断信号。
3、磁盘调度
磁盘调度分为移臂调度和旋转调度，并且是先进行移臂调度，然后进行旋转调度。
（1）存取时间=寻道时间+等待时间
寻道时间是指磁头移动到磁道所需的时间；
等待时间为等待读写的扇区转到磁头下方所用的时间，有时还需要加上数据的传输时间。
（2）磁盘调度算法
【1】先来先服务 FCFS（谁先申请先服务谁）；
【2】最短寻道时间优先 SSTF（申请时判断与磁头当前位置的距离，谁短先服务谁）；
【3】扫描算法SCAN（电梯算法，双向扫描）；
【4】循环扫描 CSCAN（单向扫描）
（移臂时只需要考虑柱面信息即可，扇区不需要考虑，同一柱面的多个扇区先后顺序随机）
（3）单缓冲区
在处理过程中，如果有关于缓冲区的使用，需要明白对于单缓冲区每次只能被一个进程使用，即向缓冲区传输数据的时候不能从缓冲区读取数据，反之亦然。
（4）优化存储
对于磁盘存储的优化是因为磁头始终保持转动状态，当读取数据在传输或处理时，磁头会移动到超前的位置，需要继续旋转才能回到逻辑下一磁盘块；优化存储就是调整磁盘块的位置，让逻辑下一磁盘块放到磁头将要开始读取该逻辑块的位置。
五、文件管理
1、绝对路径与相对路径（★★★）
（1）绝对路径从根目录开始写起，并且该文件的全名即为绝对路径+文件名。
（2）相对路径从当前位置下一级目录开始写起。
2、存储空间管理
【1】空闲区表
【2】位示图（★★）
在外存上建立一张位示图，记录文件存储器的使用情况。每一bit位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。
位示图按字进行分组，根据不同的计算机，具体一个字多长，一个字占多少bit位也不同；
【3】空闲块链
【4】成组链接法
3、索引文件结构（★★）
（1）基本概念
【1】直接索引：索引结点（线索）---->地址指向----->物理块号，结点编号的直接指向物理块，物理块里存储的是文件本身（文件的逻辑页，文件的数据），在直接索引中索引编号是连续的，对应物理块中的逻辑页也是连续的；
【2】一级间接索引：索引结点（线索）---->一级间接索引表----->物理块号，结点编号不直接指向物理块，而是指向一级间接索引表，由一级间接索引表编号指向物理块；
【3】二级间接索引：索引结点（线索）---->一级间接索引表----->二级间接索引表----->物理块号，结点编号不直接指向物理块，而是指向两次间接索引表，经过两次间接索引表编号最后指向物理块；
【4】三级间接索引：索引结点（线索）---->一级间接索引表----->二级间接索引表----->三级间接索引表----->物理块号，结点编号不直接指向物理块，而是指向三次间接索引表，经过三次间接索引表编号最后指向物理块；
一般的索引文件结构由 13 个结点组成，其中 0 - 9 个结点为直接的物理盘块（直接索引），第 10 个结点是一级间接索引，第 11 个结点是二级间接索引，第 12 个结点是三级间接索引。
（2）索引扩展原理
【1】如果一个存储结构不使用索引，那么他的容量= 物理块数 * 单位大小。
例如，如果每个物理块的单位大小为 4K，则总空间为 52K，如下图所示。
【2】如果引入了一级间接索引，索引指向了具体的物理块号，如下图所示。
如果一个地址占用 4 个字节，一个物理盘块有 4KB 容量，那么在第 10 个物理块中就可以存放 1024 （=4KB/4B）份地址，那么 10 号物理块就可以存储 1024 份容量，就是 1024 X 4KB = 4MB 的容量。
【3】如果引入了二级间接索引，索引指向了中间索引，中间索引在指向具体的物理块号，如下图所示。
如果一个地址占用 4 个字节，一个物理盘块有 4KB 容量，那么在第 11 个物理块中就可以存放 1024 份地址，每份子地址可以再存储 1024 份二级地址，那么 11 号物理块就可以存储 1024 * 1024 份容量，就是 1024 X 1024 X 4KB = 4GB 的容量。
（3）解题思路
【例题】现有一个文件系统采用索引结点管理模式，物理块大小为 1KB。 每个索引结点有 32KB 的存储空间，每个地址项占 4 字节，磁盘索引块和磁盘数据块大小均为 1KB。 其中 0 - 4 用直接地址索引，5 - 6 用一级间接地址索引，7 用二级间接地址索引，逻辑块号为 5 和 261 的物理块号在哪里？
【解题思路】逻辑块号从 0 开始编码，物理块号从 1 开始编码，所以逻辑块号 5 就代表第六块。每个地址项占 4 字节，磁盘索引块大小均为 1KB，所以一个物理块可以存放 256 份地址。 第 5 个逻辑块号的物理块号位置如下所示。
第 261 个逻辑块号的物理块号位置如下所示。
1、索引结点对应的索引方式一般题干会给出，没有给出的默认按照如图所示方式理解，下面的文件大小依图给出计算过程。
2、根据物理块大小（假设 1KB）和地址项长度（假设 4B），可以计算地址项个数=物理块大小/地址项长度，向下取整（1KB/4B =256，注意单位和进制转换）。
3、直接索引（即索引结点直接指向实际存储文件的物理块），能够表示的逻辑页号范围是 0~9，能够表示的文件大小时 10*1KB。
4、一级间接索引（即索引结点指向的物理块存放的是地址项，对应地址项个数256 个，可以指向 256 个实际存储文件的物理块），能够表示的逻辑页号范围是10~265，能够表示的文件大小是 256*1KB。
5、二级间接索引（即索引结点指向的物理块存放的是间接索引的地址项，共 256个，可以指向 256 个存放地址项的物理块，每个物理块指向实际存储文件的地址项有256 个，最终指向的物理块共有 256*256 个），能够表示的逻辑页号范围是266~ 65801，能够表示的文件大小是 65536KB。
六、总 结
笔记总结不易，如果喜欢，请关注、点赞、收藏。
完整笔记下载地址：（后续完成后更新）
基础精讲课件地址：（请关注、点赞、收藏后，私信我）
基础精讲视频地址：（请私信我）
