即時資料庫系統中價值導向排程策略之設計與分析

Abstract

即時資料庫系統之主要特性為必須同時滿足資料一致性及即時交易之時限 。在許多即時應用中, 各交易具有不同的完成價值, 在此環境下如何同時 降低錯失時限之交易數目及提高獲致之交易總價值是一大挑戰。在此課題 上雖然已有一些即時排程策略被提出, 但仍存在以下值得深入探討之問 題: 一、現存的排程策略多假設一即時交易之價值在其生命期中是固定不 變的, 而未考慮到變動性交易價值之影響性; 二、現存的排程策略只在特 定環境下有良好的效益, 無法適用於各種不同環境; 三、現存的排程策略 僅能在降低錯失時限之交易數或提高交易總價值上有良好效益, 而無法同 時滿足二者; 四、雖然許多即時資料庫系統是架構在多重處理器上, 現存 的排程策略卻多是以單處理器為主, 缺少適用於多重處理器架構之設計; 五、隨著記憶體價格之下降, 如何利用主記體資料庫來提高即時應用所能 獲致之交易總價值應作深入分析。 本論文提出一組價值導向排程策略, 以解決上述即時資料庫系統中之問題。在優先權設定上, 我們提出一個新 策略以考量即時交易之變動性價值、緊急性及衝突代價。此策略在各種系 統環境下均能在降低錯失時限之交易數目及提高獲致之交易總價值上有良 好的效益。另外, 我們也提出了一個適用於多重處理器上的排程策略, 以 利用平行處理特性同時處理高價值與緊急性之交易。在協同控制方面, 我 們提出即時檢查點策略以降低樂觀協同控制法則中因重新執行衝突交易所 浪費之時間代價, 因而減少交易之回應時間以滿足其時限。藉由仔細的模 擬實驗, 我們所提之新策略證實在各種環境下較現存的排程策略在降低錯 失時限之交易數目及提高獲致之交易總價值上均有明顯的改進。根據實驗 結果, 我們也提出如何在即時資料庫系統中對價值導向交易做排程之實際 建議。 為利用主記憶體資料庫之優點, 我們也評估了將部份資料庫由磁 碟遷移至主記憶中對一個即時應用之獲益的效應。我們由經濟角度設計了 一個代價評估公式以同時考量利用主記憶體資料庫所增加之獲益及擴充主 記憶體所需之費用, 並基於此公式提出了如何將部份資料庫由磁碟遷移至 主記憶之原則。對於能產生最大獲益之資料庫遷移比率則經由模擬實驗加 以評估。 A real-time database system (RTDBS) has the property that it must not only satisfy the consistency of data, but also the time constraints associated with a real-time transaction. For real- time applications where transactions have different values, an arisen challenge is to minimize the number of missed transactions and maximize the total values simultaneously. Although numerous studies have been done on real-time scheduling to achieve the above goal, there still exist some critical issues which motivate our research. First, the existing policies assume that a transaction's value stays constant during its lifetime. The time-variant form of transaction value is not considered. Second, the existing scheduling policies are not adaptive to different system conditions. Instead, they perform well only under some system conditions. An adaptive scheduling policy which is suitable for various system environments is required. Third, the existing policies can maintain only low number of missed transactions or high total values, rather than both. A policy which can meet both requirements of low missed transaction count and high total values is needed. Fourth, although a RTDBS is often equipped with multiprocessors, the existing policies are inherently designed for a single-processor RTDBS and can not perform efficiently under multiprocessors. Fifth, with the decrease in memory price, the effect of using main memory databases on increasing the profit of a real-time application should be analyzed. In this thesis, a set of value- based real-time scheduling policies, which meet the requirements mentioned above, are proposed. In priority assignment, we propose policies which take into account the time-variant value, the urgency and conflict cost of a transaction such that both goals of low missed transaction count and high total values are met. Moreover, this policy is adjustive to various system conditions. In addition, an adaptive policy which utilize the parallel processing property of multiprocessors to dynamically process both high-value and urgent transactions, is also proposed. In concurrency control, several checkpointing policies are proposed to reduce the wasted processing time of restarted transactions for real-time optimistic concurrency control protocols. In this way, the transaction response time is reduced, and the timeliness and total values are enhanced. Through detailed simulation experiments, the proposed policies are shown to outperform other scheduling policies substantially under various system environments. Based on the experimental results, some practical guidelines are suggested for scheduling value-based transactions in a RTDBS. To utilize the benefits of main memory databases, we also evaluate the effects of moving partial databases from disk into main memory on increasing the profit of a real-time application. From the economic standpoint, a cost formula is developed by considering both the profit gained from using the extended memory and the memory cost required. Based on the developed cost formula, some rules are proposed for moving partial database under various system environments. The optimal database moving percentage which results in the maximal profit is also evaluated via simulation experiments.