Guaranteeing real-time requirements with resource-

GuaranteeingReal-TimeRequirementswithResource-BasedCalibrationofPeriodicProcessesRichardGerberDepartmentofComputerScienceUniversityofMarylandCollegePark,[e-mail].(MS:7L-802)MountainView,[e-mail]tofComputerScienceConcordiaUniversityMontreal,[e-mail]ftwareEngineering,21(7),July1995AbstractThispaperpresentsacomprehensivedesignmethodologyforguaranteeingend-to-endre-quirementsofreal-timesystems.Applicationsarestructuredasasetofprocesscomponentsconnectedbyasynchronouschannels,inwhichtheendpointsarethesystem’sexternalinputsandoutputs.Timingconstraintsarethenpostulatedbetweentheseinputsandoutputs;theyexpresspropertiessuchasend-to-endpropagationdelay,temporalinput-samplingcorrelation,andallowableseparationtimesbetweenupdatedoutputvalues.Theautomateddesignmethodworksasfollows:Firstnewtasksarecreatedtocorrelaterelatedinputs,andanoptimizationalgorithm,whoseobjectiveistominimizeCPUutilization,transformstheend-to-endrequirementsintoasetofintermediaterateconstraintsonthetasks.Ifthealgorithmfails,arestructuringtoolattemptstoeliminatebottlenecksbytransformingtheapplication,whichisthenre-submittedintotheassignmentalgorithm.Thenalresultisaschedulablesetoffullyperiodictasks,whichcollaborativelymaintaintheend-to-endconstraints.ThisresearchissupportedinpartbyONRgrantN00014-94-10228,NSFgrantCCR-9209333,andNSFYoungInvestigatorAwardCCR-9357850.Anearlierversionofthispaperappearedbythetitleof\GuaranteeingEnd-to-EndTimingConstraintsbyCalibratingIntermediateProcesses,inpreliminaryformintheProceedingsofIEEEReal-TimeSystemSymposium,(December1994).11IntroductionMostreal-timesystemspossessonlyasmallhandfulofinherenttimingconstraintswhichwill\makeorbreaktheircorrectness.Thesearecalledend-to-endconstraints,andtheyareestablishedonthesystems’externalinputsandoutputs.Twoexamplesare:(1)Temperatureupdatesrelyonpressureandtemperaturereadingscorrelatedwithin10ms.(2)Navigationcoordinatesareupdatedataminimumrateof40ms,andamaximumrate80ms.Butwhilesuchend-to-endtimingparametersmayindeedbefewinnumber,maintainingfunction-allycorrectend-to-endvaluesmayinvolvealargesetofinteractingcomponents.Thus,toensurethattheend-to-endconstraintsaresatised,eachofthesecomponentswill,inturn,besubjecttotheirownintermediatetimingconstraints.Inthismannerasmallhandfulofend-to-endconstraintsmay{inevenamodestsystem{yieldagreatmanyintermediateconstraints.Thetaskofimposingtimingparametersonthefunctionalcomponentsisacomplexone,anditmandatessomecarefulengineering.Considerexample(2)above.Inanavionicssystem,a\naviga-tionupdatemayrequiresuchinputsas\currentheading,airspeed,pitch,roll,etc;eachsampledwithinvaryingdegreesofaccuracy.Moreover,theseattributesareusedbyothersubsystems,eachofwhichimposesitsowntolerancetodelay,andpossessesitsownoutputrate.Further,thenav-igationunitmayitselfhaveotheroutputs,whichmayhavetobedeliveredatratesfasterthan40ms,orperhapsslowerthan80ms.Andtotopito,subsystemsmaysharelimitedcomputerresources.Agoodengineerbalancessuchfactors,performsextensivetrade-oanalysis,simulationsandsensitivityanalysis,andproceedstoassigntheconstraints.Theseintermediateconstraintsareinevitablyontheconservativeside,andmoreover,theyareconveyedtotheprogrammersintermsofconstantvalues.Thusascenariolikethefollowingisoftenplayedout:ThedesignengineersmandatethatfunctionalunitsA,BandCexecutewithperiods65ms,22msand27ms,respectively.Theprogrammerscodeupthesystem,andndthatCgrosslyover-utilizesitsCPU;further,theydiscoverthatmostofC’soutputsarenotbeingreadbytheothersubsystems.Andso,theygobacktotheengineersand\negotiatefornewperiods{forexample60ms,10msand32ms.Thisprocessmaycontinueformanyiterations,untilthesystemnallygetsfabricated.Thisscenarioisduetoasimplefact:theend-to-endrequirementsallowmanypossibilitiesfortheintermediateconstraints,andengineersmakewhattheyconsidertobearationalselection.However,thebasisforthisselectioncanonlyincluderoughnotionsofsoftwarestructuringandschedulingpolicies{afterall,manytimesthehardwareisnotevenfabricatedatthispoint!OurApproach.Inthispaperwepresentanalternativestrategy,whichmaintainsthetimingcon-straintsintheirend-to-endformforaslongaspossible.Ourdesignmethoditerativelyinstantiatestheintermediateconstraints,allthewhiletakingadvantageoftheleewayinherentintheend-to-endconstraints.Iftheassignmentalgorithmfailstoproduceafullsetofintermediateconstraints,po-tentialbottlenecksareidentied.Atthispointanapplicationanalysistooltakesover,determinespotentialsolutionstothebottleneck,andifpossible,restructurestheapplicationtoavoidit.The1resultisthenre-submittedintotheassignmentalgorithm.DomainofApplicability.Duetothecomplexityofthegeneralproblem,inthispaperweplacethefollowingrestrictionsontheapplicationsthatwehandle.Restriction1:Weassumeourapplicationspossessthreeclassesoftimingconstraintswhichwecallfreshness,correlationandseparation.Afreshnessconstraint(sometimescalledpropagationdelay)boundsthetimeittakesfordata