浅谈档案系统

你是否想过:

电脑是如何储存我们所建立的档案?
为什麽要做磁碟重组?

如果不知道问题的答案，就跟着笔者一起阅读作业系统追寻问题的答案吧!

进入正题

参考 Operating System Concepts - 9th 一书对 File system 的描述:

File system resides on secondary storage (disks)
File system organized into layers
- application programs
  process 发出读取需求并提供对应路径
- logical file system
  检查储存权限
- file-organization module
  将路径转换成物理地址
- basic file system
  读取物理地址
- I/O control
  实际的 I/O 控制
- devices
  从储存装置读取资料

档案系统负责了逻辑块与物理块之间的转换、管理剩余空间并分配记忆体。采用分层的设计可以降低档案系统的复杂度，实务上，不同档案系统的分层都会有些微的差异。

档案系统的多元性

作业系统可能支援一个或多个以上的档案系统，常见的档案系统有: FAT 、 exFAT 、 NTFS 、 HFS 、 HFS+ 、 ext2 、 ext3 、 ext4 、 ODS-5 、 btrfs 、 XFS 、 UFS 、 ZFS 等。

这里的作业系统包含常见的作业系统 (Mac OS, Windows, Android, UNIX, Linux...)以及一些运作在特殊装置的作业系统 (印表机、随身听等等)。

从理论到实务: 吃拉面也能学会 FAT32 档案系统

根据恐龙书，我们可以得知档案目录的实作有两种方法，分别是:

Linear List
Linear List 纪录了所有档案的位置(使用指标指向档案的第一个位址)

File name	Address (First block)
index.js	1
readme.md	20

Hash table

因为 Hash table 的特性，如果以 Hash table 实作档案目录，可以大幅优化档案的查询速度。不过，也因为该资料结构的缺点，会有碰撞和增加空间使用的问题。

档案目录纪录了档案 (First block) 的物理位址，不过一个档案通常是由多个 block 组成。因为这样，档案系统也设计了 Block 的分配方法:

Contiguous allocation

File	Start	Length
readme	0	2
main.c	2	3
index.js	5	3

根据上面的配置方法，档案在储存装置的分配会像是:

0	1	2	3	4	5	6	7
readme	readme	main.c	main.c	main.c	index.js	index.js	index.js

Linked allocation

Contiguous allocation 的优点显而易见: 因为是连续记忆体，所以读档速度极快。 But!!! Contiguous allocation 也有非常明显的缺陷，以拉面的故事为例: 笔者之前在中山区某知名拉面店门口排队，店内只有约 10 个位置排在吧台，看起来就像是一条连续记忆体。笔者那天跟其余两位朋友排队，当时店内有 3 个空位:

1	2	3	4	5	6	7	8	9	10
X	空	X	X	空	X	X	空	X	X

因为 Contiguous allocation 的特性，我们必须坐在一块，这样就出现了一个问题: 明明有足够的位子，我们却无法入坐享受热腾腾的拉面，只能眼睁睁看着孤独的拉面猎人比我们先入坐 : )
为了阻止这样的悲剧，Linked allocation 出现了!

1	2	3	4	5	6	7	8	9	10
X	朋朋1	X	X	朋朋2	X	X	朋朋3	X	X

朋朋 1 知道朋朋 2 坐在第五个位置，朋朋 2 知道朋朋 3 坐在第八个位置，而档案目录会记录朋朋 1 的位置。

FAT32

如果看到这里你还没离开，恭喜你已经了解 FAT32 的设计了 \ (^ _ ^) /

Indexed allocation

Linked allocation 虽然让我们能顺利吃到拉面，但同行的朋友需要纪录其他人的位置，应该还有更聪明的办法吧!当众人陷入沉思时，资料科学家说话了:

边吃拉面一边群组通话不就好了?

对阿，开个群聊不就解决了吗?让我们来看看 Indexed allocation 的设计:

档案目录纪录了档案的 Index block，而存放在磁碟中的 Index block 就像是群组聊天室，让同行的拉面朋朋都可以参与视讯。
关於磁碟重组

当店内同行的客人分别坐在不同的地方时，机灵的拉面店店员可以请客人挪动位子，让同行的人尽可能的坐在一块。
当资料被写在一起，磁碟的读写头不需要不停的移动，一圈就能读完所需资料，因此，磁碟重组(重新分配坐位)可以大幅的提升磁碟的读写速度。

Virtual File System

上图为 Linux 的档案系统架构。

Virtual file system 使用物件导向开发，它让使用者 / 开发者在操作档案时不需要了解各个档案系统的实作，只需要呼叫 System call 就可以达到操作档案的目的。

换言之，有了 Virtual file system，管你拉面店放圆桌还是吧台，我通通都能处理!

不只如此，有了 Virtual file system 让作业系统可以存取多个不同档案系统的装置:

file descriptor

以下内容取自叫人头昏眼花的 stdio library 一文。

在 Unix 或是 Unix-like 中，作业系统抽象了一层资料结构用来存取 File, input / output 资源，该资料结构称为 File descriptor。并且，File descriptor 是属於 POSIX API 的一部份，在符合 POSIX 的作业系统上，每一个 Process (除了守护程序) 都应该具备至少三个 File descriptor，分别是:

Integer value (>=0)	Name	<stdio.h> file stream
0	Standard input	stdin
1	Standard output	stdout
2	Standard error	stderr

inode

inode 的设计最早可以追朔到第一版的 UNIX 作业系统，至今，大部分的 UNIX-like 都采用类似的档案系统设计，就让我们一起来看看什麽是 inode 吧!

维基百科对 inode 的定义

inode (index node) 是指在许多「类 Unix 档案系统」中的一种资料结构，用於描述档案系统物件（包括档案、目录、装置档案、 socket 、管道等）。每个 inode 储存了档案系统物件资料的属性和磁碟块位置。档案系统物件属性包含了各种元资料，如：最後修改时间、使用者群组 (owner) 和权限资料。

What's metadata

metadata (元资料) 这个名词对多数开发者都不算陌生，就像是原子操作这个名词一样，我们无法立刻了解元资料到底是什麽资料。
实际上，Metadata 就是一个用来描述资料的资料，举例来说，在 *.html 档案中，我们可以在 <head> 里面找到许多 metadata 的 Target，这些标签都是用来描述这个 *.html 档案。

inode table

在了解 file descriptor 後，我们可以在上图看到每个 file descriptor 都会指向一个全域的档案表，档案表则会指向 inode table。
inode table 其实就是一个存放 inode 的阵列，在档案系统中，他会记录所有的档案 (inode)。

xv6 中的 inode

xv6 是一个研究/教学用途的小型作业系统，他对於档案系统有完整的实作。
在 xv6 的档案系统中，inode 有两种意义:

dinode
```
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};
```
dinode 为实际存放在磁碟中的 inode，我们可以透过上方的程序码了解 dinode 结构中每个属性的定义:
- type 用来区分该 inode 是文件、目录还是特殊文件。如果 type 为 0，代表该 inode 是空闲状态。
- nlink 纪录有多少文件指向该节点，这个属性可以帮助档案系统判断该节点是否可以被回收。
- size 用来记录文件的字节数量。
- addrs 纪录 block 的实际位址。

inode

纪录在 Memory 上的 inode，是纪录在磁碟中的 inode 的副本。此外还记录了 Kernel 的相关资讯:

struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

作业系统如何读档?

我们在撰写 C 语言并用其读取档案时，会出现与下方程序类似的用法:

fp = fopen(file_name, "r");
while((ch = fgetc(fp)) != EOF)

实际上，我们可以把读档拆成好几个步骤:

fopen
Call system call
Virtual file system
File system
HDD

BTW: OS 透过 Driver 读取 HDD 的内容时，还需要考虑:

排程演算法
第一次执行 dir 指令或是开档案会比较慢，因为要从 File Control Block 查找资料。之後在开就会变快了(因为已经被 Cache 了)。
通常来说，第一个 Block 一定是 Root。

在这个过程中，一共做了 2 次记忆体存取:

Disk -> buffer (Kernel space)
Buffer (Kernal space) -> Buffer (User space)

总结

之前听到电子系上的前辈说什麽生活电磁学(?)，好啊!要互相伤害是不是?那我也来搞一个拉面档案系统阿! (读书读到头壳坏掉)。
本篇文章用愉快的步调学习枯燥乏味的档案系统，希望能够引起读者对作业系统的兴趣。

Reference

<<: [Day23]程序菜鸟自学C++资料结构演算法 – 插入排序法(Insertion Sort)

>>: 第22天~JSON / GSON

浅谈档案系统

进入正题

档案系统的多元性

从理论到实务: 吃拉面也能学会 FAT32 档案系统

Virtual File System

file descriptor

inode

维基百科对 inode 的定义

What's metadata

inode table

xv6 中的 inode

作业系统如何读档?

总结

Reference

[DAY14] 在 Azure Machine Learning 里 Label data（下）

【Day 21】卷积神经网路（Convolutional Neural Network, CNN）（上）

Day 5 基本型别 - part 2

[Day22] Flutter GetX with Dio (一)

资安学习路上-渗透测试实务1

Leetcode 挑战 Day 06 [66. Plus One]

心得总结

Android Studio初学笔记-Day5-TextView

30天学会C语言: Day 23-被消失的型别

DAY 02 CSS 预处理器