文件管理

0x00 基本概念

系统运行时，计算机以进程为基本单位进行资源的调度和分配，在用户进行输入、输出中，则以文件为基本单位。 文件系统提供了与二级存储相关的资源的抽象，让用户能在不了解文件的各种属性、文件存储介质的特征以及文件在存储介质上的具体位置等情况下，方便快捷地使用文件。

用户通过文件系统建立文件，提供应用程序的输入、输出，对资源进行管理。我们通过自底向上的形式来描述文件的结构如下：

• 数据项：数据项是文件系统中最低级的数据组织形式，分为如下两种类型：
  • 基本数据项：用于描述一个对象的某种属性的一个值，如姓名、日期或证件号等，是数据中可命名的最小逻辑数据单位，即原子数据。
  • 组合数据项：由多个基本数据项组成
• 记录：记录是一组相关的数据项的集合，用于描述一个对象在某方面的属性，如一个考生报名记录包括姓名、出生日期、报考学校代号、身份证等一系列域
• 文件：文件是指由创建者所定义的一组相关信息的集合，逻辑上可分为两种：
  • 有结构文件：文件由一组相似记录组成，如报考某学校的所有考生的报考信息记录，又称为记录式文件
  • 无结构文件：则被看成是一个字符流，比如一个二进制文件或字符文件，又称为流式文件

文件属于抽象数据类型。文件有如下几个基本操作：

• 创建文件
• 写文件
• 读文件
• 删除文件
• 文件重定位（或文件寻址）：按条目搜索目录，将当前文件设置为给定值，并且不会读、写文件
• 截断文件：文件所有属性不变，并删除文件内容，将其长度置为0并释放空间

每个打开的文件都有如下关联信息：

• 文件指针：系统跟踪上次读写位置作为当前文件位置指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存
• 文件打开计数器：文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间不够用。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件，该计数器跟踪打开和关闭的数量，当该计数为0时，系统关闭文件，删除该条目。
• 文件磁盘位置：绝大多数文件操作都要求系统修改文件数据，该信息保存在内存中，以免每个操作都从磁盘中读取
• 访问权限：每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等），该信息保存在进程的打开文件表中，以便操作系统能允许或拒绝之后的I/O请求

对于一个文件的访问常由用户访问权限和文件属性共同限制。

读取一个文件的过程

• 首先用open系统调用打开文件，open的参数中包含文件的路径名和文件名
• 使用read读取文件，其中read仅使用open所返回的文件描述符，并不使用文件名作为参数，read要求提供三个参数：1.文件描述符，2.缓冲区首址 3.传送的字节数

0x01 文件的逻辑结构

文件的逻辑结构是从用户的观点出发看到的文件的组织形式，文件的逻辑结构与存储介质特性无关。

0x00 无结构文件

无结构文件是最简单的文件组织形式，又称为流式文件，无结构文件将数据按顺序组织为记录并累积保存，以字节（Byte）为单位，对其中记录的访问只能通过穷举的方式。

0x01 有结构文件

有结构文件又称为记录式文件，按其组织形式可以进一步分为：

• 顺序文件：文件中的记录一个接一个地顺序排列，记录通常是定长的。可以顺序存储或以链表的形式存储，在访问时按照顺序搜索文件，其又分为两种结构：

  • 串结构：记录之间的顺序与关键字无关，比如由时间确定，按照存入时间的先后排列
  • 顺序结构：文件中所有记录按关键字顺序排列

  对记录的批量操作中，对顺序文件的效率是所有逻辑文件中最高的，只有顺序文件可以存储在磁带上，但是对顺序文件的查找、修改和增加比较困难。

• 索引文件：对变长记录文件只能进行顺序查找，系统开销较大，为此可以建立一张索引表以加快检索速度，索引表本身是定长记录的顺序文件。
  

• 索引顺序文件：将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该关键字的值以及指向该记录的指针。既能随机访问又能顺序访问。
  

• 直接文件或散列文件：给定记录的键值或通过hash函数转换的键值直接决定记录的物理位置，这种映射结构没有顺序的特性。

0x02 目录结构

0x00 文件控制块

操作系统为实现目录管理，引入了文件控制块（FCB）这种数据结构。文件控制块是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项。

FCB主要包含以下信息：

• 基本信息：如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等
• 存取控制信息：如文件存取权限等
• 使用信息：如文件建立时间、修改时间等

FCB必需连续存放。打开文件的过程即为将该文件的FCB存入内存的活跃文件目录表，而一个文件目录项就是一个FCB。。

在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需调入内存。因此，有的系统（如UNIX）釆用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点，在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。

存放在磁盘上的索引结点称为磁盘索引结点，UNIX中的每个文件都有一个唯一的磁盘索引结点，主要包括以下几个方面：

• 文件主标识符：拥有该文件的个人或小组的标识符
• 文件类型：包括普通文件、目录文件或特别文件
• 文件存取权限：各类用户对该文件的存取权限
• 文件物理地址：每个索引结点中含有13个地址项，即iaddr(0) ~ iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号
• 文件长度：以字节为单位
• 文件链接计数：在本文件系统中所有指向该文件的文件名的指针计数
• 文件存取时间：本文件最近被进程存取的时间、最近被修改的时间以及索引结点最近被修改的时间

文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用。在内存索引结点中又增加了以下内容：

• 索引结点编号：用于标识内存索引结点
• 状态：指示i结点是否上锁或被修改
• 访问计数：每当有一进程要访问此i结点时，计数加1，访问结束减1
• 逻辑设备号：文件所属文件系统的逻辑设备号
• 链接指针：设置分别指向空闲链表和散列队列的指针

在目录层次上所需要进行的操作：

• 搜索：当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项
• 创建文件：当创建一个新文件时，需要在目录中增加一个目录项
• 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
• 显示目录：显示目录的内容，如显示该用户目录中的所有文件及属性
• 修改目录：某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项

0x01 单级目录结构

在整个文件系统中只建立一张目录表，每个文件占一个目录项，如图：

当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。当建立一个新文件时，必须先检索所有目录项以确保没有重名的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项中。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。单级目录结构实现了按名存取，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且不适用于多用户的操作系统。

0x02 两级目录结构

单级目录很容易造成文件名称的混淆，可以考虑釆用两级方案，将文件目录分成主文件目录（Master File Directory, MFD）和用户文件目录（User File Directory, UFD）两级，如图：

主文件目录项记录用户名及相应用户文件目录所在的存储位置。用户文件目录项记录该用户文件的FCB信息。当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD，这既解决了不同用户文件的重名问题，也在一定程度上保证了文件的安全。两级目录结构可以解决多用户之间的文件重名问题，文件系统可以在目录上实现访问限制，但是两级目录结构缺乏灵活性，不能对文件分类。

0x03 多级（树形）目录结构

将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构：

用户要访问某个文件时用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件的通路上的所有目录名与数据文件名用分隔符链接起来而成。从根目录出发的路径称绝对路径。当层次较多时，每次从根目录查询浪费时间，于是加入了当前目录，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件。

树形目录结构可以方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，在树形目录中查找一个文件，需要按路径名逐级访问中间结点，这就增加了磁盘访问次数，无疑将影响查询速度。

0x04 无环图目录结构

树形目录结构可便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享：

当某用户要求删除一个共享结点时，若系统只是简单地将它删除，当另一共享用户需要访问时，却无法找到这个文件而发生错误。为此可以为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加1，每当某用户提出删除该结点时，计数器减1。仅当共享计数器为0时，才真正删除该结点，否则仅删除请求用户的共享链。

对于共享文件仅存在一个真正的文件副本，方便地实现了文件共享，但也使系统管理变得复杂，任何改变都会为其他用户所见。

0x03 文件共享

0x00 基于索引结点的共享方式

基于索引结点的共享方式也就是硬链接，在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件：

在这种共享方式中引用索引结点，即诸如文件的物理地址及其他的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还应有一个链接计数count，用于表示链接到本索引结点（亦即文件） 上的用户目录项的数目。当count=2时，表示有两个用户目录项链接到本文件上，或者说是有两个用户共享此文件。当count=0时，表示没有用户使用该文件，系统将负责删除该文件。

0x01 利用符号链实现文件共享

为使用户B能共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F，并将文件F写入用户B的目录中，以实现用户B的目录与文件F的链接，在新文件中只包含被链接文件F的路径名，这样的链接方法被称为符号链接，也称为软链接。

在利用符号链方式实现文件共享时，只有文件的拥有者才拥有指向其索引结点的指针。而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删除后，其他用户通过符号链去访问它时，会出现访问失败，于是将符号链删除，此时不会产生任何影响。当然，利用符号链实现文件共享仍然存在问题，假如一个文件釆用符号链方式共享，当文件拥有者将其删除，而在共享的其他用户使用其符号链接访问该文件之前，又有人在同一路径下创建了另一个具有同样名称的文件，则该符号链将仍然有效，但访问的文件已经改变，从而导致错误。

在符号链的共享方式中，当其他用户读共享文件时，需要根据文件路径名逐个地查找目录，直至找到该文件的索引结点。因此，每次访问时都可能要多次地读盘，使得访问文件的开销变大并增加了启动磁盘的频率，因此硬链接的查找速度要比软链接快。此外，符号链的索引结点也要耗费一定的磁盘空间。符号链方式有一个很大的优点，即网络共享只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。

硬链接和软链接都是文件系统中的静态共享方法，在文件系统中还存在着另外的共享需求，即两个进程同时对同一个文件进行操作，这样的共享可以称为动态共享。

0x04 文件系统的实现

0x00 文件系统的层次结构

如图：

• 用户调用接口：文件系统为用户提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件，建立、删除目录等。此层由若干程序模块组成，每一模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块
• 文件目录系统：文件目录系统的主要功能是管理文件目录，其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织在存储设备上的文件目录结构、调用下一级存取控制模块
• 存取控制验证：实现文件保护主要由该级软件完成，它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访问的合法性
• 逻辑文件系统与文件信息缓冲区：逻辑文件系统与文件信息缓冲区的主要功能是根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号
• 物理文件系统：物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址
• 分配模块：分配模块的主要功能是管理辅存空间，即负责分配辅存空闲空间和回收辅存空间
• 设备管理程序模块：设备管理程序模块的主要功能是分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备

0x01 目录的实现

在读文件前必须先打开文件，打开文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息，目录实现的基本方法有线性列表和哈希表两种。

最简单的目录实现方法就是使用存储文件名和数据块指针的线性列表。创建新文件时，必须首先搜索目录表以确定没有同名的文件存在，然后在目录表后增加一个目录项。删除文件则根据给定的文件名搜索目录表，接着释放分配给它的空间。若要重用目录项，可以将目录项标记为不再使用，或者将它加到空闲目录项表上，还可以将目录表中最后一个目录项复制到空闲位置，并降低目录表长度。釆用链表结构可以减少删除文件的时间。其优点在于实现简单，但是比较费时。

哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免冲突，最大的困难是哈希表长度固定以及哈希函数对表长的依赖性。

目录查询是通过在磁盘上反复搜索完成，需要不断地进行I/O操作，开销较大。所以，为了减少I/O操作，把当前使用的文件目录复制到内存，以后要使用该文件时只要在内存中操作，从而降低了磁盘操作次数，提高了系统速度。

0x02 文件实现

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块，常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。有的系统对三种方法都支持，但是更普遍的是一个系统只提供一种方法的支持。

重点在各种分配方式的特点以及需要在FCB中为其设计哪些相关描述字段。

0x00 连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上的一个线性排序，这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。一个文件的目录条目包括开始块的地址和该文件所分配区域的长度。如图：

连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快。缺点在于文件长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加，就需要大量移动盘块。此外，反复增删文件后会产生外部碎片，并且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。

0x01 链接分配

链接分配是釆取离散分配的方式，消除了外部碎片，故而显著地提高了磁盘空间的利用率。又因为是根据文件的当前需求，为它分配必需的盘块，当文件动态增长时，可以动态地再为它分配盘块，故而无需事先知道文件的大小。此外对文件的增删改也非常方便。链接分配又可以分为隐式链接和显式链接两种形式。

隐式链接中，每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方，除最后一个盘块外，每一个盘块都有指向下一个盘块的指针，这些指针对用户是透明的，目录包括文件第一块的指针和最后一块的指针，就相当于把文件内容当做一个链表中的数据项来进行了存储。如图：

创建新文件时，目录中增加一个新条目。每个目录项都有一个指向文件首块的指针。该指针初始化为NULL以表示空文件，大小字段为0。写文件会通过空闲空间管理系统找到空闲块，将该块链接到文件的尾部，以便写入。读文件则通过块到块的指针顺序读块。

隐式链接分配的缺点在于无法直接访问盘块，只能通过指针顺序访问文件，以及盘块指针消耗了一定的存储空间。隐式链接分配的稳定性较差，系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

显式链接是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的物理地址字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故称该表为文件分配表（File Allocation Table, FAT）。

0x02 索引分配

链接分配解决了连续分配的外部碎片和文件大小管理的问题。但是，链接分配不能有效支持直接访问（FAT除外）。索引分配解决了这个问题，它把每个文件的所有的盘块号都集中放在一起构成索引块（表），如图：

每个文件都有其索引块，这是一个磁盘块地址的数组。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第i块，通过索引块的第i个条目的指针来查找和读入所需的块。

创建文件时，索引块的所有指针都设为空。当首次写入第i块时，先从空闲空间中取得一个块，再将其地址写到索引块的第i个条目。

索引分配支持直接访问，且没有外部碎片问题。其缺点是由于索引块的分配，增加了系统存储空间的开销。索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件，可以釆用以下机制来处理这个问题：

• 链接方案：一个索引块通常为一个磁盘块，为了处理大文件，可以将多个索引块链接起来
• 多层索引：多层索引使第一层索引块指向第二层的索引块，第二层索引块再指向文件块。这种方法根据最大文件大小的要求依次往下扩展层数，其中两层索引允许的最大文件为4GB
• 混合索引：将多种索引分配方式相结合的分配方式

0x03 比较

	访问第n个记录	优点	缺点
顺序分配	需访问磁盘1次	顺序存取速度怏，当文件是定长时可以根据文件起始地址及记录长度进行随机访问	要求连续的存储空间，会产生外部碎片，不利于文件的动态扩充
链接分配	需访问磁盘n次	无外部碎片，提髙了外存空间的利用率，动态增长较方便	只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗外存空间
索引分配	m级需访问磁盘m+1次	可以随机访问，易于文件的增删	索引表增加存储空间的开销，索引表的查找策略对文件系统效率影响较大

0x03 文件存储空间管理

一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可以由多个物理盘组成，如图：

在一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息FCB的空间（目录区）是分离的。逻辑卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放逻辑卷信息的超级块。

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此文件存储设备的管理实质上是对空闲块的组织和管理，它包括对空闲块的组织分配与回收。

文件存储器空间的管理一般有如下几种方法：

• 空闲表法：属于连续分配方式，它与内存的动态分配方式类似，为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项，其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息，再将所有空闲区按其起始盘块号递增的次序排列。
  空闲盘区的分配与内存的动态分配类似，同样有类似的首次适应算法、循环首次适应算法等。

• 空闲链表法：将所有空闲盘区拉成一条空闲链，根据构成链所用的基本元素不同，可把链表分成两种：空闲盘块链和空闲盘区链。

  • 空闲盘块链是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。请求分配存储空间时，系统从链首开始，依次摘下适当的数目的空闲盘块分配给用户。释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法的优点是分配和回收一个盘块的过程非常简单，缺点是在为一个文件分配盘块时，可能要重复多次操作。
  • 空闲盘区链是将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小（盘块数）的信息。分配盘区的方法与内存的动态分区分配类似，通常釆用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。

  空闲表法和空闲链表法都不适合用于大型文件系统，因为这会使空闲表或空闲链表太大。

• 位示图法：是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。值为0时，表示对应的盘块空闲，值为1时，表示对应的盘块已分配。盘块的分配一般由如下几个步骤：

  • 顺序扫描位示图，从中找出一个或一组其值为0的二进制位
  • 将所找到的一个或一组二进制位，转换成对应的盘块号
  • 修改位示图，令当前盘块所对于的二进制位的值为1

• 成组链接法：在UNIX系统中釆用的是成组链接法，这种方法结合了空闲表和空闲链表两种方法，克服了表太大的缺点。其将顺序的n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，如此继续，直至所有空闲扇区均予以链接。系统只需要保存指向第一个空闲扇区的指针。通过这种方式可以迅速找到大批空闲块地址。如图：
  
  表示文件存储器空闲空间的位向量表或第一个成组链块以及卷中的目录区、文件区划分信息都需要存放在辅存储器中，一般放在卷头位置，在UNIX系统中称为超级块。 在对卷中文件进行操作前，超级块需要预先读入系统空间的主存，并且经常保持主存超级块与辅存卷中超级块的一致性。

0x05 磁盘组织与管理

0x00 基本概念

磁盘盘面上数据存储的一组同心圆称为磁道，每个磁道与磁头一样宽，磁道又划分为扇区，每个扇区固定存储大小，一个扇区称之为一个盘块。所有盘片上相对位置相同的磁道组成柱面。磁盘的存取能力受限于最内道的最大记录密度。

磁盘地址用柱面号，盘面号，扇区号来表示。

0x01 磁盘调度算法

寻找时间$T_s$：即为将磁头移动到指定磁道所需要的时间，设其跨越了n条磁道，以及启动磁臂的时间为s，则：

$$T_s=k\times n+s \\ 其中k为常数$$

延迟时间$T_r$：即为磁头定位到某一扇区的时间，设磁盘旋转速度为r，则：

$$T_r=\frac{1}{2r}$$

假设转速5400rpm则转一周即为$\frac{60}{5400}=11.1\text{ms}$，则$T_r=\frac{11.1}{2}=5.55\text{ms}$

传输时间$T_t$：即为从磁盘读出或向磁盘写入数据所经历的时间，设每秒钟的转数为r，b为读写的字节数，N为一个磁道上的字节数，则：

$$T_t=\frac{b}{rN}$$

总存储时间$T_a$则为上述的总和：

$$T_a=T_s+T_r+T_t$$

0x02 格式化

格式化即为磁盘初始化：

• 低级格式化（物理分区）：将磁盘分为扇区以便磁盘控制器能够进行读和写
• 逻辑格式化（创建文件系统）：将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间以及建立文件系统根目录

0x0 计算题总结

常用结果：

$$2^{5}=32 \\ 2^{6}=64 \\ 2^{8}=256 \\ 2^{10}=1024$$

地址索引：

• 直接地址索引就相当于地址项，每个直接地址索引指向一个数据块
• 间接地址索引就相当于用数据块来保存了多个地址项

$$设有n_i个i级地址索引，其中i=0时为直接地址索引\\ 单个数据块的大小为s，单个地址项的大小为a，则其所指向的总的数据块的大小为：\\ S=\sum_{i=0}^n n_i\times (\frac{s}{a})^i \times s$$

N级索引下单个文件最大长度：

$$类比于上面的那个地址索引：\\ n级地址索引，单个数据块大小为s，单个地址项大小为a，则单个文件最大长度：\\ S=(\frac{s}{a})^n\times s$$

位示图（从1开始计数的情况下）：

$$已知盘块号b，每行的位数n，求行号i和列号j：\\ i=(b-1)\div n+1 除法仅保留整数\\ j=(b-1) \% n+1\\ 已知第i行第j列，每行的位数n，求盘块号b：\\ b=n\times (i-1)+j$$

对于启动磁盘的次数，如果题目中问你的是完成修改后，那你一定要考虑修改是读取加写入的过程。此时，读取时已经得到了其物理地址，所以此时写入的过程就无需再获得物理地址，此时仅增加一次磁盘的启动次数。

使用间接地址索引时，需要先访盘以获取文件所在的磁盘块地址，然后再进行读取，不要忘了读取时的这一次访盘，访问到几级索引就是为了获取文件地址访问了几次磁盘，其中直接索引往往会在内存中。

FAT的最大长度：

$$\text{FAT每个表目的位数}=\lceil\log_2(\text{磁盘的块数})\rceil \\ 位数\div8即为每个表目的字节数\\ \text{FAT的大小}=\text{FAT每个表目的字节数}\times\text{磁盘的块数}$$