CN101018192A - Grid workflow virtual service scheduling method based on the open grid service architecture - Google Patents

Abstract

The grid workflow virtual service scheduling method based on the open grid service architecture belongs to the workflow scheduling technology method under the grid. The workflow virtual service PVS composed of the scheduling scheme generation module uses a large number of idle resources in the grid environment to continuously find better scheduling strategies for the defined PVS, update and store them in the scheduling scheme candidate pool of PVS; and then use the scheduling scheme When the specific task instance arrives, the scheme execution module selects the current better scheduling scheme from the selected pool of PVS scheduling schemes for job scheduling. Only when no suitable scheduling scheme can be found, it communicates with the scheduling scheme generation module. Wait for the arrival of the new scheduling scheme within the specified time. The invention has the advantages of reducing repeated scheduling, accelerating resource reservation, reducing job completion time, increasing job throughput, and improving resource utilization.

Description

Grid Workflow Virtual Service Scheduling Method Based on Open Grid Service Architecture

technical field

The invention relates to a workflow scheduling method in a grid environment, in particular to grid task scheduling through pre-scheduling, QoS guarantee and continuous optimization mechanism.

Background technique

With the progress of grid technology and the increase of demand, grid workflow (Grid Workflow) has become an important class of grid applications. A grid workflow application can be regarded as composed of a group of work segments (services in the grid), and these services need to be executed in a pre-booked order to complete a complex goal. Generally speaking, a workflow is an abstract form that includes a group of work segments, and what algorithm to use to match services and grid resources to obtain an executable workflow instance and put it into operation is an important issue in current research, called Scheduling for grid workflows. When designing a scheduling algorithm, in order to improve performance, it often needs to be combined with specific grid workflow applications. In different application environments (such as homogeneous/heterogeneous, data-intensive applications/computing-intensive applications, etc.), the performance of different workflow scheduling algorithms will be very different. Due to the dynamics and complexity of grid resources, grid workflow scheduling generally adopts a dynamic scheduling method. When scheduling, it is usually desirable to select an optimal or nearly optimal scheduling scheme. It is an NP-hard problem to match the work segments of the workflow with the grid resources to find the optimal scheduling scheme. Therefore, heuristic scheduling algorithms are generally used in scheduling: such as Min_Min heuristic, Max_min heuristic, and suffering heuristic algorithms. However, the heuristic algorithm can only find a better solution under normal circumstances, and sometimes it is far from the best solution.

In addition, the currently used grid workflow scheduling methods all have a common assumption, that is, the scheduling of each execution instance of the same workflow is independent. However, in many practical applications, due to the same workflow structure, multiple execution instances within a certain time range can sometimes share the same scheduling scheme, so that there is no need to call a scheduling algorithm for an execution instance every time. If for a workflow, the scheduling time accounts for a large proportion of the entire task completion time, then according to the current scheduling mode, for multiple execution instances, a lot of time is wasted on repeated scheduling, only relying on the scheduling algorithm Improvement, performance improvement is also limited.

Introducing grid QoS into the scheduling method is also one of the current issues that need to be considered. Quite a few of the current grid pipeline scheduling also introduce QoS guarantee mechanisms, but they are often only considered from a single aspect, and there is no relatively accurate and flexible mechanism for selecting QoS guarantees according to different applications.

Contents of the invention

The purpose of the present invention is to propose a grid workflow scheduling method based on the Open Grid Service Architecture (OGSA), to solve the problem of repeated scheduling for different instances of the same workflow, while also taking into account the completion time and fault tolerance , QoS guarantee in three aspects of security.

The present invention is characterized in that following steps are arranged in sequence:

(1) Initialization: a scheduling scheme generation module and a scheduling scheme execution module are respectively established in the scheduling scheme generator and the executor.

(2) The dispatching plan generation module judges whether there is a request signal sent from the dispatching execution module: if not, the dispatching plan generation module cyclically generates corresponding dispatching plans for all PVSs set by the system.

(3) The scheduling scheme executor selects a specific scheduling scheme according to the received user PVS execution command according to the following steps, and reserves and executes the scheduling scheme.

In general, the scheduling method uses a possible scheduling scheme of PVS as the common information sharing of the PVS, introduces QoS guarantee, pre-scheduling, resource reservation and other mechanisms, thereby reducing repeated scheduling, speeding up resource reservation, reducing job completion time, and increasing job throughput and improve resource utilization.

The performance advantages of the scheduling scheme in the present invention are shown in Fig. 4 and Fig. 5 . Among them, the comparative scheduling scheme adopts the Min_Min algorithm, which is currently more general and more efficient heuristic scheduling algorithm. It can be seen from FIG. 4 and FIG. 5 that if the ratio of the scheduling time to the actual execution time is larger, the performance of scheduling according to the scheme of the present invention is better.

Description of drawings

Fig. 1 is the flow chart of the overall PVS scheduling method of the present invention: (a) execution flow chart of dispatching plan generation module; (b) execution flow chart of dispatching plan execution module.

Fig. 2 is a structural diagram of the scheduling module of the present invention: the input parameters are: (PVS name, data source).

Fig. 3 is a method diagram of the scheduling execution module in the present invention.

Fig. 4 is a time saving rate diagram comparing the scheduling method in the present invention and the comparative scheduling method.

FIG. 5 is a comparison chart of resource utilization between the scheduling method of the present invention and the comparative scheduling method.

Fig. 6 is the quick view analysis PVS in the concrete example astronomical data processing in the present invention

Detailed ways

The present invention is mainly to solve the repeated scheduling problem of different instances of the same workflow (referred to as PVS in the present invention) in the grid workflow scheduling, and at the same time add QoS guarantees in three aspects of completion time, fault tolerance and security. Separating the generation of the scheduling plan from the execution of the scheduling plan, so that the generation of the scheduling plan can make full use of the idle resources in the grid system, and the scheduling plan can be generated before the job arrives, so that the PVS instance can be put into execution as soon as possible when it arrives, saving the traditional Lookup match time in dispatch method. At the same time, the generation of each scheduling scheme is based on the generation of previous scheduling schemes, so that it can gradually approach the optimal solution according to the change of the grid environment.

In the execution part of the scheduling plan, a reservation mechanism is adopted, that is, to reserve resources for all work segments in a PVS according to the selected scheduling plan (here "resource" refers to the grid system that can execute the deployment of the work segment in the system The specific services in the system and the required hardware and software resources), which improves the resource utilization in the system and reduces the waiting time of the job. At the same time, the reservation mechanism reserves resources of different capabilities for PVS according to different levels of PVS, which reduces the probability of blocking and further improves resource utilization.

The PVS scheduling scheme is applicable to all grid systems based on the open grid service architecture. It is mainly composed of two modules: a scheduling scheme generation module (1) and a scheduling scheme execution module (2).

(1) Scheduling scheme generation module

●Function: Responsible for generating corresponding scheduling schemes for each PVS in the system.

●Interface: This module mainly has two interfaces, as shown in Figure 2, one is the interface (10) with the dispatching scheme execution module, and the other is the interface (11) for invoking specific resources in the grid.

(2) Scheduling scheme execution module

●Function: responsible for the implementation of specific examples.

●Interface: as shown in Figure 2, the dispatching plan execution module has a user interface (9), which can receive the user's command to execute PVS; and the interface (10) with the dispatching plan generation module.

PVS (Pipeline Virtual Service) is a core concept in this scheduling method. It is a six-tuple, and the specific description is as follows:

PVS=<work segment set (3), dependency description (4), input parameter description (5), output parameter description (6), PVS authority (7), scheduling scheme candidate pool (8)>.

The working segment set (3) is a set of limited working segments. It describes which basic work segments a PVS consists of. The work segments here are abstract concepts, not associated with specific resources in the grid, and are scheduled to be executed on related resources only when the PVS instance is executed.

Dependency description (4), which is a directed acyclic graph, is used to describe the dependency of each activity in (3). Each node in the figure represents a working segment in PVS. Directed edges represent dependencies (data dependencies or control dependencies) between work segments. If the execution of work segment A depends on the completion of the execution of work segment B, node Ai has an edge pointing to the node. A node without an incoming edge is a source node, and a node without an outgoing edge is a destination node.

The PVS authority (7) represents the authority of the PVS. The larger the value of (7), the higher the priority of the PVS. Generally speaking, only users with authority not lower than (7) can call this service (this property is optional).

The scheduling scheme candidate pool (8) is a PVS scheduling scheme set, including Num (this value is given by the user when the algorithm is implemented) ordered records. A scheduling scheme = <P, makespan, security, performance>. P is a specific scheduling scheme. Makespan predicts the completion time of the job under this scheduling scheme, that is, the time from when the user submits the job to PVS to when the result is obtained. Security and performance are the security level and fault tolerance level under this scheduling scheme. In general, the higher the values of Security and performance, the better the performance of these two aspects of the scheduling scheme. The three values of Makespan, security and performance are given by the specific scheduling algorithm adopted by the user.

The input parameter description (5) and the output parameter description (6) can be a file described by WSDL, used to describe the parameter information required when the PVS is executed, or a grid service (Web service) responsible for input and output.

Once a PVS is configured, it can be shared as a service on the grid. (3)(4)(5)(6)(7) are determined during configuration, and the records in (8) change with the increase of calls to this PVS job.

To sum up, a PVS can be regarded as an encapsulation of a workflow, where (3) and (4) in PVS are the basic definition of a grid workflow, and (5) is the definition of a workflow without a predecessor node (6) is an abstract description of the output parameters of no successor nodes in the workflow, and (8) is equivalent to a set of candidate scheduling schemes for a workflow.

The basic composition of PVS is described above, but in specific applications, the expression method can be different.

The specific flowchart of the PVS scheduling method is shown in FIG. 1 . The scheduling plan generation module and the scheduling plan execution module are two relatively independent threads, or they can also be executed on two different processors.

The specific explanation of the process in Figure 1(a) is as follows. In the scheduling plan generating module, once there is idle computing resource in the grid, the scheduling plan generating module will be executed. This part cyclically updates the already defined PVS scheduling scheme candidate pool (8). The details are as follows: Suppose the system has N PVS, PVS1, PVS2, ..., PVS N in turn. For each PVS i (1<=i<=N), the scheduling scheme generation module (1) adopts the defined resource scheduling matching algorithm to obtain a scheduling scheme. In this resource scheduling matching algorithm, the user can select an existing heuristic algorithm or a search algorithm according to specific application conditions. The general situation is that the user provides an algorithm resource pool, and the system selects different algorithms according to different situations. After obtaining a scheduling plan, calculate the makespan, security and performance values of the scheduling plan according to the user definition, and compare it with the existing scheduling plan of the PVS, if the number of scheduling plans stored in (8) of the PVS is less than the maximum storage number , then directly add the new scheduling scheme, otherwise, replace a scheduling scheme that is worse than the new scheduling scheme. Then the next PVS is processed. If the scheduling plan execution module has a demand, it will send a signal to the scheduling plan generation module, so that the scheduling plan generation module will generate an interrupt after executing the current PVS processing, and give priority to the request sent by the scheduling plan execution module. Continue to execute.

The specific explanation of the flow in Fig. 1(b) is as follows. In the scheduling plan execution module, once a job arrives, that is, there is a PVS call request, the scheduling plan execution module judges whether the scheduling plan is currently available according to the values of makespan, security, and performance in (8) of the PVS, that is, Whether the resources involved in the scheduling scheme are currently available. As long as a resource is unavailable (for example, the site providing the resource is broken), the scheduling scheme becomes invalid and is deleted from the PVS (8). until a currently available schedule is found. At this time, a PVS instance is generated, and each work segment in the PVS is matched with the resources in the scheduling plan, and the overall reservation is made at the same time. After the reservation is completed, start to execute the PVS instance. If all scheduling schemes in (8) of the current PVS are not available, then the scheduling scheme execution module sends an interrupt signal to the scheduling scheme generation module at this time, and the request scheduling scheme generation module produces an available scheduling scheme for this PVS as soon as possible, and then The scheduling scheme execution module waits for a time specified by the user, and re-judges whether the PVS has an available scheduling scheme.

Figure 2 shows an example diagram of a scheduling module using the PVS scheduling method.

In the scheduling plan execution module, in order to adapt to the distribution of the grid, a two-tier scheduling model is adopted, namely global scheduling and PVS scheduling. As shown in Figure 3. Among them, there may be multiple PVS scheduling, which are distributed on different servers. When a user command is submitted to the global scheduler, the global scheduler assigns it to an appropriate PVS scheduler, and then the PVS scheduler executes a specific scheduler.

Take snapshot analysis in astronomical data processing as an example. The snapshot analysis PVS configured according to the processing flow is shown in Figure 6. The data collection of astronomical telescopes is continuous, and the PVS needs to be called repeatedly within a certain time range. After the system is started, the dispatching plan generating module continuously utilizes the idle resources in the grid system to generate a dispatching plan for Quick View Analysis PVS. Once the collected data packets arrive, a new quick-view analysis PVS execution instance will be generated in the scheduling plan execution module, and a suitable scheduling plan will be selected from the corresponding scheduling plan candidate pool for resource reservation and execution.

Claims (3)

1. A grid workflow virtual service scheduling method based on the open grid service architecture, characterized in that the method is implemented in the scheduling plan generator and the scheduling plan executor in all grid systems based on the open grid service architecture The generator and the executor are both composed of independent network processors to form a scheduling device, and the method is executed sequentially according to the following steps: Step (1) Initialize Establish a scheduling scheme generation module and a scheduling scheme execution module in the scheduling scheme generator and the executor; respectively define a same workflow virtual service six-tuple in the two modules, expressed as: PVS=<set of working segments, description of dependencies, description of input parameters, description of output parameters, PVS authority, pool of alternative scheduling schemes>, where: The set of working segments is a limited set, described as a basic working segment of PVS, which is dispatched to related resources and given specific services for execution only when PVS is actually executed; here "resource" refers to the grid system that can execute The specific services deployed in the system and the hardware and software resources required by the work segment; Dependency description, which is a directed acyclic graph, used to describe the data dependency or control dependency between the various components in the set of work segments; a node on the way represents a work segment in PVS, and directed edges represent each Dependencies between components, the source node has no incoming edges, and the destination node has no outgoing edges; PVS authority, representing the authority of PVS, the larger the value, the higher the priority; this item is optional; Scheduling scheme candidate pool is a collection of PVS scheduling schemes; it contains at most Num ordered scheduling schemes for users to choose; the value of Num can be set when configuring PVS. A scheduling scheme=<P, makespan, security, performance>; among them, P is the specific scheduling scheme of the PVS; makespan is the predicted completion time of the PVS instance under the scheduling scheme; security and performance are respectively under the scheduling scheme The higher the value, the better the performance; the selected three values of makespan, security and performance are given by the scheduling algorithm specifically adopted by the user, and the workflow is determined by the specific dependencies of the work segment composition; Input parameter description, output parameter description, using the World Wide Web Service Description Language WSDL file released by W3C, used to describe the parameter information required for PVS execution; The scheduling scheme generation module generates a corresponding scheduling scheme for each PVS in the system, and is provided with: an interface with the scheduling scheme execution module, calling the scheduling algorithm resource pool and the scheduling algorithm resource pool provided by the user including the heuristic scheduling algorithm and The interface of the scheduling algorithm corresponding to the PVS submitted by the user, and the interface for sending the generated PVS to the scheduling scheme candidate pool in the PVS six-tuple in the scheduling scheme execution module or selecting the scheduling scheme from the scheduling scheme candidate pool; The dispatching plan execution module is responsible for the execution of the example proposed by the user; it is provided with: an interface for receiving user PVS execution commands, an interface for receiving the dispatching plan provided by the dispatching plan generation module, and sending an interrupt signal to the dispatching plan generation module, and An interface for requesting each block to generate a request signal for an available scheduling scheme for the PVS proposed by the user; Step (2) dispatching scheme produces module, judges whether there is the request signal that sends from dispatching execution module; If not, this dispatching scheme produces module and produces corresponding dispatching scheme for all PVS that system is set cyclically, and its steps are as follows successively: Step (2.1) judges whether the system has idle resources, if not, then judges whether it is over; if there are idle resources, then executes the next step; Step (2.2) selects the next PVS in sequence Step (2.3) A scheduling scheme obtained according to a preset resource scheduling matching algorithm including a heuristic algorithm or a search algorithm selected by the user according to specific conditions; Step (2.4) Calculate the three values of makespan, security and performance according to the selected scheduling algorithm in step (2.3), and compare their three values with the specified QoS standard; If the number of scheduling schemes is less than the set maximum storage number, then directly add the scheduling scheme obtained in step (2.3) into the scheduling scheme candidate pool; if the scheduling scheme number in the scheduling scheme candidate pool has reached the maximum storage number number, then replace a scheduling scheme that is worse than the scheduling scheme described in step (2.3), and update the scheduling scheme alternative pool of PVS; Step (2.5), judge whether to have cycled all PVS once, if have cycled, just judge whether to end, otherwise, continue to circulate, until there is interrupt request signal to send from scheduling execution module; Step (3), the dispatching plan executor selects a specific dispatching plan and executes the dispatching plan according to the received user PVS execution order according to the following steps; Step (3.1) the scheduling scheme executor selects the corresponding scheduling scheme for the PVS from the scheduling scheme candidate pool according to the received user PVS execution order; Step (3.2) judges whether there is an available scheduling scheme; If: in the selected scheduling plan, even if only one resource required for the execution of the work segment is currently unavailable, the scheduling plan is considered invalid and deleted from the scheduling plan candidate pool until an available scheduling plan is found; Step (3.3) Reserving and matching each work segment in the PVS to be executed by the user with the required resources according to the selected scheduling scheme, forming a PVS instance, and executing the PVS instance; Step (3.4) if all the scheduling schemes in the scheduling scheme candidate pool are unavailable, then at this moment, the scheduling scheme execution module sends an interrupt request signal including the user PVS identification to the scheduling scheme generation module, and at a time specified by the user Within, accept the new scheduling scheme, and re-judge whether it is applicable to the PVS sent by the user. 2. The grid workflow virtual service scheduling method based on the open grid service architecture according to claim 1, characterized in that, the scheduling scheme execution module is provided with a reservation mechanism, and different grades are provided according to different levels of PVS. A user's PVS reserves resources of different capabilities. 3. The grid workflow virtual service scheduling method based on the open grid service architecture according to claim 1 is characterized in that, the affiliated scheduling program execution module adopts a two-layer scheduling mode of global scheduling and PVS scheduling, and the PVS The scheduling module is located on multiple different servers. When the user's PVS execution command is submitted to the global scheduling module, the global scheduling module assigns it to the appropriate PVS scheduling module. After that, the PVS scheduling module executes the specific scheduling plan.

Images