Untitled

文件系统结构

文件控制块（File Control Block, FCB）包含有关文件的信息，包括所有者、权限、文件内容的位置等

分层设计的文件系统

逻辑文件系统（logical file syste）管理元数据信息，也负责保护

文件组织模块（file-organization module）可以将逻辑块地址转成物理块地址，还包括可用空间管理器，以跟踪未分配的块并根据要求提供的文件模块

基本文件系统（basic file system）向适当设备驱动程序发送通用命令，以读取和写入磁盘的物理块

I/O 控制（I/O control）包括设备驱动程序和中断处理程序，以在主内存和磁盘系统之间传输信息

文件系统实现

概述

文件控制块

文件控制块中不包含文件名，而是交给目录项管理

磁盘上的数据结构：
- （每个卷的）引导控制块（boot control block）可以包含从该卷引导操作系统的所需信息
- （每个卷的）卷控制块（volume control block）包括卷（或分区）的详细信息，在 Unix 中称为 superblock
- （每个系统的）目录结构用于组织文件
- 每个文件的 FCB 包括该文件的许多详细信息，在 Unix 中称为 inode
内存中的数据结构：
- 安装表（mount table）包含每个安装卷的有关信息
- 目录结构的缓存含有最近访问目录的信息
- 整个系统的打开文件表（system-wide open-file table）包括每个打开文件的 FCB 的副本以及其他信息
- 每个进程的打开文件表（pre-process open-file table）包括一个指向整个系统的打开文件中的适当条目的的指针，以及其他信息

内存中的文件系统结构 (a)打开文件 (b)读文件

打开文件表的条目有多种名称，UNIX 称之为文件描述符（file descriptor），Windows 称之为文件句柄（file handle）

虚拟文件系统

Untitled

虚拟文件系统（Virtual FIle System, VFS）层提供两个重要功能：
- 定义一个 VFS 接口，将文件系统的通用操作和实现分开，以面向对象的方式实现文件系统
- 提供机制以唯一表示网络上的文件，基于 vnode 的文件表示结构

目录实现

线性列表

采用文件名称和数据块指针的线性列表

编程简单但执行费时

哈希表

根据文件名获得一个值，并返回线性列表内的一个元素指针

采用溢出链接（chained-overflow）哈希表的每个条目可以是链表而不是单个条目

分配方法

连续分配

每个文件在磁盘上占有一组连续的块

用首块的磁盘地址和连续的块数来定义

支持顺序访问和直接访问

动态存储分配问题，造成外部碎片

确定一个文件需要多少空间，文件无法扩展

Extent-Based System

Extent-based file systems allocate disk blocks in extents

An extent is a contiguous block of disks

Extents are allocated for file allocation

A file consists of one or more extents

链接分配

每个文件是磁盘块的链表，磁盘块可能会散布在磁盘的任何地方

目录包括文件第一块和最后一块的指针，每块都有下一块的指针

Untitled

写文件导致空闲空间管理系统找到一个空闲块，这个新块会被写入，并链接到文件的尾部

没有外部碎片，空闲空间列表的任何块可以用于满足请求

只能有效用于顺序访问文件，不能支持直接访问

指针需要额外的空间

文件分配表（File-Allocation Table, FAT）

链接分配的变种，把用于链接文件各物理块的指针从每个物理块的块末尾提取出来，显示地存放在内存的一张链接表中

FAT 在整个磁盘中仅设置一张，每个表项中存放对应块的下一块链接指针

文件第一块的指针记录在目录中，后续的指针可通过查 FAT 找到

Untitled

FAT 还可以标记空闲的磁盘块，为文件分配新块只需要找到第一个空闲的 FAT 条目

改善了随机访问时间，通过读入 FAT 信息，磁头能找到任何块的位置

索引分配

将所有指针放在索引块（index block）中

每个文件都有自己的索引块，这是一个磁盘块地址的数组。索引块的第 i 个条目指向文件的第 i 个块

目录包含索引块的地址。当查找和读取第 i 个块时，采用第 i 个索引块条目的指针

Untitled

创建文件时，索引块的所有指针都设为空。首次写入第 i 块时，先从空闲空间中取得一个块，再将其地址写到索引块的第 i 个条目

索引分配支持直接访问，并且没有外部碎片问题

索引表增加索引空间的开销

考虑每块大小4KB，块地址4B。

链接方案（一级索引）：一个索引块可以存4KB/4B=1K个索引地址，每个索引地址直接引到文件块，所以最大1K*4KB=4MB

多层索引（二级索引）：一个索引块可以再继续连接到索引块，因此有1K1K4KB=4GB的最大文件

混合索引（Linux 分配方案）：Linux 中共有 15 个指针在 inode 中，前面 12 个直接指向文件块，因此有 48KB 可以直接访问，其他三个指针指向间接块，第一个间接块指针指向一级间接块，第二个指向二级间接块，第三个指向三级间接块。因此最大文件的大小为：124KB+1K4KB+1K1K4KB+1K1K1K*4KB = 48KB+4MB+4GB+4TB

Untitled