Efficient assignment of processing resources in a fair queuing system

[0001] This invention relates to controlling of multi-processing servers, and more particularly, efficient assignment of processing resources to queued requests in or for a fair queuing system.

BACKGROUND OF THE INVENTION

[0002] There exist multi-processing server systems which are capable of serving many requests in parallel fashion. Requests may also be called tasks, jobs, loads, messages or consumers. A typical existing system uses multi-processing servers, all of which are capable of serving any type of request that is submitted to the system. Requests are processed by available servers as they are received by the system. When all servers become busy serving other requests, any new requests received by the system cannot be served as received. The system needs to handle those new outstanding requests. It is desirable to assign multi-processing servers and other processing resources in the system to those outstanding requests in a fair manner.

[0003] Some existing systems attempt to solve this problem by rejecting new requests when all servers are busy. Rejecting new requests is unfair because requests submitted later can be processed before rejected ones submitted earlier.

[0004] Some existing systems attempt to provide fair assignment by queuing outstanding requests in the order of receipt while they are waiting to be served. A typical existing system provides a single queue for all outstanding requests, regardless of how many servers are available. In this system, when a server becomes available, a request at the head of the queue is simply dispatched to that server.

[0005] Queuing outstanding requests is fairer compared to rejection of them. However, when there are high priority requests and low priority requests, these conventional systems often allow high priority requests to completely block low priority requests, or even the reverse. This common phenomenon is called “starvation”. Some systems avoid the starvation problems by designing the system to handle requests in a fixed way, appropriate for a specific application and hardware configuration. This technique cannot be applied to other situations without a re-design.

[0006] Some systems work around the starvation problems by giving the administrator a high degree of instantaneous control over assignment of processing resources to requests. Such systems have a very high administrative cost to keep running well.

[0007] It is therefore desirable to provide a system which is capable of automatically assigning processing resources effectively and fairly to requests that exceed the system's capacity for concurrent processing.

SUMMARY OF THE INVENTION

[0008] In computers, requests are served by running process instances of server programs. Each such process instance may serve more than one request concurrently, if the server program is multi-threaded. For the purpose of this invention, each such process of single-threaded programs or thread of multi-threaded programs is called a server instance. Each request has request parameters that determine the cost of preparing a server instance to serve the request, e.g., starting a particular program, opening files, connecting to particular external resources. In the present invention, those request parameters are identified and used collectively to define a service type.

[0009] The present invention enables configuration of server instances to serve requests of a different service type based on demand.

[0010] In accordance with an aspect of the present invention, there is provided a method for dispatching requests to processing resources. The method comprises steps of determining if a processing resource is idle, the processing resource having a current service type to process requests that have the current service type; determining if the processing resource is to be switched to a different service type to process requests having the different service type when the processing resource is idle; switching the processing resource to the different service type when the switching is determined; and dispatching an outstanding request having the different service type to the processing resource.

[0011] In accordance with another aspect of the invention, there is provided a method for dispatching queued requests to a predetermined number of server instances. The method comprises steps of determining if a server instance is idle, the server instance having a current service type to process requests that have the current service type; determining if the server instance is to be switched to a different service type to process requests having the different service type when the server instance is idle; switching the server instance to the different service type when the switching is determined; and dispatching a queued request having the different service type to the server instance.

[0012] In accordance with another aspect of the invention, there is provided a method for dispatching queued requests to a predetermined number of server instances. The method comprises steps of using a plurality of queues for queuing requests, each request having a service type, a service type being defined by a primary request parameter and one or more secondary request parameters, and each queue being used for queuing requests having a same primary request parameter; reserving a minimum number of server instance slots for each queue, each server instance slot representing a potential server instance, each server instance having a current service type; allocating one or more non-reserved server instance slots for one or more queues when the total number of server instances is larger than the sum of minimum numbers of reserved server instance slots for queues being used; reallocating a non-reserved server instance slot to a different queue when the non-reserved server instance slot is free; and dispatching a queued request from a queue to an idle server instance in a server instance slot allocated for the queue.

[0013] In accordance with another aspect of the invention, there is provided a request dispatching system for dispatching requests to processing resources. The request dispatching system comprises a processing resource controller having a switch controller for controlling switching of an idle processing resource having a current service type to a different service type; and a dispatching controller for dispatching an outstanding request having the different service type to the processing resource.

[0014] In accordance with another aspect of the invention, there is provided a request dispatching system for dispatching queued requests to a predetermined number of server instances. The request dispatching system comprises a server instance controller having a switch controller for controlling switching of an idle server instance having a current service type to a different service type; and a dispatching controller for dispatching an outstanding request having the different service type to the server instance..

[0015] Other aspects and features of the present invention will be readily apparent to those skilled in the art from a review of the following detailed description of preferred embodiments in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] The invention will be further understood from the following description with reference to the drawings in which:

[0017]FIG. 1 is a block diagram showing a system having a request dispatching system in accordance with an embodiment of the present invention;

[0018]FIG. 2 is a block diagram showing an example of the request dispatching system;

[0019]FIG. 2A is a diagram showing an example of a dispatching controller and a server process controller;

[0020]FIG. 3 is a flowchart showing an example process of configuration of server instances;

[0021]FIG. 4 is a flowchart showing an example process of selecting a queue;

[0022]FIG. 5 is a flowchart showing another example process of selecting a queue; and

[0023]FIG. 6 is a diagram showing an example system with two queues.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0024] Referring to FIGS. 1 and 2, a request dispatching system <b>10</b> in accordance with an embodiment of the present invention is described. The request dispatching system <b>10</b> is provided in a computer system <b>14</b> to handle requests <b>18</b> received from one or more clients <b>12</b>. The system <b>10</b> uses one or more queues <b>22</b>, a dispatching controller <b>24</b> and a server instance controller <b>26</b>.

[0025] The computer system <b>14</b> serves requests by running server instances. FIG. 2 schematically shows multiple server instances <b>30</b>. Potential server instances are schematically shown as server instance slots <b>28</b>.

[0026] Requests <b>18</b> from clients <b>12</b> are queued in the queues <b>22</b> using a suitable queuing controller (not shown). The request dispatching system <b>10</b> dequeues requests and dispatches them to server instances <b>30</b>. The dispatching controller <b>24</b> controls dispatching of requests from the queues <b>22</b> to server instances <b>30</b>. The server instance controller <b>26</b> controls server instances <b>30</b>, e.g., creation, allocation, preparation and/or activation/deactivation of server instances <b>30</b>, as further described below.

[0027] The dispatching system <b>10</b> allows multiple requests to be processed in parallel by the multiple server instances <b>30</b>. In this embodiment, a server instance <b>30</b> may represent a single-processing processor, a thread of a multiple-processing processor or any combination thereof. There may be one or more processors used in the system <b>10</b>. In the case where the server instances <b>30</b> include multiple single-processing processors, each processor is configurable to serve different types of requests.

[0028] In order to process requests, the server instances <b>30</b> can use a finite number of processing resources <b>15</b> within the computer system <b>14</b>. The resources <b>15</b> provided internally in the server unit <b>14</b> may include one or more Central Processing Units (CPUs), physical memory and virtual memory swap space. The resources <b>15</b> are allocated to server instances by the host operating system according to its allocation policies. These policies can be influenced by parameters that are specified by the request dispatching system <b>10</b>. One such parameter is execution priority.

[0029] The physical memory available for application use (AM) is a configurable system parameter. It is not the total physical memory on the computer, but what is left after the system is up and running, with all applications loaded but idle. The amount of additional memory consumed by processing a request (RM) is also a configurable parameter.

[0030] Swap space is virtual memory (VM) disk space for handling swapping of server instances to and from physical memory. The virtual memory VM is also a configurable system parameter.

[0031] Server instances may also use one or more external resources <b>16</b>, such as external servers, through external server connections.

[0032] It is desirable that processing resources are not only fairly allocated to requests, but also do not remain unused while there is a request available to which those resources can be applied.

[0033] The most precious processing resource <b>15</b> is usually CPUs. Accordingly, the dispatching system <b>10</b> in this embodiment minimizes the number of idle CPUs as long as there is a request to be served. However, the present invention may also be applied to other processing or related resources.

[0034] Each request has a service type. A service type is a collection of request parameters that determine the cost of preparing a server instance to serve the request. Preparation costs may be expressed in terms of real-time and other resources consumed by or reserved for the server instance. The commonly used service type of requests is defined by request priority alone. There are however situations where it is desirable to use two or more request parameters for controlling dispatching of requests. Among those request parameters defining the service type, there may be a primary parameter and one or more secondary parameters. In this embodiment, the service type is defined by request priority as a primary parameter and one or more secondary parameters. The invention may be used for different request parameters.

[0035] The service type of a request may be described using a set of attributes. Generic attributes may include interactive attributes, interactive or asynchronous attributes, and application-specific attributes. Additional generic attributes may be considered as balancing factors for balancing or distributing the processing activity among service instances <b>30</b>. Such additional generic attributes may include those representing priority, age, preparation costs and execution cost. Other attributes may include averages of above factors, number of queued items of specified types, total number of queued items, number of idle server instances and/or CPU utilization.

[0036] Server instances <b>30</b> are not permanently reserved by service type. That is, an idle server instance <b>30</b> having a service type may be reconfigured or switched to a different service type. Switching of server instances <b>30</b> is controlled by the server instance controller <b>26</b> of the request dispatching system <b>10</b>. The preparation costs for switching a server instance <b>30</b> to process a request that has the same primary parameter but different secondary parameters is relatively small, compared to the costs needed to switch the server instance <b>30</b> to process a request that has a different primary parameter. Accordingly, requests having same or similar service type, i.e., those having the same primary parameter, can be queued together.

[0037] Each queue <b>22</b> is used for queuing requests which have the same or similar service type. For example, each queue <b>22</b> may be used for queuing requests having the same primary parameter. Secondary parameters of requests queued in a queue <b>22</b> may not be the same.

[0038] In order to eliminate the starvation problems, the request dispatching system <b>10</b> reserves a minimum number NSPi of server instances <b>30</b> for each queue <b>22</b>. This reservation is shown in FIG. 2 as reserved slots <b>36</b>. The minimum number NSPi is configurable for each queue <b>22</b> and may be one or more. The minimum number NSPi of server instance slots <b>28</b> is reserved regardless of whether or not there are requests outstanding for the same or similar service type having the same primary parameter. By reserving the minimum number NSPi of server instance slots <b>36</b> for each queue <b>22</b>, the request dispatching system <b>10</b> can always allocate at least one server instance <b>30</b> to requests of each service type having a primary parameter. Thus, requests of one primary parameter are not blocked solely by requests of other primary parameter.

[0039] When the total number NS of active server instances <b>30</b> is larger than the sum of the minimum number NSPi of server instance slots <b>36</b> reserved for each queue <b>22</b>, one or more additional server instance slots may be provided to one or more queues <b>22</b> in addition to the NSPi server instance slots <b>36</b>. These additional server instance slots are shown in FIG. 2 as non-reserved slots <b>38</b>.

[0040] In order to assign processing resources fairly to requests while using available resources efficiently, the request dispatching system <b>10</b> dispatches each request to a server instance <b>30</b> based on a set of attributes that describe the service type of the request. As shown in FIG. 2A, the request dispatching system <b>10</b> may have a skip (controller <b>40</b> in the dispatching controller <b>24</b>, and a switch controller <b>50</b> and an allocation controller <b>60</b> in the server process controller <b>26</b>. Depending on the service type of outstanding requests and idle server instances <b>30</b>, the request dispatching system <b>10</b> may use the skip controller <b>40</b> to skip one or more older requests in a queue <b>22</b> and dispatch a newer request in the same queue <b>22</b> to an idle server instance <b>30</b>. The system <b>10</b> may use the switch controller <b>50</b> to switch the service type of an idle server instance <b>30</b> to a different service type having the same primary parameter to reuse it for a request having the different service type. Also, when a non-reserved slot <b>38</b> becomes free, the system <b>10</b> may use the allocation controller <b>60</b> to reallocate the non-reserved slot <b>38</b> to a different queue <b>22</b>, depending on demand. The system <b>10</b> may use only one of the skipping, switching and reallocation functions, or may use a combination of these functions. As shown in FIG. 2A, the switch controller <b>50</b> may have a request searcher <b>52</b> to search matching requests, a service type identifier <b>54</b> to identify the service type of outstanding requests, and a comparator <b>56</b> to evaluate switching costs of server instances. The allocation controller <b>60</b> may have a queue selector <b>62</b> to select queues for reallocation of non-reserved slots. These functions are further described below in detail.

[0041] When requests in a queue <b>22</b> have the same service type, i.e., both primary and secondary request parameters are equal among requests in the queue <b>22</b>, requests within the queue <b>22</b> are processed in the order in which they arrive. However, when requests within a queue <b>22</b> have different secondary parameters, it may not be efficient to process the requests in the order of their arrival. When a server instance <b>30</b> is prepared for a service type, the first request in the corresponding queue <b>22</b> may not have a service type that matches that of the server instance <b>30</b>. In that case, the request dispatching system <b>10</b> may allow skipping, i.e., dispatching of a request other than the first in the queue <b>22</b> if the other request has a matching service type.

[0042] Whenever a server instance <b>30</b> is idle and there are queued requests, then in some sense there are resources that are not being effectively used. However, an idle server instance <b>30</b> does not necessarily mean that one of the pending requests could be effectively serviced if dispatched immediately to the idle server instance <b>30</b>; it depends on what it would cost to prepare that server instance <b>30</b> for use with the request in question.

[0043] If all incoming requests are directed to idle server instances <b>30</b> with a matching service type, then preparation costs are minimized or avoided, and processing time is improved correspondingly. If there is no server instance having a matching service type to outstanding requests in a queue <b>22</b>, the request dispatching system <b>10</b> determines if it should switch the server instance <b>30</b> to a matching service type for one of the outstanding requests, depending on the preparation costs for the switching. For example, if it would cost 10 seconds to switch a first server instance <b>30</b> for the request at the head of the queue <b>22</b> and a second server instance <b>30</b> will likely become free in less than 10 seconds, and only takes 1 second to prepare the second server instance because it is a better service type match, then it is better to wait for that server instance to become free, rather than switching the first server instance <b>30</b>.

[0044]FIG. 3 shows an example of switching of an idle server instance <b>30</b>.

[0045] The server instance controller <b>26</b> starts or activates server instances <b>30</b> (<b>70</b>). Server instances <b>30</b> may be started as needed or at once. At this stage, server instances <b>30</b> are idle and wait for requests (<b>72</b>). The dispatching controller <b>24</b> checks if there is a request that has a service type matching to an idle server instance <b>30</b> (<b>74</b>). If there is one or more matching requests, the dispatching controller <b>24</b> dispatches the oldest request of the matching service type to the idle server instance <b>30</b> (<b>76</b>).

[0046] If there is no matching request (<b>74</b>), the server instance controller <b>26</b> determines whether it should switch the idle server instance <b>30</b> to a different service type having the same primary parameter for servicing a request in the queue (<b>78</b>). If the determination is affirmative, then the server instance controller <b>26</b> switches the service type of the idle server instance <b>30</b> to the different service type (<b>80</b>).

[0047] If the server instance controller <b>26</b> determines that the idle server instance <b>30</b> is not otherwise needed (<b>78</b>), it checks if the server instance <b>30</b> is idle for longer than a predetermined time period (<b>82</b>). If not, the server instance controller <b>26</b> lets the idle server instance <b>30</b> wait for a request with the matching service type (<b>72</b>).

[0048] If the server instance <b>30</b> is idle for longer than the predetermined time period (<b>82</b>), the server instance controller <b>26</b> terminates the idle server instance <b>30</b> (<b>86</b>).

[0049] If a very large number of service types and a large number of corresponding reserved server instances <b>30</b> are used in the request dispatching system <b>10</b>, it would be difficult to manage them. A service type could be maintained as an ordered list of parameters, from most significant to least significant, and idle server instances could be matched to the request with the best service type match. However, applying the best match unconditionally would violate the requirement that requests be served in the order received. Accordingly, such a best matching method would not provide fair services to all requests.

[0050] By switching the service type of an idle server instance <b>30</b> when the oldest request has been outstanding for longer than an estimated time to accomplish the switching, the request dispatching system <b>10</b> can maintain a reasonable approximation of the queue order. Thus, fair service can be achieved.

[0051] In order for the switching of idle server instances <b>30</b>, the minimum number NSPi is preferably set to (XB multiplied by NCPU). This setting allows to maximize state re-use of idle server instances <b>30</b>. NCPU is the number of CPUs on each server computer in the system <b>14</b>. XB is the number of active server instances per CPU, and it relates to connection to external resources <b>16</b>, as described below.

[0052] To minimize switching costs, the total number NS of server instances <b>30</b> is preferably set as high as possible, but not so high that the working set for all active server instances <b>30</b> exceeds the available physical memory. In order to avoid excessive swapping or swap space overflow, the total number NS of active server instances <b>30</b> is set no higher than AM divided by RM. AM is the amount of the available physical memory, and RM is the amount of additional physical memory consumed during processing of a request, as described above.

[0053] The number of external resource connections may be managed by the total number NS of server instances. There may be a need to do this if, for example, there are license limits to the number of external server connections. Closing the connection when the local server instance is idle is also possible, but then re-opening them must be managed as part of the preparation cost.

[0054] A server instance <b>30</b> that uses external resources <b>16</b> will be blocked some fraction B of its running life, waiting for these external resources <b>16</b>. In this embodiment, in order to ensure that this blockage does not result in an idle CPU, the number of active server instances per CPU is increased correspondingly, e.g. XB=/(1−B). For example, if local processes are blocked on external resources 50% of the time, 2 processes per local CPU are needed to keep all local CPU's busy. At 90% blocking, 10 processes per CPU are needed. Blocking factors substantially less than 50% are ignored.

[0055] In order to determine whether an idle server instance <b>30</b> should be switched to a different service type or wait to see if a matching request arrives at step <b>78</b> in FIG. 3, it is preferable to invoke a balancing algorithm.

[0056] The balancing algorithm may use a zero cost method, simple cost method or actual cost method.

[0057] In the zero cost method, the dispatching system <b>10</b> assumes that the cost of switching a server instance <b>30</b> to a different service type is zero. In this approach, there is no balancing across server instances <b>30</b>. This is the simplest balancing algorithm, and is the degenerate case.

[0058] In the simple cost method, a fixed estimate is used for the preparation cost for each service type. This method may be used for requests that already have estimated and/or average run costs. In this approach, an idle server instance <b>30</b> is switched when the request age exceeds the sum of the estimated preparation and run costs, expressed as real time.

[0059] In the actual cost method, actual preparation costs are measured, a running weighted average is computed for each service type, and the result is used as for the simple cost method.

[0060] If no balancing is indicated by the current queue contents, then the oldest request that is an exact type match for any available server instance <b>30</b> is dispatched to that server instance <b>30</b>, regardless of the primary parameter, e.g., priority, of the service type. Interactive/asynchronous attributes may be considered as they are part of the service type, and have reserved server instances.

[0061] The need for balancing is indicated when a request age exceeds a threshold computed from the balancing factors. If balancing is required, then the request that most exceeds the balancing factors is selected for dispatching, and a server instance <b>30</b> is allocated, by either starting a new server instance (provided the limit has not been reached), or switching an available server instance having a service type of the closest match.

[0062] Optionally, request dispatching system <b>10</b> records and maintains estimates of request preparation costs.

[0063] The reallocation function is now described referring to FIG. 4. The request distributing system <b>10</b> may reallocate free non-reserved slots <b>38</b> to a different queue <b>22</b> having more demand.

[0064] When a non-reserved slot <b>38</b> becomes free (<b>100</b>), the dispatching system <b>10</b> selects a queue <b>22</b> that has the fewest allocated server instance slots <b>28</b>, relative to the minimum number NSPi, i.e., the fewest allocated non-reserved slots <b>38</b> (<b>110</b>). For example, in an example having three priority queues, the minimum number NSPi may be set NSP <b>1</b>=1 for the low priority queue, NSP<b>2</b>=3 for the normal priority queue, and NSP<b>3</b>=4 for the high priority queue. If the numbers of server instance slots allocated to low, normal and high priority queues are three, three and five, respectively, then the low, normal and high priority queues have two, zero and one extra or non-reserved server instances, respectively, in addition to their minimum numbers NSPi of reserved server instances. Accordingly, the dispatching system <b>10</b> selects the normal priority queue.

[0065] In the case of a tie (<b>112</b>), the dispatching system <b>10</b> selects the highest priority queue among the ties (<b>114</b>). In the above example, if four server instance slots are allocated to the high priority queue, then the normal and high priority queues are tie. In this case, the dispatching system <b>10</b> selects the high priority queue.

[0066] Then, the dispatching system <b>10</b> allocates the non-reserved server instance slot <b>38</b> to the selected priority queue <b>22</b> (<b>116</b>).

[0067] Prior to allocating the non-reserved server instance slot <b>38</b> at step <b>116</b>, as shown in FIG. 5, the dispatching system <b>10</b> may check if there are any outstanding requests at the selected priority queue (<b>120</b>).

[0068] If there are no outstanding requests at that priority queue <b>22</b> (<b>120</b>), the dispatching system <b>10</b> further checks if there are at least the minimum number NSPi of server instances <b>30</b> running requests at that priority queue <b>22</b> (<b>122</b>). If yes, the dispatching system <b>10</b> selects the next priority queue <b>22</b> having the next fewest allocated server instance slots <b>28</b> (<b>124</b>) and returns to step <b>120</b>.

[0069] Thus, the minimum number NSPi of server instance slots <b>36</b> are always provided for each queue <b>22</b>. In other words, as long as NS is at least the total number NPQ of physical priority queues <b>22</b> in the dispatching system <b>10</b>, and as long as the minimum number NSPi is at least 1 for each priority queue <b>22</b>, then there is always at least one server instance slot <b>28</b> allocated to each priority, even if there are no outstanding requests at that priority. When a request arrives, it can always be dispatched immediately, unless there is already another request running at that priority.

[0070] If there is more than one queue <b>22</b> with free non-reserved server instance slots <b>38</b>, requests at the highest priority are dispatched first.

[0071] Notwithstanding the above, the request dispatching system <b>10</b> may elect to skip a request, and look for a better match with the available idle server instance(s) <b>30</b>. In this case, the request dispatching system <b>10</b> preferably manages the skipping such that the request is not skipped “indefinitely”. “Indefinitely” in this context means an amount of time that is long relative to the time required to satisfy the request.

[0072] When the primary parameter of the service type is priority, the system <b>10</b> may allow “borrowing” of server instances <b>30</b> by a queue having a higher priority.

[0073] Referring back to FIG. 5, if there are no outstanding requests at that priority queue <b>22</b> (<b>120</b>) and there are fewer than NSPi running requests at that priority (<b>122</b>), the dispatching system <b>10</b> may allow “borrowing” of the server instance <b>30</b> by a higher priority queue <b>22</b>. That is, the dispatching system <b>10</b> selects the next priority queue <b>22</b> that is higher priority than that of the current queue <b>22</b> (<b>126</b>), and returns to step <b>120</b>.

[0074] This allows a high-priority request to “borrow” server instance slots <b>28</b> from a lower priority queue <b>22</b>, if there are no pending requests at the lower priority. This respects priority, but still avoids starvation, as long as that higher priority requests take a lot less time to run than lower priority requests and will therefore block a request at the “right” priority for only a “short” time.

[0075] The balancing algorithm may determine suitability of the “borrowing” of server instances <b>30</b> so that the number of server instance slots <b>28</b> of a given priority queue <b>22</b> may temporarily fall below the minimum number NSPi. This approach increases the potential for starvation to occur, and is used only with due care and attention to that issue.

[0076] Example system with two queues

[0077]FIG. 6 shows an example system <b>100</b> with two queues <b>102</b> and <b>104</b>. The total number NPQ of physical queues is 2. Queue <b>102</b> is associated with high priority. The minimum number NSP<b>1</b> for queue <b>102</b> is set to 3. It currently has two requests R<b>1</b>-<b>6</b> and R<b>1</b>-<b>7</b> queued. Queue <b>104</b> is associated with normal priority. The minimum number NSP<b>1</b> for queue <b>104</b> is also set to 3. It is currently empty.

[0078] The total number NS of active service instances is set to 7. For queue <b>102</b>, currently three server instances SI <b>1</b> to SI <b>3</b> at reserved slots<b>1</b>-<b>1</b> to <b>1</b>-<b>3</b> (<b>106</b>) and an extra server instance S<b>17</b> (<b>110</b>) at non-reserved slots are processing requests R<b>1</b>-<b>1</b> to R<b>1</b>-<b>3</b> and R<b>1</b>-<b>4</b> (<b>105</b>). Server instance SI <b>8</b> is currently idle (<b>108</b>). Non-reserved slots are not shown in this drawing for the simplicity of illustration.

[0079] For queue <b>104</b>, three slots <b>2</b>-<b>1</b> to <b>2</b>-<b>3</b> are reserved. However, only slots <b>2</b>-<b>1</b> and <b>2</b>-<b>2</b> have slot instances SI <b>4</b> and SI <b>5</b> which are processing requests R<b>2</b>-<b>1</b> and R<b>2</b>-<b>2</b>. Since queue <b>104</b> is empty, server instance S<b>16</b> is borrowed by queue <b>102</b> (<b>112</b>) to process request R<b>1</b>-<b>5</b>. Thus, slot <b>2</b>-<b>3</b> is empty.

[0080] The server system of the present invention may be implemented by any hardware, software or a combination of hardware and software having the above described functions. The software code, either in its entirety or a part thereof, may be stored in a computer readable memory. Further, a computer data signal representing the software code which may be embedded in a carrier wave may be transmitted via a communication network. Such a computer readable memory and a computer data signal are also within the scope of the present invention, as well as the hardware, software and the combination thereof.

[0081] While particular embodiments of the present invention have been shown and described, changes and modifications may be made to such embodiments without departing from the true scope of the invention.