Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems

详细信息    查看全文

• 作者：Jinchao Chen ; Chenglie Du ; Fei Xie ; Zhenkun Yang
• 关键词：Schedulability analysis ; Non ; preemptive scheduling ; Strictly periodic task ; Multi ; core system ; Multi ; task scheduling
• 刊名：Real-Time Systems
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：52
• 期：3
• 页码：239-271
• 全文大小：1,811 KB
• 参考文献：Al-Sheikh A, Brun O, Hladik P, Prabhu B (2011) A best-response algorithm for multiprocessor periodic scheduling. In: 23rd Euromicro conference on real-time systems (ECRTS), 2011, pp 228–237
  Al-Sheikh A, Brun O, Hladik PE, Prabhu BJ (2012) Strictly periodic scheduling in IMA-based architectures. Real Time Syst 48(4):359–386CrossRef MATH
  Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: 28th IEEE international real-time systems symposium 2007, RTSS 2007, pp 119–128
  Baruah SK (2006) The non-preemptive scheduling of periodic tasks upon multiprocessors. Real Time Syst 32(1–2):9–20CrossRef MATH
  Bézout E (1779) Théorie générale des équations algébrique. PhD Pierres
  Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real Time Syst 30(1–2):129–154CrossRef MATH
  Cucu L, Sorel Y (2004) Non-preemptive multiprocessor scheduling for strict periodic systems with precedence constraints. In: Proceedings of 23rd annual workshop of the UK Planning and Scheduling Special Interest Group, PLANSIG, vol 4
  Davis RI, Burns A (2011) Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real Time Syst 47(1):1–40CrossRef MATH
  Eisenbrand F, Hhnle N, Niemeier M, Skutella M, Verschae J, Wiese A (2010a) Scheduling periodic tasks in a hard real-time environment. In: Proceedings of the 37th international colloquium conference on automata, languages and programming, ICALP’10. Springer, Berlin, pp 299–311
  Eisenbrand F, Kesavan K, Mattikalli R (2010b) Solving an avionics real-time scheduling problem by advanced ip-methods. In: de Berg M, Meyer U (eds) Algorithms ESA 2010. Lecture Notes in Computer Science, vol 6346. Springer, Berlin, pp 11–22
  Forget J, Boniol F, Grolleau E, Lesens D, Pagetti C (2010) Scheduling dependent periodic tasks without synchronization mechanisms. In: 2010 16th IEEE real-time and embedded technology and applications symposium (RTAS), pp 301–310. doi:10.​1109/​RTAS.​2010.​26
  Fudenberg D, Tirole J (1991) Game theory. The MIT Press, Cambridge, MAMATH
  George L, Rivierre N, Spuri M, Institut national de recherche en informatique et en automatique (France) (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Rapports de recherche. INRIA Centre, Paris
  Goossens J (2003) Scheduling of offset free systems. Real Time Syst 24(2):239–258. doi:10.​1023/​A:​1021782503695 CrossRef MATH
  Goossens J, Funk S, Baruah S (2003) Priority-driven scheduling of periodic task systems on multiprocessors. Real Time Syst 25(2–3):187–205. doi:10.​1023/​A:​1025120124771 CrossRef MATH
  Guan N, Yi W, Deng Q, Gu Z, Yu G (2011) Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling. J Syst Archit 57(5):536–546, special Issue on Multiprocessor Real-time Scheduling
  Heath T (1909) The thirteen books of Euclid’s elements, 2nd edn. Dover, New York
  IBM Corporation (2014) IBM ILOG CPLEX Optimizer. http://​www.​ibm.​com/​software/​commerce/​optimization/​cplex-optimizer/​ . Accessed 19 May 2014
  Jeffay K, Stanat D, Martel C (1991) On non-preemptive scheduling of period and sporadic tasks. In: Proceedings of the twelfth real-time systems symposium, 1991, pp 129–139
  Kermia O, Sorel Y (2008) Schedulability analysis for non-preemptive tasks under strict periodicity constraints. In: 14th IEEE international conference on embedded and real-time computing systems and applications, 2008, RTCSA ’08, pp 25–32
  Kermia O, Cucu L, Sorel Y (2006) Non-preemptive multiprocessor static scheduling for systems with precedence and strict periodicity constraints. In: Proceedings of the 10th international workshop on project management and scheduling, PMS06
  Korst J, Aarts E, Lenstra J, Wessels J (1991) Periodic multiprocessor scheduling. In: Aarts E, van Leeuwen J, Rem M (eds) PARLE ’91 parallel architectures and languages Europe. Lecture Notes in Computer Science, vol 505. Springer, Berlin, pp 166–178
  Lodi A, Linderoth J (2011) Milp software. In: Cochran J (ed) Wiley encyclopedia for operations research and management science. Wiley, New York
  Marouf M, Sorel Y (2011) Scheduling non-preemptive hard real-time tasks with strict periods. In: 2011 IEEE 16th conference on emerging technologies factory automation (ETFA), pp 1–8
  Park M (2007) Non-preemptive fixed priority scheduling of hard real-time periodic tasks. In: Shi Y, van Albada G, Dongarra J, Sloot P (eds) Computational science ICCS 2007. Lecture Notes in Computer Science, vol 4490. Springer, Berlin, pp 881–888. doi:10.​1007/​978-3-540-72590-9_​134
  Piaggio M, Sgorbissa A, Zaccaria R (2000) Pre-emptive versus non-pre-emptive real time scheduling in intelligent mobile robotics. J Exp Theor Artif Intell 12(2):235–245CrossRef MATH
  Pira C, Artigues C (2013) Line search method for solving a non-preemptive strictly periodic scheduling problem. In: Kendall G, McCollum B, Vanden Berghe G (eds) 6th multidisciplinary international scheduling conference: theory and applications (MISTA 2013), Gent, Belgium, pp 356–371
  Pira C, Artigues C (2014) Line search method for solving a non-preemptive strictly periodic scheduling problem. J Sched pp 1–17
  Stankovic J, Zhu R (2003) Vest: an aspect-based composition tool for real-time systems. In: Proceedings of the 9th IEEE real-time and embedded technology and applications symposium, 2003, pp 58–69
  Tendulkar P, Poplavko P, Maler O (2014) Strictly periodic scheduling of acyclic synchronous dataflow graphs using SMT solvers. Technical report TR-2014-5. Verimag research report
  Zeng H, Di Natale M (2012) Schedulability analysis of periodic tasks implementing synchronous finite state machines. In: 24th Euromicro conference on real-time systems (ECRTS), 2012, pp 353–362
  
• 作者单位：Jinchao Chen (1)
  Chenglie Du (1)
  Fei Xie (2)
  Zhenkun Yang (2)
  
  1. Department of Computer Science, Northwestern Polytechnical University, Xi’an, 710072, China
  2. Department of Computer Science, Portland State University, Portland, 97201, USA
  
• 刊物类别：Computer Science
• 刊物主题：Computer Systems Organization and Communication Networks
  Communications Engineering and Networks
  Special Purpose and Application-Based Systems
  Performance and Reliability
  Control Engineering
  
• 出版者：Springer Netherlands
• ISSN：1573-1383

文摘

Non-preemptive tasks with strict periods are usually adopted in practical real-time systems where missing deadlines may lead to catastrophic situations. Their schedulability analysis plays a crucial role in guiding the design and development of such real-time systems. In this paper, we study the schedulability analysis problem of partitioned non-preemptive scheduling for strictly periodic tasks on multiprocessors. We propose a set of schedulability conditions, which determines whether a new task can be scheduled on a processor without changing the offsets of the existing tasks and identifies all valid start time offsets for the new task if it is schedulable. Based on these conditions, we present a task assignment algorithm, which is not optimal, but provides an upper bound on the number of cores required by a periodic task set. We illustrate this algorithm with a practical example and conduct stimulation experiments with randomly generated task sets to evaluate the performance of our approach from several aspects.