On Nonpreemptive LCFS Scheduling with Deadlines

We investigate some real time behaviour of a (discrete time) single server system with nonpreemptive LCFS task scheduling. The main results deal with the probability distribution of a random variable SRD(T), which describes the time the system operates without any violation of a fixed task service time deadline T. A tree approach, similar to those already used for the derivation of the same quantities for other scheduling disciplines (e.g., FCFS) is suitable here again, establishing the power of such techniques once more. Relying on a simple general probability model, asymptotic formulas concerning all moments of SRD(T) are determined; for example, the expectation of SRD(T) is proved to grow exponentially in T, i.e., ESRD(T)] ∼ CT^3/2ρ^T for some ρ > 1. Our computations rely on a multivariate (asymptotic) coefficient extraction technique which we call asymptotic separation.