Queen's University - Utility Bar

QSpace at Queen's University >
Graduate Theses, Dissertations and Projects >
Queen's Graduate Theses and Dissertations >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1974/1787

Title: Scheduling Algorithms for Real-Time Systems

Files in This Item:

File Description SizeFormat
Mohammadi_Arezou_200904_PhD.pdf607.28 kBAdobe PDFView/Open
Keywords: Scheduling Algorithms
Real Time Systems
Issue Date: 2009
Series/Report no.: Canadian theses
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
URI: http://hdl.handle.net/1974/1787
Appears in Collections:Queen's Graduate Theses and Dissertations
School of Computing Graduate Theses

Items in QSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


  DSpace Software Copyright © 2002-2008  The DSpace Foundation - TOP