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 key 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.
The main thread should begin by parsing the input file. The input file will always be of the form (specified in BNF):
<Makefile> ::= <job> | <job> <Makefile>For example:
<job> ::= <key> ":" <depend-list> <cmd-list>
<depend-list> ::= " " <key> <depend-list> | <newline>
<cmd-list> ::= <tab> <cmd> <newline> <cmd-list> | <tab> <cmd> <newline>
<key> ::= <a-z,A-Z,0-9> <key> | <a-z,A-Z,0-9>
<cmd> ::= <Valid Unix cmd>
job1: job2 job3If you are unfamiliar with the syntax do not be afraid. We have provided you with a parsing function.
commandtoberun withargs
commandtoberun2 withargs
job2:
othercommand
job3:
finalcommand
When invoking the parser you will have to provide several "call-back" functions. This means you will have to pass a function pointer of the type defined in parser.h. These call-back functions will provide the parsed strings as arguments which you should then store in your own data structure. Those curious of the implementation can view the source in parser.c although this is not necessary for a functioning MP.
It is important to note a few differences from the standard make utility here. The key values do not represent files like in make. This means that all commands should always be executed. There is no need to do any kind of timestamp checks like make does.
The main thread of the program will read the number of worker threads to be placed in the thread pool from the command line. The argument will use the following syntax.
%>./parmake -j# makefilenameAfter the input file has been completely parsed, the worker threads should be spawned. Each worker thread will be in charge of processing jobs. This consists of determining whether its dependencies have been fulfilled and then executing any associated commands. There are several important concurrency requirements:
The worker threads should continue processing jobs until all work has been completed. At this point all worker threads should exit as well as the main thread.
Start with the provided file, parmake.c, and do not rename the file. You may add any functions you'd like to parmake.c, but please do not create any other code files for this MP.
You may find these commands useful in this MP:
...for file I/O: fopen(), fscanf(), fclose()
...for threads: pthread_create(), pthread_join()
...for command execution: system()
You can assume all input files 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.
To compile, run the following commands from a command prompt on a Linux machine:
%> make clean
%> make
To run the executable,
%> ./parmake <-j#> <file>