HardReal-TimeSystems
By:JoséJavierGutiérrezGarcía,andMichaelGonzálezHarbourDepartamentodeElectrónica,UniversidaddeCantabria,SPAIN
Abstract
Inthispaperwepresentastudyoftheeffectscausedindistributedreal-timesystemsbyjitterintheactivationoftasksandmessages.Weshowthatalthoughjitterhasusuallyasmallimpactintheschedulabilityofsingle-processorsystems,indistributedarchitecturestheworst-caseresponsetimesaresignificantlydelayed.Reducingoreliminatingjitterinthesesystemscanincreasetheschedulabilityofthesystemupto50%morethanwhenjitterispermitted.Jittercanbepreventedbyusingabandwidth-preservingschedulingalgorithmsuchasthesporadicserver.Sincethiskindofschedulingpolicyisnotdesignedforcommunicationnetworks,inthispaperwedescribehowtoadaptandimplementthesporadicserveralgorithmforcommunicationnetworks.Usingthesporadicserverbothintheprocessorsandnetworks,wecanbuilddistributedsystemswithupto100%utilizationoftheCPUsandcommunicationresources,whilestillguaranteeingthathardreal-timerequirementsaremet.
easiertomaintain,upgrade,andadaptquicklytoevolvingmanufacturingneeds.Mostofthedistributedarchitecturesusedcurrentlyinindustrialautomationonlyhavesoftreal-timerequirementsbecauseofthetechnologicallimitationsimposedbytheinterconnectionnetworksandsoftwaretechnology.However,thereisgreatinterestinbeingabletohandlehardreal-timerequirementsacrosstheentiresystem,becausethiswouldaddmoreflexibilitytothesystemandcouldbeusedtooptimizetheproductivityevenfurther.
Oneproblemthatisknowntoaffecttheschedulability(i.e.,themaximumutilizationatwhichadistributedsystemcanrunwhileguaranteeingthatallhardreal-timerequirementsaremet)isdeferredactivationorjitter.Theobjectivesoftheworkpresentedinthispaperaretocarryoutaquantitativestudyoftheeffectsofjitterintheschedulabilityofdistributedreal-timesystems,andprovidesolutionstominimizethesenegativeeffects.InSection2wediscussthemodelofthedistributedreal-timesystemthatweconsider,andwepointtothetechniquesusedtoanalyzeitstimingbehavior.Section3showstheresultsofthestudyoftheeffectsofjitter.Section4suggeststheuseofthesporadicservertoeliminatethenegativeeffectsofjitter.Section5providesdetailsoftheimplementationofthisschedulingpolicyinthecommunicationssubsystem.Finally,Section6givesourconclusions.
1.Introduction
Distributedreal-timesystemshaveanincreasingimportanceintoday’scontrolsystems,sincelow-costnetworkingfacilitiesallowtheinterconnectionofmultipledevicesandtheircontrollersintoasinglelargesystem.Thisarchitectureisveryfrequentinindustrialenvironmentsinwhichthewholeplantiscontrolledfromanintegratedsystem.Ahighdegreeofflexibilityisachievedintheconfigurationoftheplant,whichbecomes
_______________________
ThisworkhasbeensupportedinpartbytheComisiónInterministerialdeCienciayTecnologíaoftheSpanishGovernment,underGrantROB91-0288
2.Distributedsystemmodel
Thetypicalarchitectureinadistributedreal-timecontrolsystemconsistsofseveralprocessornodesinterconnectedthroughoneormoreinterconnectionnetworks.Thesystem’ssoftwareiscomposedofconcurrenttasksthatareoftenstaticallyallocatedtoprocessingnodes,becausetheeffectsofdynamicnode
allocationareverydifficulttopredictforhardreal-timesystems.Eachtaskmayexchangemessageswithothertasksinthesamenodeorindifferentnodes.Messagesexchangedwithintasksindifferentnodesarealsostaticallyallocatedtoaparticularnetwork.Tasksallocatedinthesamenodemayalsosharedataorresources,throughtheusualsynchronizationmechanismsusedinsharedmemorysystems.
Eachtaskinthesystemisactivatedbythearrivalofatriggeringeventthatmaybegeneratedbytheenvironment,atimer,orbythearrivalofamessagefromanothertask.Manyoftheseeventshaveanassociatedtimingrequirement,suchasanend-to-enddeadline,whichisthemaximumresponsetimeallowedfromthearrivalofaneventtothefinalcompletionoftheassociatedresponse.Eventsusuallyarriveinsequences,andeventswithharddeadlinesareusuallyperiodicorhaveaminimuminterarrivaltime.Duringtheexecutionoftheresponsetoanevent,asequenceofseveraltasksandmessagesmay,respectively,needtobeexecutedinoneormorenodes,ortransmittedacrossthenetworks.Othertimingrequirementsmayalsobeimposedonindividualactionswithintheresponse.
Inordertomakeitpossibletopredictworst-caseresponsetimes,wecanscheduletheactivitiesineachprocessingnodebyusingapriority-basedapproachthatallowsprocessingactivitieswithshorterdeadlinesbefore(atahigherpriority)activitieswithlongerdeadlines.Oneanalysistechniqueusedtoassesstheschedulabilityofthereal-timesystemiscalledRateMonotonicAnalysis(RMA)andiswelldefinedforsingle-processorsystems[4].TheRMAtechniquescanalsobeappliedtodistributedsystems[5][4][10]bymodelingeachnetworkasifitwereaprocessor,andeachmessageasifitwereatask.Prioritiescanbeassignedtotasksandmessagesinthesesystemsbyusinganoptimizationalgorithmthattriestooptimizeontheabilityofthedifferenttasksandmessagestomeettheirdeadlines[8][2].Theanalysistechniquestakeintoaccounttheeffectofjitterintheactivationofmessagesandtasks.Themainquestionthatweaddressinthefollowingsectionsishowmuchdoesjitterinfluencetheresponsetime,andhowcanwepreventitsnegativeeffects.
3.Effectsofjitterintheresponsetime
Amajorproblemthatappearsindistributedsystemsistheeffectofdeferredactivationoftasksormessages,alsocalledjitter.Theactivationtimeofmessagesgeneratedbytheexecutionofperiodictasksisnotperfectlyperiodic,butdependsonthecompletiontimeofthetriggeringtask,whichisvariable.Thesamehappenswithtasksactivatedfrommessages.Ingeneral,jitterinonetaskcausesdelayintheworst-caseresponsetimeoflowerprioritytasks.TheanalysisofasystemwithjitterisaddressedbyTindell[10].
Figure1showsanexampleoftheimportancethatjitterhasintheschedulabilityofahardreal-timedistributedsystem.TheaverageofthemaximumschedulableutilizationoftheCPUsandnetworksisplotted(withandwithoutjitter)asafunctionoftheratiodeadlines/periods(D/T)ofthedifferentresponsestotheeventsarrivingtothesystem.Thegraphsarebasedonanexamplesystemwith50periodictasksdistributedin8processors,and43periodicmessagessentthroughthreedifferentnetworks.Asanexample,themaximumutilizationforD/T=7isaround50%ifjitterispresent,andalmost100%whenjitterisavoided.Thesamekindofresultsisobtainedwithotherexamples.Wecanseethatthedifferencebetweenthetwographsislargerforlongerend-to-enddeadlines.Longdeadlinesareaverycommonsituationindistributedsystems,wherearesponsethatexecutesindifferentresources(CPUsandnetworks)hasalocaldeadlineofoneperiodineachresource,andthusaglobaldeadlineequaltotheperiodmultipliedbythenumberofdifferentresourcesused.
Thisnegativeeffectonschedulabilitycanbeavoidedbycalculatingtheworst-caseresponsetimeofataskthattriggerseitheramessageoranothertask,andcreatingahighpriorityagenttaskthatreleasesthemessageortaskwithjitteronlyaftertheworst-caseresponsetimeoftheoriginaltaskhaselapsed.However,fromasoftwareengineeringperspective,thistechniqueisnobetterthanthetraditionalcyclicexecutiveapproachinwhichthesoftwaredesignwasconstrainedbytimingrequirements.Inthispaperweproposetheuseofthesporadicserverschedulingpolicy[6]toeliminatetheproblemofjitterintheresponsetime,butpreservingthesoftwareengineeringprincipleofseparationofconcernsbetweenlogicalandtimingrequirements.
Thesporadicserverschedulingpolicywasdesignedtoscheduletheexecutionofaperiodicactivitiesinahardreal-timesystem.Thesporadicserverreservesacertain
amountofexecutiontime(theexecutioncapacity)forprocessingaperiodicactivitiesatthedesiredprioritylevel.Whenanaperiodiceventarrives,itactivatestheexecutionofanaperiodictask.Thearrivaltimeoftheeventisrecordedforfuturereference.Asthetaskisprocessed,theexecutiontimespentissubtractedfromthecapacity,untilthecapacitygetsexhausted.Atthispoint,executionoftheaperiodictaskissuspended.Eachportionofexecutioncapacitythatisconsumedisreplenished,i.e.,addedbacktotheavailablecapacity,atalatertime.Thistimeisequaltotheinstantwhentheportionofconsumedcapacitybecameactive(usuallytheinstantwhenthetriggeringeventarrived),plusafixedtimecalledthereplenishmentperiod.Insomeimplementations,theaperiodictaskcancontinueexecutingatabackgroundprioritylevel.
Withthesporadicserverpolicy,theeffectsofprocessingaperiodicactivitiesusingasporadicservercanbenoworsethantheequivalenteffectofaperiodictaskwithaperiodequaltothereplenishmentperiodicandanexecutiontimeequaltotheinitialexecutioncapacityofthesporadicserver.Supposeaperiodictaskthatsuffersfromdeferredactivation.Ifthistaskisscheduledusingasporadicserverwithareplenishmentperiodequaltothetask’speriodandaninitialcapacityequaltothetask’sworst-caseexecutiontime,thenitseffectsonlowerprioritytaskscannotbeworsethanthatofanequivalentperiodictask,withnodeferredexecution.Theworst-casecompletiontimeofthetaskitselfisequaltotheworstpossibledeferralintheactivation,plustheworst-casecompletiontimeofthepurelyperiodictask,whichiseasilyobtainedfromtheusualRMAschedulabilityanalysis.
4.Optimizedschedulingincommunication
networks
Thesporadicservercanbeadaptedtoschedulemessagetrafficinanetwork.Mostofthecurrentlyavailablenetworksandnetworkprotocolsdonotusepriorities,andmanyhaveunpredictableworst-casetransmissiontimes.However,somenetworkshavebeenusedinhardreal-timecommunications,suchasTDMA[10],tokenrings[7][1],theCANbus[9],etc.Networkprotocolscanbeimplementedwithmessageprioritiesinordertoincreasethemessageschedulableutilization.Forexample,theCANbususesthemessageidentifiersasa
meanstocontrolaccesstothebusandalsoasthemessagepriorities.
Anetworklayerwithprioritypreemptivemessagescanbeimplementedbydividingmessagesintofixed-sizepackets.Eachmessagecarriesanetwork-widepriority,andallofitspacketsareassignedthesamepriority.Thenetworkschedulerhasateachnodeapriorityqueueofmessagepacketstobetransmitted(Figure2-a).Anindividualpacketisnon-preemptible(i.e.,onceitstransmissionstartsnohighprioritymessagescaninterruptit),buthigherprioritypacketsarealwaysinsertedbeforelowerprioritypacketsatthescheduler’squeue.Inthisway,highprioritytasksdonotgetblockedbythetransmissionofapotentiallyverylongmessagefromalowerpriorityactivity.
Inthispriorityschedulingcontext,itiseasytoadaptthesporadicserverconcept(Figure2-b).Foragivensequenceofmessages,thesporadicserverparametersaretheinitialcapacity,ornumberofpacketsthatmaybetransmittedatthenormalpriority,andthereplenishmentperiod.Thenetworkschedulercantransmitasmanyasthereservednumberofpacketsatthenormalpriority.Foreachofthesepacketstransmitted,thecapacitytotransmitanotherpacketisreplenishedonereplenishmentperiodafterthepacketwasqueued.
Inthesporadicserverschedulerfortasks,weassociateonesporadicservertoeachtask.However,formessagesthereisnosuchconceptasatask,whichwrapsmultipleresponsesassociatedtoaparticulareventsequence;messagesarriveatthecommunicationssubsystemwithnoapparentrelationtootherpreviousmessages.Asaconsequence,wehavedefinedeachsporadicserverschedulertoworkoveranymessageofaparticularprioritylevel.Thismeansthatasufficientnumberofprioritiesisneededtoprovideeachmessagesequencewithadifferentprioritylevel.
Figure2-bshowsthegeneralstructureofaconceptualsporadicservermessagescheduler.Thesporadicserverhasthesameinterfaceastheconventionalprioritymessagescheduler(Figure2-a)withtheadditionofanoperationtosettheattributesofeachsporadicserver.Theseattributesare:
•Initialcapacity:numberofmessagepacketsthatmaybetransmittedatthenormalprioritywithoutrestriction
•Replenishmentperiod.Timethathastoelapsefromtheinstantwhenamessagepacketwasqueueduntiltheserverregainsthecapacityconsumedbythe
Figure1.Effectsofjitteronthemaximumschedulableutilizationtransmissionofthatpacket.
Foreachprioritylevel,andthusforeachsporadicserver,thereisaper-prioritystatethatisdefinedbythefollowingparameters:
•ActualCapacity.Atanyinstant,itisthenumberofmessagepacketsthatmaybetransmittedattheassociatedpriority.Initially,theactualcapacityisequaltotheinitialcapacity.
•Activationtime.Thisparameterissetequaltothecurrenttimeattwosituations:whenmessagepacketsoftheassociatedpriorityarequeuedtoasporadicserverwithanactualcapacitygreaterthanzeroandtherearenoothermessagesqueued;andalsowhenareplenishmentisexecuted(seedescriptionbelow).•UsedCapacity.Numberofmessagepacketsconsumed(i.e.setattheassociatedpriority)sincethelastrecordedactivationtime.Accordingtothestateofthequeueandthevalueoftheactualcapacity,asporadicservermaybeinthreedifferentstates:
•Idle:Nopacketsarequeuedforthatpriority
•Normal:Therearepacketsqueuedforthatpriorityandthecapacityisgreaterthanzero.
•Background:Therearepacketsqueuedforthatpriorityandthecapacityiszero.
Thereisaspecialobjectthatisresponsibleformanagingthereplenishmentoperationsforallthesporadicservers,whichiscalledthereplenishmentmanager.Ithasaqueueofpendingreplenishments,whicharesortedaccordingtotheirreplenishmenttime.Eachreplenishmentoperationstoredinthisqueuehasthefollowinginformation:
•Replenishmenttime.Itistheinstantatwhichareplenishmentexpires,i.e.whenaportionofconsumedcapacitycanbeaddedbacktotheactualcapacity.
•Replenishedcapacity.Itisthecapacitytobereplenished,innumberofpackets.
•Priority:Itistheprioritylevelthathastobereplenished.Theoperationsthatmaybeinvokedonthereplenishmentmanagerare:
•Scheduleareplenishment.Thisoperationconsistsofaddingareplenishmenttothereplenishmentqueue.Thereplenishmenttime,capacityandprioritymustbesuppliedbythecaller.
ApplicationNetwork LayerPriority SchedulerExtractPacketData LinkLayerPacketPriorityQueueSendMessageInsertPacketInitiateTransmissionTransportLayera) Priority message schedulerNetwork LayerSporadic Server SchedulerSetAttributesPacketPriorityQueueExtractPacketApplicationData LinkLayerSendMessageTransportLayerInsertPacketPer-PriorityStateReplenishmentManagerInitiateTransmissionb) Sporadic server message schedulerFigure2.StructureoftheNetworkMessageScheduler
•Executependingreplenishments.Thisoperationconsistsofextractingfromthereplenishmentqueueallthereplenishmentoperationsthathaveexpired(i.e.,whosereplenishmenttimeisbeforeoratthecurrenttime).Foreachreplenishmentoperation,thereplenishedcapacityisaddedtotheactualcapacityoftheassociatedpriority,andtheactivationtimeisrecorded.Ifthatactualcapacitywaszeroandthestateoftheassociatedsporadicserverwasbackground,itisswitchedtonormal.
Thebasicoperationsofthesporadicserverschedulerarethefollowing:
•Setattributes.Theinitialcapacityandreplenishmentperiodarestoredfortherequestedpriority
•Insert.Introduceamessagepacketintothequeueofthespecifiedpriority,inFIFOorder.Ifthestateoftheassociatedsporadicserverwasidle,itisswitched
tonormalorbackground(respectivelyforcapacity>0orcapacity=0).Ifthestateisswitchedtonormal,theactivationtimeisrecorded.
•Extract.Executesthependingreplenishments,andthenextractsamessagepacketfromthequeue.Thisoperationisusuallyinvokedfromthedatalinkdriver,toselectapackettobetransmitted.Thequeueissearchedforthefirsthighestprioritymessagepacketwhoseassociatedserverisinthenormalstate.Iftherearenopacketsinthenormalstate,thehighestprioritypacketinthebackgroundstateisextracted.Extractingapacketthatisinthenormalstateimpliesconsumingoneunitofactualcapacityand,iftheactualcapacitybecomeszero,orifthesporadicserverbecomesidle(becausetherearenomorepacketsqueuedatthatpriority),schedulingareplenishmentoperation.Thereplenishedamountisequaltotheusedcapacity,andthereplenishment
timeissettotherecordedactivationtimeplusthereplenishmentperiod.Extractingapacketthatisinthebackgroundstatedoesnotconsumeanycapacity(recallthatinthiscaseitisalreadyzero),andcanonlybedoneifnopacketisqueuedinaserverinthenormalstate.
5.Implementationofhardreal-timecommunicationswithoptimizedscheduling
5.1.Messagequeues
Wehaveimplementedahardreal-timecommunicationsystemthatusesthesporadicserverschedulingpolicy,inordertoproveitsimplementabilityusingcurrentnetworktechnology,andalsoasanexperimentaltoolwithwhichwecandofurtherresearchinthisarea.
TheimplementationhasbeendevelopedinAda,usingforthetransportlayertheinterprocesscommunicationinterfacespecifiedinthePOSIX.1bstandard[3].Thisinterfacedefinesmessagequeueoperationssuchassendorreceiveamessage,andopenorcloseamessagequeue.Eachmessagehasanassociatedprioritythatisusedtoqueuethemessageinpriorityorder.Althoughtheinterfacewasdesignedforasinglenode,we
haveimplementeditforadistributedsystem,inanetwork-transparentway.Thisintroducesahighdegreeofflexibility:Adataskscommunicatewitheachotherwithoutknowingifthecommunicationislocal,oracrossthenetwork;thisaspectisdeterminedatconfigurationtime,whenanoptimizationtechniquemaybeusedtoallocatetaskstonodesandmessagestonetworks.OurimplementationonlyusesacommonextensiontotheAda83language,whichistheCIFO3.0suspend/resumefacility(oralternativelydynamicpriorities),anditwillbecompletelyportableusingtheAda95features.
Themessageprioritiesareusedtoimplementapriority-preemptivemessageschedulerbasedonthetransmissionofbounded-lengthpackets.Thishardreal-timemessageschedulerhasbeenimplementedfortwokindsofinterconnectionnetworks:AVMEbus,inwhichsharedmemoryisusedtoimplementthetransmissionofmessagestoandfrommessagequeues,andpoint-to-pointnetworkssuchasseriallines(RS-232andRS-485).Twoormoreofthesenetworkscanbeusedinparallelinaheterogeneousconfiguration.
5.2.Operationsonremotemessagequeues
Whenthemessagequeuewhoseuseisrequestedisinanothernode,amessageissenttotheremotenodewith
Node 1UserTaskMessageQueueManagerNetworkNode 2ReceptionManagerMessageQueueSYNCHRONOUSTransmitReceiveReceptionManagerReceiveTransmitASYNCHRONOUSUserTaskMessageQueueManagerTransmitReceiveReceptionManagerMessageQueueFigure3.Modelsofoperationsonremotemessagequeuestheinformationthatisrequiredtoperformtheoperation.Insomecases,aresponsemessagewithadditionalinformationisrequired.Figure3showsahigh-levelmodelofoperationsaffectingmessagequeuesinremotenodes.Therearetwodifferentkindsofoperations:
•Synchronous.Thetaskthatinvokestheoperationissuspendedwaitingfortheresponsefromtheremotenode.Oncetheresponsearrives,thetaskmaycontinueexecuting.Anexampleofasynchronousremoteoperationisreceivingamessagefromaremotequeue.
•Asynchronous.Thetaskinvokingtheoperationdoesnotsuspend,andmaycontinueitsexecutionafterthecall.Anexampleissendingamessagetoaremotequeue.Thecommunicationnetworkisusedbothfortransmittingapplicationmessages,aswellasmessagesrequiredbytheimplementationofmessagequeues.Forexample,toreceiveanapplicationmessagefromaremotequeuewemustfirstsendamessagerequestingtransmission.Aprotocolhasbeendefinedtohandleallthedifferentkindsofapplicationandimplementationmessages.Allthesemessagesaredividedintopacketsfortransmissionacrossaspecificnetwork.Severalnetworksmaybeusedinparallel,buttheallocationofmessagequeuestonetworksisstatic,andisdeterminedatconfigurationtime.
5.3Implementationofthedatalinklayer
Wehaveimplementedadatalinklayerfortwokindsofnetworks:point-to-pointseriallines,andaVMEbus.Point-to-pointlinedriversareveryeasytoimplement,becausethereisnopriorityarbiterneeded.Thelinecanonlybeoperatedfromonesinglenode,andthereisnocontentionwithothernodes.Inthiscase,aconventionaldriver(i.e.,notbasedonpriorities)maybeused.
Theimplementationofthedatalinklayerismorecomplexinnetworksinwhichseveralnodesareabletoaccessthenetworkatthesametime.Inthesenetworks,thecontentionmustbesolvedbasedontheprioritiesofthemessagestobetransmitted.Forexample,intheCANbus,themessageidentifierisusedtoresolvecontentionandeffectivelyactsasamessagepriority.
Wehaveimplementedthedatalinklayerforreal-timecommunicationsacrossaVMEbus,whichisaverycommonbusinindustrialapplications.Inour
implementation,weusesharedmemorytoexchangemessagesbetweenthedifferentnodes.Transmissionisachievedbycopyingthepacketintoabufferlocatedinsharedmemory.Aglobaldatastructureiscreatedalsoinsharedmemorytostoretheinformationthatisrequiredtoimplementthepriority-basedarbitration.Althoughthisstructureisglobalitdoesnotrepresentamajorcontentionproblem,becausetheVMEbusitselfisalreadyaglobalresourcesharedbyallthenodesinthesystem.Accesstotheglobalcontrolstructureisprotectedthroughabussemaphore.Theinformationstoredinthisdatastructureisthemaximumpriorityofthepacketsthatarereadyforcommunicationateachnode,andtwobooleanparametersthat,respectively,reflectwhethertherearepacketstotransmit,andwhetheraninterruptednodeisrequestedtotransmitorreceiveapacket.Theoperationofthebusdriverisasfollows:
a)Packetqueuing.Whenapacketisqueuedfortransmissionandthebusisidle,thepacketistransmitted(seeb).
b)Packettransmission.Thepacketiscopiedtosharedmemory,andthereceivernodeisinterruptedtoreceivethepacket(seec).
c)ReceptionInterrupt.Thetransmitterofpacketinterruptsthereceivernodewhenthepacketisreadytoberetrieved.Thereceivernodecopiesthepacketfromsharedmemory,andthenchecksifmorepacketsneedtobetransmitted(seed)
d)Checkingfortransmission.Iftherearepacketstotransmit,thecontroldatastructureischeckedtodeterminewhichisthenodewiththemaximumprioritypacket.Ifitisthenodeexecutingtheoperation,thepacketistransmitted(seeb);otherwise,thecorrespondingnodeisinterruptedfortransmission(seee).
e)Transmissioninterrupt.Whenanodeisinterruptedfortransmissionitre-checksfortransmission(seed).Inordertoexecutetheaboveoperations,thesporadicserverschedulerhastoincludeanoperationtoquerythepriorityofthehighestprioritypackettobetransmitted.Inaddition,whenareplenishmentoperationswitchesthestateofasporadicserverfrombackgroundtonormal,andthemaximumpriorityofthepacketspendingfortransmissioninthatnodechanges,theglobalcontrolstructuremustbeupdatedaccordingly.Finally,thereplenishmentmanagerinthesporadicserverschedulermustbeanactiveobject,becausereplenishmentoperations
mustbecarriedoutatthetimewhentheyexpire,tomaintaintheconsistencyoftheglobalcontrolstructure.Inthesporadicserverimplementationforpoint-to-pointnetworksthereplenishmentmanagerwasapassiveobject(executedintheenvironmentofthetaskthatextractsapacketfromtheserver)becausereplenishmentsonlyneededtobeexecutedwhenanewpacketwasgoingtobetransmitted.
5.4.Modelingthereal-timeperformanceof
messagequeues
Theperformanceofthisimplementationhasbeenmeasuredtodeterminetheoverheadsintroducedinthecommunicationbythesporadicserverschedulingalgorithm.Thisoverheadismodeledinthereal-timeanalysisprocessasextratransmissiontime,aswellasextramessages.Accesstosharedresourcessuchasthemessagequeuesorthepacketpriorityqueuesisprotectedwithsynchronizationprimitives,andthusismodeledasblockingtime,intheusualwaysynchronizationistreatedinthereal-timeanalysis.Theinterrupthandlersandthetaskthatmanagesthereceptionofmessageshavetobeincludedintheanalysisasadditionaltasks.Thesporadicserverforpoint-to-pointcommunicationsdoesnotneedanyspecialtreatment;wejusthavetoaccountforaslightincreaseintheexecutiontimesofthemessagescheduleroperations(abouta50%incrementcomparedtothenormalpriorityscheduler).IntheVMEbusimplementation,thesporadicserverintroducesanewtask,thereplenishmentmanager,thathastobetakenintoaccountintheanalysis.Themodelofthecommunicationssystemthathasbeendevelopedtogetherwiththemeasurementsoftheexecutiontimesofeachofitsactionscanbeusedtopredicttheworst-caseresponsetimeofanyhardreal-timedistributedapplicationusingthisapplication.
6.Conclusions
Inthispaperwehaveshownthattheschedulabilitypenaltyintroducedbytheeffectsofdeferredactivationinhardreal-timedistributedsystemisverylarge.Bysimplyeliminatingjitterwecanincreaseschedulability,uptoasurprising50%increment.Jittercanbeeliminatedbyusingthesporadicserverschedulingmechanismbothto
scheduletasksineachoftheprocessingnodes,aswellasmessagesineachofthenetworks.
Althoughthesporadicserverwasdesignedasaschedulingalgorithmforprocessors,inthispaperwehaveshownthattheconceptcanbeeasilyadaptedtoschedulemessagesinareal-timecommunicationnetwork.WehaveimplementedthisalgorithminAdausingthePOSIX.1bmessagequeueinterfacewhichprovidesformessagepriorities.Ourimplementationallowsustodesign,implement,andanalyzehardreal-timedistributedsystemswithahighdegreeofutilizationandguaranteeingthatallhardreal-timerequirementsaremet.
References
[1]G.Agrawal,B.Chen,W.Zhao,andS.Davari.
\"ArchitectureImpactofFDDINetworkonSchedulingHardReal-TimeTraffic\".WorkshoponArchitecturalAspectsofReal-TimeSystems,December1991.
[2]J.J.GutiérrezGarcía,andM.GonzálezHarbour,
\"OptimizedPriorityAssignmentforTasksandMessagesinDistributedHardReal-TimeSystems\".3rdWorkshoponParallelandDistributedReal-TimeSystems,SantaBarbara,CA,1995.
[3]IEEEStandard1003.1b-1993,\"DraftStandardfor
InformationTechnology—PortableOperatingSystemInterface(POSIX)—Part1:SystemApplicationProgramInterface(API)—Amendment1:RealtimeExtension[CLanguage]\".TheInstituteofElectricalandElectronicsEngineers,1993.
[4]M.Klein,T.Ralya,B.Pollak,R.Obenza,andM.González
Harbour,\"APractitioner’sHandbookforReal-TimeSystemsAnalysis\".KluwerAcademicPub.,1993.
[5]L.Sha,andS.S.Sathaye,\"ASystematicApproachto
DesigningDistributedReal-TimeSystems\".IEEEComputer,September1993,pp.68-78
[6]B.Sprunt,L.Sha,andJ.P.Lehoczky.\"AperiodicTask
SchedulingforHardReal-TimeSystems\".TheJournalofReal-TimeSystems,Vol.1,1989,pp.27-60
[7]J.K.Strosnider,T.Marchok,J.P.Lehoczky,\"Advanced
real-timeschedulingusingtheIEEE802.5TokenRing\ProceedingsoftheIEEEReal-TimeSystemsSymposium,Huntsville,Alabama,USA,1988,pp.42-52.
[8]K.Tindell,A.Burns,andA.J.Wellings.\"AllocatingReal-TimeTasks.AnNP-HardProblemMadeEasy\".Real-TimeSystemsJournal,Vol.4,No.2,May1992.pp.145-166.[9]K.Tindell,A.Burns,andA.J.Wellings,\"Calculating
ControllerareaNetwork(CAN)MessageResponseTimes\".Proceedingsofthe1994IFACWorkshoponDistributedComputerControlSystems(DCCS),Toledo,Spain,September1994.
[10]K.Tindell,\"HolisticSchedulabilityAnalysisforDistributed
HardReal-TimeSystems\".DepartmentofComputerScienceReport,UniversityofYork,1993.
因篇幅问题不能全部显示，请点此查看更多更全内容