这里先看文件管理的需求:
IO
系统的统一接口
按文件性质和用途分类(UNIX
),一般分为普通文件、目录文件、特殊文件(设备文件)、管道文件、套接字
ASCII
或二进制文件
I/O
设备,例如终端、打印机、网卡等。
块设备文件:磁盘
说明:这里是从用户角度看文件,由用户的访问方式确定,这里给出了三种逻辑结构,还可以组织成堆、顺序、索引、索引顺序、散列等结构。第一种是以字节为单位的流式结构,第二种是一种记录式文件结构,最后一种是树形结构。
UNIX
的seek
操作。
SSD
)、磁带、光盘、U
盘、......
block
、簇cluster
)
信息存储、传输、分配的独立单位
存储设备划分为大小相等的物理块,统一编号
<div class="image-package"> <div class="image-container" style="max-width: 634px; max-height: 435px; background-color: transparent;"> <div class="image-container-fill" style="padding-bottom: 68.61%;"></div>
<div class="image-view" data-width="634" data-height="435">
</div> </div> <div class="image-caption">3</div>
</div>
一次访问磁盘的请求:读写、磁盘地址(设备号、柱面号、磁头号、扇区号),内存地址(源/目)
完成过程由三个动作组成:
0
,否则为1
。
申请物理块时,可以在位示图中查找1
的位,返回对应的物理块号
归还时,将对应位转置1
。
磁盘地址与块号的转换
成组链接法设计思想
说明:左上角的是一个专用块,表示一些有用信息,而右边大括号中的都是空闲块。所有空闲块我们分成了若干组,典型的是100
块是一组,最后一个空闲组只有99
个空闲块。专用块中有20
个空闲块号,分别对应右边的空闲块组。每次要使用文件的时候,就从专用块中挑选空闲块,一般从801
开始分配。820
中的第一块实际上是记录了后面一块800
中空闲块的空闲块号和总的空块的数量,后面的以此类推。最后一个组中的0
则表示最后一组的标志。
成组链接法:分配算法
分配一个空闲块
查L
单元(空闲块数)
空闲块数 > 1 , i = L + 空闲块数
;
从i单元得到一个空闲块号;
把该块分配给申请者;
空闲块数减1
空闲块数 = 1
, 取出L + 1
单元内容(一组的第一块号或0
);
其值 = 0
无空闲块,申请者等待
其值不等于零,把该块内容复制到专用块
该块分配给申请者;
把专用块内容读到内存L
开始的区域。
成组链表法:回收算法
归还一块
查L
单元的空闲块数
空闲块数 < 100
空闲块数加一;
j := L + 空闲块数
归还块号填入j
单元
空闲块数 = 100
, 则把内存中登记的信息写入归还块中;
把归还块号填入L+ 1
单元;
将L
单元置成1
。
File Control Block:FCB
)
为管理文件而设置的数据结构,保存管理文件所需的所有有关信息(文件属性或元数据)
ASCII
/二进制、顺序/随机访问、临时文件、锁)
</div> </div> <div class="image-caption">6</div> </div>
FCB
,目录是文件控制块的有序集合说明:最初是以一级目录结构,最后慢慢演化成了树形目录结构。
文件在存储介质上的存放方式
主要解决两个问题:
N
块,这N块在磁盘上是怎么存放的?FCB
中是怎样记录的?在上图a
中,存放者多个连续的文件,在b
中有些磁盘空间被还回来了。如果有些块太小,可能就不能再利用了。在FCB
中我们只需要给出文件块的首地址和块数即可。
说明:在FCB
中我们只需要给出第一块的块号即可。
于是我们可以对此种结构进行某种改造:文件分配表FAT
<div class="image-package"> <div class="image-container" style="max-width: 533px; max-height: 342px;"> <div class="image-container-fill" style="padding-bottom: 64.17%;"></div>
<div class="image-view" data-width="533" data-height="342">
</div> </div> <div class="image-caption">11</div>
</div>
说明:是把所有物理块的表指针都几种存放在一张表中,而不是用一个物理块的一部分来存放指针。从图中可以看到文件A
的块号是4
,而其下一个物理块的表项为7
,最后到值为-1
则表示结束。那某文件的起始块号从哪里得到?其实起始块号就记录在了FCB
中。这种结构一般用在Windows
中。在UNIX
中一般采用索引结构。
i
个条目指向文件的第i
块。那索引表应该存放在何处?
这里必须知道每个文件的索引表长度是不一样的,于是不能存放在FCB
中,因为FCB
是固定大小的。于是我们在FCB
中只记录索引表的地址。
<div class="image-package"> <div class="image-container" style="max-width: 615px; max-height: 265px;"> <div class="image-container-fill" style="padding-bottom: 43.09%;"></div>
<div class="image-view" data-width="615" data-height="265">
</div> </div> <div class="image-caption">12</div>
</div>
说明:文件B
的索引块号是24
,索引表是存放在一个物理块中的。索引块中就记录了分配给这个文件的物理块号,可以看到这里我们是可以随机存取的。
</div> </div> <div class="image-caption">13</div> </div>
说明:图上部分是多级索引模式,此模式中顶级索引表中都记录的是次级索引表地址。而在图下部分则是综合模式,顶级索引表中一部分记录的是直接的物理块,而另一部分是记录的次级索表块地址,即一部分是直接寻址,一部分是间接寻址。
在UNIX
文件系统中采用的是多级索引结构(综合模式)
15
个索引项(FCB
中),每项两个字节12
项直接存放文件的物理块号(直接寻址)12
块,则利用第13
项指向一个物理块,在该块中存放的是一级索引表。假设扇区大小为512
字节,物理块等于扇区块大小,一级索引表可以存放256
个物理块号14
项和第15
项作为二级和三级索引表</div> </div> <div class="image-caption">14</div> </div>
2
的幂次方)连续的扇区,可寻址数据库<div class="image-package"> <div class="image-container" style="max-width: 700px; max-height: 55px;"> <div class="image-container-fill" style="padding-bottom: 7.21%;"></div>
<div class="image-view" data-width="763" data-height="55">
</div> </div> <div class="image-caption">15</div>
</div>
<div class="image-package"> <div class="image-container" style="max-width: 678px; max-height: 404px;"> <div class="image-container-fill" style="padding-bottom: 59.589999999999996%;"></div>
<div class="image-view" data-width="678" data-height="404">
</div> </div> <div class="image-caption">16</div>
</div>
<div class="image-package"> <div class="image-container" style="max-width: 588px; max-height: 350px;"> <div class="image-container-fill" style="padding-bottom: 59.519999999999996%;"></div>
<div class="image-view" data-width="588" data-height="350">
</div> </div> <div class="image-caption">17</div>
</div>
访问一个文件-->两步骤
FCB
根据路径名检索:
FCB
中文件物理地址等信息,计算出文件中任意记录或字符在存储介质上的地址
FCB
分成两部分
</div> </div> <div class="image-caption">18</div> </div>
说明:每个方格表示目录文件(由目录项组成),每个椭圆表示普通文件。如何我们采用目录项分解法,于是符号目录项中的内容就特别简单,此时目录项就变成了符号目录项;基本目录项保存在了磁盘的专用区域。
FCB
占48
个字节,物理块大小512
字节。符号目录项占8
字节(文件名6
字节,文件号2
字节),基本目录项占48-5 = 42
字节。
这里给出一个目录文件有128
个目录项,在分解前则需要13
个物理块,分解后符号目录项占2
块,基本目录项占11
块。总块数是不变的,但是查找一个文件的平均访问磁盘的次数分解前为(1+13)/2=7
次,分解后为(1+2)/2 + 1 = 2.5
次。于是就提高了文件检索的速度。
FCB
= 目录项 +i
节点i
节点号i
节点:描述文件的相关信息i
节点和若干磁盘块构成
<div class="image-package">
<div class="image-container" style="max-width: 700px; max-height: 399px;">
<div class="image-container-fill" style="padding-bottom: 55.879999999999995%;"></div>
<div class="image-view" data-width="714" data-height="399">
</div> </div> <div class="image-caption">19</div> </div>
说明:上图是UNIX
系统的文件布局。下面看如何查找一个文件
<div class="image-package">
<div class="image-container" style="max-width: 676px; max-height: 392px;"> <div class="image-container-fill" style="padding-bottom: 57.989999999999995%;"></div>
<div class="image-view" data-width="676" data-height="392">
</div> </div>
<div class="image-caption">20</div> </div>
说明:要查找的文件为/usr/ast/mbox
,根目录文件中一个点表示本目录的目录项,两个点表示父目录的目录项,每个目录项都包含文件名和i
节点号。从i
节点中可以知道这个文件的第一块存放在128
这个位置,于是我们读取usr
中的内容,从这个目录中去找ast
这个文件,以此类推。
<div data-note-content="" class="show-content">
1、2、4、8、16、32
或64
扇区FAT
的作用
描述簇的分配状态、标注下一簇的簇号等
FAT
表项:2
字节(16
位)32
字节</div> </div> <div class="image-caption">1</div> </div>
</div> </div> <div class="image-caption">2</div> </div>
<div class="image-package"> <div class="image-container" style="max-width: 700px; max-height: 401px;"> <div class="image-container-fill" style="padding-bottom: 56.32%;"></div>
<div class="image-view" data-width="712" data-height="401">
</div> </div> <div class="image-caption">3</div>
</div>
说明:这里是以FAT32
为例。
<div class="image-package"> <div class="image-container" style="max-width: 697px; max-height: 429px;"> <div class="image-container-fill" style="padding-bottom: 61.550000000000004%;"></div>
<div class="image-view" data-width="697" data-height="429">
</div> </div> <div class="image-caption">4</div>
</div>
说明:这里我们看BIOS
参数块,也是以FAT32
为例。
<div class="image-package"> <div class="image-container" style="max-width: 659px; max-height: 406px;"> <div class="image-container-fill" style="padding-bottom: 61.61%;"></div>
<div class="image-view" data-width="659" data-height="406">
</div> </div> <div class="image-caption">5</div>
</div>
0xFFFF
)
0
开始编号,簇0
和簇1
是保留的。
<div class="image-package">
<div class="image-container" style="max-width: 452px; max-height: 159px;">
<div class="image-container-fill" style="padding-bottom: 35.18%;"></div>
<div class="image-view" data-width="452" data-height="159">
</div> </div> <div class="image-caption">6</div> </div>
<div class="image-package"> <div class="image-container" style="max-width: 605px; max-height: 392px;"> <div class="image-container-fill" style="padding-bottom: 64.79%;"></div>
<div class="image-view" data-width="605" data-height="392">
</div> </div> <div class="image-caption">7</div>
</div>
说明:在前面讲过,UNIX
系统中i
节点加上目录项就是FCB
,而在FAT
文件系统中FCB
就等于目录项。32
个字节没有用完,没用完的保留。
FAT32
中,根目录区(BOOT
区)不是固定区域、固定大小,而是数据区的一部分,采用与子目录文件相同的管理方式32
字节,但分为各种类型(包括:“.”
目录项、“..”
目录项、短文件名目录项、长文件名目录项、卷标项(根目录)、已删除目录项(第一字节为0xE5
)等)Unicode
</div> </div> <div class="image-caption">8</div> </div>
<div class="image-package"> <div class="image-container" style="max-width: 700px; max-height: 508px;"> <div class="image-container-fill" style="padding-bottom: 71.95%;"></div>
<div class="image-view" data-width="706" data-height="508">
</div> </div> <div class="image-caption">9</div>
</div>
说明:这是一个基本的目录项。
<div class="image-package"> <div class="image-container" style="max-width: 577px; max-height: 408px;"> <div class="image-container-fill" style="padding-bottom: 70.71%;"></div>
<div class="image-view" data-width="577" data-height="408">
</div> </div> <div class="image-caption">10</div>
</div>
说明:左边的实现是目录项的长度不固定。第一个字段给出目录项的长度,然后把固定长度的属性记录在其后,再才是文件名,因为文件名的长度是不一样的,留出足够的空间给文件名。缺点就是一个文件删除时,就留出了一块空间,而这个空间可能不能放下其他文件,这样就会产生碎片。右边的实现是由于文件名的长度不固定,所以我们希望每个目录项的大小是固定的,其中包含了一个指向文件名起始地址的指针,然后是文件的相关属性,所有的文件名都存放在另一个区域(堆)。
<div class="image-package"> <div class="image-container" style="max-width: 602px; max-height: 337px;"> <div class="image-container-fill" style="padding-bottom: 55.98%;"></div>
<div class="image-view" data-width="602" data-height="337">
</div> </div> <div class="image-caption">11</div>
</div>
说明:其中有三处地方分别记录了文件名。前5
个字符(采用的是Unicode
编码,则两个字节代表一个字符)保存文件名的前5
个字符,于是一共可以保存13
个字符。如果一个长文件名目录项不够,则需要用第二个。在第一个字段中第6
位来记录是否是最后一个目录项。下面看一个例子,文件名为The quick brown.fox
,采用Unicode
编码。
<div class="image-package"> <div class="image-container" style="max-width: 700px; max-height: 492px;"> <div class="image-container-fill" style="padding-bottom: 65.25%;"></div>
<div class="image-view" data-width="754" data-height="492">
</div> </div> <div class="image-caption">12</div>
</div>
说明:其实这样一个文件占用了三个目录项。第一个目录项就是短文件名目录项,后面的两个目录项主要保存文件名。再看一个更长的文件名文件例子:
<div class="image-package"> <div class="image-container" style="max-width: 631px; max-height: 377px;"> <div class="image-container-fill" style="padding-bottom: 59.75%;"></div>
<div class="image-view" data-width="631" data-height="377">
</div> </div> <div class="image-caption">13</div>
</div>
说明:这里的文件名更长,需要占用五个目录项。
这里主要是以UNIX
操作系统为例。
FCB
* 在目录中为新文件建立一个目录项(在`UNIX`中还需要`i`节点),根据提供的参数及需要填写相关内容
create
(文件名,访问权限)
为文件读写做准备:给出文件路径名,获得文件句柄(file handler
)或文件描述符(file descripter
),需将该文件的目录项读到内存fd = open
(文件路径名,打开方式)
i
节点号)fd
(文件描述符,是一个非负整数,用于以后读写文件)seek
(fd
, 新指针位置):系统为每个进程打开的每个文件维护一个读写指针,即相对于文件开头的偏移地址(读写指针指向每次文件读写的开始位置 ,在每次读写完成后,读写指针按照读写的数据量自动后移相应的数值)
fd
查用户打开文件表,找到对应的表项read
(文件描述符,读指针,要读的长度,内存目的地址)
I/O
操作,把磁盘块中的信息读入缓冲区,再送到指定的内存区(多次读盘)3、4
直至读出所需数量的数据或读至文件尾可靠性:抵御和预防各种物理性破坏和人为性破坏的能力
<div class="image-package"> <div class="image-container" style="max-width: 679px; max-height: 407px;"> <div class="image-container-fill" style="padding-bottom: 59.940000000000005%;"></div>
<div class="image-view" data-width="679" data-height="407">
</div> </div> <div class="image-caption">14</div>
</div>
说明::一致性检查时,检查所有的文件和空闲块,检查完之后可能会出现四种结果。第一种是一个一致性的结果,即某个磁盘块要么分配给了某个文件,要么在空闲块中。第二种结果是在空闲块中找不到,但是也没有分配给某个文件,于是我们通过在空闲块表中将磁块标记为一来解决。第三种结果是某个磁盘块在空闲块表中出现了两次,同样是不合理的,对这一位进行修改。最后一种结果是在两个文件中出现,这种情况较为复杂,我们应该在空闲块中找一个,然后将其中一个磁盘块内容拷贝到这个空闲块中,然后将使用块表中的这一位减一。
对某些文件做出了修改,那么什么时候将修改后的内容写入到文件中。这里需要考虑文件系统一致性和速度。下面有几种写入策略
write-through
)
内存中的修改立即写到磁盘。缺点是速度性能差,如FAT
文件系统。
lazy-write
)
利用回写(write back
)缓存的方法得到高速。其缺点就是可恢复性较差,可能会导致信息丢失
tansaction log
)
采用事务日志来实现文件系统的写入,既考虑安全性,又考虑速度性能,如NTFS
<div data-note-content="" class="show-content">
这里我们讨论如何确保未经授权的用户不能存取某些文件?
于是在实现的时候需要考虑用户身份验证和访问控制。对于用户身份我们可以采用比如密码、口令等方式。
有不同的访问控制手段,比如主动控制(使用访问控制表)和能力表(使用权限表)。
ID
和访问权限
用户可以是一组用户
文件可以是一组文件
采用文件的二级存取控制,审查用户的身份、审查操作的合法性
group
)other
)w
)x
)-
)FCB
)分解、当前目录、磁盘碎片整理、块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID
技术等等
又称为文件缓存、磁盘高速缓存、缓冲区高速缓存。是指在内存中为磁盘块设置的一个缓冲区,保存了磁盘中某些块的副本。当对文件系统进行操作的时候:
I/O
请求时,和可能将来还会再次访问到这一数据块。</div> </div> <div class="image-caption">1</div> </div>
说明:在块高速缓存中有若干个数据块,首先将这些块使用一个双向链表组织起来,当要访问这个链的时候就将其从此链中拿出来,然后挂接到链尾,而我们对于某个文件使用的块要检查其是否在高速缓存中,所以这里又使用块号进行散列以提高检查速度。
LRU
)
因为此缓存的空间肯定是不会很大的,所以当其满时我们需要对其进行置换。对于以后可能会再次使用的块我们将其放在链尾,而对于使用概率很小的块可能就需要将其剔除。
一般有下面三种方式:
Windows
提供的FlushFileBuffer
函数实现I/O
并发工作用户对磁盘的访问通过访问文件缓存来实现:
Windows
的Cache Manager
实现对缓存的控制
* 读取数据的时候预取
Cache
满时,根据LRU
原则清除缓存的内容Cache
一致(每秒)write-back
机制
* 在用户要对磁盘写数据时,只更改`Cache`中的内容,由`Cache Manager`决定何时将更新反映到磁盘
分配磁盘块时,把有可能顺序存取的块放在一起(尽量分配在同一柱面上,从而减少磁盘臂的移动次数和距离)
说明:我们读取文件系统时,每次都要先找到i
节点区,然后再去找到文件位置,如果i
节点区在最外道,而相关文件在最里道,则在读取的时候磁臂就需要不断的移动,这样显示效率低下。一种解决方案如(a)
,我们将i
节点区和相关文件放在距离较近的磁道上;另一种是如(b)
,首先将磁道分成了若干组,然后将i节点区也划分成若干部分,每一组磁道都有一个i
节点区,而每个文件都和其i
节点区在同一组,这样磁臂也不需要很大的移动。
当有多个访盘请求等待时,采用一定的策略,对这些请求的服务顺序调整安排,从而降低平均磁盘服务时间,达到公平、高效的目的。
一次访盘时间 = 寻道时间 + 旋转延迟时间 + 传输时间
例子:假设磁盘访问序列:98、183、37、122、14、124、65、67
,这些数字表示柱面号或磁道号。读写头起始位置为53
。请计算磁头服务序列和磁头移动总距离(道数)。下面使用几种算法进行计算:
FCFS
)
按访问请求到达的先后次序服务
* 优点:简单、公平
磁道服务序列和访问序列一致,磁头移动总距离为640
,平均80
。
Shortest Seek Time First
)(重点)
用于磁盘
优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。
SCAN
电梯算法)(重点)
当设备无访问请求时,磁头不动;当有访问请求时,磁头按一个方向移动,在移动过程中遇到的访问请求进行服务,然后判断该方向上是否有访问请求,如果有则继续扫描;否则改变移动方向,并为经过的访问请求服务,如此反复。其实是一种对距离和方向的折中算法。
C-SCAN
)
这是对扫描算法的一种改进。
* 总是从零号柱面开始向里扫描
主要的目的是减少了新请求的最大延迟。
N-step-SCAN
策略
N
的子队列,每一次用SCAN
处理一个子队列N
,则它们全部都将在下一次扫描时处理N
值比较大时,其性能接近SCAN
;当N = 1
时,即FIFO
主要是为了解决磁头臂的粘性问题。
FSCAN
策略
主要是为了解决磁头臂的粘性问题。本算法及以上都是对磁臂移动的优化算法。
记录在磁道上的排列方式也会影响输入输出操作的时间。
<div class="image-package"> <div class="image-container" style="max-width: 585px; max-height: 290px;"> <div class="image-container-fill" style="padding-bottom: 49.57%;"></div>
<div class="image-view" data-width="585" data-height="290">
</div> </div> <div class="image-caption">7</div>
</div>
说明:如果信息是按左边那样分布的,那么如果首先读到1
号记录,然后花5ms
处理,但是此时磁盘已经转到了4
号记录,于是如果我们要处理2
号记录,则必须将4、5、6、7、8
都旋转过去之后才能处理2
号记录;而如果信息是按右边那样分布的,当处理完1
号记录,而此时磁盘也刚好旋转到了2
号记录处,这样就能极大的提高文件系统的性能。
典型的例子就是目录文件的存储。
起始就是独立磁盘冗余阵列(Redundant Arrays of Independent Disks
),就是将多块磁盘按照一定要求构成一个独立的存储设备。目的就是提高可靠性和性能。在实现时,需要考虑存储系统的速度、容量、容错、数据灾难发生后的数据恢复。
stripe
)RAID 0
- 条带化
* 数据分布在阵列的所有磁盘上
<div class="image-package"> <div class="image-container" style="max-width: 519px; max-height: 228px;"> <div class="image-container-fill" style="padding-bottom: 43.93%;"></div> <div class="image-view" data-width="519" data-height="228">
</div> </div> <div class="image-caption">8</div> </div>
这种方式没有冗余信息保存,即无差错控制,性能是最佳的。
RAID 1
-镜像
* 最大限度保证数据安全和可恢复性
50%
<div class="image-package">
<div class="image-container" style="max-width: 592px; max-height: 133px;">
<div class="image-container-fill" style="padding-bottom: 22.470000000000002%;"></div>
<div class="image-view" data-width="592" data-height="133">
</div> </div> <div class="image-caption">9</div> </div>
数据的安全性是最好的,但是磁盘利用率较低。
RAID 4
-交错块奇偶校验
* 带奇偶校验
<div class="image-package"> <div class="image-container" style="max-width: 527px; max-height: 168px;"> <div class="image-container-fill" style="padding-bottom: 31.879999999999995%;"></div> <div class="image-view" data-width="527" data-height="168">
</div> </div> <div class="image-caption">10</div> </div>
数据保存在前四块盘上,而校验信息保存在第五块盘上。