Patent Publication Number: US-6711607-B1

Title: Dynamic scheduling of task streams in a multiple-resource system to ensure task stream quality of service

Description:
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&#39;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&#39;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&#39;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&#39;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&#39;s resource does not exceed 100% of the resource&#39;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. This helps further ensure that the quality of service requirements are met for those task streams having blocked tasks, without sacrificing the quality of service provided to the task streams of transferred tasks (which suffer no loss in quality of service by being transferred or transferred back). 
     One embodiment of the present invention employs a quality of service manager, an arbitrator, and a number of servers, each of which manages a resource. The quality of service manager is responsible for setting quality of service requirements for individual task streams, and storing this assignment information. The quality of service manager receives incoming tasks, and determines from their process ID, task ID, packet ID, or other data which task streams they are respectively associated with, and hence what quality of service requirement is associated with each task. 
     When a new task is received by the quality of service manager, it queries the arbitrator to determine if there is sufficient resource capacity to meet the quality of service requirements for the task stream associated with the task. The arbitrator maintains a master quality of service table that identifies each server, the task streams originally assigned to each server, and each server&#39;s current total quality of service commitments to the task streams assigned to it. The arbitrator also stores a current assignment table that indicates which tasks are currently assigned to each server; this table is updated anytime a task is transferred from one server to another. 
     If the task stream cannot be allocated to one of the servers without the total quality of service commitment of that server exceeding the total resource capacity of the resource managed by the server, then the task is denied. Otherwise, the arbitrator provides the quality of service manager with the ID of the server to which the task stream is assigned. The arbitrator updates the master quality of service table to show the assignment of the task stream to the server, and that server&#39;s new total quality of service commitment. Each server also maintains its own quality of service table that records the task D and quality of service requirement for its task streams. 
     In one embodiment, each server maintains its tasks in a task stream queue, which may include a runnable task queue and a blocked tasked queue. Tasks are initially assigned to the runnable task queue, but when a task blocks, the server moves the task to the blocked queue. When a server detects there are no entries in its runnable queue (it is idle), it informs the arbitrator. The arbitrator selects a runnable task from another server&#39;s runnable queue and moves it to the runnable queue of the idle, first server. The arbitrator also updates the current assignment table to indicate the current assignment of the task to the first server. If a task becomes unblocked on the first server, the first server preempts the transferred task, and informs the arbitrator. The arbitrator determines from the master quality of service table the original server from which the task was transferred, and moves the task back to this originating server from the first server. 
    
    
     These and other features and attributes of the present invention are now described in more detail with reference to the following figures. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a software architecture of a system in accordance with the present invention. 
     FIG. 2 is a flowgraph of the operation of one embodiment of the present invention. 
     FIGS. 3 a - 3   b  are tables illustrating the transfer of tasks between servers. FIGS. 3 a - 3   c  are tables illustrating the transfer of tasks between servers. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Referring now to FIG. 1, there is shown the software architecture of a system in accordance with one embodiment of the present invention. A task mechanism  116  processes task requests into the system. These task requests may be for any type of processing or data manipulation task that can be handled by the various servers  102  or resources  118  of the system. Typical tasks include, but are not limited to, transmitting packets to, or decoding packets received from, a network source; executing software processes; reading or writing data files; accessing or storing records in a database, and so forth. 
     The task mechanism  116  provides its task requests to the quality of service manager  100 , each task request including some form of identifying or distinguishing data, such as a task ID, file type, process ID, packet ID, source or destination address, protocol, or the like, that may be used to associate the task with a task stream. The manner in which tasks are generated by the task mechanism  116  will vary, and thus so will the particular data or attributes used to identify task streams. For example, one species of tasks are processes to be executed by a processor. How processes are generated varies by operating system; for example, in UNIX®, processes are generated by a fork system call, which would serve as the task mechanism  116  for one embodiment. Another species of tasks are packets to be transferred to a network via a network interface card, and the task mechanism  116  is any process that generates the packets. 
     The quality of service manager  100  is responsible for establishing and maintaining quality of service guarantees for task streams. The quality of service manager  100  uses a quality of service assignment table  120  that stores for each task stream information identifying each task stream (e.g., a task stream ID) and a predefined quality of service for the task stream. If need be, the quality of service manager  100  may further store data associating particular information from the tasks (e.g., task ID, packet ID, or process ID) with the information identifying the task streams. 
     There are various ways to determine the relationship between a task and a task stream. In one embodiment, where tasks are processes to be executed, the task stream of a new process may be the task stream defined for the parent process. Alternatively, a privileged (e.g., root administrator accessible only) program may be used to define an explicit mapping between each process and task stream. In the case of packets, the task stream assignment may be based on a mapping function between packet header attributes and task streams. Any of the packet header attributes may be used for this mapping, for example, the IP address, the L 2  address, or protocol type. For example, a mapping may be defined between particular IP addresses and task streams, with a set of one or more IP addresses being associated with a particular task stream (many-to-one mapping). This mapping feature enables specific client computers, having specific IP addresses, to each be given a particular QOS guarantee for all of its tasks (which form a task stream). In this way, the owner of each computer may be charged a service fee that is related to the QOS provided to its computer. The quality of service guaranteed to a task stream may be established by the system administrator according to any desired protocol or manner. In one embodiment, the quality of service for a task stream is specified in terms of percentage of a resource&#39;s availability. 
     The quality of service manager  100  communicates with an arbitrator  110  to request processing of a task with the quality of service defined for its task stream The arbitrator  110  is responsible for assigning a task stream (and thus initially all of its tasks) to whichever server (if any) has sufficient resource availability to provide the quality of service specified for the task stream. 
     In one embodiment, the arbitrator  110  manages this function by maintaining a master quality of service table  112  and a current assignment table  114 . The master quality of service table  112  lists each server  102 , the task streams assigned to the server  102  along with each task stream&#39;s quality of service requirement, and the current total quality of service requirement at each server  102 . The current assignment table  114  lists tasks that have been assigned to each server—including transferred tasks—and the server  102  from which a task was transferred (if any). 
     The arbitrator  110  is coupled to a number of servers  102  (shown in FIG. 1 as servers  1  to N). Each server  102  is responsible for managing a resource  118 , which provides any type of service to tasks, such as a disk drive providing disk access, or a network interface card providing network access, a processor for executing processes, a printer, and so forth. In one embodiment, each server  102  maintains a task stream queue  105 , which may be implemented in turn using a runnable task queue  104  and a blocked task queue  106 . 
     The runnable task queue  104  for each server  102  lists tasks assigned to the server  102  that are runnable and awaiting execution. The blocked task queue  106  lists tasks that are blocked from execution for whatever reason, such as awaiting further user or system data, unavailability of a resource, or the like. These queues need not be physically separate: a single queue of tasks may be used by including a flag with each task indicating its status as runnable or blocked. A task is initially assigned to the runnable task queue  104 , and is moved by the server  102  into the blocked task queue  106  when the task blocks. When the task unblocks the server  102  moves the task to the runnable task queue  104 . 
     Each server  102  also maintains a quality of service table  108  that lists each of the tasks assigned to the server  102 , its associated task stream, and its associated quality of service requirement. The total value of the quality of service requirements for all assigned task streams is preferably always equal to or less than the total resource availability of the server&#39;s resource  118 . 
     The various elements of this software architecture may be executed on various types of conventional computer hardware. A typical embodiment will include a server-type computer, preferably having multiple processors, one or more network interface cards for communicating with other computers, storage devices such as large capacity disk arrays, and addressable memory for executing an operating system (e.g., UNIX, LINUX, Windows NT), the quality of service manager  100 , arbitrator, and various servers  102 . 
     Referring now to FIG. 2 there is a shown a detailed flowgraph of the overall process of scheduling tasks in accordance with the present invention, The operation of the present invention may be understood from the vantage point of when a task is received into the system. Accordingly, the quality of service manager  100  receives  200  a task request from a task mechanism  116  to process the task. 
     The quality of service manager  100  reads some data from the task request (e.g. a process ID, packet header attribute, etc.) and determines  202  from its quality of service assignment table  120  which task stream is associated with the task, and the corresponding quality of service that task stream is guaranteed. The quality of service manager  100  requests  204  the arbitrator  110  to assign  206  the task to a server  102 , given the quality of service requirement for the task stream, and the task stream to which the task is assigned. 
     The arbitrator  110  determines from the master quality of service table  112  whether the task stream associated with the task has been previously assigned to a server or if the task stream is a new task stream. If the task stream has been previously assigned to a server, then the task is assigned  206  to this particular server  102 . The arbitrator  110  updates the master quality of service table  112  to indicate that the task stream has been assigned to the particular server  102 , and its quality of service requirement. The current assignment table  114  is also updated to show the initial assignment of a task to the server, with the assigned server indicated as both the originating and current server. The task is placed in the runnable task queue  104  of the server to which it is assigned. The task streams in the queues of the individual servers may be scheduled using any conventional uni-processor scheduling algorithm. 
     If the task stream has not been previously assigned to a server, the arbitrator assigns  206  the task stream and the task to one of the server, selecting the server so that the resulting total quality of service commitment for all of the task streams assigned to the server is less than the total available resource capacity. The arbitrator  110  updates the quality of service table  112  to reflect the new assignment and total quality of service commitment; likewise, the server updates its own quality of service table  108 . The arbitrator  110  also updates the current assignment table  114  to indicate the assignment of the task to the server, listing the assigned server as the originating server and as the current server. 
     If necessary to allow assignment of the new task stream, the arbitrator  110  partitions  208  all of the current task streams amongst the server  102 . In so partitioning the task streams, the arbitrator again assigns (or re-assigns as need be) the task streams to the various servers  102  so as to ensure that the total quality of service requirements for all task assigned to each server (considering both the runnable and blocked queues  104 ,  106 ) does not exceed the total available resource associated with each server. The partitioning algorithm may be based, for example, on a first fit, or other allocation method. 
     For example, assume there are three servers, Server  1 , Server  2 , and Server  3 , with the following current total quality of service commitments from their assigned task streams (here expressed in terms of percentage of total), in an example master quality of service table  112 . 
     
       
         
           
               
            
               
                   
               
               
                 Master Quality of Service Table 112 
               
            
           
           
               
               
               
               
            
               
                   
                   
                 Total 
                   
               
               
                   
                 Server 
                 QOS 
                 Assigned Task Stream (QOS Requirement) 
               
               
                   
                   
               
               
                   
                 Server 1 
                 60% 
                 TS1 (25%), TS2 (20%), TS5 (15%) 
               
               
                   
                 Server 2 
                 90% 
                 TS3 (40%), TS4 (50%) 
               
               
                   
                 Server 3 
                 55% 
                 TS6 (55%) 
               
               
                   
                   
               
            
           
         
       
     
     Further, assume a new task for existing task stream TS 1  is received by the quality of service manager  100 . The quality of service manager  100  requests the arbitrator  110  to assign the task to an appropriate server. In this example, task stream T 1  has already been assigned to Server  1 , and so the arbitrator assigns the task to this server. The current assignment table  114  is also updated to show the assignment of the new task to Server  1 , with Server  1  being both the originating and current server. 
     Assume now that a new task for a new task stream TS 7  is requested, and that task stream TS 7  has a quality of service guarantee of 25%. Using a first fit algorithm, the arbitrator  110  may assign task stream TS 7  to Server  1 , since the resulting total quality of service commitment would only be 85%. Server  2  cannot be assigned the task stream, since at 115% the total quality of service requirement would exceed the total resource availability. Using a best fit algorithm, arbitrator  110  may assign the task stream to Server  3 , since this server has the most available capacity. 
     Finally, assume that TS 7  instead had a quality of service requirement of 60%. In this case, the arbitrator  110  may repartition  208  the task streams amongst the various servers, for example as follows: 
     
       
         
           
               
            
               
                   
               
               
                 Master Quality of Service Table 112 
               
            
           
           
               
               
               
               
            
               
                   
                   
                 Total 
                   
               
               
                   
                 Server 
                 QOS 
                 Assigned Task Stream (QOS Requirement) 
               
               
                   
                   
               
            
           
           
               
               
               
               
            
               
                   
                 Server 1 
                 100% 
                 TS1 (25%), TS2 (20%), TS5 (55%) 
               
               
                   
                 Server 2 
                 90% 
                 TS3 (40%), TS4 (50%) 
               
               
                   
                 Server 3 
                 75% 
                 TS6 (15%), TS7 (60%) 
               
               
                   
                   
               
            
           
         
       
     
     This repartitioning allows task stream TS 7  to be assigned to Server  3 , instead of being rejected. 
     However, if another new task stream TS 8  is now requested with a quality of service requirement of 60% it will be rejected, since no repartitioning  208  will allow this task stream to be assigned to any server without exceeding that server&#39;s total availability. 
     as each of the servers  102  process the task streams in their respective runnable task queues  104 , various tasks in these runnable task queues will block; the server  102  then moves (or updates) the task to its blocked task queue  106 . At some point, one of the servers  102  may have all of its tasks blocked, with all of its tasks moved to its blocked task queue  106 . The server  102  then notifies the arbitrator  110  of its status as now being ‘idle.’ A server may also notify the arbitrator that it is idle when all tasks in its queues have been executed. 
     When the arbitrator  110  receives notice that a server is idle, it identifies in the current assignment table  114  at least one runnable task that is assigned to another ‘busy’ server, that is a server that has at least one task in its runnable task queue  104  (this server is also called herein an ‘originating’ server). The arbitrator  110  transfers  210  this runnable task(s) from the busy server to the idle server. The arbitrator  110  further updates the current assignment table  114  to indicate the transfer, with the idle server now as the currently assigned server. The selection of which task to transfer may be based on various selection criteria, such as selecting the highest priority task, the task from the longest runnable task queue  104 , the task resulting in the least amount of cache misses, and so on. 
     At some point, an idle server may have one or more of its tasks unblock while executing a transferred task. If so, the idle server pre-empts the transferred task, and informs the arbitrator  110 . The server also begins processing of the unblocked task. 
     The arbitrator then determines from the current assignment table  114  which task(s), if any, have been transferred to the idle server. The arbitrator may determine which tasks have been transferred since the originating server and the current server will be different. Altematively, the arbitrator may set a flag set to indicate a transferred task, and then check for these flags. The arbitrator re-transfers such task(s) back to its originating server. This ensures that the task that unblocked on the idle server receives its quality of service commitment, while at the same time not degrading the quality of service provided to the transferred task(s). 
     Referring now to FIGS. 3 a - 3   c , there is shown an example of these steps of managing transferred tasks. In the figures, there are shown two servers, Server  1  and Server  2 , and their respective runnable task queues  104  and blocked task queues  106 . Tasks T 1  and T 2  are initially assigned to Server  1  and tasks T 3  and T 4  are initially assigned to Server  2 . The tasks are in the respective runnable task queues  104  and awaiting service or being serviced by the server&#39;s resources  118 . The current assignment table  1   14  shows each server as both the originating and current server. 
     In FIG. 3 a , both task streams T 1  and T 2  on Server  1  have blocked, and Server  1  is now idle. Server  1  notifies the arbitrator  110  of this state, aid the arbitrator selects a runnable task stream, such as T 4  from Server  2  to transfer to Server  1 . Since now another task stream is present, Server  1  can begin immediate servicing of task T 4 . The arbitrator also updates the current assignment table  114  to show that task stream T 4  has been transferred from Server  2  to Server  1 . See FIG. 3 b . The arbitrator  110  may use any selection algorithm or criteria to determine which runnable task stream(s) to transfer. For example, the arbitrator may select the task stream having the highest quality of service requirement, or it may select the last task in the longest task queue for any of the servers. 
     In FIG. 3 c , task T 1  has unblocked and Server  1  has moved the task back to its runnable task queue  104 . Server  1  preempts task stream T 4 , and notifies the arbitrator  11   0 . The arbitrator determines from the current assignment table  114  of FIG. 3 b  which tasks have been transferred to Server  1 , and here identifies T 4 . It further determines that Server  2  was the originating server. Accordingly, the arbitrator re-transfers task T 4  back to Server  2 . In some instances a transferred task may not be pre-emptible (e.g., a packet being transmitted to the network), in which case the task is not pre-empted, and not transferred back to its originating server. 
     In summary, the present invention provides a software architecture and method that ensures quality of service guarantees for task streams in multi-resource/server environments. The method may be encoded in a software product, including executable code portions that define the functional and structural features of the quality of service manager, the arbitrator, and various tables, and the behavior of the servers. 
     The foregoing describes in detail the features and benefits of the present invention in various embodiments. Those of skill in the art will appreciate that the present invention is capable of various other implementations that operate in accordance with the foregoing principles and teachings. For example, the arrangement and organization of the various task queues, and the various tables used to track the status of task streams and their quality of service requirements may be altered and managed by different elements. The tables may store different data, and may differ in number or relationship to each other. The functionality of partitioning the task streams to the servers, and transferring task streams between servers may be held in multiple different entities instead of by the arbitrator or its equivalent. Certainly, the names of the various entities may be changed without impacting their functional operations. Accordingly, this detailed description is not intended to limit the scope of the present invention, which is to be understood by reference to the claims below.