Electrical computers and digital processing systems: multicomput – Distributed data processing – Client/server
Reexamination Certificate
2000-02-04
2004-03-23
Dinh, Dung C. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Distributed data processing
Client/server
C709S226000, C709S241000
Reexamination Certificate
active
06711607
ABSTRACT:
BACKGROUND
1. Field of Invention
The present invention relates generally to scheduling resources on computer systems, and more particularly, to systems and methods for scheduling resources on multiple servers.
2. Background of the Invention Scheduling the execution of processes and the use of resources in a computer is a fundamental part of operating system design. In conventional computer operating systems, there are various system resources available to processes, such as the processor itself, disk drives, memory, network connections, and so forth. An operating system includes a scheduler that schedules individual processes for execution, and further that allocates resources to various ones of the processes. The scheduler may operate in conjunction with a quality of service manager that provides quality of service (QOS) guarantees to individual processes or tasks. A quality of service guarantee typically ensures that a given process will have a certain percent share of some resource's availability. For example, a process may be given a 30% QOS guarantee for the processor, meaning that it will receive at least 30% of the available processor cycles (or some other metric of processor availability). Research in scheduling algorithms has addressed scheduling on both single processor and multi-processor systems. However, conventional scheduling algorithms typically address scheduling efficiency when considering processes individually.
In many instances, it may be necessary to schedule otherwise distinct processes in a coordinated fashion. More particularly, distinct processes may be related to a particular entity for which it is desired to provide quality of service guarantees for all of the entity's processes.
For example, consider a server computer providing services, such as file transfers, database queries, packet routing, to a number of client computers. Each client computer communicates with the server computer more or less concurrently, each providing an ongoing stream of requests and data in the form of packets that need to be processed by the server. Normally, each individual request of a client would be processed by the server as an individual process, and scheduled accordingly. However, it may be desirable to provide quality of service guarantees with respect to each of the client computers, and not merely with respect to individual processes. This would be desirable to ensure that each client obtains a particular quality of service from the server computer. In particular, this is desirable in order to differentially price the level of service provided to different clients based upon the quality of service they are guaranteed. In this fashion, client computers who are guaranteed a higher quality of service pay a premium price. For example, a company paying for a high QOS guarantee could receive higher priority processing for all of its database queries, even though each individual query is a separate process. Conventionally, providing differential quality of service and pricing to different client computers has required that separate server computers be provided for each client computer. This approach is costly, and thus makes it further desirable to handle multiple clients using a multi-processor system or the like.
A task stream is a set of tasks or process that are all issued on behalf of the same entity and that all share a common resource allocation or quality of service requirement. Examples of task streams are flows of packets that share a resource allocation, and sets of processes that jointly share a machine's resources such as CPU, memory, or disk bandwidth. For example, a task stream may be a flow of packets, where all the packets for a particular client request constitute a task stream.
Several task streams may want to use a single resource at the same time. In this case, the task streams are placed in a queue of task streams, awaiting their individual turns. It is commonly desired to provide a task stream with a guaranteed allocation of a system resource. For instance, it may be desired to guarantee that all ‘high-priority’ processes receive at least 10% of a machine's CPU.
Algorithms to schedule a queue of task streams on a single processor to give each task stream a guaranteed share of processor resources are well known in the art. With multiprocessor systems becoming widespread, it is now feasible to process a queue of task streams using. multiple servers in parallel. However, known single processor scheduling algorithms do not extend to the multiprocessor case.
Accordingly, it is desirable to provide a scheduling system and methodology that guarantees a quality of service to various task streams being served by multiple processors (or other resources) in parallel.
SUMMARY OF THE INVENTION
The present invention overcomes the limitations of conventional scheduling algorithms by providing and enforcing quality of service guarantees to individual task streams being served by multiple, parallel resources. One embodiment operates in a computer system having a number of servers. A server may be a physical processor, or a server process executing on a processor. Each server managed or controls some system resource, such as CPU, memory, disk, network interface card, and the like. In either case, multiple servers ate available to handle tasks that are being received for processing.
Each task is associated with a particular task stream preferably by some form of task stream identification number, process ID, packet attribute, or the like. As noted above, a task stream may be associated with a an entity, such as a particular client computer or application which generates or is related to otherwise independent tasks or processes having a common quality of service requirement. Each task stream has a previously determined quality of service requirement that it will receive for all of its tasks. For example, a task stream may have a 30% quality of service requirement, so that it receives 30% of the available capacity of system resources, such as CPU time. Each task stream may have a different quality of service requirement.
As a task is received into the system, the task stream with which it is associated is determined. Periodically, the task streams are partitioned or allocated among the various servers. The allocation of task streams to each server is done so that the total quality of service requirements of the task streams assigned to each server does not exceed the total availability of the resource that each server manages. For example, the allocation is preferably such that the total quality of service requirements for each server's resource does not exceed 100% of the resource's availability. The allocation of task streams to servers may be made by any type of allocation algorithm, such as first fit or best fit, or the like.
Each server executes its task streams according to some scheduling order, which may be determined by any uniprocessor scheduling algorithm. Individual tasks may be either runnable or waiting (blocked). If all of the tasks for one of the servers are waiting, then the server is idle. A runnable task from one of the other (busy) servers with runnable tasks is moved from a busy server to the idle server, where it can be immediately processed. The selection of which task and from which server may be made according to various criteria, allowing for optimization. This feature of moving runnable tasks from busy servers to idle servers is desirable because it helps ensure that each task will receive the quality of service guarantee defined for its associated task stream.
Preferably, if a waiting task on the previously idle server becomes runnable, then the task that was moved to this server is moved back to its originating server. The newly runnable task is executed, as it would have been before blocking. The re-transfer of runnable tasks back to their originating servers is desirable because it prevents tasks that are blocked temporarily from being repeatedly delayed by other tasks that are taken up by the server. Thi
Dinh Dung C.
Ensim Corporation
Fenwick & West LLP
LandOfFree
Dynamic scheduling of task streams in a multiple-resource... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic scheduling of task streams in a multiple-resource..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic scheduling of task streams in a multiple-resource... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3186297