操作系统【十四】

八、磁盘存储器的管理

1、外存分配方式

磁盘具有可随机访问的特性,故当利用磁盘存放文件时,具有很大的灵活性。在为文件分配外存空间时所要考虑的主要问题是:怎样才能有效的利用外存空间, 如何提高对文件的访问速度, 提高磁盘系统的可靠性。

文件的物理结构和外存组织方法有关。在采用不同的分配方式时将形成不同的文件物理结构。

  • 连续分配方式对应顺序式文件结构;
  • 链接分配方式形成链接式文件结构;
  • 索引分配方式形成索引式文件结构。

(1)连续分配

连续分配要求为每个文件分配一组相邻接的盘块,一组盘块地址定义了磁盘上的一段线性地址。采用连续分配方式时,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中,这样所形成的文件结构称为顺序文件结构,这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。下图为连续分配方式(假设记录与盘块一样大)。

如同动态分配分区分配一样,随着文件建立时空间的分配和文件删除时的空间回收,将使磁盘空间被分割成许多小块,这些小块的连续去已难以存储文件,此即外存的碎片,同样,可以使用紧凑的方法,将盘上所有的文件紧靠在一起,把所有的碎片拼成一大片连续的存储空间。

连续分配的优点如下

① 顺序访问容易,访问一个占有连续空间的文件非常容易。

② 顺序访问速度快,因为由连续分配所装入的文件,其所占用的盘块可能是位于一条或几条相邻的磁道上,这是,磁头移动距离最少,这种对文件访问的速度使几种存储空间分配方式中最高的一种。

连续分配的缺点如下

① 要求又连续的存储空间,要为每个文件分配一段连续的存储空间,这样,便会产生许多外部碎片,严重地降低了外存空间利用率,定期紧凑会花费大量的机器时间。

② 必须实现知道文件的长度,事先知道文件的长度,然后根据其大小,在存储空间中找出一块其大小足够的存储区,将文件装入,对于动态增长的文件非常低效。

(2)链接分配

如果将一个逻辑文件存储到外存上,并不要求为整个文件分配一块连续的空间,而是可以将文件装到多个离散的盘块中,这样就可以消除连续分配的缺点。采用链接分配方式时,可通过在每个盘块上的链接指针,将同属于一个文件的多个离散盘块链接成一个链表,把这样形成的物理文件称为链接文件。链接分配采取离散分配方式,消除了外部碎片,故而显著地提高了外存空间的利用率,并且对文件的增、删、改、查十分方便。链接方式可分为隐式链接和显示链接两种形式。

链接结构的特点是每个物理块的最后一个字节中不能存放文件的信息,而是用来存放物理块之间的链接指针

文件信息占用的第一块的物理地址登记在文件目录中,链接结构中每个物理块中的链接指针指出了文件信息存放的下一个物理块的地址。当某物理块中链接指针为“0”时,表示文件信息至本块结束。

隐式链接, 在文件目录的每个目录项中,都须含有指向链接文件第一个盘块和最后一个盘块的指针

说明:第9个盘块指向第16个盘块,第16个盘块指向第1个盘块,第1个盘块指向第10个盘块,第10个盘块指向第25个盘块(结束块)。

隐式链接分配的主要问题在于:其只适合于顺序访问,对随机访问的效率及其低效。此外,其可靠性较差,任何一个指针出现问题,都会导致整个链的断开。可以将几个盘块组成一个簇,然后以簇为单位进行分配,会减少查找指定块的时间,但是会增加内部碎片。

显示链接,把用于链接文件各物理块的指针,显式的放在内存的一张链接表中该表称为文件分配表FAT(File Allocation Table),该表在整个磁盘仅设置一张。

说明:表的序号从0开始,直至N-1,N为盘块总数,在每个表项中存放链接指针,即下一个盘块号,在该表中,凡是属于某一文件的第一个盘块号,或者说是每一条链的链首指针所对应的盘块号,均作为文件地址被填入相应的文件的FCB(File Control Block)的物理地址字段中,由于查找记录的过程是在内存中进行的,因而提高了检索速度,减少了访问磁盘的次数,由于分配给文件的所有盘块号都在该表中,故把该表称为文件分配表FAT(File Allocation Table)。

链接分配的问题如下:不能支持高效的直接存储(要对一个较大的文件进行直接存取,须首先在FAT中顺序地查找很多盘块号);FAT需要占用较大的内存空间(由于一个文件所占用的盘块的盘块号是随机地分布在FAT中的,因而只有将整个FAT调入内存,才能保证FAT中找到一个文件的所有盘块号,当磁盘容量较大时,FAT占用的容量更大)

FAT 的计算

①FAT技术

在微软公司的早期MS-DOS中,所使用的就是12位的FAT12文件系统,后来为16位的FAT16文件系统 在Windows95和Windows98系统中,升级为32位的FAT32文件系统 Windows NT、 Windows 2000和Windows XP系统中又进一步发展为NTFS文件系统 这些文件系统都属于显式链接方法。

早期MS-DOS系统的FAT系统中,引入了“卷”的概念,支持将一个物理磁盘分为四个逻辑磁盘,每个逻辑磁盘就是一个卷(或称为分区)每个卷都是一个能够被单独格式化和使用的逻辑单元一个卷中包含文件系统信息、一组文件和空闲空间每个卷都专门划出一个单独区域来存放自己的文件目录和FAT表,以及自己的逻辑驱动器字母。

Ⅰ.FAT12

以盘块为基本分配单位.在FAT的每个表项中存放下一个盘块号,它实际上是用于盘块之间的链接的指针,通过它可以将一个文件的所有盘块链接起来。

每个文件的第一个盘块号放在自己的FCB中。整个系统有一张文件分配表FAT。在FAT的每个表项中存放下一个盘块号。

对于1.2MB的软盘,每个盘块大小为512B,在每个FAT中共含有2.4K个表项,若每个FAT表项占12位,则FAT表共占有3.6KB的存储空间

由于每个FAT表项为12位,因此FAT表中最多允许有4096(212=4K)个表项若每个盘块大小为512字节,则每个磁盘分区的容量最多为4096512B=2MB如果一个物理磁盘支持4个逻辑分区,则磁盘最大容量为8MB。*为了适应磁盘容量的不断增加的需求,进行磁盘分配时,不再以盘块为单位,而是以“簇”为基本单位。**

簇是一组连续的扇区,大小一般是2^n个盘块,一个簇包含扇区的数量与磁盘容量的大小直接有关一个簇仅有一个扇区时,磁盘最大容量为8MB;一个簇有2个扇区时,磁盘最大容量为16MB;一个簇有8个扇区时,磁盘最大容量为64MB。

FAT12存在的问题

  • 最主要的问题是:对所允许的磁盘容量存在着严重的限制,通常只有数十兆字节,
  • 虽然通过增加簇的大小来提高最大磁盘容量,但相应的簇内碎片也将随之成倍的增加
Ⅱ.FAT16

解决方法FAT12的问题是增加FAT表的表项数量,即增加FAT表的宽度,将其宽度增加至16位,则表项数增至2^ 16=64K=65536个。把具有16位表宽的FAT表称为FAT16如果FAT16的每个簇有64个盘块,则最大分区空间为64k×64×512=2^31=2GB

Ⅲ.FAT32

FAT32是FAT系统文件系统的最后一个产品。 FAT32表可以有2^32=4 294 967 296个表项,若每个簇为8个盘块(即4KB),FAT32分区可以管理的最大磁盘空间为2TB。 FAT32比FAT16支持更小的簇和更大的磁盘容量,大大减少了磁盘空间的浪费。 FAT32主要应用与Windows 98及后续的Windows系统,也支持长文件名。

FAT32的不足之处:

  • 由于分配表的扩大,运行速度比FAT16格式要慢

  • FAT32有最小管理空间的限制,FAT32不支持容量小于512MB的分区,因此小分区还是需要使用FAT16或FAT12系统

Ⅳ.NTFS组织方式

NTFS新特征:

NTFS是一个专门为Windows NT开发的全新的文件系统。 NTFS具有许多新特征: 使用64位磁盘地址,理论上可以264字节磁盘分区 支持长文件名 具有系统容错功能 提供了数据的一致性 提供了文件加密、文件压缩等功能

磁盘组织:

NTFS也是以簇为磁盘分配和回收的基本单位,通过簇来间接管理磁盘,可以不需要知道盘块的大小,使NTFS具有了与磁盘物理扇区大小无关的独立性。 NTFS系统中,将簇大小称为“卷因子”,也是物理磁盘扇区的整数倍。 对于簇的定位, NTFS采用逻辑簇号LCN和虚拟簇号VCN进行的。 卷因子与LCN的乘积,可以得到文件数据所在的物理磁盘地址。

文件的组织

在NTFS中,以卷为单位,将一个卷中所有的文件信息、目录信息以及可以的未分配空间信息,都以文件记录的方式记录在一张主控文件表MFT中。卷中每个文件作为一条记录,在MFT表中占有一行,大小为1KB,称为该行所对应文件的元数据,或文件控制字。

对于一个文件的真正数据,即文件的DATA属性,如果很小,就直接存储在MFT表中对应的与数据中,这样对文件数据的访问仅需对MFT表进行即可。 这样减少了磁盘访问次数,提高了对文件的存取效率。 如果文件较大,则文件的真正数据往往保存在其它簇中,此时通过访问元数据(文件控制字)中指向文件DATA属性的队列指针,就可以方便的 查找到数据簇,完成对文件数据的访问

(3)索引分配

事实上,在打开某个文件时,只需要把该文件占用的盘块号的编号调入内存即可,完全没有必要把整个FAT调入内存,为此,应该将每个文件所对应的盘块号集中地放在一起,索引分配方式就是基于这种想法所形成的一种分配方式。其为每个文件分配一个索引块(表),再把分配给该文件的所有盘块号都记录在该索引块中,因而该索引块就是一个含有许多磁盘块号的数组。在建立一个文件时,只需要在位为之建立的目录项中填上指向该索引块的指针(单级索引)。

说明:索引方式支持直接访问,可在索引块中找到第i个盘块,索引方式也不会产生外部碎片,当文件较大时,索引分配方式要优于链接分配方式。其主要问题在于:可能需要花费较多的外存空间,每当建立一个文件时,便须为之分配一个索引块,将分配给该文件的所有盘块号记录其中。对于小文件而言,索引块的利用率非常低。

当OS为一个大文件分配磁盘空间时,如果所分配的盘块的盘块号已经装满一个索引块时,OS便为该文件分配另一个索引块,用于将以后继续为之分配的盘块号记录于其中,以此类推,然后再通过链指针将各索引块按序链接起来,当文件太大时,索引块太多,效率是低效的。此时,应该为这些索引块再建立一级索引,称为第一级索引,还可再建立索引,称为第二级索引等等。称为多级索引分配。

说明:在二级索引分配方式下,若每个盘块的大小为1KB,每个盘块号占4个字节,则在一个索引块可以存放256个盘块号,这样,在两级索引时,最多可以包括存放文件的盘块号总数为64K(256 * 256)个盘块号,所允许文件最大长度为64MB,若盘块号为4KB,则一级索引的最大文件大小为4MB,二级索引的最大文件大小为4GB。

(4)混合索引分配方式

将多种索引分配方式相结合而形成的一种分配方式,如直接地址(在索引结点中设置10个直接地址项,每项中所存放的是该文件数据所在盘块的盘块号,假如每个盘块大小为4KB,当文件不大于40KB时,可以直接从索引结点中读出该文件的全部盘号),一次间接地址(利用索引结点中的地址项来提供一次间接地址,其实质就是一级索引分配方式,在一次简直快中可存放1K个盘块号,允许最大文件为4MB),多次间接地址(当文件大于4MB + 40KB时,系统采用二次间址分配方式,其实质是两级索引分配方式,采用二次间址的最大文件大小为4GB,同理,可采用三次间接地址,允许文件最大大小为4TB)。

索引结构优缺点

  • 优点:保持了链接结构的优点,又解决了其缺点:即能顺序存取,又能随机存取,满足了文件动态增长、插入删除的要求,也能充分利用外存空间
  • 缺点:较多的寻道次数和寻道时间,索引表本身带来了系统开销,如:内外存空间,存取时间

2、文件存储空间管理

(1)空闲表法

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

空闲盘区的分配与内存的动态分配类似,同样采用首次适应算法,循环首次适应算法等。系统在对用户所释放的存储空间进行回收时,也采取类似于内存回收的方法,即考虑回收区是否与空闲表中插入点的前区和后区相邻接,对相邻接者应该予以合并。当文件较小时,采用连续分配方式,当文件较大时,可采用离散分配方式。

(2) 空闲链表法

空闲链表法是将所有空闲盘区拉成一条空闲链。把链表分成两种形式,空闲盘块链和空闲盘区链。

① 空闲盘块链,这是将磁盘上的所有空闲空间,以盘块为单位拉成一条链,当用户因创建文件而请求分配存储空间时,系统从链首开始,依次摘下适当数目的空闲盘块分配给用户,当删除文件而释放空间时,系统将回收的盘块依次插入空闲盘块链的末尾,其优点是用于分配和回收一个盘块的过程简单,但在为文件分配盘块时,可能要重复操作多次。

② 空闲盘区链,这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链,在每个盘区上除了含有只是下一个空闲盘区的指针外,还应有能指明本盘区大小(盘块数)的信息。盘区分配与内存的动态分配类似,可采用首次适应算法,在回收盘区时,同样也要将回收区和相邻接的空闲盘区相合并,在采用首次适应算法时,可以采用显式链接法提高检索速度,在内存中为空闲盘区建立一张链表。

(3)位示图法

利用二进制的一位表示磁盘中的一个盘块的使用情况,当其值为0时,表示对应的盘块空闲,为1时,表示已经分配,磁盘上的所有盘块都有一个二进制位与之对应,这样,由所有盘块所对应的位构成一个集合,称为位示图,通常可用m * n个位数来构成位示图,并使m * n等于磁盘的总块数。

对于盘块的分配分为如下三步

① 顺序扫描位示图,从中找出一个或一组值为0的二进制位。

② 将所找到的一个或一组二进制位转换成与之赌赢的盘块号。

③ 修改位示图。

对于盘块的回收分为如下两步

① 将回收盘块的盘块号转换成位示图中的行号和列号。

② 修改位示图。

此方法的优点在于从位示图中很容易找到一个或一组相邻接的空闲盘块,此外,由于位示图很小,占用空间少,因而可将其保存在内存中,进而使在每次进行盘区分配时,无需首先把盘区分配表读入内存,节省磁盘启动时间。

详解位示图法

==设行号i 列号j 盘块号B 一行的位数为n==

1.行列号从0开始,盘块号从0开始

  • b = i * n+ j
  • i = b/n
  • j =b%n

2.行列号从0开始,盘块号从1开始

相对于第一种情况,盘块号多了1

  • 分配时,相对于第一种情况,计算后盘块号再加一
    • b =i ∗ n + j + 1
  • 回收时,相对于第一种情况,计算前盘块号先减一
    • i = (b− 1) / n
    • j = (b − 1) % n

3.行列号从1开始,盘块号从0开始

相对于第一种情况,行列号多了1

  • 分配时,相对于第一种情况,计算前行列号先减一
    • b =(i− 1) * n + j− 1
  • 回收时,相对于第一种情况,计算后行列号再加一
    • i=b /n + 1
    • j=b % n + 1

4.行列号从1开始,盘块号从1开始

相对于第一种情况,盘块号、行列号都多了1

  • 分配时,相对于第一种情况,计算前行列号先减一,计算后盘块号再加一
    • b = (i − 1) * n + (j− 1) + 1
      • 即:b= (i − 1) * n+ j
  • 回收时,相对于第一种情况,计算前盘块号先减一,计算后行列号再加一
    • i =(b − 1) /n + 1
    • j =(b− 1) %n + 1

(4)成组链接法

空闲表法和空闲链表法都不适用于大型系统,因为这会使空闲表或空闲链表很长,在UNIX采用的成组链接法,结合上述两种方法。

① 空盘块的组织,空闲盘块栈用来存放当前可用的一组空闲盘块的盘块号(最多含100个号),以及栈中尚有的空闲盘块号数N,顺便指出,N兼做栈顶指针使用,栈是临界资源,系统设置一把锁供进程互斥访问。其中,S.free(0)是栈底,栈满时栈顶为S.free(99)。

② 文件区中的所有空闲盘块被分成若干个组,如每100个盘块作为一组。

将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块S.free(0)~S.free(99)中,这样,由各组的第一个盘块可链接成一条链。

④ 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中,作为当前可供分配的空闲盘块号。

⑤ 最末一组只有99个盘块,其盘块号分别记入其前一组的S.free(1)~S.free(99)中,而在S.free(0)中则存放0,作为空闲盘块链的结束。

当系统要为用户分配文件所需的盘块时,须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁,如未上锁,便从 栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。若该盘块号已是栈底,即S.free(0),这是当前栈中最后一个可分配的 盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号,因此,须调用磁盘读过程,将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内 容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1并返回。

在系统回收空闲盘块时,须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时,表示栈已满,便将现有栈中的100个盘块号,记入新回收的盘块中,再将其盘块号作为新栈底。

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~