Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling

Details Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling

2008-05-14

arxiv.org/abs/0805.1968v1

Computer Science

Performance

26 pages, 2 figures

Scientific paper

We study the conditional sojourn time distributions of processor sharing (PS), foreground background processor sharing (FBPS) and shortest remaining processing time first (SRPT) scheduling disciplines on an event where the job size of a customer arriving in stationarity is smaller than exactly k>=0 out of the preceding m>=k arrivals. Then, conditioning on the preceding event, the sojourn time distribution of this newly arriving customer behaves asymptotically the same as if the customer were served in isolation with a server of rate (1-\rho)/(k+1) for PS/FBPS, and (1-\rho) for SRPT, respectively, where \rho is the traffic intensity. Hence, the introduced notion of conditional limits allows us to distinguish the asymptotic performance of the studied schedulers by showing that SRPT exhibits considerably better asymptotic behavior for relatively smaller jobs than PS/FBPS. Inspired by the preceding results, we propose an approximation to the SRPT discipline based on a novel adaptive job grouping mechanism that uses relative size comparison of a newly arriving job to the preceding m arrivals. Specifically, if the newly arriving job is smaller than k and larger than m-k of the previous m jobs, it is routed into class k. Then, the classes of smaller jobs are served with higher priorities using the static priority scheduling. The good performance of this mechanism, even for a small number of classes m+1, is demonstrated using the asymptotic queueing analysis under the heavy-tailed job requirements. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.

Affiliated with

Also associated with

No associations

Rating

Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-55305