Specification and management of QoS in real-time databases s(4)

EarliestDeadlineFirst(EDF).Transactionsarepro-cessedintheorderdeterminedbytheirabsolutedeadlines;thenexttransactiontorunistheonewiththeearliestdeadline(foranelaboratediscussiononEDF,see,e.g.,[8]).HighestErrorFirst(HEF).Transactionsareprocessedintheorderdeterminedbytheirtransactionerror;thenexttransactiontorunistheonewiththegreatesttransactionerror.

HighestErrorDensityFirst(HEDF).Transactionsarescheduledaccordingtotheirtransactionerrordensitygiven

te,whereatiandrdidenotethebytedi¼iiarrivaltimeandrelativedeadlineofthetransactionTi,respectively,andwherethetransactionwiththehighesttransactionerrordensityisprocessedfirst.

NotethatHEFandHEDFcannotbeusedinthecasewhenerrorfunctionsfortransactionsarenotavailableastheyare

Abstract—Real-time applications such as e-commerce, flight control, chemical and nuclear control, and telecommunication are becoming increasingly sophisticated in their data needs, resulting in greater demands for real-time data services that are provided

AMIRIJOOETAL.:SPECIFICATIONANDMANAGEMENTOFQOSINREAL-TIMEDATABASESSUPPORTINGIMPRECISECOMPUTATIONS309

error-cognizantandrequireknowledgeoftei.Forallthreebasicschedulers(EDF,HEF,andHEDF),themandatorysubtransactionshavehigherprioritythantheoptionalsubtransactionsand,hence,arescheduledbeforethem.

4.4QoSControllers

Dependingonthealgorithmsused,weapplydifferentfeedbackcontrolloopstocontrolQoTinthepresenceofunpredictableworkloadandinaccurateexecutiontimeestimates.PC-MPUemploysoneutilizationcontrollerandtwomisspercentagecontrollers,i.e.,onecontrollertoadjusttheutilizationuaccordingtoareferenceurandtwocontrollerstoadjustmMandmOaccordingtothereferences

mMmakerandmO

unpredictabler,respectively.TransactionsinRTDBsoftenabortsorrestartsduetodataandresourceconflicts.Further,theexecutiontimeofthetransactionsdependsontheirdataneeds,whichmayvaryovertime.Thismakesthedeadlinemisspercentagespronetoovershoot.ToavoidovershootsgreaterthanMp,theloadofthesystemisconstantlychangedaccordingtoalinearincrease/exponentialdecreasescheme.Initially,theutiliza-tionreferenceurissettoul.Aslongasthemisspercentagesarebelowtheirreferences,urisincreasedbyacertainstep.Assoonasoneofthemisspercentagesisaboveitsreference,ururðkþ1Þ¼urðkÞþisureducedexponentiallyaccordingto

l

ð%Þ,whereurðkþ1Þisthenewutiliza-tionreference.Thisway,wearecertainthatthesystemisnotunderutilized,while,atthesametime,greatdeadlinemissratioovershootsareavoided.Thisapproachisself-adaptinganddoesnotrequireanyknowledgeabouttheunderlyingruntimeestimates.PC-MPusestwodeadlinemisspercentagecontrolloops,oneforeachofthecontrolledvariablesmMandmO.ThealgorithmsPC-ATEHEFandPC-ATEHEDFuseasingleaveragetransactionerrorcontrollooptocontrolate(i.e.,thecontrolledvariable).Here,ateismonitoredandfedintothecontroller,whichcomputes lERaccordingtoateandater.

Usingseveralcontrollersraisesthequestionofintegra-tionofthesignalsfromeachcontroller.IncasePC-MP,wheremisspercentagecontrollersareused,weneedtointegratethesignalsfromthemandatoryandtheoptionalsubtransactionmisspercentagecontrollers.Further,inPC-MPU,whereacombinationofmisspercentageandutilizationcontrollersisused,anintegratedsignalfromboththemisspercentageandtheutilizationcontrollersiscomputedandreturned.Let lMdenotethecontrolsignalcomputedbythemMcontroller, lOdenotethecontrolsignalcomputedbythemOcontroller,and ludenotethecontrolsignalcomputedbytheucontroller.Theintegratedcontrolsignalfrombothmissratiocontrollers lMPiscomputedasfollows:Ifbothmisspercentagecontrolsignalsarenegative(i.e., lM<0^ lO<0),weset lMP¼ lMþ lOtothesumofbothcontrolsignals.Thisisnecessarysincebothmisspercentagesareabovetheirreferencesandbothsignalsmustbeconsideredtocompen-sateformisspercentageovershoots.Iftheabovedoesnothold,weset lMP¼minð lM; lOÞtotheminimumofthecontrolsignals.Ifoneofthecontrolsignalsisnegative(duetoanovershoot),wereturnthenegativeonetoreducethemisspercentageofthecorrespondingsubtransactiontype.Ifbotharepositive,theminoperatorprovidesasmooth

transitionbetweenlowandhighmisspercentagesamongmandatoryandoptionalsubtransactions[11].Inthecasewhenonlymisspercentagecontrollersareused,weset lERto lMP.However,whenautilizationcontrollerisusedaswell,wederive lERbytakingtheminimumof lMPand lu.Thisisnecessaryforsimilarreasonsasthosementionedabove.

4.5QoDManagementAlgorithms

Werecallthatsettingmdeðkþ1ÞgreaterthanmdeðkÞresultsinmorediscardedupdatetransactionsand,hence,adecreaseinupdatetransactionload.Similarly,settingmdeðkþ1ÞlessthanmdeðkÞresultsinfewerdiscardedupdatetransactionsand,hence,anincreaseinupdatetransactionload.Tocomputemdeðkþ1Þgivenacertain lERðkÞ,weuseafunctionfð lERðkÞÞthatreturns,basedon lERðkÞ,thecorrespondingmdeðkþ1Þ.Thefunctionfholdsthefollowingproperty:If lERðkÞislessthanzero,thenmdeðkþ1Þissetsuchthatmdeðkþ1ÞisgreaterthanmdeðkÞ,i.e.,QoDisdegraded.Similarly,if lERðkÞisgreaterthanzero,thenmdeðkþ1Þissetsuchthatmdeðkþ1ÞislessthanmdeðkÞ,i.e.,QoDisimproved.Wewilldiscussthefunctionfinmoredetaillaterinthissection.

ThealgorithmsPC-MPUandPC-MPcontrolQoTbymonitoringmM,mO,anduandadjustingmdesuchthatagivenQoSspecificationaccordingtoQoSspecificationtypeAissatisfied.Here,weuseEDFasabasicscheduler.ThealgorithmsPC-ATEHEFandPC-ATEHEDFareerror-cognizantandcontrolQoTbymonitoringateandadjustingmdesuchthataQoSspecificationintermsofQoSspecificationtypeBissatisfied.Furthermore,PC-ATEHEFandPC-ATEHEDFaredesignedtoenhanceQoSfairnessamongtransactions(i.e.,decreasethedeviationinteiamongadmittedtransactions).WeusethesamefeedbackcontrolpolicyforPC-ATEHEFandPC-ATEHEDF,butusedifferentbasicschedulers,i.e.,PC-ATEHEFschedulesthetransactionsusingHEFandPC-ATEHEDFschedu …… 此处隐藏：5661字，全部文档内容请下载后查看。喜欢就下载吧 ……