文章目录

前言
一、文件访问方法
- 1.顺序访问
- 2.直接访问
- 3.索引访问
二、目录结构
- 1.一级目录
- - - 优点
    - 缺点
- 2.二级目录
- - - 二级目录系统的特点
- 3.树形结构目录
- 4.非循环图结构化目录
三、文件系统
- 文件系统结构
- 主引导记录（MBR）
- - - 当打开电脑时会发生什么
四、磁盘中的数据结构
- 1.引导控制块
- 2.卷控制块
- 3.目录结构（每个文件系统）
- 4.文件控制块
五、内存中的数据结构
- 1.内存安装表
- 2.内存目录结构缓存
- 3.全系统打开文件表
- 4.每个进程打开文件表
六、目录实现
- 1.线性列表
- - 特点
- 2.哈希表
- 3.分配方法
- - 连续分配
  - - 优点
    - 缺点
  - 链表分配
  - - 优点
    - 缺点
  - 文件分配表
  - - 优点
    - 缺点
  - 索引分配
  - - 优点
    - 缺点
  - 链接索引分配
  - - 单级链接索引分配
    - 多级索引分配
  - 索引节点
  - 空闲空间管理
  - - 1.位向量
    - 2.链接列表
  - 磁盘调度
  - - 寻道时间
    - 倒换延迟
    - 转换时间
    - 磁盘访问时间
    - 磁盘响应时间
    - 磁盘调度的目的
    - 磁盘调度算法的目标
    - 磁盘调度算法

前言

文件可以定义为一个存储记录序列的数据结构。文件存储在文件系统中，该文件系统可能存在于磁盘或主存储器中。文件可以是简单的（纯文本）或复杂的（特殊格式）

一、文件访问方法

1.顺序访问

大多数操作系统按顺序访问文件。在顺序访问中，操作系统逐字读取文件。维护一个指针，该指针最初指向文件的基地址。如果用户想要读取文件的第一个字，那么该指针将该字提供给用户并将其值增加一个字。这个过程一直持续到文件结束。

2.直接访问

在数据库系统中，直接访问通常是必须的。在大多数情况下，需要从数据库中过滤信息。在这种情况下，顺序访问可能非常慢并且效率低下。直接访问将提供所需的结果，尽管操作系统必须执行一些复杂的任务。但这通常在数据库应用程序中实现。

3.索引访问

如果文件可以在任何字段上排序，那么可以将索引分配给一组特定的记录。但是，特定的记录可以通过其索引来访问。索引只不过是文件中记录的地址。

索引访问中，在大型数据库中搜索变得非常快捷，但需要在内存中留出一些额外的空间来存储索引值。

二、目录结构

目录可以被定义为磁盘上相关文件的列表。该目录可以存储一些或整个文件属性。

为了在不同的操作系统上获得不同文件系统的好处，可将硬盘划分为不同大小的分区数。分区也称为卷或小型磁盘。

每个分区必须至少有一个目录，其中可以列出分区的所有文件。为目录中的每个文件维护一个目录条目，该目录存储与该文件相关的所有信息。

一个目录可被视为一个文件，其中包含一堆文件的元数据。每个目录都支持文件上的许多常用操作：
<1>文件创建
<2>搜索文件
<3>文件删除
<4>重命名文件
<5>遍历文件
<6>文件列表

1.一级目录

每个文件包含一个条目的目录出现在磁盘文件系统上

这种类型的目录可以用于简单的系统

优点

<1>实现非常简单
<2>如果文件的大小非常小，则搜索会非常快
<3>由于只有一个目录，因此文件创建，搜索和删除非常简单

缺点

<1>不能有两个具有相同名称的文件
<2>该目录可能非常大，因此搜索文件可能需要很长时间
<3>保护不能为多个用户执行
<4>没有办法将相同类型的文件分组
<5>为每个文件选择唯一的名称有点复杂，并限制了系统中的文件数量，因为大多数操作系统限制了用于构建文件名的字符数。

2.二级目录

在两级目录系统中，可以为每个用户创建一个单独的目录。有一个主目录，其中包含专用于每个用户的单独目录。对于每个用户，第二级存在不同的目录，其中包含用户文件组。系统不允许用户未经许可进入其他用户的目录。

二级目录系统的特点

<1>每个文件的路径名为/User-name/directory-name/
<2>不同的用户可以拥有相同的文件名。
<3>由于只有一个用户的列表需要遍历，搜索变得更有效率
<4>同一种文件不能分组到一个特定用户的单个目录中
每个操作系统都将一个变量保存为包含当前目录名称（当前用户名）的PWD，以便可以适当的进行搜索。

3.树形结构目录

在树结构的目录系统中，任何目录条目都可以是文件或子目录。树结构的目录系统克服了两级目录系统的缺点。现在可以将类似的文件分组到一个目录中。

每个用户都有自己的目录，并且不能进入其他用户的目录。但是，用户有权读取根数据，但他不能写入或修改此数据。只有系统管理员才能完全访问根目录。

在这个目录结构中搜索更有效率。使用当前工作目录的概念。一个文件可以通过两种类型的路径访问，无论是相对的还是绝对的。

绝对路径是文件相对于系统根目录的路径，而相对路径是相对于系统当前工作目录的路径。在树形目录系统中，用户有权创建文件以及目录。

4.非循环图结构化目录

树形目录系统不允许同一文件存在于多个目录中，因此共享是树形目录系统中的主要关注点。我们可以通过使目录成为一个非循环图来提供共享。在这个系统中，两个或多个目录项可以指向相同的文件或子目录。该文件或子目录在两个目录条目之间共享。

这些类型的目录图可以使用链接或别名来制作。可以为同一个文件创建多个路径。链接可以是符号(逻辑)或硬链接(物理)。

如果文件在非循环图结构化目录系统中被删除，那么：
<1>在软连接的情况下，文件只是被删除，则会留下一个悬挂指针
<2>在硬链接的情况下，当它的所有引用被删除，实际文件也将被删除。

三、文件系统

文件系统是负责文件管理的操作系统的一部分。它提供了一种机制来存储数据和访问文件内容，包括数据和程序。一些操作系统将所有内容视为Ubuntu文件。

文件结构 – 前面已经了解可存储文件的各种数据结构。文件系统的任务是保持最佳的文件结构。

恢复可用空间 – 每当文件从硬盘中删除时，磁盘中都会创建一个可用空间。可能有很多这样的空间需要被恢复，以便将它们重新分配给其他文件。

磁盘空间分配给这些文件 – 关于文件的主要问题是决定将文件存储在硬盘上的何处。本教程之后的章节将介绍各种磁盘调度算法。

跟踪数据位置 – 文件可以或不可以仅存储在一个块内。它可以存储在磁盘上的非连续块中。需要跟踪部分文件所在的所有块。

文件系统结构

文件系统通过允许以方便的方式存储，定位和检索数据来提供对磁盘的有效访问。文件系统必须能够存储文件，找到文件并检索文件。大多数操作系统对包括文件系统在内的每个任务都使用分层方法。文件系统的每一层都负责一些活动。
<1>当应用程序要求提供文件时，第一个请求将被引导至逻辑文件系统。逻辑文件系统包含文件和目录结构的元数据。如果应用程序没有文件所需的权限，那么该图层将会引发错误。逻辑文件系统也验证文件的路径。

<2>通常，文件被分成各种逻辑块。文件将存储在硬盘中，并从硬盘中检索。硬盘分为各种轨道和扇区。因此，为了存储和检索文件，逻辑块需要映射到物理块。该映射由文件组织模块完成。它也负责自由空间管理。

<3>一旦文件组织模块决定了应用程序需要哪个物理块，它就会将这些信息传递给基本文件系统。基本文件系统负责将命令发布到I/O控制以获取这些块。

<4>I/O控件包含使用它可以访问硬盘的代码。这些代码被称为设备驱动程序。 I/O控制也负责处理中断。

主引导记录（MBR）

主引导记录是存在于任何硬盘的第一个扇区中的信息。它包含有关操作系统在硬盘中的位置和位置的信息，以便它可以在RAM中引导。
MBR有时称为主分区表，因为它包含一个分区表，用于查找硬盘中的每个分区。

主引导记录(MBR)还包括一个程序，该程序读取包含操作系统的分区的引导扇区记录。

当打开电脑时会发生什么

由于主存储器是具有易失性，所以当我们打开计算机时，CPU不能直接访问主内存。但是，有一个特殊的程序存储在ROM中，叫做:BIOS，它会第一次被CPU访问。

BIOS包含代码，通过执行它，CPU访问MBR的第一个硬盘分区。它包含硬盘所有分区的分区表。

因为MBR包含有关操作系统存储位置的信息，并且它还包含可以读取分区引导扇区记录的程序，因此CPU会获取所有这些信息并将操作系统加载到主内存中。

四、磁盘中的数据结构

1.引导控制块

启动控制块包含从该卷启动操作系统所需的所有信息。它在UNIX文件系统中被称为引导块。在NTFS中，它被称为分区引导扇区。

2.卷控制块

卷控制会阻止有关该音量的所有信息，如块的数量，每个块的大小，分区表，指向空闲块和空闲FCB块的指针。在UNIX文件系统中，它被称为超级块。在NTFS中，此信息存储在主文件表内。

3.目录结构（每个文件系统）

目录结构(每个文件系统)包含文件名和指向相应FCB的指针。在UNIX中，它包含与文件名关联的索引节点编号。

4.文件控制块

文件控制块包含有关文件的所有详细信息，例如所有权详细信息，权限详细信息，文件大小等。在UFS中，此详细信息存储在inode中。在NTFS中，此信息作为关系数据库结构存储在主文件表内。

五、内存中的数据结构

1.内存安装表

内存中安装表包含正在安装到系统的所有设备的列表。每当连接维护到设备时，其输入将在安装表中完成。

2.内存目录结构缓存

这是CPU最近访问的目录列表。列表中的目录也可以在不久的将来被访问，所以最好将它们临时存储在缓存中。

3.全系统打开文件表

这是特定时间系统中所有打开文件的列表。每当用户打开任何文件进行读取或写入时，都会在此打开的文件表中进行输入。

4.每个进程打开文件表

它是受到每个进程打开的文件列表。由于系统中每个打开的文件都有一个列表，因此它只包含指向系统范围表中相应条目的指针。

六、目录实现

有很多算法可以使用这些目录来实现。但是，选择合适的目录实现算法可能会显着影响系统的性能。

1.线性列表

在这个算法中，目录中的所有文件都保持为单行列表。每个文件都包含指向分配给它的数据块的指针和目录中的下一个文件。

特点

<1>在创建新文件时，检查整个列表是否新文件名与现有文件名匹配。如果它不存在，则可以在开始或结束时创建该文件。因此，寻找一个唯一的名字是一个大问题，因为遍历整个列表需要时间。

<2>该列表需要在文件的每个操作(创建，删除，更新等)的情况下遍历，因此系统变得低效。

2.哈希表

要克服目录单链表实现的缺点，有一种替代方法就是哈希表。这种方法建议使用散列表和链表。

目录中每个文件的键值对都会生成并存储在哈希表中。键可以通过在文件名上应用散列函数来确定，而键指向存储在目录中的相应文件。

3.分配方法

有多种方法可用于为文件分配磁盘空间

单级链接索引分配

在索引分配中，文件大小取决于磁盘块的大小。要允许大文件，我们必须将几个索引块链接在一起。在链接索引分配中：
<1>提供文件名称的小标题
<2>前100个块地址的集合
<3>指向另一个索引块的指针
对于较大的文件，索引块的最后一个条目是一个指向另一个索引块的指针。这也被称为链接模式。
优点：它消除了文件大小限制
缺点：随机访问变得优点困难

多级索引分配

在多级指数分配中，有各种索引级别。有外层索引块包含指向内层索引块的指针，内层索引块包含指向文件数据的指针。
<1>外层索引用于查找内层索引
<2>内层索引用于查找所需的数据块
优点：随机访问变得更好，更高效
缺点：文件的访问时间会变长

索引节点

在基于UNIX的操作系统中，每个文件都由一个Inode索引。 Inode是创建文件系统时创建的特殊磁盘块。文件系统中的文件或目录数量取决于文件系统中的Inode数量。

Inode包含以下信息 –
<1>文件的属性(权限，时间戳，所有权详细信息等)

<2>包含指向文件的前12个块的指针的多个直接块。

<3>指向索引块的单个间接指针。如果文件不能被直接块完全索引，则使用单个间接指针。

<4>指向磁盘块的双重间接指针，该磁盘块是指向作为索引块的磁盘块的指针的集合。如果文件太大而无法通过直接块以及单个间接指针完全索引，则使用双索引指针。

<5>指向一个指针集合的磁盘块的三元索引指针。每个指针分别指向一个磁盘块，该块还包含一组指针，这些指针分别指向一个包含指向文件块的指针的索引块。

空闲空间管理

文件系统负责将空闲块分配给文件，因此它必须跟踪磁盘中存在的所有空闲块。主要有两种方法，使用它们管理磁盘中的空闲块

1.位向量

在这种方法中，空闲空间列表被实现为位图向量。它包含每个位代表每个块的位数。如果该块为空，则该位为1，否则为0。最初，所有块都是空的，因此位图向量中的每个位都包含1。随着空间分配的进行，文件系统开始为文件分配块并将各个位设置为0。

2.链接列表

这是空闲空间管理的另一种方法。这种方法建议将所有空闲块链接在一起，并在指向第一个空闲块的缓存中保留一个指针。因此，磁盘上的所有空闲块将用指针连接在一起。每当块被分配时，其先前的空闲块将被链接到其下一个空闲块。

磁盘调度

个进程需要两种类型的时间，CPU时间和IO时间。对于I/O，它请求操作系统访问磁盘。但是，操作系统必须足够满足每个请求，同时操作系统必须保持流程执行的效率和速度。操作系统用来确定接下来要满足的请求的技术称为磁盘调度。

一些专业术语：

寻道时间

寻道时间是将磁盘臂定位到满足读/写请求的指定磁道所用的时间。

倒换延迟

期望的扇区将自己倒换到可以访问R / W磁头的位置。

转换时间

这是传输数据所需的时间。

磁盘访问时间

磁盘访问时间=旋转延迟+搜索时间+传输时间

磁盘响应时间

这是每个请求等待IO操作所花费时间的平均值。

磁盘调度的目的

磁盘调度算法的主要目的是从IO请求队列中选择一个磁盘请求，并决定处理该请求的时间表。

磁盘调度算法的目标

<1>公平
<2>始终最高
<3>最小遍历时间

磁盘调度算法

<1>FCFS调度算法
<2>SSTF（最短寻找时间优先）算法
<3>SCAN调度
<4>C-SCAN调度
<5>LOOK调度
<6>C-LOOK调度