Computer Science Department
School of Computer Science, Carnegie Mellon University


Analyzing the Effect of Prioritized
Background Tasks in Multiserver Systems

Adam Wierman, Takayuki Osogami, Mor Harchol-Balter, Alan Scheller-Wolf

December 2003


Keywords: Reliability, M/GI/k, multiserver queue, priority queue, server farm, matrix analytic methods, busy periods, multi-class queue, preemptive priority.

Computer systems depend on high priority background processes to provide both reliability and security. This is especially true in multiserver systems where many such background processes are required for data coherence, fault detection, intrusion detection, etc. From a user's perspective, it is important to understand the effect that these many classes of high priority, background tasks have on the performance of lower priority user-level tasks.

We model this situation as an M/GI/k queue with m preemptive-resume priority classes, presenting the first analysis of this system with more than two priority classes under a general phase-type service distribution. (Prior analyses of the M/GI/k with more than two priority classes are approximations that, we show, can be highly inaccurate.) Our analytical method is very different from the prior literature: it combines the technique of dimensionality reduction with Neuts' technique for determining busy periods in multiserver systems, and then uses a novel recursive iteration technique. Our analysis is approximate, but, unlike prior techniques, can be made as accurate as desired, and is verified via simulation.

27 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by