The present invention relates to a distributed computing system having a plurality of computers connected to a network for cooperatively executing a plurality of programs, and more particularly to the configuration and method for such a distributed computing system which utilizes priority to realize real-time characteristics.
For ensuring real-time characteristics in a conventional computer system consisting only of a single computer (including a multi-processor type computer), there has been utilized an approach of controlling the order of programs to be processed based on the priority of the programs. “Operating Systems—Design and Implementation” by A. S. Tanenbaum, published by Prentice-Hall, Inc. pp. 82-84, (1987) describes an example of such processing order control using the priority of the programs.
Also, JP-A-2-113362, for example, describes a control scheme in which priority information is added to each message, when communicated between processing nodes in a distributed computing system, such that the messages are processed in the order of priority starting from the message with the highest priority level (this system is hereinafter called the “prior art 1”).
Another conventional scheme is also described in JP-A-5-35701. This scheme specifies a tolerable processing pending time when a processing request is issued in a distributed computing system having a plurality of processors, examines a scheduled processing pending time of each processor, and assigns the processing request to a processor whose scheduled processing pending time is shorter than the tolerable processing pending time. If no processors satisfy the tolerable processing pending time, the processing request is assigned to the processor with the shortest scheduled processing pending time. Processing requests assigned to the respective processors are processed beginning with basically the oldest one (this system is hereinafter called the “prior art 2”).
Further, as described, for example, in JP-A-5-35701, when processing requests are issued, a tolerable processing pending time as well as a priority level, similar to the prior art 1, are added to each request such that the processing requests, after assigned to processors, are processed by the respective assigned processors in the order of the priority level (this method is hereinafter called the “prior art 3”).
In a distributed computing system in which a plurality of computers are managed by respective operating systems associated therewith, the priority of programs is separately managed in each of the computers. Therefore, the priority of programs to be executed by the respective computers cannot be managed uniformly in the whole distributed computing system. Particularly in a distributed computing system having computers which differ in performance and load, the urgency represented by the priority of a computer may differ from the urgency represented by the priority of another computer. More specifically, in comparison of a high-performance computer with a low-performance computer, the former can complete processing faster than the latter even if they execute the same processing having a priority level set to zero. Similarly, between a heavily loaded computer and a lightly loaded computer, the meaning given by their respective priority levels will be different from each other.
Moreover, in a distributed computing system having a plurality of different kinds of computers, the priority scheme itself may be different from one computer to another. For example, a computer having a priority level range from 0 to 255 is not compatible with a computer having a priority level range from 0 to 127 with respect to the value set to the priority level. Similarly, the same priority level cannot be used in a computer which regards priority level 0 as the highest rank as well as in a computer which regards priority level 255 as the highest rank.
The prior art 1 simply transmits a message together with a priority level without considering the difference in performance, load, and type among individual computers in a distributed computing system. Therefore, if a message is sent to a low-performance computer or a heavily loaded computer, it is probable that the processing is not executed at a desired speed, possibly resulting in failing to ensure the real-time characteristics.
Further, in the prior art 1, when a plurality of computers are requested to execute programs, a reverse phenomenon may occur, i.e., a request with a lower priority level is completed faster than a request with a higher priority level. For example, assume that processing A with priority level 5 is requested to a computer A, while processing B with priority level 1 to a computer B (assume also that a higher priority is represented by a smaller priority level). In this event, the processing B should have been completed faster than the processing A, for conforming to the original intention. However, if the performance of the computer B is lower than that of the computer A, or if the computer B is more heavily loaded than the computer A, it is possible that the processing A with lower priority be completed faster than the processing B with higher priority.
Furthermore, since the prior art 1 does not consider a situation in which processing requests concentrate on a single computer, particularly, a situation in which processing requests with higher priority levels concentrate on a single computer, the computer which has received a large number of requests with higher priority levels presents difficulties in ensuring the real-time characteristics.
The prior art 2, in turn, may be used to ensure the real-time characteristics to a certain extent for individual processing requests, provided that the scheduled processing pending time can be correctly calculated for the respective processors. However, this system may fail to satisfy a time limit condition for a processing request with a short tolerable processing pending time which is newly issued after a certain number of processing requests have already been assigned to respective processors. For example, even in a situation where, if a processor was able to process a newly issued processing request prior to processing requests with a long tolerable processing pending time which have already been assigned to processors, the time limit condition would be satisfied for all of the processing requests, the system of the prior art 2, which assigns processing requests in order, occasionally fails to satisfy the time limit condition for the newly issued processing request. In other words, the prior art 2 is incapable of immediately processing a highly urgent processing request which is issued in a relatively heavily loaded situation. Thus, the prior art 2 has a problem that strict real-time characteristics cannot be ensured.
The prior art 3, on the other hand, is a system which involves: (1) selecting a processor which meets a tolerable processing pending time in assigning a processing request to a processor; and (2) executing processing requests in the order of the priority levels accompanied to the respective requests in each of the processors. According to the prior art 3, the disadvantage of the prior art 2 can be solved to some degree by setting a high priority level to a newly issued processing request with a short tolerable processing pending time. However, since this system preferentially processes a newly assigned processing request with a high priority level, it may fail to satisfy a processing pending tolerable time of an already assigned processing request with a low priority level which was determined that its tolerable processing pending time would be satisfied. For example, assume that, in a situation where a processing request A with a tolerable processing pending time set to one minute and with priority level 5 has been assigned to a processor A, determined that the tolerable processing pending time thereof would be satisfied, a processing. request B with a tolerable processing pending time set to 30 seconds and with priority level 1 is newly assigned to the processor A. In this event, the processing request B is processed prior to the processing request A. This preferential execution may result in failing to satisfy the tolerable processing pending time of the processing request A which has already been assigned to the same processor and for which the tolerable processing pending time should have been ensured to be satisfied.
Also, in the prior art 3, when different processing requests with the same tolerable processing pending time but with different priority levels are assigned to a plurality of processors, a reverse phenomenon similar to that of the prior art 1 can occur due to the difference in load amount and performance among the assigned processors, where processing requested with a lower priority level can be completed faster than processing requested with a higher priority level.
USPTO Backgrounds
USPTO Backgrounds