操作系统4：磁盘与I/O

Chapter 10. File-System Interface

10.1 文件

文件是存储在某种介质上的并且具有文件名的一组信息的集合，分为数据和程序
- 文件具有很多属性，比如name，type，location，size，protection等等
- 文件是一种抽象数据类型，可以进行创建、读写、删除等操作
- 打开文件需要：
  - 文件指针，指向上次读写位置的指针
  - 文件打开次数的计数器，记录文件被打开的次数，当最后一个进程关闭文件的时候就从打开文件的记录表中移除这个文件名
  - 文件的磁盘位置
  - 访问权限
- 文件的结构
  - 流文件结构：字符流或者字节流
  - 记录文件结构：按照行或者定长、变长的段来存储
  - 复杂结构：格式化文档、可重定位加载文件

10.2 文件访问的方式

三种存取方式
- 顺序存取：按照顺序读取文件中的内容，有一个当前位置的指针，读写一次都前进一格，也可以将指针reset
- 直接存取：可以直接读写n个字符
- 索引顺序

10.3 文件目录

磁盘的结构
- 磁盘可以划分成若干个分区，每个分区都有目录和文件
- RAID可以防止磁盘或者分区failure
目录
- 可以搜索、创建、删除、重命名、遍历文件
- 分类：
  - 单级目录
  - 多级目录
  - 树形目录：搜索速度快
    - 绝对路径和相对路径的区别
  - 无环图目录：允许项目有共享的子目录和文件，同一个文件或者目录可以出现在两个不同的目录中
    - 共享文件的实现方式是创建一个链接，链接实际上是指向另一个文件或者目录的指针，但是无环图必须是无环的，
    - 删除链接并不影响原文件而只是删除链接，当原文件被删除的时候链接也会被删除，也可以暂时不管这些指针，而是等使用的时候再发现原来的文件已经被删除
    - 也可以使用一个文件引用表，在删除所有链接之前不能删除文件，UNIX系统中采用了硬链接的方式，在inode中记录文件被引用量
  - 通用图目录

10.4 文件系统安装

文件系统在访问之间必须要进行挂载

10.5 文件共享和保护

网络文件系统：常见的分布式文件共享方式
多用户系统中可以使用用户id和组id标识文件和访问权限
Linux/Unix系统中，文件的权限分为读写执行三种，用RWX分别表示三种权限，用户/小组的权限可以用一个数字来表示，执行用1表示，读是2，写是4，用一个0-7之间的数字来表示用户的权限，比如5=4+1表示可以写和执行，7=4+2+1可以读写执行

Chapter11：File System Implementation

11.1 文件系统的分层

文件系统
- 位于二级存储中，即被存储在磁盘中
- 是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构的集合
- 文件控制块FCB：存储文件的结构
- 设备驱动器控制物理设备
- 分层的文件系统设计：
  - 逻辑文件系统：管理各类文件的元数据，即文件系统的所有数据结构，而没有实际的数据，或者文件内容，根据给定的符号文件名来管理目录结构，逻辑文件系统通过FCB来维护文件的结构
  - 文件组织模块：知道文件对应的逻辑块和物理块
  - 基本文件系统：向合适的设备驱动程序发送一般命令就可以对磁盘上的物理块进行读写
  - I/O控制：由设备驱动程序和中断处理程序组成，实现内存和磁盘之间的I/O
- 常见的文件系统
  - FAT用于MS-DOS中的文件系统，FAT32（VFAT）是Windows98中的文件系统，NTFS是最新的Windows文件系统
  - ext系列是Linux操作系统中使用的文件系统，proc是Linux的虚拟文件系统，yaffs是闪存文件系统
  - HFS+是macOS和iOS上的文件系统
  - NFS网络文件系统
  - VFS是Linux使用的一个虚拟文件系统是物理文件系统和服务之间的借口，给用户和程序提供了统一的接口（系统调用）

11.2 文件系统的实现

磁盘上的文件结构
- 在磁盘上，文件系统包括如下信息：
  - 如何启动存储的操作系统 boot control block
  - 总的块数，空闲块的数目和位置
  - 目录结构和各个具体的FCB
- FCB包括文件的权限、时间信息、大小、所有者、数据块或者数据块的指针
内存中的文件结构
- 分区表
- 目录结构
- 系统打开文件表
- 进程打开文件表

11.3 文件目录的实现

线性检索法：按照线性遍历查找所有的文件
- 程序实现比较简单
- 缺点是非常耗时
哈希表：减少了目录搜索的时间，但可能会引发冲突
索引：用的比较多，如B+树索引

11.4 文件物理结构

分配方式：磁盘块如何被分配给文件
- 连续分配：每个文件分配一系列连续的磁盘块，优点是简单但是浪费空间
  - 允许随机访问
  - 文件的size不能增长否则就要换块，可以采用defragmentation机制
  - 存在一个逻辑地址向纹理地址转换的机制，LA/512=Q…R
  - 基于长度的分配
- 连接分配：每个文件是若干磁盘块组成的链表，一个block包含数据和指针
  - 不允许随机访问，逻辑地址/块的数据位大小=Q…R
  - FAT(File-allocation table)文件系统就是连接分配的，FAT32有一个引导区，而文件分配表维护了一系列文件的链表
  - NTFS卷布局：引导系统，主文件表，文件区，MFT前16个元数据文件备份，文件区
    - 每个分区有一个主文件表MFT，用数据库形式组织，每条记录长度是1K
- 索引分配：
  - 用索引块专门存放所有的指针，每个文件使用一个索引块，包含文件所使用的块的地址
  - 分为一级索引和二级索引等形式
  - 链接索引：索引块组成的链表
- Linux的ext2/ext3以及Unix的UFS采用了混合分配机制 ##Chapter 12：大容量存储系统
存储器的体系结构，二三级都是大容量存储器

常见的大容量存储器
- 磁盘：可拆卸，通过总线连接到计算机
  - 总线的种类很多，有EIDE, ATA, SATA, USB, Fibre Channel, SCSI等等
- 固态驱动器：Solid State Drives，简称SSD，也叫固态硬盘，由控制单元和存储单元（FLASH或者DRAM）组成
- 磁带：LTFS(Liner Tape File System)为磁带提供了一种通用、开放的文件系统

###12.1 磁盘结构

磁盘的地址被分为若干个逻辑块的一位数组，一般逻辑块的大小是512字节
- 逻辑块的数组被映射到扇区中
- 扇区0是第一个磁道上的第一个扇区
- 映射的顺序是从一个磁道用完之后，使用同一个cylinder中的其他磁道，然后从cylinder从外到内

Network-attached storage(NAS) 通过网络来存储
Storage Area Network(SAN)

虚拟化存储技术
- 是将存储（子）系统内部功能与具体应用、主机及通用网络资源分离、隐藏及抽象的行为。以期达到存储或数据管理的网络无关性
- 对于存储服务及设备的虚拟化应用，以期达到整合设备功能、隐藏复杂细节以及向已经存在的底层存储资源添加新的应用

###12.2 磁盘的调度

磁盘的访问时间有三个主要影响因素
- 寻道时间：将读写头移动到对应的扇区中所需要的时间
- Rotational latency旋转延迟：将扇区旋转到读写头对齐所需要的额外的时间
  - 可以通过转速来计算，平均需要旋转半圈
- Transfer Time传输时间：读写所需要的时间
磁盘的调度算法：
- 先来先服务(FCFS)：按照需要的顺序来调度磁盘中的内容
- 最短寻道时间优先(SSTF)：先选择需要的寻道时间最短的磁盘进行调度
- 扫描(SCAN)算法：先往start或者end扫描，然后再反方向扫描，读取需要的扇区，也叫电梯算法
- 循环扫描(C-SCAN)算法：到一头之后直接返回另一端，再扫描一次
- C-LOOK：SCAN的升级版，往一端去的时候，到了最后一个请求就直接折返，不死磕到底
- 总结：
  - 扫描类算法在大规模的系统中效果更好，算法的性能取决于磁盘访问请求的数量和类型
  - 磁盘调度算法应该在操作系统中单独写成一个模块，方便被其他的算法替换。

###12.3 磁盘的管理

磁盘管理
启动块 Boot Block存储在ROM中，启动的时候，先启动ROM中的代码，然后是启动块中的代码，然后是整个OS内核

###12.4 Swap-Space Management 交换空间管理

交换空间是因为虚拟内存将磁盘空间作为内存的扩展，因此需要大量的交换
- Windows中用pagefile.sys来存储交换空间的信息
- Linux和Unix系统中划分了专门的磁盘分区

###12.5 RAID结构

RAID的全称是Redundant Arrays of Inexpensive (independent) Disks（冗余廉价磁盘阵列）
- 把多块物理硬盘组合成一个逻辑磁盘，提供更好的存储性能和数据备份技术
- 提高了fail所需的平均时间
- RAID的分级
- RAID依然有可能fail，因此备份是非常必要的
通常情况下，会有少量热备盘未被分配，自动替换失效的硬盘并在其上重建数据

##Chapter13：I/O System

I/O设备日益多样化，但是软硬件的接口却越来越标准化，因此操作系统内核设计成使用设备驱动程序模块的结构，为不同的I/O设备提供了统一的接口
I/O系统由总线I/O系统和主机I/O系统两种组成
- I/O设备具有一定的寻址方式，被直接I/O指令和内存映射I/O所使用
不同的I/O方式：
- 轮询polling，需要考虑设备的状态（ready、busy、error）
- 中断interrupt，CPU有一条中断请求线，由I/O设备触发，设备控制器通过中断请求线发送信号而引起中断，CPU捕获中断并派遣到中断处理程序，中断处理程序通过处理设备来清除中断。
  - 中断请求分为非屏蔽和可屏蔽的两类，非屏蔽的中断用于处理如不可恢复内存错误等事件，可屏蔽中断可以由CPU在执行关键的不可中断的指令序列前加以屏蔽
  - 中断优先级：能够使CPU延迟处理低优先级中断而不屏蔽所有中断，这也可以让高优先级中断抢占低优先级中断处理。
  - 中断可以用于处理各种异常，系统调用是中断驱动的，中断可以用来管理内核的控制流
- DMA：直接内存访问，不需要CPU，需要DMA控制器，数据直接在I/O设备和内存之间传输
I/O的系统调用提供了对不同I/O设备的统一接口
- 驱动设备对内核隐藏了不同I/O控制器差异
- 块设备包含了磁盘驱动器，可以进行read, write, seek 等操作，允许Raw I/O or file-system access，或者内存映射文件访问
- 字符设备包括鼠标键盘和串口，包含get和put等命令
阻塞I/O和非阻塞的I/O
- 阻塞：进程挂起直到I/O完成
- 非阻塞：I/O调用立刻返回，比如buffered I/O，通过多线程机制来实现
- 异步I/O：进程和I/O同时运行
内核的I/O子系统
- I/O的调度：
  - OS通过为每个设备维护一个请求队列来实现调度，调度方式根据实际需要确定，可以FCFS也可以优先级调度
  - 其他的实现方法：缓冲、高速缓冲、假脱机
- 缓冲：
  - 解决了CPU和I/O设备的速度失配问题，需要管理缓冲区的创建、分配和释放
  - 单缓冲、双缓冲、多缓冲、缓冲池
- 假脱机SPOOLing 用来保存设备输出的缓冲，这些设备如打印机不能接收交叉的数据流
- 内核中需要维护一些I/O相关的数据结构，保存留I/O组件使用的状态信息，包括打开文件表，网络连接，字符设备状态等
进程从磁盘中读取一个文件的过程