Loss Ratios of Different Scheduling Policies for Firm Real-time System : Analysis and Comparisons
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.
Showing items related by title, author, creator and subject.
Divya, V D (2013-02-28)Superalloys offer high temperature strength, excellent creep, corrosion and oxidation resistances, microstructural stability and good fatigue life at elevated temperatures. The composition of the superalloys has been ...
Bharath, B N (2018-04-02)Multiple-Input Multiple-Output (MIMO) communication using multiple antennas has received significant attention in recent years, both in the academia and industry, as they offer additional spatial dimensions for high-rate ...
Baheti, Varun A (2018-08-28)The electro–mechanical connection between under bump metallization (UBM) and solder in flip–chip bonding is achieved by the formation of brittle intermetallic compounds (IMCs) during the soldering process. These IMCs ...