ACF and RFR

ShyhtsunF.Wu

GailE.Kaiser

ColumbiaUniversity

DepartmentofComputerScience

500W.120thStreetNewYork,NY10027

Tel:212-939-7086,Fax:212-666-0140

wu,kaiser@cs.columbia.edu

February15,1994

c1993,ShyhtsunFelixWuandGailE.Kaiser

AllRightsReserved

Abstract

In[WK94],wedefineareal-timeproducers/consumersproblemwherealltasksareperiodicandallresourcesarenon-sharable/non-reusable.Inthispaper,westudythesameproblembutwithsharableresources.Wedefineaquantitativemeasure,resourcefreshnessratio(RFR),torepresenttheeffectofsharableversusnon-sharableresourcesonimprovingtheresourcefreshnesswhentasksstartsimultaneously.WeconsidertheRFRvaluesforbothaveragecasefreshness(ACF)andworstcase

andrespectively.Thefollowingresultsareobtained:freshness(WCF),i.e.,

1.

resourcetype

,0

10

1.

andvalueswhen2.Givenasetofconsumersandaresourcetype,thenthe

wehaveonlyonefast-producertoserveallthe-consumersaresmallerthanthevalueswhenwehavemultiple-producersandallthese-producershaveshortercycletimesthananyofthe-consumers.

3.

and

timethananyofthe-consumertasks,whereBothboundsaretight.

2

3

ifall-producertaskshaveshortercycleistheamountofconsumedinonehyper-cycle.

2

Wealsoexplainwhytheseresultsareusefulinthedomainofreal-timenetworkmonitoring,control,andmanagement.

1

1Introduction

Inanetworkmanagementsystem,managementinformationistreatedasreal-timeresources[WK93].Ifthemanagementinformationstoredinamanagementworkstationisconsistentwithwhatishap-peninginthereal-world,thenallthemanagementapplicationsusingthisinformationcanmakevalidmanagementdecisionsandactions.Therefore,itiscriticallyimportanttoguaranteethat,forexample,iftheoperationalstatusofthereal-worldnetworksystembecomesattime,thenbeforetheinformationusedbymanagementapplicationsshouldreflectthisnewstateofthenetwork.Wecallthefreshnessofthemanagementinformation.

Themanagementapplicationsarethereal-timeinformationconsumers,whilemanagementagentsaretheinformationproducers.Oneresponsibilityofamanagementagentistodetectnetworkfaultsandtosendnotificationeventstooneormoremanagementapplications.Afterreceivingafaultno-tificationevent,themanagementapplicationwouldhandlepotentialnetworkfailuresrelatedtothisfault.Sincesomeuserapplicationsonthenetworkmightbetime-sensitive,thepotentialfailuresmustberesolvedinrealtime.However,amanagementapplicationmightnotbeabletoidentifytheproblembyjustinglookingatonenotificationevent.Moreoften,aglobalconsistentviewofthewholenetworkisnecessaryforthemanagementapplicationtomakeadecision.Therefore,weneedahardreal-timemanagementinformationbasetorepresentthestateofournetwork.Anarchitectureofareal-timenetworkmanagementsystemisdepictedinFigure1.

Weproposedareal-timeproducers/consumersmodel,DONUT,in[WK94,WK93]asanabstractmodelwherewedeveloptechniquesfortheproblemsofmaintaininghardreal-timemanagementinfor-mation.In[WK94],weconsiderbothavailabilityandfreshnessoftheconsumedinformationresourceunderthecasewheretheyarenon-sharable/non-reusable.Weshowthatbothworstcasefreshness(WCF)andaveragecasefreshness(ACF)canbeoptimizedsimultaneously.Thenon-sharablecaseisusefulinadistributedmanagementsystemwhereonemanagementapplicationcannotaccessthemanagementinformationofothers.However,asinFigure1,ifmorethanonemanagementapplica-tionsareloadedonthesamemachine,thentheinformationmightbecomesharable.

Inthispaper,weanalyzethepowerofthesharableresourcesinthereal-timeproducers/consumersproblemforbothACFandWCFcases.Wedefineaquantitativemeasure,resourcefreshnessratio(RFR),torepresenttheeffectofsharableversusnon-sharableresourceswhengivenasetofperiodic

couldbeproducerandconsumertasksstartingatthesametime.Intheworstcase,weshowthat

0,whichimpliesthatsharableresourcesareinfinitelybetterthannon-sharableones.However,ifwelimitourselvestothesetoftaskswhere,resourcetype,the-producertasksalwayshaveshorter

2

cycletimesthananyofthe-consumers1,thenwecanprovethat.2Also,givenasetofconsumers,thentheRFRvaluewhenwehaveonlyonefast-producertoserveallthe-consumersissmallerthanthevalueswhenwehavemultipleslow-producersandallthese-producertaskshaveshortercycletimesthananyoftheconsumers.Furthermore,wediscoverthat

andoneproducerwithcycletime

weusetherate-monotonicschedulingalgorithm[LL73],thisimpliesthat

-consumertasks.

1If

-producertaskshavehigherprioritiesthan

2

ManagementApplicationsReal−Time MIBReal−TimeMonitoringSystemInformationAgentInformationAgentInformationAgentWorstCase:

GlobalResourceBalanceConditionShorterCycleTimeProducerTasksOneProducer,ArbitraryConsumersOneProducer,IdenticalConsumers

0

22

33

1

11

11

22

2

Figure2:ClassesofProducer/ConsumerTaskSetsandthe

Values

3

non-sharableinformationresourcesneedtobeconsideredinordertoanalyzethepreciseinformationfreshness.However,wecanassumeeithereverythingornothingissharablewhileperformingtheanalysis.Theoutcomeofthatanalysiswouldbeclosetotherealfreshnesswithaboundederror.Third,inthesystemdesignphase,ourresultsprovideinformationfordecidinghowmanyproducertasksweshouldhave.WewillelaboratemoreonthesethreeissuesinSection4.

Inthenextsection,webrieflyintroducetheDONUTmodelandtheproblemsofworstcasefreshnessandaveragecasefreshness.Then,weformallydefinetheconceptofresourcefreshnessratio(RFR).Finally,wegivetheresultsof.

2TheDONUTProblem

2.1PeriodicTasksandTaskOccurrences

Definition1(ResourceVector,

1

2

)Iftherearedistincttypesofresources,thenaresourcevector

isan-tuplebitvector,where01for1.

Definition2(PeriodicTask,)Aperiodictaskischaracterizedbythefollowing6attributes:

1

:thestartingtimeof’sfirstoccurrence.:thecyclelengthof.:thepriorityof.

:theworstcaseexecutiontimeof.:anfortheresourcesproducedby.:anfortheresourcesconsumedby.

,areallintegers.Pleasenotethatthetimethatwearedealingwithisdiscrete,and1,,

Definition3(-thoccurrenceofPeriodicTask,)

isthe-thoccurrenceoftheindexofthesequence,then

1

1

hasasequenceofoccurrences.If.Furthermore,thestartingtimeof

is,

Example1Weliveinaworldwheredonutsaretheonlyfoodwecaneat.Infigure3,therearethreedifferenttypesofdonuts:GLAZED,FROSTED,andJELLY-FILLED.And,wehavefourperiodictasks:

,,,and.willmakeoneGLAZEDdonutandoneFROSTEDdonutevery2hours.BothandareperiodicconsumersofbothGLAZEDandFROSTEDdonutsandthecycletimeis4hoursforbothofthem.Also,bothandwouldproduceoneJELLY-FILLEDdonutineach

isstilltoosmalltomakeanydonutsbutheneedstoeatoneJELLY-FILLEDtaskoccurrence.Finally,

donutevery2hours.

Sincewehaveonlythreedifferenttypesofresource,allthe’sare3-tuplebitvectors123byDefinition1.Ifweassumethatalltasksstartattime0,thenwecanspecifythesefourtasksasthefollowing:

:

1

0,

2hours,

,

,

110,

000.

::

1

0,

6hours,

,

,

001,

110.

1

0,

3hours,

,

,

001,

110.

:

1

0,

2hours,

,

,

000,

001.

4

FrostedJelly−FilledMommy2 hrsGlazedGrandmaFrostedAuntieJelly−FilledSon2 hrs5

2.3ResourceBalanceCondition

Definition4(TypeResourceBalanceCondition)Asetoftasks,resourcebalancedifandonlyif

1

2

,istype

6

tljtkit(l+1)jJkiJljthe Producerthe ConsumerGiven a pair of producer and consumer task occurrences,this is the inherent blocking region that priority inheritanceschemes can not help.Figure5:TheCasewhentheConsumerStartsEarlierthantheProducer

2.5TheResourceFreshnessProblem

Given

,wewouldliketoknowthelifetimeofthisconsumedtype

resource.Theexactlifetimeis

difficulttoknowuntilruntime.However,bythepropertiesdescribedinSection2.1,aresourcewould

(i.e.,)anditwouldbeconsumedbeforethestartingnotbeproduceduntilthestartingtimeof1

timeofthenextoccurrenceof(i.e.,).Therefore,wecanusethesetwoboundstoapproximatetheexactlifetimeofaresource.Inthefollowingdefinition,theconceptofresourcefreshnessfornon-sharable/non-reusableresourcesisdefined:

Definition8(Non-SharableResourceFreshness,

)

1

1

1

1

1

1

1

(byDefinition3)

1

1

1

1

whereisthestartingtimeofof,ataskoccurrenceoftype

,ataskoccurrenceoftyperesourceconsumer.

resourceproducer,and

isthedeadline

InDefinition8,weobservetwothings:

1.If,then0.Thisiscertainlyundesirablebecausetheconsumertaskoccurrence,,woulddefinitelymissitsdeadlinewhilewaitingfortheresourceproducedby.

1

2.Whenvalueof

,

isblockeduntil,regardlessofthevaluesofand.Thelargerthe,theharderitistoschedulethesetoftasks.ThissituationisdepictedinFigure5.

Wedonotclaimthatitisimpossibletoscheduleasetoftaskswhenweallowaconsumertaskoccurrencetostartearlierthanitscorrespondingproducertaskoccurrence.However,inordertoreducetheproblem’scomplexity,wemakethefollowingrestrictionfortheresourceallocationpolicies.Policy1(ARestrictiononResourceAllocationPolicies)Givenanyresourceallocationpolicy

1under,thenmuststartnolaterthan(i.e.,).if

,

Inordertoevaluatetheperformanceofresourceallocationpolicies,twoquantitativemeasuresare

defined.Givenaresourcetype,theworstcasefreshness()isthelargestvaluethatcouldeverhappen.Sinceweonlyconsiderperiodictasks,itissufficienttofindthelargestvalue

)istheaverageoveralltheinonehyper-cycle.Similarly,theaveragecasefreshness(

valuesfortheconsumedresources,andwecancomputethefromallthevaluesinonehyper-cycle.

7

Definition9(WorstCaseFreshness,

)

1

max

1

1

0

0

where

0

1

1

,and

1

10

ifisTRUE,otherwise

Definition10(AverageCaseFreshness,

)

1

1

1

0

0

where011

,and

istheamountof

thatanoccurrenceoftask

consume.Inotherwords,

2

10

would

8

MommyGlazedNon−SharableDonutAuntieFreshness = 4 hoursGrandmaFreshness = 6 hours6:008:0012:00Figure6:TheTimeDiagramoftheNon-SharableDonutExample

3SharableResourceFreshness

Whenresourcesaresharable,thenthevaluesarelargerthantheactualRFvalues.BytheRestrictionPolicy(Policy1inSection2.5),weknowthataconsumercanconsumeanyresourceproducedbyataskoccurrencestartingearlierthanthisconsumer.Therefore,withsharableresources,thisconsumershouldconsumetheresourcefromthelatestproducerthatwouldobeyPolicy1.

Example3(SharableDONUT)InExample2,ifwemaketheGLAZEDdonutssharableresources,

andcanhavethenboth2,thelatestproducedGLAZEDdonut.Inthiscase,thedonut

freshnessisdifferent:

22

byby

:12:12

88

4hours.4hours.

And,

44

5,

whiletheWCFratiois

4

3.

The

timediagramisillustratedinFigure7.

Definition11(SharableResourceFreshness,

)

1

1

1

3.1ResourceFreshnessRatio

Sinceweareinterestedincomparingthepowerofsharableversusnon-sharable,wedefineaquantitative

measure,resourcefreshnessratio(RFR),torepresenttheresultofthecomparison.

9

MommyGlazedSharableDonutAuntieFreshness = 4 hoursGrandma6:008:0012:00Figure7:TheTimeDiagramoftheSharableDonutExample

Definition12(ResourceFreshnessRatiofor())Weconsidertheconsumed’sinonehyper-cycle,andtheresourcefreshnessratio

ofallthe

1

max

1

3.2TightUpperandLowerBoundsfor

Since

and

,byDefinitions12and13,thevaluesofbothand

arebetween0and1.Itiseasytoseethat1istruewhenwehave

onlyone-producertaskandone-consumertaskand.Inthisspecialcase,sharableresourcescannotimprovetheresourcefreshnessatall.

andislessobvious.InthefollowingTocheckwhether0isatightlowerboundfor

example,weshowthatevenwhentheglobalresourcebalanceconditionholdsthevalueofcouldconvergetozerowhenthehyper-cycle.

Theorem1(TightLowerBoundforzerowhen

and

)

and

couldgoto

proof:

Assumeeverytaskoccurrencewouldeitherproduceorconsumeoneunitofresourcethehyper-cycle2,forsome.Wehavetwo-consumertasks1,2,and

and

1

10

-producertasks01Thecycletimesofbothconsumertasksaswellasthefirstproducertask0is2,i.e.,12.Thecycletimesofallotherproducertasks20

.Also,thefirsttaskoccurrencesforallthetasksstartattime0simultaneously,is2

1111

i.e.,110Thus,theglobalresourcebalanceconditionholds201

becauseinonehyper-cycle2resourcesareproducedandconsumed.

Ifissharable,both1and2canusetheresourcesproducedby0.Therefore,theresourcefreshness2.Sincewehave2resources,thenumeratoroftheinDefinition12is224.And,thenumeratoroftheinDefinition13ismax2222.

isnon-sharable,1ismatchedto0,and2needsConsideringtheACFcasewhen

Since12,eachofthesetaskswouldresourcesfrom12

produceonlyoneunitofresourceinonehyper-cycle.Thefirsttaskoccurrenceof2,12,

1121

2.Then,wecanseethat4,ismatchedto11,and2122

1

andingeneral,2,where1.Thus,thedenominatorofthe2

2

isequalto122123asinFigure8.Finally,

4

3

and

0as

.

ConsideringtheWCFcasewhen

theisequalto

isnon-sharable,wecanshowthatthedenominatorof

2

,only

finished,i.e.,both1and2contribute

oneresourceproducedattime0mustnotbeconsumeduntil

1.InFigure9,wepresentawaytoallocateresourcestoexactly2

meetthelowerbound.Similarly,wecanderivethesameboundforthecasewhenisodd.Thus,

212

consumerjobsare

2.Thisimpliesthat

and

0as

.

3.3SingleProducerModel

andcangotozero,thevaluescanbeByTheorem1,sincethevaluesof

muchsmallerwhenissharable.However,ifwerestrictthenumberof-producertaskstobe1,then

2

2whentheglobalresourcebalanceconditionholds.Forexample,

4

istheonlyproducerofdonut,andtherefore,asinExample3,3and

2

.2

Beforeprovingthemaintheorems,weneedtoprovethefollowinglemma:

Lemma1(MonotonicSequenceBoundingLemma)Given

,12

1

positiveintegers,

1

1

2

,where

1

11

Producersτττττp0p1p2pnConsumersc1τc2nFigure8:ResourceAllocationwhen

2

3

.

Producersτττττp0p1p2pnConsumersc1τc2nFigure9:ResourceAllocationwhen

12

Lemma2(MaximumCycleTimeBoundingLemma)Letbethenumberoftyperesourcescon-sumedinonehyper-cycle,andtheresourcebalanceconditionholds.Givenone-producertaskand-consumertasks,12,where1,then,2

2

3

where

1

3

isthenumberofconsumertasks,and

istheamountofresourcesconsumedinonehyper-cycle.

proof:AppendixA.3.

Theorem3(inSingleProducerModel)Assumealltasksstartatthesametime.Ifonlyoneproducertaskisallowedandwearegivenanarbitrarysetofconsumertasks,then,whentheglobalresourcebalanceconditionholds,

2

where

istheamountof

resourcesconsumedinonehyper-cycle.

proof:AppendixA.4.

3.4SingleProducerversusMultipleShorterCycleTimeProducers

Givenanarbitrarysetofconsumertasks,wehaveshowninTheorems2and3thatifwehaveonlyone

2

-producertoserveallthe-consumers,then2.Withthesamesetofconsumers,however,thevaluesarealwayslargerifwereplacetheonly-producerwithseveralslower-producers.Anyofthenew-producersshouldstillhaveashortercycletimethananyofthe-consumers.

Example4InExample1,ifwereplacetheonlyGLAZEDdonutproducertwoslowerproducers:

(

2hours)with

with

4hours,and

with

4hours.

1

Wehaveadifferenthypercyclegraph(Figure10).

Now,MommyisonvacationandweletDaddymakeGLAZEDdonutsforGrandma(11

)andUnclemakeGLAZEDdonutsforAuntie(1).Then,

4hours.Sinceinthiscase,thenumeratorsofbothand

4

remainthesame,4hours,wehave

2

5and

13

4 hrs4 hrs4 hrs4 hrs2 hrsDaddyUncleGrandmaAuntieSonOne Hyper CycleAnother Hyper CycleGlazedFigure10:Hyper-Cycleswith

and

Resource FreshnessNot CrossingProducerssJpJkiJljJtqCrossingConsumersstptktljittqResource FreshnessFigure11:RemovingtheCrossRelations

3.4.1CrossResourceDependencyRelations

Definition14(CrossResourceDependencyRelations)Tworesourcedependencyrelations,

and,arecrossingeachotherif.

Lemma3(RemovingCrossRelations[WK94])Givenasolutionofaresourceallocationpolicywithsomecrossresourcedependencyrelations,wecanremovethecrossrelationswithoutincreasingthesummationofresourcefreshnessinonehyper-cycle.(Figure11)proof:In[WK94].

3.4.2MultipleShorterCycleTimeProducers

Wewouldliketoreplacetheonly-producerbyseverallongercycle-producers,andthenewsetofproducersshouldtaketheresponsibilitytofulfilltheresourcerequirementsforallthe-consumers.First,weobservethatthenumeratorsofbothand(i.e.,and1

max

1

respectively)cannotbebetterbecausehavingoneshortestproduceristhecase

wheresharableresourcescanhavethebesteffect.Then,inordertoshowthathavingmultiple-and,wecanonlyconsiderthedenominatorpartsofproducersisbetterforboth

Definitions12and13.Inotherwords,wewanttoprovethat,forevery,wecouldfindaninthenewsetofproducertaskssuchthat

14

Lemma4(ResourceCounting)Givenasetoftasks(one-producerandmultiple-consumers)wheretheglobalresourcebalanceconditionholdsandalltasksstartattime0.Ifwestartcountingattime1,thenatanymoment,thenumberofproducedresourcesmustbegreaterthanorequaltothenumberofconsumedresources.

proof:AppendixA.5.

Lemma5(ShorterCycleTimeProducers)Thedenominatorpartsof

,

1

and

,

max

1

aresmallerwhenwereplacetheonly-producerwithmultiple-producertasks.And,everynewproducertaskshouldhaveashortercycletimethananyofthe-consumertasksandtheglobalresourcebalanceconditionholds.

proof:AppendixA.6.

Theorem4(TheBoundsforshortercycletimesthananyofthe

2

)2ifall-producertaskshave-consumertasksandtheglobalresourcebalanceconditionholds.

proof:FromTheorem2,Theorem3andLemma5.

3.5SpecialCase:1

Producer/ConsumersModel

Givenaresourcetype,ifproducertaskshaveshortercycletimes,22arethelowerboundsfor

and,respectively.Weshowthatthesetwoboundsareactuallytightbyprovidinga

specialcasethatwouldexactlymeetthebounds.

Definition15(SingleProducerwithIdenticalConsumers,)Inareal-timesystem,thereare

uniformconsumertasksforthetyperesources,andbecauseoftheresourceoneproducertaskand

balanceproperty,alltheconsumershavecycletimeofunits,whiletheproducer’scycletimeisoneunit(seeFigure12).Intheamountoftyperesourcesproducedinonehyper-cycleisequalto,thenumberof-consumertasks.

Lemma6(ResourceFreshnessRatioinACF(

)for

)Inthe

model,

2

3

3

boundistightbecausewhen

,theratio

2

.

Lemma7(ResourceFreshnessRatioinWCF(

)for

)Inthe

model,

15

ProducerRF = 5Consumer 1RF = 5RF = 6Consumer 2RF = 5RF = 7Consumer 3RF = 5RF = 8Consumer 4RF = 5RF = 9Consumer 5Sharable ResourcesNon−Sharable Resources5 + 6 + 7 + 8 + 9 = 355 + 5 + 5 + 5 + 5 = 2525=355957Resource Freshness Ratio(Average Case)(Worst Case)Figure12:AnExampleofaSingleProducerwith

UniformConsumers

5

proof:intheAppendixA.8.

SimilarlyfortheWCFcase,byTheorem3andLemma7,theoneproducerwithconsumersmodel,,isthemodelwheresharableresourcescanhavethebestimprovementovernon-sharableresources.Furthermore,byLemma7,weknowthe121goesto1

isthetightlowerboundfortheratiobetweensharableandnon-sharableresources

consideringaveragecasefreshness,while1

3

3

and

1

16

oftheapproximation.

Anotherinterestingquestionforasystemdesigneris,givenasetofinformationconsumers,howmanyproducertasksshouldbeprovided.Lemma5tellsusthatmoreproducerswouldachievebetterfreshnesswhenresourcesarenon-sharable.Ontheotherhand,havingmorehardreal-timetasksimpliesthatweneedmorephysicalmemoryinahardreal-timeoperatingsystem(e.g.,[FGG91]).Thusthereisatrade-offbetweenmemoryconsumptionandresourcefreshness.However,byLemma5andTheorem4,replacingasmallnumberoffastproducerswithalargenumberofslowproducerscouldonlyimprovethefreshnessbyafactorof2inatthemost.2

5OpenProblems

1.Foralltheresultsinthispaper,weassumethattheglobalresourcebalancecondition(GRBC)

problemwithnon-sharable/non-holds.GRBCisanecessaryconditionforsolvingthereusableresourcesbutisnotfortheproblemwithsharableresources.Canwecompare

andwhenGRBCisnotenforced?

2.Mostoftheresultsrequireauniformtaskstartingtime.Itisobviousthat,dependingonphase

differencesandthetaskset,theresourcefreshnessratiocouldbeeitherlargerorsmaller.Canwerelaxthisassumption?3.Ifweallow“aperiodic”producersandconsumers,whatkindof

valuescanweguarantee?

Wearecurrentlyworkingonthethirdproblem,whichisaveryimportantfornetworkmanagement.AsshowninFigure1,therearetwodifferenttypesofreal-timeinformationresources:

real-timemanagementinformationbase(polling);asynchronouseventnotification(eventreporting).

Wehavetousetheaperiodicproducers/consumersmodeltodealwiththereal-timeasynchronouseventhandling.Thefreshnessofaneventmeansthat

Ifanevent(donut)foradetectedfaultisgenerated(produced),thenthiseventmustbehandled(consumed)byatleastonemanagementapplicationwithinacertaintimeperiod(freshness)toresolvepotentialnetworkfailuresrelatedtothefault.

17

Acknowledgments

KevinJeffayprovidedmanyvaluablesuggestions.DiscussionswithStephenBrady,AurelLazar,andSubrataMazumdarwerehelpfulinunderstandingthereal-timeproblemsinthedomainofnetworkcontrolandmanagement.

References

[FGG91]BorkoFurht,DanGrostick,DavidGluch,GuyRabbat,JohnParker,andMegMcRoberts.

[LL73]

[LM80]

[WK93]

[WK94]

Real-TimeUNIXSystems:DesignandApplicationGuide.KluwerAcademicPublishers,1991.

C.L.LiuandJamesW.Layland.Schedulingalgorithmsformultiprogramminginahard-real-timeenvironment.JournaloftheACM,20(1):46–61,January1973.

JosephY.T.LeungandM.L.Merrill.ANoteonPreemptiveSchedulingofPeriodic,Real-TimeTasks.InformationProcessingLetters,11(3):115–118,November1980.

ShyhtsunF.WuandGailE.Kaiser.OnHardReal-TimeManagementInformation.InIEEEFirstInternationalWorkshoponSystemManagement,pages90–100,LosAngeles,CA,April1993.

ShyhtsunF.WuandGailE.Kaiser.Non-SharableResourceFreshnessinReal-TimeSchedul-ing.InRealTimeSystemsConference(RTS’94),pages51–66,PorteMaillot,Paris,January1994.

18

AProofs

.

A.1Lemma1

Assume

iseven,

1

1

2

1

1

1

1

1

2

2

2

21

1

2

1

1

2

2

2

12

12

1

1

2

1

1

2

andtheresultisthesame.

A.2Lemma2

Letuscompute:

1

(ResourceBalanceCondition)

Dividing

frombothsides,weget

inthesingleproducermodel,

.

A.3Theorem2

Assumewehaveconsumertaskswherecouldbearbitrarilylarge.Wethencansortthecycletimeoftheseconsumertasksinanondecreasingorder:1.Inonehyper-cycle,task1has2

19

1

1

.Becauseofthebalancecondition,

1

1

and,

1

1

Thisalsoimpliesthat0.

Withsharableresources,thefreshnessofconsumedresourcesisthecycletimeoftheconsumertasks.Thereasonisthatwhenaconsumertaskstartsanewoccurrencetheremustbeaproducer

0andalltasksstartsimultaneously.)occurrencestartingatthesametime.(Remember

isThus,thenumeratorof

1

1

1

1

1

3

1

2

20

Finally,

1

2

2

31

(byLemma2)

2

2

221

1

(byLemma2)

21

Similarly,inthemultipleproducermodel,resourcesareproducedat1,2where1.Also,forthelargercycletimeconsumers,resourcesare2

,where1.BasedonLemma3,theresourcemapping,consumedat122

1,isanoptimalsolution.ByLemma4,weknowthat1.Therefore,if,,wereplace

with,thenwewillnotgetaworseproducer/consumerrelationbecause

.

A.7Lemma6

Withsharableresources,thefreshnessforalltheconsumedresourcesisunitsoftime.Allthe-consumertaskoccurrencesaresharingthetyperesourcefromthe-producerstartingsimultaneouslywithalltheconsumers.Theresourcesfromtheproducers,where1,arelessfresh.AndconsumingtheresourcesfromtheproducersviolatestheRestrictionpolicy(Policy1inSection2.5).Thus,sincewehaveconsumers,thenumeratorofis.Withnon-sharableresources,onlythefirstconsumer1canconsumethefrom,andthe

1

freshnessis.Thesecondconsumer2wouldhavetoconsumethefrom,whichimpliesthefreshnessis1(becauseis1).Ingeneral,thefreshnessofthethconsumeris1.Now,letuscomputetheratio:

3

1

3

where1

1

.

A.8Lemma7

Withsharableresources,thefreshnessforalltheconsumedresourcesisunitsoftime.Therefore,thenumeratorofis.

Withnon-sharableresources,ingeneral,thefreshnessoftheth-consumeris1,where

.So,max1121.Finally,1