The Operating Systems Course

Exercise 8: Learning Unix and C

Goals

Learn the Unix environment: File and directory handling, editing and compiling files, first look at makefiles and libraries.
Use central features of the C language: Memory allocation and arrays, the preprocessor, passing functions as arguments.

Important: Before starting, read the exercise guidelines for this semester!

First Look at Unix

Your best friend in Unix is the man command. Make sure you are familiar with the following commands (type "man chmod", for example):

ls, cp, mv, rm, mkdir, rmdir, cd, more, head, ps, chmod, finger, who, date

In order to execute a command in the background, end the line containing it with a & sign (as in "emacs &"). Also make sure you can open new terminals and other programs by clicking the left moue button on an empty spot on the screen.

Your programming tools are emacs - the editor, gcc - the compiler and linker, ddd - the debugger, and gmake - which aids in maintainance. Emacs and ddd have help menus which are well worth a look, while gcc and gmake have man pages.

Take some time to learn the basic key combinations of Emacs - it will more than pay itself back, and soon.

The Dynamic Array Library

You will implement a library that defines a container data structure, which grows dynamically as items are added to it but still can be randomly accessed in constant time complexity. You must use the exact header file we supply, named libdarray.h. It contains the headers of the ten functions that must be implemented, with documentation on what each of them should do.

You should write a single file called libdarray.c to implement the library.

The header file contains preconditions for some of the functions - in this exercise, check them using the assert(3) function. This means that we give the responsibility for checking argument correction to the caller of the library functions. You may also place assertions anywhere in your code where you feel it to be helpful.

You must implement the library as an array of pointers. When you need to allocate memory for new insertions into the array, you are allowed to copy the existing elements of the array to a new location in memory. See the malloc(3), realloc(3) and free(3) about memory allocation. However, you should not copy the entire array every time a new element is inserted, since this would be too inefficient; allocate for future insertions in advance.

When removing an element from the array, say the n'th element, you may copy all elements that come after it one step backwards in the array. This means that the n+1'th element will become the n'th element, and next elements will change places as well. This has the disadvantages that a removal takes O(n) time and that references into the array are invalidated after a remove(), but has the advantage of being easy to implement :-).

Second, when quick-sorting an array, you are allowed to use the qsort(3) function that comes with the standard C library, instead of implementing the algorithm yourself.

Programming-wise, the exercise is quite short and easy. Most of your time is expected to be taken on learning the environment, syntax and other technical details.

Testing the Library

Copy this Makefile to the directory in which you are working (note: Do not copy and paste it from the browser. Use the 'Save as...' option instead so that tabs won't be converted to spaces). When running the gmake command, this file will be used. It contains instructions to look for two files named libdarray.h and libdarray.c in the current directory, compile them into an object file named libdarray.o and turning it into a library named libdarray.a. Running gmake will print compiler error and warning messages on the screen if any; if there are no problems, no message will be printed.

In order to use the library (for example, to test it), write a C file with a main() function that includes libdarray.h and uses the array typedef and functions. Two such example files are test1.c and test2.c. In order to compile and link such a file, the files libdarray.h and libdarray.a should be in the same directory with it. To compile test1.c, for example, type:

gcc test1.c -o test1 -Wall -ldarray -L.

Remember that Unix is case sensitive (that is, -o and -O are two different switches). If you'd like to use the debugger on the resulting executable, add the -g switch to the gcc command. If there are no errors, this command should create an executable file named test1 in the current directory.

Solve this exercise alone! If you rely on others now, you'll have little chance to catch up in future exercises. However, you are encouraged to share tests you write with other pairs.