More Web Proxy on the site http://driver.im/

research-article

Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications

Authors:

Yuhuan Du, Gustavo De VecianaAuthors Info & Claims

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Volume 2, Issue 3

Article No.: 13, Pages 1 - 30

https://doi.org/10.1145/3063713

Published: 29 June 2017 Publication History

Abstract

Cloud-based computing infrastructure provides an efficient means to support real-time processing workloads, for example, virtualized base station processing, and collaborative video conferencing. This article addresses resource allocation for a computing system with multiple resources supporting heterogeneous soft real-time applications subject to Quality of Service (QoS) constraints on failures to meet processing deadlines. We develop a general outer bound on the feasible QoS region for non-clairvoyant resource allocation policies and an inner bound for a natural class of policies based on dynamically prioritizing applications’ tasks by favoring those with the largest (QoS) deficits. This provides an avenue to study the efficiency of two natural resource allocation policies: (1) priority-based greedy task scheduling for applications with variable workloads and (2) priority-based task selection and optimal scheduling for applications with deterministic workloads. The near-optimality of these simple policies emerges when task processing deadlines are relatively large and/or when the number of compute resources is large. Analysis and simulations show substantial resource savings for such policies over reservation-based designs.

References

[1]

Fardin Ahmadizar, Mehdi Ghazanfari, and Seyyed Mohammad Taghi Fatemi Ghomi. 2010. Group shops scheduling with makespan criterion subject to random release dates and processing times. Comput. Operat. Res. 37, 1 (2010), 152--162.

Digital Library

[2]

Ali Allahverdi and Yuri Sotskov. 2003. Two-machine flowshop minimum-length scheduling problem with random and bounded processing times. Int. Trans. Operat. Res. 10 (2003), 65--76. Issue 1.

[3]

Yair Amir, Baruch Awerbuch, Amnon Barak, R. Sean Borgstrom, and Arie Keren. 2000. An opportunity cost approach for job assignment in a scalable computing cluster. IEEE Trans. Parallel Distrib. Syst. 11 (July 2000), 760--768. Issue 7.

Digital Library

[4]

Alia Atlas and Azer Bestavros. 1998. Statistical rate monotonic scheduling. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’98). 123--132.

Digital Library

[5]

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

Digital Library

[6]

Carlos J. Bernardos et al. 2014. An architecture for software defined wireless networking. IEEE Wireless Commun. 21, 3 (2014), 52--61.

[7]

Guillem Bernat and Alan Burns. 1997. Combining (ⁿ_m)-hard deadlines and dual priority scheduling. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’97). 46--57.

Digital Library

[8]

J. Blazewicz, M. Drabowski, and J. Weglarz. 1986. Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput. C-35, 5 (1986), 389--393.

Digital Library

[9]

J. Bruno, E. G. Coffman Jr., and R. Sethi. 1974. Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17, 7 (1974), 382--387.

Digital Library

[10]

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

[11]

China Mobile. 2011. C-RAN The Road Towards Green RAN. In White Paper (Oct. 2011).

[12]

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen. 2006. An optimal real-time scheduling algorithm for multiprocessors. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’06). 101--110.

Digital Library

[13]

J. H. Conway and N. J. A. Sloane. 2013. Sphere Packings, Lattices and Groups. Springer.

[14]

Robert I. Davis and Alan Burns. 2011a. A survey of hard real-time scheduling for multiprocessor systems. Comput. Surv. 43, 4 (October 2011).

Digital Library

[15]

Robert I. Davis and Alan Burns. 2011b. A survey of hard real-time scheduling for multiprocessor systems. Comput. Surv. 43, 4 (2011).

Digital Library

[16]

Christina Delimitrou and Christos Kozyrakis. 2014. Quasar: Resource-efficient and qos-aware cluster management. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems. 127--144.

Digital Library

[17]

Antonis Dimakis and Jean Walrand. 2006. Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits. Adv. Appl. Probab. 38, 2 (June 2006), 505--521.

[18]

Yuhuan Du and Gustavo de Veciana. 2014. Wireless networks without edge: Dynamic radio resource clustering and user scheduling. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM’14). 1321--1329.

[19]

Yuhuan Du and Gustavo de Veciana. 2016. Efficiency and optimality of largest deficit first prioritization: Resource allocation for real-time applications. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM’16).

Digital Library

[20]

Yuhuan Du and Gustavo de Veciana. 2017. Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications (extended version). http://arxiv.org/abs/1601.06333.

[21]

Shelby Funk, Joël Goossens, and Sanjoy Baruah. 2001. On-line scheduling on uniform multiprocessors. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’01). 183--192.

Digital Library

[22]

Shelby Funk and Archana Meka. 2009. U-LLREF: An optimal scheduling algorithm for uniform multiprocessors. In Workshop on Models and Algorithms for Planning and Scheduling Problems.

[23]

Alan Gatherer. 2015. Personal communication. (February 2015).

[24]

Moncef Hamdaoui and Parameswaran Ramanathan. 1995. A dynamic priority assignment technique for streams with (m, k)-firm deadlines. IEEE Trans. Comput. 44, 12 (Dec. 1995), 1443--1451.

Digital Library

[25]

I-Hong Hou and P. R. Kumar. 2012a. Queueing systems with hard delay constraints: A framework for real-time communication over unreliable wireless channels. Que. Syst. 71, 1--2 (March 2012), 151--177.

Digital Library

[26]

I-Hong Hou and P. R. Kumar. 2012b. Queueing systems with hard delay constraints: A framework for real-time communication over unreliable wireless channels. Que. Syst. 71, 1--2 (2012).

Digital Library

[27]

I-Hong Hou and P. R. Kumar. 2013. Packets with Deadlines: A Framework for Real-Time Wireless Networks. Morgan 8 Claypool Publishers.

Digital Library

[28]

Juan Jose Jaramillo and R. Srikant. 2011. Optimal scheduling for fair resource allocation in ad hoc networks with elastic and inelastic traffic. IEEE Trans. Netw. 19, 4 (Aug. 2011), 1125--1136.

Digital Library

[29]

Changhee Joo, Xiaojun Lin, and Ness B. Shroff. 2007a. Performance limits of greedy maximal matching in multi-hop wireless networks. In IEEE Conference on Decision and Control. 1128--1133.

[30]

Changhee Joo, Xiaojun Lin, and Ness B. Shroff. 2007b. Performance limits of greedy maximal matching in multi-hop wireless networks. In IEEE Conference on Decision and Control.

[31]

Xiaohan Kang, Weina Wang, Juan Jose Jaramillo, and Lei Ying. 2013. On the performance of largest-deficit-first for scheduling real-time traffic in wireless networks. In Proceedings of MobiHoc. 99--108.

Digital Library

[32]

Eugene L. Lawler, Jan karel Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys. 1993. Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Research and Management Science. 445--522.

[33]

Joseph Y.-T. Leung. 1989. A new algorithm for scheduling periodic, real-time tasks. Algorithmica 4, 1 (June 1989), 209--219.

[34]

Cong Liu and James H. Anderson. 2009. Task scheduling with self-suspensions in soft real-time multiprocessor systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’09). 425--436.

Digital Library

[35]

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

Digital Library

[36]

Jane W. S. Liu, Kwei-Jay Lin, and Swaminathan Natarajan. 1987. Scheduling real-time, periodic jobs using imprecise results. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’87). 252--260.

[37]

Jane W. S. Liu. 2000. Real-Time Systems. Prentice Hall.

[38]

Jason Mars, Lingjia Tang, Robert Hundt, Kevin Skadron, and Mary Lou Soffa. 2011. Bubble-up: Increasing utilization in modern warehouse scale computers via sensible co-locations. In Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture.

Digital Library

[39]

A. Müller and D. Stoyan. 2002. Comparison Methods for Stochastic Methods and Risks. Wiley.

[40]

Shailesh Patil and Gustavo de Veciana. 2007. Managing resources and quality of service in heterogeneous wireless systems exploiting opportunism. IEEE/ACM Trans. Netw. 15, 5 (October 2007), 1046--1058.

Digital Library

[41]

Michael L. Pinedo. 2012. Scheduling: Theory, Algorithms, and Systems. Springer.

[42]

Parameswaran Ramanathan. 1999. Overload management in real-time control applications using (m, k)-firm guarantee. IEEE Trans. Parallel Distrib. Syst. 10, 6 (June 1999), 549--559.

Digital Library

[43]

Sanjay Shakkottai and Alexander L. Stolyar. 2001. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR. In Proceedings of the International Teletraffic Congress. 793--804.

[44]

Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. 2015. Large-scale cluster management at google with borg. In Proceedings of the European Professional Society on Computer Systems (EuroSys’15).

Digital Library

Cited By

Sun HWang SZhou FYin LLiu M(2023)Dynamic Deployment and Scheduling Strategy for Dual-Service Pooling-Based Hierarchical Cloud Service System in Intelligent BuildingsIEEE Transactions on Cloud Computing10.1109/TCC.2021.307879511:1(139-155)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3078795
Vinothina V. Jasmine Beulah G. Rajagopal S(2021)Review on Mapping of Tasks to Resources in Cloud ComputingInternational Journal of Cloud Applications and Computing10.4018/IJCAC.202201010612:1(1-17)Online publication date: 5-Nov-2021
https://doi.org/10.4018/IJCAC.2022010106
Cong PXu GWei TLi K(2020)A Survey of Profit Optimization Techniques for Cloud ProvidersACM Computing Surveys10.1145/337691753:2(1-35)Online publication date: 20-Mar-2020
https://dl.acm.org/doi/10.1145/3376917
Show More Cited By

Index Terms

Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications

Recommendations

Efficient scheduling of soft real-time applications on multiprocessors
Real-Time Systems (Euromicro RTS-03)

In soft real-time applications, tasks are allowed to miss their deadlines. Thus, less-costly scheduling algorithms can be used at the price of occasional violations of timing constraints. This may be acceptable if reasonable tardiness bounds (i.e., ...
Scheduling for cloud-based computing systems to support soft real-time applications
IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications
Cloud-based computing infrastructure provides an efficient means to support real-time processing workloads, e.g., virtualized base station processing, and collaborative video conferencing. This paper addresses resource allocation for a computing system ...
A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Performance Evaluation of Computing Systems

ACM Transactions on Modeling and Performance Evaluation of Computing Systems Volume 2, Issue 3

September 2017

135 pages

ISSN:2376-3639

EISSN:2376-3647

DOI:10.1145/3119902

Editors:
Sem Borst
Nokia Bell Labs / Eindhoven University of Technology, Netherlands
,
Carey Williamson
University of Calgary, Canada

Issue’s Table of Contents

Copyright © 2017 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

Publication History

Published: 29 June 2017

Accepted: 01 March 2017

Revised: 01 October 2016

Received: 01 March 2016

Published in TOMPECS Volume 2, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Huawei Technologies Co. Ltd

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
263
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun HWang SZhou FYin LLiu M(2023)Dynamic Deployment and Scheduling Strategy for Dual-Service Pooling-Based Hierarchical Cloud Service System in Intelligent BuildingsIEEE Transactions on Cloud Computing10.1109/TCC.2021.307879511:1(139-155)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3078795
Vinothina V. Jasmine Beulah G. Rajagopal S(2021)Review on Mapping of Tasks to Resources in Cloud ComputingInternational Journal of Cloud Applications and Computing10.4018/IJCAC.202201010612:1(1-17)Online publication date: 5-Nov-2021
https://doi.org/10.4018/IJCAC.2022010106
Cong PXu GWei TLi K(2020)A Survey of Profit Optimization Techniques for Cloud ProvidersACM Computing Surveys10.1145/337691753:2(1-35)Online publication date: 20-Mar-2020
https://dl.acm.org/doi/10.1145/3376917
Du YVeciana G(2018)Efficiency and Optimality of Largest Deficit First PrioritizationACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/32004793:3(1-29)Online publication date: 13-Jun-2018
https://dl.acm.org/doi/10.1145/3200479
Sahoo SSahu SRath TSahoo BTuruk A(2018)TCA: A Multi Constraint Real-Time Task Scheduling Algorithm for Heterogeneous Cloud Environment2018 International Conference on Information Technology (ICIT)10.1109/ICIT.2018.00036(132-136)Online publication date: Dec-2018
https://doi.org/10.1109/ICIT.2018.00036

View Options

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