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.