Understanding the slowdown of large jobs in an M/GI/1 system
- 1 December 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 30 (3) , 9-11
- https://doi.org/10.1145/605521.605526
Abstract
We explore the performance of an M/GI/1 queue under various scheduling policies from the perspective of a new metric: the it slowdown experienced by largest jobs. We consider scheduling policies that bias against large jobs, towards large jobs, and those that are fair, e.g., Processor-Sharing. We prove that as job size increases to infinity, all work conserving policies converge almost surely with respect to this metric to no more than 1/(1-ρ), where ρ denotes load. We also find that the expected slowdown under any work conserving policy can be made arbitrarily close to that under Processor-Sharing, for all job sizes that are sufficiently large.Keywords
This publication has 2 references indexed in Scilit:
- Exploiting process lifetime distributions for dynamic load balancingACM Transactions on Computer Systems, 1997
- The Queue M/G/1 with the Shortest Remaining Processing Time DisciplineOperations Research, 1966