short-paper

Analysis of the effects of weight distribution on proportional share scheduling

Authors:

AhReum Kim,

Jinman Jung,

Joonhyouk Jang,

Sang Cheol KimAuthors Info & Claims

RACS '12: Proceedings of the 2012 ACM Research in Applied Computation Symposium

Pages 448 - 450

https://doi.org/10.1145/2401603.2401698

Published: 23 October 2012 Publication History

Get Access

Abstract

Proportional share scheduling algorithms have been widely studied as means of guaranteeing the QoS of applications. These algorithms allocate CPU resources to tasks based on their weight, but most are designed to behave differently under variations in overall weight distribution and number of tasks. In this paper, we classify proportional share scheduling algorithms according to these differences in behavior and analyze the levels of QoS they achieve. Our analysis shows that variations in weight distribution and number of tasks have a significant impact on QoS. Based on this analysis, we further explain which algorithms are best suited to various environments.

References

[1]

Stoica, I., Abdel-Wahaby H. and Jeffayz, K., "A Proportional Share Resource Allocation Algorithm for Real-Time", Time-Shared Systems, IEEE Real-Time Systems Symposium, 1996.

Digital Library

Google Scholar

[2]

Shreedhar M. and Varghese, G., "Efficient Fair Queueing Using Deficit Round Robin", ACM SIGCOMM Computer Communication Review Vol. 25, No. 4, pp. 231, 1995.

Digital Library

Google Scholar

[3]

Nieh, J., Vaill, C. and Zhong, H., "Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler", Proc. USENIX Annual Technical Conference, June. 2001.

Digital Library

Google Scholar

[4]

Waldspurger, C. A., "Lottery and stride scheduling: flexible proportional-share resource management", PhD thesis, MIT, September 1995.

Digital Library

Google Scholar

[5]

J. Bennett and H. Zhang, "WF2Q: Worst-case Fair Weighted Fair Queueing," in Proceedings of INFOCOM, 1996

Digital Library

Google Scholar

[6]

B. Caprita, W. Chun Chan, J. Nieh, C. Stein, and H. Zheng, "Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems", In Proceeding of the USENIX Annual Technical Conference, pp. 337--352, 2006

Digital Library

Google Scholar

Index Terms

Analysis of the effects of weight distribution on proportional share scheduling
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Weight Distribution of the Bases of a Matroid
Abstract
Given a weighted graph, let w₁, w₂, . . . ,w_n denote the increasing sequence of all possible distinct spanning tree weights. In 1992, Mayr and Plaxton proved the following conjecture proposed by Kano: every spanning tree of weight w₁ is at most k−...
Feedback-Based Adaptive Packet Marking for Proportional Bandwidth Allocation

Differentiated service (DiffServ) networks have been proposed to assure the achievable minimum bandwidth to aggregate flows. However, analyses in the literature show that the current DiffServ networks are biased in favor of an aggregate flow that has a ...
A provision-aware fair bandwidth distribution marker algorithm for DiffServ networks

The rise in demand for real-time applications on the Internet necessitates Quality of Service (QoS). Differentiated Services (DiffServ) is one of the technologies used currently to provide QoS and service differentiation. It is simple and scalable. It ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

RACS '12: Proceedings of the 2012 ACM Research in Applied Computation Symposium

October 2012

488 pages

ISBN:9781450314923

DOI:10.1145/2401603

General Chairs:
Yookun Cho
Seoul National University, Korea
,
Rex E. Gantenbein
University of Wyoming, USA
,
Tei-Wei Kuo
National Taiwan University, Taiwan
,
Program Chair:
Vahid Tarokh
Harvard University

In-Cooperation

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Funding Sources

Ministry of Education, Science and Technology

Conference

RACS '12

Sponsor:

ACCT

RACS '12: Research in Applied Computation Symposium

October 23 - 26, 2012

Texas, San Antonio

Acceptance Rates

Overall Acceptance Rate 393 of 1,581 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
70
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

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

Index Terms

Recommendations

Weight Distribution of the Bases of a Matroid

Feedback-Based Adaptive Packet Marking for Proportional Bandwidth Allocation

A provision-aware fair bandwidth distribution marker algorithm for DiffServ networks