臺灣博碩士論文加值系統

　　我們發展一個方法來分析，當一個伺服器使用了應用延緩重組方法的多層資料結構來服務對使用鍵值的記錄做存取的運算時，這個伺服器的效能及穩定度。
　　當伺服器執行了一部分運算後，需要重組多層資料結構使得伺服器能有效率地執行運算。我們研究需要多久做一次資料重組使其效能最佳化。如果伺服器大部分狀態下是閒置的，則可以在伺服器閒置期間完成資料重組來消除重組時的overhead。如果伺服器大部份狀態下是忙碌的，則可以在完成較多運算後做資料重組，使重組時的overhead最小。由此可看出何時要做資料重組的這個問題，不只取快於伺服器所選用的多層資料結構，而且還與系統工作量有關。
　　我們使用two - level sorted file的多層資料結構來當作我們提出的多層資料結構應用延重組方法的範例。並將這範例的結果與single - level array data structure with on - the - fly maintenance及single - level binary tree data stucture with on - the - fly maintenance作比較，去分析他們在open systems與closed systems的效能與穩定度。我們示範了多層資料結構應用眨緩重組方法可以使系統在不影響系統的穩定度下承受更高的工作量。

　　We develop a methodology for analyzing the performance and stability of a server that maintains a multilevel data structure to service a set of sccess operations for (key, value) records. A subset of the operations executed by the server (e.g., insert and delete) require the multilevel data stucture be reorganized so that the server can execte all subsequent requests efficiently. We study how often the server should carry out data reorganization (i. e., maintenance) to maximize its performance. If the server is frequently idle then there is no need to impose the reorganization overhead on the operation requests. The reorganization overhead may be completely eliminated by uttilizing server - idling periods. If the server is frequently busy, then the reorganization overhead can be minimized by performing a complete reorganization only after the server has served a sufficient number of insert / delete operations so that the amortized cost per operation is small. Therefore, the issue of how often one should perform data reorganization to minimize the average service time depends not only on the multilevel data structure maintained by the server but also on the type and intensity of the system workload.
　　The proposed methodology is exemplified with a two - level sorted file with deferred maintenance. The performance and stability results are compared with those of a single - level binary tree data structure with on - the - fly maintenance. It is shown that deferred maintenance of the two - level sorted file outperforms on - the - fly maintenance of the single - level binary tree in both open and closed systems. Furthermore, deferred maintenance can sustain higher workload intensities without risking system stability.
　　Index Terms -- queueing servers, multilevel data structures, atomic operations, open and closed systems, modeling, deferred maintenance, periodic maintenance, performance analysis, stability analysis.