6.56.5文件存储空间的管理文件存储空间的管理壹.壹.空闲表法空闲表法1.数据结构：序号第一空闲盘块号空闲盘块数124293315504——2.分配与回收：连续分配方式二二..空闲链表法空闲链表法(1)空闲盘块链657810300310……5678299300310特点：•分配、回收简单；•但分配回收时需要大量的I/O操作，效率低。二二..空闲链表法空闲链表法(2)空闲盘区链分区序号、起始块号、盘块数等三三..位示图法位示图法1.位示图概念每一位01磁盘块空闲已分配出去01234567891011121314150123411000111100101111111110011000011110111111111111111111101111011110000000000000000………..(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，如果行号、列号、块号都从0开始编号，则其相应的盘块号应按下式计算：b=n×i+j式中，n代表每行的位数。(3)修改位示图，令map［i,j］=1。三三..位示图法位示图法2.盘块的分配3.盘块的回收(1)将回收盘块的盘块号b转换成位示图中的行号i和列号j。转换公式为：i=bDIVnj=bMODn(2)修改位示图。令map［i,j］=0。三三..位示图法位示图法如果行号、列号、块号都从1开始，则：b=n×(i-1)+ji=(b-1)DIVn+1j=(b-1)MODn+1123456789101112131415161234511000111100101111111110011000011110111111111111111111101111011110000000000000000………..4.特点位示图常用于微型机和小型机中。它的特点：•找空闲块容易；•磁盘容量不大时，位示图很小，可事先读入内存，从而加快分配、回收的速度。例子：MINIX（分配单位叫区段，类似于FAT的簇）三三..位示图法位示图法i-结点区1个磁盘块i结点位示图区段位示图数据区……………0#1#引导块超级块MINIX文件卷布局5.位示图的一种变形采用FAT的文件系统：三三..位示图法位示图法一个FAT表项0其他磁盘数据区的一簇空闲已分配出去、坏簇或保留簇根目录区…FAT文件卷布局数据区1个扇区FAT1FAT2…………0#引导块FAT32(1)将所有的空闲盘块分成若干组：•最后1组99块；•其余每组100块；•剩余的、不超过100块的盘块成为第1组。(2)将各组空闲盘块链起来：•把后一组的盘块数和各个盘块的块号记入前一组的最后一个盘块中；•最后一组99块，加上结束标记“0”，仍记作100块；•第一组的块数和各个盘块的块号则记录到超级块的空闲盘块号栈中。四四..成组链接法成组链接法1.空闲盘块的组织（如：UNIX）引导块超级块索引结点区数据区对换区012……200201……79998000…9999四四..成组链接法成组链接法7801780178027802…7899789979007900301301302302…399399400400201201202202…2992993003007901790179027902…799979997701770177027702…7799779978007800…………引导块超级块索引结点区数据区对换区012……200201……79998000…999910007999790279011000799979027901…四四..成组链接法成组链接法7801780178027802…7899789979007900301301302302…399399400400201201202202…2992993003007901790179027902…79997999007701770177027702…7799779978007800s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100300299202201超级块10079007899780278011007900789978027801……100500499402401100500499402401…100400399302301100400399302301………………空闲盘块号栈四四..成组链接法成组链接法引导块超级块索引结点区数据区对换区012……200201……79998000…9999超级块•超级块也叫做卷资源表，用来记录整个文件卷的资源及使用情况。•超级块中的内容主要有：‐索引节点区占用的盘块数；‐整个文件卷的总块数；‐磁盘块的大小；‐用来登记空闲磁盘块的空闲盘块号栈及锁标志；‐用来登记空闲磁盘i结点的空闲i结点栈及锁标志；‐只读标记等信息。•当某个文件卷被安装到整个文件系统的目录树上时，其超级块便被读入内存超级块表中。2.空闲盘块的分配s_free[s_nfree]＝0?将bno号盘块的内容读到超级块的空闲盘块号栈中返回YN将s_nfree置0；置错误标记为：无空闲块s_nfree≤0?NY（系统已无空闲盘块...
