UTSA CS 3733 Operating Systems Assignment 1 Spring 2001

CS 3733 Operating Systems, Spring 2001 Assignment 1

Information here is subject to change

Due Thursday, February 8, 2001

The purpose of this assignment is to make sure you are familiar with C programming, string manipulation using pointers, use of makefiles, and separate compilation. It is also meant to see if you can follow directions and read and understand man pages.

Keep in mind the following:
If you have a working (or almost working) copy of a program, do not modify it before saving the old copy.

Use the cover sheet here as the first sheet when handing in your assignment. Make sure you include your makefile and lint output.

Make a directory called assign1 for this assignment. Keep all programs for this assignment under this directory. Copy all of the files from /usr/local/courses/cs3733/spring2001/assign1 to this directory. You should have a makefile and two include files. You can modify the first line in the makefile as you start additional parts of this assignment.

Each of the main programs described below should start by printing a line containing your name to standard error.

You should make sure you understand all lint error warnings generated and eliminate those that indicate a real problem.

Part 1. Safe readline

Write a function:
char *readline(int fd)
which reads a line from the given file descriptor and returns a pointer to the line read in. It returns NULL if an error occurs.

The function should be in the file utility.c.

This function will allocate storage necessary for the line.
Any storage that it allocates which is not needed should be freed.
If a non-NULL pointer is returned, that pointer should be able to be used as an argument to free.
If an end-of-file is reached before a newline, the string read in will be returned without the newline at the end.
Otherwise, the string returned will end in a newline.
If a non-NULL pointer is returned it will point to a string. That is, there will be a string terminator inserted at the end.
A string terminator found in the input should be ignored.
The amount of storage allocated (but not freed) should not be more than 128 bytes more that what is required to hold a string of twice the length of the string returned.
If an end-of-file is reached before any characters are read, the string returned will be empty (not NULL).
A call to readline should not interfere with a later call to read additional characters from the same file descriptor.

Use the makefile (suitably modified) to compile and lint your program.

Write a main program called testpart1 for testing this function.

Answer all of the questions on the cover sheet.

Part 2. Reading in a file

Write a function:
char **readfile(char *filename);
which reads in a file and returns an NULL-terminated array of pointers to the lines of the file. It returns NULL on error. Put this in utility.c.

Use your readline from Part 1.
Do not make any assumptions about the size or type of file that you will be reading.
Do not assume that you can do a seek on the file.
Do full error checking.
Do not do any I/O except for that necessary to read in the file.
Do not print any error messages.
Do not waste a lot of memory.
Free any unused memory.

Also write a function:
void printarray(char *lines[], int size);
which outputs the array of strings. All output should be to standard output and nothing else should be output except these lines.

Write a main program called testpart2 that takes one command line argument that is the name of a file. It uses readfile to read in the file and printarray to output it. By redirecting the output to a file your should be able to create a file which is identical to the input file.

Part 3. Timing functions.

Read the manpage for gethrtime and the related data structures. Use these to write the following functions and put them in utility.c

void start_time() that gets the current time and saves it in a variable in utility.c that has internal linkage. This time mat be relative to an arbitrary time in the past and not related to the real time. You may use any appropriate format, but it should have as high a resolution as possible.
void end_time() does the same as start_time but uses a different variable.
double elapsed_time() that returns the number of seconds between the last call to end_time() and the last call to start_time. The result should be positive if start_time was called first.

Copy testpart2 into testpart3 to test these. It should print out the times for reading in and writing out the file. Make sure you do not include the time for any other I/O. All of this output should go to standard error so as not to interfere with printarray.

Part 4. A simple sort

Create a file called sorting.c that contains a function:
void slowsort(char *lines[], int size);
that will sort an array of strings. Use an order n² sort such as a bubble sort. Do not move the strings themselves, just manipulate the pointers in the array.

Write a main program called testpart4 that takes one command line argument that is the name of a file. It uses the functions of the previous parts to read in the given file, sort it, and output it to standard output. Use your routines from Part 3 to output to standard error the number of lines int the file, the time for reading in, the time for sorting, and the time for outputting the result. All times should be in seconds with at least 6 places after the decimal point. Make sure you do not include the time for any other I/O such as your print statements. You can compare the results to the results of using the sort command. Test your program on at least 4 files having a range of sizes. The largest one should take a few seconds to sort. Do enough tests to convince yourself that the sort is really order n². Make a table giving the number of lines in the file (n), the time to sort, and the time divided by n².

Make sure all timing tests are done on the same machine when the machine is not being heavily used. Record which machine you used for timing tests.

Part 5. (Optional)

Write a function fastsort that can be used in place of slowsort but is order n log n. A heapsort is one possibility. Write a main program called testpart5 that is like testpart4 but uses this faster sort. Make a table as in Part 4, but use n log n rather than n². You should use at least one file large enough to make the sort take at least 100 milliseconds.