基本概念

文件系统和文件

文件系统: 一种用于持久性存储的系统抽象

在存储上: 组织,控制,导航,访问和检索数据
在大多数计算机系统包含文件系统
个人电脑,服务器,笔记本电脑
ipod,tivo,机顶盒,手机,电脑
google可能也是由一个文件系统构成的

文件: 文件系统中的一个单元的相关数据在操作系统中的抽象

文件系统的功能:

1. 分配文件磁盘空间
- 管理文件块(哪一块属于哪一个文件)
- 管理空闲空间(哪一块是空闲的)
- 分配算法(策略)
2**. 管理文件集合**
- 定位文件及其内容
- 命名: 通过名字找到文件的接口
- 最常见: 分层文件系统
- 文件系统类型(组织文件的不同方式)
3. 提供的便利及特征
- 保护: 分层来保护数据安全
- 可靠性,持久性: 保持文件的持久即使发生崩溃,媒体错误,攻击等

文件和块:

文件属性:

名称,类型,位置,大小,保护,创建者,创建时间,最久修改时间…

文件头:

在存储元数据中保存了每个文件的信息,保存文件的属性,跟踪哪一块存储块属于逻辑上文件结构的哪个偏移

文件描述符

文件使用模式:

使用程序必须在使用前先”打开”文件 open(name, flag)

内核跟踪每个进程打开的文件:

操作系统为每个进程维护一个打开文件表
一个打开文件描述符是这个表中的索引

需要元数据来管理打开文件:

文件指针: 指向最近的一次读写位置,每个打开了这个文件的进程都这个指针
文件打开计数: 记录文件打开的次数 - 当最后一个进程关闭了文件时,允许将其从打开文件表中移除
文件磁盘位置: 缓存数据访问信息
访问权限: 每个程序访问模式信息

3_1. 用户视图: 持久的数据结构

3_2. 系统访问接口

字节的集合(UNIX)

系统不会关心你想存储在磁盘上的任何的数据结构

3_3. 操作系统内部视角:

块的集合(块是逻辑转换单元,而扇区是物理转换单元)

块大小<> 扇区大小: 在UNIX中, 块的大小是 4KB

当用户说: 给我2-12字节空间时会发生什么?

获取字节所在的快
返回快内对应部分

如果要写2-12字节?

获取块
修改块内对应部分
写回块

在文件系统中的所有操作都是在整个块空间上进行的:

getc() putc() 即使每次只访问1字节的数据,也会缓存目标数据4096字节(一个磁盘块)

用户怎么访问文件:

在系统层面需要知道用户的访问模式

顺序访问: 按字节依次读取
1. (几乎所有的访问都是这种方式)
随机访问: 从中间读写
1. (不常用,但是仍然重要,如: 虚拟内存支持文件,内存页存储在文件中;
2. 更加快速,不希望获取文件中间的内容的时候也必须先获取块内所有字节)
内容访问: 通过特征( 比较少用 )

文件内部结构

无结构: 单词,比特的队列
简单记录结构: 列；固定长度；可变长度
复杂结构: 格式化的文档(word, PDF)；可执行文件；…

文件访问的访问控制

多用户系统中的文件共享是很必要的

访问控制:

谁能够获得哪些文件的哪些访问权限

访问模式: 读,写,执行,删除,列举等

文件访问控制列表(ACL):

<文件实体, 权限>

UNIX模式:

<用户|组|所有人,读|写|可执行>
用户ID识别用户,表明每个用户所允许的权限及保护模式
组ID允许用户组成组,并指定了组访问权限

指定多用户,客户如何同时访问共享文件:

和过程同步算法相似
因磁盘IO和网络延迟而设计简单

UNIX文件系统(UFS)语义:

多个系统/用户如何同时访问文件

对打开文件的写入内容立即对其他打开同一文件的其他用户可见

共享文件指针允许多用户同时读取和写入文件

会话语义:

写入内容只有当文件关闭时可见

锁:

一些操作系统和文件系统提供该功能

文件别名

两个或多个文件名关联同一个文件:

硬链接: 多个文件项指向一个文件
软链接: 以快捷方式指向其他文件
通过存储真实文件的逻辑名称来实现

如果删除一个有别名的文件会如何呢?

: 这个别名将成为一个悬空指针

Backpointers方案：

链接: 已存在文件的另外一个名字(指针)
链接处理: 跟随指针来定位文件

相对于方案二他会形成一个环。

如何保证没有循环呢？

只允许到文件的链接, 不允许在子目录的链接
每增加一个新的链接都用循环检测算法确定是否合理
限制路径可遍历文件目录的数量

文件系统种类

磁盘文件系统:

文件存储在数据存储设备上,如磁盘; 例如: FAT,NTFS,ext2,3,ISO9660等

数据库文件系统:

文件根据其特征是可被寻址的; 例如: WinFS

日志文件系统:

记录文件系统的修改,事件; 例如: journaling file system

网络,分布式文件系统:

例如: NFS,SMB,AFS,GFS

特殊,虚拟文件系统

网址等

文件可以通过网络被共享

分布式文件系统的问题

第二部分：虚拟文件系统

分层结果
1. 上层：虚拟文件系统
2. 底层：特定文件系统模块

虚拟文件系统的目标

目的: 对所有不同文件系统的抽象

功能:

提供相同的文件和文件系统接口
管理所有文件和文件系统关联的数据结构
高效查询例程,遍历文件系统
与特定文件系统模块的交互

数据结构:

卷[第四声]控制块(UNIX: “superblock”)

每个文件系统一个
文件系统详细信息
块,块大小,空余块,计数,指针等

文件控制块(UNIX: “vnode” or “inode”)

每个文件一个
文件详细信息
许可,拥有者,大小,数据库位置等

目录节点(Linux: “dentry”)

每个目录项一个(目录和文件)
将目录项数据结构及树形布局编码成树形数据结构
指向文件控制块,父节点,项目列表等

文件系统数据结构：

卷控制块(每个文件系统一个)
文件控制块(每个文件一个)
目录节点(每个目录项一个)

持续存储在二级存储中:

在分配在存储设备中的数据块中

当需要时加载进内存:

卷控制块: 当文件系统挂载时进入内存
文件控制块: 当文件被访问时进入内存
目录节点: 在遍历一个文件路径时进入内存

数据块缓存

各种缓存方式

数据块按需读入内存:

提供 read() 操作
预读: 预先读取后面的数据块

数据块使用后被缓存:

假设数据将会再次被使用
写操作可能被缓存和延迟写入

两种数据块缓存方式:

普通缓冲区缓存
页缓存: 同一缓存数据块和内存页

分页要求: 当需要一个页时才将其载入内存

支持存储: 一个页(在虚拟地址空间中)可以被映射到一个本地文件中(在二级存储中)

文件数据块的页缓存

在虚拟内存中文件数据块被映射成页
文件的读写操作被转换成对内存的访问
可能导致缺页和/或设置为脏页
问题：页置换 – 从进程或文件页缓存中？

打开文件的数据结构

我们都知道打开文件我们就可以对文件进行读写，但是打开文件时操作系统干了那些事情就是这次需要学习的.

打开文件描述:

每个被打开的文件一个
文件状态信息
目录项,当前文件指针,文件操作设置等

打开文件表:

一个进程一个
一个系统级的
每个卷控制块也会保存一个列表
所以如果有文件被打开将不能被卸载

一些操作系统和文件系统提供该功能
调节对文件的访问
强制和劝告:

强制 - 根据锁保持情况和需求拒绝访问

劝告 - 进程可以查找锁的状态来决定怎么做

文件分配

打开文件后我们需要对文件进行相关的操作，这些操作的背后是操作系统对内存/文件等的分配数据块

如何分配数据块

分配方式:

连续分配
链式分配
索引分配

指标:

高效: 如存储利用(外部碎片)
表现: 如访问速度

一、方式一：连续分配:

只需要知道文件头指定起始块和长度

位置/分配策略: 最先匹配,最佳匹配,…

优势: 文件读取表现好;高效的顺序和随机访问

缺点： 碎片;文件增长问题

类似数组的形式。

二、方式二：链式分配:

文件以数据块链表方式存储

文件头包含了到第一块和最后一块的指针

优势: 创建,增大,缩小很容易;没有碎片

劣势: 不可能进行真正的随机访问;可靠性

三、索引分配:

为每个文件创建一个名为索引数据块的非数据数据块(到文件数据块的指针列表)

文件头包含了索引数据块

优势: 创建,增大,缩小很容易;没有碎片;支持直接访问

劣势: 当文件很小时,存储索引的开销大;处理大文件难

两种索引：

早期Unix阶段的文件索引块：

可以看出如果文件容量小的很容易就能找到，但是对于大容量的文件就非常麻烦，对于性能及其数据块的开销等等都是有着很大的影响。

空闲空间列表

站在磁盘的角度，我们需要对文件进行分配空闲空间块，对于空闲空间块一定是从空闲的磁盘块中来的。但是空闲的磁盘块他不是属于文件的，与此同时他还需要被文件系统管理起来（类比我不是你们公司的人，但是我需要和你们公司合作，所以需要遵守贵公司的规定,,., ）

操作系统需要有效并且快速的将这些空闲的空间组织起来供文件系统去查找及其分配等等，这些都是我们操作系统的文件系统需要去解决的问题。

管理空闲空间块的使用程度：

用位图代表空闲数据块列表:

11111101101110111

如果 i = 0表明数据块i 是空闲的, 反之是分配的

使用简单但是可能会是一个big vector:

例如： 160GB disk →(有40MB的空闲块) 40M blocks → 5MB worth of bits（需要5MB来表示160GB磁盘的空闲情况）
然而,如果空闲空间在磁盘中均匀分布,那么再找到”0”之前需要扫描磁盘上数据块总数（n）/ 空闲块的数目（r）

这个管理空闲空间的数据块空间是需要保护:

指向空闲列表的指针
位图:

必须保存在磁盘上;

在内存和磁盘拷贝可能有所不同;

不允许block[i]在内存中的状态为bit[i]=1而在磁盘中bit[i]=0

解决:

在磁盘上设置bit[i] = 1;

分配block[i];

在内存中设置bit[i] = 1

多磁盘管理 -RAID

通常磁盘通过分区来最大限度减小寻道时间:

一个分区是一个柱面的集合
每个分区都是逻辑上独立的磁盘

分区: 硬件磁盘的一种适合操作系统指定格式的划分

卷: 一个拥有一个文件系统实例的可访问的存储空间

(通常常驻在磁盘的单个分区上)

提高磁盘数据可靠性及其性能

使用多个并行磁盘来增加: 吞吐量(通过并行),可靠性和可用性(通过冗余)
RAID - 冗余磁盘阵列:

各种磁盘管理技术;RAID levels: 不同RAID分类,

如RAID-0,RAID-1,RAID-5

实现:

在操作系统内核: 存储,卷管理; RAID硬件控制器(IO)

为什么我们可以通过RAID来提高磁盘效率呢？

答：我们将数据放在相对独立的硬盘里面，每个硬盘可以相对独立的并行工作。这样就可以实现数据并行的访问。

一、RAID-0

数据块分成多个子块, 存储在独立的磁盘中: 和内存交叉相似

通过更大的有效块大小来提供更大的磁盘带宽

二、RAID-1

可靠性成倍增长

读取性能线性增加(向两个磁盘写入,从任何一个读取)

三、RAID-4

数据块级磁带配有专用奇偶校验磁盘: 允许从任意一个故障磁盘中恢复

条带化和奇偶校验按byte-by-byte或者bit-by-bit: RAID-0,4,5: block-wise ;RAID-3: bit-wise

四、RAID-5

每个条带快有一个奇偶校验块,允许有一个磁盘错误

五、RAID-6

两个冗余块,有一种特殊的编码方式,允许两个磁盘错误

磁盘调度

磁盘性能优化的另一个层面（一个是RAID上一章）：

通过重新组织IO的顺序来有效的减少磁盘的访问开销

磁盘的性能怎么来表示：

读取或写入时,磁头必须被定位在期望的磁道,并从所期望的扇区开始
寻道时间: 定位到期望的磁道所花费的时间
旋转延迟: 从扇区的开始处到到达目的处花费的时间

平均旋转延迟时间 = 磁盘旋转一周时间的一半

IO传输时间表达式

寻道时间是性能上区别的原因

对单个磁盘,会有一个IO请求数目

如果请求是随机的,那么会表现很差

如何解决这种磁盘上寻道时间的开销大的问题

(一) FIFO

按顺序处理请求
公平对待所有进程
在有很多进程的情况下,接近随机调度的性能

虽然上述的FIFO是一种简洁的方式，但是它并不高效。所以需要另一种方法：

(二) 最短服务优先:

选择从磁臂当前位置需要移动最少的IO请求

总是选择最短寻道时间

(三) skan方法（电梯的IO请求调度算法） :

磁臂在一个方向上移动,满足所有为完成的请求,直到磁臂到达该方向上最后的磁道
调换方向

(四) c-skan方法 :

限制了仅在一个方向上扫描
当最后一个磁道也被访问过了后,磁臂返回到磁盘的另外一端再次进行扫描

(五) c-loop(c-skan改进)方法:

磁臂先到达该方向上最后一个请求处,然后立即反转

还有很多其他的方式：

SSTF、SCAN、CSCAN等几种调度算法。这几种就自己网上查具体实现的方式。

这几种算法也就是解决了机械硬盘的访问读写慢的问题，性能的差异解决。想要从根本上解决问题，那么就买SSD固态硬盘吧…..