Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Achieving Efficiency and Accuracy in the ALPS Application-level Proportional-share Scheduler

  • Published:
Journal of Grid Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

We present the design and implementation of ALPS, a per-application user-level proportional-share scheduler. It provides an application with a way to control the relative allocation of CPU time amongst its individual processes. The ALPS scheduler runs as just another process (belonging to the application) at user level; thus, it does not require any special kernel support, nor does it require any special privileges, making it highly portable. To achieve efficiency, ALPS delegates fine-grained time-slicing responsibility to the underlying kernel scheduler, while itself making coarse-grained decisions to achieve proportional-share scheduling, all in a way that is transparent to the underlying kernel. Our results show that the ALPS approach is practical; we can achieve good accuracy (under 5% relative error) and low overhead (under 1% of CPU time), despite user-level operation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amza, C., Cecchet, E., Chanda, A., Cox, A., Elnikety, S., Gil, R., Marguerite, J., Rajamani, K., Zwaenepoel, W.: Bottleneck characterization of dynamic web site benchmarks. Technical Report TR02-389, Rice University (2002)

  2. Amza, C., Cecchet, E., Chanda, A., Cox, A., Elnikety, S., Gil, R., Marguerite, J., Rajamani, K., Zwaenepoel, W.: Specification and implementation of dynamic web site benchmarks. In: Proc. IEEE 5th Annual Workshop on Workload Characterization (2002)

  3. Anderson, T.E., Bershad, B.N., Lazowska, E.D., Levy, H.M.: Scheduler activations: effective kernel support for the user-level management of parallelism. In: Proc. 13th ACM Symp. on Op. Sys. Princ. (1991)

  4. Arpaci-Dusseau, A.C., Arpaci-Dusseau, R.H.: Information and control in gray-box systems. In: Proc. 18th ACM Symp. on Op. Sys. Princ. (2001)

  5. Arpaci-Dusseau, A.C., Arpaci-Dusseau, R.H., Burnett, N.C., Denehy, T.E., Engle, T.J., Gunawi, H.S., Nugent, J.A., Popovici, F.I.: Transforming policies into mechanisms with infokernel. In: Proc. 19th ACM Symp. on Op. Sys. Princ. (2003)

  6. Banga, G., Druschel, P., Mogul, J.C.: Resource containers: a new facility for resource management in server systems. In: Proc. 3rd Symposium on Operating Systems Design and Implementation. USENIX (1999)

  7. Bavier, A., Bowman, M., Chun, B., Culler, D., Karlin, S., Muir, S., Peterson, L., Roscoe, T., Spalink, T., Wawrzoniak, M.: Operating system support for planetary-scale services. In: Proc. First Symposium on Network Systems Design and Implementations (NSDI) (2004)

  8. Bavier, A., Voigt, T., Wawrzoniak, M., Peterson, L., Gunninberg, P.: SILK: scout paths in the linux kernel. Technical Report 2002-009, Department of Information Tecnology, Uppsala University (2002)

  9. Chandra, A., Adler, M., Goyal, P., Shenoy, P.: Surplus fair scheduling: a proportional-share CPU scheduling algorithm for symmetric multiprocessors. In: Proc. 4th OSDI (2000)

  10. Chu, H., Nahrstedt, K.: A soft real time scheduling server in UNIX operating system. In: Proc. 4th Intl. Workshop on Interactive Distributed Multimedia Systems and Telecommunication Services (1997)

  11. Douceur, J.R., Bolosky, W.J.: Progress-based regulation of low-importance processes. In: Proc. 17th ACM Symp. on Op. Sys. Princ. (1999)

  12. Druschel, P., Banga, G.: Lazy receiver processing (LRP): a network subsystem architecture for server systems. In: Proc. 2nd Symposium on Operating Systems Design and Implementation. USENIX (1996)

  13. Duda, K.J., Cheriton, D.R.: Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler. In: Proc. 17th ACM Symp. on Op. Sys. Princ. (1999)

  14. Engler, D.R., Kaashoek, M.F., O’Toole, J. Jr.: Exo- kernel: an operating system architecture for appli- cation-level resource management. In: Proc. 15th ACM Symp. on Op. Sys. Princ. (1995)

  15. Goyal, P., Guo, X., Vin, H.M.: A hierarchial CPU scheduler for multimedia operating systems. In: Proc. 2nd OSDI (1996)

  16. Jeffay, K., Smith, F.D., Moorthy, A., Anderson, J.: Proportional share scheduling of operating system services for real-time applications. In: Proc. IEEE Real-Time Systems Symposium. IEEE Computer Society (1998)

  17. Jones, M.B., Rosu, D., Rosu, M.-C.: CPU reservations and time constraints: efficient, predictable scheduling of independent activities. In: Proc. 16th ACM Symp. on Op. Sys. Princ. (1997)

  18. Lu, Y., Abdelzaher, T.F., Lu, C., Tao, G.: An adaptive control framework for QoS guarantees and its application to differentiated caching services. In: Proc. 10th Intl. Workshop on Quality of Service (2002)

  19. McKusick, M.K., Bostic, K., Karels, M.J., Quarterman, J.S.: The Design and Implementation of the 4.4BSD Operating System. Addison-Wesley, Reading (1996)

    Google Scholar 

  20. Newhouse, T., Pasquale, J.: Java active extensions: scalable middleware for performance-isolated remote execution. Elsevier Computer Communications Journal 28(14), 1680–1691 (2005)

    Article  Google Scholar 

  21. Nieh, J., Lam, M.S.: A SMART scheduler for multimedia applications. ACM Trans. Comput. Syst. 21(2), 117–163 (2003)

    Article  Google Scholar 

  22. Nieh, J., Vaill, C., Zhong, H.: Virtual-time round-robin: an O(1) proportional share scheduler. In: Proc. 2001 USENIX Annual Technical Conf. (2001)

  23. Regehr, J., Stankovic, J.A.: HLS: a framework for composing soft real-time schedulers. In: Proc. 22nd IEEE Real-Time Systems Symposium (2001)

  24. Slashdot. http://www.slashdot.org/ (2004)

  25. Verghese, B., Gupta, A., Rosenblum, M.: Performance isolation: sharing and isolation in shared-memory multiprocessors. In: Proc. 8th International Conference on Architectural Support for Programming Languages and Operating Systems (1998)

  26. von Behren, R., Condit, J., Zhou, F., Necula, G.C., Brewer, E.: Capriccio: scalable threads for internet services. In: Proc. 19th ACM Symp. on Op. Sys. Princ. (2003)

  27. Waldspurger, C.A., Weihl, W.E.: Stride scheduling: deterministic proportional-share resource management. Technical Report MIT/LCS/TM-528, Massachusetts Institute of Technology (1995)

  28. Yuan, W., Nahrstedt, K.: Energy-efficient soft real-time cpu scheduling for mobile multimedia systems. In: Proc. 19th ACM Symp. on Op. Sys. Princ. (2003)

Download references

Author information

Authors and Affiliations

  1. Computer Science and Engineering, University of California, San Diego, La Jolla, CA, 92093-0404, USA

    T. Newhouse & J. Pasquale

Authors
  1. T. Newhouse
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Pasquale
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Pasquale.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Newhouse, T., Pasquale, J. Achieving Efficiency and Accuracy in the ALPS Application-level Proportional-share Scheduler. J Grid Computing 5, 251–270 (2007). https://doi.org/10.1007/s10723-007-9067-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10723-007-9067-7

Key words

Search

Navigation