This is the assignment:
Out: September 10, 2010
Due:
Phase 1 Milestone: 9:00AM, September 17, 2010
Phase 2 Milestone: 9:00AM, September 24, 2010
Complete Assignment: 9:00PM, October 3, 2010
This assignment is designed to get you into the swing of things with respect to C and UNIX/Linux systems programming. Be sure that all your code compiles on the school's computers using the gcc compiler in Linux as appropriate. All parts of this assignment may be done in teams.
TOTAL MARKS: 150
Phased Hand-in
The first 2 phases have additional marks that make the total number of marks equal to 150.
Part A: Parents, Children and Threads (45 marks)
PART A.1. (15 marks) Write a WINDOWS program that creates multiple threads that each perform a specific task until a deadline. The number of child threads (M) and the deadline (D) are to be command-line parameters. Each thread does the same task. The task is given below and requires a third command-line parameter (N). An example invocation of this program is the following: computeSquares 4 2000000 3. This creates 4 child threads, and has each thread compute Square(1) to Square(2000000) in a loop with a deadline of 3 seconds from the time the parent thread starts running.
* The application should have a parent thread create M child threads.
Each child then executes a procedure to calculate (but not print out) the squares of the first N positive integers (i.e., 12, 22, 32,42, 52) (where N is also given as a command-line argument). The restriction is that procedure Square() cannot use any multiplication operations (I want a simple operation that will take a long time to complete). Instead, use the following algorithm:
int Square(N)
{
if (N == 0) return (0);
return (Square (N-1) + N + N - 1);
}
The second command-line parameter is the deadline for the program in seconds (D). If child threads are not done in this time, then the program must exit. This is achieved by having the parent thread check the deadline on each execution of its main loop. If the deadline has passed, it sets a global variable named something like keepRunning that the parent can set and the children can read to have the value FALSE. The parent should do nothing else but sleep until the deadline occurs. The simplest way to do this is to use the system call Sleep.
You may need to have N be a very large number and D to be a fairly small number to get interesting results from this operation.
Upon exit, Each childshould print the following:
o elapsed real time since the child began.
o number of invocations of the Square() procedure by this thread.
You will need to become familiar with the following Win32 System calls: CreateThread(), GetSystemTime(), and Sleep().
PART A.2. (10 marks) Repeat part A.1 in UBC pthreads.
* The difference here is the threads calls syntax and the process communication. If the time expires before children threads are finished, the parent should Kill() the children threads, instead of having them check the shared flag. In this case, the parent would be responsible for printing out the statistics for each child that had not finished executing when the deadline occurred.
PART A.3. (15 marks) Repeat part A.1 with UNIX processes. The way I want you to do this will require the use of signals and signal handlers. When the time expires, the children should be signaled that this has happened and they should catch the signal and exit appropriately. You must write a signal handler to handle the SIGALRM signal. You will need to create an additional process, the timer. When the timer determines that the time to execute the program has expired, the timer process should send a SIGALRM to each child and the parent, telling them to stop. When the signal is caught by the child, it should print out the values calculated so far and return an error status to the parent. If the child terminates normally before the timer expires, it should print out its values, state that it finished normally and return a success status to the parent. The parent process should be in a waitloop, waiting for each child to finish. If each child finishes, then it should kill the timer and then terminate normally.
PART A.4. (5 marks) Repeat part A.2 in Posix threads.
* The difference here is the syntax of the threads operations.
For all of these parts, reuse as much code as possible. In particular, the calculation of Squares should all be in one C file, and be able to be linked in with any of the parts.
Part B: Shell script (5 marks)
Write an interactive shell script that executes Parts A.1, A.2, A.3 or A.4 according to the user's instructions. The shell script should read the appropriate values from the user and then invoke the corresponding program with the corresponding command line arguments. The structure you use for this part of the program is up to you, but you must do this in a loop until the user wishes to quit. Obviously, part A.1 only works on Windows, so there should be a check to see that the user is on the proper architecture for the program to be run.
Part C: Lists (65 marks)
Lists are composed of elements called nodes (NODE data type). Each node is able to hold one item. An item is any C data type that can be pointed to - so your node structure should have a (void *) field in it to reference the item held by that node. For the purposes of this assignment, though, you may create several lists WHERE EACH LIST HAS A HOMOGENOUS DATA TYPE.
You must create the user-defined type LIST, implement functions to manipulate lists, and compile the code to be used as a library. An instance of type LIST refers to a particular list and will be an argument to most of your list manipulation routines.
You are to implement the following list manipulation routines:
1. LIST *ListCreate() makes a new, empty list, and returns its reference on success. Returns a NULL pointer on failure.
2. int ListCount(list) returns the number of items in list.
3. void *ListFirst(list) returns a pointer to the first item in list and makes the first item the current item.
4. void *ListLast(list) returns a pointer to the last item in list and makes the last item the current one.
5. void *ListNext(list) advances list's current item by one, and returns a pointer to the new current item. If this operation attempts to advances the current item beyond the end of the list, a NULL pointer is returned.
6. void *ListPrev(list) backs up list's current item by one, and returns a pointer to the new current item. If this operation attempts to back up the current item beyond the start of the list, a NULL pointer is returned.
7. void *ListCurr(list) returns a pointer to the current item in list.
8. int ListAdd(list, item) adds the new item to list directly after the current item, and makes item the current item. If the current pointer is at the end of the list, the item is added at the end. Returns 0 on success, -1 on failure.
9. int ListInsert(list, item) adds item to list directly before the current item, and makes the new item the current one. If the current pointer is at the start of the list, the item is added at the start. Returns 0 on success, -1 on failure.
10. int ListAppend(list, item) adds item to the end of list, and makes the new item the current one. Returns 0 on success, -1 on failure.
11. int ListPrepend(list, item) adds item to the front of list, and makes the new item the current one. Returns 0 on success, -1 on failure.
12. void *ListRemove(list) Return current item and take it out of list. Make the next item the current one.
13. void ListConcat(list1, list2) adds list2 to the end of list1. The current pointer is set to the current pointer of list1. List2 no longer exists after the operation.
14. void ListFree(list, itemFree) delete list. itemFree is a pointer to a routine that frees an item. It should be invoked (within ListFree) as: (*itemFree)(itemToBeFreed);
15. void *ListTrim(list) Return last item and take it out of list. Make the new last item the current one.
16. void *ListSearch(list, comparator, comparisonArg) searches list starting at the current item until the end is reached or a match is found. In this context, a match is determined by the comparator parameter. This parameter is a pointer to a routine that takes as its first argument an item pointer, and as its second argument comparisonArg. Comparator returns 0 if the item and comparisonArg don't match (i.e. didn't find it), or 1 if they do (i.e. found it). Exactly what constitutes a match is up to the implementor of comparator. If a match is found, the current pointer is left at the matched item and the pointer to that item is returned. If no match is found, the current pointer is left at the end of the list and a NULL pointer is returned.
Take special note of the fact that many of these routines are mirrors of each other. Prepend is almost the same as append, so code and debug in stages, so that you know you have parts of the program working correctly from day one of starting to work on this assignment. Do not leave it until the last days.
Avoid traversing or searching the list whenever possible. It is possible to avoid traversing/searching in every function, except of course, ListSearch().
Implementation Hints/Requirements
Your code for the solution must consist of six files: list.h, list_adders.c, list_movers.c, list_removers.c, mytestlist.c and Makefile. The header file contains structure definitions and function prototypes, while the three source code files contain function definitions and variable declarations. The test program is the only file that should have a main() function, and it should call the list library routines to create, display, and manipulate the lists. As mentioned in the next paragraph, we will provide a test program to give you some clue as to the kind of testing you could do for the library. Implement in stages, putting the code for each type of list operation in the appropriate source file. ListCurr() and ListCount() should go in list_movers.c.
Since the list item is an arbitrary type, your library CANNOT KNOW how to display it, how to search for it, or how to remove it. These details must all be specified in your test program and communicated to your library via function pointers.
Part of your mark will be determined by the rigorous nature of your testing methodology as well as the implementation of your list libraries.
Compiling and Testing
You must create a Makefile that compiles your list implementation as a library archive (i.e .a file). You must include, in your makefile, the facilty to compile a test program (to be provided by the marker) as your application. The file to do the list testing MUST be named testlist.c. Where the assignment requires test files and test results from you, you are free to name the *executable* for your tests in any reasonable way.
OPTIONAL EXTRA CREDIT PORTION (20 marks)
Memory Allocation Principles. In this version of the assignment, you are to implement the list memory structure so that there are a variable number of list nodes and list headers. This does not mean that you allocate them on-demand. You shall have compile-time constants MIN_LISTS and MIN_NODES, which specify the minimum amount of memory (array size) to allocate for each of these data structures in ONE malloc for each data structure. Keep track of which nodes and lists are available by using a free list. If obtaining a new node or a new list fails, you are to double the amount of memory allocated for whichever resource has filled up (see the man page for realloc()). If you determine that less than half the allocated memory is being used for lists or nodes, you must divide the amount of memory by 2 and copy the used nodes or lists into the new space. Of course, you never go below MIN_LISTS or MIN_NODES. This is the way Java implements arrays and vectors, and the way current versions of the LINUX kernel handle the task_struct array.
Hand In Instructions
Phase 1 deliverables (15 marks: 5 for part A, 5 for part B and 5 for part C):
* design documentation for Part A and Part C. These should be 2 UNIX text files named PartA.design.txt and PartC.design.txt. This should describe your design decisions and ideas of how to progress with the rest of the assignment.
* Completed shell script for Part B.
* Skeleton program that has all the procedures and the interface between the modules. No part of the program needs to do anything except printout the following statement "Got to procedure X", where X is the name of the procedure executing.
* Makefile that compiles all Part A programs and Part C. For Part A, the name of the executables do not matter, as they will be invoked by your shell script in Part B. Your shell script shall be named parentSquares. For Part C, you must make a library named liblist.a, and compile it with a test program called testlist.c to create an executable called testlist.
* Take care to ensure that you do not try and compile Linux code on Windows nor Windows code on Linux. This can be done by if statements in the makefile. SVN log.
Phase 2 deliverables (20 marks: 10 for part A, and 10 for part C):
* Updated design documentation.
* Test plan for all of Part A and Part C. These should be 2 UNIX text files named PartA.testplan.txt and PartC.testplan.txt.
* Working prototype program
o For Part A, you must have Parts A1 and A2 working.
o For Part C, you must implement adding nodes to lists, and the increasing of memory size if memory fills up (if you are doing the extra credit).
* Test results for features implemented. These are to be in PartA.testresults.txt and PartC.testresults.txt
* Makefile to allow the marking script to compile your code.
* SVN log
Final version deliverables (115 marks: 45 for part A, 5 for Part B, and 65 for part C):
* Design documentation
* Working source code
* Test results
* Final versions of Makefiles
* SVN log.
* Bonus features document. Bonus marks (10 marks) will be given for identifying what features you think should be added next to either Part A or Part C. Further bonus marks (10 marks) will be given if successful implementation of these bonus features is achieved.
What to hand in in each phase
1. Create a directory for this assignment.
2. Place in this directory your assignment including the following:
* your source files
* any separate documentation files. For this assignment, design documentation, a test plan, testing verification and other documents as required for each phase.
* a makefile that compiles the executable files required for this assignment.
* SVN log showing the development history for the assignment.
3. The following must NOT be in the directory:
* any .o files or any executable files
* any files having nothing to do with this assignment
* any subdirectories
4. Now you are ready to hand in your assignment. To do so you are going to make a tar file, and upload it to WebCT's assignment hand-in. The TA will then untar the assignment and then run 'gmake' on your set of files to generate the executable files to evaluate your assignment. Please do not gzip the file. I've had problems with different students using different versions of the compression program and it just takes too much TA time.
5. Hand in only one complete solution per team. One of your team members should hand in this part and the other hands in a file (called partner.txt) that says, "I worked with 'X'."
6. That's it - you are done.
