分配表

文件分配表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]