On Nonpreemptive LCFS Scheduling with Deadlines

✍ Scribed by U. Schmid; J. Blieberger

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 947 KB
• Volume: 18
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.1004

✦ Synopsis

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 (\operatorname{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 (\operatorname{SRD}(T)) are determined: for example, the expectation of (\operatorname{SRD}(T)) is proved to grow exponentially in (T), i.e.. (E[\mathrm{SRD}(T)] \sim C T^{3 / 2} \rho^{T}) for some (\rho>1). Our computations rely on a multivariate (asymptotic) coefficient extraction technique which we call asymptotic separation. ." 1945 Academic Press. inc