Verifying and allocating real-time tasks on distributed processing units [Elektronische Ressource] / Alejandro Masrur

Alejandro Masrur

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 9
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

¨ ¨TECHNISCHEUNIVERSITATMUNCHEN
Lehrstuhlfur¨ Realzeit Computersysteme
VerifyingandAllocatingReal TimeTaskson
DistributedProcessingUnits
Alejandro Masrur
¨ ¨Vollstandiger Abdruck der von der Fakultat fur¨ Elektrotechnik und Informationstechnik
der Technischen Universitat¨ Munchen¨ zur Erlangung des akademischen Grades eines
Doktor Ingenieurs (Dr. Ing.)
genehmigten Dissertation.
Vorsitzender: Univ. Prof. Dr. Ing. R. Kennel
Pruf¨ er der Dissertation: 1. Univ. Prof. Dr. Ing. G. F arber¨ (em.)
2. Univ. Prof. Dr. sc. techn. A. Herkersdorf
Die Dissertation wurde am 16.06.2009 bei der Technischen Universitat¨ Munchen¨
¨eingereicht und durch die Fakultat fur¨ Elektrotechnik und Informationstechnik am
10.03.2010 angenommen.Acknowledgements
First of all, I sincerely thank Prof. Farber¨ for his guidance, his unfailing patience and for being
always available to me. None of this, neither this Ph.D. thesis nor my stay in Munich, would
have ever been possible without his support. I profoundly thank Prof. Chakraborty for his
valuable contributions to this thesis and for helping me find motivation towards the end of my
Ph.D.Fortheinterestingworkanddiscussionsshared,IthankProf.HerkersdorftowhomIam
also particularly grateful for accepting to be my second examiner. I further thank Prof. Kennel
forundertakingthechairoftheexaminationboard.
To all my colleagues and the staff at RCS, I am deeply grateful for their unconditional help
wheneverIneededitand,ofcourse,forthepleasantandfriendlyworkingatmosphere. Because
ofthem,IwillalwayslookbackonthetimeatRCSwithgreataffection.
Iwouldalsoliketothankmyparentsandbrothers,whoevertrustedandsupportedme. Ithank
them for respecting my decisions, even when they sometimes did not agree with me. I thank
very much my beloved wife Ana not only for her tolerance and sympathy, but also for her
contributionstothisthesis. Iamnotsure,ifIcompletelyunderstandherwork,butIamcertain
thatsheunderstandsmine.
Finally,IgratefullyacknowledgethesupportbytheDAADatthebeginningandduringthefirst
threeandahalfyearsofmyPh.D.
Munich,June2009TomywifeAna.Contents
1 Introduction 1
1.1 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 UniprocessorScheduling . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Multiprocessor . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 UnderlyingModelsandAssumptions . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 TaskModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 ProcessorModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Structureofthisthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 TestingFeasibilityforReal TimeTasks 11
2.1 TheTime TriggeredSchedulingApproach . . . . . . . . . . . . . . . . . . . . 12
2.1.1 TheMinimumPossibleSlot . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 ContextSwitches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 FeasibilityTest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 TheEvent TriggeredSchedulingApproach . . . . . . . . . . . . . . . . . . . 15
2.2.1 TheEDF . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 TheDM/RMScheduling . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.3 ContextSwitches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3 ConsideringSoftReal Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4 KeyFindings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 AllocatingIndependentReal TimeTaskstoProcessors 47
3.1 BinPackingandTaskAllocation . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.1 SequentialAlgorithmsforBinPacking . . . . . . . . . . . . . . . . . 48
3.1.2 StatisticalPerformanceComparison . . . . . . . . . . . . . . . . . . . 50
3.1.3 BinPackingforRM . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 TaskAllocationforArbitraryDeadlines . . . . . . . . . . . . . . . . . . . . . 52
3.2.1 AlgorithmsforEDF . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.2fortheDM/RMScheduling . . . . . . . . . . . . . . . . . 55
3.3 KeyFindings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 CommunicationandSystemConstraints 65
4.1 ModelingTaskDependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.1 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.2 SystemConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 AllocatingDependentReal TimeTasks . . . . . . . . . . . . . . . . . . . . . 69
vContents
4.2.1 TheAllocationMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.2 TheMatrixofResultingCommunication . . . . . . . . . . . . . . . . 70
4.3 AllocationAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4 AmountofCommunicationbetweenProcessors . . . . . . . . . . . . . . . . . 75
4.5 Reducing . . . . . . . . . . . . . . . . . . 77
4.5.1 TheVolumeMatrix . . . . . . . . . . . . . . . . . . . 77
4.5.2 HeuristicstoReduceCommunication . . . . . . . . . . . . . . . . . . 78
4.5.3 ProcessorsversusMaximumTaskUtilization . . . . . . . . . . . . . . 79
4.5.4 CommunicationversusMaximumTaskUtilization . . . . . . . . . . . 83
4.5.5versusTaskConnectivity . . . . . . . . . . 88
4.6 HeuristicstoReduceProcessorsandCommunication . . . . . . . . . . . . . . 93
4.6.1 ProcessorsversusMaximumTaskUtilization . . . . . . . . . . . . . . 96
4.6.2 CommunicationversusMaximumTaskUtilization . . . . . . . . . . . 99
4.6.3versusTaskConnectivity . . . . . . . . . . 103
4.7 KeyFindings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5 ConcludingRemarks 109
Bibliography 113
viAbstract
In general, two major issues arise when designing real time embedded systems upon multiple
processors: task allocation and feasibility/schedulability analysis. The task allocation problem
is concerned with the assignment of tasks to processors, whereas the feasibility/schedulability
analysis deals with testing whether a given set of real time tasks is schedulable or not. A set
of real time tasks is said to be schedulable or feasible on one or more processors, when all its
timing constraints (deadlines) can be guaranteed. Clearly, we cannot allocate real time tasks
to processors that are unable to guarantee their deadlines and, hence, these two problems are
interdependentandcannotbehandledseparately.
In this thesis, we provide an integrated framework for task allocation and feasibility analysis.
In particular, new better linear time feasibility tests are used in conjunction with allocation
heuristics. This way, we first analyze the case of allocating independent real time tasks and
then extend algorithms to consider task dependencies. The contributions of this thesis are as
follows:
• A novel technique is proposed to perform the feasibility analysis of both fixed and
dynamic priority scheduling policies. This new technique consists in calculating the
maximum loading factor generatedbyreal timetasksonasingleprocessor. Theconcept
ofloadingfactorisdefinedasthetotalexecutiondemandwithinaspecifiedtimeinterval
divided by the length of this interval. Hence, the maximum loading factor is the upper
bound on the loading factor which results from considering every possible time interval.
Asaconsequence,ifthemaximumloadingfactorofagiventasksetislessthanorequal
to unity on a single processor, the processor will be able to comply with the execution
demandofalltasks. Thus,thetasksetissaidtobefeasibleonthatprocessor.
• Applying the concept of maximum loading factor, linear time sufficient feasibility tests
are presented for the most general case of task having arbitrary deadlines. We analyze
both fixed priority and dynamic priority scheduling algorithms. Further, the proposed
feasibility tests are shown to be more accurate (i.e., less pessimistic) than the known
algorithmswithsamecomplexitythatcanbefoundintheliterature.
• The proposed feasibility tests are also combined with well known bin packing heuristics
(e.g., First Fit and First Fit Decreasing) to derive fast polynomial time allocation algo
rithms for independent real time tasks with arbitrary deadlines. By means of a detailed
comparison, we further show that these algorithms achieve better task allocations on the
average than the ones based on feasibility analysis methods from the literature. This
meansthattheproposedheuristicsleadtoabiggerreductionofthenumberofprocessors,
whicharenecessarytoguaranteefeasibilityforthewholetaskset.
vii• The problem of allocating dependent real time tasks to multiple distributed processors is
analyzed. Particularly, we focus on task communication and system constraints. For the
case of communicating tasks, different heuristics are presented to reduce the amount of
communication between processors during the allocation procedure. Finally, some addi
tional allocation heuristics are proposed to minimize both the number of processors and
the amount of communication between them. In contrast to most communication aware
allocation methods from the literature, the proposed algorithms have polynomial com
plexity and can possibly be adapted to perform an on line allocation for communicating
tasks.
viiiZusammenfass