Scheduling Algorithms for Real-Time Systems
Loading...
Authors
Mohammadi, Arezou
Date
2009-04-24T19:59:53Z
Type
thesis
Language
eng
Keyword
Scheduling Algorithms , Real Time Systems
Alternative Title
Abstract
Real-time systems are those whose correctness depends not only on logical results
of computations, but also on the time at which the results are produced. This thesis
provides a formal definition for real-time systems and includes the following original
contributions on real-time scheduling algorithms.
The first topic studied in the thesis is minimizing the total penalty to be paid
in scheduling a set of soft real-time tasks. The problem is NP-hard. We prove the
properties of any optimal scheduling algorithm. We also derive a number of heuristic
algorithms which satisfy the properties obtained. Moreover, we obtain a tight upper
bound for the optimal solution to the problem. Numerical results that compare the
upper bound with the optimal solution and the heuristic algorithms are provided.
In the second part of this thesis, we study the problem of minimizing the number
of processors required for scheduling a set of periodic preemptive independent hard
real-time tasks. We use a partitioning strategy with an EDF scheduling algorithm
on each processor. The problem is NP-hard. We derive lower and upper bounds
for the number of processors required to satisfy the constraints of the problem. We
also compare a number of heuristic algorithms with each other and with the bounds
derived in this research. Numerical results demonstrate that our lower bound is very
tight.
In the third part of the thesis, we study the problem of uplink scheduling in
telecommunication systems with two dimensional resources. Our goal is to maximize
the total value of the packets sent in uplink subframe such that system constraints and
requirements are satisfied. The packets have various QoS requirements and have
either soft or hard deadlines. We take two approaches, namely 0-1 and fractional
approaches, to model the problem. Considering the properties of the application, we
derive globally optimal solutions in polynomial time for the models. We also present
a method to fine-tune the models. Numerical results are provided to compare the
performance of the various optimal algorithms each corresponding to a model.
Description
Thesis (Ph.D, Computing) -- Queen's University, 2009-04-24 08:22:04.238
Citation
Publisher
License
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.