實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)之實(shí)時(shí)事務(wù)調(diào)度算法實(shí)時(shí)數(shù)據(jù)庫(kù)技術(shù)是實(shí)時(shí)系統(tǒng)和數(shù)據(jù)庫(kù)技術(shù)相結(jié)合的產(chǎn)物，研究人員希望利用數(shù)據(jù)庫(kù)技術(shù)來解決實(shí)時(shí)系統(tǒng)中的數(shù)據(jù)管理問題，同時(shí)利用實(shí)時(shí)技術(shù)為實(shí)時(shí)數(shù)據(jù)庫(kù)提供時(shí)間驅(qū)動(dòng)調(diào)度和資源分配算法。然而，實(shí)時(shí)數(shù)據(jù)庫(kù)并非是兩者在概念、結(jié)構(gòu)和方法上的簡(jiǎn)單集成。需要針對(duì)不同的應(yīng)用需求和應(yīng)用特點(diǎn)，對(duì)實(shí)時(shí)數(shù)據(jù)模型、實(shí)時(shí)事務(wù)調(diào)度與資源分配策略、實(shí)時(shí)數(shù)據(jù)查詢語言、實(shí)時(shí)數(shù)據(jù)通信等大量問題作深入的理論研究。實(shí)時(shí)事務(wù)調(diào)度策略定義如何為事務(wù)分配優(yōu)先級(jí)，而調(diào)度的最重要目標(biāo)是保證盡可能多的事務(wù)能夠滿足截止期。大部分實(shí)時(shí)任務(wù)調(diào)度算法并不能直接用于調(diào)度實(shí)時(shí)事務(wù)，原因在于：這些算法通常要求任務(wù)到達(dá)時(shí)間、截止期與最壞情況執(zhí)行時(shí)間與關(guān)鍵性等參數(shù)是已知的。而實(shí)時(shí)事務(wù)調(diào)度中廣泛存在的不可預(yù)測(cè)因素，主要包括數(shù)據(jù)存取的動(dòng)態(tài)性、磁盤I/O、事務(wù)夭折與回滾等，導(dǎo)致事務(wù)的最壞情況執(zhí)行時(shí)間很難估計(jì)。因此，很多實(shí)時(shí)數(shù)據(jù)庫(kù)采用主內(nèi)存數(shù)據(jù)庫(kù)模型，以消除I/O操作所帶來的影響。另一方面，實(shí)時(shí)數(shù)據(jù)庫(kù)通常應(yīng)用于開放環(huán)境，系統(tǒng)的負(fù)載變化是不可預(yù)知的且可能在較大范圍內(nèi)變化，給實(shí)時(shí)事務(wù)調(diào)度帶來更多的困難。Abbott等ABB88最先基于一個(gè)內(nèi)存駐留的實(shí)時(shí)數(shù)據(jù)庫(kù)模型，綜合研究了FCFS（First Come First Serve）、EDF（Earliest Deadline First）與LSF（Least Slack First）三種優(yōu)先級(jí)分配方法以及串行執(zhí)行（Serial Execution）、2PL-HP（2PL-High Priority）與2PL-CR（2PL-Conditional Restart）三種并發(fā)控制協(xié)議，仿真實(shí)驗(yàn)結(jié)果表明：就調(diào)度算法而言，EDF算法表現(xiàn)出最好的性能；并發(fā)控制中2PL-CR表現(xiàn)出最好的性能，但是其性能很大程度地受到事務(wù)估計(jì)執(zhí)行時(shí)間精度的影響。進(jìn)一步地，Abbott等ABB92也在磁盤駐留的實(shí)時(shí)數(shù)據(jù)庫(kù)模型之上對(duì)上面的算法與協(xié)議進(jìn)行了測(cè)試，結(jié)果表明LSF優(yōu)先級(jí)分配算法表現(xiàn)出最好的性能，而2PL-WP協(xié)議與LSF或者EDF配合使用都優(yōu)于2PL-HP協(xié)議，并且采用優(yōu)先級(jí)驅(qū)動(dòng)的I/O調(diào)度相對(duì)于FIFO方式具有很大的性能改進(jìn)。無論如何，當(dāng)系統(tǒng)負(fù)載采用步進(jìn)方式遞增時(shí)，EDF算法是性能最好的調(diào)度算法，而2PL-HP協(xié)議表現(xiàn)最佳。最后，Abbott等指出CPU調(diào)度算法是實(shí)時(shí)事務(wù)調(diào)度處理中最重要的策略，而在并發(fā)控制中使用優(yōu)先級(jí)信息解決數(shù)據(jù)沖突有利于改進(jìn)系統(tǒng)的性能。Huang等HUA89基于一個(gè)實(shí)時(shí)數(shù)據(jù)庫(kù)測(cè)試床RT-CARAT，針對(duì)實(shí)時(shí)事務(wù)調(diào)度算法與沖突解決策略進(jìn)行了實(shí)驗(yàn)研究，結(jié)果表明：實(shí)時(shí)事務(wù)調(diào)度算法必須綜合考慮事務(wù)的截止期與關(guān)鍵性（或者價(jià)值），并且在沖突解決策略中考慮這些信息能夠改進(jìn)系統(tǒng)性能；事務(wù)截止期與關(guān)鍵性的分布情況也在很大程度上影響系統(tǒng)的性能。因此，在隨后的研究中，許多算法都把事務(wù)的關(guān)鍵性或者重要性看作調(diào)度算法中必須考慮的重要因素。上個(gè)世紀(jì)九十年代，實(shí)時(shí)事務(wù)調(diào)度的研究基本上是從基于價(jià)值的事務(wù)調(diào)度、基于準(zhǔn)入控制的事務(wù)調(diào)度、滿足時(shí)態(tài)一致性的事務(wù)調(diào)度等幾個(gè)方面發(fā)展，并且進(jìn)一步地在調(diào)度中考慮不同的事務(wù)模型以及過載消解方法。最近幾年，反饋控制方法也被應(yīng)用到實(shí)時(shí)事務(wù)的調(diào)度中，并取得了相當(dāng)多的研究成果。另一方面，混合事務(wù)的也得到了越來越多的研究。1基于價(jià)值的事務(wù)調(diào)度在許多現(xiàn)實(shí)的應(yīng)用中，不同的事務(wù)具有不同的價(jià)值或者不同的關(guān)鍵程度。在實(shí)時(shí)數(shù)據(jù)庫(kù)領(lǐng)域，先前的一些研究也已經(jīng)考慮調(diào)度具有不同價(jià)值的事務(wù)，而系統(tǒng)的主要性能指標(biāo)通常也轉(zhuǎn)換為最大化系統(tǒng)的實(shí)現(xiàn)價(jià)值。最初，Huang等HUA89使用一個(gè)實(shí)時(shí)數(shù)據(jù)庫(kù)測(cè)試床RT-CARAT評(píng)估了MCF（Most Critical First）、EDF與CDF（Criticalness-Deadline First）三種調(diào)度算法的性能，其中CDF算法中事務(wù)的優(yōu)先級(jí)按照（相對(duì)截止期關(guān)鍵性）進(jìn)行分配，結(jié)果表明綜合考慮事務(wù)的截止期與關(guān)鍵性在很大上改進(jìn)了系統(tǒng)的綜合性能。Haritsa等HAR91,HAR93給出了不同的基于價(jià)值的優(yōu)先級(jí)分配算法：Highest Value First（HVF）、Value-Inflated Deadline（VD）、Value-Inflated Relative Deadline（VRD）以及桶算法（BA：Bucket Algorithm），其中VD算法中事務(wù)的優(yōu)先級(jí)按照（截止期關(guān)鍵性）進(jìn)行分配，VRD算法等同于CDF算法。實(shí)驗(yàn)結(jié)果表明，EDF算法在負(fù)載較輕時(shí)表現(xiàn)最佳，HVF與VD算法在較高負(fù)載下性能較好，而VRD算法表現(xiàn)出最好的綜合性能。不過，通過對(duì)BA算法的性能測(cè)試表明，沒有一個(gè)固定的截止期-價(jià)值的折衷能夠適用于所有負(fù)載情況，根據(jù)負(fù)載情況合理選擇參數(shù)能夠產(chǎn)生最好的性能。此外，研究也表明了在采用綜合截止期與價(jià)值的調(diào)度算法進(jìn)行固定截止期事務(wù)調(diào)度時(shí)OCC-Wait協(xié)議的性能也優(yōu)于2PL-HP協(xié)議。Tseng等TSE95提出了另一種基于價(jià)值的調(diào)度算法HRF（Highest Reward First），其中事務(wù)的優(yōu)先級(jí)按照（價(jià)值剩余執(zhí)行時(shí)間）進(jìn)行分配，因此這種優(yōu)先級(jí)是時(shí)變的。Haritsa與Tseng等HAR93,TSE95對(duì)于基于價(jià)值的調(diào)度算法進(jìn)行了廣泛研究，認(rèn)為：如果事務(wù)的價(jià)值是偏斜分布，其中10的事務(wù)提供90的價(jià)值，則在正常負(fù)載下算法性能排序?yàn)镋DFHRF HVFVRD，在系統(tǒng)過載時(shí)性能排序?yàn)镠RFHVFVRDEDF。進(jìn)一步，Tseng等TSE96研究了不同基于價(jià)值的實(shí)時(shí)事務(wù)調(diào)度算法在實(shí)時(shí)主內(nèi)存數(shù)據(jù)庫(kù)（RTMMDB）與部分駐留內(nèi)存的實(shí)時(shí)數(shù)據(jù)庫(kù)中的性能，目標(biāo)在于評(píng)估并比較這些算法在主內(nèi)存數(shù)據(jù)庫(kù)環(huán)境中的性能，以及研究只存儲(chǔ)部分?jǐn)?shù)據(jù)在主內(nèi)存中的效果。Tseng等的實(shí)驗(yàn)結(jié)果表明：當(dāng)只有部分?jǐn)?shù)據(jù)駐留內(nèi)存時(shí)，增加內(nèi)存的大小能夠產(chǎn)生改進(jìn)系統(tǒng)的性能，從而實(shí)現(xiàn)更高的價(jià)值。任務(wù)的價(jià)值也被用于準(zhǔn)入控制中，決定任務(wù)的接納或者移除先前接納的任務(wù)，這將在下一小節(jié)討論。此外，Bestavros等BES95研究了在軟實(shí)時(shí)數(shù)據(jù)庫(kù)中如何利用價(jià)值函數(shù)確定提交事務(wù)或者延遲提交事務(wù)，這種在并發(fā)控制中綜合考慮事務(wù)的截止期與價(jià)值的問題能夠歸結(jié)為如何為競(jìng)爭(zhēng)的事務(wù)定量配給冗余的資源，以便實(shí)現(xiàn)更大的系統(tǒng)價(jià)值。Hong與Chakravarthy等HON92,CHJ94在他們的研究工作中引入代價(jià)意識(shí)（Cost Consciousness）的概念，提出并評(píng)估了一個(gè)CCA-ALF（Cost Conscious Approach with Average Load Factor）調(diào)度策略，這是一個(gè)最大努力的方法，調(diào)度決策中既考慮了事務(wù)的靜態(tài)方面（軟/固截止期），也考慮了事務(wù)執(zhí)行的動(dòng)態(tài)方面（系統(tǒng)負(fù)載）。在Braoudakis的研究中BRA94，假設(shè)每個(gè)事務(wù)關(guān)聯(lián)一個(gè)價(jià)值函數(shù)，標(biāo)識(shí)了這個(gè)事務(wù)的時(shí)間需求與重要性。在這個(gè)框架下，事務(wù)的不同特征能夠被描述，包括硬、固定、軟或者無截止期事務(wù)，從而允許單個(gè)的事務(wù)處理協(xié)議在所有類型的事務(wù)上一致地執(zhí)行。2基于準(zhǔn)入的事務(wù)調(diào)度實(shí)時(shí)事務(wù)調(diào)度面臨的一個(gè)主要挑戰(zhàn)是事務(wù)執(zhí)行所需要的資源是事先未知的。例如，事務(wù)讀/寫的數(shù)據(jù)對(duì)象可能依賴于用戶的輸入或者傳感器輸入，因此為事務(wù)預(yù)留資源以保證事務(wù)的最壞情況執(zhí)行時(shí)間WCET（Worst Case Execution Time）是非常困難的。考慮當(dāng)前在實(shí)時(shí)事務(wù)調(diào)度與實(shí)時(shí)并發(fā)控制方面眾多的研究成果，其中包括許多時(shí)間認(rèn)知的并發(fā)控制協(xié)議被提出，目的在于最大化滿足截止期的事務(wù)數(shù)量。這些算法或者協(xié)議的優(yōu)勢(shì)只有當(dāng)系統(tǒng)出現(xiàn)過載時(shí)才被具體地體現(xiàn)，它們的性能在系統(tǒng)欠載的情況下通常與非常簡(jiǎn)單的算法（如EDF與2PL-HP）相當(dāng)。既然當(dāng)一個(gè)實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)過載時(shí)，大量的事務(wù)錯(cuò)失了截止期，如果通過準(zhǔn)入控制與過載管理策略拒絕一些事務(wù)進(jìn)入系統(tǒng)，就能夠避免有限的資源浪費(fèi)在執(zhí)行不可能及時(shí)完成的事務(wù)上。正是基于這種思想，一些研究針對(duì)準(zhǔn)入控制技術(shù)進(jìn)行了較深入的研究。Bestavros等BES96給出一個(gè)實(shí)時(shí)數(shù)據(jù)庫(kù)模型，并在此基礎(chǔ)上研究了硬截止期事務(wù)的準(zhǔn)入控制與過載管理問題。由于硬實(shí)時(shí)事務(wù)錯(cuò)失截止期可能產(chǎn)生嚴(yán)重的后果，因此硬實(shí)時(shí)事務(wù)的執(zhí)行需求必須預(yù)先知道，或者定義一些補(bǔ)救活動(dòng)，以保證系統(tǒng)不會(huì)出現(xiàn)災(zāi)難性的后果。Bestavros等定義的事務(wù)模型中，每個(gè)事務(wù)由兩個(gè)部分組成：基本子事務(wù)與補(bǔ)償子事務(wù)。準(zhǔn)入控制器用于決定是否接納新到達(dá)的事務(wù)。這里，準(zhǔn)入控制器由兩個(gè)部分組成：并發(fā)準(zhǔn)入控制器（CACM：Concurrency ACM）與負(fù)載準(zhǔn)入控制器（WACM：Workload ACM）。為了保證補(bǔ)償事務(wù)的完成，系統(tǒng)采用兩層優(yōu)先級(jí)模式進(jìn)行調(diào)度。系統(tǒng)總是為補(bǔ)償子事務(wù)分配一個(gè)更高的優(yōu)先級(jí)，并且一個(gè)補(bǔ)償子事務(wù)不能夠被一個(gè)基本子事務(wù)或者另一個(gè)補(bǔ)償子事務(wù)搶占。WACM基于估計(jì)系統(tǒng)負(fù)載確定是否接納一個(gè)事務(wù)，特別是，如果用于補(bǔ)償子事務(wù)的處理器帶寬比較高，則應(yīng)該謹(jǐn)慎地拒絕新到達(dá)的事務(wù)。為了確保補(bǔ)償子事務(wù)無阻礙地執(zhí)行，CACM保證被接納事務(wù)的補(bǔ)償子事務(wù)不與系統(tǒng)中已經(jīng)接納事務(wù)的補(bǔ)償子事務(wù)存在沖突。Bestavros等BES96提出了一些不同的方法用于WACM并通過模擬實(shí)驗(yàn)比較了它們的性能。這些方法包括First-Fit（FF）、Latest-Fit（LF）、Latest-Marginal-Fit（LMF）、Latest-Adaptable-Fit（LAF）以及Value-Adaptable-Fit（VAF），其中前面四種方法都是通過判斷補(bǔ)償事務(wù)的可調(diào)度性或者給定補(bǔ)償子事務(wù)處理器閾值下處理器帶寬的可得到性決定接納或者拒絕事務(wù)。VAF方法中準(zhǔn)入控制分為兩個(gè)部分：（1）評(píng)估接納一個(gè)事務(wù)進(jìn)入系統(tǒng)的預(yù)期價(jià)值，這是通過對(duì)比接納這個(gè)事務(wù)潛在的價(jià)值與損失達(dá)到的；（2）通過動(dòng)態(tài)計(jì)算分配給補(bǔ)償事務(wù)的處理器帶寬，對(duì)比補(bǔ)償事務(wù)的處理器利用率，確定是否接納這個(gè)事務(wù)。LAF與VAF都具有一定的自適應(yīng)能力，但是其參數(shù)必須通過離線的仿真確定。雖然上面的論文研究了并發(fā)控制、準(zhǔn)入控制與事務(wù)調(diào)度之間的相互作用，但是這些工作依然不夠。例如，CCM應(yīng)該能夠使用CACM中的信息更好的進(jìn)行并發(fā)控制決策；反之，CACM能夠利用基本子事務(wù)的讀寫集確定是否執(zhí)行特定的補(bǔ)償事務(wù)。3動(dòng)態(tài)過載消解方法準(zhǔn)入控制通常作為過載管理的一部分，也存在一些研究通過不精確計(jì)算模型或者剔除部分已經(jīng)接納但是價(jià)值較小的事務(wù)來控制系統(tǒng)過載。在不精確計(jì)算模型LLS91,SHI89,SHI92中，任務(wù)分為必須與可選兩部分，前者用于計(jì)算出一個(gè)滿足最小系統(tǒng)需求的結(jié)果，而后者用于提高這個(gè)結(jié)果的質(zhì)量。通常，必須的子任務(wù)具有硬截止期而可選子任務(wù)具有固定截止期。其實(shí)，基本/補(bǔ)償事務(wù)BES96、主事務(wù)/附帶事務(wù)HAN98、嵌套事務(wù)ELM92以及自適應(yīng)事務(wù)Do96都與不精確計(jì)算模型基于相同的思想。Hansson等HAN98,HAN99給出了一個(gè)新的事務(wù)調(diào)度框架與過載管理算法，這個(gè)算法面向具有多類事務(wù)負(fù)載的主內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)。當(dāng)準(zhǔn)入控制器檢測(cè)到系統(tǒng)過載，會(huì)調(diào)用過載消解器給出一個(gè)規(guī)劃，從接納的事務(wù)中解除足夠的資源分配以便接納新的事務(wù)，并且也確定執(zhí)行這個(gè)規(guī)劃是否有利于系統(tǒng)目標(biāo)。Hansson等研究工作的優(yōu)點(diǎn)之一在于把過載管理與事務(wù)調(diào)度、準(zhǔn)入控制分開，進(jìn)一步地，過載消解能夠通過平衡多種策略并確定最優(yōu)或者接近最優(yōu)的方法。但是，其中存在的問題在于沒有很好地討論并解決并發(fā)控制與事務(wù)調(diào)度、系統(tǒng)過載之間的相互影響。另一方面，許多應(yīng)用如協(xié)同工作系統(tǒng)等要求事務(wù)之間的協(xié)調(diào)與并行性，這些復(fù)雜的事務(wù)可以歸類為擴(kuò)展事務(wù)模型（ETM：Extended Transaction Model）ELM92。使用嵌套事務(wù)的驅(qū)動(dòng)力之一是表達(dá)長(zhǎng)壽事務(wù)，嵌套事務(wù)提供了事務(wù)內(nèi)的并行性，具有較好的失效恢復(fù)能力。Fortier等FOR94通過擴(kuò)展標(biāo)準(zhǔn)SQL語言描述了一個(gè)擴(kuò)展事務(wù)模型，增加了前置條件與后置條件以定義事務(wù)的語義正確性。盡管基本/補(bǔ)償事務(wù)BES96、主事務(wù)/附帶事務(wù)HAN98可以歸結(jié)為嵌套事務(wù)，但是這些研究更加偏重于成為一種滿足事務(wù)截止期的策略。Dodu等Do96,Do96b給出了一種自適應(yīng)實(shí)時(shí)事務(wù)模型，并提出了幾種面向自適應(yīng)事務(wù)的調(diào)度策略。自適應(yīng)事務(wù)是具有可選與必需子事務(wù)的嵌套事務(wù)，構(gòu)造為一個(gè)事務(wù)樹，并通過時(shí)間約束來支持實(shí)時(shí)應(yīng)用。每個(gè)自適應(yīng)事務(wù)具有一個(gè)最小執(zhí)行子集（MES：Minimal Execution Set），這個(gè)子集是從根結(jié)點(diǎn)開始連通所有必需子事務(wù)的一棵子樹。自適應(yīng)事務(wù)能夠動(dòng)態(tài)適應(yīng)系統(tǒng)的負(fù)載情形，從而事務(wù)處理系統(tǒng)能夠根據(jù)系統(tǒng)需求自動(dòng)調(diào)節(jié)事務(wù)，有助于其它事務(wù)的完成。但是，調(diào)度自適應(yīng)事務(wù)存在兩個(gè)矛盾的方面：（1）最大化完成的事務(wù)數(shù)量，即事務(wù)成功率；（2）最大化每個(gè)自適應(yīng)事務(wù)完成的部分，即事務(wù)子集完成率。因此，調(diào)度自適應(yīng)事務(wù)的性能評(píng)估要求一個(gè)平衡的性能尺度。仿真結(jié)果也表明了基于優(yōu)先級(jí)的事務(wù)調(diào)度如果考慮事務(wù)的結(jié)構(gòu)能夠改進(jìn)系統(tǒng)性能。4面向時(shí)態(tài)一致性的調(diào)度機(jī)制在許多實(shí)時(shí)數(shù)據(jù)庫(kù)應(yīng)用中，不僅事務(wù)具有截止期，而且數(shù)據(jù)具有時(shí)態(tài)一致性需求。就維護(hù)數(shù)據(jù)的時(shí)態(tài)一致性方面，Song等SON95綜合研究了RM、EDF調(diào)度算法與2PL、OCC并發(fā)控制協(xié)議，結(jié)果表明RM與EDF算法在較大負(fù)載下具有相似的性能，而在較高的負(fù)載下EDF算法在維護(hù)時(shí)態(tài)一致性方面優(yōu)于RM算法；另一方面，盡管OCC協(xié)議允許更多的事務(wù)滿足截止期，但是在維護(hù)時(shí)態(tài)一致性方面不如基于鎖的協(xié)議。進(jìn)一步地，Xiong等XIO96,XIO96b提出了數(shù)據(jù)截止期（Data-deadline）與時(shí)間認(rèn)知的強(qiáng)迫等待（Forced Wait）的策略。由于事務(wù)存取的數(shù)據(jù)具有時(shí)態(tài)一致性需求，使得事務(wù)隱含地得到了數(shù)據(jù)截止期；如果一個(gè)事務(wù)所要訪問的某項(xiàng)數(shù)據(jù)已經(jīng)過時(shí)，則能夠采用強(qiáng)迫等待方法推遲事務(wù)的執(zhí)行直到這個(gè)數(shù)據(jù)項(xiàng)的新版本出現(xiàn)，或者利用數(shù)據(jù)相似性繼續(xù)執(zhí)行。研究表明，在調(diào)度事務(wù)時(shí)如果只考慮事務(wù)的數(shù)據(jù)截止期，性能具有一定的改進(jìn)，而如果進(jìn)一步結(jié)合強(qiáng)迫等待策略，則性能會(huì)有很大提高。當(dāng)不采用強(qiáng)迫等待而利用數(shù)據(jù)相似性時(shí)，系統(tǒng)性能也有很大的提高，但是兩種同時(shí)使用時(shí)，數(shù)據(jù)相似性沒有明顯地影響系統(tǒng)性能。5基于反饋控制的事務(wù)調(diào)度由于實(shí)時(shí)數(shù)據(jù)庫(kù)越來越多地應(yīng)用到開放與不可預(yù)測(cè)的環(huán)境中，特別是實(shí)時(shí)事務(wù)的執(zhí)行時(shí)間與數(shù)據(jù)需求通常是不確定的，因此，一些自適應(yīng)的算法被提出并應(yīng)用到實(shí)時(shí)數(shù)據(jù)庫(kù)中的許多方面，包括調(diào)度算法、索引機(jī)制以及內(nèi)存管理等。最初，Haritsa等HAR91b給出了兩種基于反饋機(jī)制的調(diào)度算法自適應(yīng)的最早截止期（AED：Adaptive Earliest Deadline）與層次最早截止期（HED：Hierarchical Earliest Deadline）調(diào)度算法，這兩種算法被用于固定截止期實(shí)時(shí)數(shù)據(jù)庫(kù)環(huán)境中穩(wěn)定EDF算法在過載情況下的性能降級(jí)。仿真實(shí)驗(yàn)的結(jié)果表明，AED與HED算法都具有很好的綜合性能。盡管AED與HED算法能夠通過連續(xù)的反饋提供一定的自適應(yīng)性，但是參數(shù)調(diào)整公式都是經(jīng)驗(yàn)式的，不能夠根據(jù)系統(tǒng)中的負(fù)載與應(yīng)用環(huán)境自動(dòng)進(jìn)行調(diào)整。Goyal等GOY95通過實(shí)驗(yàn)發(fā)現(xiàn)B-link算法能通過增加負(fù)載控制機(jī)制而改進(jìn)性能，因此提出了LAB-link（Load Adaptive B-link）算法，其中采用的機(jī)制類似與AED算法，利用反饋機(jī)制監(jiān)視系統(tǒng)資源的利用率，如果瓶頸資源的利用率超過MaxUtil，則拒絕新的事