ON NONPREEMPTIVE LCFS SCHEDULING WITH DEADLINES

We investigate some real time behaviour of a (discrete time) single se rver system with nonpreemptive LCFS task scheduling. The main results deal with the probability distribution of a random variable SRD(T), wh ich 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 sched uling disciplines (e.g., FCFS) is suitable here again, establishing th e power of such techniques once more. Relying on a simple general prob ability model, asymptotic formulas concerning all moments of SRD(T) ar e determined; for example, the expectation of SRD(T) is proved to grow exponentially in T, i.e., E[SRD)(T)] similar to CT(3/2)rho(T) for som e rho > 1. Our computations rely on a multivariate (asymptotic) coeffi cient extraction technique which we call asymptotic separation, (C) 19 95 Academic Press, Inc.