在分散式系統中,基於局部記憶體限制,以簡易啟發式演算法找出最佳檔案配置方式

Abstract

由於分散式計算系統具有高速和可靠的性能優點，因此分散式計算系統已 經成為目前電腦系統設計的主流，而系統可靠度是設計分散式計算系統時 一項重要的考量，藉由在分散式計算系統之中增加多份重複的軟體可以提 高系統的可靠度，而這些檔案的分佈情形會影響程式或系統的可靠度。以 可靠度為導向的檔案配置問題就是找出一種好的檔案的分配方式，使得程 式或系統的可靠度最佳。這篇論文裡對以可靠度為導向的檔案配置問題提 出了一個簡易的啟發式演算法，這個演算法使用了快速簡單的檔案配置決 定方法，經由模擬實驗結果顯示，此演算法在大部份的情況下，可以迅速 地求得近似最佳解，而且其誤差十分地小。 Distributed computing systems (DCS) have become a major trend in computer system design today because of their high speed and high reliable performance advantages. Reliability is an important performance parameter in DCS design. Typically, redundant copies of software can be added to a system to increase system's reliability. The distribution of program and data files can also affect the distributed program reliability (DPR) and distributed system reliability (DSR). The reliability- oriented file assignment problem is to find a file distribution such that program reliability or system reliability is maximal. In this thesis, we develop a simple heuristic file assignment algorithm which use several simple heuristic assignment rules to achieve reliability-oriented file assignment. The proposed algorithm can obtain the optimal solutions in most cases and reduce computation time significantly. Examples are given to illustrate the applicability and advantages of the proposed algorithm. Also, the time complexity is analyzed.