CaltechAUTHORS
  A Caltech Library Service

How to Determine a Good Multi-Programming Level for External Scheduling

Schroeder, Bianca and Harchol-Balter, Mor and Iyengar, Arun and Nahum, Erich and Wierman, Adam (2006) How to Determine a Good Multi-Programming Level for External Scheduling. In: 22nd International Conference on Data Engineering (ICDE'06). IEEE , Piscataway, NJ, Art. No. 60. ISBN 0769525709. https://resolver.caltech.edu/CaltechAUTHORS:20190306-130910057

[img] PDF - Published Version
See Usage Policy.

276Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190306-130910057

Abstract

Scheduling/prioritization of DBMS transactions is important for many applications that rely on database backends. A convenient way to achieve scheduling is to limit the number of transactions within the database, maintaining most of the transactions in an external queue, which can be ordered as desired by the application. While external scheduling has many advantages in that it doesn’t require changes to internal resources, it is also difficult to get right in that its performance depends critically on the particular multiprogramming limit used (the MPL), i.e. the number of transactions allowed into the database. If the MPL is too low, throughput will suffer, since not all DBMS resources will be utilized. On the other hand, if the MPL is too high, there is insufficient control on scheduling. The question of how to adjust theMPL to achieve both goals simultaneously is an open problem, not just for databases but in system design in general. Herein we study this problem in the context of transactional workloads, both via extensive experimentation and queueing theoretic analysis. We find that the two most critical factors in adjusting the MPL are the number of resources that the workload utilizes and the variability of the transactions’ service demands. We develop a feedback based controller, augmented by queueing theoretic models for automatically adjusting the MPL. Finally, we apply our methods to the specific problem of external prioritization of transactions. We find that external prioritization can be nearly as effective as internal prioritization, without any negative consequences, when the MPL is set appropriately.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/icde.2006.78DOIArticle
Additional Information:© 2006 IEEE. Supported by NSF grants CCR-0133077, CCR-0311383, 0313148, and a 2005 Pittsburgh Digital Greenhouse Grant.
Funders:
Funding AgencyGrant Number
NSFCCR-0133077
NSFCCR-0311383
NSFCCF-0313148
2005 Pittsburgh Digital Greenhouse GrantUNSPECIFIED
Record Number:CaltechAUTHORS:20190306-130910057
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190306-130910057
Official Citation:B. Schroeder, M. Harchol-Balter, A. Iyengar, E. Nahum and A. Wierman, "How to Determine a Good Multi-Programming Level for External Scheduling," 22nd International Conference on Data Engineering (ICDE'06), Atlanta, GA, USA, 2006, pp. 60-60. doi: 10.1109/ICDE.2006.78
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93597
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:06 Mar 2019 22:50
Last Modified:03 Oct 2019 20:56

Repository Staff Only: item control page