文件系统

文件系统概述

文件系统结构

┌─────────────────────────────────────────────────────────┐
│                   文件系统层次                          │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  ┌─────────────────────────────────────────────────┐   │
│  │              应用程序                            │   │
│  └─────────────────────────────────────────────────┘   │
│                        │                               │
│  ┌─────────────────────────────────────────────────┐   │
│  │           逻辑文件系统                           │   │
│  └─────────────────────────────────────────────────┘   │
│                        │                               │
│  ┌─────────────────────────────────────────────────┐   │
│  │           文件组织模块                           │   │
│  └─────────────────────────────────────────────────┘   │
│                        │                               │
│  ┌─────────────────────────────────────────────────┐   │
│  │           基本文件系统                           │   │
│  └─────────────────────────────────────────────────┘   │
│                        │                               │
│  ┌─────────────────────────────────────────────────┐   │
│  │             I/O 控制                            │   │
│  └─────────────────────────────────────────────────┘   │
│                        │                               │
│  ┌─────────────────────────────────────────────────┐   │
│  │               设备                              │   │
│  └─────────────────────────────────────────────────┘   │
│                                                         │
└─────────────────────────────────────────────────────────┘

文件控制块（FCB）

┌─────────────────────────────────────────────────────────┐
│                        FCB                              │
├─────────────────────────────────────────────────────────┤
│  文件名                                                 │
│  文件类型                                               │
│  文件大小                                               │
│  文件位置（磁盘块号）                                    │
│  访问权限                                               │
│  创建时间                                               │
│  修改时间                                               │
│  访问时间                                               │
└─────────────────────────────────────────────────────────┘

文件分配方式

连续分配

┌─────────────────────────────────────────────────────────┐
│                   连续分配                              │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  文件 A: 起始块=0, 长度=3                               │
│  文件 B: 起始块=5, 长度=2                               │
│                                                         │
│  磁盘: [A][A][A][ ][ ][B][B][ ][ ][ ]                  │
│         0  1  2  3  4  5  6  7  8  9                   │
│                                                         │
│  优点：顺序访问快，随机访问简单                          │
│  缺点：外部碎片，文件扩展困难                           │
│                                                         │
└─────────────────────────────────────────────────────────┘

链接分配

┌─────────────────────────────────────────────────────────┐
│                   链接分配                              │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  文件 A: 起始块=0                                       │
│                                                         │
│  ┌───┐    ┌───┐    ┌───┐                              │
│  │ 0 │───>│ 3 │───>│ 7 │───> NULL                     │
│  └───┘    └───┘    └───┘                              │
│                                                         │
│  优点：无外部碎片，扩展方便                             │
│  缺点：随机访问慢，指针占空间                           │
│                                                         │
└─────────────────────────────────────────────────────────┘

索引分配

┌─────────────────────────────────────────────────────────┐
│                   索引分配                              │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  索引块:                                               │
│  ┌─────┐                                               │
│  │  0  │ → 数据块 0                                    │
│  │  3  │ → 数据块 3                                    │
│  │  7  │ → 数据块 7                                    │
│  │ ... │                                               │
│  └─────┘                                               │
│                                                         │
│  优点：支持随机访问，无外部碎片                          │
│  缺点：索引块占空间                                     │
│                                                         │
└─────────────────────────────────────────────────────────┘

目录结构

目录类型

类型	说明
单级目录	所有文件在一个目录
两级目录	用户目录 + 文件
树形目录	多级目录结构
无环图目录	支持文件共享

目录实现

┌─────────────────────────────────────────────────────────┐
│                   目录项                                │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  方式1：目录项包含完整 FCB                              │
│  ┌──────────────────────────────────────┐              │
│  │ 文件名 │ 属性 │ 大小 │ 位置 │ ...    │              │
│  └──────────────────────────────────────┘              │
│                                                         │
│  方式2：目录项只包含文件名和 inode 号                   │
│  ┌─────────────────┐                                   │
│  │ 文件名 │ inode │ ───> inode 表                     │
│  └─────────────────┘                                   │
│                                                         │
└─────────────────────────────────────────────────────────┘

I/O 系统

I/O 控制方式

方式	说明	特点
程序直接控制	CPU 轮询	简单，CPU 利用率低
中断驱动	I/O 完成后中断	CPU 利用率提高
DMA	直接内存访问	减少 CPU 干预
通道	专用 I/O 处理器	进一步解放 CPU

磁盘调度算法

算法	说明
FCFS	先来先服务
SSTF	最短寻道时间优先
SCAN	电梯算法
C-SCAN	循环扫描
LOOK	改进的 SCAN

SCAN 算法示例

磁道请求: 98, 183, 37, 122, 14, 124, 65, 67
当前磁头: 53，向右移动

移动顺序: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 37 → 14