nach oben

Design Automation for Embedded Systems

Erschienen in:

01.06.2013

The OMLP family of optimal multiprocessor real-time locking protocols

verfasst von: Björn B. Brandenburg, James H. Anderson

Erschienen in: Design Automation for Embedded Systems | Ausgabe 2/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents the first suspension-based multiprocessor real-time locking protocols with asymptotically optimal blocking bounds (under certain analysis assumptions). These protocols can be applied under any global, clustered, or partitioned job-level fixed-priority scheduler and support mutual exclusion, reader-writer exclusion, and k-exclusion constraints. Notably, the reader-writer and k-exclusion protocols are the first analytically-sound suspension-based multiprocessor real-time locking protocols of their kind. To formalize a notion of “optimal blocking,” precise definitions of what constitutes “blocking” in a multiprocessor real-time system are given and a simple complexity metric for real-time locking protocols, called maximum priority-inversion blocking (pi-blocking), is introduced. It is shown that, in a system with m processors, Ω(m) maximum pi-blocking is unavoidable. This bound is shown to be asymptotically tight with the introduction of the O(m) multiprocessor locking protocol (OMLP) family presented herein, which includes protocols that ensure an upper bound on maximum pi-blocking that is approximately within a factor of two of the lower bound. In addition to the coarse-grained asymptotic bounds, detailed blocking bounds suitable for schedulability analysis are derived using holistic blocking analysis. Based on the detailed bounds, the proposed locking protocols are compared with each other and with previously-proposed protocols in an empirical schedulability study involving more than one billion task sets. In this study, the OMLP was found to perform better than two variants of the classic (but non-optimal) multiprocessor priority-ceiling protocol (MPCP).

Vorheriger Artikel Model-based implementation of distributed systems with priorities

Nächster Artikel Symbolic system-level design methodology for multi-mode reconfigurable 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

Nur mit Berechtigung zugänglich

A protocol has a resource augmentation factor x if any feasible task set that is not schedulable under it is guaranteed to be schedulable on an x-times faster processor.

Without loss of generality, we assume uniform cluster sizes and \(\frac{m}{c}\in \mathbb {N}\). Non-uniform cluster sizes could be trivially integrated into the presented analysis at the expense of additional notation.

For the sake of simplicity, we assume that jobs require a processor for the entirety of each critical section. This is accurate for shared data structures, but may be somewhat pessimistic when accessing devices. The assumption could be relaxed at the expense of additional notation by splitting each request length parameter into a processor component and a suspension component.

Interestingly, in the uniprocessor case, the PCP [43, 47] and the SRP [3] both ensure O(1) maximum pi-blocking regardless of the number of requests, which is possible due to the lack of concurrency (after a job has acquired a resource once, lower-priority jobs cannot lock it again while higher-priority jobs are ready). In the multiprocessor case, resources may be repeatedly locked by concurrently-scheduled remote jobs, which implies that a job may incur pi-blocking each time that it issues a request.

The initial description of the OMLP [17] contained a variant for partitioned scheduling. This special case is not considered herein because, from an analytical point of view, it has since been superseded by the OMLP’s mutex protocol for clustered scheduling.

If WQ_q and CQ_q are both empty, then DQ_q is necessarily empty, too, as any readers in the draining queue would have had to enqueue when it was still the collecting queue (Rule R1) and the roles of CQ_q and DQ_q are only switched when a writer is waiting (Rules W1 and W3).

It is unknown whether N _i⋅(m−1) is a tight lower bound in absolute terms (i.e., non-asymptotically).

Bootstrapping is a standard technique for estimating sampling statistics for unknown population distributions (e.g., see [27]). Given a sample vector X=(x ₁,x ₂,…,x _s) consisting of s observations, N bootstrap sample vectors \(Y^{i} = (y_{1}^{i},y_{2}^{i},\ldots,y^{i}_{s})\), where i∈{1,…,N}, are constructed by uniformly choosing each \(y^{i}_{k} \in\{x_{1}, x_{2}, \ldots, x_{s}\}\) (i.e., each Y ⁱ is drawn from X with replacement). The distribution of a statistic f(X) can then be estimated by applying f to each Y ⁱ; an estimate of the 95 %-confidence interval of f(X) can be obtained from the 2.5th and 97.5th percentiles of the histogram of f(Y ⁱ). In our experiments, each x _k, where 1≤k≤s=1,000, is a schedulability test result (i.e., x _k∈{0,1}) and the computed statistic is the sample mean (i.e., the fraction of schedulable task sets). Bootstrapping is well-suited to schedulability experiments since it does not make any assumptions about the underlying population distribution. We used N=10,000 bootstrap samples.

Andersson B, Easwaran A (2010) Provably good multiprocessor scheduling with resource sharing. Real-Time Syst 46(2):153–159 CrossRefMATH

Audsley N, Burns A, Richardson M, Tindell K, Wellings A (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284–292 CrossRef

Baker T (1991) Stack-based scheduling for realtime processes. Real-Time Syst 3(1):67–99 CrossRef

Baker T (2005) A comparison of global and partitioned EDF schedulability tests for multiprocessors. Tech Rep TR-051101, Florida State University

Baker T, Baruah S (2007) Schedulability analysis of multiprocessor sporadic task systems. In: Handbook of real-time and embedded systems. Chapman Hall/CRC, London

Baker T, Baruah S (2009) Sustainable multiprocessor scheduling of sporadic task systems. In: Proceedings of the 21st Euromicro conference on real-time systems, pp 141–150

Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: Proceedings of the 28th IEEE real-time systems symposium, pp 119–128

Baruah S, Burns A (2006) Sustainable scheduling analysis. In: Proceedings of the 27th IEEE real-time systems symposium, pp 159–168

Bastoni A (2011) Towards the integration of theory and practice in multiprocessor real-time scheduling. Ph.D. thesis, Universita‘ degli Studi di Roma “Tor Vergata”

10.

Bastoni A, Brandenburg B, Anderson J (2010) An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers. In: Proceedings of the 31st IEEE real-time systems symposium, pp 14–24

11.

Bastoni A, Brandenburg B, Anderson J (2011) Is semi-partitioned scheduling practical? In: Proceedings of the 23rd Euromicro conference on real-time systems, pp 125–135

12.

Bertogna M, Cirinei M (2007) Response-time analysis for globally scheduled symmetric multiprocessor platforms. In: Proceedings of the 28th IEEE real-time systems symposium, pp 149–160

13.

Block A, Leontyev H, Brandenburg B, Anderson J (2007) A flexible real-time locking protocol for multiprocessors. In: Proceedings of the 13th IEEE conference on embedded and real-time computing systems and applications, pp 47–57

14.

Brandenburg B (2011) Scheduling and locking in multiprocessor real-time operating systems. Ph.D. thesis, The University of North Carolina at Chapel Hill

15.

Brandenburg B, Anderson J (2008) A comparison of the M-PCP, D-PCP, and FMLP on LITMUS^RT. In: Proceedings of the 12th international conference on principles of distributed systems. LNCS, vol 5401. Springer, Berlin, pp 105–124 CrossRef

16.

Brandenburg B, Anderson J (2008) An implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP real-time synchronization protocols in LITMUS^RT. In: Proceedings of the 14th IEEE real-time and embedded technology and applications symposium, pp 185–194

17.

Brandenburg B, Anderson J (2010) Optimality results for multiprocessor real-time locking. In: Proceedings of the 31st real-time systems symposium, pp 49–60

18.

Brandenburg B, Anderson J (2010) Spin-based reader-writer synchronization for multiprocessor real-time systems. Real-Time Syst 46(1):25–87 CrossRefMATH

19.

Brandenburg B, Anderson J (2011) Real-time resource-sharing under clustered scheduling: mutex, reader-writer, and k-exclusion locks. In: Proceedings of the 9th ACM international conference on embedded software

20.

Brandenburg B, Calandrino J, Block A, Leontyev H, Anderson J (2008) Synchronization on real-time multiprocessors: to block or not to block, to suspend or spin? In: Proceedings of the 14th IEEE real-time and embedded technology and applications symposium, pp 342–353

21.

Calandrino J, Anderson J, Baumberger D (2007) A hybrid real-time scheduling approach for large-scale multicore platforms. In: Proceedings of the 19th Euromicro conference on real-time systems, pp 247–256 CrossRef

22.

Calandrino J, Leontyev H, Block A, Devi U, Anderson J (2006) LITMUS^RT: a testbed for empirically comparing real-time multiprocessor schedulers. In: Proceedings of the 27th IEEE real-time systems symposium, pp 111–123

23.

Carpenter J, Funk S, Holman P, Srinivasan A, Anderson J, Baruah S (2004) A categorization of real-time multiprocessor scheduling problems and algorithms. In: Handbook of scheduling: algorithms, models, and performance analysis. Chapman Hall/CRC, London

24.

Chen C, Tripathi S (1994) Multiprocessor priority ceiling based protocols. Tech Rep CS-TR-3252, Univ of Maryland

25.

Chen M, Lin K (1991) A priority ceiling protocol for multiple-instance resources. In: Proceedings of the 12th IEEE real-time system symposium, pp 140–149

26.

Courtois P, Heymans F, Parnas D (1971) Concurrent control with “readers” and “writers”. Commun ACM 14(10):667–668 CrossRef

27.

Davison A, Hinkley D (1997) Bootstrap methods and their application. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, Cambridge CrossRefMATH

28.

Devi U, Leontyev H, Anderson J (2006) Efficient synchronization under global EDF scheduling on multiprocessors. In: Proceedings of the 18th Euromicro conference on real-time systems, pp 75–84 CrossRef

29.

Easwaran A, Andersson B (2009) Resource sharing in global fixed-priority preemptive multiprocessor scheduling. In: Proceedings of the 30th IEEE real-time systems symposium, pp 377–386

30.

Elliott G, Anderson J (2011) An optimal k-exclusion real-time locking protocol motivated by multi-GPU systems. In: Proceedings of the 19th international conference on real-time and network systems

31.

Faggioli D, Lipari G, Cucinotta T (2010) The multiprocessor bandwidth inheritance protocol. In: Proceedings of the 22nd Euromicro conference on real-time systems, pp 90–99

32.

Gai P, di Natale M, Lipari G, Ferrari A, Gabellini C, Marceca P (2003) A comparison of MPCP and MSRP when sharing resources in the Janus multiple processor on a chip platform. In: Proceedings of the 9th IEEE real-time and embedded technology application symposium, pp 189–198

33.

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

34.

Hsiu PC, Lee DN, Kuo TW (2011) Task synchronization and allocation for many-core real-time systems. In: Proceedings of the 9th ACM international conference on embedded software. ACM, New York, pp 79–88

35.

Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390–395 CrossRefMathSciNet

36.

Lakshmanan K, Niz D, Rajkumar R (2009) Coordinated task scheduling, allocation and synchronization on multiprocessors. In: Proceedings of the 30th IEEE real-time systems symposium, pp 469–478

37.

Liu C, Layland J (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 30:46–61 CrossRefMathSciNet

38.

Liu J (2000) Real-time systems. Prentice Hall, New York

39.

Macariu G, Cretu V (2011) Limited blocking resource sharing for global multiprocessor scheduling. In: Proceedings of the 23rd Euromicro conference on real-time systems, pp 262–271

40.

Nemati F, Behnam M, Nolte T (2011) Independently-developed real-time systems on multi-cores with shared resources. In: Proceedings of the 23rd Euromicro conference on real-time systems, pp 251–261

41.

Nemati F, Nolte T, Behnam M (2010) Partitioning real-time systems on multiprocessors with shared resources. In: Proceedings of the 14th international conference on principles of distributed systems. LNCS, vol 6490, pp 253–269 CrossRef

42.

Rajkumar R (1990) Real-time synchronization protocols for shared memory multiprocessors. In: Proceedings of the 10th international conference on distributed computing systems, pp 116–123 CrossRef

43.

Rajkumar RS (1991) In: Real-time systems—a priority inheritance approach. Kluwer Academic, Dordrecht

44.

Rajkumar R, Sha L, Lehoczky J (1988) Real-time synchronization protocols for multiprocessors. In: Proceedings of the 9th IEEE real-time systems symposium, pp 259–269 CrossRef

45.

Ridouard F, Richard P, Cottet F (2004) Negative results for scheduling independent hard real-time tasks with self-suspensions. In: Proceedings of the 25th IEEE real-time systems symposium, pp 47–56 CrossRef

46.

Schliecker S, Negrean M, Ernst R (2009) Response time analysis on multicore ECUs with shared resources. IEEE Trans Ind Informatics 5(4):402–413 CrossRef

47.

Sha L, Rajkumar R, Lehoczky J (1990) Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans Comput 39(9):1175–1185 CrossRefMathSciNet

Titel: The OMLP family of optimal multiprocessor real-time locking protocols
verfasst von: Björn B. Brandenburg
James H. Anderson
Publikationsdatum: 01.06.2013
Verlag: Springer US
Erschienen in: Design Automation for Embedded Systems / Ausgabe 2/2013
Print ISSN: 0929-5585
Elektronische ISSN: 1572-8080
DOI: https://doi.org/10.1007/s10617-012-9090-1

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 2/2013

On the hard-real-time scheduling of embedded streaming applications

Symbolic system-level design methodology for multi-mode reconfigurable systems

Fault buffers

Virtualizing on-chip distributed ScratchPad memories for low power and trusted application execution

Instruction scheduling with k-successor tree for clustered VLIW processors

Model-based implementation of distributed systems with priorities

Premium Partner