操作系统第8章磁盘存储器的管理.

第八章文件管理8.1外存的组织方式8.2文件存储空间的管理8.1外存的组织方式文件的物理结构又称为文件的存储结构，是指文件在外存上的存储组织形式，与存储介质的特性有关类型顺序文件结构链接文件结构索引文件结构8.1外存的组织方式外存组织方式连续组织方式（连续分配）链接组织方式（链接分配）索引组织方式（索引分配）8.1外存的组织方式连续组织方式为每个文件分配一组连续的盘块文件物理地址：文件所占的第一个盘块号和盘块数优点实现简单顺序访问容易顺序访问速度快缺点创建时就要知道文件的最大长度存在磁盘碎片（存储压缩技术）在CD-ROM上被广泛使用012345678910111213141516171819202122232425262728293031文件名始址块数count02tr143mail196list284f62文件目录countftrmaillist8.1外存的组织方式链接组织方式一个文件的信息存放在若干不连续的盘块中，各块之间通过指针连接优点提高了磁盘空间利用率，不存在外部碎片问题有利于文件插入和删除有利于文件动态增长链接方式分为隐式链接显式链接8.1外存的组织方式隐式链接文件物理地址：指向第一个盘块和最后一个盘块的指针其余盘块靠盘块自身所含的指针相连缺点存取速度慢，不适于随机存取可靠性差（如指针出错）更多的寻道次数和寻道时间链接指针占用一定的空间改进将几个盘块组成一个簇，以簇为单位分配盘块，文件的每一个元素也以簇为单位文件名始址末址jeep925文件目录01234567891011121314151617181920212223242526272829303111016-1258.1外存的组织方式显式链接文件分配表FAT（FileAllocationTable）整个磁盘一张，存于内存其序号为盘块号，内容为链接指针文件物理地址：链首指针所对应的盘块号其余指针存放于FAT中优点减少访盘次数，提高检索速度，随机存取容易缺点FAT占据大量内存空间在内存中使用文件分配表的链表结构8.1外存的组织方式8.1外存的组织方式索引组织方式单级索引组织方式一个文件的信息存放在若干不连续的物理块中，系统为该文件建立一个专用数据结构--索引表，并将其所占块的盘块号存放在该索引表中一个索引表就是磁盘块地址数组，其中第i个条目指向文件的第i块文件物理地址：索引表所在盘块号8.1外存的组织方式优点既能顺序存取，又能随机存取满足了文件动态增长、插入删除的要求能充分利用外存空间缺点较多的寻道次数和寻道时间索引表本身带来了系统开销如：内外存空间，存取时间012345678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep1991711025-1-1-1198.1外存的组织方式多级索引组织方式将一个大文件的所有索引表（二级索引）的地址放在另一个索引表（一级索引）中012……………105106254356357985105106254740356357…1125985360740…1125…主索引360第二级索引磁盘空间8.1外存的组织方式增量式索引组织方式UNIX文件系统采用每个文件的物理地址为13个地址项最前面10项存放文件所占物理块号（直接寻址）第11项存放一级索引地址第12项存放二级索引地址（间接寻址）第13项存放三级索引地址8.1外存的组织方式返回8.2文件存储空间的管理空闲表法系统设一张空闲表每组连续的空闲盘块占一个表项（序号，第一空闲盘块号，空闲盘块数）属连续分配：分配和回收与内存管理的动态分区分配方法类似分配速度快，可减少访盘频率，用于小文件的分配和对换空间的管理8.2文件存储空间的管理序号第一空闲盘块号空闲盘块数12429331554----空闲表8.2文件存储空间的管理空闲链表法把所有空闲盘块链成一个空闲链表根据构成链的基本元素不同，可有两种链表形式空闲盘块链：基本元素为盘块优点：分配回收过程简单缺点：空闲盘块链可能很长空闲盘区链：基本元素为盘区（可包含若干个连续的空闲盘块）优点：链比较短缺点：分配回收与动态分区类似，较复杂8.2文件存储空间的管理位示图法位示图所有盘块都有一个二进制位与之对应，由所有盘块所对应的位组成的集合，称为位示图。二进制位——1，表示对应的盘块已分配——0，表示对应的盘块空闲varmap：array[1…m，1…n]ofbit优点：占用空间少，可保存在内存；描述能力强，适合各种物理结构8.2文件存储空间的管理位示图123456789101112131415161110001110010011020001111110000111311100011111100004168.2文件存储空间的管理盘块的分配顺序扫描位示图，查找为0的一个或一组二进制位返回对应盘块号假设找到的二进制位位于第i行，第j列，对应的盘块号为：b=n(i-1)+j（n为每行的位数）修改位示图：map[i,j]=1盘块的回收将回收盘块号b转换成行号i和列号ji=(b-1)DIVn+1；j=(b-1)MODn+1修改位示图：map[i,j]=08.2文件存储空间的管理成组链接法空闲块成组链接，建立空闲块专用栈，空闲块分配时按组进行，一组的空闲块分配完了，再使用下一组；回收时次序相反，入栈一组空闲块后，够成一组。这种方法兼备了空闲空间表法和空闲块链接法的优点UNIX系统使用这种空闲块管理策略8.2文件存储空间的管理分配与回收s-nfree空闲块数;s_free[100]空闲块块号;s_flock锁位8.2文件存储空间的管理分配过程的例子设当前空闲盘块号栈中还有两块未分配现有一文件申请3块299#300#400#7900#…空闲盘块号栈…s_free203001299…99…399#7899#7999#301#7801#7901#……………1分配0分配10007999…7901…100500499…401…100400399…301…300#400#7900#…空闲盘块号栈…s_free10004001399……99301…399#7899#7999#301#7801#7901#……………分配99分配10007999…7901…100500499…401…100400399…301…8.2文件存储空间的管理回收过程的例子设当前空闲盘块号栈中有99个空闲块现有一文件归还2块（500#，310#）299#460#700#506#…空闲盘块号栈…s_free9904601299……9835099…899#7899#7999#601#7801#7901#……500100350#回收500#10007999…7901…1005067899…7801…100700899…601…299#460#700#506#…空闲盘块号栈…s_free9904601299……9835099…899#7899#7999#601#7801#7901#……500100350#回收500#回收310#310#1310100460299…500…10007999…7901…1005067899…7801…100700899…601…