Assignment 9, due Apr. 15

Part of the homework for 22C:112, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

On every assignment, write your name and the course number legibly. Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

  1. Background: Suppose a programmer wanted to build a garbage collector to use with programs written in C and C++. Compilers for these languages all assume that applications will explicitly free unused objects, so the compiler never bothers maintaining any data structure analogous to tags on the words of memory to tell if a word contains a pointer or other data.

    One way to build such a garbage collector would be to assume that the value in every word of memory is a pointer, whether it is actually a pointer or actually a floating point number, integer, or a fragment of a character string. All you need to assume is that all of the pointers are aligned on word boundaries -- something most compilers do for performance reasons.

    In a garbage collector that relies on tags, once it inspects a word and finds that the tag on that word indicates that it is a pointer, it knows that the pointer is legitimate and it can safely follow it and mark the object it points to.

    In a garbage collector without benefit of any kind of tags, where some words contain legitimate pointers and others do not, you can quickly check to see if a word is not a pointer by seeing if it points within the range of memory addresses allocated to the heap. All values that, when interpreted as pointers, don't point into the memory being managed by the heap manager, must not be pointers. (or, if they are, they are of no concern to the garbage collector).

    a) A word is found that seems to point to an object in the heap region of memory. It might be a coincidence, or it might be a real pointer to that object. What is the impact of this on the performance of the garbage collector? Assume that the object really does exist in the heap. It is only the pointer that is in doubt. (0.5 points)

    b) Part a said "seems to point to an object in the heap region." How could you determine if a pointer seemed to point to an object, as opposed to merely pointing somewhere between the start and end of the heap? Note that this problem has actually been solved by real garbage collectors that are available as afterthought add-ons for C and C++ programming environments. (0.5 points)

  2. Background: Take a look at the User Level Threads package indexed from the course web page. This package works on implementations of C on 32-bit machines, but it does not work on 64-bit systems. Indexed under the main page for the thread package, you will find the source code for the thread package.

    The central mechanisms in this package revolve around the struct thread data type, current, the current running thread, and readylist, a queue of threads. The declaration of these is near the center of the source file, after a horrible prologue consisting of code to reverse engineer the C implementation enough to be able to launch threads.

    The central interface user code calls to transfer control from one thread to another is the relinquish() routine. For this problem, all you need to examine in any depth is the struct thread type and the relinquish() operation, plus the standard C library routines longjmp() and setjmp(); all of the available documentation for the latter shows how they are used for exception handling, so the use made in the thread package is, formally speaking, an abuse.

    a) What must be stored in the objects of the jump_buf data type for this to work? The answer depends as much on your understanding of how function calls are implemented in assembly language as it depends on any of the standard C documentation. It is more likely that you will successfully answer this question by inventing the answer than by using Google. (0.5 points)

    b) Suppose you write code for one thread of a multithreaded application, and your thread calls the relinquish() routine. How does control return to the caller? (0.5 points)

  3. Background: Consider this set of function calls:

    If calling a() outputs A and calling b() outputs B, etc, then this set of constraints permits ABCDEFG or ACBEDFG or ABDEFCG or a number of other orderings.

    A Problem:

    Give a C main program that calls these functions allowing for maximal parallelism. You will need to use fork(), exit(), and wait() or waitpid() to do this. If you opt to experiment with your code, use write(1,"A",1), for example, to output the letter A, instead of using C streams, in order to avoid problems with stream buffering obscuring what is really going on. (1.0 points)


Write a heap manager, using the heap implementation of your choice. The interface to your heap manager will be mymalloc() and myfree() with calling sequences that are fully compatible with the calling sequences of the heap manager in the C library. Your heap manager should use static initializaiton of global variables on startup, so there is no need for a separate initializer -- although you may need to write an initializer routine that mymalloc() calls the first time it is called. Note that the header file <stdint.h> declares the useful integer types intptr_t and uintptr_t, signed and unsigned integer types large enough to hold a pointer. When you need to do arithmetic on pointers, cast the pointer to one of these types, do the arithmetic, and then cast it back to the pointer type if needed. Note that the choice between signed and unsigned integer types depends on the particular arithmetic you intend to do. Also note that size_t is an integer type big enough to hold a block size. Your heap should have a capacity of 3000 bytes. We will use a variation of the exercise program given in Homework 8 to test it, with an average demand of 2500 bytes. This is high enough that our exerciser should frequently cause your allocator to return null because no sufficiently large block is available on the heap. If your solution to the machine problem is in mp4.c and your test code is in file mp4test.c, your test program can call mymalloc() and myfree() by including the following two lines in the test program before the main program:

     void * mymalloc(size_t size);
     void myfree(void * ptr);

Finally, to compile and run your program, the following shell commands will work:

     void * mymalloc(size_t size);
     void myfree(void * ptr);
Finally, submit your work in the usual way, in the mp4 submission directory, and submit it before midnight, April 11.