Record Details

Loss Ratios of Different Scheduling Policies for Firm Real-time System : Analysis and Comparisons

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Loss Ratios of Different Scheduling Policies for Firm Real-time System : Analysis and Comparisons
 
Creator Das, Sudipta
 
Subject Firm Real-time Systems
Real Time Systems
Loss Ratio Comparison
First Come First Served (FCFS) Scheduling
Exact Admission Control (EAC)
Earliest Deadline First (EDF) Scheduling
Early Job Discarding Technique (EDT)
Real-time System Analysis
M/M/1 Queue System
Queing Theory Model
Service Time Dependent Scheduling
Electrical Engineering
 
Description Firm real time system with Poisson arrival process, iid exponential service times and iid deadlines till the end of service of a job, operated under the First Come First Served (FCFS) scheduling policy is well studied. In this thesis, we present an exact theoretical analysis of a similar (M/M/1 + G queue) system with exact admission control (EAC). We provide an explicit expression for the steady state workload distribution. We use this solution to derive explicit expressions for the loss ratio and the sojourn time distribution.
An exact theoretical analysis of the performance of an M/M/1 + G queue with preemptive deadlines till the end of service, operating under the Earliest Deadline First (EDF) scheduling policy, appears to be difficult, and only approximate formulas for the loss ratio are available in the literature. We present in this thesis similar approximate formulas for the loss ratio in the present of an exit control mechanism, which discards a job at the epoch of its getting the server if there is no chance of completing it. We refer to this exit control mechanism as the Early job Discarding Technique (EDT). Monte Carlo simulations of performance indicate that the maximum approximation error is reasonably small for a wide range of arrival rates and mean deadlines.
Finally, we compare the loss ratios of the First Come First Served and the Earliest Deadline First scheduling policies with or without admission or exit control mechanism, as well as their counterparts with deterministic deadlines. The results include some formal equalities, inequalities and some counter-examples to establish non-existence of an order. A few relations involving loss ratios are posed as conjectures, and simulation results in support of these are reported. These results lead to a complete picture of dominance and non-dominance relations between pairs of scheduling policies, in terms of loss ratios.
 
Contributor Jenkins, Lawrence
 
Date 2017-11-27T15:24:36Z
2017-11-27T15:24:36Z
2017-11-27
2013
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/2808
http://etd.ncsi.iisc.ernet.in/abstracts/3581/G25542-Abs.pdf
 
Language en_US
 
Relation G25542