Write a program that creates a hierarchy of processes using the fork() system call. The initial program termed the root, along with all its osprings will ultimately form a full binary tree. The tree has both internal and leaf-level nodes.

The basic objective of the tree is to help sort the content of a (potentially very large) data le consisting of taxpayer records. This is done in a \divide-and-conquer" style: the leaf-level nodes are responsible for sorting portions of the data le, while the internal nodes help merge partially ordered data and present their combined outcome to their parent and ultimately to the root.

The leaf level nodes use diverse independent programs to sort the portion of the input data le they are assigned to. The required data communication between consecutive levels of processes takes place with the help of named-pipes (FIFOs).

In the context of this project, you will:

Create a hierarchy of processes using fork(),  allow the execution of various executables (or dierent pieces of code) by the nodes of the hierarchy, use a number of useful system calls including fork(), exec*(), read(), write(), mkfo(), wait(), poll(), etc.

The Process Hierarchy:

Figure 1 depicts a sample process hierarchy your program may generate. The overall goal of the hierarchy is to create a sorted listing of all data records based on a user-provided condition; records are provided to the root in the form of a data le (binary/text). There are three types of nodes that try to accomplish dierent types of tasks. In particular:

1. root node: this is your program and functions as the \anchor" for the entire hierarchy; more importantly, it orchestrates of the entire sorting operation.

At rst, it creates a single splitter/merger node and the root passes to this node {named sm0{ the range of records whose sorting is to oversee (i.e., the entire range). The depth of the tree (and consequently the number of levels internal nodes can be found) is designated by a parameter at the command line of your program (root).

2. sort nodes: each of these leaf-level nodes is provided with a set of records (possibly in the form of a le name/descriptor, as well as the range of the records in the le) that it will have to sort. To achieve their goal, sorters deploy dierent programs and return to their parent their outcome in the form of a named-pipe (FIFO queue).

Four dierent programs are used to do sorting at leaf-level, namely:

(a) Shell-Sort (SH): you have to write this independent program

(b) Quick-Sort (QS): you have to write this independent program

(c) sort (SO): the Unix system program

(d) Buble-Sort (BS): you have to write this independent program