[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/233013.233019acmconferencesArticle/Chapter ViewAbstractPublication PagesmetricsConference Proceedingsconference-collections
Article
Free access

Exploiting process lifetime distributions for dynamic load balancing

Published: 15 May 1996 Publication History

Abstract

We measure the distribution of lifetimes for UNIX processes and propose a functional form that fits this distribution well. We use this functional form to derive a policy for preemptive migration, and then use a trace-driven simulator to compare our proposed policy with other preemptive migration policies, and with a non-preemptive load balancing strategy. We find that, contrary to previous reports, the performance benefits of preemptive migration are significantly greater than those of non-preemptive migration, even when the memory-transfer cost is high. Using a model of migration costs representative of current systems, we find that preemptive migration reduces the mean delay (queueing and migration) by 35 - 50%, compared to non-preemptive migration.

References

[1]
Rakesh Agrawal and Ahmed Ezzet. Location independent remote execution in NEST. IEEE Transactions on Software Engineering, 13(8):905-912, August 1987.
[2]
Y. Artsy and R. Finkel Designing a process migration facility: The Charlotte experience. IEEE Computer, pages 47-56, September 1989.
[3]
Raymond M. Bryant and Raphael A. Finkel. A stable distributed scheduling algorithm. In 2rid International Conference on Distributed Computing Systems, pages 314-323, 1981.
[4]
Havio Bonomi and Anurag Kumar. Adaptive optimal load balancing in a nonhomogeneous multiserver system with a central job scheduler. IEEE Transactions on Computers, 39(10): 1232-1250, October 1990.
[5]
Avner Braverman, 1995. Personal Communication.
[6]
Amnon Barak, Guday Shai, and Richard G. Wheeler. The MOSIX Distributed Operating System:Load Balancing for UNIX Springer Vedag, Berlin, 1993.
[7]
Jeremy Casas, Dan L. Clark, Ravi Konuru, Steve W. Otto, Robert M. Prouty, and Jonathan Walpole. Mpvm: A migration transparent version of pvm. Computing Systems, 8(2):171-216, Spring 1995.
[8]
Thomas L. Casavant and Jon G. Kuhl. Analysis of three dynamic distributed load-balancing strategies with varying global informataon requirements. In 7th International Conference on Distributed Computing Systems, pages 185-192, September 1987.
[9]
Allen B. Downey and Mor Harchol-Balter A note on "The limited performance benefits of migrating active processes for load sharing". Technical Report UCB//CSD-95-888, University of California, Berkeley, November 1995.
[10]
Fred Douglis and John Ousterhout. Transparent process rmgration: Design alternatives and the sprite implementation. Software- Praeuce and Experience, 21(8).757-785, August 1991.
[11]
D.J. Evans and W U. N. Butt Dynamic load balancing using tasktransfer probablilites. Parallel Computing, 19:897-916, August 1993.
[12]
Derek L. Eager, Edward D. Lazowska, and Joht~ Zahorjan. Adaptive load sharing in homogeneous distributed systems. IEEE Transactions on Software Engineering, 12(5)'662-675, May 1986.
[13]
Derek L. Eager, Edward D. Lazowska, and John Zahorjan. The limited performance benefits of migrating active processes for load sharing. In S1GMETRICS, pages 662-675, May 1988.
[14]
G.W. Gerrity, A. Goscinski, J. Indulska, W. Toomey, and W. Zhu. RHODOS-a testbed for studying design issues in distributed operating systems, in Towards Network Globalization (SICON 91): 2nd intert~tional Conference on Networks, pages 268-274, September 1991.
[15]
Anna Ha6 and Xiaowei Jin. Dynamic load balancing in a distributed system using a sender-initiated algorithm. Journal of Systems Software, 11'79-94, 1990
[16]
John L Hennessy and David A. Patterson. Computer Architecture A Quantitative Approach. Morgan Kaufmann Publishers, San Mateo, CA, 1990
[17]
Phillip Krueger and Miron Livny. A comparison of preemptive and non-preemptive load distributing In 8th International Conference on Distributed Computing Systems, pages 123-130, June 1988.
[18]
Thomas Kunz. The influence of different workload descriptions on a heuristic load balancing scheme. IEEE Transactions on Software Engineering, I7(7):725-730, July 1991.
[19]
M. Litzkow and M. Livny. Experience with the Condor distributed batch system. In IEEE Workshop on Experimental Distributed Systems, pages 9%101, 1990.
[20]
M.J. Litzkow, M. Livny, and M.W. Mutka. Condor - a hunter of idle workstations. In 8th International Conference on Distributed Computing Systems, June 1988.
[21]
Miron Livny and Myron Melman. Load balancing in homogeneous broadcastdistributed systems In ACM Computer Network Perfor. mance Symposium, pages 47-55, April 1982.
[22]
W.E. Leland and T. J. Ott. Load-balancing heuristics and process behavior. In Proceedings of Performance and ACM Sigmetrics, volume 14, pages 54--69, 1986.
[23]
Hwa-Chun Lin and C.S. Raghavendra. A state-aggregation method for analyzing dynamic load-balancing policies. In IEEE 13th International Conference on Distributed Computing Systems, pages 482--489, May 1993.
[24]
Raw Mirchandaney, Don Towsley, and John A. Stankovic. Adaptive load sharing in heterogeneous distributed systems. Journal of Parallel and Distributed Computing, 9:331-346, 1990.
[25]
Mark Nuttall. Survey of systems providing process or object migration. Technical Report DOC94/10, Imperial College Research Report, 1994.
[26]
M.L. Powell and B.P. Miller. Process migrations in DEMOS/MP In ACM-SIGOPS 6th ACM Symposium on Operating Systems Principles, pages I 10-119, November 1983.
[27]
S'piridon Pulidas, Don Towsley, and John A. Stankovic. Imbedding gradient estimators in load balancing algorithms. In 8th International Conference on Distributed Computing Systems, pages 482-490, June 1988.
[28]
C Gary Rommel. The probability of load balancing success in a homogeneous network. IEEE Transactions on Software Engineering, 17:922-933, 1991.
[29]
Robert E Rosin. Determining a computing center environment. Communications of the ACM, 8(7), 1965.
[30]
A. Silberschatz, J.L. Peterson, and P.B. Galvin. Operating System Concepts, 4th Edition. Addison-Wesley, Reading, MA, 1994.
[31]
Anders Svensson. History, an intelligent load sharing filter. In IEEE lOth International Conference on Distributed Computing Systems, pages 546-553, 1990.
[32]
G. Thiel. Locus operating system, a transparent system. Computer Communications, 14(6):336-346, 1991.
[33]
Marvin M. Theimer, Keith A. Lantz, and David R Cheriton. Preemptable remote execution facilities for the V-System. In ACM-SIGOPS lOth ACM Symposium on Operating Systems Principles, pages 2-I2, December 1985.
[34]
A.S. Tanenbaum, R. van Renesse adn H. van Staveren, and G.J. Sharp. Experiences with the Amoeba distributed operating system. Communications of the ACM, pages 336-346, December 1990.
[35]
Amin Vahdat, 1995. Personal Communication
[36]
Amin M. Vahdat, Douglas P. Ghormtey, and Thomas E Anderson. Eftieient,portable, and robust extension of operating system functionality. Technical Report UCB//CSD-94-842, University of California, Berkeley, 1994.
[37]
Yung-Terng Wang and Robert J.T. Morris. Load sharing in distributed systems. IEEE Transactions on Computers, c-94(3):204-217, March 1985.
[38]
J. Wang, S. Zhou, K.Ahmed, and W. Long. LSBATCH: A distributed load ~hafing batch system. Tochnical Roport C8RI-286, Computer Systems Research Institute, University of Toronto, April 1993.
[39]
E.R. Zayas. Attacking the process migration bottleneck. In ACM- SIGOPS llth ACM Symposium on Operating Systems Principles, pages 13-24, 1987.
[40]
Songnian Zhou. Performance studies for dynamic load balancing in distributed systems. PhD Dissertation, University of California, Berkeley, 1989.
[41]
S Zhou, J. Wang, X. Zheng, and P. Delisle. Utopia: a load-sharing faeitlity for large heterogeneous distributed computing systems. Software - Practice and Expeience, 23(2): 1305-1336, December 1993.

Cited By

View all
  • (2024)Load Balancing with Job-Size Testing: Performance Improvement or Degradation?ACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36511549:2(1-27)Online publication date: 4-Mar-2024
  • (2020)BorgProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387517(1-14)Online publication date: 15-Apr-2020
  • (2019)Reducing Writebacks Through In-Cache DisplacementACM Transactions on Design Automation of Electronic Systems10.1145/328918724:2(1-21)Online publication date: 10-Jan-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGMETRICS '96: Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
May 1996
279 pages
ISBN:0897917936
DOI:10.1145/233013
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 May 1996

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMETRICS96
Sponsor:

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)100
  • Downloads (Last 6 weeks)13
Reflects downloads up to 11 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Load Balancing with Job-Size Testing: Performance Improvement or Degradation?ACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36511549:2(1-27)Online publication date: 4-Mar-2024
  • (2020)BorgProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387517(1-14)Online publication date: 15-Apr-2020
  • (2019)Reducing Writebacks Through In-Cache DisplacementACM Transactions on Design Automation of Electronic Systems10.1145/328918724:2(1-21)Online publication date: 10-Jan-2019
  • (2019)Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distributions2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2019.8919929(9-16)Online publication date: Sep-2019
  • (2017)Detecting and mitigating data-dependent DRAM failures by exploiting current memory contentProceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3123939.3123945(27-40)Online publication date: 14-Oct-2017
  • (2016)Using Regression Techniques to Predict Large Data TransfersThe International Journal of High Performance Computing Applications10.1177/109434200317300417:3(249-268)Online publication date: 26-Jul-2016
  • (2014)Application level scheduling of gene sequence comparison on metacomputersACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667176(269-276)Online publication date: 10-Jun-2014
  • (2010)Display power management policies in practiceProceedings of the 7th international conference on Autonomic computing10.1145/1809049.1809057(51-60)Online publication date: 7-Jun-2010
  • (2009)Managing responsiveness of virtual desktops using passive monitoringProceedings of the 11th IFIP/IEEE international conference on Symposium on Integrated Network Management10.5555/1688933.1688985(319-326)Online publication date: 1-Jun-2009
  • (2009)LDP Lean Document Production---O.R.-Enhanced Productivity Improvements for the Printing IndustryInterfaces10.1287/inte.1080.041339:1(69-90)Online publication date: 1-Jan-2009
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media