Using stages to handle dependencies in parallel tasks

Technologies are described herein for using stages for managing dependencies between tasks executed in parallel. A request for permission to execute a task from a group or batch of tasks is received. The specified task is retrieved from a task definition list defining a task ID, stage, and maximum stage for each task in the group. If another pending or currently running task exists with a stage and maximum stage less than the stage defined for the retrieved task, then the retrieved task is not allowed to run. If no other pending or currently running task exists with a stage and maximum stage less than the stage defined for the retrieved task, then the permission to execute the specified task is given.

BACKGROUND

A system administrator or developer in a computer system environment may often be required to execute a large list of tasks or processes. The easiest way to schedule the list of tasks is to run them sequentially. This solution may not be optimal, however, because of underutilized execution resources and increased total time of execution of the tasks.

While running the tasks in parallel may be more efficient, it may also be more complicated due to dependencies that exist between tasks in the list. For example, some tasks may temporarily change the topology of the system in such a way that other tasks running in parallel would fail. Other tasks may depend upon the output or changes to data generated by previously executed tasks in the list.

An optimum approach may be to run as many tasks in the list in parallel as possible while taking into consideration these dependencies between tasks. However, analyzing dependencies between large numbers of tasks to produce an execution schedule may be complex. In addition, frequent changes to the environment may require the dependencies be changed frequently, and maintenance of the complex set of dependencies may be difficult and costly.

SUMMARY

Technologies are described herein for using stages for managing dependencies between tasks executed in parallel. Utilizing the technologies presented herein, extra abstraction layer “stages” may be added to the definition of a group or batch of tasks to be executed in order to handle dependencies that may exist between tasks. Using stages defined for each task may allow a maximum number of tasks to be executed in parallel while preventing tasks with dependencies from executing at the same time. In addition, each task is mapped to only one rule, i.e. a stage and maximum stage, defined for each task, making the maintenance of the task definitions manageable and the solution highly scalable.

According to embodiments, a request for permission to execute a task from the group or batch of tasks is received. The specified task is retrieved from a task definition list defining a task identifier (“ID”), stage, and maximum stage for each task. If another pending or currently running task exists with a stage and maximum stage less than the stage defined for the retrieved task, then the specified task is not allowed to run. If no other pending or currently running task exists with a stage and maximum stage less than the stage defined for the retrieved task, then permission to execute the specified task is given.

DETAILED DESCRIPTION

In the following detailed description, references are made to the accompanying drawings that form a part hereof and that show, by way of illustration, specific embodiments or examples. In the accompanying drawings, like numerals represent like elements through the several figures.

FIG. 1shows an illustrative operating environment100including several software components for using stages for managing dependencies between tasks executed in parallel, according to embodiments provided herein. The environment100includes an application server102. The application server102may represent one or more conventional server computers, Web servers, database servers, or network appliances. Alternatively, the application server102may represent a user computing device, such as a personal computer (“PC”), a desktop workstation, a laptop, a notebook, a mobile device, a personal digital assistant (“PDA”), and the like. It will be appreciated that the application server102may represent any server computers or user computing devices known in the art.

The application server102executes a task dependencies management module104. According to one embodiment, the task dependencies management module104is responsible for managing the dependencies in the parallel execution of a number of tasks106A-106N (referred to herein generally as tasks106) on a number of execution resources108A-108N (referred to herein generally as execution resources108) in the operating environment100. The task dependencies management module104may be implemented as hardware, software, or a combination of the two. The task dependencies management module104may be an add-in or component of a batch processing system, a software testing suite, or the like, and may include a number of application program modules and other components executing on the application server102and/or other computers or computing devices.

The tasks106may include any computer-executable instructions presented in any form, such as software programs, application modules, database scripts, stored procedures, system scripts, testing profiles, and the like. The execution resources108may include computing resources for executing the tasks, such as CPUs, virtual machines, execution threads, runtime engines, batch processors, database engines, testing engines, and the like. The execution resources108may be provided by the application server102and/or one or more other computers or computing devices in the operating environment100.

According to embodiments, the tasks106for parallel execution are defined in a task definition list110. The task definition list110includes a definition of each task106to be executed. In one embodiment, the definition of each task106in the task definition list110comprises a tuple including a task ID identifying the task to be executed, a numeric stage of execution for the task, and a maximum stage indicating a maximum stage of execution that can be executed in parallel with the task. The stage and maximum stage of each task are used by the task dependencies management module104to determine which tasks106defined in the task definition list110may be executed in parallel. The stages and maximum stages defined in the task definition list110may be based on the dependencies between the tasks. According to embodiments, each task106is assigned to only one stage, and each stage may contain multiple tasks. Tasks106assigned to the same stage may run in parallel. In addition, all the tasks106assigned to stages that are less than a current maximum stage can also be executed in parallel.

Therefore, the task dependencies management module104may determine if a particular task106may be executed based on the stage and/or maximum stage of all other pending or running tasks. Particularly, a task A with stage SA and maximum stage MA will be allowed to execute unless another task B is pending or currently running with stage SB less than SA and maximum stage MB less than SA. For example, the task definition list110may include four tuples defining four tasks A, B, C, and D, as shown below in Table 1.

According to the task definitions shown in Table 1, task A will be allowed to execute at any time, since no other defined task has a maximum stage less than the stage SA of task A, i.e. MB>=SA, MC>=SA, and MD>=SA. Task B may also execute at any time for the same reasons (MA>=SB, MC>=SB, and MD>=SB). However, task C may only execute after task B is complete, because while the maximum stage MA of task A and the maximum stage MD of task D are both greater than or equal to the stage SC, i.e. MA>=SC and MD>=SC, the maximum stage MB of task B is less than the stage SC. Similarly, task D may only be executed alone, once tasks A, B, and C are complete (MA<SD, MB<SD, MC<SD).

In one embodiment, the task definition list110may comprise an extensible markup language (“XML”) file with a node defining each task106.FIG. 2shows a sample portion of XML200from a task definition list110, according to the embodiment. The XML200may include a Task node202for each task106. The task node202may include a Name attribute204identifying a script, profile, or definition of the associated task106. The task node202also includes a Stage attribute206specifying the numeric stage of the task, and a MaximumStage attribute208specifying the maximum stage. For example, as shown inFIG. 2, a task106identified as “BVT_Client-BecWebService.xml” may have a stage of “001” and a maximum stage of “019.” In another embodiment, the Task nodes202may be grouped under a parent node, such as a Batch, Group, or Cycle node, with its own name or identifier, and multiple batches or groups may be defined in the task definition list110.

According to the task definition list110defined by the XML200, all tasks106in the listing except “BVT_SubscriptionExtendedTests.xml” and “UnlistedBVTProfiles” would be allowed to run in parallel with the task “BVT_Client-BecWebService.xml.” Similarly, the task “BVT_AuthZExtendedTests.xml” is set to execute in stage “001,” but only other tasks assigned to stage “001” may run in parallel with the task. Therefore, the task “BVT_Aws.xml,” which is set to execute in stage “002,” will not be allowed to execute until the “BVT_AuthZExtendedTests.xml” has completed.

In other embodiments, the task definition list110may be stored in a delimited flat file, a database table, or any other mechanism known in the art for storing structured data. As further shown inFIG. 2, each task106has only one associated entry in the task definition list110, making the listing easy to maintain and ensuring that the solution scales well. The concept of stages may also allow for increased maintainability as it groups parallel tasks in the same stage. Once the tasks are mapped to stages in the task definition list110, the task dependencies management module104need only read the stage configuration and base the decision whether to run a task on the stage and maximum stage data. There is no extra design effort required from system administrators or developers.

According to one embodiment, the task dependencies management module104reads and parses the task definition list110in order to provide an indication of whether a particular task is allowed to execute or not upon request for permission to execute the task from an execution resource108. The task dependencies management module104may implement an application programming interface (“API”)114that is used by the execution resources108to determine whether tasks106may be executed based on the defined dependencies. When an execution resource108becomes available, the execution resource may utilize the API114to request permission to execute a particular task106from the task dependencies management module104by specifying the task ID, such as the task Name attribute206, for example. The task dependencies management module104may utilize the stage and maximum stage defined for the identified task106in the task definition list110, along with knowledge of the completed and currently executing tasks, to determine if the requested task can currently be executed, using a procedure similar to that described below in regard toFIG. 3. The task dependencies management module104may then return an indication of whether the specified task106may currently be executed to the requesting execution resource108.

The execution resources108may also utilize the API114to update the task dependencies management module104on the completion of a particular task106as well as whether the task completed successfully or not. The task dependencies management module104may track the completed tasks106and/or the currently executing tasks in an executed task list112. The executed task list112may be utilized to determine whether a particular task106may be executed, as described above. The executed task list112may be stored in a memory of the application server102, or may be stored in a database or other storage mechanism accessible by the server.

According to another embodiment, the task dependencies management module104reads the task definitions from the task definition list110and initiates execution of the defined tasks106in stage order on the available execution resources108in the environment100. The task dependencies management module104may further monitor execution of the tasks106on the execution resources108to determine when a task completes and an execution resource becomes available. Upon completion of a task106and/or an execution resource108becoming available, the task dependencies management module104utilizes the stage and maximum stage defined for each task to determine which task(s) may be executed next.

In a further embodiment, the task definition list110is parsed and the task definitions contained therein are stored in a table of a database on the application server102. The executed task list112may also be stored in the database, and the functionality required by the task dependencies management module104to determine whether a particular task may execute, as will be described below in regard toFIG. 3, may be implemented in stored procedures. The database may expose the API114and the stored procedures executed to handle each request made by an execution resource108, as described above.

FIG. 3illustrates one routine300for determining whether a specified task106may be executed based on the stage and maximum stage defined for the tasks in the task definition list110. According to one embodiment, the routine300may be performed by the task dependencies management module104executing on the application server102and/or other servers or computing devices. It will be appreciated that the routine300may also be performed by other modules or components executing on other computing devices, or by any combination of modules, components, and computing devices. As described above, the routine300may be performed by the task dependencies management module104in response to a request by an execution resource via the API114for permission to execute a particular task106.

The routine300begins at operation302, where the task dependencies management module104loads a list of tasks from the task definition list110. As described above in regard toFIG. 1, the task definition list110may comprise one or more tuples defining a task ID, stage, and maximum stage for each task. According to embodiments, the list of tasks parsed from the task definition list110may be stored in memory of the application server102or in a database table or other storage mechanism accessible by the server. It will be appreciated that the operation302to load the list of tasks from the task definition list110may only be executed once by the task dependencies management module104at the beginning of the execution of a group or batch of tasks defined in the task definition list, instead of upon every request.

From operation302, the routine300proceeds to operation304, where the task dependencies management module104receives the task ID of the task106to be executed. For example, an execution resource108may utilize the API114of the task dependencies management module104to request permission to execute a particular task106. The request may specify a task ID of the task106, such as the task Name attribute206described above in regard toFIG. 2.

The routine300then proceeds from operation304to operation306, where the task dependencies management module104determines whether the specified task may be executed based on the stage and maximum stage of all other pending or running tasks106. Particularly, the task dependencies management module104determines if any pending or currently running task106has a stage or maximum stage that is less than the stage defined for the specified task. If another task B is pending or currently running with a stage SB less than the stage SA of the retrieved task and a maximum stage MB less than SA, the specified task is not allowed to run in parallel with or prior to the other task, and the routine300proceeds to operation304, where the task dependencies management module104prevents the specified task from being executed. For example, the task dependencies management module104may respond to the requesting execution resource108with an indicator indicating that the specified task may not be executed at this time.

However, if no other pending or currently running task106has a stage or maximum stage that is less than the stage defined for the specified task, then the routine300proceeds from operation306to operation310, where the specified task is allowed to execute. For example, the task dependencies management module104may respond to the requesting execution resource108with an indicator indicating that the task may be executed. From operations308or310, the routine300ends.

In a further embodiment, a client module may execute on a remote computer and manage the execution of the tasks106defined in a local list or group of tasks on a subset of the execution resources108. Upon detecting that an execution resource108is available, the client module may determine the next task in the local list of tasks to be executed, and utilize the API114of the task dependencies management module104to request permission to execute the task, by providing a task ID, for example. The task execution module104will utilize the routine300described above to determine if the task is allowed to execute based on the stage and maximum stage of the other pending and currently running tasks, as determined from the list of tasks and the executed task list112.

The task execution module104may then respond to the client module with an indicator indicating whether the task may be executed or not. If the task may be executed, then the client module will initiate the task106on the available execution resource108. If the task may not be executed, then the client module will select the next task in the local task list for execution and request permission for execution of that task from the task dependencies management module104. In another embodiment, the client module may execute on the same application server102as the task dependencies management module104or may be a component of the task dependencies management module, and the local task list may be the task definition list116.

FIG. 4shows an example computer architecture for a computer400capable of executing the software components described herein for using stages for managing dependencies between tasks executed in parallel, in the manner presented above. The computer architecture shown inFIG. 4illustrates a conventional server computer, desktop computer, laptop, notebook, PDA, wireless phone, or other computing device, and may be utilized to execute any aspects of the software components presented herein described as executing on the application server102or other computing device.

The computer architecture shown inFIG. 4includes one or more central processing units (“CPUs”)402. The CPUs402may be standard processors that perform the arithmetic and logical operations necessary for the operation of the computer400. The CPUs402perform the necessary operations by transitioning from one discrete, physical state to the next through the manipulation of switching elements that differentiating between and change these states. Switching elements may generally include electronic circuits that maintain one of two binary states, such as flip-flops, and electronic circuits that provide an output state based on the logical combination of the states of one or more other switching elements, such as logic gates. These basic switching elements may be combined to create more complex logic circuits, including registers, adders-subtractors, arithmetic logic units, floating-point units, and other logic elements.

The computer architecture further includes a system memory408, including a random access memory (“RAM”)414and a read-only memory416(“ROM”), and a system bus404that couples the memory to the CPUs402. A basic input/output system containing the basic routines that help to transfer information between elements within the computer400, such as during startup, is stored in the ROM416. The computer400also includes a mass storage device410for storing an operating system422, application programs, and other program modules, which are described in greater detail herein.

The mass storage device410is connected to the CPUs402through a mass storage controller (not shown) connected to the bus404. The mass storage device410provides non-volatile storage for the computer400. The computer400may store information on the mass storage device410by transforming the physical state of the device to reflect the information being stored. The specific transformation of physical state may depend on various factors, in different implementations of this description. Examples of such factors may include, but are not limited to, the technology used to implement the mass storage device, whether the mass storage device is characterized as primary or secondary storage, and the like.

For example, the computer400may store information to the mass storage device410by issuing instructions to the mass storage controller to alter the magnetic characteristics of a particular location within a magnetic disk drive, the reflective or refractive characteristics of a particular location in an optical storage device, or the electrical characteristics of a particular capacitor, transistor, or other discrete component in a solid-state storage device. Other transformations of physical media are possible without departing from the scope and spirit of the present description. The computer400may further read information from the mass storage device410by detecting the physical states or characteristics of one or more particular locations within the mass storage device.

As mentioned briefly above, a number of program modules and data files may be stored in the mass storage device410and RAM414of the computer400, including an operating system418suitable for controlling the operation of a computer. The mass storage device410and RAM414may also store one or more program modules. In particular, the mass storage device410and the RAM414may store the task dependencies management module104, which was described in detail above in regard toFIG. 1. The mass storage device410and the RAM414may also store other types of program modules or data.

In addition to the mass storage device410described above, the computer400may have access to other computer-readable media to store and retrieve information, such as program modules, data structures, or other data. It should be appreciated by those skilled in the art that computer-readable media may be any available media that can be accessed by the computer400, including computer-readable storage media and communications media. Communications media includes transitory signals. Computer-readable storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for the storage of information, such as computer-readable instructions, data structures, program modules, or other data, but does not encompass transitory signals. For example, computer-readable storage media includes, but is not limited to, RAM, ROM, EPROM, EEPROM, flash memory or other solid state memory technology, CD-ROM, digital versatile disks (DVD), HD-DVD, BLU-RAY, or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information and that can be accessed by the computer400.

The computer-readable storage medium may be encoded with computer-executable instructions that, when loaded into the computer400, may transform the computer system from a general-purpose computing system into a special-purpose computer capable of implementing the embodiments described herein. The computer-executable instructions may be encoded on the computer-readable storage medium by altering the electrical, optical, magnetic, or other physical characteristics of particular locations within the media. These computer-executable instructions transform the computer400by specifying how the CPUs402transition between states, as described above. According to one embodiment, the computer400may have access to computer-readable storage media storing computer-executable instructions that, when executed by the computer, perform the routine300for using stages for managing dependencies between tasks executed in parallel, described above in regard toFIG. 3.

According to various embodiments, the computer400may operate in a networked environment using logical connections to execution resources108, remote computing devices, and computer systems through a network420, such as a LAN, a WAN, the Internet, or a network of any topology known in the art. The computer400may connect to the network420through a network interface unit406connected to the bus404. It should be appreciated that the network interface unit406may also be utilized to connect to other types of networks and remote computer systems.

The computer400may also include an input/output controller412for receiving and processing input from a number of input devices, including a keyboard, a mouse, a touchpad, a touch screen, an electronic stylus, or other type of input device. Similarly, the input/output controller412may provide output to a display device, such as a computer monitor, a flat-panel display, a digital projector, a printer, a plotter, or other type of output device. It will be appreciated that the computer400may not include all of the components shown inFIG. 4, may include other components that are not explicitly shown inFIG. 4, or may utilize an architecture completely different than that shown inFIG. 4.

Based on the foregoing, it should be appreciated that technologies for using stages for managing dependencies between tasks executed in parallel are provided herein. Although the subject matter presented herein has been described in language specific to computer structural features, methodological acts, and computer-readable storage media, it is to be understood that the invention defined in the appended claims is not necessarily limited to the specific features, acts, or media described herein. Rather, the specific features, acts, and mediums are disclosed as example forms of implementing the claims.