$29.99
Programming Assignment #2 Solution
Introduction
The purpose of this lab is to learn using the Opera ng System’s I/O and file system calls. In par cular, you will do some prac ces with File I/O opera ons, File pointers and buffering, File descriptors and I/O redirec ons, file system, and directories. In the previous assignment, we provided several u lity func ons, e.g., to read, parse, and write a file. In this assignment, you will need to create your own func ons to do those func ons.
The Overview of Our Existing Vote Count Application
Recall that our vote count applica on has three types of node: (1) root node, (2) aggregator node, and
(3) leaf node. An example of the applica on can be seen in the figure below:
In our existing vote count applica on:
1) The leaf node will execute a “leafcounter” executable which will read an input file and write out the summary of the input file into an output file.
2) The aggregator node will execute a “aggregate_votes” executable which will read n
intermediate results and aggregate them into a single output file.
3) The root node has two main func ons: (1) to parse an <input.txt which contains the informa on of the DAG (Directed Acyclic Graph) and (2) to execute “Output_Who_Won” executable which will read n intermediate results, aggregate them, and output the winner to an output file.
Your Assignment
In this assignment, you will create a new breed of the Vote Counter applica on in which the structure of the graph is given in the form of a directory structure. For example, the figure above can be translated into a structure of 5 directories with a root node of Who_Won directory as follows:
Bob@foo:/$ ls
Who_Won
Bob@foo:/$ cd Who_Won; ls
Region_1 Region_2
Bob@foo:/Who_Won$ ls Region_2
votes.txt //Contains the votes for Region_2.
Bob@foo:/Who_Won$ cd Region_1; ls
County_1 County_2
Bob@foo:/Who_Won/Region_1$ ls County_1; ls County_2 votes.txt //Contain the votes for County_1. votes.txt //Contain the votes for County_2.
Your applica on will need to traverse the directories and aggregate the votes as needed. Depending on
your implementa on, your applica on may traverse the directories in a depth-first search (
FS) or in a
breadth-first search (BFS) manner. Furthermore, you will need to write your own func on to read and write the result to a file. In general, your assignment is to create three executables, i.e., Leaf_Counter, Aggregator, and Vote_Counter that will be discussed below.
Setup
You may use your assignment 1 as a star ng point for the project. However, it is recommended to start the assignment from scratch as there will be many changes to your assignment 1 code. However, you may use some func ons from your assignment 1 to do this assignment, e.g., the Makeargv.h
However, you are not allowed to use any binaries that we have provided for programming assignment 1. There are three executables that you will need to create for this assignment. (Note: the name of the executables must be the same with the following):
Executable 1: Leaf_Counter
This executable will act as the leaf nodes.
Input:
This program has one argument and will be executed as follows:
./Leaf_Counter <path
- <path: is the rela ve path to a directory.
Main Functionality:
- This program has a similar func onality with your first programming assignment in which it will read the votes file located at the path, i.e., “<path/votes.txt”, aggregate the votes for each candidate, and output the results into a file that is also located in the path.
- The votes file will always be called “votes.txt” and the output file name will always be the path name with “.txt” appended to it. For example, if the
<path=”Who_Won/Region_1/County_1”, the output file will be
“Who_Won/Region_1/County_1/County_1.txt”.
Output:
- If the program is called on a directory that does not have votes.txt, it writes to the standard output the following message: “Not a leaf node.\n”
- Otherwise, the program has two outputs: (1) output the coun ng result into an output file whose name is the last directory name in the path appended with “.txt” and (2) write to the standard output the path to the output file ended with a new line character.
- The output file contains a coun ng result in the form of: “<candidate_1:<count_1,<candidate_2:<count_2,...,<candidate_n:<count_n\n”
- If the output file already exists, it will replace it with the new one.
Example: (Look at figure above for the structure of the DAG)
Bob@foo:/$ ./Leaf_Counter Who_Won/Region_1
Not a leaf node.
Bob@foo:/$ ls Who_Won/Region_1/County_1 votes.txt
Bob@foo:/$ cat Who_Won/Region_1/County_1/votes.txt
A B A C
Bob@foo:/$ ./Leaf_Counter Who_Won/Region_1/County_1
Who_Won/Region_1/County_1/County_1.txt
Bob@foo:/$ ls Who_Won/Region_1/County_1 vote.txt County_1.txt
Bob@foo:/$ cat Who_Won/Region_1/County_1/County_1.txt
A:2,B:1,C:1
Executable 2: Aggregate_Votes
This program will act as the aggregator nodes.
Input:
This program has one argument and will be executed as follows:
./Aggregate_Votes <path
- <path: is the rela ve path to a directory.
Main Functionality:
- This program has a similar func onality with your first programming assignment in which it will aggregate all the vo ng results of all subdirectories, i.e., its children, that are defined in <path and write the aggrega on result to a file in <path. The aggrega on result file will have the same name as the current node appended with “.txt”
- If we call this program on a leaf node, then it will execute the Leaf_Counter program.
- Each subdirectory (or child) can either be: (1) a leaf node or (2) a non-leaf node. If the child is a leaf, then this program will spawn a child process to execute the Leaf_Counter program. If the child is a non-leaf, then this program will spawn a child process to execute another Aggregate_Votes program.
- The child process must not print their result into the standard output.
- If a directory is not a leaf node, however, contains a “votes.txt”, then this program must ignore
the “votes.txt”.
Output:
- The program has two outputs: (1) output the aggrega on result into an output file located in
<path with a file name of the directory name appended with “.txt” and (2) write to the standard output the output file path ended with a new line character.
- The output file contains a coun ng result in the form of: “<candidate_1:<count_1,<candidate_2:<count_2,...,<candidate_n:<count_n\n”
- If the output file already exists, it will replace it with the new one.
Example: (Look at figure above for the structure of the DAG)
Bob@foo:/$ ls Who_Won/Region_1/County_1 votes.txt County_1.txt
Bob@foo:/$ ./Aggregate_Votes Who_Won/Region_1/County_1
Who_Won/Region_1/County_1/County_1.txt
Bob@foo:/$ cat Who_Won/Region_1/County_1/County_1.txt
A:2,B:1,C:1
Bob@foo:/$ cat Who_Won/Region_1/County_2/votes.txt
A D
Bob@foo/:$ ./Aggregate_Votes Who_Won/Region_1
Who_Won/Region_1/Region_1.txt
Bob@foo/:$ ls /Who_Won/Region_1/County_2 //Check the output of County_2 votes.txt County_2.txt
Bob@foo/:$ cat /Who_Won/Region_1/Region_1.txt
A:3,B:1,C:1,D:1
Executable 3: Vote_Counter
This program is the root node of the whole vote coun ng applica on.
This program has zero or one argument and will be executed as follows:
./Vote_Counter <root_path
- <root_path: the rela ve path from the current directory to the root.
Main Functionality:
- The working directory where the program is executed will be the root of the program.
- This program basically will call the Aggregate_Votes program, read output file of the aggrega on result, and append the winner into the output file.
- Similarly, child process should not write any messages to the standard output.
- This program can also be called from any parts of the DAG.
Output:
- The program has one output: write to the standard output the output file path ended with a new line character.
- This program will alsol append the aggrega on result with a winner as follows: “Winner: <candidate_n\n”
Example: (Look at figure above for the structure of the DAG)
Bob@foo:/$ ls Who_Won
Region_1 Region_2
Bob@foo:/$ cat Who_Won/Region_2/votes.txt
E E E E
Bob@foo:/$ ./Vote_Counter Who_Won
Who_Won/Who_Won.txt
Bob@foo:/$ cat Who_Won/Who_Won.txt
A:3,B:1,C:1,D:1,E:4 //Written by the Aggregate_Votes on Who_Won
Winner:E //Appended by the Vote_Counter
Putting It Together
- Each executable must be able to be executed on its own without execu ng the Vote_Counter program. For example, we should be able to run Leaf_Counter and Aggregate_Votes independently.
- Both Aggregate_Votes and Vote_Counter can be executed on any parts of the DAG. For example,
we can run an Aggregate_Votes or Vote_Counter on a leaf node.
1) Calling the Leaf_Counter program on County_1 will count the data from the leaf node and print the result file name into the standard output.
2) Calling the Aggregate_Votes on Who_Won will spawn two processes, one for the Region_2 and one for the Region_1. For the Region_2, the Aggregate_Votes will execute a Leaf_Counter. For the Region_1, it will execute another Aggregate_Votes on Region_1. Then, the Who_Won aggregator will read the output of both children (the file names of the their output), parse the files and write out the aggrega on result to the current directory. Lastly, it will print the
aggrega on result file name into the standard output.
3) Calling the Vote_Counter on Who_Won will execute the Aggregate_Votes on Who_Won and append the winner into the output_file.
4) Calling an Aggregate_Votes on County_1 will execute a Leaf_Counter program on County_1 because County_1 is a leaf node.
5) Calling a Vote_Counter on County_1 will execute the Aggregate_Votes program which will execute the Leaf_Counter program on County_1. Then, the Vote_Counter will append the winner to the output file.
