网站建设需求分析的功能,大型网站建设优化排名,工业设计之父,重庆好的seo平台引言
之前已经学习过数据在内存中是如何表示#xff0c;如何存储#xff0c;但是这些存储在PC断电后数据便消失。因此我们需要一个可以持久化存储并且容量远远大于内存的结构#xff0c;这一篇我们将学习#xff0c;文件是如何被组织和操作的#xff0c;这是一个操作系统…引言
之前已经学习过数据在内存中是如何表示如何存储但是这些存储在PC断电后数据便消失。因此我们需要一个可以持久化存储并且容量远远大于内存的结构这一篇我们将学习文件是如何被组织和操作的这是一个操作系统重要的部分-文件系统。文章的结构主要分为文件和目录的概念、文件系统的实现、文件系统的管理和优化、最后是例子。
文件和目录的基本概念
文件
文件定义文件是一种抽象的概念它提供了一种方法可以将信息存储到硬盘并且随后读取回来。文件命名 文件命名规则是通常分为两部分小数点后的叫文件扩展名不是必须的小数点前的叫文件名某些操作系统有字符数限制学完文件的组织结构就知道为什么了某些系统区分大小写。文件结构文件结构可以多种方式下图是常见的三种方式 a 代表文件是一个无结构的字节序列操作系统无需知道文件是什么由用户程序解释字节序列。这种方式提供了最大限度的灵活性用户程序可以以自己觉得合适的方式来存放文件。 b代表文件是一个定长记录的序列记录有其内部结构。核心思想是对文件的操作以记录为单位读取一个记录 c代表文件被组织成树型结构树最大的好处就是方便查找因此这种文件结构在数据库日常作索引比如mysql的BTree索引。 文件类型 文件类型通常分为普通文件和目录目录比较重要后面会讲unix还有额外的字符特殊文件和块特殊文件。 普通文件
ASCII ASCII文件包含多行正文每行以换行或者回车结束Windows系统同时使用换行和回车。ASCII文件的好处是可以显示和打印也可以通过文本编辑器编辑二进制文件 二进制文件即使打印出来也是无法理解的字符通常其有独立的内部结构只有其用户程序才能解释下面是两个UNIX系统的两个二进制文件的例子 1. 可执行二进制 通常可执行程序都是存放为二进制 头以魔数开头魔数通常用于标识程序的特定文件比如java的class文件就有魔数0xCAFEBABE还存放了正文大小、数据大小等信息 程序正文代码 数据 重定位位程序被载入内存重定位时需要 符号表通常是程序debug需要 2. 存档文件 UNIX存档文件是已编译但未链接的文件其结构如下 字符特殊文件通常用于串行I/O设备比如终端、打印机和网络 块特殊文件通常用于硬盘交互 文件访问 顺序访问
早期操作系统只支持顺序访问那时的磁带也只支持顺序访问 随机访问
磁盘支持随机访问有两种思路
read操作每次指定开始读文件的位置读取通过seek设置当前位置然后顺序读取UNIX和Windows采用这种方式
文件属性 前四个是创建者和所有者以及访问权限相关 flags指定特殊属性很容易理解 record-length、key-position、key-length只出现在用key查找的文件中 Time相关属性Creation time是创建时间Time of last access最后访问时间Time of last change最后修改时间 size相关属性Current size文件字节数Maximum size在老的操作系统中有使用在创建时指定文件的最大大小然后预留存储空间现代操作系统已经不需要 文件操作 Create创建文件 Delete删除文件 Open打开文件在使用文件之前必须先打开 Close关闭文件 Read读取文件通常从当前位置读取必须指定需要读取多少个byte而且必须提供一个buffer来容纳它们 Write写入文件通常从当前位置写入如果当前位置是文件末尾则增加文件的大小如果在中间则覆盖原有的数据 Append追加内容只能写入在文件末尾 Seek用于随机访问时指定文件的需要操作的位置seek操作后read和write操作都将在这个位置执行 Get attributes获取文件属性 Set attributes设置文件属性 Rename重命名
目录
目录是为了记录文件的位置管理文件 单级目录系统 早期个人计算机比较通用这类目录系统那时个人计算机通常只有一个用户。这个方案的好处是简单定位文件快因为磁盘只有一个地方存目录信息目前常用于嵌入式设备因为现代计算机文件太多单级的目录无法适用。其结构示意图如下 层级目录系统 虽然单级目录系统有简单和定位文件快的好处但是现在计算机的用户通常有成千上万的文件不可能放到一个目录中因此需要一种方法将有关系文件分组聚集在一起一种方案是层级目录就像一本书的目录如下图不仅可以分组聚集相关文件还可以为不同用户创建独立的目录 路径名 用目录树组织目录时需用某种方法指定文件名。 绝对路径每个文件获得一个从root目录到文件的路径。比如路径/usr/ast/mailbox代表根目录有一个子目录usr然后usr下有一个子目录ast然后ast目录有mailbox文件。绝对路径都是从根目录“/“开始并且是唯一的。在UNIX下路径目录分隔用”/“windows下用”\“
相对路径相对路径通常和工作目录一起使用例如使用绝对路径复制mailbox
cp /usr/ast/mailbox /usr/ast/mailbox.bak如果此时在目录/usr/ast也就是工作目录是/usr/ast使用相对路径
cp mailbox mailbox.bak每个目录中有两个特殊的目录.“和”,“”.“代表当前目录”…代表父级目录
目录主要操作 Create创建一个空目录除了.和”…“ Delete只有空目录才能被删除 Opendir打开目录 Closedir关闭目录 Readdir返回打开目录的下一个目录项 Rename重命名 Link链接可以使同一个文件出现在多个目录中 Unlink解除链接当文件只出现在一个目录中时删除文件
文件系统实现
文件系统布局
文件系统存储在磁盘上一个disk可以分成多个分区每个分区都可以有自己独立的文件系统 MBR0号扇区叫作主引导记录用于引导计算机在MBR结尾有一个分区表记录了磁盘分区的开始和结束位置表中的一个记录被标记为活跃的。 分区计算机引导时读入MBR并执行MBR程序的第一件事是确定活跃分区并读入第一个块引导块boot block引导块的程序将加载该分区的操作系统每一个分区都是以boot block开头即使没有可执行的操作系统。文件系统分区布局如下 超级块(superblock)包含了文件系统的所有关键参数在计算机启动时或者文件系统第一次使用时就会被读入内存通常里边包括代表文件系统类型的魔数文件系统块数量和其他关键管理信息 Free space mgmt管理空闲块信息 I-nodesi节点数组每个文件一个包含文件的各种信息 Root dir根目录存放了文件系统目录树的根 Files and directories所有其他目录和文件 系统引导读取文件系统流程
文件实现
文件实现的关键问题是记录各个文件用了哪些块 连续分配最简单的方案为各个文件分配连续的块存储示意图如下a是磁盘前40个块存放7个文件块的示意图 优点 实现简单只需要记录文件起始块和块数 有出色的读取性能只需要一次seek操作就可以读取整个文件因为块连续只需要找到文件第一个块就可以 缺点 随着时间推移磁盘容易产生碎片如上图中b文件D和F被删除后留下了磁盘碎片如果压缩磁盘碎片开销非常高解决方法是利用碎片列表重用碎片但是为了选择合适的碎片需要确定的文件最终大小这种方式对用户很不友好比如编辑一个文档根本不知道最终大小只能预估。 适用场景CD-ROMs因为CD-ROMs第一次写的时候明确知道文件的大小并且后续不会改变比如存放电影 链式分配每个块的第一个字都是指向下一个块的指针其结构如图 - 优点 不会像连续分配那样产生外部碎片 目录项中只需要保存文件第一个块的地址 缺点、 随机读取速度慢因为每一次都要从头开始 因为块中需要空间存放指针因为存放数据不足一个块此时如果程序读取一个块的数据就要读两个块 利用内存存放表的链式分配链式分配的两个缺点都可以通过将文件用到的块信息单独存放在内存的方式来解决这个内存中表叫做FAT(File Allocation Table)这样块不用再存放指针而且随机访问也变得容易 缺点要使用这种方式FAT需要常驻内存假设1T的硬盘和1kb大小的块可能需要2个多G的内存空间。由于这个缺点导致它的扩展性很差 I-nodes为文件单独分配的一个数据结构用来存放文件的属性和文件包含的磁盘块。一个简单的i-nodes例子 优点i-nodes只需要将打开的文件的nodes信息存入内存中节省大量的空间使得i-nodes可以支持很大的磁盘因此其对大磁盘的扩展性较好因为它占用内存的大小和磁盘大小无关而和打开的文件有关 解决文件块数量很多的问题如果i-node的大小是固定的那么文件可以存放的磁盘块地址也是固定的为了解决这个问题当i-node结构不能存放所有块时那么最后一个块地址不是指向文件的数据而是指向存放额外块的块如上图
目录实现
目录属性存储方式
attributes存在目录项中具有固定长度的目录项 如果系统使用i-node那么可以将attributes存储到i-node中如下图前面文件系统布局提到过i-nodes数组单独存放在分区的某个位置。因此目录项非常短只需要存储文件名和i-node索引号
文件名实现方式 1.定长文件名比如分配255个字符固定长度来存放文件名浪费空间 2.变长文件名 行内存放文件名目录项的开头是目录项的长度目录项属性是定长的文件名放在属性后变长的如下图。缺点是当文件删除后目录项会产生空隙之后的目录项可能不匹配这个空隙 堆内存放文件名目录项有固定的长度将文件名放在目录项后边的堆中如下图。这种方式的优点是当文件被删除时产生的目录项空隙肯定可以和下一个目录项匹配一个优化是堆中的文件名不需要字对齐
加速查找
散列查找文件名当目录中的文件非常多时如果线性查找必然会慢一种解决方法是每个目录构造一个散列表用文件名的hash值求模来映射如果hash值相同用链表来连接缓存文件查找结果
共享文件
共享文件如下图的C目录的一个文件也出现在了B目录下B对共享文件的联系称为链接 共享文件实现
目录不包含文件的磁盘块而是列入文件中的一个小数据结构目录指向这个结构UNIX就是采用这种方式小型数据结构即i-node。i-node中需要一个计数器记录当前有多少目录项指向它当删除时扣减计数直到为0时由其所有者删除符号链接当B链接C目录下的文件时系统会在B目录中创建一个LINK类型的文件只包含了共享文件的路径当读取B目录下的共享文件时发现类型为LINK则拿到真实的路径读取共享文件。缺点是需要额外的开销
日志结构文件系统(LFS)
基本假设
随着内存和磁盘缓存越来越大一般程序的工作集都会保持在内存和磁盘缓存中真正的读操作是很少的大部分磁盘操作都是写操作磁盘的随机操作速度慢顺序操作速度快传统的零碎写操作是非常低效的 LFS实现
写入流程将磁盘抽象为一个日志将零碎的写先缓存在内存中当缓存达到一个段的大小时然后作为一个段写在日志的末尾由于是顺序写因此可以高效的利用磁盘带宽。段中包含各种数据比如目录块、文件数据块和i-nodes段的开头是段内容的摘要概述了段中包含什么内容。i-node的查找处理因为i-nodes现在散落在各个段中所以查找i-nodes是一个很困难的任务因此LFS引入一个i-node的映射的map这个map保存在磁盘上当然也会缓存在内存中磁盘压缩磁盘的容量是有上限的因此需要定期清理已删除的文件。清理的过程是读入一个段如果段中的信息已经没有使用丢弃该内容否则写入缓冲区等待写回下一个段清理线程从后面清理因此磁盘成了一个大环形缓冲区。LFS详细介绍会单独写一篇文章
日志文件系统
原理以日志的方式记录文件系统下一步的操作当系统崩溃时重启读取日志完成未完成的任务。记录日志的操作必须幂等的可以重复执行
文件系统管理和优化
磁盘空间管理 块大小 选择合适的块大小需要平衡空间浪费和性能大尺寸的块存放小文件浪费空间小尺寸的块查找块次数多导致访问慢SSD除外。确定合适的尺寸需要统计文件大小分布一个文件大小分布的研究数据是1984年和2005年的大型研究型大学的计算机系、一个政治网站(www.electoral-vote.com)的文件分布数据。通过数据可以看出90%以下的文件是小于64KB的 磁盘访问时间 seekrotationaldelaytransfer磁盘块大小对磁盘数据率和磁盘利用率的影响实线是磁盘利用率随着磁盘块的增大而减小虚线代表磁盘数据率随磁盘块增大而增大 记录空闲块 前面我们学习过空闲内存的管理其实知识都是相通的所以我们也很容易的想到用链表和bitmap来管理 前面我们学习过空闲内存的管理其实知识都是相通的所以我们也很容易的想到用链表和bitmap来管理 链表如果块大小为1KB一个块号用32位表示则一个块可以存放256个空闲块如果1T的硬盘没有使用时需要400万个块管理空闲块虽然占用了很多空间但是它们是存储在空闲块中并且随着磁盘使用率增加它们占用的空间会变小 空闲链表管理实现过程保持一个空闲链表块在内存中当文件删除导致块回收时空闲链表块增加当空闲链表块满时写回磁盘如下图的a-b为了避免刚删除文件导致空闲链表写回磁盘后马上又有需要写文件导致刚写回的空闲链表块又读回内存做了一个优化当内存中的空闲链表块满时不是整块写回磁盘而是写一半然后内存中的空闲块就只剩一半左右的空闲块来处理临时的释放和申请空闲块减少磁盘IO bittmap只需要用一位就可以表示一个块是否空闲假设磁盘大小为1T块大小为1KB则需要130,000 1-KB块存储 磁盘配额 在多用户系统中为了避免某一个用户占用太多的磁盘空间通常会对用户做限额限额主要是文件数量和磁盘块数量。 实现原理当一个文件被创建或打开时会记录到打开的文件列表中并且根据其属性中的所有者加载用户配额到内存中的配额表打开的文件列表项中记录了文件所有者配额的指针如图配额表项结构 Soft * limit软限制Hard * limit硬限制绝对不能超过warnings left剩余警告次数当用户登录时会校验软限制如果其中一项超过则会警告用户每警告一次该值减一当减到0时则用户被拒绝登录
文件系统备份 备份的关键问题 是整个文件系统备份还是部分备份对前一次备份后没有变化的文件备份是非常浪费的增量转储 - 最简单的定期与全量备份比较备份期间变化的 - 更好的方式与上一次备份比较 - 优缺点最小化了备份时间但是恢复时可能比较复杂备份的数据通常都是很大的因此可能会采用压缩备份的方式但是压缩过程中产生的一个错误可能导致整个备份文件无法使用因此使用压缩算法时要小心对活动文件系统备份是困难因为可能导致数据不一致虽然可能在晚上或空闲的时候备份但是有时可能备份时间很长。Hutchinson在1999年提出基于文件系统快照的备份记录文件系统关键数据结构的快照然后在空闲的时候备份非技术性数据安全问题 备份策略
文件一致性
当系统崩溃时可能导致文件系统数据一致性问题OS通过应用程序来分析和处理这些数据一致性问题 块检查 检查需要的数据结构一个表记录文件用到的块一个表记录空闲块 程序执行步骤 1.读出所有的i-node从磁盘0号块开始由i-node开始构建第一个表如果块被使用计数加12.读出空闲链表或者bitmap检查空闲的块如果块出现在空闲链表或bitmap中第二个表中计数加13. 对比两个表如果文件系统一致那么一个块有且仅出现一次在两个表中的某一个且必须出现程序执行结果各种情形 文件系统一致 块缺失块不在任何一个表中比如2号块不会造成实际的损害但是会造成空间的浪费解决方法很简单将它加入空闲链表 空闲块重复比如4号块这种情况解决方法也很简单减少空闲链表 数据块重复最坏的情况是一个块出现在两个或多个文件中比如5号块这中情形应该报告给用户由用户处理 文件检查 原理从文件目录的根目录开始递归扫描将出现的文件和目录加入一个表中并增加其计数然后遍历表将i-nodes的链接数文件创建时值为1每一个硬链接都会加1和表的计数对比如果一致则文件系统一致第一种错误i-nodes链接数目太大 导致问题即使所有目录中都删除了这个文件该文件也不会释放会继续占用空间。解决办法修正i-nodes中的值为正确值 第二种错误i-nodes链接数目太小 导致问题可能会导致严重的后果当有两个文件链接了文件而i-nodes链接计数为1时一旦一个文件链接删除则i-nodes的链接计数将降为0导致文件i-nodes和块被释放如果被分配给其他文件则此时另一个链接指向了错误的文件。解决办法修正i-nodes中的链接数值为真实的链接数即表中的计数
文件系统性能 缓存 缓存结构通过设备号和磁盘地址的hash值构建一个hash表快速查询缓存缓存节点有三个指针一个是用于hash冲突时构成的一个单链表另外两个用户构造缓存块使用顺序的双向链表、 缓存淘汰算法类似内存分页系统的页面淘汰算法 LRU算法磁盘缓存存在的问题 1.使用LRU缓存对块的修改会在淘汰的时候写回磁盘但是如果修改一个i-nodes块要从队尾到队首才写回磁盘中间需要一段时间而此时系统崩溃会导致文件系统不一致 - 考虑两个因素1.这个块是否会在稍后还会修改2.这个块是否对文件系统一致性是必不可少的- 根据上述因素对块分类1. i-nodes块2. 间接块3. 目录块4. 满数据块5. 不满数据块- 改进将稍后可能不在需要的块放在队首将还在写不满的块放在队尾除了数据块其他块应该立刻写回磁盘 解决办法 1. unix提供sync系统调用系统启动时启动一个update进程定期调用sync系统调用强制将修改写回磁盘2. Windows提供FlushFileBuffers调用Windows采用比unix更好某种程度更坏的策略采用write-through caches的方式每当缓存中的块发生改变立刻写回磁盘和CPU高速缓存的写穿透一样。但是需要更多的磁盘IOWindows和unix处理的区别 1.如果unix没有调用sync就移除磁盘那么数据会丢失 2. Unix的方法在Windows中也有使用ntfs改进日志文件系统了来增强其可靠性 块预读 原理在块被需要使用之前先将它们载入到缓存中来提高缓存命中率缺点这种策略只能在顺序读时能提高效率实现需要跟踪每个文件的访问方式通过提供一个访问模式标记来判断当前读是顺序访问还是随机访问如果不知道是什么模式先以顺序读的模式读读完之后立即清除标记如果接下来读是顺序的那么顺序读标记就会被设置
磁盘碎片整理
Windows下有defrag用户应该定时运行除了SSD SSD碎片整理会缩短其寿命
refhttps://blog.csdn.net/houwanfeimark/article/details/106972929
其它
