research-article

ERfair Scheduler with Processor Suspension for Real-Time Multiprocessor Embedded Systems

Authors:

Piyoosh Purushothaman Nair,

P. P. Chakrabarti,

Sujoy GhoseAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 22, Issue 1

Article No.: 19, Pages 1 - 25

https://doi.org/10.1145/2948979

Published: 13 December 2016 Publication History

Abstract

Proportional fair schedulers with their ability to provide optimal schedulability along with hard timeliness and quality-of-service guarantees on multiprocessors form an attractive alternative in real-time embedded systems that concurrently run a mix of independent applications with varying timeliness constraints. This article presents ERfair Scheduler with Suspension on Multiprocessors (ESSM), an efficient, optimal proportional fair scheduler that attempts to reduce system wide energy consumption by locally maximizing the processor suspension intervals while not sacrificing the ERfairness timing constraints of the system. The proposed technique takes advantage of higher execution rates of tasks in underloaded ERfair systems and uses a procrastination scheme to search for time points within the schedule where suspension intervals are locally maximal. Evaluation results reveal that ESSM achieves good sleep efficiency and provides up to 50% higher effective total sleep durations as compared to the Basic-ERfair scheduler on systems consisting of 2 to 20 processors.

References

[1]

J. Anderson and A. Srinivasan. 2000. Early-release fair scheduling. In Proceedings of the 12th Euromicro Conference on Real-Time Systems. 35--43.

Digital Library

[2]

M. A. Awan and S. M. Petters. 2013. Energy-aware partitioning of tasks onto a heterogeneous multi-core platform. In Proceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS). 205--214.

Digital Library

[3]

Muhammad Ali Awan and Stefan M. Petters. 2011. Enhanced race-to-halt: A leakage-aware energy management approach for dynamic priority systems. In Proceedings of the 2011 23rd Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 92--101.

Digital Library

[4]

P. Baptiste, M. Chrobak, and C. Durr. 2007. Polynomial time algorithms for minimum energy scheduling. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA). 136--150.

Digital Library

[5]

S. Baruah, N. Cohen, C. G. Plaxton, and D. Varvel. 1996. Proportionate progress: A notion of fairness in resource allocation. Algorithmica 15, 6 (1996), 600--625.

Digital Library

[6]

Andrea Bastoni, Björn Brandenburg, and James Anderson. 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Proceedings of OSPERT. 33--44.

[7]

M. Bhatti, Muhammad Farooq, Cécile Belleudy, and Michel Auguin. 2009. Controlling energy profile of rt multiprocessor systems by anticipating workload at runtime. In SYMPosium en Architectures Nouvelles de Machines.

[8]

John Carpenter, Shelby Funk, Philip Holman, Anand Srinivasan, James Anderson, and Sanjoy Baruah. 2004. A categorization of real-time multiprocessor scheduling problems and algorithms. Handbook on Scheduling Algorithms, Methods, and Models (2004), 30--1.

[9]

Gang Chen, Kai Huang, and Alois Knoll. 2014. Adaptive dynamic power management for hard real-time pipelined multiprocessor systems. In Proceedings of the 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). IEEE, 1--10.

[10]

J. Chen and T. Kuo. 2006. Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES). 153--162.

Digital Library

[11]

Jian-Jia Chen, Heng-Ruey Hsu, and Tei-Wei Kuo. 2006. Leakage-aware energy-efficient scheduling of real-time tasks in multiprocessor systems. In Proceedings of the 12th Real-Time and Embedded Technology and Applications Symposium IEEE. IEEE, 408--417.

Digital Library

[12]

F. Harada, T. Ushio, and Y. Nakamoto. 2008. Adaptive fair resource allocation for energy and QoS trade-off management. IEICE Trans. Fundam. Electron. E91-A, 11 (2008), 3245--3252.

Digital Library

[13]

Hongtao Huang, Feng Xia, Jijie Wang, Siyu Lei, and Guowei Wu. 2010. Leakage-aware reallocation for periodic real-time tasks on multicore processors. In FCST. 85--91.

Digital Library

[14]

K. Jeffay and S. Goddard. 2001. Rate-based resource allocation models for embedded systems. Lect. Not. Comput. Sci. 2211 (2001), 204--222.

Digital Library

[15]

R. Jejurikar and R. Gupta. 2004. Procrastination scheduling in fixed priority real-time systems. ACM SIGPLAN Not. 39, 7 (2004), 57--66.

Digital Library

[16]

R. Jejurikar and R. Gupta. 2005. Dynamic slack reclamation with procrastination scheduling in real-time embedded systems. In Proceedings of the 42nd Annual Conference on Design Automation (DAC’05). ACM, New York, NY, 111--116.

Digital Library

[17]

M. T. Jones. 2009. Inside the Linux 2.6 Completely Fair Scheduler. Retrieved from http://www.ibm.com/developerworks/library/l-completely-fair-scheduler/l-completely-fair-scheduler-pdf.pdf. (2009).

[18]

N. S. Kim, T. Austin, D. Blaauw, T. Mudge, K. Flautner, J. S. Hu, M. J. Irwin, M. Kandemir, and V. Narayanan. 2003. Leakage current: Moore’s law meets static power. Computer 36 (2003), 68--75.

Digital Library

[19]

H. Kweon, Y. Do, J. Lee, and B. Ahn. 2007. An efficient power-aware scheduling algorithm in real time system. In Proceedings of the IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. 350--353.

[20]

I. Lee, J. Leung, and S. H. Son (Eds.). 2007. Handbook of Real-Time and Embedded Systems. Chapman 8 Hall/CRC Press.

Digital Library

[21]

Y. Lee, K. P. Reddy, and C. M. Krishna. 2003. Scheduling techniques for reducing leakage power in hard real-time systems. In Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS). 105--112.

[22]

Vincent Legout, Mathieu Jan, and Laurent Pautet. 2013a. An off-line multiprocessor real-time scheduling algorithm to reduce static energy consumption. In Proceedings of the 1st Workshop on Highly-Reliable Power-Efficient Embedded Designs (HARSH). 7--12.

[23]

Vincent Legout, Mathieu Jan, and Laurent Pautet. 2013b. A scheduling algorithm to reduce the static energy consumption of multiprocessor real-time systems. In Proceedings of the 21st International Conference on Real-Time Networks and Systems. ACM, 99--108.

Digital Library

[24]

Vincent Legout, Mathieu Jan, and Laurent Pautet. 2015. Scheduling algorithms to reduce the static energy consumption of real-time systems. Real-Time Syst. 51, 2 (March 2015), 153--191.

Digital Library

[25]

Chung Laung Liu and James W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1 (1973), 46--61.

Digital Library

[26]

B. Venkateswarlu Naik, Shirshendu Das, and Hemangee K. Kapoor. 2014. RT-DVS for power optimization in multiprocessor real-time systems. In Proceedings of the 2014 International Conference on Information Technology (ICIT). IEEE, 24--29.

Digital Library

[27]

A. Sarkar, S. Swaroop, S. Ghose, and P. P. Chakrabarti. 2009. ERfair scheduler with processor shutdown. In Proceedings of the 16th Annual International Conference on High Performance Computing. 365--368.

[28]

A. Srinivasan, P. Holman, and J. Anderson. 2003. The case for fair multiprocessor scheduling. In Proceedings of the 11th International Workshop on Parallel and Distributed Real-time Systems.

Digital Library

[29]

Abdel-Wahab Hussein Stoica, Ion, Kevin Jeffay, Sanjoy Baruah, Johannes Gehrke, and C. Greg Plaxton. 1996. A proportional share resource allocation algorithm for real-time, time-shared systems. In Proceedings of the 17th IEEE Real-Time Systems Symposium. Retrieved from citeseer.ist.psu.edu/stoica96proportional.html.

Digital Library

[30]

D. Suleiman, M. Ibrahim, and I. Hamarash. 2005. Dynamic voltage frequency scaling (DVFS) for microprocessors power and energy reduction. In Proceedings of the 4th International Conference on Electrical and Electronics Engineering.

[31]

www.kernel.org. 2015. CFS Scheduler - The Linux Kernel Archives. Retrieved from https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt.

[32]

Dakai Zhu, Xuan Qi, Daniel Mossé, and Rami Melhem. 2011. An optimal boundary fair scheduling algorithm for multiprocessor real-time systems. J. Parallel Distrib. Comput. 71, 10 (2011), 1411--1425.

Cited By

Zheng XDong F(2022)Application of Virtual Instrument Technology in the Teaching of Embedded System CourseInternational Transactions on Electrical Energy Systems10.1155/2022/67214502022(1-11)Online publication date: 16-Sep-2022
https://doi.org/10.1155/2022/6721450
Zhu H(2022)Innovation of Visual Communication Design Based on Wireless Virtualization Network ArchitectureMobile Information Systems10.1155/2022/22053622022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2205362
Ren XCui Y(2021)Embedded System Intelligent Platform Design Based on Digital Multimedia Artistic DesignWireless Communications & Mobile Computing10.1155/2021/39591992021Online publication date: 21-Dec-2021
https://dl.acm.org/doi/10.1155/2021/3959199
Show More Cited By

Index Terms

ERfair Scheduler with Processor Suspension for Real-Time Multiprocessor Embedded Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Power management
        Scheduling
    2. Software system structures
      1. Real-time systems software

Recommendations

A Low-Overhead Partition-Oriented ERfair Scheduler for Hard Real-Time Embedded Systems

This letter presents partition-oriented ERfair scheduler (POES), a low-overhead proportional fair scheduler for hard real-time multiprocessor embedded systems. POES achieves lower overheads using an online partitioning/merging mechanism that retains the ...
Sticky-ERfair: a task-processor affinity aware proportional fair scheduler

A drawback of current proportional fair schedulers is that they ignore task-to-processor mutual affinities, thereby causing frequent inter-processor task migrations and cache misses. This paper presents the Sticky-ERfair Scheduler, an Early-Release Fair ...
Partition oriented frame based fair scheduler

Proportionate fair schedulers provide an effective methodology for scheduling recurrent real-time tasks on multiprocessors. However, a drawback in these schedulers is that they ignore a task's affinity towards the processor where it was executed last, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 22, Issue 1

January 2017

463 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/2948199

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 13 December 2016

Accepted: 01 May 2016

Revised: 01 May 2016

Received: 01 July 2015

Published in TODAES Volume 22, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
180
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zheng XDong F(2022)Application of Virtual Instrument Technology in the Teaching of Embedded System CourseInternational Transactions on Electrical Energy Systems10.1155/2022/67214502022(1-11)Online publication date: 16-Sep-2022
https://doi.org/10.1155/2022/6721450
Zhu H(2022)Innovation of Visual Communication Design Based on Wireless Virtualization Network ArchitectureMobile Information Systems10.1155/2022/22053622022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2205362
Ren XCui Y(2021)Embedded System Intelligent Platform Design Based on Digital Multimedia Artistic DesignWireless Communications & Mobile Computing10.1155/2021/39591992021Online publication date: 21-Dec-2021
https://dl.acm.org/doi/10.1155/2021/3959199
Sun JCho HEaswaran APark JChoi B(2019)Flow Network-Based Real-Time Scheduling for Reducing Static Energy Consumption on MultiprocessorsIEEE Access10.1109/ACCESS.2018.28865627(1330-1344)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2018.2886562
Nair PDevaraj RSarkar A(2018)FEST: Fault-Tolerant Energy-Aware Scheduling on Two-Core Heterogeneous Platform2018 8th International Symposium on Embedded Computing and System Design (ISED)10.1109/ISED.2018.8704123(63-68)Online publication date: Dec-2018
https://doi.org/10.1109/ISED.2018.8704123
Ramesh PRamachandraiah U(2018)Energy Aware Proportionate Slack Management Scheduling for Multiprocessor SystemsProcedia Computer Science10.1016/j.procs.2018.07.109133(855-863)Online publication date: 2018
https://doi.org/10.1016/j.procs.2018.07.109
Moulik SDevaraj RSarkar AShaw A(2017)A Deadline-Partition Oriented Heterogeneous Multi-Core Scheduler for Periodic Tasks2017 18th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)10.1109/PDCAT.2017.00041(204-210)Online publication date: Dec-2017
https://doi.org/10.1109/PDCAT.2017.00041

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents