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
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

5. Analyzing Non-preemptive Global Scheduling

verfasst von : Nan Guan

Erschienen in: Techniques for Building Timing-Predictable Embedded Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Non-preemptive scheduling is usually considered inferior to preemptive scheduling for time critical systems, because the non-preempti1ve block would lead to poor task responsiveness.

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
Vorheriges Kapitel Analyzing Preemptive Global Scheduling
Nächstes Kapitel Liu and Layland’s Utilization Bound
Fußnoten
1
One can get a tighter bound on W with a more precise calculation of carry-in/carry-out. However, to get a linear over-approximation of workload in the derivation of the first test condition in the following, a bound needs to be relaxed anyway, which leads to the same result as using this simple bound.
 
Literatur
1.
2.
V. Suhendra, T. Mitra, Exploring locking and partitioning for predictable shared caches on multi-cores, in DAC, 2008
3.
4.
R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. FerdinanRd, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, P. Stenström, The worst-case execution-time problem overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7(3), 36:1–36:53 (2008)
5.
H. Theiling, Control flow graphs for real-time system analysis: reconstruction from binary executables and usage in ilp-based path analysis. Ph.D. thesis, Universitat des Saarlandes, 2002
6.
C. Cullmann, F. Martin, Data-flow based detection of loop bounds, in 7th International Workshop on Worst-Case Execution Time (WCET) Analysis, ed. by C. Rochange (Dagstuhl, Wadern). Internationales Begegnungs- und Forschungszentrum f”ur Informatik (IBFI) (Schloss Dagstuhl, Wadern, 2007)
7.
J. Gustafsson, A. Ermedahl, C. Sandberg, B. Lisper, Automatic derivation of loop bounds and infeasible paths for wcet analysis using abstract execution, in RTSS (IEEE Computer Society, Washington, DC, 2006), pp. 57–66
8.
C. Healy, M. Sjödin, V. Rustagi, D. Whalley, R. Van Engelen, Supporting timing analysis by automatic bounding of loop iterations. Real-Time Syst. 18(2/3), 129–156 (2000)CrossRef
9.
F. Stappert, P. Altenbernd, Complete worst-case execution time analysis of straight-line hard real-time programs. J. Syst. Archit. 46(4), 339–355 (2000)CrossRef
10.
P. Altenbernd, On the false path problem in hard real-time programs, in Proceedings of the 8th Euromicro Workshop on Real-Time Systems, 1996, pp. 102–107
11.
C.A. Healy, D.B. Whalley, Automatic detection and exploitation of branch constraints for timing analysis. IEEE Trans. Softw. Eng. 28(8), 763–781 (2002)CrossRef
12.
R. Wilhelm, P. Lucas, O. Parshin, L. Tan, B. Wachter, Improving the precision of WCET analysis by input constraints and model-derived flow constraints, in Advances in Real-Time Systems, ed. by S. Chakraborty, J. Eberspächer. Lecture Notes in Computer Science. (Springer, Berlin, 2011)
13.
J. Engblom, Processor pipelines and static worst-case execution time analysis. Ph.D. Thesis, Uppsala University, 2002
14.
X. Li, A. Roychoudhury, T. Mitra, Modeling out-of-order processors for software timing analysis, in RTSS, 2004, pp. 92–103
15.
S. Thesing, Safe and precise wcet determination by abstract interpretation of pipeline models. Ph.D. thesis, Universitat des Saarlandes, 2004
16.
S. Wilhelm, B. Wachter, Symbolic state traversal for wcet analysis, in EMSOFT (ACM, New York, NY, 2009), pp. 137–146
17.
E. Althaus, S. Altmeyer, R. Naujoks, Precise and efficient parametric path analysis, in LCTES (ACM, New York, NY, 2011), pp. 141–150
18.
Y.-T. Steven Li, S. Malik, Performance analysis of embedded software using implicit path enumeration, in DAC (ACM, New York, NY, 1995), pp. 456–461
19.
20.
H. Theiling, Ilp-based interprocedural path analysis, in EMSOFT ’02 (Springer, London, 2002), pp. 349–363
21.
D. Grund, J. Reineke, Abstract interpretation of fifo replacement, in SAS (Springer, Berlin/Heidelberg, 2009), pp. 120–136
22.
N. Guan, M. Lv, W. Yi, G. Yu, Wcet analysis with mru caches: Challenging lru for predictability. in RTAS, 2012, pp. 55–64
23.
D. Grund, J. Reineke, Toward precise plru cache analysis, in WCET, 2010, pp. 23–35
24.
C. Ferdinand, Cache behavior prediction for real-time systems. Ph.D. thesis, Universitat des Saarlandes, 1997
25.
F. Mueller, Generalizing Timing Predictions to Set-Associative Caches, vol. 0 (IEEE Computer Society, Los Alamitos, CA, 1997), p. 64
26.
27.
R. Wilhelm, D. Grund, J. Reineke, M. Schlickling, M. Pister, C. Ferdinand, Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 28(7), 966–978 (2009)CrossRef
28.
D. Grund, J. Reineke, Precise and efficient fifo-replacement analysis based on static phase detection, in ECRTS (IEEE Computer Society, Washington, DC, 2010), pp. 155–164
29.
M. Lv, N. Guan, W. Yi, Q. Deng, G. Yu, Efficient instruction cache analysis with model checking, in RTAS, Work-in-Progress Session, 2010
30.
S. Baruah, A. Mok, L. Rosier, Preemptively scheduling hard-real-time sporadic tasks on one processor, in RTSS, 1990
31.
32.
33.
On-Line Applications Research Corporation (OAR), RTEMS Applications C User’s Guide (2001)
34.
J. Calandrino, H. Leontyev, A. Block, U. Devi, J. Anderson, Litmusrt: a testbed for empirically comparing real-time multiprocessor schedulers, in RTSS, 2006
35.
J.P. Lehoczky, Fixed priority scheduling of periodic task sets with arbitrary deadlines, in RTSS, 1990
36.
R.I. Davis, A. Burns, R.J. Bril, J.J. Lukkien, Controller Area Network (CAN) schedulability analysis: refuted, revisited and revised. Real-Time Syst. 35(3), 239–272 (2007)CrossRef
37.
L. George, N. Rivierre, M. Spuri, Preemptive and non-preemptive real-time uni-processor scheduling. Technical Report, INRIA, 1996
38.
39.
40.
A. Hamann, M. Jersak, K. Richter, R. Ernst, Design space exploration and system optimization with symta/s-symbolic timing analysis for systems, in RTSS, 2004
41.
M. Gonzalez Harbour, J. Palencia Gutierrez, Schedulability analysis for tasks with static and dynamic offsets, in RTSS, 1998
42.
K. Tindell, Adding time-offsets to schedulability analysis. Technical Report, 1994
43.
44.
M. Stigge, N. Guan, W. Yi, Refinement-based exact response time analysis. Technical Report, 2014CrossRef
45.
T.W. Kuo, A.K. Mok, Load adjustment in adaptive real-time systems, in RTSS, 1991
46.
C. Lu, J.A. Stankovic, S.H. Son, G. Tao, Feedback control real-time scheduling: framework, modeling, and algorithms. Real-Time Syst. 23(1–2), 85–126 (2002)CrossRefMATH
47.
C.L. Liu, Scheduling algorithms for multiprocessors in a hard real-time environment, in JPL Space Programs Summary, 1969
48.
49.
R.I. Davis, A. Burns, A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43(4), 35:1–35:44 (2011)
50.
B. Andersson, S. Baruah, J. Jonsson, Static-priority scheduling on multiprocessors, in RTSS, 2001
51.
B. Andersson, Global static priority preemptive multiprocessor scheduling with utilization bound 38%, in OPODIS, 2008
52.
T.P. Baker, Multiprocessor edf and deadline monotonic schedulability analysis, in RTSS, 2003
53.
S.K. Baruah, Techniques for multiprocessor global schedulability analysis, in RTSS, 2007
54.
M. Bertogna, M. Cirinei, G. Lipari, Improved schedulability analysis of edf on multiprocessor platforms, in ECRTS, 2005
55.
N. Guan, M. Stigge, W. Yi, G. Yu, New response time bounds for fixed priority multiprocessor scheduling, in Proceedings of the 30st IEEE Real-Time Systems Symposium (RTSS), 2009
56.
B. Andersson, J. Jonsson, Some insights on fixed-priority preemptive non-partitioned multiprocessor scheduling. Technical Report, Chalmers University of Technology, 2001
57.
S. Lauzac, R.G. Melhem, D. Mosse, Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor, in ECRTS, 1998
58.
59.
B. Andersson, J. Jonsson, The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%, in Euromicro Conference on Real-Time Systems (ECRTS), 2003
60.
S. Baruah, N. Fisher, The partitioned multiprocessor scheduling of sporadic task systems, in RTSS, 2005
61.
A. Burchard, J. Liebeherr, Y. Oh, S.H. Son, New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. Comput. 44(12), 1429–1442 (1995)MathSciNetCrossRefMATH
62.
N. Fisher, S.K. Baruah, T.P. Baker, The partitioned scheduling of sporadic tasks according to static-priorities, in ECRTS, 2006, pp. 118–127
63.
64.
S.K. Dhall, S. Davari, On a periodic real time task allocation problem, in Annual International Conference on System Sciences, 1986
65.
66.
J. Anderson, V. Bud, U.C. Devi, An EDF-based scheduling algorithm for multiprocessor soft real-time systems, in ECRTS, 2005
67.
B. Andersson, K. Bletsas, S. Baruah, Scheduling arbitrary-deadline sporadic task systems multiprocessors, in RTSS, 2008
68.
N. Guan, M. Stigge, W. Yi, G. Yu, Fixed-priority multiprocessor scheduling with Liu & Layland’s utilization bound, in RTAS, 2010
69.
S. Kato, N. Yamasaki, Portioned EDF-based scheduling on multiprocessors, in EMSOFT, 2008
70.
A. Abel, F. Benz, J. Doerfert, B. Dörr, S. Hahn, F. Haupenthal, M. Jacobs, A.H. Moin, J. Reineke, B. Schommer, R. Wilhelm, Impact of resource sharing on performance and performance prediction: a survey, in CONCUR, 2013, pp. 25–43
71.
C. Rochange, An overview of approaches towards the timing analysability of parallel architecture, in PPES, 2011, pp. 32–41
72.
J.C. Palencia Gutiérrez, J.J. Gutiérrez García, M. González Harbour, On the schedulability analysis for distributed hard real-time systems, in RTS, 1997, pp. 136–143
73.
74.
S. Chakraborty, S. Künzli, L. Thiele, A general framework for analysing system properties in platform-based embedded system designs, in DATE, 2003, pp. 10190–10195
75.
J. Rox, R. Ernst, Compositional performance analysis with improved analysis techniques for obtaining viable end-to-end latencies in distributed embedded systems, in STTT, 2013
76.
L. Thiele, S. Chakraborty, M. Naedele, Real-time calculus for scheduling hard real-time systems, in ISCAS 2000, vol. 4, 2000, pp. 101–104
77.
J.-Y. Le Boudec, P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet (Springer, Berlin/Heidelberg, 2001)CrossRef
78.
E. Wandeler, Modular performance analysis and interface-based design for embedded real-time systems. Ph.D. thesis, ETHZ, 2006
79.
B. Jonsson, S. Perathoner, L. Thiele, W. Yi, Cyclic dependencies in modular performance analysis, in EMSOFT, 2008, pp. 179–188
80.
81.
J. Hennessy, D. Patterson, Computer Architecture – A Quantitative Approach, 4th edn. (Morgan Kaufmann, San Francisco, 2007)
82.
H. Al-Zoubi, A. Milenkovic, M. Milenkovic, Performance evaluation of cache replacement policies for the spec cpu2000 benchmark suite, in ACM-SE 42 (ACM, New York, NY, 2004), pp. 267–272
83.
D. Eklov, N. Nikoleris, D. Black-Schaffer, E. Hagersten, Cache pirating: measuring the curse of the shared cache, in ICPP (IEEE Computer Society, Washington, DC, 2011), pp. 165–175
84.
G. Grohoski, Niagara-2: a highly threaded server-on-a-chip, in HotChips, 2006
85.
T.P. Baker, M. Cirinei, Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks, in OPODIS, 2007, pp. 62–75
86.
Q. Deng, S. Gao, N. Guan, Z. Gu, G. Yu, Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking, in Proceedings of the 5th IFIP Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS), 2007
87.
N. Guan, Z. Gu, M. Lv, Q. Deng, G. Yu, Schedulability analysis of global fixed-priority or edf multiprocessor scheduling with symbolic model-checking, in ISORC, 2008, pp. 556–560
88.
Y. Li, V. Suhendra, Y. Liang, T. Mitra, A. Roychoudhury, Timing analysis of concurrent programs running on shared cache multi-cores, in RTSS, 2009, pp. 57–67
89.
J. Yan, W. Zhang, Wcet analysis for multi-core processors with shared l2 instruction caches, in RTAS, 2008
90.
W. Zhang, J. Yan, Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches, in RTCSA, 2009, pp. 455–463
91.
S. Perathoner, EDF scheduling with real time calculus, in Presentation, TEC Group, Computer Engineering and Networks Laboratory, ETH Zurich, 2007
92.
J.P. Erickson, J.H. Anderson, Fair lateness scheduling: reducing maximum lateness in g-edf-like scheduling, in ECRTS (2012)
93.
H. Leontyev, J.H. Anderson, Generalized tardiness bounds for global multiprocessor scheduling. Real-Time Syst. 44(1–3), 26–71 (2010)CrossRefMATH
94.
M. Spuri, Analysis of deadline scheduled real-time systems, in RR-2772, INRIA, France, 1996
95.
J. Reineke, Caches in wcet analysis – predictability, competitiveness, sensitivity. Ph.D. thesis, Saarland University, 2008
96.
R. Heckmann, M. Langenbach, S. Thesing, R. Wilhelm, The influence of processor architecture on the design and the results of wcet tools, in Proceedings of the IEEE (2003)
97.
A. Malamy, R.N. Patel, N.M. Hayes, Methods and apparatus for implementing a pseudo-lru cache memory replacement scheme with a locking feature. US Patent 5029072, 1994
98.
A.S. Tanenbaum, Modern Operating Systems, 3rd edn. (Prentice Hall Press, Upper Saddle River, NJ, 2007)
99.
100.
P. Kongetira, K. Aingaran, K. Olukotun, Niagara: a 32-way multithreaded sparc processor. IEEE Micro 25(2), 21–29 (2005)CrossRef
101.
J. Reineke, D. Grund, Relative competitive analysis of cache replacement policies, in Proceedings of the 2008 ACM SIGPLAN-SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES ’08 (ACM, New York, NY, 2008), pp. 51–60
102.
Y.-T.S. Li, S. Malik, A. Wolfe, Cache modeling for real-time software: beyond direct mapped instruction caches, in RTSS (IEEE Computer Society, Washington, DC, 1996), pp. 254–261
103.
R.D. Arnold, F. Mueller, D.B. Whalley, M.G. Harmon, Bounding worst-case instruction cache performance, in RTSS (IEEE Computer Society, 1994), pp. 172–181
104.
F. Mueller, Static cache simulation and its applications. Ph.D. thesis, Florida State University, 1994
105.
106.
C. Ballabriga, H. Casse, Improving the first-miss computation in set-associative instruction caches, in ECRTS (IEEE Computer Society, Washington, DC, 2008), pp. 341–350
107.
C. Cullmann, Cache persistence analysis: a novel approach theory and practice, in LCTES (ACM, New York, NY, 2011), pp. 121–130
108.
C. Ferdinand, R. Wilhelm, On predicting data cache behavior for real-time systems, in Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, LCTES ’98 (Springer, London, 1998), pp. 16–30
109.
R. Sen, Y.N. Srikant, Wcet estimation for executables in the presence of data caches, in Proceedings of the 7th ACM & IEEE International Conference on Embedded Software, EMSOFT ’07 (ACM, New York, NY, 2007), pp. 203–212CrossRef
110.
B.K. Huynh, L. Ju, A. Roychoudhury, Scope-aware data cache analysis for wcet estimation, in RTAS (IEEE Computer Society, Washington, DC, 2011), pp. 203–212
111.
D. Hardy, I. Puaut, Wcet analysis of multi-level non-inclusive set-associative instruction caches, in RTSS (IEEE Computer Society, Washington, DC, 2008), pp. 456–466
112.
T. Sondag, H. Rajan, A more precise abstract domain for multi-level caches for tighter wcet analysis, in RTSS (IEEE Computer Society, Washington, DC, 2010), pp. 395–404
113.
Y. Li, V. Suhendra, Y. Liang, T. Mitra, A. Roychoudhury, Timing analysis of concurrent programs running on shared cache multi-cores, in RTSS (IEEE Computer Society, Washington, DC, 2009), pp. 57–67
114.
S. Chattopadhyay, A. Roychoudhury, T. Mitra, Modeling shared cache and bus in multi-cores for timing analysis, in Proceedings of the 13th International Workshop on Software & Compilers for Embedded Systems, SCOPES ’10 (ACM, New York, NY, 2010), pp. 6:1–6:10
115.
116.
S. Altmeyer, C. Maiza, J. Reineke, Resilience analysis: tightening the crpd bound for set-associative caches, in LCTES (ACM, New York, NY, 2010), pp. 153–162
117.
118.
119.
F.E. Allen, Control flow analysis, in Proceedings of Symposium on Compiler Optimization (ACM, New York, NY, 1970), pp. 1–19CrossRef
120.
A.V. Aho, R. Sethi, J.D. Ullman, Compilers: Principles, Techniques, and Tools (Addison-Wesley Longman Publishing Co. Inc., Boston, MA, 1986)
121.
J. Gustafsson, A. Betts, A. Ermedahl, B. Lisper, The mälardalen wcet benchmarks: past, present and future, in 10th International Workshop on Worst-Case Execution-Time Analysis, WCET’10, 2010
122.
123.
T. Austin, E. Larson, D. Ernst, Simplescalar: an infrastructure for computer system modeling. Computer 35(2), 59–67 (2002)CrossRef
124.
125.
126.
R. Wilhelm, Why AI + ILP is good for WCET, but MC is not, nor ILP alone, in VMCAI, 2004
127.
E.W. Dijkstra, Chapter I: notes on structured programming, in Structured Programming (Academic, London, 1972), pp. 1–82
128.
M. Berkelaar, lp_solve: a mixed integer linear program solver. Relatorio Tecnico, Eindhoven University of Technology, 1999
129.
M. Bertogna, M. Cirinei, Response-time analysis for globally scheduled symmetric multiprocessor platforms, in Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS), 2007
130.
E. Bini, T.H.C. Nguyen, P. Richard, S.K. Baruah, A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans. Comput. 58(2), 279–286 (2009)MathSciNetCrossRef
131.
K. Tindell, H. Hansson, A. Wellings, Analysing realtime communications: controller area network (can), in RTSS, 1994
132.
A. Burns, A. Wellings, Real-Time Systems and Programming Languages, 3rd edn. (Addison-Wesley, Boston, 2001)
133.
L. Lundberg, Multiprocessor scheduling of age constraint processes, in RTCSA, 1998
134.
N. Guan, W. Yi, Z. Gu, Q. Deng, G. Yu, New schedulability test conditions for non-preemptive scheduling on multiprocessor platforms, in RTSS, 2008
135.
T.P. Baker, A comparison of global and partitioned edf schedulability tests for multiprocessors. Technical Report, Department of Computer Science, Florida State University, FL, 2005
136.
137.
K. Jeffay, D.F. Stanat, C.U. Martel, On non-preemptive scheduling of periodic and sporadic tasks, in Proceedings of the 12th IEEE Real-Time Systems Symposium (RTSS), 1991
138.
H. Leontyev, J.H. Anderson, A unified hard/soft real-time schedulability test for global edf multiprocessor scheduling, in Proceedings of the 29th IEEE Real-Time Systems Symposium (RTSS), 2008
139.
140.
C.A. Phillips, C. Stein, E. Torng, J. Wein, Optimal time-critical scheduling via resource augmentation, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), 1997
141.
S.K. Baruah, S. Chakraborty, Schedulability analysis of non-preemptive recurring real-time tasks, in The 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), 2006
142.
143.
144.
S.K. Baruah, A. Burns, Sustainable scheduling analysis, in Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS), 2006
145.
A.K. Mok, W.-C. Poon, Non-preemptive robustness under reduced system load, in Proceedings of the 26th IEEE Real-Time Systems Symposium (RTSS), 2005
146.
R. Ha, J.W.S. Liu, Validating timing constraints in multiprocessor and distributed real-time systems, in Proceedings of the 14th International Conference on Distributed Computing Systems (ICDCS), 1994
147.
T.P. Baker, S. Baruah, Sustainable multiprocessor scheduling of sporadic task systems, in ECRTS, 2009
148.
149.
150.
U. Devi, J. Anderson, Tardiness bounds for global edf scheduling on a multiprocessor, in IEEE Real-Time Systems Symposium (RTSS), 2005
151.
K. Lakshmanan, R. Rajkumar, J. Lehoczky, Partitioned fixed-priority preemptive scheduling for multi-core processors, in ECRTS, 2009
152.
B. Andersson, E. Tovar, Multiprocessor scheduling with few preemptions, in RTCSA, 2006
153.
B. Andersson, K. Bletsas, Sporadic multiprocessor scheduling with few preemptions, in Euromicro Conference on Real-Time Systems (ECRTS), 2008
154.
S. Kato, N. Yamasaki, Real-time scheduling with task splitting on multiprocessors, in IEEE Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2007
155.
S. Kato, N. Yamasaki, Y. Ishikawa, Semi-partitioned scheduling of sporadic task systems on multiprocessors, in ECRTS, 2009
156.
S. Kato,N. Yamasaki, Portioned static-priority scheduling on multiprocessors, in IPDPS, 2008
157.
S. Kato, N. Yamasaki, Semi-partitioned fixed-priority scheduling on multiprocessors, in RTAS, 2009
158.
J.W.S. Liu, Real-Time Systems (Prentice Hall, Upper Saddle River, 2000)
159.
J.P. Lehoczky, L. Sha, Y. Ding, The rate monotonic scheduling algorithm: exact characterization and average case behavior, in RTSS, 1989
160.
161.
H. Cho, B. Ravindran, E. Jensen, An optimal realtime scheduling algorithm for multiprocessors, in RTSS, 2006
162.
K. Funaoka et al., Work-conserving optimal real-time scheduling on multiprocessors, in ECRTS, 2008
163.
S. Lauzac, R. Melhem, D. Mosse, An efficient rms admission control and its application to multiprocessor scheduling, in IPPS, 1998
164.
165.
B.K. Bershad, B.J. Chen, D. Lee, T.H. Romer, Avoiding conflict misses dynamically in large direct mapped caches, in ASPLOS, 1994
166.
J. Herter, J. Reineke, R. Wilhelm, Cama: cache-aware memory allocation for wcet analysis, in ECRTS, 2008
167.
J. Rosen, A. Andrei, P. Eles, Z. Peng, Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip, in RTSS, 2007
168.
A. Fedorova, M. Seltzer, C. Small, D. Nussbaum, Throughput-oriented scheduling on chip multithreading systems. Technical Report, Harvard University, 2005
169.
D. Chandra, F. Guo, S. Kim, Y. Solihin, Predicting inter-thread cache contention on a multi-processor architecture, in HPCA, 2005
170.
J.H. Anderson, J.M. Calandrino, U.C. Devi, Real-time scheduling on multicore platforms, in RTAS, 2006
171.
J.H. Anderson, J.M. Calandrino, Parallel real-time task scheduling on multicore platforms, in RTSS, 2006
172.
J.M. Calandrino, J.H. Anderson, Cache-aware real-time scheduling on multicore platforms: heuristics and a case study, in ECRTS, 2008
173.
K. Danne, M. Platzner, An edf schedulability test for periodic tasks on reconfigurable hardware devices, in LCTES, 2006
174.
N. Guan, Q. Deng, Z. Gu, W. Xu, G. Yu, Schedulability analysis of preemptive and non-preemptive edf on partial runtime-reconfigurable fpgas, in ACM Transaction on Design Automation of Electronic Systems, vol. 13, no. 4 (2008)
175.
N. Fisher, J. Anderson, S. Baruah, Task partitioning upon memory-constrained multiprocessors, in RTCSA, 2005, p. 1
176.
V. Suhendra, C. Raghavan, T. Mitra, Integrated scratchpad memory optimization and task scheduling for mpsoc architectures, in CASES, 2006
177.
H. Salamy, J. Ramanujam, A framework for task scheduling and memory partitioning for multi-processor system-on-chip, in HiPEAC, 2009
178.
179.
S. Dropsho, C. Weems, Comparing caching techniques for multitasking real-time systems. Technical Report, University of Massachusetts-Amherst, 1997
180.
B.D. Bui, M. Caccamo, L. Sha, J. Martinez, Impact of cache partitioning on multi-tasking real time embedded systems, in RTCSA, 2008
181.
D. Chiou, S. Devadas, L. Rudolph, B.S. Ang, Dynamic cache partitioning via columnization. Technical Report, MIT, 1999
182.
D. Tam, R. Azimi, M. Stumm, L. Soares, Managing shared l2 caches on multicore systems in software, WIOSCA, 2007
183.
J. Liedtke, H. Hartig, M. Hohmuth, Os-controlled cache predictability for real-time systems, in RTAS, 1997
184.
185.
C. Kim, D. Burger, S.W. Keckler, An adaptive, nonuniform cache structure for wiredelay dominated on-chip caches, in ASPLOS, 2002
186.
L. Thiele, S. Chakraborty, M. Naedele, Real-time calculus for scheduling hard real-time systems, in Proceedings of the International Symposium on Circuits and Systems, 2000
187.
J.L. Boudec, P. Thiran, Network calculus – a theory of deterministic queuing systems for the internet, in LNCS 2050 (Springer, Berlin, 2001)
188.
A. Maxiaguine, Y. Zhu, S. Chakraborty, W.-F. Wong, Tuning soc platforms for multimedia processing: identifying limits and tradeoffs, in CODES+ISSS, 2004
189.
J. Bengtsson, W. Yi, Timed automata: semantics, algorithms and tools, in Lectures on Concurrency and Petri Nets, 2003
190.
S. Perathoner, T. Rein, L. Thiele, K. Lampka, J. Rox, Modeling structured event streams in system level performance analysis, in LCTES, 2010
191.
L. Thiele E. Wandeler, Characterizing workload correlations in multi processor hard real-time systems, in RTAS, 2005
192.
L. Thiele, E. Wandeler, N. Stoimenov, Real-time interfaces for composing real-time systems, in EMSOFT, 2006
193.
L.T.X. Phan, S. Chakraborty, P.S. Thiagarajan, A multi-mode real-time calculus, in RTSS, 2008
194.
195.
M. Gonzalez Harbour, J.J. Gutierrez Garcia, J.C. Palencia Gutierrez, J.M. Drake Moyano, Mast: modeling and analysis suite for real time applications, in ECRTS (2001)
196.
S. Perathoner, E. Wandeler, L. Thiele, A. Hamann, S. Schliecker, R. Henia, R. Racu, R. Ernst, M. Gonzalez Harbour, Influence of different abstractions on the performance analysis of distributed hard real-time systems. Des. Autom. Embed. Syst. 13(1–2), 27–49 (2009). doi:10.1007/s10617-008-9015-1. http://​dx.​doi.​org/​10.​1007/​s10617-008-9015-1 CrossRef
197.
K. Lampka, S. Perathoner, L. Thiele, Analytic real-time analysis and timed automata: a hybrid method for analyzing embedded real-time systems, in EMSOFT, 2009
198.
M. Moy, K. Altisen, Arrival curves for real-time calculus: the causality problem and its solutions, in TACAS, 2010
199.
200.
K. Richter, Compositional scheduling analysis using standard event models. Ph.D. thesis, Technical University Carolo-Wilhelmina of Braunschweig, 2005
201.
K. Richter, Compositional scheduling analysis using standard event models. Ph.D. thesis, Technical University of Braunschweig, 2004
202.
V. Pollex, S. Kollmann, F. Slomka, Generalizing response-time analysis, in RTCSA, 2010
203.
L. Thiele et al., A framework for evaluating design tradeoffs in packet processing architectures, in DAC, 2002
204.
A. Easwaran, M. Anand, I. Lee, Compositional analysis framework using edp resource models, in RTSS, 2007
205.
I. Shin, I. Lee, Compositional real-time scheduling framework, in RTSS, 2004
206.
C. Kenna, J. Herman, B. Brandenburg, A. Mills, J. Anderson, Soft real-time on multiprocessors: are analysis-based schedulers really worth it?, in RTSS, 2011
207.
S. Perathoner, EDF scheduling with real time calculus, in Presentation Slides, TEC Group, Computer Engineering and Networks Laboratory, ETH Zurich, 2007
208.
Metadaten
Titel
Analyzing Non-preemptive Global Scheduling
verfasst von
Nan Guan
Copyright-Jahr
2016
Buch
Techniques for Building Timing-Predictable Embedded Systems

Print ISBN: 978-3-319-27196-5

Electronic ISBN: 978-3-319-27198-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-27198-9_5

Neuer Inhalt

    Bildnachweise