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.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
Additional Information:© 2006 IEEE. Supported by NSF grants CCR-0133077, CCR-0311383, 0313148, and a 2005 Pittsburgh Digital Greenhouse Grant.
Funding AgencyGrant Number
2005 Pittsburgh Digital Greenhouse GrantUNSPECIFIED
Record Number:CaltechAUTHORS:20190306-130910057
Persistent URL:
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
Deposited By: Tony Diaz
Deposited On:06 Mar 2019 22:50
Last Modified:16 Nov 2021 16:59

Repository Staff Only: item control page