新年到来了！！新年的第一篇blog
引言：操作系统的文件系统与文件管理方式

文件管理

文件与文件系统

有关基本概念

数据的组成：

• 数据线
  • 基本数据项（最小的逻辑数据单位）
  • 组合数据项
• 记录：一组相关数据项的集合
• 文件：记录在外存上的具有文件名的一组相关信息的集合
  • 有结构文件：若干个相关记录组成
  • 无结构文件：被看成一个字符流（绝大部分都是无结构文件）

文件、记录、数据项的层次关系：

文件属性：文件名、文件类型、文件长度、文件物理位置、建立日期

文件名：不同系统有长度限制、特殊字符不能用于文件名

扩展名：后缀名，window系统中的概念，在类Unix系统中仅仅只有表意的作用

文件类型：

• 按用途分类
  • 系统文件
  • 用户文件
  • 库文件：.lib静态库文件.dll动态库文件
• 按数据形式分类
  • 源文件
  • 目标文件.obj
  • 可执行文件.exe
• 按存取控制属性分类
  • 只执行文件
  • 只读文件
  • 读写文件
• 按组织形式和处理方式分类（Unix系统）
  • 普通文件
  • 目录文件
  • 特殊文件：各类IO设备
• 按使用情况分类：
  • 临时文件：工作完毕会自动删除
  • 永久文件
  • 档案文件：系统或一些实用工具软件包在工作过程中记录在案的文挡资料文件

文件的特点：

• 具有保存性
• 按名存取
• 一组信息的集合

文件系统的主要功能

• 实现按文件名存取文件信息
• 为用户提供统一的和友好的接口
• 实施对文件和文件目录的管理
• 文件存储器空间的分配和回收
• 提供有关文件的共享和保护

可以从用户和系统的角度来看：

• 从用户的角度：
  • 实现了信息的按名存取
• 从系统的角度
  • 文件存储器空间的分配回收
  • 文件的保护和检索

文件系统的结构层次

可分为三个层次：从上到下

• 文件系统接口
  • 命令接口：键盘中断敲入命令
  • 程序接口：系统调用来使用
• 对对象操纵和管理的软件集合（核心）
  • 文件存储空间的管理
  • 文件目录的管理
  • 文件的逻辑地址与物理地址转换机制
  • 对文件的读和写的管理
  • 对文件的共享和保护
• 对象及其属性
  • 文件
  • 目录
  • 磁盘存储空间

文件系统 = 文件管理程序 + 它所管理的全部文件

文件系统特点

• 使用方便
• 安全可靠
• 便于共享
• 统一管理

文件操作

文件系统以系统调用的方式，为用户提供服务

基本的文件操作

创建文件

1. 系统为新文件分配必要的外存空间
2. 在文件系统的目录中为该文件建立一个目录项，目录项中记录新文件的文件名及其在外存的地址等属性

删除文件

1. 系统从文件目录中找到要删除文件的目录项，使之成为空闲目录项
2. 回收该文件所占用的存储空间。

读/写文件

读文件：把文件中的数据从外存读入内存的用户区

写文件：当用户要求对文件添加或修改信息时，可用该命令将信息写入文件

应在系统调用中给出文件名和存放读出内容的内存地址

打开文件

目的：为了避免用户在每次访问文件时从外存中查找文件目录

所谓“打开”：系统将文件的属性（目录信息）从外存复制到内存打开文件表中，并返回该表目的编号给用户，建立了用户与文件间的联系。以后若再访问此文件，则利用编号直接在内存中检索，从而节省大量的检索开销，提高了文件的操作速度

关闭文件

将文件的属性从内存打开表中删除，从而切断用户与文件间的联系

其他文件操作

• 对于文件属性的操作
  • 改变文件名
  • 改变文件的拥有者
  • 改变文件的访问权
  • 查询文件的状态
• 对目录的操作
  • 创建、删除
  • 改变当前工作目录
  • 实现文件共享

文件的使用

1. 建立一个新文件
   • 建立文件
   • 写文件
   • 关闭文件
2. 读一个已存在的文件
   • 打开文件
   • 读文件
   • 关闭文件

文件的逻辑结构

在系统中文件有两种形式的结构：

• 物理结构
  • 文件的存储结构，与存储介质有关
• 逻辑结构
  • 从用户的观点观察到的文件组织形式

文件的逻辑结构和物理结构都将影响文件的检索速度

文件逻辑结构的类型

• 按文件是否有结构分类：
  • 有结构的记录式文件
    • 定长记录：文件中所有记录长度相同
    • 变长记录
    • 按文件的组织方式分类，可以将有结构文件分为
      • 顺序文件
      • 索引文件
      • 索引顺序文件
  • 无结构的流式文件
    • 由字符流构成
    • 长度：字节为单位
    • 访问：读写指针

顺序文件

排序方式：

• 串结构：记录顺序与关键字无关，按存入时间的先后顺序排列
• 顺序结构：记录顺序按关键字排序

优点：

• 顺序存取速度较快（批量存取）
• 对定长记录，还可方便实现直接存取
• 只有顺序文件才能存储在磁带上，并能有效地工作

缺点：

• 如果用户要求查找或修改单个记录，系统要逐个地查找诸记录, 效率很差，尤其是当文件较大时，情况更为严重
• 增加或删除一个记录较困难
• 对变长记录，直接存取低效

索引文件

为解决变长记录文件的直接存取低效问题

为变长记录文件建立一张索引表

优点：

• 通过索引表可方便地实现直接存取，具有较快的检索速度。
• 易于进行文件的增删

缺点：

• 索引表的使用增加了存储费用
• 索引表的查找策略对文件系统的效率影响很大

索引顺序文件

为解决变长记录文件的直接存取低效且存储费用增加的问题

将所有记录分为若干个组(例如，50个记录为一个组)；

为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针

优点

• 通过索引表可方便地实现直接存取，具有较快的检索速度
• 易于进行文件的增删

缺点

• 索引表的查找策略对文件系统的效率影响很大.

文件的存取方法

通常有三种：

• 顺序存取
• 直接存取（随机存取）
• 按键存取

顺序存取

对于定长记录文件：

设置读/写指针rptr与wptr指向下一次读/写的地址

读/写完指针做对应修改：rptr = rptr + L

对于不定长记录文件：

每次将读写指针加上Li，Li是刚读或刚写完的记录的长度：

rptr = rptr+Li

直接存取

允许按任意顺序存取文件中的任何一个记录

对于定长记录文件：

​ rptr = addr + i*L

对于变长记录文件：

顺序文件不能使用；

索引文件可以使用（由于索引表本身是定长的）；

按键存取

实质是直接存取法，根据记录中的关键字（键）经过某种方法计算转换成相应的物理地址

注意：

顺序文件中的记录寻址有：

• 显示寻址：
  • 通过文件中记录的位置
    • 对于定长记录文件就可以通过计算
    • 对于可变记录文件必须从头遍历
  • 通过关键字
• 隐式寻址：就是顺序寻址

文件的物理结构

物理结构指存储结构：

• 连续分配方式：将是顺序式的文件结构；
• 链接分配方式将形成链接式文件结构；
• 索引分配方式则将形成索引式文件结构

顺序结构

也叫连续结构，最简单的物理文件结构，它将一个文件的信息存放在若干连续的物理块中。（类似内存的连续分配）

特点：

• 顺序存取速度快，所需的磁盘寻道次数和寻道时间最少
• 浪费空间：动态存储分配问题，产生外零头
• 可以通过紧凑技术合并空闲的区域

优点：

• 顺序访问容易
• 顺序访问速度快

缺点：

• 要求分配连续的存储空间
• 必须实现知道文件长度
• 不能灵活的删除和插入记录
• 不利于动态增长的文件，存在外零头

链接结构

又称串联结构，将一个逻辑上连续的文件信息存放在外存的不连续(或连续)物理块中

隐式链接：每个盘块中有指向下一个块的指针

显式链接：有文件分配表FAT

隐式链接：

显式链接：

优点：

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

缺点：

• 存取速度慢，不适于随机存取，对顺序存取特别有效。（找到一个盘块才能知道下一个盘块位置）
• 可靠性问题，如指针出错（隐式链接）
• 更多的寻道次数和寻道时间。（分配的每个盘块可能不连续，可能分布于不同的磁道中）
• 链接指针占用一定的空间。（隐式链接）

链接结构的一个变形: 文件分配表FAT－显式链接

索引结构

文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构–索引表，并将这些块的块号存放在一个索引表中。

特点：

• 索引快地址由FCB指出
• 支持随机存取
• 不会产生外零头
• 适用于大文件

分类：

• 单级索引分配
• 多级索引分配
• 混合索引分配

单级索引分配

优点：

• 支持直接访问。读i个块时，从索引块中找到盘块号
• 不会产生外部碎片
• 文件较大时，优于链接结构

缺点：

• 可能花费较多的外存空间。每建立一个文件，必须分配一个索引块（索引块本身也是一个盘块） 。
• 一般系统中小型文件居多，索引块利用率低。
• 对于大文件来说，索引块也会占用不少的盘块

多级索引分配

例如：设每个盘块的大小为4 KB，每个盘块号占4个字节，则在一个索引块中可存放1K个盘块号。

解：

采用单级索引时所允许的最大文件长度为4 MB；

而采用两级索引时，最多可包含的存放文件的盘块的盘块号总数N = 1K × 1K = 1 M个盘块号，则允许的最大文件长度可达4 GB。

混合索引分配

既有一级、也有二级、三级，在类Unix系统中使用

优点：

• 保持了链接结构的优点,又解决了其缺点：
  • 既能顺序存取,又能随机存取
  • 满足了文件动态增长、插入删除的要求
  • 也能充分利用外存空间。

缺点：

• 较多的寻道次数和寻道时间
• 索引表本身带来了系统开销，如：内外存空间，存取时间。

文件存储空间管理

分配盘块的方式

• 空闲表法
• 空闲链表法
• 位视图
• Unix成组链接

空闲表法

系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息

序号	第一空白块号	空白块个数	空闲物理块号
1	2	4	（2，3，4，5）
2	7	3	（7，8，9）
3	15	5	（15，16，17，18，19)
4	—	—	—

• 仅当有少量的空白区时才有较好的效果。（多个空白区说明这些空白区是不连续的）
• 如果存取空间中有着大量的小的空白区，则空闲表变得很大，效率大为降低。
• 这种分配技术适用于建立连续文件

空闲链表法

将所有空闲盘区拉成一条空闲链

分为两种：

• 空闲盘块链：以盘块为单位拉成一条链
• 空闲盘区链：以盘区(1个盘区可包含若干连续的盘块)拉成一条链
  • 每个盘区上除有指示下一个盘区的指针外，还应指明本盘区大小
  • 分配盘区通常采用首次适应算法
  • 回收盘区时，也要将回收区与相邻接的空闲盘区相合并

位视图法

系统建立一张位示图，以反映整个存储空间的分配情况

用二进制位反映磁盘空间的分配,

每个物理块对应一位, “1”表示对应的物理块已分配，“0”表示其对应的块未分配

分配：

1. 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
2. 将二进制位转换成相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按b = n(i-1) + j （n表示每行的位数）
3. 修改为1

回收：

1. 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为

   i = (b - 1) DIV n + 1
   j = (b - 1) MOD n + 1

2. 修改为0

优点：

• 易找到空闲盘块
• 占用空间少

成组链接法

特点：

• 栈结构
• s.free表示该盘块号内空闲的盘块
• 每个盘块号栈的第一个位置链接到下一个盘块号栈，为0代表没有下一个盘块

注意：

例题：某个系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态如下图所示：

1. 在为某个文件分配3个盘块后，系统要删除另一个文件，并回收它所占的5个盘块，它们的盘块号依次为700、711、703、788、701，请画出回收后的盘块链接情况。

文件目录

文件目录

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

目录项：就是FCB

目录文件：为了实现对文件目录的管理，通常对文件目录以文件形式保存在外存

当文件多时，文件目录占用磁盘上大量的盘块 ，设文件目录所占用的盘块数为N，按顺序法查找一个目录项平均需调入盘块**(N+1)／2**次

一个FCB为64B，盘块大小为1KB，则每个盘块中只能存放16个FCB；

若一个文件目录中共有640个FCB，需占用40个盘块，故平均查找一个文件需启动磁盘20次

解决：把文件名与文件描述信息分开存放

索引结点：文件除文件名外的描述信息单独形成一个称为索引结点的数据结构，简称为i结点

文件名	索引结点编号
文件名1
文件名2

文件名14B，i 结点指针2B。 1 KB盘块中可做64个目录项，平均启动磁盘次数缩小，节省了系统开销

目录管理

• 实现“按名存取”
• 提高对目录的检索速度
• 文件共享
• 允许文件重名（允许不同用户对不同文件用相同文件名。）

文件目录结构

• 单级目录结构：在整个系统中只建立一张目录表
  • 优点：简单，易实现按名存取
  • 缺点：
    • 不允许重名
    • 查找速度慢
    • 不利于文件共享（不利于不同用户用不同文件名来访问同一个文件）
• 两级目录结构
  • 每个用户建一个用户文件目录UFD
  • 系统为所有用户建立一个主文件目录MFD
  • 优点：
    • 提高了检索速度
    • 不同用户目录可重名
    • 不同用户用不同文件名来访问同一个文件
  • 缺点：
    • 限制了个用户文件的共享
    • 不太适合大量用户和大量文件的大系统
• 多级文件目录
  • 树型目录结构
  • 根目录根节点、数据文件是叶子结点
  • 删除方式
    • 不删除非空目录：得调用递归才能删除多目录结构
    • 可删除非空目录（危险）
  • 优点
    • 层次结构清晰
    • 易于管理保护
    • 有利于文件分类
    • 解决重名问题
    • 提高检索速度
    • 能进行权限控制
  • 缺点：
    • 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度