Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
1999-09-30
2004-02-03
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Store and forward
C709S241000
Reexamination Certificate
active
06687257
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
BACKGROUND OF THE INVENTION
The present invention relates to industrial controllers for controlling industrial processes and equipment and more generally to an operating system suitable for a distributed industrial control system having multiple processing nodes spatially separated about a factory or the like.
Industrial controllers are special purpose computers used for controlling industrial processes and manufacturing equipment. Under the direction of a stored control program the industrial controller examines a series of inputs reflecting the status of the controlled process and in response, adjusts a series of outputs controlling the industrial process. The inputs and outputs may be binary, that is on or off, or analog providing a value within a continuous range of values.
Centralized industrial controllers may receive electrical inputs from the controlled process through remote input/output (I/O) modules communicating with the industrial controller over a high-speed communication network. Outputs generated by the industrial controller are likewise transmitted over the network to the I/O circuits to be communicated to the controlled equipment. The network provides a simplified means of communicating signals over a factory environment without multiple wires and the attendant cost of installation.
Effective real-time control is provided by executing the control program repeatedly in high speed “scan” cycles. During each scan cycle each input is read and new outputs are computed. Together with the high-speed communications network, this ensures the response of the control program to changes in the inputs and its generation of outputs will be rapid. All information is dealt with centrally by a well-characterized processor and communicated over a known communication network to yield predictable delay times critical to deterministic control.
The centralized industrial controller architecture, however, is not readily scalable, and with foreseeably large and complex control problems, unacceptable delays will result from the large amount of data that must be communicated to a central location and from the demands placed on the centralized processor. For this reason, it may be desirable to adopt a distributed control architecture in which multiple processors perform portions of the control program at spatially separate locations about the factory. By distributing the control, multiple processors may be brought to bear on the control problem reducing the burden on any individual processor and the amount of input and output data that must be transmitted.
Unfortunately, the distributed control model is not as well characterized as far as guaranteeing performance as is required for real-time control. Delay in the execution of a portion of the control program by one processor can be fatal to successful real-time execution of the control program, and because the demand for individual processor resources fluctuates, the potential for an unexpected overloading of a single processor is possible. This is particularly true when a number of different and independent application programs are executed on the distributed controller and where the application programs compete for the same set of physical hardware resources.
One weak point in the distributed control model is the introduction of communication delays in the execution of control tasks. These communication delays result from the need for different portions of the control program on different spatially separated hardware to communicate with each other. In a typical first-in/first-out (FIFO) communication system, where outbound messages are queued according to their time of arrival at the communication circuit, a message with a high priority, as may be necessary for the prompt completion of a control task, will always be transmitted later than an earlier arriving message of low priority. This can cause a form of unbounded priority inversion where low priority task block high priority tasks, and this may upset the timing requirements of the real-time control program.
A second problem with the distributed control model arises from operating distributed control devices in a multi-tasking mode to be shared among different program tasks. Such multi-tasking is necessary for efficient use of hardware resources. Present real-time multitasking operating systems allow the assignment of a priority to a given task. The user selects the necessary priority levels for each task to ensure that the timing constraints implicit in the real-time control process are realized.
One problem with this approach is first that it is necessarily conservative because the priorities must be set before the fact resulting in poor utilization of the scheduled resource. Further because the timing constraints are not explicit but only indirectly reflected in the priorities set by the user, the operating system is unable to detect a failure to meet the timing constraints during run time.
On the other hand, some dynamic scheduling systems (which adapt to the circumstances at run-time) exist but they don't accept user assigned priorities and thus provide no guarantee as to which tasks will fail under transient overload conditions. There are also scheduling systems for multi-tasking that allow for both setting of priorities and that have a dynamic component to allow for greater processor utilization, for example, those that use the Maximum Urgency First algorithm. See generally D. B. Stewart and P. K. Khosla, “Real Time Scheduling of Dynamically Reconfigurable Systems,” Proceedings of the 1991 International Conference on Systems Engineering, Dayton August 1991 pp. 139-142.
Unfortunately, such algorithms require rescheduling of all tasks as a new task becomes ready for execution. This results in greater overhead and produces a potential for an unbounded number of context switches (in which the scheduled resource switches its task) which can be detrimental to guaranteeing a completion time for a particular task as required by real-time control. Further current scheduling systems do not provide any guarantee for execution time of the tasks and the potential allow low priority tasks to fail.
SUMMARY OF THE INVENTION
The present invention provides an operating system for a distributed control system that applies more sophisticated scheduling to the queuing of messages intercommunicating between distributed tasks. By investing the communication circuitry with an appropriate scheduling system, guarantees may be made for the completion of distributed tasks of which communication between the distributed tasks is a part.
The scheduling used in the preferred embodiment considers both the priority of the message and an allocated portion of a timing constraint imposed on the message by the operating system, that timing constraint portion being a fraction of the timing guarantee for the task of which the message is a part. Messages are only transmitted if bandwidth for the message has been pre-allocated by the operating system.
The mixed priority scheduling system for messages may also be used more generally in scheduling tasks for the processor in a multi-tasking environment.
Specifically then, the present invention provides a distributed control system having a network and a set of spatially distributed control components attached to the network, each including a processor and a memory system as well as a portion of an application distributed over these multiple control components. A communication circuit connects the control component to the network allowing intercommunication via messages with other control components having other portions of the application program. The operating system provides a time constraint value for the execution of the portion of an application program at a given control component and the communication circuit responds to the time constraint value to queue the message to meet the time constraint value.
Thus it is one object of the invention to produce a communication circuit that is sensitive
Gerasimow Alexander M.
Ly Anh-Vu H
Pham Chi
Quarles & Brady LLP
Rockwell Automation Technologies Inc.
LandOfFree
Distributed real-time operating system providing dynamic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed real-time operating system providing dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed real-time operating system providing dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3339756