文件管理

文件系统基础[王道操作系统知识备份]

• 文件的概念

  • 文件是以计算机硬盘为载体的存储在计算机上的信息的集合。系统运行时计算机以进程为基本单位进行资源调度，用户进行输入输出时，以文件为基本单位

  • 数据项：用于描述一个对象某种属性的一个值。包括基本数据项和组合数据项

  • 记录：记录一组相关数据项的集合

  • 文件：由创建者所定义的一组相关信息的集合。包括有结构文件和无结构文件

• 文件属性

  • 名称、标识符、类型、位置、大小、保护、时间日期用户标识

• 文件基本操作

  • 创建文件、写文件、读文件、文件重定位（文件寻址，按某条件搜索返回文件位置）、删除文件、截断文件

• 文件打开与关闭

  • 许多文件操作都涉及为给定文件搜索相关目录条目，许多文件系统要求首次使用文件时，文件被显式的打开，即使用系统调用open将文件的属性复制到内存的打开文件表的一个表目中（open返回指向打开文件表表目的指针）。操作系统一般维护一个打开文件表，用户需要一个文件时从打开文件表的索引指定文件，文件不在使用则将此条目从打开文件表删除。

  • 通常，系统打开文件表的某一项文件时，还会打开一个文件计数器，记录多少个进程打开了该文件。当计数为0时，删除该条目

  • 每个打开文件都关联一些信息：

    • 文件指针

    • 文件打开计数

    • 文件磁盘位置

    • 访问权限

• 文件逻辑结构

  • 无结构文件

    • 流式文件，以字节为单位，将数据按顺序记录并积累保存

  • 有结构文件

    • 顺序文件：文件记录一个接一个的顺序排列，记录一般定长，可顺序存储或链表方式存储

    • 索引文件：
      image

    • 索引顺序文件：
      image

    • 散列文件（直接文件）：通过散列函数键值直接决定记录的物理位置

• 目录结构

  • 文件控制块FCB
    类比PCB进程控制块

    • 文件控制块FCB是存放控制文件需要的各种信息的数据结构。FCB的有序集合称为文件目录，FCB就是文件目录项。

    • FCB主要包含基本信息（文件名、物理位置、逻辑结构、物理结构），存取控制信息，实用信息（建立时间、修改时间）

  • 索引节点
    注意I结点存放的是文件描述信息，目录项中存放文件名和指向I结点的指针

    • 在检索文件过程中，只用找到文件名，然后取出对应的物理地址即可。也就是说检索目录时，只需要将文件名加载到内存，其他信息不需要。因此UNIX采用文件名和其他信息分开的方法，文件描述信息单独形成一个索引节点，称为I结点。文件目录中的目录项是包含文件名和指向I结点的指针。

    • 一个FCB大小64B，盘块大小1KB，一个盘块可存放16个FCB（FCB必须连续存放）。在UNIX中，一个目录项只有16B，其中14B是文件名，2B是i结点指针。1KB可存放64个文件目录项

    • UNIX系统的索引结点包含：文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件链接计数、文件存取时间

    • 文件被打开时，磁盘索引结点复制到内存中，在内存中索引结点加了以下内容：索引结点编号（用于标识索引结点）、状态、访问计数、逻辑设备号、链接指针

  • 目录结构

    • 单级、
      image

    • 两级、
      image

    • 多级、
      image

    • 无环图
      image
      • 便于实现文件共享

• 文件共享

  • 基于索引节点的共享（硬链接）
    image
    • 基于索引结点的共享，在索引结点中有一个链接计数count，用于记录链接到本索引结点的用户目录项数目。当count为0时才删除该文件

  • 基于符号链实现的共享（软链接）
    符号链是一个文件，这个文件内容就是被链接文件的路径

    • 为使用户B可共享A的文件F，创建一个LINK类文件，也取名为F，并将F写入B的文件目录中。这个新文件只包含被链接文件F的路径名，这种方式被称为符号链接。

    • 符号链有一个优点是网络共享时，只需要知道该文件主机网络地址和主机内的绝对地址。

• 文件保护

  • 可加控制的访问类型：读、写、执行、添加、删除、列表清单，（重命名、复制、编辑）

  • 访问控制

    • 基于身份的访问控制

      • 为每个文件和目录增加一个访问控制表，规定每个用户名及其可被允许的访问类型

      • 精简的访问列表包括拥有者（创建文件），组（共享文件且具有类似访问的用户），其他（系统内其他用户）

    • 口令

      • 用户在创建文件时提供一个口令，在创建FCB时附上相应口令。用户请求时必须提供口令

      • 时间空间开销少，但是口令直接存储在系统内部不安全

    • 密码

      • 对文件进行加密，被访问时需要使用密码

文件系统实现

• 文件系统层次结构

  • 用户调用接口

    • 文件系统为用户提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件、建立或删除目录

    • 此层由若干个程序模块组成，每个模块对应一个系统调用，用户发出系统调用，控制即转入相应模块

  • 文件目录系统

    • 主要功能是管理文件目录。（管理活跃文件目录表、读写状态信息表、管理进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块）

  • 存取控制验证模块

    • 实现文件保护，把用户访问要求与FCB中指示的访问控制权限进行比较

  • 逻辑文件系统与文件信息缓冲区

    • 根据文件的逻辑结构将用户读写的逻辑记录转换称文件逻辑结构内对应的块号

  • 物理文件系统

    • 把逻辑记录转换为实际物理地址

  • 辅助分配模块

    • 管理辅存空间

  • 设备管理程序模块

    • 分配设备、分配设备读写用缓冲区，磁盘调度、启动设备、处理设备中断、设法设备读写缓冲区、释放设备

• 目录实现
  目录实现是为了查找文件，线性表对那个现象查找，哈希表对应散列查找

  • 线性列表

    • 最简单的目录实现方式是使用存储文件名和数据块指针的线性表。使用链表可减少删除文件的时间，实现简单但是比较费时

  • 哈希表

    • 根据文件名得到一个值，并返回一个指向线性列表中元素的指针。优点查找迅速，插入删除页比较简单。

• 文件实现
  文件实现其实是研究文件的物理结构，即文件数据在物理存储设备上如何分布。包含两方面，一是文件的分配方式，即对磁盘非空闲块管理，二是文件存储空间管理，即对磁盘空闲块管理

  • 文件分配方式
    image

    指如何为文件分配磁盘块

    • 连续分配

      • 每个文件占用磁盘上一组连续的块，这种方式作业访问磁盘需要寻道数和寻道时间最小

      • 支持顺序访问和直接访问，优点实现简单，存取速度快，缺点文件长度无法动态增加。反复增删文件后会出现外部碎片

    • 链接分配

      • 采取离散分配方式，消除了外部碎片，显著提高磁盘利用率，可动态增加文件大小

      • 链接分配又可分为隐式链接和显式链接

        • 隐式链接，每个文件对应一个磁盘块链表，每个磁盘块存有指向下一个块的指针，目录项存储第一块指针和最后一块指针。创建文件时，目录增加一个目录项，指针初始化为NULL，大小为0。隐式链接缺点无法直接访问盘块，且盘块指针也会消耗存储空间。

        • 显式链接，指的是将指向文件物理块的指针，从每个块末尾提取出来存放到一个链接表中，这个表称为文件分配表（FAT表），每个表项存放对应块的下一块链接指针。文件分配表不仅记录了文件各块之间的先后顺序，也可标记出空闲的磁盘块。（空闲磁盘块在文件存取表中对应下一块指针为-2）

    • 索引分配

      • 索引分配将文件的所有盘块号集中放到一起构成索引表（块）。每个文件都有其索引块，索引块是一个数组，数目的条目是磁盘块地址数组。索引块第i个条目指向文件的第i个块。目录项条目存储索引块的地址。

      • 索引块支持直接访问，且没有外部碎片，缺点是因为索引块，增加了系统存储空间开销

      • 索引分配为了支持大文件，可使用链接索引块方式、多层索引、混合索引的方式

  • 文件存储空间管理

    • 文件存储空间划分与初始化

      • 一个文件存储于文件卷中，这个卷可以是物理盘的一部分、也可以是整个物理盘。

      • 文件卷中，文件区和目录区是分开的。

      • 逻辑卷在提供服务前需要划分好目录区和文件区，建立空闲分区管理表格及存放逻辑卷信息的超级块

    • 文件存储器空间管理
      文件存储设备管理实际是对空闲块的组织和管理

      • 空闲表

        • 空闲表法属于连续分配方法，与内存的动态分区方法类似。

        • 系统为外存所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项，包括表项序号、空闲区第一个盘块号、盘块数。然后将空闲区按照起始盘块号递增排列。

        • 空闲盘区分配，与内存动态分配类似，使用首次适应算法、循环首次适应算法等

      • 空闲链表

        • 空闲链表包括空闲盘块链和空闲盘区链

        • 空闲盘块链是将磁盘空闲的空闲空间以盘块为单位拉成一条链。用户请求分配空间时，从链首开始摘下适当数目盘块。

        • 空闲盘区链是将空闲盘区拉成一条链，每个盘区上应有指明本盘区大小的信息。分配盘曲方法和空闲表类似。（首次适应、循环首次适应）

      • 位示图

        • 位示图利用二进制的一个位标识磁盘对应块的使用情况。值为0时表示空闲，值为1时表示已分配。

      • 成组链接法
        空闲表和空闲链表不适用与大型文件系统，UNIX采用成组链接法

        • 把顺序的n个空闲扇区地址保存到第一个空闲扇区内，其后一个空闲扇区保存另一组顺序空闲扇区地址，如此继续，直到所有空闲扇区均予以链接。

        • 系统只需要保存一个指向第一个空闲扇区的指针。

        • 表示文件存储器空闲空间的位向量表或第一个成组链块，以及卷中的目录区、文件区划分信息都需要放到辅存储器中，一般放在卷头位置，在UNIX系统中称为超级块。在对卷中文件操作时，超级块需要预先读入系统空闲的主存。

磁盘组织与管理

• 磁盘结构
  image

  • 磁盘是由表面涂有磁性物质的金属或塑料构成的圆形盘片，通过一个成为磁头的导体线圈读取数据

  • 存储数据的同心圆称为磁道，磁道与磁头一样宽，一个磁道被分为几百个扇区，每个扇区固定大小。相邻磁道之间通过一定间隙分隔开。

  • 磁盘存储能力受限于最内道的最大记录密度

  • 磁盘可分为固定头自盘，活动头磁盘，固定盘磁盘，可换盘磁盘

• 磁盘调度算法

  • 磁盘时间

    • 寻找时间

      • 活动头磁盘读取信息前，将磁头移动到指定位置，这个时间包括跨越n个磁道的时间和启动磁臂的时间。T_n = m \times n + s

    • 延迟时间

      • 磁头定位到某一磁道的扇区所需时间，对于转速r的磁盘T_r = \frac {1} {2r} ，

    • 传输时间

      • 从磁盘读出或向磁盘写入数据的时间，取决于每次读取的字节数和磁盘转速。T_t = \frac b {rN}

    • 总平均时间 T_a = T_s + \frac 1 {2r} + \frac b {rN}

  • 磁盘调度算法
    image

    • 先来先服务（FCFS）算法
      image
      • 若有大量进程竞争使用磁盘，算法在性能上接近随机调度（较差）

    • 最短寻找时间优先（SSTF）算法
      image
      • 性能优于FCFS，但是会产生饥饿现象

    • 扫描算法（SCAN，电梯调度算法）

      • 在当前移动方向上选择与当前磁头所在磁道最近的作为下一次服务的对象

      • SCAN对最近扫描过的区域不公平，在局部性方面不如FCFS和SSTF。

    • 循环扫描算法（C-SCAN）

      • 在扫描算法基础上规定磁头单向移动，回返时直接快速移动至起始端，从而避免，SCAN算法总是偏向于处理接近最里或最外的磁道的访问请求。

      • 实际上采用SCAN（C-SCAN），磁头总是严格的遵循从盘面一端到另一端，显然这是可以改进的。如LOOC调度，磁头只需要移动到最远端的一个请求即可返回

  • 磁盘管理

    • 磁盘初始化

      • 低级初始化：磁盘能存储数据前，划分为扇区以便磁盘控制器可以读和写。低级初始化为磁盘每个扇区采用特别的数据结构，每个扇区由头、数据区域（512B），尾部组成

      • 操作系统将自身数据结构记录在磁盘：第一步将磁盘分为一个或多个柱面组成的分区（C盘、D盘），第二部进行逻辑格式化，也就是初始化文件系统

    • 引导块

      • 计算机启动时需要运行一个初始化程序（自举程序），初始化CPU、寄存器等

      • 自举程序保存在ROM中，为避免改变自举代码需要改变ROM硬件的问题，因此ROM中只保留很小的自举装入程序，完整的功能（自举程序）保存在磁盘启动块中。启动块位于磁盘固定位置，拥有启动分区的磁盘称为启动磁盘或系统磁盘

    • 坏块

      • 简单磁盘处理坏块，坏扇区会在FAT表（文件分配表）中标明，程序不会使用

      • 复杂的磁盘，其控制器维护一个磁盘坏块表。控制器可用备用块来逻辑的替换坏块，称为扇区备用