FPSL, FPCL and FPZL schedulability analysis

详细信息    查看全文

• 作者：Robert I. Davis (1) rob.davis@cs.york.ac.uk
  Shinpei Kato (2) shinpei@ece.cmu.edu
• 关键词：Real ; time – ; Schedulability analysis – ; Fixed priority – ; Zero laxity – ; Critical laxity – ; FPSL – ; FPCL – ; FPZL – ; Global scheduling – ; Multiprocessor
• 刊名：Real-Time Systems
• 出版年：2012
• 出版时间：November 2012
• 年：2012
• 卷：48
• 期：6
• 页码：750-788
• 全文大小：1.3 MB
• 参考文献：1. Andersson B, Jonsson J (2000) Some insights on fixed-priority pre-emptive non-partitioned multiprocessor scheduling. In: Proceedings real-time systems symposium (RTSS)—work-in-progress session
  2. Andersson B, Bletsas K, Baruah SK (2008) Scheduling arbitrary-deadline sporadic tasks on multiprocessors. In: Proceedings real-time systems symposium (RTSS)
  3. Audsley NC (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report YCS 164, Dept Computer Science, University of York, UK, Dec 1991
  4. Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Process Lett 79(1):39–44
  5. Baker TP (2003) Multiprocessor EDF and deadline monotonic schedulability analysis. In: Proceedings real-time systems symposium (RTSS), pp 120–129
  6. Baker TP (2006) An analysis of fixed-priority scheduling on a multiprocessor. Real-Time Syst 32(1–2):49–71
  7. Baker TP, Baruah SK (2009) Sustainable multiprocessor scheduling of sporadic task systems. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 141–150
  8. Baker TP, Cirinei M (2006) A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks. In: Proceedings real-time systems symposium (RTSS)—work-in-progress (WIP) session
  9. Baker TP, Cirinei M, Bertogna M (2008) EDZL scheduling analysis. Real-Time Syst 40(3):264–289
  10. Baruah SK (2007) Techniques for multiprocessor global schedulability analysis. In: Proceedings real-time systems symposium (RTSS), pp 119–128
  11. Baruah SK, Baker TP (2009) An analysis of global EDF schedulability for arbitrary sporadic task systems. Real-Time Syst 43(1):3–24, ECRTS special issue
  12. Baruah SK, Burns A (2006) Sustainable scheduling analysis. In: Proceedings real-time systems symposium (RTSS), pp 159–168
  13. Baruah SK, Fisher N (2008) Global fixed-priority scheduling of arbitrary-deadline sporadic…. In: Proc of the 9th int’l conference on distributed computing and networking, pp 215–226
  14. Baruah SK, Bonifaci V, Marchetti-Spaccamela A, Stiller S (2009) Implementation of a speedup-optimal global EDF schedulability test. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 259–268
  15. Bastoni A, Brandenburg BB, Anderson JH (2010a) An empirical comparison of global, partitioned, and clustered multiprocessor real-time schedulers. In: Proceedings real-time systems symposium (RTSS)
  16. Bastoni A, Brandenburg B, Anderson J (2010b) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: Proceedings of the sixth international workshop on operating systems platforms for embedded real-time applications (OSPERT 2010), July 2010, pp 33–44
  17. Beal D, Bianchi E, Dozio L, Hughes S, Mantegazza P, Papacharalambous S (2000) RTAI: real time application interface. Linux J 29:10
  18. Bertogna M (2007) Real-time scheduling analysis for multiprocessor platforms. PhD Thesis, Scuola Superiore Sant’Anna, Pisa
  19. Bertogna M (2009) Evaluation of existing schedulability tests for global EDF. In: Proceedings of the first international workshop on real-time systems on multicore platforms: theory and practice
  20. Bertogna M, Cirinei M (2007) Response time analysis for global scheduled symmetric multiprocessor platforms. In: Proceedings real-time systems symposium (RTSS), pp 149–158
  21. Bertogna M, Cirinei M, Lipari G (2005) New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In: Proc 9th international conf on principles of distributed systems, pp 306–321
  22. Bertogna M, Cirinei M, Lipari G (2009) Schedulability analysis of global scheduling algorithms on multiprocessor platforms. IEEE Trans Parallel Distrib Syst 20(4):553–566
  23. Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1–2):129–154
  24. Brandenburg BB, Calandrino JM, Anderson JH (2008) On the scalability of real-time scheduling algorithms on multicore platforms: a case study. In: Proceedings real-time systems symposium (RTSS), pp 157–169
  25. Burns A, Davis RI, Wang P, Zhang F (2011) Partitioned EDF scheduling for multiprocessors using a C=D scheme. Real-Time Syst 48(1):3–33
  26. Calandrino J, Leontyev H, Block A, Devi U, Anderson J (2006) LITMUSRT: a testbed for empirically comparing real-time multiprocessor schedulers. In: Proceedings real-time systems symposium (RTSS), pp 111–123
  27. Chao Y-H, Lin S-S, Lin K-J (2008) Schedulability issues for EDZL scheduling on real-time multiprocessor systems. Inf Process Lett 107(5):158–164
  28. Cho S, Lee S-K, Han A, Lin K-J (2002) Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans Commun E85-B(12):2859–2867
  29. Cho H, Ravindran B, Jensen ED (2006) An optimal real-time scheduling algorithm for multiprocessors. In: Proceedings real-time systems symposium (RTSS), pp 101–110
  30. Cirinei M, Baker TP (2007) EDZL scheduling analysis. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 9–18
  31. Davis RI, Burns A (2009) Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: Proceedings real-time systems symposium (RTSS), pp 398–409
  32. Davis RI, Burns A (2010a) Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-Time Syst 47(1):1–40. doi:
  33. Davis RI, Burns A (2010b) FPZL schedulability analysis. Technical Report YCS-2010-452, Dept of Computer Science, University of York, April 2010
  34. Davis RI, Burns A (2011a) FPZL schedulability analysis. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 245–256
  35. Davis RI, Burns A (2011b) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 43(4):35 doi:
  36. Faggioli D, Trimarchi M, Checconi F (2009) An implementation of the earliest deadline first algorithm in Linux. In: Proceedings ACM symposium on applied computing, pp 1984–1989
  37. Fisher N, Baruah SK (2006) Global static-priority scheduling of sporadic task systems on multiprocessor platforms. In: Proceedings IASTED international conference on parallel and distributed computing and systems
  38. Funk S, Nadadur V (2009) LRE-TL: an optimal multiprocessor algorithm for sporadic task sets. In: Proceedings real-time and network systems (RTNS), pp 159–168
  39. Guan N, Stigge M, Yi W, Yu G (2009) New response time bounds for fixed priority multiprocessor scheduling. In: Proceedings real-time systems symposium (RTSS), pp 387–397
  40. Guan N, Stigge M, Yi W, Yu G (2010) Fixed-priority multiprocessor scheduling with Liu & Layland’s utilization bound. In: Proceedings real-time and embedded technology and applications symposium (RTAS)
  41. Kato S, Yamasaki N (2008) Global EDF-based scheduling with efficient priority promotion. In: Proceedings of real-time computing systems and applications (RTCSA), pp 197–206
  42. Kato S, Yamasaki N (2009a) Semi-partitioned fixed-priority scheduling on multiprocessors. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 23–32
  43. Kato S, Yamasaki N (2009b) Real-time scheduling module for Linux kernel. IPSJ Trans Adv Comput Syst 2(1 (ACS25)):75–86 (in Japanese)
  44. Kato S, Takeda A, Yamasaki N (2010) Global rate-monotonic scheduling with priority promotion. Technical Report CMU-ECE-TR10-05, May 2010
  45. Lee SK (1994) On-line multiprocessor scheduling algorithms for real-time tasks. In: Proc IEEE region 10’s ninth annual international conference, pp 607–611
  46. Leung JY-T (1989) A new algorithm for scheduling periodic real-time tasks. Algorithmica 4:209–219
  47. Oikawa S, Rajkumar R (1999) Portable RT: a portable resource kernel for guaranteed and enforced timing behaviour. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 111–120
  48. Park M, Han S, Kim H, Cho S, Cho Y (2005) Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor. IEICE Trans Inf Syst E88-D(3):658–661
  49. Piao X, Han S, Kim H, Park M, Cho Y, Cho S (2006) Predictability of earliest deadline zero laxity algorithm for multiprocessor real time systems. In: Proc of the 9th IEEE international symposium on object and component-oriented real-time distributed computing, Gjeongju, Korea
  50. Srinivasan B, Pather S, Hill R, Ansari F, Niehaus D (1998) A firm real-time system implementation using commercial off-the shelf hardware and free software. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 112–119
  51. Takeda A, Kato S, Yamasaki N (2009) Real-time scheduling based on rate monotonic for multiprocessors. IPSJ Trans Adv Comput Syst 2(1 (ACS25)):64–74 (in Japanese)
• 作者单位：1. Real-Time Systems Research Group, Department of Computer Science, University of York, YO10 5DD York, UK2. Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA
• ISSN：1573-1383

文摘

This paper presents the Fixed Priority until Static Laxity (FPSL), Fixed Priority until Critical Laxity (FPCL) and Fixed Priority until Zero Laxity (FPZL) scheduling algorithms for multiprocessor real-time systems. FPZL is similar to global fixed priority pre-emptive scheduling; however, whenever a task reaches a state of zero laxity it is given the highest priority. FPSL and FPCL are variants of FPZL that introduce no additional scheduling points beyond those present with fixed priority scheduling. FPSL, FPCL and FPZL are minimally dynamic algorithms, in that the priority of a job can change at most once during its execution, bounding the number of pre-emptions.