请选择 进入手机版 | 继续访问电脑版

操作系统:文件系统的实现

[复制链接]
唐少琼 发表于 2021-1-3 12:22:18 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
目次



一、文件系统结构

磁盘的逻辑单元为块,内存和磁盘之间的I/O传输以块为单元执行。
磁盘的特点

  • 可以原地重写,可以从磁盘上读一块儿,修改该块,并将它写回到原来的位置
  • 可以直接访问磁盘上的任意一块。因此,可以方便地按顺序或随机访问文件
文件系统需要提供高效快捷磁盘访问,以便轻松存储、定位、提取数据。即存储文件、访问文件
文件系统有两个差异的设计问题

  • 访问问题:如何界说文件系统对用户的接口
  • 存储问题:创建数据结构和算法,把逻辑文件系统映射到物理外存设备
文件系统自己通常由许多差异层组成。每层实际使用更低层功能,创建新的功能,以用于更高层的服务。

设备驱动步伐可以作为翻译器,他的输入作为高级指令,输出由底层的、硬件特定指令组成。
根本文件系统只需向适当设备驱动步伐发送下令。
逻辑文件系统通过文件控制块维护文件结构。
文件控制块(FCB)包罗有关文件的信息,包罗所有者、权限、文件内容的位置等。
大多数利用系统支持多种差异的文件系统,举例:


  • CD-ROM ISO9660 文件格式
  • Unix 文件系统(Unix File System)
  • Windows文件系统:FAT(File Allocation Table),FAT32, FAT64,NTFS(Windows NT File System)
  • Linux 文件系统:可扩展文件系统(Extended file system),分布式文件系统(Distributed File System)
二、文件系统实现

1.概述

在磁盘上,文件系统包罗的信息有

  • 如何启动存储在那里利用系统
  • 总的块数
  • 空闲块的数目和位置
  • 目次结构
  • 各个详细文件 等
上述许多结构会在之后详细陈诉。这里简述如下:


  • 引导控制块(每个卷):可以包罗从该卷引导利用系统的所需信息。如果磁盘不包罗利用系统,则这块的内容为空。UFS称为引导块(boot block),NFS称为分区引导扇区(partition boot sector)
  • 卷控制块(每个卷):包罗卷的详细信息(分区的块数、块的巨细、空闲块的数量和指针、空闲
    FCB 的数量和指针等)。UFS称为超等块儿(super block),NTFS主控文件表(master boot sector)
  • 每个文件的FCB包罗该文件的许多详细信息。他有一个唯一的标识号,以便与目次条目相关联
  • 每个文件系统的目次结构用于组织文件
内存中的信息用于管理文件系统并通过缓存来提高性能,这些数据在安装文件装系统时被加载,在文件系统利用期间被更新,在卸载是被卸载。这些结构范例包罗:

  • 每个历程的打开文件表:包罗一个指向系统的打开文件表中符合条目的指针和其他信息
  • 整个系统的打开文件表:包罗每个打开文件的FCB副本和其他信息
创建一个新文件

  • 应用步伐调用逻辑文件系统。逻辑文件系统指导目次结构的格式,它会分配一个新的FCB
  • 系统将相应的目次信息读入内存
  • 更新目次结构和FCB
  • 将效果写回磁盘
一旦文件被创建,就能用于I/O,不外,首先他要被打开。系统调用open()将文件名传到逻辑文件系统,系统调用open():

  • 首先搜索整个系统的打开文件表,检察是否已经被打开,如果是,则在该历程的打开文件表创建一个条目,并指向现有整个系统的打开文件表。
  • 否则,根据文件名搜索目次结构
  • 找到后,它的FCB会复制到内存的整个系统的开放文件表中(该表还存放着打开该文件的历程数量) ,接下来,在该历程的打开文件表创建一个条目,并指向现有整个系统的打开文件表。
Open() 返回值:文件形貌符是一个非负整数。它是一历程打开文件表的索引值,指向系统范围内打开文件表相应条目


2.虚拟文件系统

利用系统如何才华将多个范例的文件系统集成到目次结构中?用户如安在访问文件系统空间时,可以无缝地在文件系统范例间迁移?大多数利用系统采取面向对象的技能来简化、组织、模块化实现。
数据结构和步伐用于隔离根本的利用系统调用的功能与实现细节。因此,文件系统的实现有三个主要层构成。
第一层为文件系统接口。
第二层为虚拟文件系统(VFS),把文件系统的通用利用和详细实现分开,虚拟文件系统提供了在唯一标识一个文件的机制。VFS基于vnode 的文件体现结构,它包罗了一个数值标识符来唯一体现网络上的一个文件。

  • VFS能区分差异本地文件系统
  • VFS能区分本地文件系统和远程文件系统


三、目次实现

1.线性列表

采取文件名称和数据块指针的线性列表


  • 优点:编程简朴
  • 缺点:因为需要搜索,运行较为费时
2.哈希表

哈希表根据文件名得到一个值,并返回一个指向线性列表中元素的指针


  • 优点:淘汰目次搜索时间
  • 缺点:两个文件名哈希到相同的位置时大概发生辩论;因哈希表固定巨细,创建文件需要哈希表重建时,比力贫苦。
四、磁盘空间的分配方法

1.一连分配

每个文件在磁盘上占有一组一连的块。 文件的一连分配可以用文件第一块的磁盘地点和一连块的数量(即长度)来界说

一连分配支持顺序访问和直接访问
问题:当文件需要扩展,文件巨细变大时会无法扩

办理:找更大的一连空间,复制已往
基于扩展的一连分配方案
用以下参数来界说文件

  • 开始地点
  • 块儿数
  • 指向下一个扩展块儿的指针(扩展块儿可以是多个)
界说格式:
文件【开始地点,块儿数,指向下一个扩展块的指针】
2.链接分配

每个文件是磁盘块儿的链表,磁盘块分布在磁盘的任何地方,文件有起始块和竣事块来界说
界说格式:【起始块,竣事块】
同时,每个磁盘块都有指向下一个磁盘块的地点。

优点:没有磁盘空间浪费
缺点:

  • 不支持文件的直接访问
  • 需要更多的磁盘空间(来记载指针)
链接分配的一个重要变种是文件分配表
每个卷的开始部分用于存储文件分配表(File Allocation Table),表中每个磁盘块都有一个FAT条目,并可通过块号索引。(未使用的块为0,使用的块包罗下一个块儿号)

目次条目含有文件首块号码,通过这个块号索引的FAT条目包罗文件下一块的号码,这个链会继承下去,直到最后一块,最后一块的表条目值为文件竣事值。

3.索引分配

通过将所有指针放在一起,即索引块
文件用索引块来界说, 每个文件有其索引块。

这里有一个问题,索引块应为多大?
每个文件必须有一个索引块,因此索引块应尽大概小,然而必能太小,否则放不下足够多的指针,为处理处罚这个问题,有如下一些机制:

  • 链接方案:为了处理处罚大文件,可以将多个索引块链接起来
  • 多条理索引:用第一层索引块指向一组第二层的索引块,第二层索引块再指向文件块
  • 组合方案:用于基于UNIX的文件系统,将索引块的前15个指针存储在文件的i-node中。此中,前12个指针指向直接块,剩下3个指针指向间接块

五、磁盘空闲空间的管理

1.位向量

空闲空间表实现为位图, 或位向量,每块用一位(bit)体现。1体现块空闲;0体现块已分配
2.链表

所有空闲块用链表链接起来,并将指向第一个空闲块儿的指针生存在特殊位置,同时缓存在内存。
每个块儿含有下一个块儿的指针
3.组

将n个空闲块的地点生存在第一个空闲块中。
这些空闲块中的前n-1个为空,而最后一块包罗别的n个空闲块的地点。
比链表好的是空闲块的地点可以很快找到,而且可以明确一段一连空闲块空间
例:n=3

4.计数

基于以下事实:
通常有多个一连块需要同时分配或释放,尤其是在使用一连分配时。因此记载


  • 记载第一块的地点和紧跟第一块的一连的空闲块的数量。
  • 空闲空间表的每个条目包罗磁盘地点和数量
例:

六、文件系统的性能和效率

磁盘空间的有效使用(效率),取决于


  • 磁盘分配和目次管理算法
  • 生存在文件目次条目中的数据范例
改善性能的方法:缓存

  • 缓冲区缓存:一块独立内存,位于此中的块是立刻需要使用的
  • 页面缓存:将文件数据作为页而不是块来缓存。页面缓存使用虚拟内存技能,将文件数据作为页来缓存,比采取物理磁盘块来缓存更高效
  • 板载高速缓存

如果没有统一缓存,则会由下图情况发生:

系统调用read()和write()会通过缓冲区缓存,然而,内存映射调用需要使用两个缓存,即页面缓存和缓冲区缓存。内存映射先从文件系统中读入磁盘块,并放入缓冲区缓存,由于虚拟内存系统没有缓冲区缓存接口,缓冲缓存内的文件必须复制到页面缓存中。
采取统一缓冲缓存
统一缓冲缓存:统一使用缓冲器缓存来缓存历程页和文件数据。

无论是缓存块照旧页面都有置换问题,
文件的读入或写出一般是按顺序举行。所以,不适
合采取LRU算法,因为最近使用的页面最后才会用甚至根本不会再用。
顺序访问可以通过立刻释放和预先读取来加以优化

  • 立刻释放(free-behind):请求下一页时,立刻释放上一页
  • 预先读取(read-ahead):请求页之后的下一个页也一起读入
七、文件系统的规复

目次信息一般事先生存在内存中以加速访问,有时会导致目次结构中的数据和磁盘块中的数据不一致。
办理:

  • 一致性查抄:比力目次结构中的数据和磁盘块中的数据,实验着去修正不一致
  • 备份&规复:
    I. 备份(backup):使用系统步伐来备份数据到其他的存储设备。软盘,磁带
    II. 规复(recovery):通过从备份来规复丢失的文件或磁盘
基于日志结构的文件系统


  • 文件创建涉及到目次结构修改,FCB分配,数据块分配等
  • 所有元数据(meta data)的厘革写入日志上,一旦这些修改写到日志,就认为已经提交了。
  • 提交了的事务,并不一定立刻完成利用
  • 当整个提交的事务已经完成时,就从日志中删除事务条目
  • 如果系统瓦解,日志文件大概还存在事务,它包罗的任何事务虽然已颠末利用系统提交了,但还没有完成到文件系统,必须重新执行。

来源:https://blog.csdn.net/weixin_44759105/article/details/111835946
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )