跳转至

HW13

文件系统

概念梳理

文件系统结构与视图

  • 分层设计结构：逻辑文件系统层 -> 文件组织模块层 -> 基本文件系统层 -> I/O 控制层

image-20260609110008239

  • 数据结构：在磁盘上（盘上结构）包含引导控制块、卷控制块（超级块）、目录结构和文件控制块（FCB/inode） 。
  • 内存结构：安装表、目录结构、打开文件表。

image-20260609110400675

image-20260609110428894

inode 作为类似索引，指向实际的 FCB 块。

文件存储空间分配

  • 连续分配：FCB 连着分布在存储中
  • 链接分配 (FAT)：FCB 分布不连续，上一个 FCB 末尾存放发往下一个 FCB 的指针。
  • 索引分配：每个文件对应一个索引块，给索引块归档到索引表。每个表项对应一个物理文件块。
    • 二级/多级索引。

image-20260609110734505

混合索引

空闲存储空间管理

  • 位图法：

需要额外存储

image-20260609110806890

  • 链接法

无需额外空间，在连续空间中表现不佳

image-20260609110849665

  • 分组法

通过链表指针，拼接多个空闲块的 索引表 image-20260609110949880

  • 计数法

适用于连续分配 / 释放

image-20260609111029384

文件共享

硬链接

image-20260609111100023

已有：(A，inodeA)；再设置 (B，inodeA) 通过相同的索引指向一致的 FCB 。会改变索引节点中的 count 计数。

符号链接/软链接

image-20260609111248960

软链接是一个全新的文件 它可以理解为 (softLink, inodeSoftLink) 指向的 FCBSoftLink 中 存放的是 LinkFile 的文件名。也就是说软链接的修改的引用和原文件的引用是彼此独立的

image-20260609111536497

示例习题：

image-20260609111547680

  • F2 是软链接，具备向自己的索引。countF2 = 1
  • F3 为硬链接，F3、F1 共享一个 inode 此时 countF1 = count F3 = 2
  • F1 删除，本质是 F1 对应的 inode 失效，对应的 FCB 中关于 F1 的部分失效。但是 inode 原本是 2 ，自减后得到了 inode = 1 此时 FCB 关于 F3 的部分、以及 FCB 的数据依然存在。countF3 = 1

B

习题

image-20260609111948872

  • 1 Disk 1024B
    • 1 FCB 64B
      • 1 FileName 8B

这里的划分方式是给 FCB 进行拆分：

16B (FileName, FileInterNode); 64B(FileInterNode, FileEtcInfo)

这里使用分解法与否的效果的关键就在于一个磁盘空间可以存放多少索引的 inode 信息

假设使用分解法：

只需给 16B 放入相关的磁盘中，1 disk 可以存放 64 个 inode ，一共只需要 \(\frac{254}{64}\approx3.96\) 也就是 4 个磁盘就可以存放好文件内部号信息。

  • 查找文件号次数：

最坏4次 最好1次 平均 2.5 次找到文件内部号

  • 根据文件号找到文件控制块：

1次

总共 3.5次。

不用分解法

文件内部号存在 FCB 中 一个磁盘可以放 16 个 FCB/内部号。总共需要 \(\frac{254}{16}\approx15.8\) 也就是 16个磁盘。

  • 直接查找 FCB 块

平均 17/2 = 8.5 次

总共 8.5 次

分解前占用 n 个盘，分解后占用 m 个盘，那么

\[\frac{n+1}{2} \gt \frac{m+1}{2}+1\]
\[n > m + 2\]

image-20260609114529569

如何理解这里的表目/物理结构

用来作为索引，指向相关的磁盘/逻辑块。

这里索引结构的设计思路，使得我们可以在一个磁盘块中放大量的表目，作为索引表。一个磁盘块可以存放 256 个指针索引。

  • 60% 文件大小不超过 8 个逻辑块。那么我们先分配 8 个直截索引，来一步到位访问到逻辑块

  • 30% 文件大小不超过 260 个块，因为已有 8 个块的直截索引，还差 252 个，可以用一个表目指向索引逻辑表，这里能提供 256 个二级索引，满足要求。

  • 10% 文件大小不超过 65000 个块，参考类似的思路，如果我们使用剩下的最后一个表目指针，设计二级的索引，有：65536 个块 满足需求。

磁盘存储

概念梳理

存储结构概述

  • 存储介质

    • 磁盘

image-20260609161838386

  • 磁带

  • SSD

  • 访问时间

image-20260609161834949

  • 磁盘连接

image-20260609161830963

磁盘调度

旋转延迟和传输时间是相对固定的，想要优化磁盘的访问效率，主要在于优化寻道时间，即如何最快的定位到需要的磁道。

可以把整个磁道系统画成一条数轴，磁头就是一个左右移动的指针。

  • FCFS

image-20260609115950495

image-20260609120157227

按顺序来

  • SSTF

image-20260609161737941

image-20260609161747987

100开始 最近90 ； 90后，最近58；58后，最近55....

会饥饿

  • SCAN

image-20260609161806494

基于 SSTF ，固定磁头走的方向，直到走到磁道尽头再掉头。

image-20260609161811576

先往150 移动，再考虑慢慢往回。

  • CSCAN

image-20260609161816385

与 SCAN 的区分在于： SCAN 的去程和返程都处理磁道任务， CSCAN 只有去程处理，其余立刻返回。

对于两端请求公平。

  • Look / C-Look

image-20260609131349460

与磁道的尽头不太一样，走到请求的尽头就掉头。

  • N-Step-SCAN

先给所有的磁道请求分成 N 个队列，队列使用 FCFS 。每个队列中使用 SCAN。

  • FSCAN

简化到 2 个队列

  • 一个存放初始的所有请求
  • 一个存放在扫描过程中新到的所有请求。

image-20260609161858660

  • 4-Step-SCAN

进行拆分，Queue 1 : [98, 183, 37, 122] Queue 2 : [14, 124, 65, 67] Queue 3 : [80, 25]

SCAN 默认请求结尾调头

Queue 1 ：

\[50\to98\to122\to183\to37\quad l_1=183-50+183-37=279\]

Queue 2 ：

\[37\to14\to65\to67\to124\quad l_2=37-14+124-14=133\]

Queue 3 ：

\[124\to80\to25\quad l_3=124-25=99\]

\(L=511\)

  • FSCAN

Queue 1 ： [98, 183, 37, 122, 14, 124, 65, 67] Queue 2 : [80, 25]

Queue 1 :

\[50\to65\to67\to98\to122\to124\to183\to37\to14\quad l_1=183-50+183-14=302\]

Queue 2 :

\[14\to25\to80\quad l_2=80-14=66\]

\(L=368\)

磁盘管理与优化

  • 格式化与引导 image-20260609162350655

  • 坏区管理与优化 image-20260609162355299

  • 空间交换 image-20260609162400648

磁盘容错技术

分三级展开：

  • 第一级容错技术
  • 第二级容错技术
    • 双份目录
    • 写后读校验
    • 磁盘镜像
    • 磁盘双工
  • 第三级容错技术
    • 文件服务器镜像
    • RAID 技术
      • RAID 0# 数据条带
      • RAID 1# 磁盘镜像
      • RAID 2# 字存取，提供冗余检测
      • RAID 3# Simplier 2# 使用奇偶校验盘
      • RAID 4# 类似 3# 但是数据按 Block 拆分
      • RAID 5#、6#、7#

习题

image-20260609162417122

前两者不管方向。

  1. FCFS
\[143\to86\to147\to91\to177\to94\to150\to102\to175\to130\quad L=63+61+56+86+83+56+48+73+45=571\]
  1. SSTF

Queue [86, 147, 91, 177, 94, 150, 102, 175, 130]

\[143\to147\to150\to130\to102\to94\to91\to86\to175\to177\quad L=4+3+20+28+8+3+5+89+2=162\]
  1. Look

按增大的方向走，走到请求尽头调头。

\[143\to147\to150\to175\to177\to130\to102\to94\to91\to86\quad L=4+3+25+2+47+28+8+3+5=125\]

image-20260609162452152

image-20260609162454966

  1. 2KB = 2 * 1024 * 8 = 16386 Bits 使用位示图即可，一个比特代表一个磁盘的空闲状态。
  2. “寻道 + 等半圈 + 读数据” 先提取关键点：初始在 100，向变大方向移动。先按照 CSCAN 梳理移动序列：

Queue : [50, 90, 30, 120] 从 100 开始 ：

\[100\to120\to30\to50\to90\quad L=120-100+120-30+60=170\]

寻道用时 : 110 * 1ms = 170ms

扇区旋转用时 : 1min 6000r -> 1s 100r 转一圈只需要 10ms , 读取一个扇区需要 0.1 ms 平均旋转等待时间为 5ms 综合用时 170 + (5.1) * 4 = 190.4 ms

  1. 非常简洁，我们都已经不考虑寻道时间，直接 FCFS 即可， Less is More