Post

操作系统--文件系统

Posted
By SmallC
9 min read
操作系统--文件系统

1 File

挑选难理解的概念进行讲解。

三种文件种类：byte sequence 、 record sequence 、 tree

文件类型：

  • Regular files：普通文件，分为文本文件和二进制文件
  • Directories：目录
  • Character special file：特殊字符文件，模拟io设备比如终端、打印机和网络
  • Block special files：块文件，模拟disk

文件访问：

  • 顺序访问：从头开始读文件，不可以跳跃，可以回退和后退，在磁盘媒介中比较便利
  • 随机访问：随意读取文件，file marker用来定位开始read的位置，就是seek操作。可以先读在seek也可以先seek，再读

metadata：文件属性（file attribute）

文件操作

2 Directory 目录

  • 文件系统通过目录来查找文件
  • 目录是一个文件名和文件位置相同的文件
  • directory entries 拥有文件的信息。目录下有文件创建，文件条目也跟着创建，有文件删除，条目也跟着删除；

目录的好处：

  • 方便查找文件
  • 文件可以在不同目录下重复命名
  • 归类

目录系统：

  • 单目录系统
  • 多目录系统
  • 层次目录系统

路径分为相对路径和绝对路径

3 文件系统

超级块：描述文件系统的状态：分区大小，块大小，指向空块的指针列表，root目录的inode number，magic number

文件系统认为disk是一个block数组

实现文件存储就是最追踪file放在哪些disk block中

  • Contiguous Allocation
  • Linked List Allocation
  • Indexed Allocation

Contiguous Allocation

把file储存在相邻的blocks中

优点：

  • 简单实现
  • 读操作非常高效

缺点：

  • 存在external fragmentation，块与块之间有没利用的外部碎片
  • file一旦创建，文件的大小无法改变

Good for CD-ROMs, DVDs and other write-once optical media

Linked List Allocation

使用一串用指针连接的Link list的块来储存file，block的头部储存指向下一个块的指针

优点：

  • 没有external fragmentation
  • 目录条目简单，只用储存第一个块的第一个字的地址
  • file的大小可以变化
  • 对顺序访问很友好

缺点：

  • 随机访问很慢
  • 块中的data的数目不是2的次方

Linked List Allocation Using FAT

FAT：index table 存放着每个块的table pointer word

FAT文件系统中，disk的数据区被划分为多个蔟，文件的储存需要分配蔟，而FAT表就是记录这些文件分配到的蔟的地址，如果一个文件大小大于一个蔟的大小，就会被分配到多个蔟，FAT表就会记录这些蔟的连接关系

就是单独建立一张表来记录一个文件所用的块的连接关系，用于搜索

  • 分区的第一个section会存放FAT
  • FAT可以读入内存中以减小disk seek
  • disk中一块一个FAT entry，按块号排序
  • 每一个entry持有下一个block的地址
  • 最后一个文件标记-1
  • -2表示该蔟是空的

优点：

  • 整个块对data是可用的
  • 可以通过对FAT的扫描实现随机访问
  • 目录条目只需要一个number：starting block number（文件的第一块对于FAT 表的索引）

缺点：

  • 整张表需要拷贝进内存，挤占内存空间

inode（index node）

每个文件都有自己的inode，inode里列举了文件属性和文件所有的data block的地址

inode内部的块地址分配也有直接和间接两种，间接又分为single indirect block、double indirect block和triple indirect block三种

  • A single indirect block contains pointers to data blocks.
  • A double indirect block contains pointers to single indirect blocks.
  • A triple indirect block contains pointers to double indirect blocks.

优点：

  • 快速的查找和随机访问
  • 没有外部碎片
  • 文件被打开时，对应文件的inode才被加载到内存中，占用小

缺点：

  • 索引开销大

目录实现

  • 目录的储存和文件的储存方式一样
    • 目录条目也储存在data block中
    • 目录文件就是一个目录条目列表
  • 文件打开时，文件系统会使用文件路径来定位目录条目

  • 目录条目提供找到disk block的需要信息：文件地址/第一个块的块号/inode号

  • 文件属性的位置
    • 在目录条目中
    • 在一个单独的数据结构中
      • 目录条目保存有文件名和inode number
      • 文件属性放在inode里

问题：如果目录中有很长的文件名怎么办

  1. 给储存名字的地方的大小固定大一点
  2. Directory entry comprises fixed and variable portion (in line) 缺点：
    • 文件移除的时候会出现大小不同的间隔
    • 文件名可能跨页，导致页错误
  3. 目录条目固定大小，但是存放文件名的地方是一个指向对堆区的指针，指向文件名 缺点：管理堆区；页错误同样会发生

Share Files

Hard Link：两个目录有共享文件，则分别指向同一个inode。

Symbolic Link（Soft Link）：如果一个目录下想创建另一个文件的共享文件，则创建一个类型为Link的文件，文件内保存有共享文件的路径。

Hard Link 文件的删除：

  • 在每个inode中增加引用次数
  • 计算指向该inode的引用次数
  • 当删除一个Link时，引用次数减1
  • 当引用次数为0时，删除共享文件的file data

软Link 文件删除：

Hard Link的限制：

  • 不能跨分区建立连接
  • 如果其中一个文件被移动到另一个文件系统，则会将其复制，并相应地调整两个文件的链接计数
  • 只用管理员才可以建立对目录的硬链接

Soft Link的限制：

  • Extra space on disk and extra i-node to store the link file
  • Extra overhead in the traversing path
  • If the original file is moved to a different location, it can no longer be accessed via the symbolic link (dangling link)
  • Having multiple copies of a file may set copied when dumping a file onto a tape.

block size：

  • Large：higher data rate, lower space utilization
  • Small： lower data rate, higher space utilization

追踪空余的块

  • Linked list
  • Bit-Map：每个块对应一位，1表示空，0表示非空
  • counting

Linked list vs Bit-Map：

  • 存放空块号的block要求，Bit-Map远小于Linked list

文件系统的backup 备份

  • Physical dump
  • Logical dump
操作系统
This post is licensed under CC BY 4.0 by the author.