标题: 即時資料庫系統中價值導向排程策略之設計與分析
Design and Analysis of Value-Based Scheduling Policies for Real- Time Database Systems
作者: 曾新穆
Tseng, Shin-Mu
楊維邦
Yang Wei-Pang
資訊科學與工程研究所
关键字: 即時排程;交易價值;優先權設定;協同控制;多處理器資料庫系統;檢查點策略;real-time scheduling;transaction value;priority assignment;concurrency control;multiprocessor database system;checkpointing policy
公开日期: 1997
摘要: 即時資料庫系統之主要特性為必須同時滿足資料一致性及即時交易之時限
。在許多即時應用中, 各交易具有不同的完成價值, 在此環境下如何同時
降低錯失時限之交易數目及提高獲致之交易總價值是一大挑戰。在此課題
上雖然已有一些即時排程策略被提出, 但仍存在以下值得深入探討之問
題: 一、現存的排程策略多假設一即時交易之價值在其生命期中是固定不
變的, 而未考慮到變動性交易價值之影響性; 二、現存的排程策略只在特
定環境下有良好的效益, 無法適用於各種不同環境; 三、現存的排程策略
僅能在降低錯失時限之交易數或提高交易總價值上有良好效益, 而無法同
時滿足二者; 四、雖然許多即時資料庫系統是架構在多重處理器上, 現存
的排程策略卻多是以單處理器為主, 缺少適用於多重處理器架構之設計;
五、隨著記憶體價格之下降, 如何利用主記體資料庫來提高即時應用所能
獲致之交易總價值應作深入分析。 本論文提出一組價值導向排程策略,
以解決上述即時資料庫系統中之問題。在優先權設定上, 我們提出一個新
策略以考量即時交易之變動性價值、緊急性及衝突代價。此策略在各種系
統環境下均能在降低錯失時限之交易數目及提高獲致之交易總價值上有良
好的效益。另外, 我們也提出了一個適用於多重處理器上的排程策略, 以
利用平行處理特性同時處理高價值與緊急性之交易。在協同控制方面, 我
們提出即時檢查點策略以降低樂觀協同控制法則中因重新執行衝突交易所
浪費之時間代價, 因而減少交易之回應時間以滿足其時限。藉由仔細的模
擬實驗, 我們所提之新策略證實在各種環境下較現存的排程策略在降低錯
失時限之交易數目及提高獲致之交易總價值上均有明顯的改進。根據實驗
結果, 我們也提出如何在即時資料庫系統中對價值導向交易做排程之實際
建議。 為利用主記憶體資料庫之優點, 我們也評估了將部份資料庫由磁
碟遷移至主記憶中對一個即時應用之獲益的效應。我們由經濟角度設計了
一個代價評估公式以同時考量利用主記憶體資料庫所增加之獲益及擴充主
記憶體所需之費用, 並基於此公式提出了如何將部份資料庫由磁碟遷移至
主記憶之原則。對於能產生最大獲益之資料庫遷移比率則經由模擬實驗加
以評估。
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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT860394010
http://hdl.handle.net/11536/62836
显示于类别:Thesis