image.png

系统中的文件实际上是一个对象，包含数据和一系列操作。用户对文件进行读写产生了数据，而读写过程需要完成逻辑结构和物理结构上的转换、组织文件在磁盘上存放。

（一）文件形式

1. 概念

1.1 什么是文件？

文件=程序+数据，可以长期存放在硬盘或者存储器中，其中数据可以数字、字母或者二进制代码，不同的数据组织形式形成不同多文件逻辑结构——无结构文件和有结构文件。

1.2 如何描述文件？

当我们向对方介绍自己时，总会先介绍关于自己的一些基本信息，比如来自哪，年龄和喜好等等，这些用于描述个人的信息可以称为属性。文件也需要一些基本属性来描述，这些基本属性都保存在目录结构中。
常用的文件属性有：

• 名称：方便读取；
• 标识符：标识文件系统内文件的唯一标签；
• 类型：被支持不同类型的文件系统使用；
• 位置：指向设备和设备上文件的指针；
• 大小；
• 保护：访问控制信息；
• 时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息；

image.png

1.3 可以对文件进行哪些基本操作？

由操作系统提供调用对文件进行基本操作：

• 创建文件；
• 写文件；
• 读文件；
• 文件重定位；
• 删除文件；
• 截断文件。

2. 逻辑结构

因为数据的组织方式不同，也就有不同的文件逻辑结构。

2.1 有哪些数据组织方式？

当数据以字符流的形式记录，比如以二进制、或字符形成文件，则称为无结构文件；
而数据以一组记录的方式组成，例如在校学生记录，则成为有结构文件。

2.2 无结构文件

常见的无结构文件有源程序文件、目标代码文件。它们以字节为单位，对记录的访问只能通过穷举搜索的方法，管理简单，方便用户对其操作，但是对信息单位操作多的文件不适用。

2.3 有结构文件

有结构文件可以分为以下四种：

• 顺序文件

  
  image.png

• 索引文件

  
  image.png

• 索引顺序文件

  
  image.png

• 散列文件

  
  image.png

image.png

3. 目录结构

目录结构除了包含记录单个文件信息的文件目录，还需要一定的组织文件结构来提高检索速度。

1. 文件目录包含哪些内容？

文件目录作为查找文件的指路人，不仅要清楚文件名，还要知道查找文件的路径。

• 文件控制块（FCB）：存放控制文件需要的各种信息的数据结构，实现“按名存取”；

• 索引结点：用于读出文件的物理地址。

  
  image.png

image.png

2. 如何组织文件目录？

有四种方式组织文件：单级目录结构、二级目录结构、多级目录结构和无环图目录结构。

• 单级目录结构：整个文件系统只建立一张目录表，每个文件占一个目录项

image.png

• 二级目录结构：将文件目录分成文件目录和用户文件目录，前者用于记录用户文件目录所存在的存储位置，后者用于记录该用户文件的FCB信息。

image.png

• 多级目录结构：由二级目录结构发展而来，层次结构清晰，方便对文件进行管理和保护。

image.png

• 无环图目录结构：在树形目录结构的基础上增加一些指向同一结点的有向边，方便实现文件共享。

image.png

4. 文件共享

有时候多个用户或进程需要共享同一个文件，如果不能提供共享文件，会因每个用户有各自的副本导致存储空间的浪费。常用的文件共享方式有：基于索引结点的共享方式（硬链接）和利用符号链实现文件共享（软链接）。

• 基于索引结点的共享方式（硬链接）：多个用户共享的文件不放在目录项中，而是放在索引结点中，索引结点存放文件的物理地址、文件属性、链接计数器count等。当某个用户不再需要该文件时，count减1，并且删除自己目录中的相应目录项。系统根据count判断是否将共享文件删除。

  
  多个用户共享一个文件.png

某个用户删除共享文件.png

• 利用符号链实现文件共享（软链接）：B用户要想共享A用户的文件F，由系统创建一个LINK类型的新文件，也取名为F，并将F写入用户B的目录中，从而实现用户B的目录与文件F的链接。当A用户删除文件F时，B用户再去访问则访问失败。

image.png

5. 文件保护

对文件的保护通常采用事前预防机制：访问控制、口令保护和加密保护。

1. 访问控制

对文件的访问控制从设置文件访问类型出发，文件访问类型主要有：

• 读；
• 写；
• 执行；
• 添加；
• 删除；
• 列表清单

通过对用户划分权限来达到访问控制目的，因此要为每个文件和目录增加一个访问控制列表。常用的是精简的访问列表，该列表将用户分为三类：

• 拥有者：创建文件的用户；
• 组： 一组需要共享文件且具有类似访问的用户；
• 其他：系统内的所有其他用户。

2. 口令和密码

• 口令：用户在建立一个文件时提供一个口令，系统在建立FCB时将该口令附上；
• 密码：用户对文件加密，文件被访问时需要使用密钥。

（二）实现

了解了文件结构、目录结构，这都是逻辑结构，通过目录查找文件如何实现？

1. 层次结构

首先对用户查找某个文件的过程有大致了解，下图为某用户读取文件示意图：

image.png

1.用户要查看文件F -> 对操作系统发出命令（第一层）
2.操作系统得到命令 -> 查找目录 -> 查找文件F的索引信息
3.查看FCB -> 用户是否有访问该文件的权限（第二层）
4.验证通过开始寻址 -> 通过逻辑文件系统与文件信息缓冲区找到逻辑地址（第三层）
5.把逻辑地址转换为物理地址（第四层）
6.如果要删除文件 -> 辅助分配模块；如果用于给设备进行输入/输出 ->设备管理程序模块

2. 目录实现

文件通过目录进行查找，目录实现方式有两种：线性列表和哈希表。

• 线性列表：将文件名和数据库指针存储在线性表上

image.png

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

3. 文件分配

通常将一个程序文件分类为多个子文件，不仅方便内存调用，也方便存放在磁盘块上。那么文件如何摆放在磁盘上？有三种分配方式——连续分配、链接分配和索引分配。

• 连续分配：每个文件在磁盘上载有一组连续的块

image.png

• 链接分配：一个文件拆分成多个子文件，分别放入磁盘的任何磁盘块中，每个盘块都有指向下一个盘块的指针。

image.png

• 索引分配：把每个文件的所有盘块号集中放在一起构成索引块，每个文件的索引块上记录多个条目，第i个条目指向文件的第i个块。

image.png

对以上三种方式进行比较：

image.png

4. 文件存储空间管理

存储文件前，需要知道磁盘中有哪些空闲区域（物理块），如何分配这些分配这些空闲区域才能提高利用空间。常用管理物理块管理方式有：空闲表法、空闲链表法、位示图法和成组链接法。

• 空闲表法：连续分配方式中，常通过空闲表为文件分配一块连续的存储空间；

  
  image.png
• 空闲链表法：将所有空闲盘区拉成一条空闲链，每个指针指向下一个空闲盘区；

• 位示图法：用二进制的一位来表示磁盘中的一个盘块的使用情况，磁盘上所有的盘块都有一个二进制与之对应；

  
  image.png

• 成组链接法：把顺序的n个空间扇区地址保存在第一个空闲扇区内，后面的扇区内则保存另一顺序扇区的地址。

  
  image.png

（三）访问

磁盘如何存放文件？
将磁盘划分为容量相等的磁盘块
1.以圆点为中心，划分成一个个同心圆，一个同心圆之间的面积区域是一个磁道；
2.以圆点为中心，向外划分射线，两条射线与两个同心圆之间的面积区域是一块磁盘块。
文件就存放在这些磁盘块上，当要查找文件时，用磁头臂在这些磁盘块上移动。

clipboard.png

1. 访问时间

查找文件时间=磁头臂寻道时间+延迟时间+传输时间

• 寻道时间
  Ts = m*n+s
  m：磁盘驱动器速度有关常数，约0.2s；
  n：表示磁道；
  s：磁臂启动时间，约为2ms。

• 延迟时间
  Tr = 1/2r
  r：旋转速度

• 传输时间
  Tt = b/rN
  b：每次读/写的字节数b；
  r：磁盘每秒的转数；
  N：磁道上的字节数。

2. 调度算法

通过调度算法控制磁臂移动方向。常用的调度算法有：先来先服务、最短寻找时间优先、扫描算法和循环扫描算法。

• 先来先服务：根据进程请求访问磁盘的先后顺序进行调度。适合有少量进程需要访问且大部分请求访问的是簇聚的文件扇区；

  
  image.png

• 最短寻找时间优先：优先调度的磁道是与当前磁头所在磁道距离最近的磁道，以便使每次的寻找时间最短，性能比先来先服务算法好，但容易产生“饥饿”现象；

image.png

• 扫描算法：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务对象，防止“饥饿”现象。

  
  image.png

• 循环扫描算法：在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动到起始端而不服务任何请求。

  
  image.png

image.png

3. 磁盘的管理

对磁盘的管理包括使用前（初始化），使用时（引导块），使用后（坏块）。

• 初始化：在存储数据之前划分扇区，创建特别的数据结构，存放一些操作系统需要的数据；
• 引导块：引导块放置初始化程序，通过初始化程序启动操作系统；
• 坏块：磁盘是物理硬件，很难避免物理伤害。对于坏块通常使用某种机制使系统不去使用它。