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

1、第八章,文件管理,8.1,外存的组织方式,8.2,文件存储空间的管理,8.1,外存的组织方式,文件的物理结构,?,又称为文件的存储结构，是指文件在外存上的存,储组织形式，与存储介质的特性有关,?,类型,?,?,?,顺序文件结构,链接文件结构,索引文件结构,8.1,外存的组织方式,外存组织方式,?,连续组织方式（连续分配）,?,链接组织方式（链接分配）,?,索引组织方式（索引分配）,8.1,外存的组织方式,连续组织方式,?,为每个文件分配一组连续的盘块,?,文件物理地址：文件所占的第一个盘块号和盘块数,?,优点,?,实现简单,?,顺序访问容易,?,顺序访问速度快,?,缺点,?,创建时就要知道文件

2、的最大长度,?,存在磁盘碎片（存储压缩技术）,?,在,CD-ROM,上被广泛使用,count,0,4,8,12,16,20,1,5,9,13,17,21,25,29,2,6,10,14,18,22,26,30,f,3,7,11,文件目录,文件名,始址,块数,tr,mail,19,23,27,31,15,list,28,24,count 0 2,tr 14 3,mail 19 6,list 28 4,f 6 2,8.1,外存的组织方式,链接组织方式,?,一个文件的信息存放在若干不连续的盘块中，各,块之间通过指针连接,?,优点,?,提高了磁盘空间利用率，不存在外部碎片问题,?,有利于文件插入和删除

3、,?,有利于文件动态增长,?,链接方式分为,?,隐式链接,?,显式链接,8.1,外存的组织方式,?,隐式链接,?,?,?,文件物理地址：指向第一个盘块和最后一个盘块的指针,其余盘块靠盘块自身所含的指针相连,缺点,?,?,?,?,存取速度慢，不适于随机存取,可靠性差（如指针出错）,更多的寻道次数和寻道时间,链接指针占用一定的空间,将几个盘块组成一个簇，以簇为单位分配盘块，文,件的每一个元素也以簇为单位,?,改进,?,文件目录,文件名,0,4,1,10,2,5,6,3,7,始址,末址,jeep 9 25,8,12,9,16,10,25,11,13,14,18,15,19,16,1,17,20,24

4、,28,21,22,23,27,31,25,-1,26,29,30,8.1,外存的组织方式,?,显式链接,?,文件分配表,FAT,（,File Allocation Table,）,?,?,整个磁盘一张，存于内存,其序号为盘块号，内容为链接指针,?,?,?,文件物理地址：链首指针所对应的盘块号,其余指针存放于,FAT,中,优点,?,减少访盘次数，提高检索速度，随机存取容易,FAT,占据大量内存空间,?,缺点,?,8.1,外存的组织方式,在内存中使用文件分配表的链表结构,8.1,外存的组织方式,索引组织方式,?,单级索引组织方式,?,一个文件的信息存放在若干不连续的物理块中，系统为,该文件建立一

5、个专用数据结构,-,索引表，并将其所占块,的盘块号存放在该索引表中,?,一个索引表就是磁盘块地址数组，其中第,i,个条目指向,文件的第,i,块,?,文件物理地址：索引表所在盘块号,8.1,外存的组织方式,?,优点,?,既能顺序存取，又能随机存取,?,满足了文件动态增长、插入删除的要求,?,能充分利用外存空间,?,缺点,?,较多的寻道次数和寻道时间,?,索引表本身带来了系统开销如：内外存空间，存取,时间,文件目录,文件名,0,4,1,5,2,6,3,7,索引表地址,Jeep 19,9,17,1,10,25,-1,-1,-1,8,9,10,14,18,11,15,19,12,13,16,17,19

6、,20,21,22,23,24,25,28,29,26,30,27,31,8.1,外存的组织方式,?,多级索引组织方式,?,将一个大文件的所有索引表（二级索引）的地址放在,另一个索引表（一级索引）中,第二级索引,主索引,360,740,360,105,106,254,磁盘空间,0,1,2,105,106,740,356,357,1125,254,1125,985,356,357,985,8.1,外存的组织方式,?,增量式索引组织方式,?,?,UNIX,文件系统采用,每个文件的物理地址为,13,个地址项,?,?,?,?,最前面,10,项存放文件所占物理块号（直接寻址）,第,11,项存放一级索引地

7、址,第,12,项存放二级索引地址,第,13,项存放三级索引地址,（间接寻址）,8.1,外存的组织方式,返回,8.2,空闲表法,文件存储空间的管理,?,系统设一张空闲表,?,每组连续的空闲盘块占一个表项（序号，第一空,闲盘块号，空闲盘块数）,?,属连续分配：分配和回收与内存管理的动态分区,分配方法类似,?,分配速度快，可减少访盘频率，用于小文件的分,配和对换空间的管理,8.2,序号,文件存储空间的管理,第一空闲盘块号,空闲盘块数,1,2,3,2,9,15,4,3,5,4,-,空闲表,-,8.2,文件存储空间的管理,空闲链表法,?,把所有空闲盘块链成一个空闲链表,?,根据构成链的基本元素不同，可有

8、两种链表形式,?,空闲盘块链：基本元素为盘块,?,?,优点：分配回收过程简单,缺点：空闲盘块链可能很长,?,空闲盘区链：基本元素为盘区（可包含若干个连续的空,闲盘块）,?,?,优点：链比较短,缺点：分配回收与动态分区类似，较复杂,8.2,位示图法,?,位示图,?,文件存储空间的管理,所有盘块都有一个二进制位与之对应，由所有盘块所对,应的位组成的集合，称为位示图。,二进制位,1,，表示对应的盘块已分配,0,，表示对应的盘块空闲,var map,：,array1m,，,1n of bit,?,?,?,优点：占用空间少，可保存在内存；描述能力强，适合,各种物理结构,8.2,1,2,3,4,?,16,

9、1,1,0,1,2,1,0,1,3,0,0,1,文件存储空间的管理,4,0,1,0,5,0,1,0,6,1,1,0,7,1,1,1,8,1,1,1,9,0,1,1,10,11,12,13,14,15,16,0,1,0,0,1,1,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,位示图,8.2,文件存储空间的管理,?,盘块的分配,?,?,顺序扫描位示图，查找为,0,的一个或一组二进制位,返回对应盘块号,?,假设找到的二进制位位于第,i,行，第,j,列，对应的盘块,号为：,b=n(i-1)+j,（,n,为每行的位数）,?,修改位示图：,mapi,j=1,将回收盘块号,b,转换成行号,i

10、,和列号,j,?,?,盘块的回收,?,i=(b-1)DIV n + 1,；,j=(b-1) MOD n + 1,?,修改位示图,：,mapi,j=0,8.2,文件存储空间的管理,成组链接法,?,空闲块成组链接，建立空闲块专用栈，空闲块分,配时按组进行，一组的空闲块分配完了，再使用,下一组；回收时次序相反，入栈一组空闲块后，,够成一组。,?,这种方法兼备了空闲空间表法和空闲块链接法的,优点,?,UNIX,系统使用这种空闲块管理策略,8.2,文件存储空间的管理,?,分配与回收,s-nfree,空闲块数,;,s_free100,空闲块块号,;,s_flock,锁位,8.2,文件存储空间的管理,?,分

11、配过程的例子,?,?,设当前空闲盘块号栈中还有两块未分配,现有一文件申请,3,块,100,100,400,500,空闲盘,块号栈,399,499,301,401,s_free,1,0,2,分配,0,300,300#,400#,1,299,分配,299#,399#,99,301#,100,0,7999,7901,7900#,7899#,7999#,7801#,7901#,100,100,400,500,空闲盘,块号栈,399,499,301,401,s_free,100,99,分配,0,400,300#,400#,1,399,399#,99,301,分配,301#,100,0,7999,7901,7900#,7899#,7999#,7801#,7901#,8.2,文件存储空间的管理,?,回收过程的例子,?,?,设当前空闲盘块号栈中有,99,个空闲块,现有一文件归还,2,块（,500#,，,310#,）,100,空闲盘,块号栈,100,100,700,899,506,7899,0,7999,601,460#,7801,700#,899#,7901,506#,7899#,7999#,s_free,0,1,100,99,460,299,98,99,350,500,299#,350#,回收,500#,601#,7801#,7901#,100,回收,空闲盘,块