article

Free access

Load-balancing heuristics and process behavior

Authors:

Teunis J. OttAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 14, Issue 1

Pages 54 - 69

https://doi.org/10.1145/317531.317539

Published: 01 May 1986 Publication History

Abstract

Dynamic load balancing in a system of loosely-coupled homogeneous processors may employ both judicious initial placement of processes and migration of existing processes to processors with fewer resident processes. In order to predict the possible benefits of these dynamic assignment techniques, we analyzed the behavior (CPU, disk, and memory use) of 9.5 million Unix* processes during normal use. The observed process behavior was then used to drive simulation studies of particular dynamic assignment heuristics.

Let F(·) be the probability distribution of the amount of CPU time used by an arbitrary process. In the environment studied we found:

(1-F(x)) ≉ rx^-c, 1.05<c<1.25.

F(·) is far enough from exponential to make exponential models of little use.

With a foreground-background process scheduling policy in each processor, simple heuristics for initial placement and processor migration can significantly improve the response ratios of processes that demand exceptional amounts of CPU, without harming the response ratios of ordinary processes.

References

[1]

Barak, Amnon and Litman, Awl; "A Distributed Loadbalancing Policy for a Multieomputer," Software -- Practice and Ezperienee, 15, no. 9 (September 1985), pp. 901-913

Digital Library

[2]

Barak, Amnon and Litman, Ami, ~#VIOS: a Multieomputer Distributed Operating System," So#toare -- Practice and Ezperience, 16, no. 8 (August, 1985), pp. 725-737 Aug, 1985 pp 725-737

Digital Library

[3]

Bryant, Ray and Finkel, Raphael A; "A Stable Distributed Scheduling A|gorithm," Proceedings of the Second {nternational Conference in Distributed Computing Systems, IF.EE Computer Society, Los Alamitos, California (April 1981), pp. 314-323

[4]

Cabrera, Luis Felipe; Hunter, Edward; Karels, Mike; Mosher, David; A User-Process Oriented Performance Study of Ethernet Networking Under Berkeley UNIX 4.#BSD, Report No. UCB/CSD 84/217 (December 1984), Computer Science Division (EECS), University of California, Berkeley.

Digital Library

[5]

Chambers, John M.; Cleveland, William S.; Kleiner, Beat; Tukey, Paul A.; Graphical Methods /or Data Analysis, Wadsworth International Group, Belmont, California, 1983

[6]

Cheriton, David R.; "The V Kernel: A Software Base for Distributed Systems," IEEE Software, 1, no. 2 (1984), pp. 19-43

Digital Library

[7]

Chou, Timothy C. K. and Abraham, Jacob A.; '#Load Balancing in Distributed Systems," IEEE Transactions on Software Engineering, SE-8, no. 4 (July 1982), pp. 401-412

Digital Library

[8]

Eager, Derek L.; Lazowska, Edward D.; Zahorjan, John; Adaptive Load Sharing in Homogeneous Distributed S#stems, Technical Report 84-10-01 (October 1984), Department of Computer Science, University of Washington

[9]

Eager, Derek L.; Lazowska, Edward D.; Zahorjan, John; '~A Comparison of Receiver-Initiated and Sender- Initiated Adaptive Load Sharing," Performance Evaluation Review, 18, no. 2 (August, 1985), pp. 1-3

Digital Library

[10]

Hwang, Kai; Croft, William J.; Goble, George H.; Wah, Benjamin W.; Briggs, Faye A; Simmons, William R.; Coates, Clarence L; "A Unix-based Local Computer Network with Load Balancing," IEEE Computer Magazine, 15, no. 4 (April 1982), pp. 5#-66

Digital Library

[11]

Kameda, Hisao; '#Effects of Job Loading Policies for Multiprogramming Systems in Processing a Job Stream," A CM Transactions on Computer Systems, 4, no. 1 (February, 1986), pp. 71-106

Digital Library

[12]

Kleinrock, Leonard; Queueinff Systems -- Volume II: Computer Applications, John Wiley and Sons, New York, 1976

[13]

Krueger, Philip and Finkel, Raphael A.; "An Adaptive Load Balancing Algorithm for a Multieomputer," Technical Report (1983), Department of Computer Sciences, University of Wisconsin--Madison

[14]

Leland, Will E. and Ott, Teunis J.; "Unix Process Behavior and Load Balancing among Loosely Coupled Computers," International Seminar on Teletratiic Analysis and Computer Performance Evaluation (June, 1986)

Digital Library

[15]

Livny, M. and Melman, M.; '#oad Balancing in Homogeneous Broadcast Distributed Systems," Proeeedinos of the A CM Computer Network Performance Symposium, (April 1982), pp. 47-55

Digital Library

[16]

Nachbar, Daniel; "TRACK- A System for Automatic Distribution of Software and Data," Bell Communications Research Technical Memo (1986, in press).

[17]

Ni, Lionel M. and Hwang, Kai; "Optimal Load Balancing in a Multiple Processor System with Many Job Classes," IEEE Transactions on Software Engineering, SF_,-ll, no. 5 (May 1985), pp. 491-496

[18]

Popek, G., Walker, B., Chow, J., Edwards, D., Kline, C., Rudisin, G., Thiel, G., " Locus: A Network Transparent, High Reliability Distributed System," Proceedings of the Eighth Symposium on Operating Systems Principles, Operating System6 Review, 15, no. 5 (December 1981), pp. 169-77

Digital Library

[19]

Peachey, Darwyn R.; Bunt, Richard B.; Wiliiamson, Carey L.; and Brecht, Tim B.; "An Experimental Investigation of Scheduling Strategies for UNIX," Proceedings of the 1984 Sigmetrics Conference on Measurement and Modeling of Computer Systems, Performance Evaluation Review, 12, no. 3 (August 198.4), pp. 158 - 166

Digital Library

[20]

Stankovie, John A.; "Simulations of Three Adaptive, Decentralized Controlled, Task Scheduling Algorithms," Computer Networks, 8, no. 3 (June 1984), pp. 199-217

Digital Library

[21]

Stankovic, John A.; "Stability and Distributed Scheduling Algorithms," IEEE Transactio# on Software Engineering, SE,-ll, no. 10 (October 1985), pp. 1141- 1152

Digital Library

[22]

Tantawi, Asset N. and Towsley, Don; "Optimal Static Load Balancing in Distributed Computer Systerr#," Journal o/the A CM, 82, no. 2 (April 1985), pp. 445-485

Digital Library

[23]

Wang, Yung-Terng and Morris, Robert J. T.; '#oad Sharing in Distributed Systems," IEEE Transactions on Computers, C-84, no. 3 (March 1985), pp. 204-217

Cited By

Van Tendeloo YVangheluwe H(2017)Increasing the performance of a Discrete Event System Specification simulator by means of computational resource usage “activity” modelsSIMULATION10.1177/003754971772659593:12(1045-1061)Online publication date: 30-Aug-2017
https://doi.org/10.1177/0037549717726595
Sudarsan RRibbens C(2016)Combining performance and priority for scheduling resizable parallel applicationsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.09.00787:C(55-66)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.09.007
Trivedi K(2016)Continuous Random VariablesProbability and Statistics with Reliability, Queuing and Computer Science Applications10.1002/9781119285441.ch3(121-200)Online publication date: 26-Aug-2016
https://doi.org/10.1002/9781119285441.ch3
Show More Cited By

Recommendations

Load-balancing heuristics and process behavior
SIGMETRICS '86/PERFORMANCE '86: Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation
Dynamic load balancing in a system of loosely-coupled homogeneous processors may employ both judicious initial placement of processes and migration of existing processes to processors with fewer resident processes. In order to predict the possible ...
Multi-cluster load balancing based on process migration
APPT'07: Proceedings of the 7th international conference on Advanced parallel processing technologies

Load balancing is important for distributed computing systems to achieve maximum resource utilization, and process migration is an efficient way to dynamically balance the load among multiple nodes. Due to limited capacity of a single cluster, it's ...
Workload Characteristics for Process Migration and Load Balancing
ICDCS '97: Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97)

Is process migration useful for load balancing? We present experimental results indicating that the answer to this question depends largely on the characteristics of the applied workload. Experiments with our Shiva system, which supports remote ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 14, Issue 1

May 1986

277 pages

ISSN:0163-5999

DOI:10.1145/317531

Editor:
Blaine D. Galther
Burroghs Corp., Santa Ana, CA

Issue’s Table of Contents

SIGMETRICS '86/PERFORMANCE '86: Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation
May 1986
262 pages
ISBN:0897911849
DOI:10.1145/317499
Chairmen:
Harry G. Perros
North Carolina State Univ., Raleigh
,
William J. Stewart
North Carolina State Univ., Raleigh
,
Kishor S. Trivedi

Copyright © 1986 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: 01 May 1986

Published in SIGMETRICS Volume 14, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

174
Total Citations
View Citations
1,145
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)14

Reflects downloads up to 10 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Van Tendeloo YVangheluwe H(2017)Increasing the performance of a Discrete Event System Specification simulator by means of computational resource usage “activity” modelsSIMULATION10.1177/003754971772659593:12(1045-1061)Online publication date: 30-Aug-2017
https://doi.org/10.1177/0037549717726595
Sudarsan RRibbens C(2016)Combining performance and priority for scheduling resizable parallel applicationsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.09.00787:C(55-66)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.09.007
Trivedi K(2016)Continuous Random VariablesProbability and Statistics with Reliability, Queuing and Computer Science Applications10.1002/9781119285441.ch3(121-200)Online publication date: 26-Aug-2016
https://doi.org/10.1002/9781119285441.ch3
Ghasemi MLubin B(2015)Modeling multi-attribute demand for sustainable cloud computing with copulaeProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832612(2596-2602)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832612
Nahir AOrda ARaz DMedhi D(2012)Distributed oblivious load balancing using prioritized job replicationProceedings of the 8th International Conference on Network and Service Management10.5555/2499406.2499413(55-63)Online publication date: 22-Oct-2012
https://dl.acm.org/doi/10.5555/2499406.2499413
Singh HKumar S(2012)Dispatcher Based Dynamic Load Balancing on Web Server SystemInternational Journal of System Dynamics Applications10.4018/ijsda.20120401021:2(15-27)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.4018/ijsda.2012040102
Muzy AVarenne FZeigler BCaux JCoquillard PTouraille LPrunetti DCaillou PMichel OHill D(2012)Refounding of the activity concept? Towards a federative paradigm for modeling and simulationSIMULATION10.1177/003754971245785289:2(156-177)Online publication date: 22-Oct-2012
https://doi.org/10.1177/0037549712457852
Chen XLiu XWang SChang X(2012)TailConProceedings of the 2012 IEEE 31st Symposium on Reliable Distributed Systems10.1109/SRDS.2012.72(61-70)Online publication date: 8-Oct-2012
https://dl.acm.org/doi/10.1109/SRDS.2012.72
Wang SMunawar WLiu JChen JLiu X(2012)Power-Saving Design for Server Farms with Response Time Percentile GuaranteesProceedings of the 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium10.1109/RTAS.2012.35(273-284)Online publication date: 16-Apr-2012
https://dl.acm.org/doi/10.1109/RTAS.2012.35
Wang JQiao CSudhaakar RAddepalli SJin YArgibay-Losada P(2012)Flow Inspection Router Assignment (FIRA) in Access/Aggregation Network CloudsProceedings of the 2012 32nd International Conference on Distributed Computing Systems Workshops10.1109/ICDCSW.2012.86(436-445)Online publication date: 18-Jun-2012
https://dl.acm.org/doi/10.1109/ICDCSW.2012.86
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Figures

Tables

Media

View Issue’s Table of Contents