Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-03-31
2004-04-27
Follansbee, John (Department: 2126)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C717S152000
Reexamination Certificate
active
06728961
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to distributed computer processing and, in particular, to a protocol for creating a dynamic pool of computational resources that are made available to other users and computers in a networked computer environment.
2. Description of the Related Art
In any organization with large numbers of personal computers, a large percentage of those computers are sitting idle for a significant part of the day. In recognition of this fact, it has been proposed in the prior art to add the computational resources of those computers to a pool and to make those resources available to other users and computers. This “clustering” technique theoretically enables “load balancing” of the collective resources of the system.
In one known approach, a master machine is used to distribute the load among the various connected machines. This approach, however, is undesirable because if the master machine fails, the load can no longer be balanced. Another known load balancing technique is based on remote procedure calls (RPCs). In this type of system, a set of shared procedures is distributed across similar types of machines. The procedures are designed to be separately compiled on the host machine. Before they can be accessed, the procedures are first registered with an RPC database that is resident on each machine. This approach is complex because it requires each machine in the processing group to know that address of each procedure available in the processing cluster. It further requires the procedure code to be pre-compiled, i.e. to exist in executable form, on the host, which consumes processing resources. Yet another approach to load balancing exists in platform-specific architectures, wherein pre-compiled code is run on machines that are similarly configured. That approach, however, is limited to homogeneous platforms. Still another approach is to maintain an availability or so-called “load” table for all the member computers of a cluster processing group. That approach requires significant memory and communications overhead.
Thus, there remains a need in the art to provide an improved method and system for load balancing in a distributed computer environment.
BRIEF SUMMARY OF THE INVENTION
A primary object of the present invention is to provide a protocol for aggregating available computer resources into a pool that is managed automatically and made available to users transparently, i.e. without users having to make changes to their systems in order to take advantage of the extra computational power. The inventive protocol preferably is implemented across a set of peer machines that each have an interpreter, e.g., a Java virtual machine. Machines in the pool dynamically bid for the right to interpret methods that require processing.
It is another primary object of this invention to provide a protocol by which a set of computers are transformed into a large, parallel processing cluster of machines that share resources. According to the protocol, as machines become available, they are automatically added to the processing cluster. As machines become unavailable, they are automatically removed from the group.
It is further object of this invention to load balance a set of computer resources in a decentralized manner, i.e. without the need for a central group controller.
A still further object of this invention is to implement load balancing across a processing cluster wherein machines are heterogenous.
Yet another object of the present invention is to provide a cluster-based processing group whose computational capabilities increase as needed to address system loads.
It is another object of this invention to provide a distributed processing architecture wherein if one of the machines in the group becomes unavailable, any of the other machines can take over the computing requirements of the unavailable machine.
Still another more general object of this invention is to automatically balance workload across all available machines in a processing cluster.
A further object of this invention is to provide a load balancing solution that is platform-independent.
Yet another object of this invention is to provide load balancing within a distributed computer environment that does not require procedures to be pre-compiled or registered on a given machine in the cluster group prior to their execution. Rather, the inventive protocol allows a given peer machine (a “client”) to send the code that needs to be executed to another peer machine (the “server”) in an uncompiled format so that the server can run any code on the client's behalf, not just code that has been pre-registered and compiled.
These and other objects are achieved in a distributed computing environment in which each of a plurality of peer machines includes an interpreter for interpreting methods written in an interpreted language to platform-specific methods. The interpreter, for example, is a Java virtual machine that has been modified to implement the inventive protocol. The protocol dynamically load balances a process as follows. In response to receiving a new method for interpretation at a first peer machine, the machine profiles the new method to determine whether there is an advantage to sending the new method to another peer machine for interpretation. Thus, for example, it may be advantageous to have the new method interpreted elsewhere because some other peer machine has available CPU cycles, available disk storage, available system memory, or the like. If there is an advantage to having the new method interpreted elsewhere, a given subset of the peer machines bid to interpret the new method on behalf of the first peer machine. The winning machine interprets the method on behalf of first peer machine, and then returns the results back to the first peer machine.
In one preferred embodiment, each peer machine includes a Java virtual machine interpreter that is modified or augmented to execute the inventive cluster protocol. Machines join and/or leave the cluster as their available computing resources (e.g., CPU cycles, disk memory, system memory and the like) become available or unavailable, as the case may be. Each of the “active” machines in the cluster selectively bid to interpret methods designed to be executed on a native machine. As noted above, the inventive protocol preferably profiles a given method that may be executed on another peer machine in the cluster. When a given peer machine decides to export the method to another machine in the cluster, given machines in the cluster bid for the right to execute the method. To facilitate the bidding process, the method preferably is exported, together with its associated profile, to the other machines in the processing group. The requesting machine preferably also includes its bid in the package. According to the present invention, it is not required that the method be supported on the given peer machine prior to the bidding process. In the inventive protocol, as machines become unavailable, they simply do not respond to bid requests. As machines become more heavily loaded, they lose bids.
The present invention may be implemented in various types of distributed environments. Thus, for example, a given set of peer machines may be in a bus topology. In this environment, peer machines broadcast a request for bids to other machines. Alternatively, given machines are connected in a ring topology. In this case, the bid request is issued to a given peer machine and then passed around the ring in a point-to-point manner.
The foregoing has outlined some of the more pertinent objects and features of the present invention. These objects should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial results can be attained by applying the disclosed invention in a different manner or modifying the invention as will be described. Accordingly, other objects and a fuller understanding of the invention may be had by referring to the followi
Follansbee John
Kinslow Cathrine K.
LaBaw Jeffrey S.
Truong Lechi
Yee Duke W.
LandOfFree
Method and system for dynamically load balancing a process... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for dynamically load balancing a process..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for dynamically load balancing a process... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211565