• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Formalization of uniprocessor and multiprocessor scheduling of real-time systems using supervisory control of discrete-event systems.
【24h】

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

机译：使用离散事件系统的监督控制，对实时系统的单处理器和多处理器调度进行形式化。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 tau time units completes stau 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.
机译：离散事件系统的监督控制理论已应用于实时系统。我们提出的工作的贡献在于开发了一种正式的构造方法，用于控制在单处理器和多处理器系统上实时任务的抢先执行。系统的所有可能定时迹线的集合由离散定时自动机指定，其中每个过渡与事件发生或一个时间单位的过去相关。这种方法允许基于实时应用程序模型的时序分析对调度理论进行统一的了解，这意味着确定可调度性和找到合适的调度算法的问题被认为是混合问题，而解决方案则是一个也是另一种解决方案。首先，提出了一种基于监督控制理论（SCT）设计用于单处理器实时任务的通用调度程序的框架。为此，在SCT中引入了优先级，并将其应用于离散定时自动机的设置，以便开发用于在单个CPU上进行任务调度的正式统一框架。通用调度器不确定地选择要执行的任务，以最小限度的方式满足所有时序约束，同时它包含所有可行的确定性调度策略。然后，我们通过提供一种正式的构造方法来扩展该框架，以控制硬实时任务的抢先式和迁移式执行，同时在一组统一的处理器上调度它们。该方法依赖于这样的思想，即可以通过对表示实时应用的模型的可控制动作的连续且适当的限制来获得调度系统的模型。在统一的多处理器中，每个处理器的特征在于其自身的计算能力，这种解释是在tau时间单位的计算能力为s的处理器上执行的任务将完成stau执行单位。由于我们在调度程序设计中明确表示了离散时间，因此模型大小很大。使用监督控制合成调度程序的复杂性[62]源于以下事实：对于同步乘积，复合定时离散事件系统（TDES）的状态数量会随着实时任务的数量呈指数增长。 。我们试图通过使用非正式程序设计状态空间减少的非正式程序，来减轻在使用离散事件系统框架的监督控制为实时系统设计调度程序时遇到的一些状态爆炸问题[39，41]。

著录项

  • 作者

    Janarthanan, Vasudevan.;

  • 作者单位

    Concordia University (Canada).;

  • 授予单位 Concordia University (Canada).;
  • 学科 Engineering Electronics and Electrical.
  • 学位 Ph.D.
  • 年度 2007
  • 页码 103 p.
  • 总页数 103
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 无线电电子学、电信技术;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号