[科普中国]-分配表

文件分配表（FAT）简介

文件分配表FAT（File Allocation Table）用来记录文件所在位置的表格。它对于硬盘的使用是非常重要的，假若丢失文件分配表，那么硬盘上的数据就无法定位而不能使用了。

不同的操作系统所使用的文件系统不尽相同，在个人计算机上常用的操作系统中，DOS 6.x及以下版本和Windows 3.x使用FAT16；OS/2使用HPFS；Windows NT则使用NTFS；而MS-DOS7.10/8.0（Windows 95OSR2及Windows 98自带的DOS）及ROM-DOS 7.x同时提供了FAT16及FAT32供用户选用。其中我们接触最多的是FAT16、FAT32文件系统。FAT16在DOS时代得到广泛的应用，一般不常见了。FAT32是FAT16的升级版本，这种格式采用32位的文件分配表，对磁盘的管理能力大大增强，突破了FAT16对每一个分区的容量只有2gb的限制。运用FAT32的分区格式后，用户可以将一个大硬盘定义成一个分区，而不必分为几个分区使用，大大方便了对硬盘的管理工作。而且，FAT32还具有一个最大的优点：在一个不超过8gb的分区中，FAT32分区格式的每个簇容量都固定为4kb，与FAT16相比，可以大大地减少硬盘空间的浪费，提高了硬盘利用效率。虽然在安全性和稳定性上比不上NTFS格式，但它有个最大的优点，那就是兼容性好，几乎所有的操作系统都识别该格式，包括DOS6.0、Win9X、WinNT、Win2000和 WinXP。

Windows95 OSR2和Windows 98开始支持FAT32 文件系统，它是对早期DOS的FAT16文件系统的增强，由于文件系统的核心--文件分配表FAT由16位扩充为32位，所以称为FAT32文件系统。

含义数据文件在磁盘上是以“簇”为单位存放的，而每簇包含有多少扇区则由该磁盘的类型所决 定，较长的文件或程序需要占用多个簇的磁盘存贮空间。为了有效地管理磁盘文件，Dos采用了链表结构，通过指针把磁盘上的相应簇链接起来，这样就可以允许把存盘文件分割成 若干块分散存放在磁盘上，块的大小由该盘上原有文件存放的物理位置决定，最小仅为l簇，从而可以充分利用磁盘存贮空间，文件是通过指针来维持它的逻辑连续性。在这里，存放链表指针的单元的集( 组 )合就是(FAT)表。该表实际上是一个特殊的一维数组，它指出了用 户文件在磁盘数据区中存放的物理位置以及文件存放顺序的信息。这个数组中每个元素 (链 表指针) 的长度则由磁盘的容量来决定，也可通过文件分配表中第一个字节即磁盘类别来 获得。当磁盘数据区中总的簇数值大于4087时，FA使用2B( 16位)作为链表指针，否则使 用1.5B ( 12位)作为链表指针。由于FAT中的链表指针与用“簇”表示的磁盘数据区中的存储块是一一对应的，因此当需要读写磁盘文件操作时，只需对该表作适当操作即可得到具 体的物理地址。

簇的基本概念为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在FAT 中它是作为一个虚拟扇区，簇的大小一般是 2n(n为整数)个盘块，在MS-DOS 的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为 8 MB；当一个簇包含两个扇区时，磁盘的最大容量可以达到 16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到64 MB。由上所述可以看出，以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位虽可减少 FAT表中的项数(在相同的磁盘容量下，FAT 表的项数是与簇的大小成反比的)。这一方面会使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。2

基于任务分配表的动态负载平衡算法背景实时集群系统是工作在时间约束下的系统，与一般计算机系统的主要区别是引入了时间概念。对实时集群系统而言，最重要的指标是系统的实时性，不但要保证计算结果的逻辑正确性，而且实时任务要在规定的时间内完成计算。所以说，实时集群除了要发挥一般集群系统的计算能力之外，还需要有足够快的系统反应时间，以满足苛刻的时间要求。实时集群负载平衡的目标是根据处理机的性能来分配与其相称的任务，以最小化应用程序的执行时间， 所以解决负载平衡问题是提高实时集群性能的重要因素。众所周知，负载平衡问题是一个经典的组合优化难题，是一个NP完全问题。当前只有为数不多的负载平衡算法采用进程迁移的策略实现了负载平衡，而且其中的大多数只是使用模拟结果对算法性能进行评估，无法满足实时集群的技术要求。因此，实时集群系统的负载平衡算法，需要根据系统硬件环境和事务处理的需求专门开发。

算法的基本思想实时集群中各节点驻留自身工作信息收集守护进程，在每个计算周期向集群控制中心作出汇报，控制中心汇总各节点信息，绘制系统资源单一映像，再根据调度策略生成任务分配表， 并将任务分配表通过网络广播至各计算节点。实时集群中的计算节点收到任务分配表后， 根据任务分配表来确定本节点要处理的数据，进行数据解算，并向控制中心报告任务完成情况。 任务分配表由控制中心驻留的负载平衡软件建立，根据系统各节点的软硬件工作状态和负载信息， 以及控制员的人工干预命令来动态实时调整。

任务分配表生成策略采用循环轮转的方式为每个计算节点分配任务，但分配前首先检查节点是否可用，若不可用则对下一节点进行分配。在同构集群中，各计算节点性能一致，所以各节点之间的任务数差别不大于1。任务分配表的生成遵循以下策略：在任务分配过程中，若是首次产生任务分配表，则根据可用计算节点数分配所有数据通道，使数据通道尽可能地均匀分配，并保存分配标志；当有数据通道增加时，则在原来分配表的基础上只对增加的数据通道进行分配，分配接着上次分配的计算节点和进程进行；当有数据通道减少时，记录所对应的计算节点和计算进程，通道恢复或有通道增加时首先对此节点进程进行分配；当有计算节点失效时，迁移它对应的数据通道至其它计算节点。任务分配表生成后，广播给集群各个计算节点。同时，各计算节点上的控制进程将收到的原始数据写入共享内存，以供计算守护进程读取并进行解算。

以“任务分配表”为核心的实时集群动态负载平衡机制，极大地简化了集群并行计算程序的开发和调试过程，有效地解决了任务分配、消息传递、任务迁移等关键技术，从而实现了集群系统的实时化。3