文件系统结构

磁盘特点：可以原地重写，可以直接访问任意一块。

内存和磁盘之间的IO以块为单位。每块为一个或多个扇区。扇区通常为512B

File system resides on secondary storage (disks) OS通过文件系统存储、定位、提取数据

• IO control 最底层

  由device driver 和 Interrupt handlers组成

  实现内存和磁盘之间的信息传输。

  device driver可作为翻译器。输入是高层命令，输出是底层的、硬件特定的命令。命令用于控制hardware controller

  

  device driver控制一类设备

• basic file system

  Issue generic commands to the appropriate device driver to read and write physical blocks on the disk.

• file-organization module

  将逻辑块地址 转换成 物理块地址

  也包括空闲空间管理器

• logical file system

  管理metadata，元数据包括文件系统所有结构数据，而不包括实际数据

  管理目录结构

  通过FCB((inodes in UNIX))维护文件结构

  负责保护和安全

Layering useful for reducing complexity and redundancy, but adds overhead and can decrease performance.

绝大多数OS支持多个文件系统

UNIX使用UFS

标准的Linux文件系统是extende file system

文件系统实现

每个卷的boot control block：从该卷引导OS需要的信息。如果没有OS，该块为空，通常为卷的第一块。UFS称之为boot block，NTFS称之为partition boot sector

每个卷的volume control blcok：包括卷(或分区)的详细信息，如分区的块数，块的大小…UFS称之为superblock，NTFS中它存在master file table中

每个文件系统的目录结构用来组织文件。UFS中包含文件名和相关的inode号，NTFS中它存储在master file table中

每个文件的FCB。UFS中是inode，NTFS存在master file table中，每个文件占一行

In-Memory File System Structures

一个内存中的mount table(partition table)

一个内存中的director structure cache

system-wide open-file table: 包括每个打开文件的FCB副本

per-process open-file table: Contains a pointer to the appropriate entry in the system-wide open-file table.

buffers hold data blocks from secondary storage.

对于访问打开文件表的索引：UNIX称之为file descriptor，Windows称之为file handle. 只要文件没有关闭，所有文件操作都是通过打开文件表来进行的

partitions and mounting 分区和安装

一个disk可以分为多个partition，一个partition可以横跨多个disk(作为RAID的一种形式比较合适)

分区可以是

• raw 没有文件系统
• cooked 含有文件系统

引导信息能保存在多个分区中，通常为一组有序块，并作为镜像文件读入内存

boot loader知道位于引导区的多个文件系统和多个操作系统，一旦装入，它可以引导位于磁盘上的一个操作系统。磁盘可以有多个分区，每个分区包含不同类型的文件系统和不同的操作系统。

root partiton包括操作系统内核或其他系统文件，在引导时装入内存。

内存中有Mount table – containing information about file systems that has been mounted.

virtual file system (VFS)

Virtual file system (VFS) on most OSes, including Unix, use object-oriented techniques to implement the file system. 用户甚至可以访问位于网络上的操作系统

VFS allows the same system call interface (the API) to be used for different types of file systems.

Implements vnodes which hold inodes or network file details.

The API is to the VFS interface, rather than any specific type of file system.

多个VFS接口的实现可以共存在同一台机器上

vnode表示位于整个网络范围内唯一的文件

Linux has four object types: inode, file, superblock, dentry

VFS defines a set of operations on the objects that must be implemented.

目录实现

linear list 线性列表

linear search time费时

sorted list允许binary search

a balanced tree

hash table

decreases directory search time

需要处理collision(两个文件名哈希到相同的位置)：chained-overflow

Difficulties: fixed size, hash function

分配方法

how disk blocks are allocated for files

Contiguous Allocation 连续分配

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

访问连续分配文件所需寻道数最少

用第一块的磁盘地址和连续块的数量来定义

sequential and direct access

Best performance in most cases

问题

• Difficult to find space for a new file: First-fit, best-fit
• External fragmentation
• compaction off-line (downtime) or on-line

Extent-Based Systems, a modified contiguous allocation scheme 当空间不够时，另一块被称为扩展的连续空间会添加到原来的文件分配中

Linked Allocation 链接分配

每个文件是磁盘块的链表

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

没有外部碎片

只要有空闲块，文件就可以增大

Disadvantages: 不能随机访问，指针需要空间，不可靠

对于指针需要空间，解决办法是将多个块组成簇(cluster)，代价是增加了内部碎片

FAT(file-allocation table)文件分配表

used by MS-DOS and OS/2

对FAT采用缓存

支持直接访问

Indexed Allocation 索引分配

每个文件都有索引块，是一个磁盘块地址的数组

目录条目包括索引块的地址

支持直接访问

没有外部碎片

索引块应该多大

• linked scheme

  将多个索引块链接起来

• two-level index

• combined scheme

  UNIX采用

性能

contiguous great for sequential and random

linked good for sequential, not random

combine contiguous allocation with indexed allocation by using contiguous allocation for small files (up to three or four blocks), automatically switching to an indexed allocation if the file grows large.

free-space management

文件系统需要维护free-space list记录空闲磁盘空间(不一定是链表)

bit map / bit vector

每块用一位表示。空闲-1，已分配-0

查找第一个和n个连续空闲块简单高效

Bit map requires extra space.

Easy to get contiguous files space.

linked list 链表

将所有空闲块用链表链接

将指向第一空闲块的指针缓存在内存

Cannot get contiguous space easily.

grouping

将n个空闲块的地址存在第一个空闲块里。(前n-1确实为空，最后一块包含另外n个空闲块的地址)

可以找到大量空闲块

counting

记录第一块的地址和紧跟第一块的连续的空闲块的数量n

can be stored in a balanced tree for efficiency

最后修改于 2020-02-28