實時數(shù)據(jù)流系統(tǒng)中調(diào)度算法的研究與實現(xiàn).pdf

1、隨著信息處理在通信、工業(yè)生產(chǎn)、商務處理等領域的廣泛應用，數(shù)據(jù)已不僅僅拘泥于文件、數(shù)據(jù)庫等傳統(tǒng)的靜態(tài)形式，一種連續(xù)、無界、不定速度的數(shù)據(jù)流已經(jīng)出現(xiàn)在越來越多的應用領域，如：網(wǎng)絡監(jiān)控，傳感器的數(shù)據(jù)處理，生產(chǎn)線管理，股市信息分析等。特別是在數(shù)字化、智能化的嵌入式系統(tǒng)中，需要對實時數(shù)據(jù)進行復雜、高效的分析和處理。對流式數(shù)據(jù)的管理是這些應用領域的核心問題，由此興起的支持高性能實時計算的流式數(shù)據(jù)管理技術正在成為數(shù)據(jù)庫領域新的研究課題。 在一

2、些關鍵應用中，要求實時處理大量、連續(xù)到達、快速甚至爆發(fā)的數(shù)據(jù)流，在截止期內(nèi)給出實時查詢結果。由于系統(tǒng)資源(如CPU速度、內(nèi)存容量等)限制，特別是在流爆發(fā)時，不可能實時處理完數(shù)據(jù)流上的所有數(shù)據(jù)，而是盡力處理盡可能多的流數(shù)據(jù)，以獲得高質量的近似查詢結果。 提供數(shù)據(jù)流管理功能的系統(tǒng)稱為數(shù)據(jù)流管理系統(tǒng)(datastreammanagementsystem,簡稱DSMS)，而調(diào)度策略是影響系統(tǒng)的整體性能最為關鍵的因素之一。在動態(tài)爆發(fā)的數(shù)據(jù)

3、流環(huán)境中，如何設計實時調(diào)度策略，保證應用的實時需求，并獲取高質量的近似查詢結果，成為目前學術界和產(chǎn)業(yè)界關注的熱點問題。 本文討論了當有截止期實時約束以及存在有流爆發(fā)的數(shù)據(jù)流環(huán)境中，如何設計高效的固實時任務調(diào)度策略，以最小化截止期錯失率(SDMR)的問題。首先給出了固實時模型定義，并提出批劃分單位，作為準確劃分批任務的依據(jù)。給出了一種基于Tick的基本批任務調(diào)度方法，稱為BasicTickScheduling(BTS)方法，有效降