實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)節(jié)能降負(fù)策略研究.pdf

1、實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)(Real-TimeDataBaseSystem,簡(jiǎn)稱RTDBS)是數(shù)據(jù)庫(kù)技術(shù)和實(shí)時(shí)系統(tǒng)相結(jié)合的產(chǎn)物,它集成了實(shí)時(shí)系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)的相關(guān)理論和技術(shù)。近年來(lái),RTDBS在電力和數(shù)據(jù)網(wǎng)絡(luò)管理、雷達(dá)跟蹤、工業(yè)生產(chǎn)過(guò)程控制和證券交易等需要定時(shí)存取數(shù)據(jù)或?qū)Α皶簳r(shí)有效”數(shù)據(jù)進(jìn)行存取的這樣一類(lèi)國(guó)防軍事及民用實(shí)時(shí)信息服務(wù)領(lǐng)域得到了廣泛應(yīng)用。盡管應(yīng)用取得了極大的成功,但是與許多其他的計(jì)算系統(tǒng)一樣,RTDBS也受到了過(guò)量能耗的困擾。過(guò)多的能量

2、消耗對(duì)系統(tǒng)的服務(wù)質(zhì)量(包括服務(wù)時(shí)間,穩(wěn)定性和可靠性等)產(chǎn)生了巨大的影響。在某些特定的運(yùn)用環(huán)境中(典型如嵌入式環(huán)境),RTDBS通常是靠電池驅(qū)動(dòng)的,系統(tǒng)補(bǔ)充能量的代價(jià)太高,甚至由于環(huán)境的限制而在相當(dāng)長(zhǎng)一段時(shí)間內(nèi)無(wú)法補(bǔ)充能量,而在可見(jiàn)的將來(lái)電池的壽命限制問(wèn)題都難以得到徹底解決,此時(shí)節(jié)省能耗從而延長(zhǎng)系統(tǒng)的服務(wù)時(shí)間變得尤為重要。
　　與傳統(tǒng)數(shù)據(jù)庫(kù)中的數(shù)據(jù)對(duì)象不同,在實(shí)時(shí)數(shù)據(jù)庫(kù)中,數(shù)據(jù)對(duì)象只在一段時(shí)間內(nèi)是流行的(有效的),也即每一個(gè)數(shù)據(jù)對(duì)象

3、都有一個(gè)有效期作為該數(shù)據(jù)當(dāng)前值的生命周期,一旦超過(guò)了生命周期,該數(shù)據(jù)就是非時(shí)序一致性的(也即無(wú)效)。因此,必須在數(shù)據(jù)對(duì)象的舊版本(值)變成無(wú)效之前用新值更新該數(shù)據(jù)對(duì)象,以使其總是能夠反映外部實(shí)體的當(dāng)前狀態(tài)。由于RTDBS的計(jì)算資源通常是有限的(尤其在嵌入式環(huán)境下),此時(shí)如何合理設(shè)置更新事務(wù)的截止期和周期并對(duì)更新事務(wù)集進(jìn)行調(diào)度,以在保證數(shù)據(jù)對(duì)象時(shí)序一致性的前提下盡量減少用于更新事務(wù)的處理器負(fù)載變得非常重要。
　　在RTDBS中,因?yàn)?/p>

4、用于鎖表及檢測(cè)數(shù)據(jù)庫(kù)一致性的時(shí)間開(kāi)銷(xiāo)比執(zhí)行事務(wù)本身的時(shí)間開(kāi)銷(xiāo)要大得多,事務(wù)通常以非搶占的方式執(zhí)行,而已有的實(shí)時(shí)節(jié)能調(diào)度算法大都是基于可搶占任務(wù)集的。盡管也存在針對(duì)部分非搶占段任務(wù)集的節(jié)能調(diào)度策略,但是直接將它們應(yīng)用于完全非搶占任務(wù)集時(shí)往往會(huì)計(jì)算出過(guò)高的減速因子(標(biāo)準(zhǔn)化的任務(wù)執(zhí)行速度),因而并不能獲得最佳的節(jié)能效果。為此,針對(duì)完全非搶占實(shí)時(shí)任務(wù)集提出了一個(gè)新的減速因子計(jì)算方法ISA,通過(guò)精確分析來(lái)自高優(yōu)先級(jí)任務(wù)的執(zhí)行次數(shù),求得了更低的減速

5、因子,使得任務(wù)集在頻率繼承策略下通過(guò)使用新的減速因子能夠顯著降低系統(tǒng)能耗。同時(shí)注意到在發(fā)生任務(wù)阻塞時(shí),不必要總是采用頻率繼承策略來(lái)保證任務(wù)的截止期,提出了選擇性頻率繼承策略SFI以進(jìn)一步降低系統(tǒng)能耗。此外,考慮到任務(wù)的實(shí)際執(zhí)行時(shí)間通常要小于其最壞情況執(zhí)行時(shí)間,提出了動(dòng)態(tài)空閑時(shí)間回收算法ISA-DR以獲得額外的能耗節(jié)省。性能評(píng)估結(jié)果表明,提出的節(jié)能調(diào)度算法和相關(guān)策略相比于已有算法可以獲得可觀(平均為20％-30%)的能耗節(jié)省。
　　

6、目前針對(duì)單處理器系統(tǒng)靜態(tài)優(yōu)先級(jí)調(diào)度下更新事務(wù)截止期與周期計(jì)算問(wèn)題的研究已經(jīng)非常成熟,但是針對(duì)該問(wèn)題在動(dòng)態(tài)優(yōu)先級(jí)調(diào)度下的研究還比較少見(jiàn)。已有算法要么求得的處理器負(fù)載過(guò)高,要么運(yùn)行效率過(guò)于低下。基于此,提出了一個(gè)新的兩階段算法GEEDF。GEEDF算法的第一階段具有線性執(zhí)行時(shí)間,因而能被用來(lái)快速求得一個(gè)解。且證明了當(dāng)分派順序固定為最短時(shí)序優(yōu)先時(shí),由第一階段求得的解具有最優(yōu)(最小)負(fù)載。當(dāng)?shù)谝浑A段失敗時(shí),基于確切性可調(diào)度判定條件提出了GEED

7、F算法的第二階段。由于該階段具有偽多項(xiàng)式執(zhí)行時(shí)間,介紹了若干技術(shù),通過(guò)減少需要檢測(cè)的調(diào)度點(diǎn)數(shù)目和迭代步驟來(lái)降低進(jìn)行可調(diào)度性測(cè)試時(shí)的計(jì)算代價(jià),從而提高算法的執(zhí)行效率。實(shí)驗(yàn)結(jié)果表明,相較于現(xiàn)有算法,GEEDF算法能夠快速得到處理器負(fù)載更低的可行解。
　　以往針對(duì)RTDBS中數(shù)據(jù)對(duì)象時(shí)序一致性的研究都是基于單處理器系統(tǒng)來(lái)進(jìn)行的,目前國(guó)際國(guó)內(nèi)還未見(jiàn)針對(duì)該問(wèn)題在多處理器環(huán)境下的相關(guān)研究。首次研究了多處理器環(huán)境下保證實(shí)時(shí)數(shù)據(jù)對(duì)象時(shí)序一致性的更

8、新事務(wù)分派問(wèn)題,證明了多處理環(huán)境下最小化處理器負(fù)載的更新事務(wù)分派問(wèn)題是NP難的。鑒于問(wèn)題的復(fù)雜性,首先只考慮問(wèn)題的可調(diào)度性方面,提出了一個(gè)多項(xiàng)式時(shí)間分派算法TCP,并從理論上證明了TCP算法具有3?1m的資源放大界值。隨后統(tǒng)籌考慮事務(wù)分派問(wèn)題的可調(diào)度性與最小化處理器負(fù)載兩個(gè)方面,基于“一個(gè)在各個(gè)處理器之間平衡密度因子的事務(wù)分派方案趨向于得到更低的處理器負(fù)載”這一觀察,提出了具有多項(xiàng)式時(shí)間復(fù)雜度的啟發(fā)式分派算法DBF,并證明了DBF算法也