Sojourn times in (discrete) time shared systems and their continuous time limits

摘要

We consider two classes of preemptive processor sharing scheduling policies in which the instantaneous weight given to a customer depends on a) the amount of service already imparted to the customer (Age-based scheduling), or b) the amount of service yet to be imparted to the customer (Residual Processing Time, RPT, based scheduling). We analyze the system for the mean sojourn time of a tagged customer conditioned on its service requirement. The main contribution of this article are:i) We decompose the sojourn time of a customer into two parts: a) the contribution of the descendants of the customer, and b) the contribution of the jobs (and their descendants) which the customer sees on arrival. For the preemptive system under consideration, it is shown that the behavior of the mean sojourn time for large values of service requirement is determined only by the first term above. We provide a closed form expression for this component of the sojourn time for general Age-based and RPT-based scheduling disciplines.iii) If the weight assigned to a customer with an age x units is xα for some α, we show that the behavior of mean sojourn time conditioned on service requirement is asymptotically linear for all 0 ≤ α ≤ 1. Moreover, this asymptotic slope is same for 0 ≤ α 1 and shows a discontinuity at α = 1.