操作系统概念——文件系统和IO

第十二章 文件系统实现
12.1 文件系统结构
磁盘上有很多种类的文件系统实现,主要是因为磁盘支持随机任意读写.
文件系统主要关注2个问题:
1) 对用户的展示和接口,如文件有什么属性,目录结构如何组织等.
2) 采用什么数据结构和算法来将逻辑文件映射到物理设备上.

文件系统本身是按层次来组织的,主要包括 :
IO控制层:驱动,硬件中断,处理硬件指令交互.
基本文件系统层:给下层发指令,以及管理buffer/cache.
文件组织模块层:管理文件逻辑块到物理块位置的映射;空闲块回收.
逻辑文件系统层:管理文件元数据,目录结构,权限保护等.

文件系统设计和实现一直是操作系统活跃研究领域.

12.2 文件系统实现
文件系统在磁盘上的结构:
启动控制块:用于引导加载操作系统.
分卷控制块:分区总信息,包括总块数、(空闲)块索引、(空闲)inode索引、块大小等; 即Unix下超级块.
目录组织结构:如文件名和inode号.
PCB:如每个文件的inode.

文件系统在内存中的结构:
挂载表:记录所有已挂载的分卷信息.
目录结构cache:最近访问的目录信息缓存.
系统级文件表:所有打开的文件的PCB信息等.
进程级文件表:包含有指向系统文件表的指针.
以及文件读写buffer.

用于启动加载的信息一般单独放到一个分区里,并需要知道操作系统所分区的文件系统结构.
因为此时OS尚未加载,文件系统相关代码也还不存在,需要靠启动程序从磁盘加载OS.
存放操作系统的分区会在启动时自动挂载,其他数据分析可以稍后手动挂载或通过配置自动挂载.

虚拟文件系统VFS为各种文件系统的实现提供了一套统一的OOP接口.

12.3 目录实现
线性表:
将目录内容组织为线性表,缺点是一些文件操作需要遍历查表.
一般组织为有序表,如通过平衡排序树组织.

哈希表:
速度快,但有动态扩展问题;可以使用溢出链表组织.

12.4 空间分配算法
即对新文件或增长的文件如何分配存储空间,一般有以下几种方式:
a) 连续分配
为文件分配连续的磁盘存储空间,好处是顺序和随机查找都很高效.
缺点是有外部碎片问题;以及一般没法事先知道文件的大小.

b) 链表分配
将块使用链表串联起来,不需要连续,无外部碎片问题.
缺点是随机访问可能要遍历所有的块十分低效,一般用于顺序访问.
对此的一个优化是把链表部分抽取出来集中存放,如FAT:
fat_linklist

c) 索引分配
使用索引块记录每一块对应的数据块的位置,类似页表.
好处是随机访问比链表方式快,缺点是需要额外的索引块存储.
大文件一般需要多个索引,如多级索引组织.
Unix inode中有12个直接索引字段,1个间接索引字段,1个2级间接索引字段,1个3级间接索引字段:
unix_inode_index
因此Unix下小于12*4K=48K的小文件不需要额外的索引块.

索引方式的性能和文件大小、索引结构、以及要读写的位置都有关.
一些系统对小文件采取连续分配,对大文件使用索引分配,平均性能较好.

12.5 空闲空间管理
文件系统需要维护空闲空间列表,有多种方式:
a) bitmap
回收和分配都比较简单,但需要载入内存,开销较大.

b) 链表
有个表头指针指向空闲块链表.
需要分配大量块的时候比较低效,可以通过索引聚集、计数等方法优化.

c) 空间映射
Solaris优化大规模文件系统元数据读写的方法.
采用日志文件系统记录文件分配和回收活动,需要的时候载入内存回放.

12.6 空间效率和性能
磁盘IO一般是系统的性能瓶颈.
一般会通过合理牺牲空间来提升性能,如预分配inode、批量块分配(内部碎片)、减少动态元数据等.
有时也会通过牺牲一定的性能来保证系统设计的通用性和可扩展性,如引入动态变长的位置指针.
一些系统提供buffer cache和page cache进一步加速IO访问.
在统一虚拟内存模型下,进程的page cache和文件的page cache是统一的.
走VM的page cache更高效因为VM涉及的交互比FS更简单.
块数据一般采用异步写的方式,元数据一般是同步写的.

12.7 数据恢复
发生掉电等异常时文件系统各结构可能数据不一致导致损坏.
一种方法是使用一个一致性检查工具如fsck来发现并修复.
另一种是采用日志文件系统,来保证元数据操作的事务性.
即一旦一条变更持久化到日志里了就返回成功,系统异步播放日志执行.
如果系统崩溃,则重启后将未完成的事务继续做完即可.
其他方法包括snapshot和数据周期备份等.

12.8 NFS
一种广泛使用的网络文件系统,方便集体协作,主要分为远程挂载和文件处理两部分协议.
Solaris内核线程直接支持NFS:
solaris_nfs
可以看到client和server是可互换的,一台机器通常即是client也是server.
NFS的一个特点是无状态的,无需open或close,每次请求要带上所有操作.
这就需要每次操作具有幂等性,需要用序号等机制排除重复请求.
server也必须同步写到磁盘才能返回client成功,可以用NVRAM加速.

第十三章 IO系统
13.1 概览
硬件设备发展的两个大的趋势:
1) 功能、种类越来越多样.
2) 软硬件接口逐步通用和统一.
操作系统内核一般通过驱动模块来管理硬件,后者为IO子系统提供统一的交互接口.

13.2 IO硬件
硬件通过端口(Port)与计算机相连,多个硬件可能共享同一个总线(Bus).
系统通过硬件控制芯片(Controller)来操作硬件,后者提供一些数据/指令寄存器供读写.
Cpu可以直接通过专用IO指令来读写这些端口地址,也可以使用Memory-Mapped IO.
系统发指令给硬件后,与硬件的交互分2种方式:
1) Polling:
不断轮训查看硬件是否ready,即忙等
2) 中断:
硬件完成后给系统发异步中断,后者调用响应的Interrupt Handler处理.
中断处理一般是驱动程序的一部分,系统需要支持不同的响应优先级.

DMA:传输大块内容时,cpu不停的按字节单位在内存和设备间移动数据和监控硬件状态比较浪费,可以代理给DMA专门做这个事情.
DMA执行时会和cpu争抢内存总线,但总体上是提高了利用率的.
dma_steps

13.3 应用层IO接口
驱动程序按照操作系统的要求实现统一的接口供其集成.
厂商一般都会为多种系统提供其硬件的驱动.
驱动一般以内核模块的形式存在,驱动层为IO子系统屏蔽了硬件的多样性和差异.
不同的硬件的差异主要体现在传输单位、速度、只读或读写、顺序或随机、同步或异步、共享或独占等多个方面.
在应用层看来一般分为以下几大类:
1) 块设备和字符设备
2) 网络设备
3) 时钟和可编程定时器

同步阻塞IO:进程挂起等待直到IO完成,进程恢复执行.
同步非阻塞IO:进程不挂起,接口立即返回,有多少就完成多少,如果暂时设备不可用则放弃.
异步非阻塞IO:进程不挂起,发起IO命令后接口立即返回,系统异步执行IO,需有其他机制在完成时通知进程.
Select:只判断当前fd是否可读或可写,一般紧跟着read/write调用.
Vectored IO:多个分散地址的读写操作,可减少IO调用次数.

13.4 内核IO子系统
驱动层之上的IO子系统一般提供一下若干服务:
1) IO调度:合理安排排队的请求提高整体效率.
2) Buffering:高低速设备间缓冲/传输块大小适配/复制语义保障
3) Caching:加速设备访问
4) 请求隔离和设备独占,如打印机
5) 错误处理、IO保护等.
内核一般会以文件打开列表的方式管理设备.

13.5 从IO请求到设备执行
中间需要经过多层子系统和多次动态表查找,一次完整IO如下:
io_steps
(判断那里指的是有无命中cache)

13.6 STREAMS
Unix中一种基于模块的驱动或网络栈协议扩展框架. Linux不采用.

13.7 性能
IO的性能主要消耗在多次上下文切换、多次内存copy、频繁中断等.
一般需要平衡IO、Cpu、总线和内存的性能,最小化瓶颈.
IO特性可以在多个层次实现,一般越往底层(硬件)效率越高,抽象性越好,但成本和调试灵活性都较差;
越往上层(应用)灵活性越好成本低,但性能和效果差.

发表评论

电子邮件地址不会被公开。