Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Real-Time Systems
Erschienen in: Real-Time Systems 6/2012

01.11.2012

Analysis and implementation of the multiprocessor bandwidth inheritance protocol

verfasst von: Dario Faggioli, Giuseppe Lipari, Tommaso Cucinotta

Erschienen in: Real-Time Systems | Ausgabe 6/2012

Einloggen

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

search-config
loading …

Abstract

The Multiprocessor Bandwidth Inheritance (M-BWI) protocol is an extension of the Bandwidth Inheritance (BWI) protocol for symmetric multiprocessor systems. Similar to Priority Inheritance, M-BWI lets a task that has locked a resource execute in the resource reservations of the blocked tasks, thus reducing their blocking time. The protocol is particularly suitable for open systems where different kinds of tasks dynamically arrive and leave, because it guarantees temporal isolation among independent subsets of tasks without requiring any information on their temporal parameters. Additionally, if the temporal parameters of the interacting tasks are known, it is possible to compute an upper bound to the interference suffered by a task due to other interacting tasks. Thus, it is possible to provide timing guarantees for a subset of interacting hard real-time tasks. Finally, the M-BWI protocol is neutral to the underlying scheduling policy: it can be implemented in global, clustered and semi-partitioned scheduling.
After introducing the M-BWI protocol, in this paper we formally prove its isolation properties, and propose an algorithm to compute an upper bound to the interference suffered by a task. Then, we describe our implementation of the protocol for the LITMUS RT real-time testbed, and measure its overhead. Finally, we compare M-BWI against FMLP and OMLP, two other protocols for resource sharing in multiprocessor systems.
Vorheriger Artikel FPSL, FPCL and FPZL schedulability analysis

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
More information is available at: www.​litmus-rt.​org.
 
2
These, under certain assumptions and for the purposes of this paper, can be considered as a particular form of reservation-based systems
 
3
Notice that we have re-labelled both tasks and resources in the chain to highlight the blocking sequence.
 
4
Resource reservation and servers can also be used as the basis for hierarchical scheduling, in which case each server is assigned more than one task. In this paper, however, we will not take hierarchical scheduling into account.
 
5
Very recently, Ward and Anderson proposed an extension of OMLP to support nested critical sections (Ward and Anderson 2012).
 
6
The test program is available on-line as supplementary material at www.​springerlink.​com.
 
Literatur
Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proceedings of the IEEE real-time systems symposium, Madrid, Spain, pp 4–13
Anderson JH, Ramamurthy S (1996) A framework for implementing objects and scheduling tasks in lock-free real-time systems. In: Proceedings of the IEEE real-time systems symposium (RTSS). IEEE Computer Society, Los Alamitos, pp 94–105
Behnam M, Shin I, Nolte T, Nolin M (2007) Sirap: a synchronization protocol for hierarchical resource sharing real-time open systems. In: Proceedings of the 7th ACM and IEEE international conference on embedded software
Bertogna M, Cirinei M (2007) Response-time analysis for globally scheduled symmetric multiprocessor platforms. In: Proceedings of the 28th IEEE real-time systems symposium. RTSS, Tucson, AZ, USA
Bertogna M, Checconi F, Faggioli D (2008) Non-preemptive access to shared resources in hierarchical real-time systems. In: Proceedings of the 1st workshop on compositional theory and technology for real-time embedded systems, Barcelona, Spain
Block A, Leontyev H, Brandenburg BB, Anderson JH (2007) A flexible real-time locking protocol for multiprocessors. In: Proceedings of the 13th IEEE international conference on embedded and real-time computing systems and applications, pp 47–56
Brandenburg BB, Anderson JH (2007) Feather-trace: a light-weight event tracing toolkit. In: Proceedings of the international workshop on operating systems platforms for embedded real-time applications (OSPERT)
Brandenburg BB, Anderson JH (2010) Optimality results for multiprocessor real-time locking. In: Proceedings of the IEEE real-time systems symposium (RTSS). IEEE Computer Society, Los Alamitos, pp 49–60
Chen CM, Tripathi SK (1994) Multiprocessor priority ceiling based protocols. Technical report, College Park, MD, USA
Cho H, Ravindran B, Jensen ED (2007) Space-optimal, wait-free real-time synchronization. IEEE Trans Comput 56(3):373–384 MathSciNetCrossRef
Cucinotta T, Checconi F, Abeni L, Palopoli L (2010) Self-tuning schedulers for legacy real-time applications. In: Proceedings of the 5th European conference on computer systems (Eurosys 2010), Paris, France. European chapter of the ACM SIGOPS
Davis RI, Burns A (2006) Resource sharing in hierarchical fixed priority pre-emptive systems. In: Proceedings of the IEEE real-time systems symposium
Devi UC, Leontyev H, Anderson JH (2006) Efficient synchronization under global edf scheduling on multiprocessors. In: Proceedings of the 18th Euromicro conference on real-time systems, pp 75–84
Easwaran A, Andersson B (2009) Resource sharing in global fixed-priority preemptive multiprocessor scheduling. In: Proceedings of IEEE real-time systems symposium
Emberson P, Stafford R, Davis R (2010) Techniques for the synthesis of multiprocessor task sets. In: First international workshop on analysis tools and methodologies for embedded and real-time
Faggioli D, Lipari G, Cucinotta T (2008) An efficient implementation of the bandwidth inheritance protocol for handling hard and soft real-time applications in the Linux kernel. In: Proceedings of the 4th international workshop on operating systems platforms for embedded real-time applications (OSPERT 2008), Prague, Czech Republic
Faggioli D, Lipari G, Cucinotta T (2010) The multiprocessor bandwidth inheritance protocol. In: Proceedings of the 22nd Euromicro conference on real-time systems (ECRTS 2010), pp 90–99
Feng X, Mok AK (2002) A model of hierarchical real-time virtual resources. In: Proceedings of the 23rd IEEE real-time systems symposium, pp 26–35
Fisher N, Bertogna M, Baruah S (2007) The design of an EDF-scheduled resource-sharing open environment. In: Proceedings of the 28th IEEE real-time system symposium
Gai P, Lipari G, di Natale M (2001) Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In: Proceedings of the IEEE real-time systems symposium
Guan N, Ekberg P, Stigge M, Yi W (2011) Resource sharing protocols for real-time task graph systems. In: Proceedings of the 23rd Euromicro conference on real-time systems (ECRTS 2011), Porto, Portugal
Lakshmanan K, de Niz D, Rajkumar R (2009) Coordinated task scheduling, allocation and synchronization on multiprocessors. In: Proceedings of IEEE real-time systems symposium
Lamastra G, Lipari G, Abeni L (2001) A bandwidth inheritance algorithm for real-time task synchronization in open systems. In: Proceedings of the 22nd IEEE real-time systems symposium
Lelli J, Lipari G, Faggioli D, Cucinotta T (2011) An efficient and scalable implementation of global edf in Linux. In: Proceedings of the international workshop on operating systems platforms for embedded real-time applications (OSPERT)
Lipari G, Bini E (2004) A methodology for designing hierarchical scheduling systems. J Embed Comput 1(2)
Lipari G, Lamastra G, Abeni L (2004) Task synchronization in reservation-based real-time systems. IEEE Trans Comput 53(12):1591–1601 CrossRef
Lopez JM, Diaz JL, Garcia DF (2004) Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Syst 28:39–68 MATHCrossRef
Macariu G (2011) Limited blocking resource sharing for global multiprocessor scheduling. In: Proceedings of the 23rd Euromicro conference on real-time systems (ECRTS 2011), Porto, Portugal
Mancina A, Faggioli D, Lipari G, Herder JN, Gras B, Tanenbaum AS (2009) Enhancing a dependable multiserver operating system with temporal protection via resource reservations. Real-Time Syst 43(2):177–210 MATHCrossRef
Nemati F, Behnam M, Nolte T (2009a) An investigation of synchronization under multiprocessors hierarchical scheduling. In: Proceedings of the work-in-progress (WIP) session of the 21st Euromicro conference on real-time systems (ECRTS’09), pp 49–52
Nemati F, Behnam M, Nolte T (2009b) Multiprocessor synchronization and hierarchical scheduling. In: Proceedings of the first international workshop on real-time systems on multicore platforms: theory and practice (XRTS-2009) in conjunction with ICPP’09
Nemati F, Behnam M, Nolte T (2011a) Independently-developed real-time systems on multi-cores with shared resources. In: Proceedings of the 23rd Euromicro conference on real-time systems (ECRTS 2011), Porto, Portugal
Nemati F, Behnam M, Nolte T (2011b) Sharing resources among independently-developed systems on multi-cores. ACM SIGBED Rev 8(1)
Niz DD, Abeni L, Saewong S, Rajkumar RR (2001) Resource sharing in reservation-based systems. In: Proceedings of the 22nd IEEE real-time systems symposium, pp 171–180
Palopoli L, Abeni L, Cucinotta T, Lipari G, Baruah SK (2008) Weighted feedback reclaiming for multimedia applications. In: Proceedings of the 6th IEEE workshop on embedded systems for real-time multimedia (ESTIMedia 2008), Atlanta, GA, pp 121–126. doi:10.​1109/​ESTMED.​2008.​4697009 CrossRef
Rajkumar R (1990) Real-time synchronization protocols for shared memory multiprocessors. In: Proceedings of the international conference on distributed computing systems, pp 116–123 CrossRef
Rajkumar R, Sha L, Lehoczky J (1988) Real-time synchronization protocols for multiprocessors. In: Proceedings of the ninth IEEE real-time systems symposium, pp 259–269 CrossRef
Rajkumar R, Juvva K, Molano A, Oikawa S (1998) Resource kernels: a resource-centric approach to real-time and multimedia systems. In: Proceedings of the conference on multimedia computing and networking
Sha L, Rajkumar R, Lehoczky JP (1990) Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans Comput 39(9)
Shih I, Lee I (2003) Periodic resource model for compositional real-time guarantees. In: Proceedings of the 24th real-time systems symposium, pp 2–13
Sprunt B, Sha L, Lehoczky J (1989) Aperiodic task scheduling for hard-real-time systems. Real-Time Syst 1(1):27–60 CrossRef
van den Heuvel MM, Bril RJ, Lukkien JJ (2011) Dependable resource sharing for compositional real-time systems. In: 2011 IEEE 17th international conference on embedded and real-time computing systems and applications. IEEE Press, New York, pp 153–163. doi:10.​1109/​RTCSA.​2011.​29 CrossRef
Ward B, Anderson J (2012) Nested multiprocessor real-time locking with improved blocking. In: Proceedings of the 24th Euromicro conference on real-time systems
Metadaten
Titel
Analysis and implementation of the multiprocessor bandwidth inheritance protocol
verfasst von
Dario Faggioli
Giuseppe Lipari
Tommaso Cucinotta
Publikationsdatum
01.11.2012
Verlag
Springer US
Erschienen in
Real-Time Systems / Ausgabe 6/2012
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-012-9162-0

Weitere Artikel der Ausgabe 6/2012

Real-Time Systems 6/2012 Zur Ausgabe

OriginalPaper

FPSL, FPCL and FPZL schedulability analysis

OriginalPaper

Timing analysis of concurrent programs running on shared cache multi-cores

OriginalPaper

Laxity dynamics and LLF schedulability analysis on multiprocessor platforms

OriginalPaper

Memory-centric scheduling for multicore hard real-time systems

News

Guest editorial

Premium Partner

    Bildnachweise