CN112631746A - Service scheduling method and device, electronic equipment and storage medium - Google Patents

Abstract

The application relates to a service scheduling method, a service scheduling device, an electronic device and a storage medium, wherein the embodiment of the application acquires first service processing time of a first service and second service processing time of a second service, and the first service processing time is greater than or equal to the second service processing time; acquiring the ratio of the first service processing time to the second service processing time according to the first service processing time and the second service processing time; if the ratio is smaller than a threshold value, scheduling the first service and the second service to the same machine for processing; according to the embodiment of the application, the ratio of the processing time of the two services is calculated, the two services with the similar processing time are dispatched to the same machine for processing, the processing time of the machine is reduced, and the calculation efficiency of the system is improved.

Description

Service scheduling method, device, electronic device and storage medium

technical field

The embodiments of the present application relate to, but are not limited to, the field of computer technologies, and in particular, relate to a service scheduling method, apparatus, electronic device, and storage medium.

Background technique

Large-scale computing systems, such as clusters, parallel systems, and clouds, need to optimize the working hours of machines through business scheduling. For the bounded parallel interval scheduling problem, it means to minimize the total work of the machine by scheduling services to different machines within a certain time interval and under the condition that each machine can execute a certain number of services in parallel. time and improve business processing efficiency.

The existing service scheduling method obtains multiple service processing time intervals through the maximum service processing time and the minimum service processing time. When a new service arrives, its service processing time is pre-judged, and it is scheduled to the corresponding service processing time interval. The machine performs business processing, that is, the business with similar processing time is packed into one machine for processing. However, when two services with a small difference in service processing time are dispatched to machines in different service processing intervals for service processing, the overall service processing efficiency will be reduced.

SUMMARY OF THE INVENTION

The following is an overview of the topics detailed in this article. This summary is not intended to limit the scope of protection of the claims.

The embodiments of the present application provide a service scheduling method, device, electronic device, and storage medium. By scheduling services with similar service processing time to the same machine for processing, the processing time of the machine is optimized, thereby improving the computing efficiency of the entire parallel system.

In a first aspect, an embodiment of the present application provides a service scheduling method, including: obtaining a first service processing time of a first service and a second service processing time of a second service, where the first service processing time is greater than or equal to all the second service processing time; obtain the ratio of the first service processing time and the second service processing time according to the first service processing time and the second service processing time; if the ratio is less than the threshold, The first service and the second service are scheduled to be processed on the same machine.

The service scheduling method according to the embodiment of the present invention has at least the following beneficial effects: by calculating the ratio of the processing time of the two services, two services with similar processing time are scheduled to the same machine for processing, thereby reducing the processing time of the machine.

According to some embodiments of the present invention, it further includes: the threshold is adjusted according to at least one of the following factors: the maximum number of business processing that the machine can process in parallel; the maximum business processing time in the first time window in the business scheduling process The ratio of the minimum service processing time; wherein, the first time window has a preset first time length.

In a second aspect, the embodiments of the present application provide a service scheduling method for a parallel system with two or more machines, including: obtaining the processing time of the service to be scheduled for the current service to be scheduled; obtaining the processing time of the service in the computing system The scheduled service processing time set on each machine; according to the to-be-scheduled service processing time and the scheduled service processing time set on each machine, calculate the to-be-scheduled service processing time and each machine respectively The ratio of each element in the scheduled service processing time set above, and by adjusting the order of the two as the numerator and denominator, the ratio is greater than or equal to 1; if the ratio corresponding to each scheduled service processing time set is less than or equal to 1 If the first threshold is set, the currently to-be-scheduled service is scheduled to the machine corresponding to the scheduled service processing time set for service processing.

The service scheduling method according to the embodiment of the present invention has at least the following beneficial effects: the ratio between the processing time of the service to be scheduled and the processing time of the scheduled services that have been allocated to multiple machines is calculated one by one, and the corresponding processing time of the scheduled service that is similar to its processing time is obtained. Then, by scheduling the business to be scheduled to the machine, the total working time of multiple machines used in the parallel system can be shortened, the computing efficiency of the parallel system can be improved, and the system energy consumption and expenses can be reduced.

According to some embodiments of the present invention, the method further includes: the first threshold is adjusted according to at least one of the following factors: the maximum number of business processes that the machine can process in parallel; the maximum number of business processes within the first time window in the business scheduling process The ratio of the time to the minimum service processing time; wherein, the first time window has a preset first time length.

According to some embodiments of the present invention, it further includes: the service scheduling process further includes a second time window and a third time window, the second time window has a preset second time length, and the third time window has a preset third time length, the second time length is greater than the first time length, and the third time length is less than the first time length; in the service scheduling process, according to the first time window, For the second time window and the third time window, the corresponding first threshold, the second threshold and the third threshold are obtained, respectively, and the calculation is based on the first threshold, the second threshold and the third threshold. Computational efficiency or current business processing time of different machines scheduled by the threshold.

According to some embodiments of the present invention, the method further includes: the service scheduling method further includes: adjusting the time length of the first time window according to the calculation efficiency or the current service processing time.

According to some embodiments of the present invention, it further includes: the adjusting the time length of the first time window according to the computing efficiency or the current service processing time includes: updating the time window corresponding to the highest computing efficiency in real time as the first time window , or, regularly update the time window corresponding to the highest computing efficiency as the first time window.

According to some embodiments of the present invention, the method further includes: if the current service processing time is within a preset processing time range, the time length of the first time window remains unchanged.

In a third aspect, an embodiment of the present application further provides a service scheduling apparatus for executing the service scheduling method described in the first aspect or the second aspect.

The service scheduling apparatus according to the embodiment of the present invention has at least the following beneficial effects: by executing the service scheduling method described in the embodiment of the first aspect or the second aspect, the processing time of the machine can be reduced, thereby shortening the number of machines used in the parallel system. The total working time of the machine can improve the computing efficiency of the parallel system, thereby reducing the energy consumption and expenses of the system.

In a fourth aspect, embodiments of the present application further provide an electronic device, including: one or more processors; and a storage device for storing one or more programs, when the one or more programs are stored by the one or more programs or multiple processors execute, so that the one or more processors implement the service scheduling method according to the first aspect or the second aspect.

The electronic device according to the embodiment of the present invention has at least the following beneficial effects: by executing the service scheduling method described in the embodiment of the first aspect or the second aspect, the processing time of the machine can be reduced, thereby shortening the multiple machines used in the parallel system The total working time of the parallel system is improved, and the computing efficiency of the parallel system is improved, thereby reducing the energy consumption and expenditure of the system.

In a fifth aspect, an embodiment of the present application further provides a computer-readable storage medium storing computer-executable instructions, where the computer-executable instructions are used to execute the service scheduling method described in the first aspect or the second aspect above .

In this embodiment of the present application, by calculating the ratio between the processing time of the service to be scheduled and the processing time of the scheduled service allocated to multiple machines one by one, a machine corresponding to a scheduled service with a similar processing time is obtained, and then by scheduling the service to be scheduled to The machine can shorten the total working time of multiple machines used in the parallel system, improve the computing efficiency of the parallel system, and then reduce the energy consumption and expenses of the system.

Other features and advantages of the present application will be set forth in the description which follows, and in part will be apparent from the description, or may be learned by practice of the present application. The objectives and other advantages of the application may be realized and attained by the structure particularly pointed out in the description, claims and drawings.

Description of drawings

The present invention will be further described below in conjunction with the accompanying drawings and embodiments, wherein:

Fig. 1 is a schematic flowchart of a traditional service scheduling method;

FIG. 2 is a schematic flowchart of a service scheduling method provided by an embodiment of the present application;

3 is a schematic flowchart of a service scheduling method provided by another embodiment of the present application;

FIG. 4 is a schematic flowchart of a service scheduling method provided by an embodiment of the present application;

5 is a schematic flowchart of a specific calculation process of a fine-tuning parameter component provided by another embodiment of the present application;

6 is a schematic flowchart of a specific calculation process of a fine-tuning parameter component provided by another embodiment of the present application;

FIG. 7 is a schematic flowchart of a specific calculation process for selecting a service processing machine according to another embodiment of the present application.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application, but not to limit the present application.

It should be noted that although the functional modules are divided in the schematic diagram of the device, and the logical sequence is shown in the flowchart, in some cases, the modules may be divided differently from the device, or executed in the order in the flowchart. steps shown or described. The terms "first", "second" and the like in the description and claims and the above drawings are used to distinguish similar objects and are not necessarily used to describe a specific order or sequence.

In the description of the embodiments of the present application, unless otherwise clearly defined, words such as setting, installation, and connection should be understood in a broad sense, and those skilled in the art can reasonably determine the meaning of the above-mentioned words in the embodiments of the present application in combination with the specific content of the technical solution. specific meaning.

The embodiments of the present application will be further described below with reference to the accompanying drawings.

Existing large-scale computing systems such as clusters, parallel computing systems, and clouds include multiple machines that can perform computations. By reasonably scheduling services to different machines, the computing efficiency of the entire computing system can be effectively improved. The premise of the above-mentioned business scheduling is that the processing time of the business is a priori, that is, the business processing time can be easily predicted with high precision, while the existing business types, such as cloud games, video encoding/transcoding operations, and data analysis, etc. The business is repetitive, so its business processing time can be known in advance.

FIG. 1 is a schematic flowchart of a traditional service scheduling method. As shown in Figure 1, the traditional service scheduling method at least includes:

Step S101: Start the service scheduling process.

Step S102: Perform parameter adjustment according to the ratio of the maximum service processing time to the minimum service processing time in the service list and the maximum number of services processed in parallel.

Specifically, first, calculate the ratio μ of the maximum service processing time to the minimum service processing time in the entire service list;

Step S103: Obtain the classification.

Specifically, the total number of classifications n is calculated according to μ. Taking the maximum business processing time of 15 time units and the minimum business processing time of 1 time unit as an example, the entire business processing time can be divided into 4 categories, [1, 2), [2, 4), [4, 8) , [8, 16).

Step S104: The new service enters the computing system and waits for scheduling. Specifically, the new service _ji enters the system and waits for scheduling.

Step S105: Obtain the category to which the task belongs. Specifically, it is assumed that the processing time of service _ji is b. When C≥0, if a C≤b≤a ^{C +1} (a is a given constant) is satisfied, then the service _ji will be classified into C class. Then, service _ji is assigned to the first available machine that meets the capability requirements required to execute service _ji .

However, the method based on the above classification may lead to an inferior solution, that is, when μ is large, even the business with similar processing time will be divided into the machines belonging to the two classifications for processing. More specifically, it is assumed that at a certain point in time, two services (j _z and j _z+1 ) arrive in the system to wait for processing, and their processing time is 7.9 time units and 8 time units, respectively. Assuming that there are four categories ([1,2), [2,4), [4,8), [8,16), based on the above classification method, the business j _z will be assigned to those belonging to the category [8,16) one machine of ; meanwhile assigning business j _z+1 to one machine 105 belonging to class [4, 8). Obviously, even if the processing time of these services is similar, they are boxed and assigned to different machines for processing, which will lead to a decrease in the overall computing efficiency of the system.

In a first aspect, an embodiment of the present application provides a service scheduling method. FIG. 2 is a schematic flowchart of a service scheduling method provided by another embodiment of the present application. As shown in Figure 2, it includes at least:

Step S201: Obtain the first service processing time of the first service and the second service processing time of the second service, where the first service processing time is greater than or equal to the second service processing time.

In this embodiment, the first service and the second service may also be any two services, and the service processing times of the two services are known. In order to simplify the calculation, the processing time of the first service in this embodiment is set to be greater than or equal to the processing time of the second service. In actual calculation, as long as the service with a longer processing time is used as the first service, and the service with a shorter processing time is used as the second service; if the processing time lengths of the two services are equal, the first service and the second service can be assigned arbitrarily. .

Step S202: Obtain the ratio of the first service processing time and the second service processing time according to the first service processing time and the second service processing time.

In this embodiment, because the processing time of the first service is greater than or equal to the processing time of the second service, the ratio of the processing time of the first service to the processing time of the second service is a value greater than or equal to 1. In this step, the approximation of the processing time of the two services can be obtained.

Step S203: If the ratio is smaller than the threshold, schedule the first service and the second service to the same machine for processing.

When the ratio is less than the threshold, it means that the processing time of the two services is relatively similar, so allocating them to the same machine for processing can improve the overall computing efficiency. The above process can be called judging whether the two services are mutually exclusive, that is, if the ratio is greater than the threshold, the two services are mutually exclusive and cannot be assigned to the same machine for processing, that is, they cannot be loaded into the same box; if the ratio is less than the threshold , then the two services are not mutually exclusive, they can be assigned to the same machine for processing, that is, they can be loaded into the same box.

In some embodiments, the business scheduling method of allocating services with similar processing time to the same machine for processing can effectively improve the computing efficiency of the system, especially when the system includes multiple machines and multiple services with different processing times , which has a particularly obvious effect on improving the computing efficiency.

In some embodiments, the threshold is adjusted according to at least one of the following factors: the maximum number of service processing that the machine can process in parallel; the ratio of the maximum service processing time to the minimum service processing time in the first time window in the service scheduling process; wherein, The first time window has a preset first time length.

Those skilled in the art know that the traditional technology will calculate the ratio of the longest processing time to the shortest processing time in the service queue, so it is equivalent to a global concept. Window, the business entered in this time interval is classified as belonging to this time window, and the time window will keep sliding. In some embodiments, the first threshold is determined by the ratio of the longest service processing time in the first time window to the shortest service processing time in the first time window. The setting of the time window is equivalent to a local concept. While simplifying the calculation, it can also be calculated according to the business processing time of the business that is adjacent to the current business to be scheduled, so as to ensure the real-time update of parameters.

In a second aspect, an embodiment of the present application provides a service scheduling method. FIG. 2 is a schematic flowchart of a service scheduling method provided by another embodiment of the present application. As shown in Figure 2, it includes at least:

FIG. 3 is a schematic flowchart of a service scheduling method provided by an embodiment of the present application. As shown in Figure 3, it includes at least:

Step S301 : Acquire the processing time of the to-be-scheduled service of the current to-be-scheduled service.

In an embodiment, the currently to-be-scheduled service is an unscheduled service, and its service processing time is known.

Step S302: Acquire the scheduled service processing time set on each machine in the computing system.

In one embodiment, the computing system has multiple machines for computing, and each machine has assigned services, which are called scheduled services. Obtaining the processing time of scheduled services on each machine can form a set of scheduled service processing times, and each machine has a set, so for the computing system, there are multiple sets of scheduled service processing times.

Step S303: According to the service processing time to be scheduled and the scheduled service processing time set on each machine, calculate the ratio of the service processing time to be scheduled and each element in the scheduled service processing time set on each machine, and pass Adjust the order of the two as the numerator and denominator so that the ratio is greater than or equal to 1.

In this embodiment, the calculated ratio is still the ratio of the two service processing times. To simplify the calculation, use a longer processing time than a shorter processing time to obtain a ratio greater than or equal to 1. This method only needs to calculate the threshold at one end, which can simplify the calculation.

Step S304: If the ratio corresponding to each scheduled service processing time set is smaller than the first threshold, schedule the current to-be-scheduled service to the machine corresponding to the scheduled service processing time set for service processing.

In this embodiment, if the ratio corresponding to each scheduled service processing time set is less than the first threshold, it means that the processing time of all the services scheduled to this machine is similar to the processing time of the service to be scheduled, and the On the premise that the two services are not mutually exclusive, they can be dispatched to the same machine for processing.

It is worth noting that the first threshold is adjusted according to at least one of the following factors: the maximum number of business processing that the machine can process in parallel; the ratio of the maximum business processing time to the minimum business processing time in the first time window in the business scheduling process; wherein , the first time window has a preset first time length.

Those skilled in the art know that the traditional technology will calculate the ratio of the longest processing time to the shortest processing time in the service queue, so it is equivalent to a global concept. Window, the business entered in this time interval is classified as belonging to this time window, and the time window will keep sliding. In some embodiments, the first threshold is determined by the ratio of the longest service processing time in the first time window to the shortest service processing time in the first time window. The setting of the time window is equivalent to a local concept. While simplifying the calculation, it can also be calculated according to the business processing time of the business that is adjacent to the current business to be scheduled, so as to ensure the real-time update of parameters.

It is worth noting that the selection of the time window size will directly affect the selection of the two services with the longest processing time and the shortest in the window, which will directly affect the selection of the threshold, which in turn affects the judgment of whether the two services are mutually exclusive services.

In the above embodiment, by calculating the ratio between the processing time of the service to be scheduled and the processing time of the scheduled service that has been allocated to multiple machines one by one, the machine corresponding to the scheduled service with a similar processing time is obtained, and then by dividing the service to be scheduled Scheduling to this machine can shorten the total working time of multiple machines used in the parallel system, improve the computing efficiency of the parallel system, and then reduce system energy consumption and expenses.

FIG. 4 is a schematic flowchart of a service scheduling method provided by another embodiment of the present application. As shown in FIG. 4 , the service scheduling method provided by this embodiment at least includes:

Step S401: Start the service scheduling process.

Step S402: The new service is waiting for scheduling.

Step S403: Create three parallel service processing threads.

In some embodiments, the service scheduler will create three parallel service processing threads, and the three threads have different window sizes. If the thread with the first window serves as the main thread, the second thread serves as the auxiliary thread and has the second window. , the third thread has a third window as an auxiliary thread, and the size of the first window is between the second and third windows. The specific reason is that the size of the window of the main thread will be continuously adjusted according to the actual computing efficiency in the subsequent steps. adjustment, so at least two cases larger than and smaller than the main thread window should be considered.

Step S404: The fine-tuning parameter component adjusts the threshold value according to the ratio of the maximum service processing time to the minimum service processing time in the time window and the maximum number of services processed in parallel.

Steps S404a-S404c represent executing the above steps in three threads corresponding to different time windows.

Step S405: Obtain all machines that are not mutually exclusive with the new service.

Steps S405a-S405c represent executing the above steps in three threads corresponding to different time windows.

In some embodiments, due to the different sizes of the time windows, the selected maximum and minimum services are different, so the parameters obtained by calculation are also different, and therefore the final selected machines are also different.

Step S406: Use any packing algorithm to schedule the new service to the machine corresponding to the classification for processing.

Steps S406a-S406c represent executing the above steps in three threads corresponding to different time windows.

The above-mentioned bin packing algorithm is the common knowledge of those skilled in the art, and is not repeated in this embodiment.

Step S407: thread synchronization.

Step S408: Complete the service scheduling of the main thread.

Step S409: Select the time window corresponding to the thread with the highest computational efficiency.

Step S410: Update the time window of the main thread according to the time window of the high-performance thread.

Step S411: Update the time window component.

The time window component calculates all the input time window parameters in a time range and returns the parameter μ, and uses this as the premise for calculating the threshold.

这意味着对于不同的时间范围，最大业务时间和最小业务时间之间的比率可能不同，从而导致三个不同的(μ₁、μ₂和μ₃)比值。这表明，业务处理时间模式可能会在未来发生变化，因此用于描述这种模式的精确比值μ对于改善多机业务分配效率具有重要意义。在步骤S407过后，系统在数据库上完成主线程业务的调度，即步骤S408。同时根据高性能线程的τ更新τ₂，即步骤S410。In one embodiment, assume that traffic _ji arrives at the system at the 20th time unit, and that traffic j _x , j _y and j _z have completed scheduling at time units 5, 10 and 15, respectively. Then, at the moment of the first time window τ=10, only the services j _y and j _z are captured by the system from 200 to 210 . When a new service arrives in the system, the service scheduler creates three threads. The main thread is represented by a solid line. Auxiliary threads are indicated by dashed lines. The processing flow of each thread is the same, except that the time ranges of their time window components are different (ie, τ ₁ , τ ₂ , τ ₃ ). Each thread sends a different value of τ to the time window component. Specifically, τ ₂ represents the time window time range of the main thread, τ ₁ =Aτ ₂ (A>1),

This means that for different time horizons, the ratio between the maximum and minimum traffic times may be different, resulting in three different (μ ₁ , μ ₂ and μ ₃ ) ratios. This shows that the business processing time pattern may change in the future, so the precise ratio μ used to describe this pattern is of great significance for improving the efficiency of multi-machine business allocation. After step S407, the system completes the scheduling of the main thread service on the database, that is, step S408. At the same time, τ ₂ is updated according to the τ of the high-performance thread, that is, step S410.

The update time window may be to update the time window corresponding to the highest computing efficiency in real time as the first time window, or periodically update the time window corresponding to the highest computing efficiency as the first time window. In this embodiment, the time window is periodically updated, so the real-time update will cause fine-tuning of parameters to be performed after each scheduling. When resources are insufficient, system performance will be degraded. At the same time, if the current business processing time is at the preset value The processing time range indicates that the processing efficiency and speed of the service can meet the requirements, and the time length of the first time window can be kept unchanged.

Those skilled in the art know that the adjustment frequency and amplitude of the time window size can be in various forms, the purpose of which is to improve the rationality of service scheduling and reduce the waste of system resources. Therefore, according to the calculation efficiency of parallel threads with different time windows The methods for optimizing the time window by comparison are all within the protection scope of the embodiments of the present application.

Below, the calculation process of some specific parameters in the embodiments of the present application will be explained through flowcharts. Before that, with reference to the lemma, the lower bound of the algorithm based on the mutual exclusion threshold calculated using the scheduled service processing time ratio parameter in the embodiment of the present application is described.

Suppose k is the maximum number of services that a machine can execute at the same time, which is related to the number of cores of the machine and the load capacity of one or more machines in the processing capacity.

Formula (1) can obtain the lower bound of the traditional bin packing algorithm ALG.

f(x)=max(f ₁ (x), f ₂ (x)) (1)

Formula (2) can obtain the lower bound of the algorithm based on the mutual exclusion threshold using the existing scheduling processing time ratio parameter.

Equation (3) yields a lower bound for a mutually exclusive threshold-based algorithm using actual VM time parameters, where x represents the threshold.

Equation (4) yields a lower bound for a mutually exclusive threshold-based algorithm using the remaining traffic processing time parameter, where the remaining threshold is expressed.

Equation (5) can derive the lower bound of the mutually exclusive threshold-based algorithm using the remaining business time ratio parameter.

FIG. 5 is a schematic flowchart of a specific calculation process of the fine-tuning parameter component according to an embodiment of FIG. 4 .

--即不执行向下去整函数时的f₁；(b)一个足够小的常数δ，使得微调组件采用的二分法的左端点a非常接近但不完全等于1；(c)一个足够大的数值，用作二分法常数和的右端点；(d)前文所述常数μ和k；(e)常数N和tol，作为微调组件采用的二分法的停止条件。首先，步骤S501：从数据库检索得到历史业务处理时间比率μ_old和阈值x_old。如果μ_old等于当前μ，则该程序在设定x＝x_old后停止；如果二者不相等，则程序将使用N或

作为停止条件执行二分法，即步骤S502，找到新的阈值

如果

和

非常接近，即步骤S503判断为真，则返回

值；否则，将使用与先前二分法相同的输入值，再次执行二分法，对应步骤S504，找到新的阈值x′，区别在于其右端点等于

如果步骤504返回x′值，并且

即步骤S505，则将x′设置为右端点(即β)，对应步骤S506以保证

在上述两种情况下，流程都将返回微调阈值x′。Assuming that the packing decision is based on the existing business processing time, when considering the existing business processing time, the goal of fine-tuning the parameter component is to find a threshold x that minimizes equation (1). Threshold is a lower bound on algorithm performance. The above lower bound is based on the fact that the input value can be determined to ensure that under the condition of using the mutual exclusion criterion and its corresponding formula (2) and the traditional boxing technique (that is, any machine can receive any business) and its In the case of the corresponding formula (3), the lower limit can be maximized. The input parameters of the fine-tuning component include: (a) the function used in equation (1) (ie f ₁ , f ₂ ) and

--that is, f ₁ when the downward rounding function is not performed; (b) a sufficiently small constant δ, so that the left endpoint a of the dichotomy adopted by the fine-tuning component is very close to but not exactly equal to 1; (c) a sufficiently large Numerical value, used as the right endpoint of the dichotomy constant sum; (d) the constants μ and k described above; (e) the constants N and tol, as stopping conditions for the dichotomy employed by the trim component. First, step S501 : retrieve the historical business processing time ratio μ _old and the threshold x _old from the database. If μ _old is equal to the current μ, the program stops after setting x = x _old ; if they are not equal, the program will use N or

Perform the dichotomy as a stopping condition, i.e. step S502, find a new threshold

if

and

Very close, that is, step S503 is determined to be true, then return to

Otherwise, the same input value as the previous dichotomy will be used, and the dichotomy will be performed again, corresponding to step S504, to find a new threshold x', the difference is that its right endpoint is equal to

If step 504 returns the x' value, and

That is, in step S505, x' is set as the right endpoint (ie, β), corresponding to step S506 to ensure that

In both cases above, the flow will return to fine-tuning the threshold x'.

FIG. 6 is a schematic flowchart of a specific calculation process of the fine-tuning parameter component according to another embodiment of FIG. 4 .

Figure 6 shows a similar flow to Figure 5, except that its binning decision is based on the processing time of the remaining business. When considering the remaining business time, the goal of fine-tuning the parameter component is to find a threshold x that minimizes Eq. (4), which represents a lower bound on the performance of the algorithm taking x as a mutually exclusive threshold. The above lower bound is based on the fact that the input value can be determined to ensure that under the condition of using the mutual exclusion criterion and its corresponding formula (4) and the traditional box packing technology (that is, any machine can undertake any business) and its In the case of the corresponding formula (5), the lower limit is maximized.

被替换为g₁、g₂和

其中，

实际上是不执行向下取整函数的g₁。图6所示流程与图5所示流程基本相同，唯一的不同在于步骤S504和步骤S506，其中，“无”输出值和单一输出值不作为最终输出值，而是作为步骤S606的输入值。如果步骤S606的输入值(即x′)不超过公差，则取x′作为最终输出值。否则，将使用N或|g₁-g₂|＜tol作为停止条件执行二分法，找到新的阈值x″，取S607的输出值作为最终输出值。The input parameters of the fine-tuning component shown in Fig. 6 are the same as those of Fig. 5, except that f ₁ , f ₂ and

are replaced by g ₁ , g ₂ and

in,

It is actually g ₁ that does not perform the round-down function. The process shown in FIG. 6 is basically the same as the process shown in FIG. 5 , with the only difference being in steps S504 and S506 , wherein the “none” output value and the single output value are not used as the final output value, but as the input value in step S606 . If the input value (ie x') of step S606 does not exceed the tolerance, take x' as the final output value. Otherwise, the dichotomy will be performed using N or |g ₁ -g ₂ |<tol as the stopping condition, a new threshold x″ will be found, and the output value of S607 will be taken as the final output value.

FIG. 7 is a schematic flowchart of a specific calculation process for selecting a service processing machine according to another embodiment of FIG. 4 .

The goal of this process is to recommend a set of active machines for each incoming business within the system. The input parameters include the following three parameters: (a) mutual exclusion threshold x; (b) di (that is _, the processing time of business _ji ); and (c) indicating whether the packing decision is based on the existing business processing time or the remaining business processing judgment of time. First, step S701 creates an empty list CM of candidate machines. Then, step S702 iteratively scans the entire active machine list to obtain more available candidate machines. The candidate machines must meet the following rules: for any two received services, their processing time ratio is less than x, where the numerator is the middle of the service. The maximum processing time of , and the denominator is the minimum processing time of the business. Regardless of whether the completed processing time or the remaining processing time of each service is selected, the above rules apply to the judgment in step S703. It should be noted that d _max represents the longest processing time among all the services installed on the machine, and d _min represents the shortest processing time among all the services installed on the machine. In addition, R ₁ represents the ratio between the maximum value and the minimum value between d _max and d _i ; R ₂ represents the ratio between the maximum value and the minimum value between d _min and d _i . If the packing decision is made based on the processing time of the completed business, step S705 is selected to be executed; otherwise, step S704 is selected to be executed. Suppose that the current business boxing operation of a machine m meets the condition x. If machine m is to receive service _ji and still meet the conditions of x, it is necessary to ensure that the service still satisfies the above rules after packing. When R ₁ and R ₂ satisfy the judgment condition of step S707 at the same time, the above rules are equivalent. To see why the above rules apply, consider the following: (i) when d _i < d _min , if R ₁ applies, it means that for all transactions j _z in machine m, d _i /d _z < x also applies; (ii) when d _i > d _max , if R ₂ applies, it means that for all services j _z in machine m, d _z /d _i <x also applies; (iii) when d _i ∈ [d _min , d _max ], the above rules apply; otherwise, the binning before business j _i arrives must not meet the mutual exclusion threshold condition, which contradicts the initial assumption.

In the above embodiment, the configuration process of parameters in the service scheduling method is described in detail. By calculating the ratio between the processing time of the service to be scheduled and the processing time of the scheduled services that have been allocated to multiple machines one by one, the processing time of the service close to its processing time is obtained. Scheduling the machine corresponding to the service, and then by scheduling the service to be scheduled to the machine, the total working time of multiple machines used in the parallel system can be shortened, the computing efficiency of the parallel system can be improved, and the system energy consumption and expenses can be reduced.

In a third aspect, the embodiments of the present application provide a service scheduling apparatus for executing the service scheduling method provided by the embodiments of the first aspect and/or the second aspect.

In a fourth aspect, embodiments of the present application provide an electronic device, including one or more processors; a storage device for storing one or more programs, when the one or more programs are executed by the one or more processors , so that one or more processors implement the service scheduling method described in the first aspect and/or the service scheduling method described in the second aspect.

In a fifth aspect, embodiments of the present application further provide a computer-readable storage medium storing computer-executable instructions for executing the method of the first aspect and/or the second aspect as described above. .

The apparatus embodiments described above are only illustrative, and the units described as separate components may or may not be physically separated, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution in this embodiment.

Those of ordinary skill in the art can understand that all or some of the steps in the methods disclosed above, functional modules/units in the systems, and devices can be implemented as software, firmware, hardware, and appropriate combinations thereof. In a hardware implementation, the division between functional modules/units mentioned in the above description does not necessarily correspond to the division of physical components; for example, one physical component may have multiple functions, or one function or step may be composed of several physical components Components execute cooperatively. Some or all physical components may be implemented as software executed by a processor, such as a central processing unit, digital signal processor or microprocessor, or as hardware, or as an integrated circuit, such as an application specific integrated circuit . Such software may be distributed on computer-readable media, which may include computer storage media (or non-transitory media) and communication media (or transitory media). As known to those of ordinary skill in the art, the term computer storage media includes both volatile and nonvolatile implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules or other data flexible, removable and non-removable media. Computer storage media include, but are not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disk (DVD) or other optical disk storage, magnetic cartridges, magnetic tape, magnetic disk storage or other magnetic storage devices, or may Any other medium used to store desired information and which can be accessed by a computer. In addition, communication media typically embodies computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism, and can include any information delivery media, as is well known to those of ordinary skill in the art . The mobile terminal device can be a mobile phone, a tablet computer, a notebook computer, a handheld computer, a vehicle terminal device, a wearable device, a super mobile personal computer, a netbook, a personal digital assistant, a CPE, a UFI (wireless hotspot device), etc.; Specific restrictions.

The above is a specific description of the preferred implementation of the application, but the application is not limited to the above-mentioned embodiments. Those skilled in the art can also make various equivalent deformations or replacements on the premise of not violating the spirit of the application. These Equivalent modifications or substitutions are included within the scope defined by the claims of the present application.

Claims (11)

1. a service scheduling method, is characterized in that, comprises: Obtain the first service processing time of the first service and the second service processing time of the second service, where the first service processing time is greater than or equal to the second service processing time; obtaining the ratio of the first service processing time to the second service processing time according to the first service processing time and the second service processing time; If the ratio is smaller than the threshold, the first service and the second service are scheduled to be processed on the same machine. 2. The service scheduling method according to claim 1, wherein the threshold is adjusted according to at least one of the following factors: the maximum number of business processes that the machine can process in parallel; The ratio of the maximum service processing time to the minimum service processing time in the first time window in the service scheduling process; wherein the first time window has a preset first time length. 3. A service scheduling method, characterized in that, for a parallel system with two or more machines, comprising: Obtain the processing time of the to-be-scheduled service of the current to-be-scheduled service; Acquire a set of scheduled business processing times on each machine in the parallel system; According to the to-be-scheduled service processing time and the scheduled service processing time set on each machine, respectively calculate the to-be-scheduled service processing time and each element in the scheduled service processing time set on each machine The ratio of , and by adjusting the order of the two as the numerator and denominator, the ratio is greater than or equal to 1; If the ratio corresponding to each scheduled service processing time set is smaller than the first threshold, the current to-be-scheduled service is scheduled to the machine corresponding to the scheduled service processing time set for service processing. 4. The service scheduling method according to claim 3, wherein the first threshold is adjusted according to at least one of the following factors: the maximum number of business processes that the machine can process in parallel; The ratio of the maximum service processing time to the minimum service processing time in the first time window in the service scheduling process; wherein the first time window has a preset first time length. 5. The service scheduling method according to claim 4, wherein the service scheduling process further comprises a second time window and a third time window, the second time window has a preset second time length, and the The third time window has a preset third time length, the second time length is greater than the first time length, and the third time length is less than the first time length; in the service scheduling process, according to the The first time window, the second time window and the third time window, the corresponding first threshold, the second threshold and the third threshold are obtained, respectively, according to the first threshold, the second The computing efficiency or current service processing time of different machines scheduled by the threshold and the third threshold. 6. The service scheduling method according to claim 5, wherein the service scheduling method further comprises: The time length of the first time window is adjusted according to the calculation efficiency or the current service processing time. 7. The service scheduling method according to claim 6, wherein the adjusting the time length of the first time window according to computing efficiency or current service processing time comprises: The time window corresponding to the highest computing efficiency is updated in real time as the first time window, or the time window corresponding to the highest computing efficiency is regularly updated as the first time window. 8. The service scheduling method according to claim 5, wherein the service scheduling method further comprises: If the current service processing time is within the preset processing time range, the time length of the first time window remains unchanged. 9. A service scheduling apparatus, configured to execute the service scheduling method according to any one of claims 1 to 2, and/or the service scheduling method according to any one of claims 3 to 8. 10. An electronic device, comprising: one or more processors; storage means for storing one or more programs which, when executed by said one or more processors, cause said one or more processors to implement The service scheduling method according to any one of claims 1 to 2, and/or the service scheduling method according to any one of claims 3 to 8. 11. A computer-readable storage medium storing computer-executable instructions for executing the service scheduling method according to any one of claims 1 to 2, and/or claims 3 to 8 Any one of the service scheduling methods.

Images