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

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

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

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