Partitioned Fixed-Priority Multiprocessor Scheduling for Mixed-Criticality Real-Time Systems

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/193944
Download file(s):
File Description SizeFormat 
193944.pdfFulltext2.14 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Partitioned Fixed-Priority Multiprocessor Scheduling for Mixed-Criticality Real-Time Systems
Authors: Lautenbach, Aljoscha
Abstract: The scheduling of real-time systems has been the subject of research for many years since it has many implications for safety-critical embedded real-time systems. Within that field, there have been two recent developments which are the subject of this thesis. The first is the development of new scheduling theory for mixedcriticality systems, i.e. systems in which functions of differing importance are scheduled on the same processor. The second is the increasing production use of multiprocessor systems, even in the world of embedded real-time systems. The purpose of this work is twofold. First a new schedulability test for fixedpriority mixed-criticality uniprocessor systems will be presented and evaluated. Secondly, that schedulability test will be used in an evaluation of different heuristics for partitioned multiprocessor scheduling of mixed-criticality systems. In order to evaluate the performance of the new schedulability test and the di erent heuristics in terms of schedulability, a number of experiments were performed. For this purpose random task sets were generated, and each such task set was tested for schedulability. It was found that the new uniprocessor schedulability test outperforms the previously known approaches for fixed-priority mixed-criticality task sets on preemptively scheduled uniprocessor systems. In terms of the heuristics that were evaluated for partitioning, it was determined that the combination of a slackmonotonic initial ordering with a best-fit allocation algorithm and deadline monotonic priority ordering yields the best schedulability. It seems surprising that using a deadline monotonic priority ordering outperforms Audsley's priority ordering approach. Furthermore, it was shown that a utilisation-based worst-fit task allocation algorithm is not a good heuristic for the kind of systems under assessment. Finally, the presented uniprocessor schedulability test seems to scale well with the number of processors, if the number of tasks per taskset is sufficiently high.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2014
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/193944
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.