Homework 8

22C:116, Fall 1998

Due Monday Oct 26, 1998, in class

1. Background: Consider the problem of writing a garbage collector for the heap manager used for C and Pascal programs. Assume that the heap manager provides the malloc and free services that are usual with programming languages such as C; and assume that boundary tags separate heap blocks, so that next-block(b) and prev-block(b), for any block b in the heap, will give you its neighbors, and assume the heap runs from first-block to last-block. Also assume sizeof(b) gives you the size of block b.

   Also, assume that current-ar gives the pointer to the current activation record, that prev-ar(a) gives a pointer to the previous activation record on the stack under the activation record a, and that global-ar refers to the activation record at the base of the stack to hold all global variables.

   Assume that memory is word addressable, assume that block(p), for any pointer into the heap, returns the heap block containing the referent of p. If p is a pointer to an address outside the heap, block(p) returns nil.

   Assume that the heap manager includes a word in each heap block that is available for use by a grabage collector. If b points to a heap block, b->gc is this word.

   Part A: Write detailed pseudocode for a mark-sweep garbage collector that will work in this environment

   Part B: Suggest an implementation of the block(p) function. This is not trivial!

2. Do problems 3 and 4 on page 394 of Tannenbaum.

3. Background: The term kernel was originally introduced in the context of simple computer systems. The services offered by our thread package are an example of traditonal kernel services, and as originally intended (not as used in the context of the UNIX system), the kernel was supposed to be used to implement such operating system services as the file system, window manager and other system services relied on by the user.

   The Problem: How does such a kernel differ from the kind of microkernel discussed by Tannenbaum in Chapter 9?

4. Examine the UNIX man page for the socket() system call, and examine any of the other services listed under the SEE ALSO header on the man page. What level(s) in the ISO OSI protocol hierarchy does the socket() service expose to the user?