MP6 Parallel Make
CS 241 MP6 Parallel Make
CS 241: MP6

Due: Tuesday, April 3, 2012 at 11:59pm

Introduction

More and more programs today are being programmed as multithreaded applications. The goal of this MP is to give you more practice writing multithreaded applications and to expose common pitfalls that occur while designing a program to work in a parallel manner. Additionally, you will need to make use of synchronization primitives to protect memory shared amongst the threads.

You are tasked with writing an application which will imitate the common make utility. We have provided a parse function which will list dependencies and commands to run for different target values. You will need to use this parse function to store the work that needs to be done. Then using a fixed pool of threads, you will make sure that all commands are executed after their dependencies. When there is less work to be done than there are threads, the remaining idle threads should sleep.

Before starting you should read the Wikipedia article on Make.

TASK

[Part 1]

The first thing you will need to do is parse the command-line options given. All handling of options should be done using getopt(). This function will allow you to specify which options are valid and which require arguments. The usage for parmake looks like:
parmake [ -f makefile ] [ -j threads ] [ targets ]
If a makefile is not specified, ./makefile or ./Makefile should be used in that order, if they exist (see access()). Return a non-zero value if neither of these files exist. If the number of worker threads -j is not specified, the default value of 1 should be used. The j worker threads are in addition to the one main thread. The space seperated list of targets will always come last and is optional. You will need to save any targets given for use in Part 2. The man page for getopt() shows an example of how to locate the position of targets within argc.

[Part 2]

Next, the main thread should parse the makefile. The makefile will always consist of one or more rules of the form:

target [target ...]: [dependency ...]
[<TAB>command 1]
.
.
[<TAB>command n]
For example:
rule1: rule2 rule3
    commandtoberun withargs
    commandtoberun2 withargs
rule2:
    othercommand
rule3 rule4:
    finalcommand
If you are unfamiliar with the syntax do not be afraid. We have provided you with a parsing function, parser_parse_makefile().

When invoking the parser you will have to provide "call-back" functions and the list of targets from Part 1. This means you will have to pass function pointers of the type defined in parser.h. These callback functions will be called from parser_parse_makefile() providing you with the parsed strings. For dependencies and commands, the target to which the dependency or command belongs is also passed back.

The list of targets should be a NULL-terminated array of strings similar to that of argv. The targets are used by the parser to select the correct rules (for example 'make clean' only runs the clean target). If no targets are given on the command line, the list of targets will only include the terminating NULL pointer. Those curious of the implementation can view the source in parser.c although this is not necessary for a functioning MP.

We have provided an implementation of a queue for you to store rules. It can be viewed in queue.h.

[Part 3]

Once all rules have been parsed, you will want to decide which rule dependencies refer to other rules and which refer to files on disk. This is important when deciding which rules are ready to run and which are waiting on a dependency. If a dependency refers to another rule, it is only met once the other rule has been run. If a dependency does not refer to another rule, the dependency refers to a file. You should exit with a non-zero value if the file cannot be found (use access()). These rules decide when a rule can be run.

In order to decide if a rule should be run, you will have to use the modification times of the files represented by the dependency list. The modification time for a given file can be retrieved using stat(). Interpreting all dependencies and the target as filenames, if any dependency has a modification time more recent than the target, the rule should be run. Said another way, if all dependencies have modification time older than the target, the rule should NOT be run.

[Part 4]

After the makefile has been completely parsed and unnecessary rules have been removed, the worker threads should be spawned. The number of threads is given as the command-line option -j. Each worker thread will be in charge of processing rules. This consists of determining whether its dependencies have been fulfilled and then executing any associated commands. There are several important concurrency requirements:

  • You should NOT make any rule unless its dependencies have been met (all dependent rules have been run)
  • If there exists J rules with all dependencies met and T threads where J>=T, NO threads should be sleeping
  • If there exists J rules with all dependencies met and T threads where J<T, T-J threads should be sleeping

All commands should be printed to the screen just as GNU make does and can be run using system(). If a command returns a non-zero value, parmake should exit immediately with a non-zero value. The worker threads should continue processing rules until all work has been completed. At this point all worker threads should exit including the main thread.

NOTES

  • You should only edit parmake.c.

  • You can assume all makefiles will be in valid Makefile style syntax as described previously as well as have no circular dependencies.

  • All threads should stay busy if possible. Reordering of tasks to achieve global optimal efficiency is not required. The dependency graph might have natural choke points where one task limits all the others.

  • You will receive 0 points if your implementation uses sleep().

COMPILING AND RUNNING MP6

To compile, run the following commands from a command prompt on a Linux machine:

%> make clean
%> make

To run the executable,

%> ./parmake [ -f makefile ] [ -j threads] [ targets ]
 All Data Structures Files Functions Variables Enumerations