操作系统（五）| 文件系统上结构存取方式文件目录检索

文章目录

1 文件系统概述
2 文件的结构与存取方式
- 2.1 磁盘
- 2.2 文件的物理结构
- - 2.2.1 连续结构
  - 2.2.2 链式结构
  - 2.2.3 索引结构
- 2.3 文件的存取方式
3 文件目录
- 3.1 基本概念
- 3.2 目录结构
- - 单级目录结构
  - 多级目录结构
- 3.3 文件目录检索
- - 3.3.1 目录检索
  - 文件寻址
- 3.4 文件目录的实现

1 文件系统概述

为什么引入文件系统

长期保存（大量的）数据

方便用户使用

文件是有名字的记录在外存中的一组有逻辑意义的数据项序列

什么是文件系统

文件系统是OS中用来管理文件的那一部分软件

文件系统功能

统一管理文件的存储空间，实施存储空间的分配与回收
实现文件信息的共享，提供文件的保护和保密措施
实现文件的按名访问
访问的透明性：用户不关心文件的物理位置和存储结构
向用户提供一个方便使用的接口，提供对文件系统操作的命令
提供与I/O的统一接口

文件分类：

Unix系统将文件分为3类:
普通文件(regular)：ASCII或二进制文件
目录文件(directory)
特殊文件：设备文件，管道，套接字（socket），符号链接等

2 文件的结构与存取方式

文件是存在磁盘上的

2.1 磁盘

磁盘有扇片磁道扇区

扇区——磁盘最小可寻址单元

簇——存储块，固定数量的扇区

平均存取时间

T=平均寻道时间+平均旋转等待时间+数据传输时间（有时候忽略不计）

其中

平均寻道时间——磁头寻找到指定磁道所需要的平均时间（大约5ms）

平均旋转等待时间——指定扇区旋转到磁头下方所需要的平均时间（约4-6ms）

磁盘响应时间=平均存取时间+排队时间+控制器时间

注意想明白这里的0.5的来源

2.2 文件的物理结构

2.2.1 连续结构

文件的数据存放在若干连续的物理块中
在这里插入图片描述

优点：

简单，只要记住首块的地址和文件长度即可
支持顺序存取和随机存取
顺序存取速度快
所需的磁盘寻道时间最少

缺点：

不利于文件的动态增长
若预留空间：浪费，而且预先不知道文件的最大长度
否则需要重新分配和移动
不利于文件内容的插入和删除
存在外部碎片问题

2.2.2 链式结构

一个文件的数据存放在若干不连续的物理块中，各块之间通过指针连接，
每个物理块指向下一个物理块

在这里插入图片描述

优点

提高了磁盘空间利用率
不存在外部碎片问题
有利于文件的插入和删除
有利于文件的动态扩充

缺点：
随机存取相当缓慢
需要更多的寻道时间
链接指针占用一定的空间

改进变形

FAT表

文件分配表FAT的一种实现：
磁盘的每个分区包含一个FAT，分区中的每个盘块在其中占有1项（以块号为索引），指出文件中下一块的块号。
在目录项中包含文件首块的块号。

在这里插入图片描述

2.2.3 索引结构

一个文件的数据存放在若干不连续的物理块中，系统为每个文件建立一个专用数据结构–索引表。
索引表存放逻辑块号与物理块号的对应关系
一个索引表就是磁盘块地址（块号）数组，其中第i个条目存放的是逻辑块号i对应的物理块号
文件目录的目录项中指出索引表的物理地址

在这里插入图片描述

优点：保持了链接结构的优点，又避免了其缺点
既能顺序存取，又能随机存取
能满足文件动态增长、插入、删除的要求
能充分利用外存空间
缺点：
索引表本身带来了系统开销

UNIX文件系统采用的是多级混合索引结构。
每个文件的索引表为13个索引项
最前面10项直接登记存放文件数据的物理块号（直接寻址）
如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址
UNIX中采用了三级索引结构后，文件最大可达16M个物理块

索引表的组织方式

如果文件很大，索引表较大，超过了一个物理块，就必须考虑索引表的组织方式，即怎么去存储索引表

索引表的组织方式:
（1）连续方式
索引表占用多个连续的盘块
（2）链接方式
索引表按照链式结构组织，占用多个不连续的盘块
（3）多级索引（多重索引）
例如，二级索引：将一个大文件的所有索引表（二级索引）的地址放在另一个索引表（一级索引）中
此外，还有三级索引等。

题目

设每个盘块4kB，每个盘块号4B，则采用3次间址可表示的文件最大长度为 [4T] B。

2.3 文件的存取方式

主要有顺序存取和随机存取两种。
1 顺序存取
对文件中的数据按逻辑顺序进行读/写的存取方式
2 随机存取
对文件中的数据按任意顺序进行读/写的存取方式
3 按键（key）存取：如DBMS

还与介质有关

3 文件目录

3.1 基本概念

几个基本的概念

1 文件控制块

文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有相关信息（文件属性）

基本信息：文件的名字、地址（起始物理块号）、长度、结构（逻辑结构、物理结构）、类型
存取控制信息：文件属主（owner）、存取权限或口令
使用信息：共享计数，文件的建立、修改日期等

2 文件目录

把所有的FCB组织在一起，就构成了文件目录
即文件控制块的有序集合

3 目录项
构成文件目录的项目（目录项就是FCB）

4 目录文件

为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，
这个文件就叫目录文件
目录主要是为了系统快速实现“按名访问”而引入的，
查目录是文件系统最频繁的操作，因此目录的合理组织很重要

3.2 目录结构

单级目录结构

为所有文件建立一个目录文件（组成一线性表）
优点：简单，易实现

缺点：
限制了用户对文件的命名（容易出现“命名冲突”）
顺序检索文件时，平均检索时间长
不利于对文件的共享

多级目录结构

对二级目录简单扩充可得三级或三级以上的多级目录结构，
即允许每一级目录中的FCB要么指向文件，要么指向下一级子目录。
这是当今主流OS普遍采用的目录结构
优点：
层次结构清晰，便于管理和保护；有利于文件分类；
能较好地避免重名问题；提高了文件检索速度；有利于访问权限的控制

3.3 文件目录检索

访问文件时，必须首先确定读写文件的地址，需要下列2步：
（1）目录检索：根据文件名，查目录，确定文件的起始地址。
（2）文件寻址：确定所要访问文件内容的起始位置（地址）。

3.3.1 目录检索

文件的“按名存取”是通过查目录实现的，系统按照文件的路径名检索
基本的目录检索技术主要有：
线性检索法
Hash方法
为了加快目录检索，许多系统引入当前目录（工作目录）、相对路径名等。

文件寻址

根据目录项（FCB）中记录的文件物理地址等信息，
求出文件的任意记录或字节在存取介质上的地址
文件寻址与文件的物理结构和逻辑结构以及设备的物理特性有关
文件的内容是以块为单位存储的。
但存取文件时，对于记录式文件，是以逻辑记录为单位提出存取要求的，因此，
存储介质上的物理块长度与逻辑记录的长度是否匹配直接影响到对文件的寻址