Distributed control method and apparatus

• US 7,322,033 B2
• Filed: 03/26/2003
• Issued: 01/22/2008
• Est. Priority Date: 03/29/2002
• Status: Expired due to Fees

• Current Assignee: DENSO Corporation
• Original Assignee: DENSO Corporation
• Inventors: Ito, Takafumi
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Tang; Kenneth
• Application Number:
  US10/396,474
• Publication Number:
  US 20030187907A1
• Time in Patent Office: 1,763 Days
• Field of Search: 718/100, 718/102, 718106-108, 718/104, 719/313
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

In a distributed control method of executing distributed control such that a lot of tasks distributively executed in a lot of nodes connected to a network and made to implement multitasking operations communicate a message with each other to operate cooperatively in time sequence, an estimated completion time of the distributed control is calculated by summing up the worst execution times of the processing times of all tasks pertaining to the distributed control and the communication times of all messages between the tasks and an initial value of a margin time with respect to a deadline is determined by subtracting the estimated completion time from a control cycle of the distributed control. This margin time is set for each of all the distributed control to be executed on the system and is sequentially updated in accordance with the states of the tasks and messages. The processing on the tasks or the transmission of the messages is made preferentially in the order of lengthening margin time. This assures a response time and deadline condition to be required in distributed control without imposing an excessive burden on a designer of a distributed control system.

Claims

1. A method of controlling distributed control executed in time sequence through mutual communication of messages by a plurality of tasks distributively executed on a plurality of nodes connected to a network for the communication and respectively made to implement parallel multitasking operations for the distributed control, the method comprising:

making each of the nodes set, with respect to each of said tasks executable on the respective nodes, a margin time representative of a difference between an estimated completion time of said distributed control relating to each executed task, and a deadline time of said distributed control;

making each of the nodes allocate a higher execution right preferentially to each of said tasks in an ascending order of the margin time;

determining whether or not an execution time of any of said tasks reaching completion of the execution does not reach a worst case execution time set in advance for said task;

when it is determined that the execution time of said task reaching completion of the execution does not reach a worst case execution time, increasing said margin time for said task by a value corresponding to a difference between said worst case execution time and said execution time and

when it is determined that said execution time thereof exceeds said worst case execution time, decreasing said margin time for said task by said value corresponding to the difference therebetween.

2. The method according to claim 1, further comprising

determining whether or not the margin time is smaller than a switching decision time set in advance;

and

when it is determined that said margin time is smaller than the switching decision time, switching the corresponding task from a normal task to be used in a normal condition to a simplified task shorter in execution time than said normal task.

3. The method according to claim 1, further comprising determining whether or not the margin time is smaller than a discontinuation decision time set in advance;

and

when it is determined that said margin time is smaller than the discontinuation decision value, discontinuing the execution of the corresponding task.

4. The method according to claim 1, wherein said margin time of said tasks waiting for acquisition of an execution right is shortened with a passage of time until said tasks acquire said execution right.

5. The method according to claim 1, further comprising:

determining whether or not an execution time of said task acquiring an execution right overruns a worst case execution time set in advance for said task; and

when it is determined that the execution time of said task acquiring the execution right overruns the worst case execution time, decreasing said margin time for said task with a passage of time until the execution of said task comes to an end.

6. The method according to claim 1, wherein in the making of the nodes to allocate, said margin time for said message waiting for acquisition of said communication right is decreased with a passage of time until said message acquires said communication right.

7. The method according to claim 1, further comprising:

transmitting in said messages, time information indicative of said margin time for said messages together with said messages.

8. The method according to claim 7, wherein, in the making of the nodes to set, in setting said margin time for said task at the lime of activation of said task, for a first task to be activated initially in said distributed control, an initial time of said margin time prepared in advance is set as said margin time, and for other tasks, other than the first task, to be activated upon receipt of said message, a time value based on said time information inserted into said message is set as said margin time.

9. The method according to claim 8, further comprising:

transmitting said message through the use of a frame according to the CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) method on said network; and

inserting said time information in an area of said frame to be used for arbitration control on said transmission line.

10. The method according to claim 8, further comprising:

transmitting said message through the use of a frame according to the CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) method on said network;

inserting said time information in an area of said frame to be used for arbitration control on said transmission line; and

executing simultaneously both arbitration for communication in the plurality of nodes and transmitting said time information.

11. The method according to claim 1, wherein said margin time of said tasks waiting for acquisition of an execution right is shortened with a passage of time, and said tasks acquire said execution right at a time that said margin time of said tasks waiting for acquisition of the execution right below a margin time of the tasks currently having said execution right.

12. The method according to claim 1, wherein in the making of the nodes to allocate, said margin time for said message waiting for acquisition of said communication right is decreased with a passage of time, and said message acquires said communication right is below a margin time of the task currently having said communication right.

13. A method of controlling distributed control executed in time sequence through mutual communication of messages by a plurality of tasks distributively executed on a plurality of nodes connected to a network for the communication and respectively made to implement parallel multitasking operations for the distributed control, the method comprising:

making each of the nodes set, with respect to each of said tasks executable on the respective nodes, a margin time representative of a difference between an estimated completion time of said distributed control relating to each executed task, and a deadline time of said distributed control; and

making each of the nodes allocate a higher execution right preferentially to each of said tasks in an ascending order of the margin time;

determining whether or not said margin time is smaller than a switching decision value set in advance; and

when it is determined that said margin time is smaller than the switching decision value, switching the corresponding message from a normal message to be used at an ordinary condition to a simplified message smaller in size than said normal message,

wherein in the making of the nodes to allocate, on the basis of said margin time for said distributed control to which each of messages transmittable pertains, each of said nodes allocates a message transmission right preferentially to each of said messages in the ascending order of the margin time.

14. A method of controlling distributed control executed in time sequence through mutual communication of messages by a plurality of tasks distributively executed on a plurality of nodes connected to a network for the communication and respectively made to implement parallel multitasking operations for the distributed control, the method comprising:

making each of the nodes set, with respect to each of said tasks executable on the respective nodes, a margin time representative of a difference between an estimated completion time of said distributed control relating to each executed task, and a deadline time of said distributed control; and

making each of the nodes allocate a higher execution right preferentially to each of said tasks in an ascending order of the margin time;

determining whether or not an estimated communication time to be taken from which said communication right is acquired until the communication comes to an end in the case of assuming that the transmission is made successfully at the next transmission occasion does not reach a worst case communication time set in advance;

when it is determined that the estimated communication time does not reach the worst case communication time, increasing said margin time for said message by a value corresponding to a difference between said worst case communication time and said estimated communication time; and

when it is determined that said estimated communication time exceeds said worst case communication time, decreasing said margin time for said message by said value corresponding to said difference therebetween,

wherein in the making of the nodes to allocate, on the basis of said margin time for said distributed control to which each of messages transmittable pertains, each of said nodes allocates a message transmission right preferentially to each of said messages in the ascending order of the margin time.

15. A distributed control apparatus implemented in each of a plurality of nodes communicably connected to a network so that the nodes communicate with each other through the network to distributedly execute a plurality of tasks, in which each node is made to implement multitasking operations and each task communicates a message with other tasks to be executed on another node for cooperatively executed distributed control, said distributed control apparatus comprising:

task scheduling means for, i) scheduling, on the basis of a margin time representative of a difference between an estimated completion time of said distributed control relating to each executed task, and a deadline time of said distributed control, and ii) allocating an execution right preferentially to each of said tasks, placed into an executable state, in an ascending order of the margin time;

message transmitting/receiving means for transmitting/receiving said message produced by said task and time information representative of said margin time for said message, inserted into said message, through said network and for, when receiving a message, issuing a request to one of the plurality of nodes for activation of said task corresponding to said message to said task scheduling means;

activation time setting means for, when said task is activated by said task scheduling means and when said task is a first task to be initially executed in said distributed control, setting an initial value of said margin time prepared in advance as said margin time for said task and for, when said task is other than said first task and is activated in response to reception of said message, setting a value based on said time information inserted into said message as said margin time for said task; and

first updating means for sequentially updating said margin time, set by said activation time setting means, in accordance with an execution state of each of said tasks by said task scheduling means.

16. The apparatus according to claim 15, further comprising message scheduling means for, on the basis of said margin time for each of said messages, allocating a message transmission right in said message transmitting/receiving means preferentially to each of said messages in an ascending order of the margin time.

17. The apparatus according to claim 15, further comprising second updating means for sequentially updating said margin time, set by said activation time setting means, in accordance with an execution state of the transmission of each of said messages by said message transmitting/receiving means.

18. A distributed control apparatus implemented in each of a plurality of nodes communicably connected to a network so that the nodes communicate with each other through the network to distributedly execute a plurality of tasks, in which each node is made to implement multitasking operations and each task communicates a message with other tasks to be executed on another node for cooperatively executed distributed control, said distributed control apparatus comprising:

task scheduling means for, i) scheduling, on the basis of a margin time representative of a difference between an estimated completion time of said distributed control relating to each executed task and a deadline time of said distributed control , ii) allocating an execution right preferentially to each of said tasks, placed into an executable state, in an ascending order of the margin time, iii) transfer said execution right for said task being executed, to a new task when the margin time of said new task reaches below said margin time of said tasks being executed;

message transmitting/receiving means for transmitting/receiving said message produced by said task and time information representative of said margin time for said message, inserted into said message, through said network, executing simultaneously both arbitration for communication in the plurality of nodes and transmitting said time information and issuing a request to one of the plurality of nodes for activation of said task corresponding to said message to said task scheduling means;

message scheduling means for, on the basis of said margin time for each of said messages waiting for a message transmission right, allocating said message transmission right in said message transmitting/receiving means preferentially to each of said messages in the ascending order of the margin time, and when an event occurs for a message has a smaller margin time than said margin time of said message currently transmitting with said transmission right, issuing a request for starting transmitting of said message having said smaller margin time to said message transmitting/receiving means;

activation time setting means for, when said task is activated by said task scheduling means and when said task is a first task to be initially executed in said distributed control, setting an initial value of said margin time prepared in advance as said margin time for said task and for, when said task is other than said first task and is activated in response to reception of said message, setting a value based on said time information inserted into said message as said margin time for said task; and

first updating means for sequentially updating said margin time, set by said activation time setting means, in accordance with an execution state of each of said tasks by said task scheduling means.