Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-10-07
2003-06-10
Banankhah, Majid (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06578064
ABSTRACT:
BACKGROUND OF THE INVENTION
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
Nakamura Tomoaki
Saito Masahiko
Shimada Masaru
Tsunedomi Kunihiko
Yokoyama Takanori
Antonelli Terry Stout & Kraus LLP
Banankhah Majid
LandOfFree
Distributed computing system 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 computing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed computing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158927