Allocation and scheduling of real-time periodic tasks with relative timing constraints

Sheng Tzong Cheng, Ashok K. Agrawala

Research output: Contribution to conferencePaper

14 Citations (Scopus)

Abstract

Allocation problem has always been one of the fundamental issues of building the applications in real-time computing systems. For real-time applications, the allocation problem should directly address the issues of task and communication scheduling. In this context, the allocation of tasks has to fully utilize the available processors and the scheduling of tasks has to meet the specified timing constraints. Clearly, the execution of tasks under the allocation and schedule has to satisfy the precedence, resources, and other synchronization constraints among them. Recently, the timing requirements of the real-time systems emerge that the relative timing constraints are imposed on the consecutive executions of each task and the inter-task temporal relationships are specified across task periods. In this paper we consider the allocation and scheduling problem of the periodic tasks with such timing requirements. Given a set of periodic tasks, we consider the least common multiple (LCM) of the task periods. Each task is extended to several instances within the LCM. The scheduling window for each task instance is derived to satisfy the timing constraints. We develop a simulated annealing algorithm as the overall control algorithm. An example problem of the sanitized version of the Boeing 777 Aircraft Information Management System is solved by the algorithm. Experimental results show that the algorithm solves the problem in a reasonable time complexity.

Original languageEnglish
Pages210-217
Number of pages8
Publication statusPublished - 1995 Dec 1
EventProceedings of the 1995 2nd International Workshop on Real-Time Computing Systems and Applications - Tokyo, Jpn
Duration: 1995 Oct 251995 Oct 27

Other

OtherProceedings of the 1995 2nd International Workshop on Real-Time Computing Systems and Applications
CityTokyo, Jpn
Period95-10-2595-10-27

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Allocation and scheduling of real-time periodic tasks with relative timing constraints'. Together they form a unique fingerprint.

  • Cite this

    Cheng, S. T., & Agrawala, A. K. (1995). Allocation and scheduling of real-time periodic tasks with relative timing constraints. 210-217. Paper presented at Proceedings of the 1995 2nd International Workshop on Real-Time Computing Systems and Applications, Tokyo, Jpn, .