If you want a piece of software to execute a task in parallel, the first challenge is to split that task into meaningful subtasks, which the computer can then processes simultaneously. Libraries such as OpenMP help programmers achieve this kind of parallelization.

Bash scripts typically don't handle numeric problems, so most programmers don't think of a bash script as a candidate for parallelization. The venerable bash shell, however, is used for other types of jobs that lend themselves to a parallel approach. For instance, a bash script is often employed as a tool for processing multiple files in the same way.

Listing 1 shows a shell function that processes all the arguments in the script one by one and passes the results to a program (doSomething). In this scenario, it is easy to imagine the benefits of some parallel-processing techniques.

Figure 1: The output from sar shows the load for all CPUs. Parallelization only makes sense if some cores are overworked while others are doing nothing.

Brute Force

Minimal changes to the code in Listing 1 produces the parallel-processing alternative shown in Listing 2. Listing 2 starts a separate process for each argument. In line 6, the script waits for its child processes to terminate. This approach can cause problems: If the system is stressed by excessively large numbers of processes, the overhead will increase because of many context changes. In environments with limited memory, you also might see the machine slow to a crawl as it swaps individual processes. In some situations, however, this simple approach to parallelization makes sense.

Listing 2a is a variant on Listing 2. In this case, the arguments are not known; instead, a separate process (createWorkItems) creates them sequentially – this could be a find that is run against a very large filesystem. If the generating and processing rates, which depend on the number of available processors, are approximately the same, you will not experience system overload. If this is not the case, you will need a more elaborate solution. The script in Listing 3 distributes the arguments depending on the number of processors and then processes the subsets sequentially. Line 1 of the script determines the number of processors (PMAX) for the system. If the process is heavy on the I/O, it might make sense to set the number of processes to a value greater than PMAX to allow one process to work while another is waiting for I/O.

Unfortunately, bash only uses single-dimensional arrays, which makes the construct in lines 6 and 13 slightly complicated. For each process, the script creates a long string containing the arguments for the process within an array element (lines 5 through 9). The script then launches PMAX parallel processes (lines 11 through 14). Line 12 prevents empty processing (e.g., in the case of just two arguments on a quadcore machine), and eval in line 12 makes sure that the shell interprets the quotes in line 6 correctly.

Dynamic Dispatcher

The scheme shown in Listing 3 is optimal if the average processing time per item is not subject to major fluctuation. Unfortunately, you can't always rely on this. For example, if you are converting multiple tracks, an unfavorable distribution of long and short tracks could mean that some processes finish sooner than others. Another situation in which this approach might be a problem is the task of converting images from digital cameras. Some cameras create JPG or thumbnail files in addition to RAW files. If every other file uses the RAW format and has to be converted, half of the conversion processes will finish significantly sooner because the processing scheme assigns all the RAW files to one process and all the JPG files to the other.

The processing method in Listing 3 also suffers in cases in which not all arguments are known in advance. If the arguments generated later in the script occur in sequence, it would not make sense to wait for them all to be created and then distribute them over the processes.

The solution for this problem is to use worker processes and a dynamic dispatcher. In this scenario, the script launches a number of worker processes. A dispatcher accepts tasks and distributes them as intelligently as possible to the workers. In contrast to the parallel solutions described earlier, in which all worker processes need to receive all their arguments at the start, the dispatcher talks to the workers after they have launched.

Named pipes or FIFOs are used as communications channels. To begin, the dispatcher opens a pipe for each worker and sends new tasks to the pipe (Figure 2). Another pipe that is shared by the dispatcher and the workers is used as the return channel. If a worker has nothing to do, it writes its ID to the pipe. The dispatcher reads an ID from the pipe after each task and sends the next task to this worker.

Figure 2: Dispatcher and worker processes use pipes to communicate.

Listing 4 shows an implementation of this concept. In lines 1 to 4, the program sets a number of constants, if this has not already happened. Normally, the user will only define the _cmd variable. The dispatchWork function in lines 54 to 72 is the public part of the interface. The function starts by creating a temporary directory for all the pipes in line 55 (referred to as controlDir in the script). The mkfifo command in line 58 sets up the return channel.

Line 59 needs some explanation. Here, the shell opens the return channel for reading and writing, although read-only access is all it really needs. The problem is that read-only access to a pipe blocks the system call. A similar problem occurs in the startWorker() function, which creates a pipe for each worker process (line 37) and opens it for reading and writing (line 40).

The additional eval in line 40 is necessary because the bash parser processes the input redirection at a very early stage – before the variable substitution. (This also explains the backslashes before the lesser than and greater than symbols.)

Listing 4 simply contains functions – other scripts include this file and then use the dispatchWork function (see Listing 5).

Pitfalls

The script in Listing 4 has a couple of minor issues to contend with: For example, a kill command would leave orphaned worker processes (although this problem could be handled by a timeout variable). Also, if you have more than six processes, the script will use file descriptors (channel numbers) that are greater than 9. According to the bash manual, you have to be "careful" with this – whatever that means – because bash might already be using these descriptors for internal purposes. As a workaround, you can modify the offset for the channel numbers (line 4).

Other implementations are possible. For example, the dispatcher and workers could use files to communicate. The dispatcher would then write tasks to worker-specific files. Workers would use polling to see whether their worker files exist, process the tasks defined in the files, and then delete the files. At the other end, the dispatcher would check for worker files that are missing and thus would know which workers are idle.

Of course, this solution is typically inefficient because of the need for continuous polling.

A longer version of Listing 4 is available at the Linux Magazine website [1]. This expanded version supports calls to dispatchWork at the command line:

$ dispatchWork c "doSomething" file1 file2 [...]

The longer version also includes comments and some switches for optional debug output that allow administrators to monitor scripts.