Login | Register

Formalization of uniprocessor and multiprocessor scheduling of real-time systems using supervisory control of discrete-event systems

Title:

Formalization of uniprocessor and multiprocessor scheduling of real-time systems using supervisory control of discrete-event systems

Janarthanan, Vasudevan (2007) Formalization of uniprocessor and multiprocessor scheduling of real-time systems using supervisory control of discrete-event systems. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR30136.pdf - Accepted Version
3MB

Abstract

The theory of supervisory control of discrete-event systems has been applied to real-time systems. The contribution of our proposed work lies in the development of a formal constructive method for controlling the preemptive execution of real-time tasks on both uniprocessor and multiprocessor systems. The set of all possible timed traces of the system is specified by a discrete timed automaton, where each transition is associated with an event occurrence or the passage of one unit of time. This approach allows a unified view of scheduling theory based on the timing analysis of models of real-time applications, meaning that the problem of determining schedulability and finding out a suitable scheduling algorithm are assumed to be intermingled issues, with the solution of one in turn is a solution to the other too. First, a framework for designing universal schedulers for real-time tasks on uniprocessors based on Supervisory Control Theory (SCT) is presented. For this purpose, priorities are introduced in SCT and applied to the setting of discrete timed automata in order to develop a formal and unified framework for task scheduling on a single CPU. A universal scheduler nondeterministically selects a task for execution in such a way that all timing constraints are met in a minimally restrictive fashion, while it contains all feasible deterministic scheduling policies. We then extend that framework by providing a formal constructive method for controlling the preemptive and migrative execution of hard real-time tasks while scheduling them on a set of uniform processors. The methodology relies on the idea that the model of the scheduled system can be obtained by successive and appropriate restrictions of controllable actions of a model representing the real-time application. In uniform multiprocessors, each processor is characterized by its own computing capacity, with the interpretation that a task that executes on a processor of computing capacity s for x time units completes s x units of execution. Since we represented explicitly discrete time in our scheduler design, model sizes were considerably large. The complexity in the synthesis of a scheduler using supervisory control [62] stems from the fact that, with the synchronous product, the number of states of a composite Timed Discrete-Event System (TDES) increases exponentially with the number of real-time tasks. We have attempted to alleviate some of the state explosion problems we had faced while designing schedulers for real-time systems using supervisory control of discrete-event systems framework [39, 41], by providing an informal procedure to design schedulers with reduced state space.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Electrical and Computer Engineering
Item Type:Thesis (PhD)
Authors:Janarthanan, Vasudevan
Pagination:xiv, 103 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Electrical and Computer Engineering
Date:2007
Thesis Supervisor(s):Gohari, Peyman
ID Code:975302
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:05
Last Modified:18 Jan 2018 17:40
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top