Portioned EDF-based scheduling on multiprocessors

ABSTRACT

This paper presents an EDF-based algorithm, called Earliest Deadline Deferrable Portion (EDDP), for efficient scheduling of recurrent real-time tasks on multiprocessor systems. The design of EDDP is based on the portioned scheduling technique which classifies each task into a fixed task or a migratable task. A fixed task is scheduled on the dedicated processor without migrations. A migratable task is meanwhile permitted to migrate between the particular two processors. In order to curb the cost of task migrations, EDDP makes at most M -- 1 migratable tasks on M processors. The scheduling analysis derives the condition for a given task set to be schedulable. It is also proven that no tasks ever miss deadlines, if the system utilization does not exceed 65%. Beyond the theoretical analysis, the effectiveness of EDDP is evaluated through simulation studies. Simulation results show that EDDP achieves high system utilization with a small number of preemptions, compared with the traditional EDF-based algorithms.

REFERENCES

• 1: J. Anderson and A. Srinivasan. Early-Release Fair Scheduling. In Proc. of the Euromicro Conference on Real-Time Systems, pages 35--43, 2000.
• 2: Bjorn Andersson , Eduardo Tovar, Multiprocessor Scheduling with Few Preemptions, Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.322-334, August 16-18, 2006 [doi>10.1109/RTCSA.2006.45]
• 3: Theodore P. Baker, An Analysis of EDF Schedulability on a Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.16 n.8, p.760-768, August 2005 [doi>10.1109/TPDS.2005.88]
• 4: S. Baruah, N. Cohen, C. Plaxton, and D. Varvel. Proportionate Progress: A Notion of Fairness in Resource Allocation. Algorithmica, 15:600--625, 1996.
• 5: Sanjoy K. Baruah , Johannes Gehrke , C. Greg Plaxton, Fast scheduling of periodic tasks on multiple resources, Proceedings of the 9th International Symposium on Parallel Processing, p.280-288, April 25-28, 1995
• 6: John M. Calandrino , Hennadiy Leontyev , Aaron Block , UmaMaheswari C. Devi , James H. Anderson, LITMUS^RT: A Testbed for Empirically Comparing Real-Time Multiprocessor Schedulers, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.111-126, December 05-08, 2006 [doi>10.1109/RTSS.2006.27]
• 7: Hyeonjoong Cho , Binoy Ravindran , E. Douglas Jensen, An Optimal Real-Time Scheduling Algorithm for Multiprocessors, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.101-110, December 05-08, 2006 [doi>10.1109/RTSS.2006.10]
• 8: S. Cho, S. Lee, A. Han, and K. Lin. Efficient Real-Time Scheduling Algorithms for Multiprocessor Systems. IEICE Transactions on Communications, E85-B(12):2859--2867, 2002.
• 9: Michele Cirinei , Theodore P. Baker, EDZL Scheduling Analysis, Proceedings of the 19th Euromicro Conference on Real-Time Systems, p.9-18, July 04-06, 2007 [doi>10.1109/ECRTS.2007.14]
• 10: S. K. Dhall and C. L. Liu. On a Real-Time Scheduling Problem. Operations Research, 26:127--140, 1978.
• 11: Kenji Funaoka , Shinpei Kato , Nobuyuki Yamasaki, Work-Conserving Optimal Real-Time Scheduling on Multiprocessors, Proceedings of the 2008 Euromicro Conference on Real-Time Systems, p.13-22, July 02-04, 2008 [doi>10.1109/ECRTS.2008.15]
• 12: Shinpei Kato , Nobuyuki Yamasaki, Real-Time Scheduling with Task Splitting on Multiprocessors, Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.441-450, August 21-24, 2007 [doi>10.1109/RTCSA.2007.61]
• 13: S. Kato and N. Yamasaki. Portioned Static-Priority Scheduling on Multiprocessors. In Proc. of the IEEE International Parallel and Distributed Processing Symposium, 2008.
• 14: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 15: J. M. López , J. L. Díaz , D. F. García, Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems, Real-Time Systems, v.28 n.1, p.39-68, October 2004 [doi>10.1023/B:TIME.0000033378.56741.14]
• 16: Xuefeng Piao , Sangchul Han , Heeheon Kim , Minkyu Park , Yookun Cho , Seongje Cho, Predictability of Earliest Deadline Zero Laxity Algorithm for Multiprocessor Real-Time Systems, Proceedings of the Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, p.359-364, April 24-26, 2006 [doi>10.1109/ISORC.2006.64]
• 17: Anand Srinivasan , Sanjoy Baruah, Deadline-based scheduling of periodic task systems on multiprocessors, Information Processing Letters, v.84 n.2, p.93-98, 31 October 2002 [doi>10.1016/S0020-0190(02)00231-4]
• 18: Anand Srinivasan , Philip Holman , James H. Anderson , Sanjoy Baruah, The Case for Fair Multiprocessor Scheduling, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.114.1, April 22-26, 2003
• 19: Hsin-Wen Wei , Yi-Hsiung Chao , Shun-Shii Lin , Kwei-Jay Lin , Wei-Kuan Shih, Current Results on EDZL Scheduling for Multiprocessor Real-Time Systems, Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.120-130, August 21-24, 2007 [doi>10.1109/RTCSA.2007.34]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Theory

Keywords:
multiprocessor systems, real-time systems, scheduling algorithm