Reference no: EM131643059

Assignment 1: Shell, Processes, Threads, Lists and Intro to Xv6

Part A: Parents, Children and Threads

PART A.1. Write a WINDOWS program that creates multiple threads that each perform a speci?c task until a deadline, without synchronization between the processes/threads of any kind. The number of child threads (threads) and the deadline (deadline) and the maximum integer (size) are to be command-line parameters. Each thread does the same task. The task is given below which utilizes the third command-line parameter (size). The usage is as follows: partA1 threads deadline size.

Parent thread task:

The application should have a parent thread create M child threads.
The parent should then sleep until the deadline. The simplest way to do this is to use the system call Sleep. If the deadline occurs before all children complete, inform the child threads that they should exit. If the deadline has passed, the parent sets a global variable named something like keepRunning to have the value FALSE. The child threads would read this variable each time Square() is called from the main loop

of the parent thread. If you ?nd some other way to do this, you may do so. Please document your solution carefully.

Child thread task: Once created, each child then executes a procedure to calculate (but not print out) the squares of each of the ?rst size positive integers in a loop (i.e., 12, 22, 32,42, 52). The restriction is that procedure Square() cannot use any multiplication operations (I want a simple operation that will take a long time to complete and a lot of stack space). Instead, use the following algorithm:
int Square(N)
{
if (N == 0) return (0);
return (Square (N-1) + N + N - 1);
}

An example invocation of this program is the following: partA1 4 3 200000. This creates 4 child threads, and has each thread compute Square(1), Square(2), Square(3) ... Square(200000) with a deadline of 3 seconds from the time the parent thread starts running.

You may need to have size be a very large number and deadline to be a fairly small number to get interesting results from this operation.

Upon exit, Each child should print the following:

elapsed real time since the child began.
number of invocations of the Square() procedure by this thread. You will need to come up with some strategy for counting the number of recursive calls that does not change the parameter list for Square(). Consider an array of counters, indexed by a parameter (threadId) passed to the thread upon creation. The parent and child threads would both have access to this counter.

You will need to become familiar with the following Win32 System calls: CreateThread(), GetSystemTime(), and Sleep().

PART A.2. Repeat part A.1 in UBC pthreads.

The difference here is the syntax of the thread calls and the process communication. If the time expires before children threads are ?nished, the parent should Kill() the children threads, instead of having them check the shared ?ag. In this case, the parent would be responsible for printing out the statistics for each child that had not ?nished executing when the deadline occurred.

PART A.3. BONUS.2 in Posix threads.

The difference here is the syntax of the threads operations.

PART A.4. 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 ?nished normally and return a success status to the parent. The parent process should be in a waitloop, waiting for each child to ?nish. If each child ?nishes, then it should kill the timer and then terminate normally.

NOTE:

1) For all of these parts, reuse as much code as possible. In particular, the calculation of Squares must be in one C source ?le, and be able to be compiled/linked in with any of the parts. Recall that the .o ?les and executable ?les that you create will need to be distinguished from each other for the different computer architectures (Linux, Windows, Mac, Intel, ARM, Sparc), so create your make?le with care.

2) The marks for Part A will be equally allocated to coding style, execution and testing. A complete description of your design is required, but will receive a lower weighting. Finally, your use of SVN and make will receive some consideration.

3) Phase 1 and 2 have 15 marks in total for Part A.

Part B: Shell script

Write an interactive shell script that executes Parts A.1, A.2, A.3 or A.4 (bonus) according to the user's instructions. The shell script reads the appropriate values from the user and then invokes 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.

A standard format for the interface is required. Therefore, please code your shell program to the following standard.

partB.bash version
where version is one of A1, A2, or A3 (or A4 for the bonus part).

You are free then to develop an interactive menu, and provide error checking, but also make it so that the input can come from a ?le, such as the following:

partB.bash version < inputfile
This should allow a user to provide arguments to the program interactively in a loop until the end of ?le is reached. Have the user input contain 3 integers on each line. NOTE: You should check for invalid input in the bash script as well as in the C program (things like negative numbers, strings, etc).

Note: Phase 1 has 5 marks for Part B. Phase 3 has 5 marks for Part B. Hand in this script for all 3 phases.

Part C: List Library

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 *) ?eld in it to reference the item held by that node. For the purposes of this assignment, though, your code should allow a user to create several lists WHERE EACH LIST HAS A HOMOGENOUS DATA TYPE.

The implementation of the library shall have no dynamic memory allocation on a per-list or per-node basis. The standard way of doing this is to de?ne two static memory blocks at compile time: one for LISTs and one for NODEs. These are separate data types and test code knows only about LISTs and items. It knows nothing about NODEs. It is permissible to dynamically allocate a large chunk of memory for a collection of lists or nodes, but only one allocation at the beginning of the execution. Any other uses of the malloc() function inside the library will result in an implementation grade of 0. Also note that there is no ListInit() function, so you will have to ?nd some way to know when the ?rst execution happens. De?ne a maximum number of LISTs and a maximum number of NODEs and implement the library such that any LIST may have between 0 and the maximum number of nodes at different points in time, but no more than the maximum number of nodes may be in use at any one point in time. Think of the array of NODEs as a pool that may be shared between the lists. Over time, there can also be a different number of LISTs actively being used.

You must create the user-de?ned 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 ?rst item in list and makes the ?rst 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. The current pointer shall be the new last item in the list.

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 ?rst 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 ?nd 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. ListPrepend is almost the same as ListAppend, 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 testing and integration until the last days before the assignment is due. Do not add any other procedures in the entire implementation without checking with the instructor or TA. The requested procedures are the API (Application Programming Interface) to the list library. That means that you many not call an API function from inside the API.

Avoid traversing or searching the list whenever possible. It is possible to avoid traversing/searching in every function, except of course, ListSearch() (and ListFree()).

Implementation Hints/Requirements

Your code for the solution for Part C must consist of six ?les: list.h, list_adders.c, list_movers.c, list_removers.c, mytestlist.c and Make?le.

Note that there is no separate make?le for Part C. There is one make?le for the entire assignment. That means your make?le must know if it is being executed on Windows or Linux and only compile the appropriate portions of the program as requested.

The header ?le (list.h) contains structure de?nitions and function prototypes, while the three source code ?les contain function de?nitions and variable declarations. The test program is the only ?le that should have a main() function, and it should call the list library routines to create, populate, and manipulate the lists. As mentioned in the next section, we will provide a simple sample 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 ?le. 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 speci?ed in your test program and communicated to your library via function pointers. All display debugging that wants to see the details of an item must be located in the test program.

Part of your mark will be determined by the rigorous nature of your testing methodology.

Compiling and Testing

Your make?le will compile your list implementation as a library archive (i.e .a ?le). You must include, in your make?le, the commands to compile a test program (to be provided by the marking script) as your application. The ?le to do the marker's list testing IS going to be named testlist.c. Where the assignment requires test ?les and test results from you, you are free to name the *executable* that executes your tests in any reasonable way. DO NOT hand in any source ?le named testlist.c. If you do, our script will overwrite that ?le and your testing will disappear.

Mark Allocation. Marks will be allocated roughly equally between implementation, and testing in the ?nal phase hand-in. A small portion of the marks will be allocated to proper use of SVN and adequate construction of the make?le lines appropriate for each component.

Part D: Xv6 System Call (30 marks - phase 3 all)
For this part of the assignment, you will download, con?gure and compile a simple operating system kernel (xv6). You will need to read parts of the kernel to understand its structure, and ?nally, you will make a small modi?cation to the kernel.

Your task is to add a system call csinfo() that returns an integer value giving the number of context switches that took place in the process from the time it started.

You will also need to write a userspace program to test your new system call. Your userspace program should do some simple tasks (make some function calls, maybe even use the task from Part A, forking off children processes, or sleep) and invoke your new system call periodically and then print the result. Recall that xv6 does not natively support multi-threaded processes.

You will need a counter in the proc structure to keep track of this value, and to determine where to increment it. Some tips:
Find some other relatively simple xv6 system call, and look at how it is implemented. Look at the code in xv6 that uses the process table.
Attend tutorials to get some pointers on how to add an xv6 system call, and how to create a new userspace program that you can use with xv6.

Part E: Shell (30 marks - Phase 3 all)
The assignment is to program a shell program that conforms to the speci?cation given in this section. The shell should have the following features:

Print a command prompt that also displays the current working directory. Allow the user to enter commands and execute these commands.

The entered command string must be tokenized into an array of strings by removing the space delimiters. Also delimiters consisting of more than one space must be handled correctly.
Implement exit (to exit the shell) and cd (to change the current working directory) as built-in commands. The cd built-in command should display errors if necessary.
Ability to ?nd program to be launched in the ?le system using a hard-coded array of standard locations in case the name of the executable is not preceded by an absolute or relative path. You must implement this yourself, do not use execlp or execvp.
Display an appropriate error if a requested command cannot be found or is not executable. Execute commands and correctly pass the provided arguments to this command.
Execute commands that contain a pipe character by starting two new processes that are interconnected with a pipe. Your shell should be able to handle data streams of arbitrary length.
Note 1: your shell only has to be capable of running commands that contain a single pipe character. Check how many pipe characters a command contains and simply display an error if more than one pipe character is found.
Note 2: to simplify implementation, you only have to deal with the case that the pipe character is separated by spaces, so the tokenizer you have to implement already creates a separate token for the pipe character. For instance a command of the form "cat Makefile|wc -l" does not have to be handled correctly by your program.

Hand In Instructions

NOTE: All ?les must be UNIX text ?les. That is where the marking is going to take place for the most part, and it is very annoying for the marker to have to examine code with extraneous characters messing things up. As well, the Mac ?lesystem creates ._?les for many of the ?les that get modi?ed. If you use a Mac, please remove all of these ?les. There must be no lines longer than 80 characters. If you write on Windows, make sure you use a program to convert the text ?le to a UNIX ?le (man dos2unix, use a 'tr' command to get rid of the unwanted characters, or better yet, just don't write documentation in Windows for this course).

Phase 1 deliverables:

design documentation for Part A and Part C. These should be 2 UNIX text ?les 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. Your shell script shall be named partB.bash.
Skeleton programs that have all the procedures and the interface between the modules for both Parts A.1 and C. No part of the programs need to do anything functional except check that the correct type and range of parameter values have been passed between caller and callee and printout the following statement "Got to procedure X", where X is the name of the procedure executing, or "Error in procedure X: invalid parameter Y", if the interface rules have been broken by the caller. This is done by having the main() program call every function and having the function check for error conditions and return appropriate error values.
Make?le that compiles all Part A programs and Part C. For Part A.2 and Part A.3, have commands that compile a dummy pthreads and Posix threads program, respectively. Nothing has to execute for PartA.2 and A.3. For Part C, you must make a library named liblist.a, and supply a test program called mytestlist.c and lines in the make?le to create an executable called mytestlist. For Phase 3, we will use our own test program to verify the functionality of your assignment.
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 make?le.
SVN log. Logs of the commits done. There should be commits done by both partners.

Phase 2 deliverables :

Updated design documentation.
Test plan for all of Part A and Part C. These should be 2 UNIX text ?les named PartA.testplan.txt and
PartC.testplan.txt. Working prototype program
For Part A, you must have Parts A1 and A2 working.
For Part B, hand the script in again. There are no marks allocated for it in this phase, but hand it in, so we can test your parts A.1 and A.2.
For Part C, you must implement adding nodes to lists, and the increasing of memory size if memory ?lls 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.
Make?le to allow the marking script to compile your code. SVN log

Phase 3 deliverables (145 marks: 40 for part A, 5 for Part B, 70 for part C, and 30 for Part D, 35 for Part E): For parts A, B, and C, hand in the following:
Design documentation (Part[ABC].design.txt) Working source code for all subparts
Final test plan for all subparts Test results for all subparts

Final versions of Make?le that compiles Windows executables on Windows and Linux executables on Linux. The list library should only be compiled on Linux.
SVN log.

For Part D, hand in the following:

Design document: PartD.design.txt Diff ?le of the changes you made
tar of the source ?les only (including make?le) of the xv6 directory named explicitly xv6-A1.tar (this can be done with a 'make clean' and then tar).
test results of your program and instructions for how the marker can reproduce them svn logs of the work done by both partners

Bonus features document. Bonus marks (10 marks) will be given for identifying what features you think could 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.

For each phase

1. Create a directory for this assignment (e.g. a1-phase1).

2. Place in this directory your assignment including the following: your source ?les
any separate documentation ?les. For this assignment, design documentation, a test plan, testing veri?cation and other documents as required for each phase.
a make?le that compiles the executable ?les required for this assignment. SVN log showing the development history for the assignment.

3. The following must NOT be in the directory: any .o ?les or any executable ?les
any ?les having nothing to do with this assignment
any subdirectories, especially not the entire contents of your SVN repository.

Any failure to meet these requirements will result in a grade of 0. We just do not have the time in the budget to repair your assignments so that they will properly compile with the marking scripts that we have developed. ALL FILES MUST BE IN THE ROOT OF THE DIRECTORY THAT IS TAR-ED. YOUR xv6 TAR FILE WILL EXPAND INTO A HIERARCHY AS IN THE ORIGINAL, BUT THE TAR FILE MUST BE IN THE ROOT.

4. Now you are ready to hand in your assignment. To do so you are going to make a tar ?le from within the directory that you have placed all your ?les, and upload it to Blackboard's assignment hand-in. The TA will then untar the assignment and then run 'make' on your set of ?les to generate the executable ?les to evaluate your assignment. Please do not gzip the ?le, or use any other types of compression. 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 ?le (called partner.txt) that says, "I worked with 'X'."

6. That's it - you are done.

You have to do only Part B.