文件实现
标签: 操作系统
学习人数: 10588

1. 文件分配方式

文件的物理结构是指一个文件在外存上的存储组织形式,与外存分配方式有关。是指如何为文件分配磁盘块。常用的磁盘空间分配方 法有三种:连续分配、链接分配和索引分配。有的系统对三种方法都支持,但是更普遍的是一个系统只提供一种方法的支持。

①连续分配。

连续分配是最简单的磁盘空间分配策略,连续分配方法要求每个文件在磁盘上占有一组连续的磁盘区域。磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。用户必须在分配前说明待创建文件所需的存储空间大小,然后系统查找空闲区的管理表格,查看是否有足够大的空闲区供其使用。如果有,就给文件分配所需的存储空间;如果没有,该文件就不能建立,用户进程必须等待。

连续分配

连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快。缺点在于,文件长度不宜动态增加,因为一个文件末尾后的盘块可能已经分配给其他文件,一旦需要增加, 就需要大量移动盘块。此外,反复增删文件后会产生外部碎片(与内存管理分配方式中的碎片相似),并且很难确定一个文件需要的空间大小,因而只适用于长度固定的文件。

②链接分配

链接分配是釆取离散分配的方式,消除了外部碎片,故而显著地提高了 磁盘空间的利用率;又因为是根据文件的当前需求,为它分配必需的盘块,当文件动态增长时,可以动态地再为它分配盘块,故而无需事先知道文件的大小。此外,对文件的增、删、改也非常方便。链接分配又可以分为隐式链接和显式链接两种形式。

隐式链接分配的缺点在于无法直接访问盘块,只能通过指针顺序访问文件,以及盘块指针消耗了一定的存储空间。隐式链接分配的稳定性也是一个问题,系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏,会导致文件数据的丢失。

隐式链接

显示链接

③索引分配

链接分配解决了连续分配的外部碎片和文件大小管理的问题。但是,链 接分配不能有效支持直接访问(FAT除外),需要按照链接指针依次进行查找,这样查找十分缓慢。索引分配解决了这个问题,它把每个文件的所有的盘块号都集中放在一起构成索引块(表)。

索引分配

索引分配方式不仅支持直接访问,而且不会产生外部碎片,文件长度受限制的问题也得到了解决。每个文件都有其索引块,这是一个磁盘块地址的数组。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第i块,通过索引块的第i个条目的指针来查找和读入所需的块。

索引分配支持直接访问,且没有外部碎片问题。其缺点是由于索引块的分配,增加了系统存储空间的开销。索引块的大小是一个重要的问题,每个文件必须有一个索引块,因此索引块应尽可能小,但索引块太小就无法支持大文件。可以釆用以下机制来处理这个问题。

当文件很大时,文件的索引表会很大。如果索引表的大小超过了一个物理块,可以将索引表本身作为一个文件,再为其建立一个“索引表”,这个“索引表”作为文件索引的索引,从而构成了二级索引。依次类推,可逐级建立索引,进而构成多级索引。

混合索引分配

直接地址:为了提高文件的检索速度,在索引结点中可设置10个直接地址项。这里每项中存放的是该文件所在盘块的盘块号,当文件不大于40KB时,便可以直接从索引结点中读出该文件的全部盘块号(10×4KB=40KB)。

一次间接地址:对于较大的文件,索引结点提供了一次间接地址,其实质就是一级索引分配方式。在一次间接地址中可以存放1K个盘块号,因此允许文件长达4MB (1K×4KB=4MB)。若既采用直接地址,又采用一次间接地址,允许文件长达4MB+40KB。

二次间接地址:当文件很大时,系统应采用二级间接地址。该方式实质上是两级索引分配方式,此时系统是在二次间接地址块中记入所有一次间接地址块的盘号。在采用二级间接地址方式时,文件最大长度可达到4GB (1K×1K×4KB=4GB)。如果同时采用直接地址、一次间接地址和二次间接地址,允许文件长达4GB+4MB+40KB。

这种思想可以推广到三级间接地址等。当采用三级间接地址时,所允许的最大文件长度为 4TB+4GB+4MB+40KB。

文件三种分配方式的比较

 

2. 文件存储空间管理

文件存储设备分成许多大小相同的物理块,并以块为单位交换信息,因此,文件存储设备的管理实质上是对空闲块的组织和管理,它包括空闲块的组织、 分配与回收等问题。下面介绍几种常用的空闲存储空间管理方法。

①空闲表法

空闲表法属于连续分配方式,它与内存的动态分配方式雷同,它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表,每个空闲区对应于一个空闲表项,其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列,形成空闲盘块表。

空闲盘区的分配与内存的动态分配类似,同样是釆用首次适应算法、循环首次适应算法等。当请求的块数正好等于某个目录表目中的空闲块数时,就把这些块全部分配给该文件并把该表目标记为空。若该项中的块数多于请求的块数,则把多余的块号留在表中,并修改该表目中的各项。同样,在释放过程中,若被释放的物理块号与某一目录项中的物理块号相邻,则还要进行空闲文件的合并。

仅当文件存储空间中只有少量空闲文件时,这种方法才有较好的效果。若存储空间中有大量的小空闲文件,则空闲文件目录将变得很大,其效率将大为降低。这种管理方法仅适用于连续文件。

空闲盘块表

②空闲链表法

将所有空闲盘区拉成一条空闲链,根据构成链所用的基本元素不同,可把链表分成两种形式:空闲盘块链和空闲盘区链。

1)空闲盘块链:这是将磁盘上的所有空闲空间以盘块为单位拉成一条链,其中的每一个盘块都有指向后继盘块的指针。

2)空闲盘区链:这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外,还应有能指明本盘区大小(盘块数)的信息。

分配盘区的方法与内存的动态分区分配类似,通常采用首次适应算法。在回收盘区时,同样也要将回收区与相邻接的空闲盘区合并。

③位示图法

位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有的盘块都有一个二进制位与之对应。当其值为“0”时,表示对应的盘块空闲;当其值为“1”时,表示 对应的盘块已分配。由所有盘块所对应的位构成一个集合,称为位示图。

位示图法示意图

当请求分配存储空间时,系统顺序扫描位示图并按需要从中找出一组值为0 的二进制位,再经过简单的换算就可以得到相应的盘块号,然后将这些位变为1。当回收存储空间时,只需要将位示图的相应位清0。

④成组链接法

空闲表法和空闲链表法都不适合用于大型文件系统,因为这会使空闲表或空闲链表太大。在UNIX系统中釆用的是成组链接法,这种方法结合了空闲表和空闲链表两种方法,克服了表太大的缺点。其大致的思想是:把顺序的n个空闲扇区地址保存在第一个空闲扇区内, 其后一个空闲扇区内则保存另一顺序空闲扇区的地址,如此继续,直至所有空闲扇区均予以链接。系统只需要保存一个指向第一个空闲扇区的指针。假设磁盘最初全为空闲扇区。通过这种方式可以迅速找到大批空闲块地址。

成组链接法示意图

 

空闲盘块的分配与回收

当系统要为文件分配空闲盘块时,先查找第一组的盘块数,若不止一块,则将超级块中的空闲盘块数减1 ,将栈顶的盘块分配出去。若第一组只剩下一块(是放置下一组的盘块数和盘块号的那个块,不是空闲块)且栈顶的盘块号不是结束标记0(说明这一组不是最后一组),则先将该块的内容读到超级块中(下一组成了第一组,所以下一组的盘块数和盘块号需要放到超级块中),然后再将该块分配出去(该块中的信息不再有用,这一块成了空闲块);若栈顶的盘块号是结束标记0 ,则表示磁盘已无空闲盘块,分配不成功。

当系统回收空闲块时,若第一组不满100块,则只要在超级块的空闲盘块的栈顶放入该空闲盘块的块号,并将其中的空闲盘块数加1 即可;若第一组已经有 100块了,则先将第一组中的盘块数和盘块号写入到该空闲盘块中,然后将“盘块数=1及栈顶块号=该空闲盘块块号”写入到超级块中(该空闲盘块成了新的第一组,原本的第一组成了第二组)。

 



课后作业

课后习题

 

1. 【2009统考真题】下列文件物理结构中,适合随机访问且易于文件扩展的是( )。

A. 连续结构

B. 索引结构

C. 链式结构且磁盘块定长

D. 链式结构且磁盘块变长

【答案】B

【解析】文件的物理结构包括连续、链式、索引三种,其中链式结构不能实现随机访问,连续结构的文件不易于扩展。因此随机访问且易于扩展是索引结构的特性。

 

2. 【2010统考真题】设文件索引结点中有7 个地址项,其中4 个地址项是直接地址索引,2个地址项是一级间接地址索引,1个地址项是二级间接地址索引,每个地址项大小为4B,若磁盘索引块和磁盘数据块大小均为256B,则可表示的单个文件最大长度是( )。

A. 33KB                       B. 519KB .

C. 1057KB                     D. 16516KB

【答案】C

【解析】每个磁盘索引块和磁盘数据块大小均为256B,每个磁盘索引块有256/4 = 64个地址项。因此,4个直接地址索引指向的数据块大小为4×256B; 2个一级间接索引包含的直接地址索引数为2×(256/4),即其指向的数据块大小为2×(256/4)×256B。1个二级间接索引所包含的直接地址索引数为(256/4)×(256/4),即其所指向的数据块大小为(256/4)×(256/4)×256B。因此,7个地址项所指向的数据块总大小为 4×256 + 2×(256/4)×256 + (256/4)×(256/4)×256 = 1082368B = 1057KB。

 

3. 【2013统考真题】为支持CD-ROM中视频文件的快速随机播放,播放性能最好的文件数据块组织方式是( )。

A .连续结构                   B .链式结构

C .直接索引结构               D .多级索引结构

【答案】A

【解析】为了实现快速随机播放,要保证最短的查询时间,即不能选取链表和索引结构,因此连续结构最优。

 

4. 【2013统考真题】若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则 下列选项中,与单个文件长度无关的因素是(  )。

A .索引结点的总数                        B .间接地址索引的级数

C .地址项的个数                          D .文件块大小

【答案】A

【解析】四个选项中,只有A 选项是与单个文件长度无关的。

 

5. 【2015统考真题】在文件的索引结点中存放直接索引指针10个,一级和二级索引指针各 1个。磁盘块大小为1KB,每个索引指针占4B。若某文件的索引结点已在内存中,则把该文件偏移量(按字节编址)为 1234和 307400处所在的磁盘块读入内存,需访问的磁盘块个数分别是( )。

A. 1, 2                              B. 1, 3

C. 2, 3                              D. 2, 4

【答案】B

【解析】10个直接索引指针指向的数据块大小为10xlKB = 10KB。每个索引指针占4 B ,则每个磁盘块可存放1KB/4B = 256个索引指针,一级索引指针指向的数据块大小为256×1KB = 256KB,二 级索引指针指向的数据块大小为256×256×1KB = KB = 64MB。

按字节编址,偏移量为1234时,因1234B<10KB,由直接索引指针可得到其所在的磁盘块地址。文件的索引结点已在内存中,因此地址可直接得到,因此仅需1次访盘即可。

偏移量为307400时,因 10KB + 256KB < 307400B < 64M B,可知该偏移量的内容在二级索引指针所指向的某个磁盘块中,索引结点已在内存中,因此先访盘2次得到文件所在的磁盘块地址,再访盘1次即可读出内容,共需3次访盘。

 

6. 【2015统考真题】文件系统用位图法表示磁盘空间的分配情况,位图存于磁盘的32~127号块中,每个盘块占1024B,盘块和块内字节均从0 开始编号。假设要释放的盘块号为409612,则位图中要修改的位所在的盘块号和块内字节序号分别是( )。

A. 81, 1                               B. 81, 2

C. 82, 1                                D. 82, 2

【答案】C

【解析】盘块号= 起始块号+⌊盘块号/(1024×8) ⌋ = 32 + ⌊409612/(1024×8) ⌋ = 32 + 50 = 82 ,这里问的是块内字节号而不是位号,因此还需除以8 (1B = 8位 ),块内字节号=⌊ (盘块号% (1024×8))/8 ⌋= 1。

 

7. 【2019统考真题】下列选项中,可用于文件系统管理空闲磁盘块的数据结构是( )。

I . 位图          Ⅱ.索引结点        Ⅲ.空闲磁盘块链        Ⅳ.文件分配表(FAT)

A . 仅 I、II            B . 仅 I、Ⅲ、IV       C . 仅 I、III        D . 仅 II、Ⅲ、IV

【答案】B

【解析】传统文件系统管理空闲磁盘的方法包括空闲表法、空闲链表法、位示图法和成组链接法,I、Ⅲ正确。文件分配表(FAT)的表项与物理磁盘块一一对应,并且可以用一个特殊的数字-1表示文件的最后一块,用-2表示这个磁盘块是空闲的(当然,规定用-3,-4 来表示也是可行的)。因此文件分配表(FAT)不仅记录了文件中各个块的先后链接关系,同时还标记了空闲的磁盘块,操作系统可以通过FAT对文件存储空间进行管理,IV 正确。索引结点是操作系统为了实现文件名与文件信息分开而设计的数据结构,存储了文件描述信息,索引结点属于文件目录管理部分的内容?Ⅱ错误。

 

8. 【2011统考真题】某文件系统为一级目录结构,文件的数据一次性写入磁盘,已写入的文件不可修改,但可多次创建新文件。请回答如下问题。

1) 在连续、链式、索引三种文件的数据块组织方式中,哪种更合适?说明理由。为定位文件数据块,需要在FCB中设计哪些相关描述字段?

2) 为快速找到文件,对于FCB,是集中存储好,还是与对应的文件数据块连续存储好?说明理由。

【解析】

1) 在磁盘中连续存放(采取连续结构),磁盘寻道时间更短,文件随机访问效率更高;在FCB中加入的字段为〈起始块号,块数〉或<起始块号,结束块号〉。

2) 将所有的FCB集中存放,文件数据集中存放。这样在随机查找文件名时,只需访问FCB对应的块,可减少磁头移动和磁盘I/O访问次数。

 

9. 【2016统考真题】某磁盘文件系统使用链接分配方式组织文件,簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号,其他簇号存放在文件分配表FAT 中。

1) 假定目录树如下图所示,各文件占用的簇号及顺序如下表所示, 其中dir,dir1是目录, file1, file2是用户文件。请给出所有目录文件的内容。

2) 若 FAT的每个表项仅存放簇号,占2B ,则 FAT的最大长度为多少字节?该文件系统支持的文件长度最大是多少?

3) 系统通过目录文件和FAT实现对文件的按名存取,说明filel的 106, 108两个簇号分别存放在FAT的哪个表项中。

4 ) 假设仅FAT和dir目录文件已读入内存,若需将文件dir/dir1/file1的第5000个字节读入内存,则要访问哪几个簇?

【解析】

1 )两个目录文件dir和dir1的内容如下表所示。

2) FAT的最大长度为216×2B = 128KB,文件的最大长度是216×4KB = 256MB。

3) file1的簇号106存放在FAT的 100号表项中,簇号108存放在FAT的 106号表项中。

4) 需要访问目录文件dirl所在的48号簇及文件file 1 的 106号簇。

 

10. 【2012统考真题】某文件系统空间的最大容量为4TB (1TB = 240B) , 以磁盘块为基本分配单位。磁盘块大小为IKB。文件控制块(FCB)包含一个512B的索引表区。请回 答下列问题:

1) 假设索引表区仅采用直接索引结构,索引表区存放文件占用的磁盘块号,索引表项中块号最少占多少字节?可支持的单个文件的最大长度是多少字节?

2) 假设索引表区采用如下结构:第0~7字节采用<起始块号,块数〉格式表示文件创建时预分配的连续存储空间。其中起始块号占6 B ,块数占2 B ,剩余504B采用直接索引结构,一个索引项占6B,则可支持的单个文件的最大长度是多少字节?为使单个文件的长度达到最大,请指出起始块号和块数分别所占字节数的合理值并说明理由。

【解析】

1) 文件系统中所能容纳的磁盘块总数为4TB/1KB = 232。要完全表示所有磁盘块,索引项中的块号最少要占32/8 = 4B。而索引表区仅采用直接索引结构,因此512B的索引表区能容纳512B/4B = 128个索引项。每个索引项对应一个磁盘块,所以该系统可支持的单个文件最大长度是128×1KB = 128KB。

2) 这里考查的分配方式不同于我们熟悉的三种经典分配方式,但题目中给出了详细的解释。所求的单个文件最大长度一共包含两部分:预分配的连续空间和直接索引区。连续区块数占2 B ,共可表示216个磁盘块,即226B。直接索引区共504B/6B =84个索引项。所以该系统可支持的单个文件最大长度是226B+84KB.为了使单个文件的长度达到最大,应使连续区的块数字段表示的空间大小尽可能接近系统最大容量4TB。分别设起始块号和块数占4 B ,这样起始块号可以寻址的范围是232个磁盘块,共4TB,即整个系统空间。同样,块数字段可以表示最多232个磁盘块,共4TB。

 

11. 【2014统考真题】文件F 由200条记录组成,记录从1开始编号。用户打开文件后,欲将内存中的一条记录插入文件F中,作为其第30条记录。请回答下列问题,并说明理由。

1) 若文件系统采用连续分配方式,每个磁盘块存放一条记录,文件F存储区域前后均

有足够的空闲磁盘空间,则完成上述插入操作最少需要访问多少次磁盘块? F 的文件

控制块内容会发生哪些改变?

2) 若文件系统采用链接分配方式,每个磁盘块存放一条记录和一个链接指针,则完成

上述插入操作需要访问多少次磁盘块?若每个存储块大小为1KB,其中4B存放链接

指针,则该文件系统支持的文件最大长度是多少?

【解析】

1) 系统采用顺序分配方式时,插入记录需要移动其他的记录块,整个文件共有200条记录,要插入新记录作为第30条,而存储区前后均有足够的磁盘空间,且要求最少的访问存储块数,则要把文件前29条记录前移,若算访盘次数,移动一条记录读出和存回磁盘各是一次访盘,29条记录共访盘58次,存回第30条记录访盘1次,共访盘59次。

F 的文件控制区的起始块号和文件长度的内容会因此改变。

2) 文件系统采用链接分配方式时,插入记录并不用移动其他记录,只需找到相应的记录,修改指针即可。插入的记录为其第30条记录,因此需要找到文件系统的第29块,一共需要访盘29次,然后把第29块的下块地址部分赋给新块,把新块存回磁盘会访盘1次,然后修改内存中第29块的下块地址字段,再存回磁盘,一共访盘31次。

4B共 32位,可以寻址232 = 4GB块存储块,每块的大小为1KB,即1024B,其中下块地址部分占4 B,数据部分占1020B,因此该系统的文件最大长度是4GB×l020B = 4080GB。

 

12. 【2018统考真题】某文件系统采用索引结点存放文件的属性和地址信息,簇大小为4KB。每个文件索引结点占64B ,有 11个地址项,其中直接地址项8 个,一级、二级和三级间接地址项各1个,每个地址项长度为4B。请回答下列问题:

1) 该文件系统能支持的最大文件长度是多少? (给出计算表达式即可)

2) 文件系统用1M (1M = 220)个簇存放文件索引结点,用512M个簇存放文件数据。若一个图像文件的大小为5600B,则该文件系统最多能存放多少个这样的图像文件?

3) 若文件的大小为6KB,文件F2的大小为40KB,则该文系统获取F1和F2最后一个簇的簇号需要的时间是否相同?为什么?

【解析】

1) 簇大小为4KB ,每个地址项长度为4 B ,因此每簇有4KB/4B = 1024个地址项。最大文件的物理块数可达8 + 1×1024 + 1×10242 + 1×10243每个物理块(簇)大小为4KB ,因此 最大文件长度为(8 + 1×1024 + 1×10242 + 1×10243)×4KB = 32KB + 4MB + 4GB + 4TB。

2) 文件索引结点总个数为1Mx4KB/64B = 64M, 5600B的文件占2 个簇,512M个簇可存放 的文件总个数为512M/2 = 256M。可表示的文件总个数受限于文件索引结点总个数,因此能存储64M个大小为5600B的图像文件

3) 文件F1的大小为6KB <4KB×8 = 32KB,因此获取文件F l的最后一个簇的簇号只需要访问索引结点的直接地址项。文件F2大小为40KB, 4KB×8<40KB <4KB×8 + 4KB×1024,因此获取F2的最后一个簇的簇号还需要读一级索引表。综上,需要的时间不相同。

 


登录后发布评论

暂无评论,来抢沙发