Task scheduling and message passing

Details Task scheduling and message passing Task scheduling and message passing

1999-05-14

2003-05-20

Banankhah, Majid (Department: 2127)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000, C709S241000, C709S241000

Reexamination Certificate

active

06567840

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to task scheduling and message passing within task systems, and in particular to modeling real-time periodic and aperiodic task scheduling and message passing adapted to analyze the timing behavior within multitask systems and to define electronic systems and instructions for carrying out such scheduling and message passing.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright© 1999, Honeywell, Inc., All Rights Reserved.
BACKGROUND
Computer processes are often subdivided into a variety of functions which may be executed as tasks in serial and/or parallel fashion. These computer processes can be used to gather and act upon information, and to bring about some result in response to the information. These functional task systems find use in a variety of important environments. Examples may include monitor and control of an industrial process, such as a power generation and distribution system, or monitor and control of complex equipment, such as a commercial airliner.
Classical control functions rely on data flows between periodically executed tasks, with the results of a task delivered at the next dispatch of that task. This behavior allows cyclic data dependencies among tasks, i.e., feed-back loops, and is consistent with the assumptions underlying the mathematical analysis of discrete time dynamic systems. A message passing communication model is more suitable for partitioned multiprocessor systems than a shared memory communication model, especially systems that are loosely coupled to maintain a high degree of hardware fault isolation.
In many mission critical systems software needs to be modularized using an appropriate functional breakdown, which often requires decomposing a traditional control task into multiple communicating subtasks. This may require end-to-end ordering and scheduling of certain subtasks and messages. For example, in an avionics system, inertial measurement processing and autopiloting might be implemented as separate functions performed by separate task sets. There would be an end-to-end deadline from reading sensor data to outputting actuator commands, and task and message order dependencies within this deadline.
The increasing complexity of hardware makes it harder to accurately bound computation and communication times. Caches, for example, make it more difficult to accurately bound worst-case compute times, even for algorithms whose control flow is data-independent. Actual worst-case compute times may be substantially less than bounds that can be easily established during development. Actual compute times may vary significantly across different dispatches of the same task. Systems will be designed so that only the more critical functions are guaranteed with highest assurance to be schedulable under worst-case compute time bounds. Load shredding of the less critical tasks will occur during any intervals of transient processor overload.
High-assurance systems have additional requirements. The dependency ordering of computations and communications, and the exact times of interactions with the external world, must produce deterministic outcomes. Uncertainties or variations in task compute times must not affect the values of designated control outputs. It is necessary to formally model and analyze the timing behavior of a system. Specifications, models, analyses and code all need to be well-structured, understandable, traceable and amenable to multiple independent means of verification.
There is a need in the art for solutions in modeling real-time periodic and aperiodic task scheduling and message passing useful in integrated mission-critical systems, or in systems with high-rate applications and microcontrollers having constrained throughput and/or memory.
SUMMARY
The invention addresses deterministic communication between two periodic processes. It includes a communication model, a deadline reduction technique, a period transformation technique and implementation efficiency buffer assignment rules.
In one embodiment, the invention provides a method of generating an assigned scheduling priority of a plurality of tasks in a multitask system. The method includes defining a first list of the plurality of tasks, wherein the first list of the plurality of tasks is sorted with a task deadline as a primary key and a task criticality as a secondary key. The method further includes transforming the task deadline of each of the plurality of tasks that do not produce undelayed messages. The transformation occurs one at a time using a transformation scenario beginning with the task having the least task deadline, thereby producing a transformed task deadline for each of the plurality of tasks. The method still further includes defining a second list of the plurality of tasks, wherein the second list of the plurality of tasks is sorted with the transformed task deadline as the primary key and wherein each transformed task deadline of a task having a first task criticality is less than any transformed task deadline of a task having a task criticality less than the first task criticality. Scheduling priority is then assigned in the order of the second list of the plurality of tasks, thereby producing the assigned scheduling priority. In a further embodiment, the multitask system is a flight control system.
In another embodiment, the invention provides a method of operating a multitask system. The method includes communicating among tasks, with each task having a priority and a criticality. Each task is a sender and/or receiver of undelayed messages and/or single sample delay messages. The method further includes assigning a priority to each sender task sending undelayed messages such that the priority of the sender task is higher than the priority of any downstream receiver task. The method further includes assigning a priority to each sender task that does not send undelayed messages, where each such task having a first criticality has a priority greater than any such task having a criticality lower than the first criticality. The method still further includes executing each of the tasks on a processor according to their assigned priorities. In yet another embodiment, the multitask system is a flight control system.
In a further embodiment, the invention provides a multitask system. The multitask system includes a processor and a plurality of tasks operating on the processor. Each task is of a periodic or aperiodic task type. Each task has associated with it at least one I/O buffer. Communications with each I/O buffer is adapted to either undelayed messages or single sample delay messages. An executive task having a periodic dispatcher, an event handler and a service component is utilized for controlling dispatching of tasks and communications among the I/O buffers. The periodic dispatcher manages dispatching of periodic tasks and their single sample delay communications. The event handler manages dispatching of aperiodic tasks and their single sample delay message communications. The service component manages task completions and all undelayed message communications. In a still further embodiment, the multitask system is a flight control system.


REFERENCES:
patent: 3648253 (1972-03-01), Mullery et al.
patent: 5408663 (1995-04-01), Miller
patent: 5560032 (1996-09-01), Nguyen et al.
patent: 5566177 (1996-10-01), Bhandari et al.
patent: 5630096 (1997-05-01), Zuravleff et al.
Hiroyuki Kaneko, John A. Stankovic: “Integrated Scheduling of Multimedia And Hard Real-Time Tasks”, Proceedings of the IEEE Real-Time Systems Symposiums, US, New York, IEEE, vol. Symp. 17, Dec. 4, 1996, pp. 206-217, XP000659642, ISBN: 0-7803-380

Affiliated with

Also associated with

Rating

Task scheduling and message passing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Task scheduling and message passing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Task scheduling and message passing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3054367