CN106528287B - Resource for computer system distribution method and device - Google Patents

Abstract

This application discloses the method and apparatus of resource for computer system distribution.The method utilizes the maximum resource quota of resource user, least resource quota and application Resources calculation obtain resource saturation data, resource user is sorted according to resource saturation degree and determines boundary resource user according to the condition of setting, according to the relationship of the resource saturation degree of the resource user of application resource and the resource saturation degree of boundary resource user, corresponding resource quota is distributed for it.It is high to solve existing resource distribution method distribution resource time complexity, the problem of being unable to satisfy the requirement calculated in real time, do not support least resource quota amount.

Description

Computer system resource allocation method and device

technical field

The present application relates to a system resource allocation method and device. In particular, the invention relates to a computer system resource allocation method and device.

Background technique

For a system with many resource users, the resource users of the system often need to apply to the system for the resources managed by the system. After receiving the resource user's request for resource application, the system will allocate a corresponding amount of resources for different resource users. Resource consumers use. Since the total amount of system resources is fixed, the resources available to each resource user must be limited. The weight of each resource user is different. At a certain moment, some resource users apply for a large amount of resources, and some resource users apply for a small amount of resources. The existing resource allocation algorithm will apply for a small amount of resources The available resource quota of resource users is evenly distributed to resource users who apply for a large amount of resources. Specifically, most of the existing resource quota calculations are the following schemes:

1. Allocate the total system resources in proportion to the maximum resource quota (MaxQuota) of each resource user, and obtain the static balance quota resource (ScaleQuota) of the resource user.

2. When the sum of resources requested by resource users (Request) is less than the total amount of system resources, the resource quota obtained by each resource user is the requested resource amount (Request) of the resource user, and the allocation process ends.

3. Divide resource users into two categories, category B: the amount of resources requested by resource users (Request) is less than the static balance quota resource (ScaleQuota) of resource users; category C: the amount of resources requested by resource users (Request) is greater than the resource usage Or statically balance quota resources (ScaleQuota).

4. For resource users of class B, the difference between the statically balanced quota resources (ScaleQuota) and the amount of resources requested by resource users (Request) can be allocated to resource users of class C; the accumulated sum of these differences is recorded as the available resource in the system The total amount of reallocated resources, denoted as

5. will Allocate to class C resource users in proportion to the resource user's maximum resource quota (MaxQuota), then the new available resource quota of class C resource users = static balance resource quota (ScaleQuota) + newly obtained resource quota, denoted as Ω.

6. If the Ω of the C-type resource user is greater than the resource user’s application resource amount (Request), the difference between Ω and the resource user’s application resource amount (Request) can also be allocated to the C-type resource user, and Ω is still smaller than the resource usage The resource user who applies for the amount of resources (Request), the algorithm jumps back to step 3 to iterate until the total amount of resources that can be allocated

It can be seen that the time complexity O of the existing resource quota calculation method in the worst case and the average case is the square (n ² ) of the number of resource users n, and when one only wants to know the resource allocation of a certain resource user When , the resource allocation of all resource users must be fully calculated. For a large system with many resource users, the existing computer system resource allocation methods cannot meet the requirements of real-time calculation. At the same time, the existing computer system resource allocation method cannot support the situation that the resource user configures the minimum resource quota.

application content

This application provides two computer system resource allocation methods to solve the problem that the existing resource allocation methods have high time complexity and cannot meet the requirements of real-time computing. In addition, the present application also provides two kinds of computer system resource allocation devices.

A method for allocating computer system resources provided by the present application includes the following steps:

Obtain the total amount of system resources and resource allocation-related data of resource users who have the right to make resource application requests, and the resource allocation-related data of resource users include the resource user's maximum resource quota and application resource amount;

calculating the resource saturation of the resource user by dividing the resource amount requested by the resource user by the maximum resource quota;

sorting the resource users based on the resource saturation of the resource users;

According to the ranking of resource users, a boundary resource user is determined by setting conditions, and resource users whose resource saturation is less than or equal to the boundary resource user are called B-type resource users; resource saturation is greater than the boundary A resource user of a resource user is called a class C resource user;

For B-type resource users, resources are allocated to them based on the amount of resources they apply for as their resource quota; for C-type resource users, the total amount of system resources is subtracted from all the resources allocated for B-type resource users as described , to obtain the amount of remaining resources; the amount of remaining resources, according to the ratio of the maximum resource quota of the C-type resource user to the sum of the maximum resource quotas of all C-type resource users, is used as its resource quota, and the above-mentioned The resource quota allocated resources to the C-type resource users.

Optionally, the setting condition is that the boundary resource user satisfies Inequality 1 and Inequality 2,

Inequality one:

Inequality two:

Among them, ToatalResource: the total amount of system resources; Request _i : if the resource saturation is less than or equal to the resource saturation of the border resource user, the i-th class B resource user among other class B resource users except the border resource user Application resource amount; MaxQuota _j : the maximum resource quota of the jth class C resource user whose resource saturation is greater than the resource saturation of the boundary resource user; Request _h : the application resource amount of the boundary resource user; MaxQuota _h : boundary The maximum resource quota of a resource user; Request _h+1 : Among the sorted resource users, the resource saturation is less than the resource saturation of any other C-type resource users, but greater than the resource saturation of the boundary resource users The amount of resources requested by a class C resource user; MaxQuota _h+1 : Among the resource users sorted, the resource saturation is less than that of any other class C resource user, but greater than the resource saturation of the boundary resource user The maximum resource quota of C-type resource users; m: the number of other B-type resource users except for boundary resource users whose resource saturation in the system is less than or equal to the resource saturation of boundary resource users; n : The number of C-type resource users whose resource saturation in the system is greater than that of the boundary resource users; ∑: summation operation.

Optionally, the method of determining a boundary resource user by setting conditions according to the sorting of resource users includes:

using one of the sorted resource users as a temporary boundary resource user;

Substitute the temporary boundary resource user into the above inequality 1 and inequality 2 as the boundary resource user, if both inequalities are true, then the temporary resource user is the boundary resource user; if the two inequalities cannot both be true, then all Another resource user among the sorted resource users is used as a temporary border resource user, and returns to the step of "substituting the data of the temporary border resource user into Inequality 1 and Inequality 2 as the data of the border resource user".

Optionally, the method for using another resource user among the sorted resource users as a temporary boundary resource user includes:

If inequality one is not established, select a resource user whose resource saturation is less than the resource saturation of the temporary boundary resource user among the sorted resource users, and use the resource user as the temporary boundary resource user;

If the second inequality is not established, select a resource user whose resource saturation is greater than that of the temporary border resource user among the sorted resource users, and use this resource user as the temporary border resource user.

Optionally,

The method for sorting the resource users based on the resource saturation of the resource users includes: forming a tree node based on resource allocation related data of the resource users, inserting and sorting the binary tree according to the resource saturation Store the data nodes of the resource user in or update the sorted binary tree, and maintain the binary tree as a sorted binary tree by adjusting the positions and relationships between the nodes of the sorted binary tree; the resource allocation related data of the resource user includes The resource saturation of resource users, the amount of requested resources and the maximum resource quota;

Correspondingly, the method for using one of the sorted resource users as a temporary border resource user includes: using the resource user stored in the root node of the sorted binary tree as a temporary border resource user ;

Correspondingly, the method for selecting a resource user whose resource saturation is less than the resource saturation of the temporary boundary resource user among the sorted resource users is as follows: select a resource saturation less than or Equal to the resource user corresponding to the direct child node on the resource saturation side of the temporary boundary resource user;

Correspondingly, the method for selecting a resource user whose resource saturation is greater than the resource saturation of the temporary boundary resource user among the sorted resource users is as follows: select a resource saturation greater than the temporary boundary in the sorted binary tree The resource user corresponding to the direct child node on the resource saturation side of the resource user.

Optionally, the data related to the resource allocation of the resource user further includes: the sum of the application resources of resource users whose resource saturation is less than or equal to the resource saturation of the resource user and the resource saturation of the resource user greater than the resource saturation of the resource user The sum of the maximum resource quotas of the resource users of resource saturation.

Optionally,

The method for sorting the resource users based on the resource saturation of the resource users includes: forming a tree node based on resource allocation related data of the resource users, inserting and sorting the binary tree according to the resource saturation Store the data nodes of the resource user in or update the sorted binary tree, and maintain the binary tree as a sorted binary tree by adjusting the positions and relationships between the nodes of the sorted binary tree; the resource allocation related data of the resource user includes The resource saturation of resource users, the amount of requested resources and the maximum amount of resource quota.

Optionally,

The data related to the resource allocation of the resource user further includes: the sum of the application resources of the resource users whose resource saturation is less than or equal to the resource saturation of the resource user and the resource saturation of the resource user whose resource saturation is greater than the resource saturation of the resource user The sum of the maximum resource quotas of resource users.

A method for allocating computer system resources provided by the present application includes the following steps:

Obtain the total amount of system resources and resource allocation-related data of resource users who have the right to request resource applications. The resource allocation-related data of resource users includes the resource user's minimum resource quota, maximum resource quota, and resource application ;

calculating the resource saturation of the resource user by dividing the difference between the resource user's application resource amount minus the minimum resource quota amount by the maximum resource quota amount;

Based on the resource saturation of the resource users, sort the resource users whose application resources are greater than their minimum resource quotas;

Resource users whose application resource amount is less than or equal to their minimum resource quota are called A-type resource users; according to the order of resource users, a boundary resource user is determined by setting conditions. For resource saturation less than or equal to all A resource user whose resource saturation is above the boundary resource user is called a B-type resource user; a resource user whose resource saturation is greater than the resource saturation of the boundary resource user is called a C-type resource user;

For Type A resource users and Type B resource users, resources are allocated to them based on the amount of resources they apply for as their resource quota; for Type C resource users, the total amount of system resources minus the above is used as a Type A resource user After subtracting the sum of the minimum resource quotas of all Class C resource users from all resources allocated by Class B resource users, the remaining resource amount is obtained; The ratio of the maximum resource quota of all C-type resource users to the sum of the maximum resource quotas of all C-type resource users is taken as the resource allocation exceeding the minimum resource quota, and the above-mentioned resource allocation exceeding the minimum resource quota plus the The sum of the minimum resource quota of the C-type resource user is used as the resource quota of the C-type resource user to allocate resources to it.

Optionally, the set condition is that the data of the boundary resource user satisfies the following Inequality 3 and Inequality 4,

Inequality three:

Inequality four:

in

ToatalResource: the total amount of system resources; Request _k : the application resource amount of the kth resource user whose application resource amount is less than or equal to its minimum resource quota; MinQuota _i : resource saturation is less than or equal to the resource saturation of the boundary resource user , and the amount of applied resources is greater than its minimum resource quota, the minimum resource quota of the i-th B-type resource user among other B-type resource users except boundary resource users; Request _i : resource saturation is less than or equal to Resource saturation of border resource users, and if the amount of applied resources is greater than its minimum resource quota, the application resource amount of the i-th class B resource user among other B resource users except border resource users; MaxQuota _j : The resource saturation is greater than the resource saturation of the boundary resource user, and the maximum resource quota of the jth class C resource user whose application resource is greater than the minimum resource quota; MinQuota _j : The resource saturation is greater than the boundary resource user resource saturation, and the minimum resource quota of the jth class C resource user whose application resource is greater than its minimum resource quota; Request _h : the application resource amount of the border resource user; MaxQuota _h : the border resource user’s The maximum resource quota; MinQuata _h : the minimum resource quota of the boundary resource user; Request _h+1 : among the sorted resource users, the resource saturation is smaller than any other resource saturation and greater than the resource saturation of the boundary resource user degree of resource saturation of resource users, but greater than the resource saturation of boundary resource users, the application resource amount of class C resource users; MaxQuota _h+1 : Among the sorted resource users, the resource saturation is less than any - The resource saturation of other resource users whose resource saturation is greater than the resource saturation of the boundary resource user, but the maximum resource quota of the C-type resource users whose resource saturation is greater than the resource saturation of the boundary resource user; MinQuota _h+1 : Among the sorted resource users, the resource saturation is less than the resource saturation of any other resource user whose resource saturation is greater than the resource saturation of the border resource user, but greater than the resource saturation of the border resource user Class C The minimum resource quota of resource users; s: the number of Class A resource users whose application resources in the system are less than or equal to their minimum resource quota; m: the resource saturation in the system is less than or equal to the resource saturation of boundary resource users degree, and the amount of applied resources is greater than its minimum resource quota, the number of other B-type resource users except boundary resource users; n: C-type resources whose resource saturation in the system is greater than the resource saturation of boundary resource users The number of users; ∑: sum operation.

Optionally, the method of determining a boundary resource user by setting conditions according to the sorting of resource users includes:

using one of the sorted resource users as a temporary boundary resource user;

Substituting the temporary boundary resource user as the boundary resource user into the above inequality 3 and inequality 4, if the two inequalities are both established, then the temporary resource user is the boundary resource user; if the two inequalities cannot both be established, then all Another resource user among the resource users sorted above acts as a temporary border resource user, and returns to the step of "substituting the temporary border resource user as a border resource user into Inequality 3 and Inequality 4".

Optionally, the method for using another resource user among the sorted resource users as a temporary boundary resource user includes:

If Inequality 3 is not established, then select a resource user whose resource saturation is less than that of the temporary border resource user among the sorted resource users, and use the data of the resource user as the data of the temporary border resource user ;

If inequality four is not established, then select a resource user whose resource saturation is greater than the resource saturation of the temporary border resource user among the resource users of the sorting, and use the data of the resource user as the data of the temporary border resource user .

Optionally,

The method for sorting resource users whose application resources are greater than their minimum resource quotas based on the resource saturation of the resource users includes: using resource allocation related data of resource users

Form a tree node into a sorted binary tree according to the size of resource saturation or update the sorted binary tree to store the resource user’s data node, and by adjusting the position and relationship between the nodes of the sorted binary tree, keep the binary tree still as Sort the binary tree; the data related to the resource allocation of the resource user includes the resource saturation of the resource user, the amount of applied resources, the minimum resource quota and the maximum resource quota;

Correspondingly, the method for using one of the sorted resource users as a temporary border resource user includes: using the resource user stored in the root node of the sorted binary tree as a temporary border resource user ;

Correspondingly, the method for selecting a resource user whose resource saturation is less than the resource saturation of the temporary boundary resource user among the sorted resource users is as follows: select a resource saturation less than or equal to in the sorted binary tree The resource user corresponding to the direct child node on the resource saturation side of the temporary boundary resource user;

Correspondingly, the method for selecting a resource user whose resource saturation is greater than the resource saturation of the temporary boundary resource user among the sorted resource users is as follows: select a resource saturation greater than the temporary boundary in the sorted binary tree The resource user corresponding to the direct child node on the resource saturation side of the resource user.

Optionally, the resource user resource allocation-related data further includes: the sum of resource applications of resource users whose resource saturation is less than or equal to the resource saturation of the resource user, and the resource saturation is less than or equal to the resource usage The sum of the minimum resource quotas of the resource users whose resource saturation is greater than the resource saturation of the resource user, the sum of the maximum resource quotas of the resource users whose resource saturation is greater than the resource saturation of the resource user, and the resource saturation greater than the node corresponding to The sum of the minimum resource quotas of the resource users whose resources are saturated, and the sum of the application resources of the resource users whose application resources are less than their minimum quotas.

Optionally,

Based on the resource saturation of the resource users, the method for sorting the resource users whose application resources are greater than their minimum resource quotas includes: using the data related to the resource allocation of the resource users to form a tree node according to the resources The size of the saturation is inserted into the sorted binary tree or updated into the sorted binary tree to store the data nodes of the resource user, and by adjusting the position and relationship between the nodes of the sorted binary tree, the binary tree is still a sorted binary tree; the resource Data related to user resource allocation includes: resource saturation of resource users, amount of requested resources, minimum resource quota and maximum resource quota.

Optionally, the resource user resource allocation-related data further includes:

The sum of the application resources of the resource users whose resource saturation is less than or equal to the resource saturation of the resource user, and the sum of the minimum resource quotas of the resource users whose resource saturation is less than or equal to the resource saturation of the resource user , the sum of the maximum resource quotas of the resource users whose resource saturation is greater than the resource saturation of the resource user, and the minimum resource quota of the resource users whose resource saturation is greater than the resource saturation of the resource user corresponding to the node and the sum of resource requests of resource users whose application resources are less than their minimum quota.

A computer system resource allocation device provided by the present application includes:

An acquisition unit, configured to acquire the total amount of system resources and resource allocation-related data of resource users who have the right to make resource application requests, and the resource allocation-related data of resource users includes the resource user's maximum resource quota and application resource amount ;

A resource saturation calculation unit, configured to calculate the resource saturation of the resource user by dividing the amount of resources requested by the resource user by the maximum resource quota;

a sorting unit, configured to sort the resource users based on the resource saturation of the resource users;

The classification unit is used to sort resource users, determine a boundary resource user by setting conditions, and classify resource users whose resource saturation is less than or equal to the boundary resource user as B-type resource users; saturate resources A resource user whose degree is greater than the boundary resource user is called a class C resource user;

The resource allocation unit is used to allocate resources to Class B resource users using their application resource amount as their resource quota; for Class C resource users, subtract the total amount of system resources from the above-mentioned resources to use Class B resources After all the resources allocated by the user, the remaining resources are obtained; the remaining resources are calculated as For its resource quota, allocate resources to the C-type resource user according to the resource quota.

A computer system resource allocation device provided by the present application includes:

The obtaining unit is used to obtain the total amount of system resources and resource allocation-related data of resource users who have the right to make resource application requests. The resource allocation-related data of resource users includes the resource user's minimum resource quota and maximum resource quota amount and application resources;

The resource saturation calculation unit is used to calculate the resource saturation of the resource user by dividing the difference between the resource user's application resource amount minus the minimum resource quota amount by the maximum resource quota amount;

A sorting unit, configured to sort resource users whose application resources are greater than their minimum resource quotas based on the resource saturation of the resource users;

The taxonomy unit is used to classify resource users whose application resources are less than or equal to their minimum resource quotas as Class A resource users; sort resource users to determine a boundary resource user by setting conditions. For resource saturation A resource user whose resource saturation degree is less than or equal to the resource saturation degree of the boundary resource user is called a type B resource user; a resource user whose resource saturation degree is greater than the resource saturation degree of the boundary resource user is called a type C resource user;

The resource allocation unit is used to allocate resources to Class A resource users and Class B resource users using their application resources as their resource quotas; for Class C resource users, subtract the total system resources according to After subtracting the sum of the minimum resource quotas of all Class C resource users from all the resources allocated to Class A resource users and Class B resource users, the remaining resource amount is obtained; the remaining resource amount is calculated according to The proportion of the maximum resource quota of the C-type resource user to the sum of the maximum resource quotas of all C-type resource users is taken as the resource allocation amount exceeding the minimum resource quota, and the ratio of the exceeding minimum resource quota The sum of the resource allocation amount plus the minimum resource quota amount of the C-type resource user is used as the resource quota of the C-type resource user to allocate resources to it.

Compared with the prior art, the present application has the following advantages:

The technical solution of this application introduces the concept of resource saturation, sorts resource users according to their resource saturation, searches for boundary resource users among the sorted resource users, and utilizes resource saturation and boundary resource usage of resource users The comparison result of the resource saturation of the user can quickly calculate the resource quota of the resource user, and reduce the time complexity of calculating the resource quota of the resource user from O(n ² ) to the level of O(log n) (the n is the number of users). It can reduce the time complexity of calculating the resource quotas of resource users and meet the requirements of real-time computing. At the same time, it is only necessary to calculate the resource quotas of resource users who apply for resources instead of calculating the resource quotas of all resource users, further speeding up the processing of resources. The effect of resource allocation on resource consumers.

In addition, in addition to the technical features of the above-mentioned solution, another technical solution of the present application can not only achieve the above-mentioned reduction in the time complexity of computing resource users' resource quotas, but also meet the requirements of real-time computing. The requirements and the effect of not needing to calculate the resource quotas of all resource users can also play a role in satisfying the minimum resource quota allocation of resource users.

Description of drawings

FIG. 1 is a schematic flowchart of an embodiment of a method for allocating computer system resources according to the first embodiment of the present application;

FIG. 2 is a structural block diagram of an embodiment of a computer system resource allocation device according to the second embodiment of the present application;

FIG. 3 is a schematic flowchart of an embodiment of a computer system resource allocation method according to the third embodiment of the present application;

Fig. 4 is a structural block diagram of an embodiment of a computer system resource allocation device according to the fourth embodiment of the present application;

Detailed ways

In the following description, numerous specific details are set forth in order to provide a thorough understanding of the application. However, the present application can be implemented in many other ways different from those described here, and those skilled in the art can make similar promotions without violating the connotation of the present application. Therefore, the present application is not limited by the specific implementation disclosed below.

The first embodiment of the present application provides a computer system resource allocation method, as shown in Figure 1, which includes the following steps:

Step S101, obtaining the total amount of system resources and resource allocation-related data of resource users who have the right to request resource applications. The resource allocation-related data of resource users includes the resource user's maximum resource quota and resource application.

After receiving a request from a resource user to apply for system resources, obtain the total amount of system resources and data related to resource allocation of the resource user, including the maximum resource quota of the resource user and the data of the resource amount applied for by the resource user.

In step S102, the resource saturation degree of the resource user is calculated by dividing the requested resource amount by the resource user by the maximum resource quota amount.

The resource saturation value is calculated by dividing the requested resource amount of the resource user by its maximum resource quota.

Step S103, sorting the resource users based on the resource saturation of the resource users.

Sort according to the resource saturation of resource users. There are many ways to sort resource users. In this embodiment, when a new resource application request is received, if the resource user is applying for resources for the first time, the system has not yet arranged for the resource user. After sorting, the corresponding sorted data storage structure does not contain any data of the resource user. At this time, the data of the resource user includes the maximum resource quota, the amount of requested resources, and the resource saturation as a data node, and inserted according to A sorted binary tree sorted by resource saturation of resource consumers.

The parent node directly connected to each node in the binary tree is called the node's parent node, and the next-level node directly connected to it is called the direct child node of the node. The resource saturation of the resource user stored in the direct child node of any node in the binary tree is less than the resource saturation of the resource user stored in the node, and the resource saturation stored in the direct child node of the other side of the node is The resource saturation of the resource user is greater than the resource saturation of the resource user stored in the node.

When inserting the data of resource users applying for resources into the binary tree, by rotating the position and relationship of the nodes, the binary tree after inserting the nodes can still be a binary tree sorted according to resource saturation.

When a new resource application request is received, if the resource user is not applying for a resource for the first time, the data of the resource user has already been saved in the binary tree, and at this time, only the relevant data of the corresponding tree node needs to be updated , specifically the application resource amount and resource saturation. At the same time, rotate the nodes of the binary tree and adjust their positions and relationships so that they remain as a binary tree sorted by resource saturation.

Step S104, according to the ranking of resource users, determine a boundary resource user by setting conditions, and classify resource users whose resource saturation is less than or equal to the boundary resource user as B-type resource users; The resource users of the boundary resource users are called C-type resource users.

In this embodiment, among the sorted resource users, find resource users whose data satisfy the following two inequalities, and call them boundary resource users.

Inequality one:

Inequality two:

Among them, ToatalResource: the total amount of system resources; Request _i : if the resource saturation is less than or equal to the resource saturation of the border resource user, the i-th class B resource user among other class B resource users except the border resource user Application resource amount; MaxQuota _j : the maximum resource quota of the jth class C resource user whose resource saturation is greater than the resource saturation of the boundary resource user; Request _h : the application resource amount of the boundary resource user; MaxQuota _h : boundary The maximum resource quota of a resource user; Request _h+1 : Among the sorted resource users, the resource saturation is less than the resource saturation of any other C-type resource users, but greater than the resource saturation of the boundary resource users The amount of resources requested by a class C resource user; MaxQuota _h+1 : Among the resource users sorted, the resource saturation is less than that of any other class C resource user, but greater than the resource saturation of the boundary resource user The maximum resource quota of C-type resource users; m: the number of other B-type resource users except for boundary resource users whose resource saturation in the system is less than or equal to the resource saturation of boundary resource users; n : The number of C-type resource users whose resource saturation in the system is greater than that of the boundary resource users; ∑: summation operation.

Among the sorted resource users, resource users whose resource saturation is less than or equal to the boundary user's resource saturation are called B-type resource users; resources whose resource saturation is greater than the boundary user's resource saturation The user becomes a class C resource user.

The method of finding the boundary user can be different according to the data storage method of the resource user. In this embodiment, for the method of storing resource user data in a binary tree sorted according to resource saturation, firstly, the resource user stored in the root node of the binary tree is used as a temporary boundary resource user, and the temporary boundary resource The user's data is used as the data of the border resource user, and the data of the node on the side that is less than or equal to the resource saturation of the node where the temporary border resource user is located is taken as the resource saturation of the border resource user is less than or equal to the resource saturation of the border resource user The data of the resource user whose resource saturation is higher than the boundary resource user's data is the data of the node on the other side; the data of the direct child node on the other side is the resource saturation only Data for resource consumers whose resource saturation is greater than the boundary resource consumer.

Inequality 1 and Inequality 2 are used to determine whether the temporary border resource user is a border resource user.

If the temporary boundary resource user is used as the boundary resource user so that Inequality 1 does not hold, then the resource saturation of the node where the temporary boundary user is located is less than or equal to the resource saturation stored in the direct child node As a temporary border resource consumer. Substitute the data of the new temporary boundary resource user in the sorted binary tree into Inequality 1 again, and so on, until the data of the resource user stored in a certain node satisfies Inequality 1 as the data of the temporary boundary resource user. Then judge whether the data of the temporary border resource user satisfies the second inequality.

If the temporary boundary resource user is used as the boundary resource user so that Inequality 2 does not hold, then the resource saturation of the node where the temporary boundary user is located has a resource saturation greater than its resource saturation stored in the direct child node as the temporary resource user Boundary resource users. Substitute the data of the new temporary boundary resource user in the sorted binary tree into inequality 2 again, and so on, until the data of the resource user stored in a certain node satisfies inequality 2 as the data of the temporary boundary resource user. Then judge whether the data of the temporary border resource user satisfies inequality one.

The temporary boundary resource user who can make both inequality 1 and inequality 2 hold true is the boundary resource user.

A resource user whose resource saturation is less than or equal to the resource saturation of the boundary resource user is called a type B resource user, and a resource user whose resource saturation is greater than the resource saturation of the boundary resource user is called a class B resource user. Class C resource users. That is to say, in the sorted binary tree, the node on one side of the node where the boundary resource user is located stores the data of the B-type resource user, and the other side node stores the data of the C-type resource user.

According to the resource saturation value of resource users who apply for resources, they are classified as corresponding resource users. That is, if the resource saturation of the resource user applying for the resource is less than or equal to the resource saturation of the boundary resource user, the resource user applying for the resource is classified as a B-type resource user; if the resource user applying for the resource The resource saturation of the resource is greater than the resource saturation of the boundary resource user, and the resource user applying for the resource is classified as a C-type resource user.

Step S105, for resource users of type B, allocate resources to them based on the amount of resources they apply for as their resource quota; After the resource amount is obtained, the remaining resource amount is obtained; the remaining resource amount is used as the resource quota according to the ratio of the maximum resource quota amount of the C-type resource user to the maximum resource quota amount of all C-type resource users, Allocate resources to the C-type resource users according to the resource quota.

When the resource user applying for the resource belongs to the B-type resource user, allocate the amount of the resource applied for to it.

When the resource user who applies for resources is a class C resource user, the difference between the total amount of system resources minus the sum of the resources requested by all class B resource users is the remaining resource amount of the system. The remaining resources of the system are allocated to the resource user as their resource quota according to the ratio of the maximum resource quota of the resource user to the sum of the maximum resource quotas of all C-type resource users, and resources are allocated to it. That is, the amount of resources is allocated to it according to the following formula:

Resource quota formula 1:

Among them, Resource _x : the resource quota of class C resource user x whose resource saturation is greater than the resource saturation of the border resource user; MaxQuota _x : the resource quota of class C resource user x whose resource saturation is greater than the resource saturation of the border resource user Maximum resource quota; ToatalResource: total system resources; Request _h : application resource amount of border resource users; Request _i : resource saturation less than or equal to the resource saturation of border resource users, except for border resource users The application resource amount of the i-th type B resource user; MaxQuota _j : the maximum resource quota of the j-th type C resource user whose resource saturation is greater than the resource saturation of the boundary resource user; m: resource saturation in the system If the resource saturation of the boundary resource user is less than or equal to the resource saturation of the boundary resource user, the number of other B-type resource users except the boundary resource user; n: the use of C-type resources whose resource saturation in the system is greater than the resource saturation of the boundary resource user The number of participants; ∑: summation operation.

For simplifying the calculation, when inserting or updating tree nodes in step S103, the value of the summation item in Inequality 1 and Inequality 2 can be saved respectively in the node being inserted or updating, like this, each node of described sorting binary tree In addition to saving the resource user's maximum resource quota, application resource amount and resource saturation, it also saves the application resource amount of resource users whose resource saturation is less than or equal to the resource saturation of the resource user corresponding to this node The sum and the sum of the maximum resource quota of the resource user whose resource saturation is greater than the resource saturation of the resource user corresponding to the node. In this way, when the above inequality 1 and inequality 2 are used to find the boundary resource user and the resource quota formula 1 is used to calculate the resource quota of the resource user, time can be saved.

In the above-mentioned embodiments, a computer system resource allocation method is provided, which reduces the time complexity of calculating the resource quota of the resource user from O(n ² ) to the level of O(log n) (where n is the resource number of users). It can reduce the time complexity of calculating the resource quotas of resource users and meet the requirements of real-time computing. At the same time, it is only necessary to calculate the resource quotas of resource users who apply for resources instead of calculating the resource quotas of all resource users, further speeding up the processing of resources. The effect of resource allocation on resource consumers. Correspondingly, the present application also provides a computer system resource allocation device. Please refer to FIG. 2 , which is a schematic structural diagram of an embodiment of an apparatus for allocating computer system resources according to the present application. Since the device embodiment is basically similar to the method embodiment, the description is relatively simple, and for relevant parts, refer to the part of the description of the method embodiment. The device embodiments described below are illustrative only.

Please refer to FIG. 2 , the computer system resource allocation device includes an acquisition unit U201, a resource saturation calculation unit U202, a sorting unit U203, a classification unit U204 and a resource allocation unit U205.

The acquiring unit U201 is configured to acquire the total amount of system resources and resource allocation-related data of resource users who have the right to make resource application requests, and the resource allocation-related data of resource users includes the resource user's maximum resource quota and The amount of resources requested.

The resource saturation calculation unit U202 is configured to calculate the resource saturation of the resource user by dividing the amount of resources requested by the resource user by the maximum resource quota.

The sorting unit U203 is configured to sort the resource users based on the resource saturation of the resource users.

The classification unit U204 is configured to determine a border resource user by setting conditions according to the sorting of resource users, and classify resource users whose resource saturation is less than or equal to the border resource user as B-type resource users; A resource user whose resource saturation is greater than the boundary resource user is called a C-type resource user.

The resource allocation unit U205, a resource allocation unit, is configured to allocate resources to the B-type resource users with the amount of resources they apply for as their resource quotas. For resource users of type C, the remaining resource amount is obtained after subtracting the amount of all resources allocated for resource users of type B from the total amount of system resources. The remaining resource amount, according to the ratio of the maximum resource quota of the C-type resource user to the sum of the maximum resource quotas of all C-type resource users, is used as its resource quota, and the resource quota is used to provide the C Class resource users allocate resources.

The third embodiment of the present application also provides a method for allocating computer system resources, the flowchart of which is shown in FIG. 3 . Include the following steps:

Step S301, obtaining the total amount of system resources and resource allocation-related data of resource users who have the right to make resource application requests. The resource allocation-related data of resource users includes the resource user's minimum resource quota, maximum resource quota and The amount of resources requested.

After receiving a request from a resource user to apply for system resources, obtain the total amount of system resources and the resource allocation-related data of the resource user, including not only the amount of requested resources, the maximum resource quota, but also the minimum resource quota.

Step S302, using the resource user's application resource amount minus the minimum resource quota amount and dividing by the maximum resource quota amount to calculate the resource saturation of the resource user;

The resource saturation value of the resource user is obtained by dividing the resource user's requested resource amount minus the minimum resource quota by the resource user's maximum resource quota. For resource users whose application resources are less than or equal to their minimum resource quota, the resource saturation values are negative or zero respectively; for resource users whose application resources are greater than their minimum resource quota, their resource saturation values are greater than zero

Step S303, sorting the resource users whose applied resource amount is greater than their minimum resource quota amount based on the resource saturation of the resource user.

According to the value of the resource saturation of the resource user, the resource users whose applied resource amount is greater than their minimum resource quota, that is, the resource users whose resource saturation value is greater than zero, are sorted.

When receiving a request from a resource user to apply for a resource, if the resource user applying for the resource is applying for the resource for the first time or the system has not yet sorted the resource user, the corresponding sorted data storage structure does not include the resource user. Any data of the resource user. In this case, the data of the resource user includes the maximum resource quota, the minimum resource quota, the application resource amount, and the resource saturation as a data node, which is inserted according to the resource saturation of the resource user sorted sorted binary tree.

The resource saturation of the resource user stored in the direct child node of any node in the binary tree is less than or equal to the resource saturation of the resource user stored in the node, and the resource saturation stored in the direct child node of the other side of the node is The stored resource saturation of the resource user is greater than the resource saturation of the resource user stored in the node.

When inserting the data of resource users applying for resources into the binary tree, by rotating the position and relationship of the nodes, the binary tree after inserting the nodes can still be a binary tree sorted according to resource saturation.

When receiving a request from a resource user to apply for a resource, if the resource user applying for the resource is not applying for the resource for the first time, and the system has previously sorted the resource user, the corresponding sorted data storage structure will include the resource The user's data, in this case, it is only necessary to update the relevant data of the corresponding node of the sorted binary tree, specifically the application resource amount and resource saturation. At the same time, the nodes of the binary tree are rotated to adjust their positions and relationships, so that they remain as a binary tree sorted by resource saturation.

Step S304, classify resource users whose application resource amount is less than or equal to the minimum resource quota amount as class A resource users; determine a boundary resource user by setting conditions according to the ranking of resource users, and for resource saturation less than Or a resource user equal to the resource saturation of the boundary resource user is called a B-type resource user; a resource user whose resource saturation is greater than the resource saturation of the boundary resource user is called a C-type resource user .

For resource users whose application resources are less than their minimum or equal to their resource quota, they are called Class A resource users.

For resource users whose applied resource amount is greater than their minimum resource quota, sort the resource users to determine a boundary resource user by setting conditions.

In this embodiment, among the sorted resource users, find resource users whose data satisfy the following two inequalities, and call them boundary resource users.

Inequality three:

Inequality four:

Further, the above two inequalities can be simplified into the following form by performing the operation of merging similar items:

Inequality three:

Inequality four:

in

ToatalResource: the total amount of system resources; Request _k : the application resource amount of the kth resource user whose application resource amount is less than or equal to its minimum resource quota; MinQuota _i : resource saturation is less than or equal to the resource saturation of the boundary resource user , and the amount of applied resources is greater than its minimum resource quota, the minimum resource quota of the i-th B-type resource user among other B-type resource users except boundary resource users; Request _i : resource saturation is less than or equal to Resource saturation of border resource users, and if the amount of applied resources is greater than its minimum resource quota, the application resource amount of the i-th class B resource user among other B resource users except border resource users; MaxQuota _j : The resource saturation is greater than the resource saturation of the boundary resource user, and the maximum resource quota of the jth class C resource user whose application resource is greater than the minimum resource quota; MinQuota _j : The resource saturation is greater than the boundary resource user resource saturation, and the minimum resource quota of the jth class C resource user whose application resource is greater than its minimum resource quota; Request _h : the application resource amount of the border resource user; MaxQuota _h : the border resource user’s The maximum resource quota; MinQuata _h : the minimum resource quota of the boundary resource user; Request _h+1 : among the sorted resource users, the resource saturation is smaller than any other resource saturation and greater than the resource saturation of the boundary resource user degree of resource saturation of resource users, but greater than the resource saturation of boundary resource users, the application resource amount of class C resource users; MaxQuota _h+1 : Among the sorted resource users, the resource saturation is less than any - The resource saturation of other resource users whose resource saturation is greater than the resource saturation of the boundary resource user, but the maximum resource quota of the C-type resource users whose resource saturation is greater than the resource saturation of the boundary resource user; MinQuota _h+1 : Among the sorted resource users, the resource saturation is less than the resource saturation of any other resource user whose resource saturation is greater than the resource saturation of the border resource user, but greater than the resource saturation of the border resource user Class C The minimum resource quota of resource users; s: the number of Class A resource users whose application resources in the system are less than or equal to their minimum resource quota; m: the resource saturation in the system is less than or equal to the resource saturation of boundary resource users degree, and the amount of applied resources is greater than its minimum resource quota, the number of other B-type resource users except boundary resource users; n: C-type resources whose resource saturation in the system is greater than the resource saturation of boundary resource users The number of users; ∑: sum operation.

A resource user whose resource saturation is less than or equal to the boundary resource user is called a B-type resource user; a resource user whose resource saturation is greater than the boundary resource user is called a C-type resource user.

The method of finding the boundary user can be different according to the data storage method of the resource user. In this embodiment, for the method of storing the data of the resource user in a binary tree sorted according to the resource saturation, first of all, the The resource user stored in the root node of the binary tree is used as a temporary boundary resource user, and the data of the temporary boundary resource user is used as the data of the boundary resource user, and the resources smaller than the node where the temporary boundary resource user is located are saturated The data of the nodes on one side of the degree is taken as the data of the resource users whose resource saturation is less than or equal to the resource saturation of the boundary resource users; the data of the nodes on the other side are taken as the resource saturation of the resource saturation of the boundary resource users The data of the resource user whose resource saturation is only greater than the resource saturation of the boundary resource user is the data of the direct child node on the other side.

Inequality 3 and Inequality 4 are used to determine whether the temporary border resource user is a border resource user.

If the temporary boundary resource user is used as the boundary resource user so that Inequality 3 does not hold, then the resource usage stored in the direct child node on the side where the resource saturation of the node where the temporary boundary user is located is less than or equal to its resource saturation as temporary border resource users. Substitute the data of the new temporary boundary resource user in the sorted binary tree into the third inequality again, and so on, until the data of the resource user stored in a node as the data of the temporary boundary resource user satisfies the third inequality. Then judge whether the data of the temporary border resource user satisfies inequality four.

If the temporary boundary resource user is used as the boundary resource user so that Inequality 4 does not hold, then the resource user stored in the direct child node on the side where the node where the temporary boundary user is located has a resource saturation greater than its resource saturation is taken as Temporary border resource consumer. Substitute the data of the new temporary boundary resource user in the sorted binary tree into Inequality 4 again, and so on, until the data of the resource user stored in a certain node satisfies Inequality 4 as the data of the temporary boundary resource user. Then judge whether the data of the temporary border resource user satisfies inequality three.

The temporary boundary resource user who can make both inequality 3 and inequality 4 hold true is the boundary resource user.

A resource user whose resource saturation is less than or equal to the resource saturation of the boundary resource user is called a type B resource user, and a resource user whose resource saturation is greater than the resource saturation of the boundary resource user is called a class B resource user. Class C resource users. That is to say, in the sorted binary tree, the node on one side of the node where the boundary resource user is located stores the data of the B-type resource user, and the other side node stores the data of the C-type resource user.

According to the application resource amount, the minimum resource quota amount, the maximum resource quota amount and the resource saturation value of the resource user who applies for resources, it is classified into the corresponding class of resource users. That is, if the amount of resources requested by a resource user who applies for resources is less than or equal to the minimum resource quota, the resource user who applies for resources is classified as a type A resource user. If the amount of resources requested by the resource user applying for resources is greater than its minimum resource quota, and the resource saturation is less than or equal to the resource saturation of the border resource user, then the resource user applying for resources is classified as a B-type resource user ; If the requested resource amount of the resource user applying for resources is greater than its minimum resource quota, and the resource saturation is greater than the resource saturation of the border resource user, then the resource user applying for resources is classified as a C-type resource user.

Step S305, for resource users of type A and resource users of type B, allocate resources to them with the amount of resources they apply for as their resource quota; After subtracting the sum of the minimum resource quotas of C-type users from all the resources allocated by resource users and B-type resource users, the remaining resource amount is obtained; the remaining resource amount is used according to the C-type resource The ratio of the maximum resource quota amount of the user to the sum of the maximum resource quota amounts of all C-type resource users is taken as the resource allocation amount exceeding the minimum resource quota amount, and the above-mentioned resource allocation amount exceeding the minimum resource quota amount plus The sum of the minimum resource quota of the C-type resource user is used as the resource quota of the C-type resource user to allocate resources to it.

When the resource user applying for resources belongs to category A or category B resource users, allocate the amount of resources they apply for.

When the resource user applying for the resource is a class C resource user, subtract the sum of the application resources of all class A resource users and class B resource users from the total system resources, and then subtract all the resource usage of class C The difference after the minimum resource quota of the resource user is used as the remaining resource of the system, and the remaining resource of the system is allocated to the resource user according to the ratio of the maximum resource quota of the resource user to the sum of the maximum resource quota of all C-type resource users. The resource user takes the resource quota exceeding the minimum resource quota as its resource quota, and allocates resources to the resource user by taking the resource quota exceeding the minimum resource quota plus the minimum resource quota as its resource quota. That is, the amount of resources is allocated to it according to the following formula:

Resource quota formula 2:

Further, the operation of merging similar items on the above formula can simplify the above resource quota formula 2 into the following form:

Among them, Resource _x : the resource quota of class C resource user x whose resource saturation is greater than the resource saturation of the border resource user; MinQuota _x : the resource quota of class C resource user x whose resource saturation is greater than the resource saturation of the border resource user The minimum resource quota; MaxQuota _x : the maximum resource quota of class C resource user x whose resource saturation is greater than the resource saturation of the boundary resource user; ToatalResource: the total amount of system resources; Request _k : the amount of requested resources is less than its minimum resource The application resource amount of the kth class A resource user of the quota amount; MinQuota _i : resource saturation is less than or equal to the resource saturation of its boundary resource user, and the application resource amount is greater than its minimum resource quota amount, except for boundary resources The minimum resource quota of the i-th class B resource user other than the user; Request _i : if the resource saturation is less than or equal to the resource saturation of the boundary resource user, and the amount of requested resources is greater than its minimum resource quota, except for the boundary The application resource amount of the i-th class B resource user other than the resource user; MaxQuota _j : the maximum resource quota of the j-th class C resource user whose resource saturation is greater than the resource saturation of the boundary resource user; MinQuota _j : the minimum resource quota of the jth class C resource user whose resource saturation is greater than the resource saturation of the boundary resource user; Request _h : the amount of resources requested by the boundary resource user; s: the amount of resources requested in the system is less than its minimum resource The number of class A resource users with a quota amount; m: If the resource saturation in the system is less than or equal to the resource saturation of boundary resource users, and the amount of applied resources is greater than its minimum resource quota, B other than boundary resource users The number of class resource users; n: the number of class C resource users whose resource saturation in the system is greater than that of the boundary resource users; ∑: summation operation.

In order to simplify the calculation, when inserting or updating tree nodes in step S303, the values of the summation items in Inequality 3 and Inequality 4 can be saved or updated respectively in the inserted or updated nodes, so that each of the sorted binary trees In addition to saving the maximum resource quota, minimum resource quota, application resource and resource saturation of the resource user, a node can also save the following data: the resource saturation is less than or equal to the resource user corresponding to the node The sum of the application resources of the resource users whose resource saturation is less than or equal to the resource saturation of the resource user corresponding to the node is the sum of the minimum resource quotas of the resource users, and the resource saturation is greater than the The sum of the maximum resource quotas of resource users corresponding to the resource saturation of the resource user corresponding to the node, and the sum of the minimum resource quotas of resource users whose resource saturation is greater than the resource saturation of the resource user corresponding to the node , the sum of the requested resources of the resource users whose requested resources are less than their minimum quota. In this way, when using the above inequalities 3 and 4 to search for boundary resource users and to use resource quota formula 2 to calculate resource quotas of resource users, time can be saved.

In the above embodiments, a computer system resource allocation method is provided, which can not only reduce the time complexity of calculating the resource quotas of resource users, but also meet the requirements of real-time computing and the effect of not needing to calculate the resource quotas of all resource users , and can also play a role in satisfying the resource user's minimum resource quota configuration. Correspondingly, the present application also provides a computer system resource allocation device. Please refer to FIG. 4 , which is a schematic structural diagram of an embodiment of an apparatus for allocating computer system resources according to the present application. Since the device embodiment is basically similar to the method embodiment, the description is relatively simple, and for relevant parts, refer to the part of the description of the method embodiment. The device embodiments described below are illustrative only.

The present application provides a computer system resource allocation device, including: an acquisition unit U401, a resource saturation calculation unit U402, a sorting unit U403, a classification unit U404 and a resource allocation unit U405.

The acquiring unit U401 is configured to acquire the total amount of system resources and resource allocation-related data of resource users who have the right to make resource application requests, and the resource allocation-related data of resource users includes the resource user's minimum resource quota, The maximum resource quota and the amount of requested resources.

The resource saturation calculation unit U402 is configured to calculate the resource saturation of the resource user by dividing the difference between the resource user's application resource amount minus the minimum resource quota amount by the maximum resource quota amount.

The sorting unit U403 is configured to sort the resource users whose application resources are greater than their minimum resource quotas based on the resource saturation of the resource users.

The classification unit U404 is used to classify resource users whose application resource amount is less than or equal to the minimum resource quota amount as type A resource users; determine a boundary resource user by setting conditions according to the sorting of resource users, A resource user whose resource saturation is less than or equal to the resource saturation of the boundary resource user is called a type B resource user; a resource user whose resource saturation is greater than the resource saturation of the boundary resource user is called Class C resource users.

The resource allocation unit U405 is used to allocate resources to Class A resource users and Class B resource users using their application resources as their resource quotas; for Class C resource users, subtract the total amount of system resources from After subtracting the sum of the minimum resource quotas of all C-type resource users from the amount of all resources allocated to A-type resource users and B-type resource users, the remaining resource amount is obtained; the remaining resource amount, according to the ratio of the maximum resource quota of the C-type resource user to the sum of the maximum resource quotas of all C-type resource users, as the resource allocation amount exceeding the minimum resource quota, and the above-mentioned minimum resource quota The resource allocation amount of the quota amount plus the minimum resource quota amount of the C-type resource user is used as the resource quota of the C-type resource user to allocate resources to it.

Although the present application is disclosed as above with preferred embodiments, it is not used to limit the present application. Any person skilled in the art can make possible changes and modifications without departing from the spirit and scope of the present application. Therefore, the present application The scope of protection should be based on the scope defined by the claims of this application.

In a typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in computer readable media, in the form of random access memory (RAM) and/or nonvolatile memory such as read only memory (ROM) or flash RAM. Memory is an example of computer readable media.

1. Computer-readable media include permanent and non-permanent, removable and non-removable media. Information storage can be realized by any method or technology. Information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Flash memory or other memory technology, Compact Disc Read-Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic tape cartridge, tape magnetic disk storage or other magnetic storage device or any other non-transmission medium that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media excludes non-transitory computer-readable media, such as modulated data signals and carrier waves.

2. Those skilled in the art should understand that the embodiments of the present application may be provided as methods, systems or computer program products. Accordingly, the present application can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

Claims (18)

1. a kind of resource for computer system distribution method, which comprises the following steps:

It obtains system resource total amount and has the right to propose the resource allocation related data of the resource user of resource bid request, it is described The resource allocation related data of resource user includes the maximum resource quota amount and application stock number of resource user；

Using the application stock number of the resource user divided by maximum resource quota amount, the resource of resource user is calculated Saturation degree；

Using the resource saturation degree of the resource user as foundation, the resource user is ranked up；

It is sorted according to resource user, determines a boundary resource user to impose a condition, resource saturation degree is less than or is waited In the resource user of the boundary resource user, referred to as B class resource user；Resource saturation degree is greater than the boundary resource The resource user of user is known as C class resource user；

To B class resource user, apply for that stock number distributes resource as its resource quota to it using it；C class resource is used Person after system resource total amount to be subtracted to all stock numbers for B class resource user distribution, obtains surplus yield；It will be described Surplus yield is matched according to the maximum resource that the maximum resource quota amount of the C class resource user accounts for all C class resource users The ratio of the summation of volume amount distributes resource to the C class resource user with the resource quota as its resource quota.

2. resource for computer system distribution method according to claim 1, which is characterized in that the setting condition is described Boundary resource user meets inequality one and inequality two,

Inequality one:

Inequality two:

Wherein ToatalResource: system resource total amount；Request_i: resource saturation degree is used less than or equal to boundary resource The resource saturation degree of person, i-th of B class resource user in other B class resource users in addition to boundary resource user Application stock number；MaxQuota_j: resource saturation degree is greater than j-th of C class resource of the resource saturation degree of boundary resource user The maximum resource quota amount of user；Request_h: the application stock number of boundary resource user；MaxQuota_h: boundary resource The maximum resource quota amount of user；Request_h+1: in the sequencing resources user, resource saturation degree is less than other any C The resource saturation degree of class resource user, but it is greater than the Shen of the C class resource user of the resource saturation degree of boundary resource user It please stock number；MaxQuota_h+1: in the resource user of the sequence, resource saturation degree is used less than other any C class resources The resource saturation degree of person, but it is greater than the maximum resource quota of the C class resource user of the resource saturation degree of boundary resource user Amount；M: resource saturation degree is less than or equal to the resource saturation degree of boundary resource user in system, removes boundary resource user The quantity of other B class resource users in addition；N: the resource that resource saturation degree is greater than boundary resource user in system is saturated The quantity of the C class resource user of degree；∑: summation operation.

3. resource for computer system distribution method according to claim 2, which is characterized in that described according to resource user Sequence, to impose a condition, the method for determining a boundary resource user includes:

Using a resource user in the resource user of the sequence as temporary boundary resource user；

Substitute into the inequality one and inequality two for temporary boundary resource user as boundary resource user, if two not Equation is all set up, then temporary resource user is boundary resource user；It, will be described if two inequality cannot all be set up For another resource user in the resource user of sequence as temporary boundary resource user, returning to execution " will be interim The step of data of boundary resource user substitute into inequality one and inequality two " as the data of boundary resource user.

4. resource for computer system distribution method according to claim 3, which is characterized in that the money by the sequence Another resource user in the user of source includes: as the method for temporary boundary resource user

If inequality one is invalid, a resource saturation degree is selected to be less than temporary boundary in the resource user of the sequence The resource user of the resource saturation degree of resource user, using resource user as temporary boundary resource user；

If inequality two is invalid, a resource saturation degree is selected to be greater than temporary boundary in the resource user of the sequence The resource user of the resource saturation degree of resource user, using resource user as temporary boundary resource user.

5. resource for computer system distribution method according to claim 4, which is characterized in that

The method packet that using the resource saturation degree of the resource user as foundation, the resource user is ranked up It includes: with resource user's resource allocation related data, a tree node is formed, according to the size insertion sort two of resource saturation degree The back end of resource user is stored in fork tree or in more new sort binary tree, and by adjusting the sequence binary tree Position and correlation between node, keeping the binary tree still is sequence binary tree；The resource user resource allocation phase The resource saturation degree that data include resource user is closed, applies for stock number and maximum resource quota amount；

Correspondingly, a resource user in the resource user using the sequence is as temporary boundary resource user Method include: to use the resource user that the root node of the binary tree of the sequence is stored as temporary boundary resource Person；

Correspondingly, described, selecting a resource saturation degree to be less than temporary boundary resource in the resource user of the sequence makes The method of the resource user of the resource saturation degree of user is as follows: in the sequence binary tree select resource saturation degree be less than or Resource user corresponding to direct child node equal to the resource saturation degree side of temporary boundary resource user；

Correspondingly, described to select a resource saturation degree to use greater than temporary boundary resource in the resource user of the sequence The method of the resource user of the resource saturation degree of person is as follows: selecting resource saturation degree to be greater than in the sequence binary tree interim Resource user corresponding to the direct child node of the resource saturation degree side of boundary resource user.

6. resource for computer system distribution method according to claim 5, which is characterized in that the resource user resource Distribute related data further include: resource saturation degree is less than or equal to the resource user's of the resource saturation degree of resource user Apply for that the sum of stock number and resource saturation degree are greater than the maximum resource of the resource user of the resource saturation degree of resource user The sum of quota amount.

7. resource for computer system distribution method according to claim 1, which is characterized in that

The method packet that using the resource saturation degree of the resource user as foundation, the resource user is ranked up It includes: with resource user's resource allocation related data, a tree node is formed, according to the size insertion sort two of resource saturation degree The back end of resource user is stored in fork tree or in more new sort binary tree, and by adjusting the sequence binary tree Position and correlation between node, keeping the binary tree still is sequence binary tree；The resource user resource allocation phase The resource saturation degree that data include resource user is closed, applies for stock number and maximum resource quota amount.

8. resource for computer system distribution method according to claim 7, which is characterized in that

The resource user resource allocation related data further include: resource saturation degree is less than or equal to the money of resource user The sum of application stock number of resource user of source saturation degree and resource saturation degree are greater than the resource saturation degree of resource user The sum of the maximum resource quota amount of resource user.

9. a kind of resource for computer system distribution method, which comprises the following steps:

It obtains system resource total amount and has the right to propose the resource allocation related data of the resource user of resource bid request, it is described The resource allocation related data of resource user includes the least resource quota amount of resource user, maximum resource quota amount and Shen It please stock number；

The difference of least resource quota amount is cut divided by maximum resource quota amount, meter using the application stock number of the resource user Calculate the resource saturation degree for obtaining resource user；

Using the resource saturation degree of the resource user as foundation, the resource of its least resource quota amount is greater than to application stock number User is ranked up；

It will apply for that stock number is less than or equal to the resource user of its least resource quota amount, referred to as A class resource user；According to Resource user sequence determines a boundary resource user to impose a condition, and resource saturation degree is less than or equal to described The resource user of the resource saturation degree of boundary resource user, referred to as B class resource user；Resource saturation degree is greater than the side The resource user of the resource saturation degree of boundary resource user is known as C class resource user；

To A class resource user and B class resource user, apply for that stock number distributes resource as its resource quota to it using it； For C class resource user, system resource total amount is subtracted as all of A class resource user and B class resource user distribution After stock number, then after subtracting the summation of least resource quota amount of all C class resource users, surplus yield is obtained；By institute Surplus yield is stated, the maximum resource of all C class resource users is accounted for according to the maximum resource quota amount of the C class resource user The ratio of the summation of quota amount exceeds the resource allocation of least resource quota amount as it, exceeds least resource with described its The resource allocation of quota amount adds the sum of the least resource quota amount of the C class resource user as the C class resource user Resource quota to its distribute resource.

10. resource for computer system distribution method according to claim 9, which is characterized in that the setting condition is institute The data for stating boundary resource user meet following inequality three and inequality four,

Inequality three:

Inequality four:

Wherein

ToatalResource: system resource total amount；Request_k: application stock number is less than or equal to its least resource quota amount K-th of resource user application stock number；MinQuota_i: resource saturation degree is less than or equal to boundary resource user's Resource saturation degree, and apply for that stock number is greater than its least resource quota amount, other B classes money in addition to boundary resource user The least resource quota amount of i-th of B class resource user in the user of source；Request_i: resource saturation degree is less than or equal to side The resource saturation degree of boundary resource user, and apply for that stock number is greater than its least resource quota amount, remove boundary resource user The application stock number of i-th of B class resource user in other B class resource users in addition；MaxQuota_j: resource saturation degree Greater than the resource saturation degree of boundary resource user, and apply for that stock number is greater than j-th of C class resource of its least resource quota amount The maximum resource quota amount of user；MinQuota_j: resource saturation degree is greater than the resource saturation degree of boundary resource user, and Apply for that stock number is greater than the least resource quota amount of j-th of C class resource user of its least resource quota amount；Request_h: The application stock number of boundary resource user；MaxQuota_h: the maximum resource quota amount of boundary resource user；MinQuata_h: The least resource quota amount of boundary resource user；Request_h+1: in the resource user of the sequence, resource saturation degree is small It is greater than the resource saturation degree of the resource user of the resource saturation degree of boundary resource user in other any resource saturation degrees, but Greater than the application stock number of the C class resource user of the resource saturation degree of boundary resource user；MaxQuota_h+1: the sequence Resource user in, resource saturation degree be less than other any resource saturation degrees be greater than boundary resource user resource saturation degree Resource user resource saturation degree, but be greater than boundary resource user resource saturation degree C class resource user most Large resource quota amount；MinQuota_h+1: in the resource user of the sequence, resource saturation degree is saturated less than other any resources Degree is greater than the resource saturation degree of the resource user of the resource saturation degree of boundary resource user, but is greater than boundary resource user Resource saturation degree C class resource user least resource quota amount；S: application stock number is less than or equal to it most in system The quantity of the A class resource user of small resource quota amount；M: resource saturation degree is less than or equal to boundary resource user in system Resource saturation degree, and apply for that stock number is greater than its least resource quota amount, other B classes in addition to boundary resource user The quantity of resource user；N: the C class resource that resource saturation degree is greater than the resource saturation degree of boundary resource user in system makes The quantity of user；∑: summation operation.

11. resource for computer system distribution method according to claim 10, which is characterized in that described to be used according to resource Person's sequence, to impose a condition, the method for determining a boundary resource user includes:

Using a resource user in the resource user of the sequence as temporary boundary resource user；

Substitute into the inequality three and inequality four for temporary boundary resource user as boundary resource user, if two not Equation is all set up, then temporary resource user is boundary resource user；It, will be described if two inequality cannot all be set up For another resource user in the resource user of sequence as temporary boundary resource user, returning to execution " will be interim The step of boundary resource user substitutes into inequality three and inequality four " as boundary resource user.

12. resource for computer system distribution method according to claim 11, which is characterized in that described by the sequence Another resource user in resource user includes: as the method for temporary boundary resource user

If inequality three is invalid, a resource saturation degree is selected to be less than temporary boundary in the resource user of the sequence The resource user of the resource saturation degree of resource user, using the data of resource user as temporary boundary resource user Data；

If inequality four is invalid, a resource saturation degree is selected to be greater than temporary boundary in the resource user of the sequence The resource user of the resource saturation degree of resource user, using the data of resource user as temporary boundary resource user Data.

13. resource for computer system distribution method according to claim 12, which is characterized in that

It is described using the resource saturation degree of the resource user as foundation, its least resource quota amount is greater than to application stock number The method that resource user is ranked up includes: into a tree node with resource user's resource allocation related data according to resource The back end of resource user is stored in the size insertion sort binary tree of saturation degree or in more new sort binary tree, and is led to Position and correlation between the node for adjusting the sequence binary tree are crossed, keeping the binary tree still is sequence binary tree；Institute The resource saturation degree that resource user's resource allocation related data includes resource user is stated, applies for that stock number, least resource are matched Volume amount and maximum resource quota amount；

Correspondingly, a resource user in the resource user using the sequence is as temporary boundary resource user Method include: to use the resource user that the root node of the binary tree of the sequence is stored as temporary boundary resource Person；

Correspondingly, described to select a resource saturation degree to use less than temporary boundary resource in the resource user of the sequence The method of the resource user of the resource saturation degree of person is as follows: selecting resource saturation degree to be less than or wait in the sequence binary tree The resource user corresponding to the direct child node of the resource saturation degree side of temporary boundary resource user；

Correspondingly, described to select a resource saturation degree to use greater than temporary boundary resource in the resource user of the sequence The method of the resource user of the resource saturation degree of person is as follows: selecting resource saturation degree to be greater than in the sequence binary tree interim Resource user corresponding to the direct child node of the resource saturation degree side of boundary resource user.

14. resource for computer system distribution method according to claim 13, which is characterized in that the resource user money Related data is distributed in source further include: resource saturation degree is less than or equal to the resource user of the resource saturation degree of resource user The sum of application stock number, resource saturation degree is less than or equal to the resource user of the resource saturation degree of resource user most The sum of small resource quota amount, resource saturation degree are greater than the maximum resource of the resource user of the resource saturation degree of resource user The sum of quota amount, resource saturation degree are greater than the resource user of the resource saturation degree of resource user corresponding to the node most The sum of small resource quota amount, and application stock number are less than the sum of the application stock number of resource user of its minimum quota amount.

15. resource for computer system distribution method according to claim 9, which is characterized in that

It is described using the resource saturation degree of the resource user as foundation, its least resource quota amount is greater than to application stock number The method that resource user is ranked up include: with resource user's resource allocation related data, formed a tree node according to The back end of resource user is stored in the size insertion sort binary tree of resource saturation degree or in more new sort binary tree, And by adjusting position and correlation between the node of the sequence binary tree, keeping the binary tree still is sequence y-bend Tree；The resource user resource allocation related data includes: the resource saturation degree of resource user, applies for stock number, minimum Resource quota amount and maximum resource quota amount.

16. resource for computer system distribution method according to claim 15, which is characterized in that the resource user money Related data is distributed in source further include:

Resource saturation degree is less than or equal to the sum of the application stock number of resource user of resource saturation degree of resource user, Resource saturation degree is less than or equal to the sum of the least resource quota amount of resource user of resource saturation degree of resource user, Resource saturation degree is greater than the sum of the maximum resource quota amount of resource user of resource saturation degree of resource user, and resource is full It is greater than the sum of the least resource quota amount of resource user of resource saturation degree of resource user corresponding to the node with degree, It is less than the sum of the application stock number of resource user of its minimum quota amount with application stock number.

17. a kind of resource for computer system distributor, which is characterized in that including

Acquiring unit proposes the resource allocation of the resource user of resource bid request for obtaining system resource total amount and having the right Related data, the resource allocation related data of the resource user include the maximum resource quota amount and application of resource user Stock number；

Resource saturation computation unit, for the application stock number using the resource user divided by maximum resource quota amount, The resource saturation degree of resource user is calculated；

Sequencing unit, for being ranked up to the resource user using the resource saturation degree of the resource user as foundation；

Taxon determines a boundary resource user to impose a condition, resource is satisfied for being sorted according to resource user It is less than or equal to the resource user of the boundary resource user, referred to as B class resource user with degree；Resource saturation degree is greater than The resource user of boundary resource user is known as C class resource user；

Resource allocation unit is used for, and to B class resource user, applies for that stock number is provided as its resource quota to its distribution using it Source；For C class resource user, after all stock numbers that system resource total amount is subtracted to B class resource user distribution, remained Remaining stock number；By the surplus yield, accounting for all C class resources according to the maximum resource quota amount of the C class resource user makes The ratio of the summation of the maximum resource quota amount of user is made with the resource quota to the C class resource as its resource quota User distributes resource.

18. a kind of resource for computer system distributor, which is characterized in that including

Acquiring unit proposes the resource allocation of the resource user of resource bid request for obtaining system resource total amount and having the right Related data, the resource allocation related data of the resource user include the least resource quota amount of resource user, maximum Resource quota amount and application stock number；

Resource saturation computation unit, for cutting least resource quota amount using the application stock number of the resource user The resource saturation degree of resource user is calculated divided by maximum resource quota amount in difference；

Sequencing unit, for being greater than its most petty bourgeoisie to application stock number using the resource saturation degree of the resource user as foundation The resource user of source quota amount is ranked up；

Taxon, for that will apply for that stock number is less than or equal to the resource user of its least resource quota amount, referred to as A class is provided Source user；It is sorted according to resource user, determines a boundary resource user to impose a condition, it is small for resource saturation degree In or equal to the boundary resource user resource saturation degree resource user, referred to as B class resource user；Resource is satisfied The resource user for being greater than the resource saturation degree of boundary resource user with degree is known as C class resource user；

Resource allocation unit, for applying stock number as its resource using it to A class resource user and B class resource user Quota distributes resource to it；For C class resource user, system resource total amount is subtracted as A class resource user and B class resource After all stock numbers of user's distribution, then after subtracting the summation of least resource quota amount of all C class resource users, obtain Surplus yield；By the surplus yield, all C class resources are accounted for according to the maximum resource quota amount of the C class resource user The ratio of the summation of the maximum resource quota amount of user exceeds the resource allocation of least resource quota amount, as it with institute State its beyond least resource quota amount resource allocation plus the C class resource user least resource quota amount and conduct The resource quota of the C class resource user distributes resource to it.