Model-Driven Resource Management for Distributed Real-Time and Embedded Systems

Real-TimeandEmbeddedSystems

ChangLiu,DavidFleeman,EricAber,LonnieWelch,andDavidJuedes

CenterforIntelligent,DistributedandDependableSystemsSchoolofElectricalEngineeringandComputerScience

RussCollegeofEngineeringandTechnology

OhioUniversity

Athens,Ohio45701,U.S.A.

liuc@ohio.edu

http://ace.cs.ohiou.edu/~changliu

Abstract.Weproposeamodel-drivenresourcemanagementtechniquedesignedforonlineresourcemanagementofdistributedreal-timeandembeddedsystems.WehaveimplementedthistechniqueintheQARMAresourcemanagerandrelatedde-signtools.ThispaperdescribesavisualmodelingtoolusedbyQARMA,thespeci-ficationlanguagesitgenerates,aswellasQARMA’sunderlyingmodelandsoftwarearchitecture.

1Introduction

Weaddresstheproblemofconductingonlineresourcemanagementfordistributedreal-timeandembedded(DRE)systems[9].InDREsystems,typically,multipledistributedapplicationsworktogethertoprocessreal-timetasks.Eachapplicationrequirescertainamountofresourcestocompleteitsdesignatedtask.Someapplicationsaredesignedtousedifferentamountsofresourceswhentherequirementonitsperformanceandqualitychanges.Suchapplicationsaresometimescalledflexibleapplications[7,Chapter10].WhensuchapplicationsarepresentinDREsystems,itispossibletoadjustresourceallocationatruntimesothattheoverallsystemswithfixedamountofresourcescanperformbetterindifferentsituations.ThegoalofonlineresourcemanagementforDREsystemsistomakeappropriateadjustmenttoresourceallocationatappropriatetimesothattheoverallsystemprovidesatisfactorybenefitstoitsusers.

Weadoptamodel-drivenapproachtoaddressthisproblem.TheDREsystemmodelsdescribedin[12,13],onwhichourworkisbased,showedthataclearly-definedunderlyingmodelforboththeDREsystemanditsenvironmentisthebasisofresourceallocationalgorithms.Inaddition,withamodel,wecan1)checkthemodelbeforethesystemisbuilt;2)providebasisforsystemcertificationafterthesystemisimplemented;and3)pre-computenecessarydatasothattheresourcemanagercanperformbetteratruntime.

WedesignaQuality-basedAdaptiveResourceManagementArchitecture(QARMA)torealizeourresourcemanagementtechnique[3].TheQARMAResourceManager,whichisimplementedinthecontextofCORBA,hasthreemajorcomponents:theResourceMan-agementService,theSystemRepositoryService,andtheEnactorService.TheSystemRepositoryServiceprovidesastorageforbothstaticanddynamicinformationaboutcom-putingresourcesandsoftwareapplicationsinanDREsystem.Inotherwords,thesystemrepositorycontainsallconcreteinformationoftheDREsystemwithrespecttothesys-temmodel.TheResourceManagementServicemakesdecisiononresourceallocationbasedontheinformationinthesystemrepository.TheEnactorServicecarriesouthigh-levelQARMAdecisionsbyinvokinglower-levelenactorsprovidedbyCORBAmiddlewareor

2Liuetal.

applicationsoftware.Fig.1depictstheQARMAresourcemanagementarchitectureaswellasasoftwareengineeringprocessthatadoptsQARMA,whichisexplainedingreaterdetailinSec.4.

QARMA󰀀Specification󰀀Software󰀀Developer󰀀QARMA Modeling Tool󰀀QARMA󰀀Resource󰀀Management󰀀System󰀀Repository󰀀Enactor󰀀DRE System󰀀Fig.1.AnoverviewoftheQARMAresourcemanagementarchitectureandprocess.

2AnDRESystemModelforDynamicResourceManagement

TheresourceallocationofastaticDREsystem,whichdoesnotchangeovertime,canbemodeledasathree-tupleDREs=(R,S,A)where

–Risasetofresourcesupplies,suchasCPUs,memory,andnetworkconnections;–Sisasetofsoftwareapplicationsthatdemandresources;and

–A={a|a∈R×S×Real},whereRealisthesetofrealnumbers,isasetofquan-tifiedmappingsbetweenresourcesandsoftwareapplicationsthatreflecttheresourceallocation.AdynamicDREsystem,whoseresourceallocationcouldchangeatruntime,canbemodeledasaseven-tupleDREd=(R,S,P,AttrType,Attr,A,B)where––––

Risasetofresourcesupplies;

Sisasetofsoftwareapplicationsthatdemandresources;Pisasetofsequencesofsoftwareapplications;

AttrTypeisasetofsymbolicnamesofattributesthatdescriberesource,softwareap-plication,andpathpropertiesthatcouldbeofinteresttoaresourcemanager;

–Attr:{R∪S∪P}×AttrType→R∪S∪Real∪{unknown,invalid},whereunknownandinvalidaretwopredefinedsymbols,isafunctionthatdeterminesthevaluesofresource,softwareapplication,orpathattributes;

Model-DrivenResourceManagementforDRESystems3

–A={a|a∈R×S×Real}isasetofquantifiedmappingsthatreflecttheresourceallocation;and

–Bisafunctionthatmapsaresourceallocationtoarealnumber,whichrepresentstheoverallbenefitsprovidedbytheDREsystemtoitsusers[2,1].AdynamicDREsystemmodelmustincludethesetofresourceandsoftwareapplicationattributesbecausetheyspecifyresourcesuppliesanddemandsinthesystemandarethebasisofonlineresourceallocationdecisions.Pathattributestypicallyrepresentend-to-endQoSrequirements.

GivenadynamicDREsystemmodel,onecanpotentiallyperformthefollowingthreetasksatdesigntime:

1.Checkresourceallocations,identifyfeasibleones,anddetectinfeasibleones;

2.Computeinformationthatmaybeneededbytheresourcemanageratruntime;and3.Verifyalgorithmsandstrategiesusedbytheresourcemanager,whichhelpssystemcertificationofDREsystemswithdynamicresourcemanagement.Next,weuseanexampletoillustratehowtoperformthefirsttask.

Aresourceallocationisinfeasibleifmoresoftwareapplicationsareassignedtoasingleresourcethanitiscapabletoservice.Forexample,ifthreeapplicationsapp1,app2,andapp3areassignedtothesamesingle-processorcomputer.Allthreeapplicationsareperiodicalandhavethesameperiodof30seconds.Supposetheexecutiontimeofapp1is5seconds,app210seconds,andapp320secondswhentheyfunctionattheirrespectivedesirableservicelevels.Apparently,thisallocationisinfeasiblebecausethetheoreticalCPUworkloadofthecomputerexceeds100%.

ThealgorithmforsimpleworkloadverificationisshowninAlgorithm1.ThecomplexityofthealgorithmisO(|R|×|S|).Thisalgorithmassumesthatperiodandexecution

1

2

Thisalgorithmcanbeeasilyextendedtocopewithsoftwareapplicationswithmultipleservicelevels.ThecomplexityoftheextendedalgorithmisstillO(|R|×|S|).SpecIntandSpecFpareusedtospecifyCPUspeeds.

4Liuetal.

Require:DREd;specintisspecifiedforeachCPU;periodandexecution

8:9:10:11:12:13:14:15:16:17:18:

time,z)∈DREd.Attrthen

ifthereexiststsuchthat(r,s,t)∈DREd.Athen{applicationsisassignedtoCPUr}

w⇐w+z/yendifendifendifendfor

ifw>1then{workload>100%}f⇐Falseendifendifendfor

3.2.1,java

3

SPECstandsfortheStandardPerformanceEvaluationCorporation.Seehttp://www.spec.org/.

Model-DrivenResourceManagementforDRESystems5

multipledimensionalrelationships.ToovercomethisdeficiencyoftheQARMAspecificationlanguage,wedeveloptheQARMAvisualmodelingtoolthatenablesDREsystemdesignerstographicallyconstructandexamineQARMAmodels,whichcanbeencodedinQARMAspecificationsautomaticallygeneratedbytheQARMAmodelingtool.

TheQARMAvisualmodelingtoolisbasedontheGenericModelingEnvironment(GME)[6,5],ageneral-purpose,configurablemodelingenvironmentwithamodular,ex-tensiblearchitecturethatenablesuserstocreatedomain-specificmodelingtools.VEST(VirginiaEmbeddedSystemsToolkit),aGME-basedtool,isacustomizedtoolkitforcon-structingandanalyzingcomponent-basedDREsystems[10,11].VESTprovidesalibrarythatsupportsdescriptionsofhardwarecomponentsandnetworks.TheQARMAmodelingtoolextendstheVESTlibraryand,amongotherenhancements,addssupportforthede-scriptionsofsoftwareapplicationsandpaths.TheQARMAtoolenablesanDREsystemdesignertocaptureinagraphicmodelallaspectsofaDREsystemthatisofinteresttotheQARMAresourcemanager.

Fig.1containsascreenshotoftheQARMAvisualmodelingtool,whichprovidesthefollowingmain“buildingblocks”initslibrary:–hardware

hostmodelsuni-processorcomputers;switchmodelsnetworkswitches;processormodelsCPUs;

memorymodelsmainmemoryinahostcomputer;

networkinterfacemodelsnetworkinterfacesinahostcomputer.–software

pathsconsistsasequenceofsoftwareapplicationswhichperformssystem-leveltask

together;

softwareapplicationsmodelsindividualsoftwareapplicationsintheDREsystem;extrinsicattributesmodelspropertiesoftheenvironment;

serviceattributesmodelsadjustablepropertiesofsoftwareapplications;

benefittablesmodelshowoverallsystembenefitsareperceivedbyDREsystemusers.InasoftwareengineeringprocessthatadoptsQARMA,theDREsystemdesignercon-structsaQARMAmodelinteractively.Hestartswitheitheranemptymodelorasimilarmodelcopiedfromapreviousproject.Hecanthen––––

add“buildingblocks”inthelibrarypiecebypiecetothemodel,create,adjust,ordeleteassociationsbetweenelementsinthemodel,deleteelementsfromthemodel,or

specifyormodifypropertiesofanelement.

Hecanvisuallyexaminethemodelatanytimeduringtheprocess.Asshowninfig.1,whenheissatisfiedwiththemodel,hecaninvokethespecificationgenerationfeatureandinstructthetooltoautomaticallygenerateaQARMAspecificationofthemodel,whichcanbeprovidedtotheQARMAresourcemanagerlater.

TheQARMAmodelingtoolenablesDREsystemdesignerstovisuallyconstructDREsystemmodelsusingexisting“buildingblocks”.ThisismoreefficientthaneditingQARMAspecificationtextdirectly.Furthermore,theQARMAmodelingtoolguaranteesthatthegeneratedQARMAspecificationsareerror-free,whichfurtherimprovesdesignerefficiency.VisualmodelingtoolssuchasUML-MAST[8,4]enablesvisualmodelingandanalysisofreal-timesystems.Theyarepuredesign-timetoolsanddonothaveaninterfacewithruntimemechanisms.TheQARMAmodelingtool,ontheotherhand,doesinterfacewith

6Liuetal.

theruntimeQARMAresourcemanagerthroughtheQARMAspecification,whichistheoutputoftheQARMAtool.TheQARMAspecificationwillbereadinbytheQARMAresourcemanagerandstoredinthesystemrepository.TheseinformationprovidesthebasisforQARMA’sdecisionmakingatruntime.

5Summary

Inconclusion,ourmodel-driventechniqueforonlineresourcemanagementofDREsystemsconsistsofamodelingtool,aspecificationlanguage,andasystemarchitecturethathasbeenimplementedinthecontextofCORBA.ThisapproachenablesDREsystemdeveloperstointuitivelyconstructsystemmodels,automaticallygeneratesystemresourcespecifications,andusetheQARMAresourcemanagertoimproveDREsystemssothattheyaremoreflexible,performbetterindifferentsituationswithfixedamountofresources,andprovidemoreoverallbenefitstoDREsystemusers.

Wehaveappliedourmodel-driventechniqueonareal-worldexampleandobtainedsatisfactoryexperimentalresults,whichwillbereportedinadifferentpaperduetospaceconstraints.

References

1.D.Andrews,R.Vemuri,D.Chelberg,D.Fleeman,D.Parrott,L.Welch,andS.Brandt.Aframeworkforusingbenefitfunctionsincomplexreal-timesystems.JournalofParallelandDistributedComputingPractices,toappear.

2.D.Andrews,L.Welch,D.Chelberg,andS.Brandt.Aframeworkforusingbenefitfunctionsincomplexrealtimesystems.Inthe10thWorkshoponParallelandDistributedReal-TimeSystems(WPDRTS’2002),April2002.

3.D.Fleeman,M.Gillen,A.Lenharth,M.Delaney,L.Welch,D.Juedes,andC.Liu.Quality-basedadaptiveresourcemanagementarchitecture(QARMA):ACORBAresourcemanage-mentservice.InThe12thInternationalWorkshoponParallelandDistributedReal-TimeSystems(WPDRTS’2004),SantaFe,NewMexico,U.S.A.,April26-27,2004.

4.M.GonzlezHarbour,J.J.GutirrezGarca,J.C.PalenciaGutirrez,andJ.M.DrakeMoy-ano.MAST:Modelingandanalysissuiteforreal-timeapplications.Inthe13thEuromicroConferenceonReal-TimeSystems(ECRTS’01),Delft,TheNetherlands,June13-15,2001.5.G.Karsai,M.Maroti,A.Ledeczi,J.Gray,andJ.Sztipanovits.Compositionandcloninginmodelingandmeta-modeling.IEEETransactionsonControlSystemTechnology,March2004.6.A.Ledeczi,M.Maroti,A.Bakay,G.Karsai,J.Garrett,C.ThomasIV,G.Nordstrom,J.Sprin-kle,andP.Volgyesi.Thegenericmodelingenvironment.InWorkshoponIntelligentSignalProcessing,Budapest,Hungary,May2001.

7.J.W.S.Liu.Real-TimeSystems.PrenticeHall,2000.

8.J.L.MedinaPasaje,M.GonzlezHarbour,andJ.M.Drake.MASTreal-timeview:AgraphicUMLtoolformodelingobject-orientedreal-timesystems.Inthe22ndIEEEReal-TimeSystemsSymposium(RTSS’01),pages245–256,London,UK,December3-6,2001.

9.B.Ravindran,L.R.Welch,andB.A.Shirazi.Resourcemanagementmiddlewarefordynamic,dependablereal-timesystems.TheJournalofReal-TimeSystems,20:183–196,2000.

10.J.Stankovic.VEST:Atoolsetforconstructingandanalyzingcomponentbasedembedded

systems.Springer-VerlagLectureNotes,pages390–402,October2001.

11.J.A.Stankovic,R.Zhu,R.Poornalingam,C.Lu,Z.Yu,M.Humphrey,andB.Ellis.VEST:An

aspect-basedcompositiontoolforreal-timesystems.InReal-TimeApplicationsSymposium,May2003.

12.L.R.Welch,B.Ravindran,B.A.Shirazi,andC.Bruggemen.Specificationandmodeling

ofdynamic,distributedreal-timesystems.Inthe19thIEEEReal-TimeSystemsSymposium(RTSS’98),pages72–81,Madrid,Spain,December2-4,1998.

13.L.R.Welch,P.V.Werme,B.A.Shirazi,C.D.Cavanaugh,L.Fontenot,E.-N.Huh,and

M.W.Masters.Loadbalancingfordynamicreal-timesystems.ClusterComputing,3(3):125–138,2000.