nach oben

Real-Time Systems

Erschienen in:

09.10.2018

Analysis techniques for supporting hard real-time sporadic gang task systems

verfasst von: Zheng Dong, Cong Liu

Erschienen in: Real-Time Systems | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper first studies the problem of scheduling hard real-time sporadic gang task systems under global earliest-deadline-first on a multiprocessor platform, where a gang application’s threads need to be concurrently scheduled on distinct processors. A novel approach combining new lag-based reasoning and executing/non-executing gang interval analysis technique is introduced, which is able to characterize the parallelism-induced idleness, as a key challenge of analyzing gang task schedules. To the best of our knowledge, this approach yields the first utilization-based test for hard real-time gang task systems. To further handle the clustered scheduling scenario, we propose a partitioning scheme that enables a set of gang tasks to be efficiently assigned and scheduled among multiple clusters.

Vorheriger Artikel Guest editorial: special issue on the Real-Time Systems Symposium 2017

Nächster Artikel The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Under the density test, an implicit-deadline sporadic task system is schedulable under GEDF if \(U_{sum} \le M - (M-1) \cdot u_{max}\) holds, where \(u_{max}\) denotes the maximum task utilization in the system.

Note that we assume that \(M \ge \max _{1 \le i \le n}\{m_i\}\). Otherwise, some tasks cannot be executed due to the insufficient number of processors.

Note that the [BAR] test given in Baruah (2007) incorrectly presents inequality (3), where \(\ge \) should have been used instead of using >. We thus use the corrected inequality herein according to [27] and Bertogna and Baruah (2011).

In this paper, we only consider gang tasks with implicit deadlines.

Adhianto L, Banerjee S, Fagan M, Krentel M, Marin G, Mellor-Crummey J, Tallent NR (2010) Hpctoolkit: tools for performance analysis of optimized parallel programs. Concurr Comput 22(6):685–701

Baker TP (2003) Multiprocessor edf and deadline monotonic schedulability analysis. In: Real-time systems symposium. IEEE, pp 120–129

Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: RTSS, pp 119–128

Berten V, Courbin P, Goossens J (2011) Gang fixed priority scheduling of periodic moldable real-time tasks. In: 5th junior researcher workshop on real-time computing, pp 9–12

Bertogna M (xxxx) Evaluation of existing schedulability tests for global edf. In: ICPPW’09

Bertogna M, Baruah S (2011) Tests for global edf schedulability analysis. J Syst Archit 57(5):487–497CrossRef

Bonifaci V, Marchetti-Spaccamela A, Stiller S, Wiese A (2013) Feasibility analysis in the sporadic dag task model. In: 25th Euromicro conference on real-time systems

Collette S, Cucu L, Goossens J (2008) Integrating job parallelism in real-time scheduling theory. Inf Process Lett 106(5):180–187MathSciNetCrossRefMATH

Courbin P, Lupu I, Goossens J (2013) Scheduling of hard real-time multi-phase multi-thread (mpmt) periodic tasks’. Real-Time Syst 49(2):239–266CrossRefMATH

Dagum L, Menon R (1998) Openmp: an industry standard api for shared-memory programming. IEEE Comput Sci Eng 5(1):46–55CrossRef

Devi UC, Anderson JH (2005) Tardiness bounds under global edf scheduling on a multiprocessor. In: RTSS, pp 12–24

Dong Z, Liu C (2016) Closing the loop for the selective conversion approach: a utilization-based test for hard real-time suspending task systems. In: 2016 IEEE on real-time systems symposium (RTSS). IEEE, pp 339–350

Dong Z, Liu C, Gatherer A, McFearin L, Yan P, Anderson JH (2017) Optimal dataflow scheduling on a heterogeneous multiprocessor with reduced response time bounds. In: Proceedings of 29th Euromicro conference on real-time systems (ECRTS 2017)

Feitelson DG (1996) Packing schemes for gang scheduling. In: Workshop on job scheduling strategies for parallel processing. Springer, pp 89–110

Feitelson DG, Rudolph L (1992) Gang scheduling performance benefits for fine-grain synchronization. J Parallel Distrib Comput 16(4):306–318CrossRefMATH

Goossens J, Richard P (2016) Optimal scheduling of periodic gang tasks. Leibniz Trans Embed Syst 3(1):04-1

Goossens J, Funk S, Baruah S (2003) Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst 25(2–3):187–205CrossRefMATH

Goossens J, Berten V (2010) Gang ftp scheduling of periodic and parallel rigid real-time tasks. arXiv:1006.2617

Jette MA (1997) Performance characteristics of gang scheduling in multiprogrammed environments. In: Proceedings of the ACM/IEEE conference on supercomputing, SC, 15–21 Nov 1997, San Jose, CA, USA, p 54. https://doi.org/10.1145/509593.509647

Kato S, Ishikawa Y (2009) Gang edf scheduling of parallel task systems. In: Real-time systems symposium, 2009, RTSS 2009. 30th IEEE. IEEE, pp 459–468

Lakshmanan K, Kato S, Rajkumar R (2010) Scheduling parallel real-time tasks on multi-core processors. In: 2010 IEEE 31st real-time systems symposium (RTSS). IEEE, pp 259–268

Leontyev H (2010) Compositional analysis techniques for multiprocessor soft real-time scheduling, Ph.D. dissertation, University of North Carolina at Chapel Hill

Li J, Agrawal K, Lu C, Gill C (2013) Outstanding paper award: analysis of global edf for parallel tasks. In: 25th Euromicro conference on real-time systems

Liu C (2013) Efficient design, analysis, and implementation of complex multiprocessor real-time systems, Ph.D. dissertation, Citeseer

Liu C, Anderson JH (2012) An o (m) analysis technique for supporting real-time self-suspending task systems. In: RTSS, pp 373–382

Manimaran G, Murthy CSR, Ramamritham K (1998) A new approach for scheduling of parallelizable tasks in real-time multiprocessor systems’. Real-Time Syst 15(1):39–60CrossRef

Nelissen G, Berten V, Goossens J, Milojevic D (2012) Techniques optimizing the number of processors to schedule multi-threaded tasks. In: 2012 24th Euromicro conference on real-time systems (ECRTS). IEEE, pp 321–330

Ousterhout JK et al (1982) Scheduling techniques for concurrent systems. In: ICDCS, vol 82, pp 22–30

Pacheco PS (1997) Parallel programming with MPI. Morgan Kaufmann, San FranciscoMATH

Papazachos ZC, Karatza HD (2011) Gang scheduling in multi-core clusters implementing migrations. Fut Gener Comput Syst 27(8):1153–1165CrossRef

Richard P, Goossens J, Kato S (2017) Comments on gang edf schedulability analysis. arXiv:1705.05798

Ryu KD, Pachapurkar N, Fong LL (2004) Adaptive memory paging for efficient gang scheduling of parallel applications. In: Parallel and distributed processing symposium, 2004. Proceedings. 18th International. IEEE, p 30

Saifullah A, Li J, Agrawal K, Lu C, Gill C (2013) Multi-core real-time scheduling for generalized parallel task models. Real-Time Syst 49(4):404–435CrossRefMATH

Singh S (2012) Performance optimization in gang scheduling in cloud computing. Int Organ Sci Res 2(4):49–52

Szeliski R (2010) Computer vision: algorithms and applications. Springer, New YorkMATH

Tesla speculation: how many nvidia drive px2 gpus are needed for level 5 autonomy? http://teslaspeculation.com/2017/07/03/how-many-nvidia-drive-px2-gpus-are-needed-for-level-5-autonomy/

Zhou BB, Brent RP (2001) Gang scheduling with a queue for large jobs. In: Parallel and distributed processing symposium, Proceedings 15th international. IEEE

Titel: Analysis techniques for supporting hard real-time sporadic gang task systems
verfasst von: Zheng Dong
Cong Liu
Publikationsdatum: 09.10.2018
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 3/2019
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-018-9318-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2019

Dynamic budget management and budget reclamation for mixed-criticality systems

The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systems

A comparison of schedulability analysis methods using state and digraph models for the schedulability analysis of synchronous FSMs

FFOB: efficient online mode-switch procrastination in mixed-criticality systems

Decision-driven scheduling

Guest editorial: special issue on the Real-Time Systems Symposium 2017