文章目录

文件及其逻辑结构

文件概念：由创建者所定义、具有文件名的一组相关元素的集合，可分为结构文件和无结构文件两种。

文件逻辑结构概念：文件的逻辑结构是从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。

顺序文件

  • 顺序文件由数据依次排列组成。
  • 顺序文件可分为串结构文件和有序结构文件。、
    • 串结构文件按记录存入文件的时间先后排列。
    • 有序结构按关键字值大小排列。
  • 顺序文件又分为定长记录文件和变长记录文件。

索引文件

若顺序文件是变长记录文件，可按记录号或关键字为每条记录建立一个索引文件，存储记录在顺序文件中的位置信息。

索引文件是定长的文件。

索引顺序文件

  • 索引文件太长会要求更多的I/O次数，直接影响了文件的读/写效率。
  • 索引顺序文件先对顺序文件按记录号或关键字排序分组，然后对组的第一个记录索引。

直接文件和哈希文件

  • 直接文件是一种特殊的哈希文件,记录关键字值决定了记录在顺序文件中的位置。

  • 哈希文件则由关键字值通过哈希函数计算获得记录在顺序文件中的位置。

目录的要求

  1. 实现“按名存取”。
  2. 提高对目录的检索速度。
  3. 文件共享。
  4. 允许文件重名。

文件的物理结构（***）

概念：文件的物理结构指文件的外存分配组织管理方式

文件占用的外存空间以块或簇等逻辑单位计量

连续分配

文件数据连续存储可以提高存取速度，但限制了文件动态增长。

链接分配

隐式链接，链接指针包含在给文件分配的块中，目录中仅包含文件的起始块和结束块(或长度)。

  • 链接指针分散在多个块中，不利于安全措施的实现

显示链接：将所有的链接信息提取放到文件分配表中

索引分配

  • 在链接分配中，文件块链接指针离散存储,造成文件占用块号解析效率不高。

  • 索引分配方式就是将块号集中存放。

单级索引（一级索引）

用一个块来记录文件占用的所有块号,我们称之为索引块

二级索引

因为一个索引块的大小有限，但是多级索引需要检索多次，会影响性能

混合索引(直接地址、-级索引、两级索引、三级索引方式)

空闲空间管理

空闲表法

  • 若干连续的空闲块组合成一个空闲区。
  • 空闲表法将所有的空闲区记录在一张表里， 包括项号、起始空闲块号、空闲块数等。

空闲链表法

空闲链表法是以空闲块或空闲区为结点构成一个链表结构。

位视图法（***）

用一位二进制表示，1代表已分配，0代表空闲。

  • 块号从0开始，BitsOfLine 是一行有多少位，如char类型为8位
  • block = line X BitsOfLine + column
  • line = block/BitsOfLine
  • column = block%BitsOfLine

成组链表法

用树的结构表示

文件系统软件模型

对象及其属性

  • 文件系统对象
  • 超级块对象
  • 文件
  • 目录
  • 索引结点
  • 数据块

对对象操纵和管理的软件集合

  • 对文件的读/写
  • 对目录文件的读/写
  • 对磁盘空闲空间的管理
  • 将文件的逻辑地址转换为物理地址
  • 对文件的保护与共享;

文件系统接口

  • 基于文件名(路径)、文件逻辑地址(相对于文件起始地址的偏移)给用户提供各种操作。
  • 常用的文件操作有，创建文件、删除文件、读文件、写文件、设置文件读1写位置、打开文件、关闭文件等。

文件共享

  • 基于索引结点的共享方式
  • 基于符号链的共享方式

课本习题

  1. 11 在 UNIX 中，如果一个盘块的大小为 1KB ，每个盘块号占 4 个字节，即每块可放 256个地址。请转换下列文件的字节偏移量为物理地址。

    ⑴ 9999 ； ⑵ 18000 ；⑶ 420000

    答：首先将逻辑文件的字节偏移量转换为逻辑块号和块内偏移量 ,就是将 [字节偏移量 ]/[ 盘块大小 ]，商为逻辑块号，余数是块内偏移量。在 FCB 中，第 0-9 个地址为直接地址，第 10 个为一次间接地址，第 11 个地址为二次间接地址，第 12 个地址为三次间接地址。

    再将文件的逻辑块号转换为物理块号。使用多重索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到对应的物理块号。

    • 9999/1024=9余 783 ，则逻辑块号为9 ，直接索引第9个地址得到物理块号，块内偏移地址为 783 。

    • 18000/1024=17 余 592 ，则逻辑块号为10<17<10+256，通过一次间接索引在第10个地址可得到物理块号，块内偏移地址为592 。

    • 420000/1024=410 余160 ，则逻辑块号为 10+256<410 ，通过二次间接索引在第 11 个地址可得到一次间址，再由此得到二次间址，再找到物理块号，其块内偏移地址160 。

  2. 某操作系统磁盘文件空间共 500 块，若用字长为 32 位的位示图管理磁盘空间，试问：

    （1）位示图需要多少字？

    （2）第 i 字第 j 位对应的块号是多少？

    （3）给出申请 /归还一块的工作流程。

    答：

    （1）位示图需要的字数计算： INT （ 500/32 ） =16个字。

    （2）块号 b=(i-1)*32+j

    （3 ）申请的过程：顺序扫描位示图、找到空闲块并分配、修改位示图map[i,j]=1 。归还的过程：找到回收盘块在位示图中的行和列，修改位示图map[i,j]=0 。

题目练习