文件分配方式

（对非空闲磁盘块的管理）

• 所谓的物理结构就是指在操作系统看来，文件的数据是如何存放在外存的

• 在很多的 操作系统中，磁盘块的大小与内存块，页面的大小相同

• 连续分配

  • 要求文件在磁盘上占有一组连续的块

  • 目录项新增内容

    • 起始块号和长度

  • 物理块号=起始块号+逻辑块号

  • 优点

    • 支持顺序访问和随机访问，随机访问的速度比索引分配的随机速度更快
    • 顺序读写时速度最快

  • 缺点

    • 文件拓展很不方便（要移动到有连续块的位置）
    • 存储空间利用率很低，产生难以利用的磁盘碎片（紧凑）

• 链接分配

  • 隐式链接

    • 

      • 每个磁盘块记录指向下一个磁盘块的指针（透明）

      • 目录项内容

        • 文件名，起始块号和终止块号

      • 优点

        • 方便拓展文件，不会产生碎片

      • 缺点

        • 只支持顺序访问，不支持随机访问
        • 若要启动第k个磁盘，必须先启动前k-1个磁盘，带来了很多次磁盘启动

  • 显式链接

    • 

      • 文件分配表（FAT）

        • 把链接各个物理块的指针显式地放在表中
        • 物理块号（隐含）+下一块
        • 下一块为-1，代表无下一块
        • 一个磁盘一个FAT，开机后读入，常驻内存
        • -2表示这个磁盘块空闲，所以他还兼职做着管理空闲磁盘块的功能

      • 目录项内容

        • 文件名，起始块号

      • 优点

        • 支持顺序访问和随机访问
        • 不需要访问磁盘，速度快（FAT常驻内存）
        • 便于文件拓展，不会有碎片，外存利用率高

      • 缺点

        • FAT占用一定的内存空间

• 索引分配

  • 每个文件有一张索引表，
    索引表中记录了各个逻辑块对应的物理块
    有点类似于内存管理中的页表

    • 索引表

      • 逻辑块号（顺序隐含）+物理块号

        • 逻辑块号占多少位？

          • 0字节，隐含表示

        • 物理块号占多少位？

          • 取决于磁盘的总的物理块数

    • 

    • 目录项内容

      • 文件名+新增索引块块号

        • 由索引块号找到索引表内容，再由索引表访问数据块

    • 优点

      • 支持随机访问和顺序访问，容易实现文件拓展，没有外部碎片

    • 缺点

      • 索引表占内存

  • 若一个索引块装不下一张索引表

    • 链接方案（低效）

      • 将多个索引块链接起来
      • 
      • 问题：对非常大的文件读取最后一个索引块需要访问前面所有的索引块

    • 多层索引

      • 二级索引

        • 

      • 采用K层索引结构，且顶级索引表没有调入内存，访问一个数据需要K+1读磁盘操作

    • 混合索引

      • 
      • 顶级索引表中既包含直接地址索引，一级间接索引，二级间接索引…
      • 对于小文件就可以放在直接地址索引中，这样就只需要两次读磁盘操作