设为首页 加入收藏

TOP

空闲空间管理和文件系统结构的优化策略(一)
2023-09-09 10:25:26 】 浏览:82
Tags:空闲空 管理和 文件系

空闲空间的管理

关于空闲空间的管理,前面提到的是已被占用的数据块的组织和管理。接下来要解决的问题是,当我要保存一个数据块时,应该将其放在硬盘的哪个位置。难道需要扫描所有的块,随意找个空的地方放吗?

然而,这种方式效率太低了。因此,我们需要引入一种管理磁盘空闲空间的机制。下面介绍几种常见的方法:

  • 空闲表法:使用一个表格来维护磁盘空闲块的信息。表格中的每个条目表示一个空闲块,包含块的起始地址和长度。当需要保存数据块时,可以在表格中找到合适的空闲块,并将其标记为已占用。
  • 空闲链表法:使用链表来维护磁盘空闲块的信息。每个链表节点表示一个空闲块,包含块的起始地址和长度,以及指向下一个空闲块的指针。通过遍历链表,可以找到合适的空闲块,并将其标记为已占用。
  • 位图法:使用一个位图来表示磁盘的空闲块信息。位图中的每个位表示一个块的状态,1表示已占用,0表示空闲。通过对位图进行操作,可以快速找到空闲块并标记为已占用。

你可以想象一下如果给你一张MySQL表,在已经分配好所有id主键后,你可能会觉得一直顺序写入就可以了,但是一旦中间有删除的操作,这就会存在有空闲的id行没用上,你去保存有空闲的数据行可以怎么做?

空闲表法

它通过建立一张表来记录所有的空闲区域,表中包括空闲区的第一个块号和该空闲区的块个数。需要注意的是,这种方法适用于连续分配。如图所示:

image

当系统需要分配磁盘空间时,它会顺序扫描空闲表的内容,直到找到一个合适的空闲区域为止。而当用户撤销一个文件时,系统会回收文件的空间。此时,系统会再次顺序扫描空闲表,寻找一个空闲表条目,并将释放空间的第一个物理块号及其占用的块数填入该条目中。

然而,空闲表法在空闲区较少的情况下才能发挥较好的效果。如果存储空间中存在大量小的空闲区域,空闲表会变得非常庞大,从而降低查询效率。此外,这种分配技术适用于建立连续文件。

空闲链表法

除了空闲表法之外,我们还可以使用空闲链表法来管理磁盘的空闲空间。在空闲链表法中,我们使用链表的方式来组织和管理空闲块。如下图:

image

每个空闲块都包含一个指针,指向下一个空闲块。当需要创建文件时,我们可以从链表的头部开始依次获取所需的块数。相反地,当需要回收空间时,我们可以将这些空闲块依次接入链表的头部。

使用空闲链表法的好处是它的实现相对简单,只需要在主存中保存一个指针,指向链表的头部即可。然而,空闲链表法也有一些局限性。由于无法进行随机访问,它的工作效率较低。每当在链表上增加或移动空闲块时,都需要进行大量的输入/输出操作。此外,空闲链表法也会消耗一定的存储空间,因为每个数据块都需要包含一个指针。

需要注意的是,空闲链表法和空闲表法都不适合用于大型文件系统,因为它们会导致空闲表或空闲链表变得过大。在大型文件系统中,我们需要考虑更高效的管理方法来提高性能和减少空间消耗。

位图法

除了空闲表法和空闲链表法,我们还可以使用位图法来管理磁盘的空闲空间。位图法利用二进制位来表示磁盘中每个块的使用情况,每个块都有一个对应的二进制位。

当二进制位的值为0时,表示对应的盘块是空闲的;当二进制位的值为1时,表示对应的盘块已经被分配。位图的形式如下所示:

11111111111111100011101101111...

在 Linux 文件系统就采用了位图的方式来管理空闲空间,位图不仅用于管理数据空闲块,还用于管理inode(索引节点)空闲块。因为inode也是存储在磁盘上的,所以需要对其进行管理。

位图法的优点是实现简单,存储空间占用小。通过位运算可以快速判断一个盘块是否空闲,以及找到一个空闲盘块。由于位图法不需要额外的数据结构来记录空闲块的信息,因此在大型文件系统中,位图法往往是一种较为高效的管理方法。

文件系统的结构

文件系统的结构主要包括普通文件和目录两类。普通文件是存储用户数据的基本单位,而目录则用于组织和管理文件。下面我们来详细了解它们的存储方式。

文件的存储

在Linux文件系统中,文件的存储是通过位图的方式进行管理的。当用户创建一个新文件时,Linux内核会根据inode的位图来找到空闲可用的inode,并进行分配。当需要存储数据时,它会通过块的位图来找到空闲的数据块,并进行分配。然而,经过仔细计算后,我们会发现存在一些问题。

数据块的位图是存储在磁盘块中的,假设每个块的大小为4K,那么一个块能够表示的位数就是4 × 1024 × 8 = 215个块。由于每个数据块的大小为4K,那么最大可以表示的空间就是215 × 4 × 1024 = 2^27个字节,即128M。

换句话说,按照上述结构,如果使用"一个块的位图 + 一系列的块"以及"一个块的inode位图 + 一系列的inode结构"来表示空间,最大能够表示的空间也只有128M。然而,现在很多文件的大小都超过了这个限制。

因此,在Linux文件系统中,引入了块组的概念来解决这个问题。每个块组包含一个块的位图和一系列的块,以及一个inode的位图和一系列的inode结构。通过增加块组的数量,文件系统就能够表示更大的文件。这样,用户就可以利用多个块组来存储大文件,从而突破了128M的限制。

image

最前面的第一个块是引导块,在系统启动时用于启用引导,接着后面就是一个一个连续的块组了,块组的内容如下:

  • 超级块,它包含了文件系统的重要信息,比如inode总个数、块总个数、每个块组的inode个数、每个块组的块个数等等。超级块对于文件系统的正常运行起着至关重要的作用。
  • 块组描述符,它包含了文件系统中各个块组的状态信息,比如块组中空闲块和inode的数目等。每个块组都包含了文件系统中所有块组的组描述符信息,这样可以方便地管理和维护整个文件系统。
  • 数据位图和inode位图,它们用于表示对应的数据块或inode是空闲的,还是被使用中。数据位图和inode位图的使用可以有效地管理文件系统的空闲空间和资源。
  • inode列表,它包含了块组中所有的inode。inode用于保存文件系统中与各个文件和目录相关的所有元数据,比如文件的大小、权限、所属用户等。
  • 数据块,它包含了文件的有用数据。

你可能会发现每个块组里有很多重复的信息,比如超级块和块组描述符表,这两个都是全局信息,而且非常重要。这么做有两个原因:

  • 一是如果系统崩溃破坏了超级块或块组描述符,有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本,该信息是可能恢复的。
  • 二是通过使文件和管理数据尽可能接近,可以减少磁头寻道和旋转,从而提高文件系统的性能。不过,Ext2的后续版本采用了稀疏技术。稀疏技术的做法是,超级块和块组描述符表不再存储到文件系统的每个块组中,而是只写入到块组0、块组1和其他ID可以表示为3、5、7的幂的块组中。这样可以进一步减少重复的信息,提高文件系统的存储效率和性能。

目录的存储

在前面我们已经了解了普通文件的存储方式,但是目录作为一个特殊文件,它的存储方式又是怎样的呢?

基于 Linux 一切皆文件的设计思想,目录实际上也是一个文件,你甚至可以使用vim打开它。目录文件也有一个inode,其中也包含指向其他块的指针。

然而,与普通文件不同的是,普通文件的块中保存的是文件的实际数据,而目

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇zabbix 自动发现 下一篇拯救“消失的她”——双系统grub..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目