Assignment 9 Solutions

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)

If the word was not intended to be a pointer, and the object to which it points was not reachable by any real pointer, then that object should be collected as garbage, but our garbage collector will mistakenly mark it as reachable and will not collect it. In sum, the collector will not collect some garbage, so the user will need a larger heap than would be needed with a more strongly typed language where the garbage collector could accurately tell which values were pointers.

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)

Here, the challenge is, given a pointer to an arbitrary address, find the start of the object containing that address. This is a search problem. A linear search of a boundary tag heap would find the boundary tags above and below the pointer, but it would not be very efficient. If the boundary tags were arranged in a binary tree, we could get a log(n) solution, but even this sounds annoyingly slow. A hash table hashing addresses to "is this address the first address in an object" could help reject false pointers.

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)

A jump_buf must contain, at least, a copy of the stack pointer (or activation record pointer) and return address. Having the jump buffer contain all of the saved registers is wasteful, but it works.

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)

You call relinquish, which saves your thread on the thread ready list. Some other threads run, and eventually, your thread reaches the head of the ready list. At that point, some thread calls relinquish or waits on a semaphore, and your thread is removed from the ready list.

That was just the prologue. The core of the answer is this: Either wait or relinquish calls longjmp to transfer control to you. The result is that the code of relinquish -- running on your stack, comes alive again, right after the call to setjmp, and it returns to your code.

• a() must be called first
• b() must be called after a()
• c() must be called after a()
• d() must be called after b()
• e() must be called after b()
• f() must be called after d() and e()
• g() must be called after c() and f()

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)

The following solution is dangerous but it might work. The problem is, we do not control which child we are waiting for. It should work because no process creates multiple children before it waits.

main(){
    a();
    if (fork()) { /* parent */
        c();
        wait(NULL);
    } else { /* child */
        b();
        if (fork()) { /* parent */
            d();
            wait(NULL);
        } else { /* child */
            e();
            exit();
        }
        f();
        exit();
    }
    g();
}

The following very similar solution is wrong and does not work because one process creates two children and then waits for either to terminate.

main(){
    a();
    if (fork()) { /* parent */
        b();
        if (fork()) { /* parent */
            d();
            wait(NULL); --- error, the exit after C could signal this wait!
        } else { /* child */
            e();
            exit();
        }
        f();
        wait(NULL);
    } else { /* child */
        c();
        exit();
    }
    g();
}

The following conservative code is much safer, since there are no ordering constraints on the branches and it is explicit, with each wait, which child it is waiting for.

main();
    pid_t child1, child2;
    a();
    if (child_id = fork()) { /* parent */
        b();
        if (fork()) { /* parent */
            d();
            waitpid(child2, NULL, 0);
        } else { /* child */
            e();
            exit();
        }
        f();
        waitpid(child1, NULL, 0);
    } else { /* child */
        c();
        exit();
    }
    g();
}