基本介紹
- 中文名：分配表
- 外文名：Allocation Table
- 學科：計算機科學
- 領域：作業系統
- 目的：資源的有效管理
- 定義：記錄資源分配或所在位置的表格
檔案分配表（FAT）,簡介,含義,簇的基本概念,基於任務分配表的動態負載平衡算法,背景,算法的基本思想,任務分配表生成策略,
檔案分配表（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表的存取開銷，提高檔案系統的效率；但這也會造成更大的簇內零頭(它與存儲器管理中的頁內零頭相似)。
基於任務分配表的動態負載平衡算法
背景
實時集群系統是工作在時間約束下的系統，與一般計算機系統的主要區別是引入了時間概念。對實時集群系統而言，最重要的指標是系統的實時性，不但要保證計算結果的邏輯正確性，而且實時任務要在規定的時間內完成計算。所以說，實時集群除了要發揮一般集群系統的計算能力之外，還需要有足夠快的系統反應時間，以滿足苛刻的時間要求。實時集群負載平衡的目標是根據處理機的性能來分配與其相稱的任務，以最小化應用程式的執行時間， 所以解決負載平衡問題是提高實時集群性能的重要因素。眾所周知，負載平衡問題是一個經典的組合最佳化難題，是一個NP完全問題。當前只有為數不多的負載平衡算法採用進程遷移的策略實現了負載平衡，而且其中的大多數只是使用模擬結果對算法性能進行評估，無法滿足實時集群的技術要求。因此，實時集群系統的負載平衡算法，需要根據系統硬體環境和事務處理的需求專門開發。
算法的基本思想
實時集群中各節點駐留自身工作信息收集守護進程，在每個計算周期向集群控制中心作出匯報，控制中心匯總各節點信息，繪製系統資源單一映像，再根據調度策略生成任務分配表， 並將任務分配表通過網路廣播至各計算節點。實時集群中的計算節點收到任務分配表後， 根據任務分配表來確定本節點要處理的數據，進行數據解算，並向控制中心報告任務完成情況。 任務分配表由控制中心駐留的負載平衡軟體建立，根據系統各節點的軟硬體工作狀態和負載信息， 以及控制員的人工干預命令來動態實時調整。
任務分配表生成策略
採用循環輪轉的方式為每個計算節點分配任務，但分配前首先檢查節點是否可用，若不可用則對下一節點進行分配。在同構集群中，各計算節點性能一致，所以各節點之間的任務數差別不大於1。任務分配表的生成遵循以下策略：在任務分配過程中，若是首次產生任務分配表，則根據可用計算節點數分配所有數據通道，使數據通道儘可能地均勻分配，並保存分配標誌；當有數據通道增加時，則在原來分配表的基礎上只對增加的數據通道進行分配，分配接著上次分配的計算節點和進程進行；當有數據通道減少時，記錄所對應的計算節點和計算進程，通道恢復或有通道增加時首先對此節點進程進行分配；當有計算節點失效時，遷移它對應的數據通道至其它計算節點。任務分配表生成後，廣播給集群各個計算節點。同時，各計算節點上的控制進程將收到的原始數據寫入共享記憶體，以供計算守護進程讀取並進行解算。
以“任務分配表”為核心的實時集群動態負載平衡機制，極大地簡化了集群並行計算程式的開發和調試過程，有效地解決了任務分配、訊息傳遞、任務遷移等關鍵技術，從而實現了集群系統的實時化。
