Distributed real-time operating system providing dynamic guaranteed mixed priority scheduling for communications and processing

• US 6,687,257 B1
• Filed: 09/30/1999
• Issued: 02/03/2004
• Est. Priority Date: 08/12/1999
• Status: Expired due to Term

• Current Assignee: Allen-Bradley Company LLC (Rockwell Automation, Inc.)
• Original Assignee: Rockwell Automation Technologies Incorporated (Allen-Bradley Co., Inc.)
• Inventors: Balasubramanian, Sivaram
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LY, ANH VU H
• Application Number:
  US09/408,696
• Time in Patent Office: 1,587 Days
• Field of Search: 370/363, 370/368, 370/371, 370/374, 370/378, 370/381, 370/382, 370/383, 370/412, 370/413, 370/428, 370/429, 709/102, 709/103, 709/104, 709/105, 709/107, 709/207, 709/215
• US Class Current: 370/429
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/31218 Scheduling communication on bus
• CPC Class Codes: G05B 2219/32266 Priority orders
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

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.

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.

2. The distributed control system of claim 1 wherein the messages are associated with a pre-identified priority and wherein communication circuit further includes:

(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.

4. The communication circuit of claim 3 wherein when there are multiple messages with the same priority and LATEST STARTING TIME, the scheduler inserts the new message in a location in the queue according to the completion timing constraint of the new message relative to the other messages of the queue.

5. The communication circuit of claim 4 wherein when there are multiple messages with the same priority, LATEST STARTING TIME and completion timing constraint, the scheduler inserts the new message in a location in the queue according to the execution time of the new message relative to the other messages in the queue.

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.

10. The operating system of claim 9 wherein when there are multiple tasks with the same priority and LATEST STARTING TIME, the scheduler inserts the new task in a location in the queue according to the completion timing constraint of the new task relative to the other tasks of the queue.

11. The operating system of claim 10 wherein when there are multiple tasks with the same priority, LATEST STARTING TIME and completion timing constraint, the scheduler inserts the new task in a location in the queue according to the execution time of the new task relative to the other tasks in the queue.

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.