PARSH README

============ INTRODUCTION

Parsh, the Parallel Dependency Shell, attempts to automate parallel execution of commands whenever possible, without any extra effort from script writers or generation programs.

As a brief architectural summary, Parsh has a central file hash table data structure and three main threads that operate on this structure: a parser, an evaluator, and a reaper. These threads all communicate with a central file hash table structure to determine which commands are runnable and which must wait.

The file hash is a hash table of files that are currently being accessed or will be accessed by processed commands. Each file has a single entry in the table, and each entry contains an "accessor queue," a queue of commands waiting for access to the file. When multiple commands need access to a single file, they are enqueued. The first command in the queue (or commands, if they are all reads) has access to the file and are considered "runnable," while the remaining are blocked.

The parser takes input from the user or a script, parses the commands from them, and adds them to the hash. At this stage, if a new command accesses a file that is not already in the hash table, a new file entry will be created. Otherwise the command will be enqueued in the command queue of an existing file entry.

The evaluator makes use of the concept of a "frontier," which is a list of commands in the file hash table that are runnable. The hash table has taken care of all matters of dependency and control flow, thus the evaluator only needs to mindlessly evaluate the next command in the frontier list.

The reaper catches signals sent by exiting processes, removes the appropriate commands from the file hash, and re-evaluates the dependency status of related commands, possibly marking them as runnable.

============ Dependencies

There are three types of dependencies in Parsh: 1) File dependencies 2) Control flow dependencies 3) Variable dependencies

File Dependencies: Commands attempting to access the same file are considered to collide if at least one is not a read access. The structure for a file dependency has the following fields:

inode #: primary way of identifying files, since with inode numbers there is no need to worry about links. absolute path: for resolving the inode # of a link, and as a secondary way of identifying a file when an inode # is not available (i.e. the file has yet to be created). read/write: access type to determine dependency

For file dependencies, each file is hashed into the file hash table. Each file entry contains the fields listed above. Each command that accesses a file (an "accessor") will enqueue itself in the file entry's accessor queue. In the case of multiple accessors, the head of the queue is runnable, while the rest are blocked. In the case consecutive read accessors are at the head of the queue, they are all simultaneously runnable.

Control Flow Dependencies: Some commands must know another's exit status to determine whether to run or not. These maybe a command inside an IF statement, or a command waiting to see if control flow reaches a BREAK. A simple IF-like dependency (IF, ||, UNTIL and the such) are handled solely within the dependency hash. A CONTINUE or BREAK dependency is more complicated, and thus requires its own data structure.

nest level: the true level the CONTINUE or BREAK statement belongs to. For example, a BREAK 2 nested 4 levels deep acts on other commands at nest level 2 or greater. parent: to follow the nest chain up. iteration: loop iteration. For nested loops, this is the iteration of the innermost loop. If the iteration of an outer loop is needed, the parent pointer should be followed.

Note that in order to establish a dependency, a command must be at or below the same nest level. For CONTINUE, to be at the same iteration is a requirement, while for BREAK the command needs to be at the same or a later iteration in the nest level of the BREAK command.

Control flow dependencies are handled internally in the file hash table. A control flow command will be considered an accessor of all the subcommands in it. Upon evaluating the branch decision, the appropriate subcommands will be inserted into the hash table.

For example, an IF command is considered an accessor of all files accessed in the conditional, if, and else part of the command. When the IF command becomes runnable, the conditional part is evaluated. Depending on the outcome, either the if or else part will become runnable.

Variable Dependencies: In Parsh, variables use static single assignment form, thus there is never a value collision. Rather, the only variable dependencies in Parsh will be a command waiting for a delayed value resolution. This will be explained in more detail in the variables section.

Variable dependencies are handled by the variable module. For the scope of this section, it will be sufficient to say that a variable whose value is not yet ready counts towards a accessor command's dependencies, and upon the value becoming available the accessor will be updated.