The Foreground-Background queue: a survey
Misja Nuyens Adam Wierman
5th October 2006
Abstract Computer systems researchers have begun to apply the Foreground-Background (FB) scheduling discipline to a variety of applications, and as a result, there has been a resurgence in theoretical research studying FB. In this paper, we bring together results from both of these research streams to provide a survey of state-of-the-art theoretical results characterizing the performance of FB. Our emphasis throughout is on the impact of these results on computer systems.
Keywords: scheduling policies, FB, LAST, SEPT, M/G/1 queue
1
Introduction
Scheduling is a common mechanism for improving computer-system performance without purchasing additional resources. Simple policies such as First-Come-First-Served (FCFS) and ProcessorSharing (PS), which shares the service capacity equally among all jobs in the system, are most commonly used in computer systems. However, many recent system designs use policies that give priority to jobs with small service demands in order to reduce the mean response time (sojourn times) and mean queue length, see, e.g., [25, 42]. The emergence of policies that prioritize small jobs is motivated by the Shortest-RemainingProcessing-Time (SRPT) policy, which always serves the job in the system that needs the least amount of service in order to complete: SRPT is known to be optimal with respect to mean response time and mean queue length [51, 52]. The improvement of SRPT over FCFS and PS with respect to mean response time is quite dramatic under heavy-tailed service distributions, which appear frequently as models for service-demand distributions in computer systems, see for example Crovella and Bestavros [15] and Taqqu et al. [55].
Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081, 1081 HV Amsterdam, The
Netherlands, mnuyens@few.vu.nl Computer Science Department, Carnegie Mellon University, 5000 Forbes Avenue Pittsburgh, PA, USA, acw@cs.cmu.edu

下一页