Distributed real-time operating system providing dynamic guaranteed mixed priority scheduling for communications and processing
First Claim
Patent Images
1. A distributed control system comprising:
- (a) a network;
(b) a set of spatially distributed control components attached to the network each including;
(i) a processor and memory system;
(ii) a portion of an application program distributed over multiple control components;
(iii) a completion timing constraint for execution of the portion of the application program at the respective control component, wherein the completion timing constraint is indicative of a maximum allowable amount of time that can occur between a receipt of an input that is logically true and an occurrence of an output in response to the input; and
(iv) a communication circuit for connecting the respective control component to the network allowing intercommunication with other control components having parts of the application program via messages and responding to the completion timing constraint to queue a message to meet the completion timing constraint.
1 Assignment
0 Petitions
Accused Products
Abstract
A communication function for connecting, via a network, distributed hardware in a distributed control system, prioritizes the queuing of messages on the network according both to a message priority established by the user and the context of the task and according to a deadline period by which the task must be executed. In this way, the normal queuing of messages for a communication network does not defeat the guarantee of the completion time of the execution of tasks. The same scheduling method may be used for the tasks themselves.
-
Citations
13 Claims
-
1. A distributed control system comprising:
-
(a) a network;
(b) a set of spatially distributed control components attached to the network each including;
(i) a processor and memory system;
(ii) a portion of an application program distributed over multiple control components;
(iii) a completion timing constraint for execution of the portion of the application program at the respective control component, wherein the completion timing constraint is indicative of a maximum allowable amount of time that can occur between a receipt of an input that is logically true and an occurrence of an output in response to the input; and
(iv) a communication circuit for connecting the respective control component to the network allowing intercommunication with other control components having parts of the application program via messages and responding to the completion timing constraint to queue a message to meet the completion timing constraint. - View Dependent Claims (2)
(a) a message queue having locations for storing messages, the locations determining an order for transmission of the messages on the network;
(b) a message scheduler operating to;
(i) receive a new message together with the completion timing constraint; and
(ii) insert the new message in the message queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new message relative to pre-identified priority information and the completion timing constraint of the other messages in the queue.
-
-
3. A communication circuit for a distributed control system having spatially separated control hardware communicating via the communication circuit over a network, the communication circuit comprising:
-
(a) a message queue having locations for storing messages, the locations determining an order for transmission of the messages on the network;
(b) a message scheduler operating to;
(i) receive a new message together with pre-identified priority information about the message and a completion timing constraint;
(ii) insert the new message in the message queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new message relative to pre-identified priority information and the completion timing constraint of the other messages in the queue, wherein the new message is further associated with an execution time necessary to transmit the message on the network and wherein the scheduler inserts the new message in a location in the message queue first according to priority of the new message and then if there are multiple messages with the same priority second according to LATEST STARTING TIME of the new message with respect to other messages in the queue;
wherein the LATEST STARTING TIME equals an arrival time of the new message at the communication circuit plus the completion timing constraint minus the execution time. - View Dependent Claims (4, 5)
-
-
6. A communication circuit for a distributed control system having spatially separated control hardware communicating via the communication circuit over a network, the communication circuit comprising:
-
(a) a message queue having locations for storing messages, the locations determining an order for transmission of the messages on the network;
(b) a message scheduler operating to;
(i) receive a new message together with pre-identified priority information about the message and a completion timing constraint;
(ii) insert the new message in the message queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new message relative to pre-identified priority information and the completion timing constraint of the other messages in the queue, wherein the new message is further associated with a user application program and an interarrival period and wherein the scheduler only inserts the new message in the queue after the interarrival period has expired for a previous message associated with the user application program.
-
-
7. A communication circuit for a distributed control system having spatially separated control hardware communicating via the communication circuit over a network, the communication circuit comprising:
-
(a) a message queue having locations for storing messages, the locations determining an order for transmission of the messages on the network;
(b) a message scheduler operating to;
(i) receive a new message together with pre-identified priority information about the message and a completion timing constraint;
(ii) insert the new message in the message queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new message relative to pre-identified priority information and the completion timing constraint of the other messages in the queue. wherein;
(i) the new message provides communication among portions of a user application divided among the spatially separated control hardware; and
(ii) the user application has an application completion timing constraint; and
wherein the message scheduler is implemented by a processor executing a portion of a distributed operating system providing the completion timing constraint as a portion of the applicant completion timing constraint of the user application.
-
-
8. A communication circuit for a distributed control system having spatially separated control hardware communicating via the communication circuit over a network, the communication circuit comprising:
-
(a) a message queue having locations for storing messages, the locations determining an order for transmission of the messages on the network;
(b) a message scheduler operating to;
(i) receive a new message together with pre-identified priority information about the message and a completion timing constraint;
(ii) insert the new message in the message queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new message relative to pre-identified priority information and the completion timing constraint of the other messages in the queue;
wherein;
(i) the new message provides communication among portions of a user application divided among the spatially separated control hardware; and
(ii) the new message is further associated with a user application program;
wherein the message scheduler is implemented by a processor executing a portion of a distributed operating system providing an allocation of a portion of a total time of the communication circuit to each of a plurality of application programs; and
wherein the scheduler only inserts the new message in the queue if the new message'"'"'s execution time will not exceed the allocation of a portion of the total time given to the application program associated with the new message.
-
-
9. An operating system for a distributed control system having spatially separated control processors communicating via a network, the operating system executing on a processor to:
-
(a) generate a task queue having locations for a storing task identifier identifying portions of application programs for execution on the processor, the locations determining an order for execution of the portions of application programs on the processor;
(b) a task scheduler operating to;
(i) receive a new task together with pre-identified priority information about the task and a completion timing constraint; and
(ii) insert the new task in the task queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new task relative to pre-identified priority information and the completion timing constraint of the other tasks in the task queue;
wherein the new task is further associated with an execution time necessary to execute the task on the processor; and
wherein the scheduler inserts the new task in a location in the task queue first according to priority of the new task and then if there are multiple tasks with the same priority second according to LATEST STARTING TIME of the new task with respect to other tasks in the queue; and
wherein LATEST STARTING TIME equals an initiation time of the new task at the processor plus the completion timing constraint minus the execution time. - View Dependent Claims (10, 11)
-
-
12. An operating system for a distributed control system having spatially separated control processors communicating via a network, the operating system executing on a processor to:
-
(a) generate a task queue having locations for a storing task identifier identifying portions of application programs for execution on the processor, the locations determining an order for execution of the portions of application programs on the processor;
(b) a task scheduler operating to;
(i) receive a new task together with pre-identified priority information about the task and a completion timing constraint; and
(ii) insert the new task in the task queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new task relative to pre-identified priority information and the completion timing constraint of the other tasks in the task queue;
wherein the invocation of the task is further associated with an interarrival period and wherein the scheduler only inserts the new invocation of the task in the queue after the interarrival period has expired for a previous invocation of the task associated with a same user application program.
-
-
13. An operating system for a distributed control system having spatially separated control processors communicating via a network, the operating system executing on a processor to:
-
(a) generate a task queue having locations for a storing task identifier identifying portions of application programs for execution on the processor, the locations determining an order for execution of the portions of application programs on the processor, (b) a task scheduler operating to;
(i) receive a new task together with pre-identified priority information about the task and a completion timing constraint; and
(ii) insert the new task in the task queue at a location that is a function of both the pre-identified priority information and the completion timing constraint of the new task relative to pre-identified priority information md the completion timing constraint of the other tasks in the task queue;
wherein;
the operating system further provides the allocation of a portion of a total time of the processor to each of a plurality of application programs and wherein the scheduler only inserts the new task in the queue if its execution time will not exceed the allocation of a portion of the total time given to the application program associated with the new task.
-
Specification