Fall2001EE249DesignofEmbeddedSystemsHomework3Prof.AlbertoSangiovanni-VincentelliTA:ClaudioPinelloSuggestionsfrom:varioussourcesDueinclass,Nov27th,Tuesday,10%offforupto1weeklateProblem1(20points)ConsiderthefollowingSynchronousDataflowGraph:1abcd e777625566315211Problem2(20points)Problem3(20points)Weshallconsiderasetofperiodicallyactivatedtasks.Eachtaskischaracterizedbyatripleofparameters:• Ci:computationtime,• Pi:activationperiod,• Di:relativedeadline.EverytaskisassumedtobeactivatedattimekPi,k=0,1,…..UponeachactivationataskexecutesajobrequiringCiCPUtimeunitsandithastoterminatebeforekPi+Di.AlltaskssharethesameCPUand,hence,aschedulingalgorithmhastobeapplied.Aschedulingalgorithmiscalledpreemptiveifitpermitstointerrupttheexecutionofataskbeforeitterminatesajobandnon-preemptiveotherwise.Preemptivereal-timeschedulingalgorithmsmakeschedulingdecisionsaccordingtoprioritiesassignedtotasks.Prioritycanbeassignedstaticallyorchangeddynamically(e.g.uponthearrivalofanewjobrequestforatask).TheresultoftheapplicationofaschedulingalgorithmisafunctionassigningeachtimeslotoftheCPUtoatask.Suchafunctionisdefinedschedule.Ascheduleissaidfeasibleifeachjobterminatesbeforeitsassigneddeadline.Asetoftasksforwhichafeasiblescheduleexistsundersomealgorithmissaidschedulable.Part1.Forthefollowingtasksetsverifyifafeasiblescheduleexistsbasedona)nonpreemptivealgorithms,b)preemptivealgorithmswithstaticpriorities,c)preemptivealgorithmswithdynamicpriorities.3.1.1) Ci Pi DiTask1354Task2142Task3320203.1.2)3.1.3)Part2.Alargepartoftheresultsdescribedintheliteraturedealswithindependenttasks.Let’sconsiderhereadifferentcaseforthefollowingtaskset.3.2.1) Ci Pi DiTask1191Task253615Task351818Lettasks1and3sharesomecommonresource,inexampleasamememorybuffertointeractwithspecialperipherals.Bothtaskslocktheresourceatthebeginningofajobandreleaseitattheendofit.Whenoneofthetwoisusingtheresource,theothercannotstartexecutionuntiltheresourceisreleased(intheexampleabovethemutualexclusionlockpreventscrosscorruptionofdatainthebuffer).Task2isindependentoftheothertwo,soinprincipleitcanbepreemptedbyandcanpreemptanyofthem.Verifyifafeasiblescheduleexistsfor3.2.1)usinga) RateMonotonicschedulingb) EarliestDeadlineFirstscheduling Ci Pi DiTask1344Task231212 Ci Pi DiTask161512Task252020Task33105Part3.Forthefollowingtasksetsdeadlinesareassumedtobeequaltoperiods.VerifyifthefollowingtasksetsareschedulableusingRateMonotonicandEDFusingconditionsandalgorithmsshowninclassandvalidateresultsconstructingtheschedule.3.3.1)3.3.2) Ci PiTask113Task212Task329 Ci
View Full Document