• Login
    View Item 
    •   Home
    • Graduate Theses, Dissertations and Projects
    • Queen's Graduate Theses and Dissertations
    • View Item
    •   Home
    • Graduate Theses, Dissertations and Projects
    • Queen's Graduate Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Scheduling Algorithms for Real-Time Systems

    Thumbnail
    View/Open
    Mohammadi_Arezou_200904_PhD.pdf (607.2Kb)
    Date
    2009-04-24
    Author
    Mohammadi, Arezou
    Metadata
    Show full item record
    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.
    URI for this record
    http://hdl.handle.net/1974/1787
    Collections
    • Queen's Graduate Theses and Dissertations
    • School of Computing Graduate Theses
    Request an alternative format
    If you require this document in an alternate, accessible format, please contact the Queen's Adaptive Technology Centre

    DSpace software copyright © 2002-2015  DuraSpace
    Contact Us
    Theme by 
    Atmire NV
     

     

    Browse

    All of QSpaceCommunities & CollectionsPublished DatesAuthorsTitlesSubjectsTypesThis CollectionPublished DatesAuthorsTitlesSubjectsTypes

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    DSpace software copyright © 2002-2015  DuraSpace
    Contact Us
    Theme by 
    Atmire NV