Assignment 11, due Nov. 15

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

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers 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: The classical states of a process (from the perspective of a process manager) are ready, running, waiting and dead. What process state changes are associated with each of the following? You must give both the former state and the new states for each process that changes state in each case, and identify the processes as much as possible. (In some cases, you may need to say: "some other process," or say that it changes from or to "either state a or b"). (0.2 points each)

    a) A program calls read() and the requested data is not yet available.

    b) The disk interrupt handler signals a process that its write() has completed.

    c) A user types control c for a process that has no handler installed for the SIGINT signal.

    d) A program calls exit().

    e) A program calls setpriority() to lower its priority below that of some ready process.

  2. Background: In the discussion of I/O earlier in the semester, we wrote code like this, in the interrupt-driven FIFO-queue based input/output driver:
    	while (inq.empty()) do /* polling loop */;
            return inq.dequeue();

    A Problem: How should we change this now that we have multiple user processes and a scheduler? (0.5 points)

  3. Background: Consider the code for the wait() and signal() operations on semaphores. The lecture notes for Nov. 13 include example code to implement semaphores. This code makes good sense under a round-robin scheduler, but it is incorrect under a priority scheduler because it can lead to priority inversions, where the current running process can end up having a lower priority than some ready process. Identify the point in the code where this inversion could begin. (0.5 points)

  4. Background: Consider the problem of writing drivers for sequential input and output devices. FIFO queues play an important role. For a FIFO queue connecting two processes at the user level, each enqueue involves a wait() for free space and a signal() that data is available, and each dequeue involves a wait() for data and a signal() that free space has been created.

    When one end of the queue is in a user process and the other end of the queue is in an interrupt service routine, things are more complex.

    a) (0.5 points) When a user process needs to signal an interrupt service routine that a resource it might need is available, can it use a semaphore? Explain any constraints.

    b) (0.5 points) When an interrupt service rutine needs to signal a use process that a resource it might need is available, can it use a semaphore? Explain any constraints.


Machine Problem VI

Due Monday, Dec. 2

This problem involves using sbrk() in the context of the buddy system. See problem 1 in assignment 10.

Here is a test program for any implementation of malloc. In this case, the program calls mymalloc() so it can test your heap implementation. All it does is repeatedly and randomly call either the allocate or free routine.

-- mp6test.c

Here is a shim, a bit of software to sit between the test program and a buddy-system implementation of the heap manager. It's job is to make a user interface compatable with the C standard malloc(), except named mymalloc() in this case, based on the buddy system.

-- mymalloc.c

Finally, here is a buddy system implementation of the heap manager. This code has been thoroughly tested using the above tools, and then the piece of code that uses sbrk() to get more memory has been deleted.

-- mp6skel.c

These programs use the following header files:

/* mymalloc.h */

void * mymalloc( intptr_t size );
void myfree( void * p );


/* buddy.h */

/* buddy system allocate one block of size 2 to the i */
void * buddyalloc( int i );

/* buddy system free the block p of size 2 to the i */
void buddyfree( void * p, int i );

/* buddy system enlarge the heap by at least size bytes */
void enlargeheap( int size );

Your job is to write the missing code.

As usual, your solution should have the name mp6.c and it should have your name in the header comments, while retaining credit to the original author. Failure to put your name in the header comments will be severely penalized.


A student asked: "p = sbrk(s) returns a pointer p to at least s bytes. How do we find out the actual size of the block p points to?"

The man page for sbrk() says: " The current value of the program break is reliably returned by ``sbrk(0)'' ..."

From this, we conclude the following:

p = sbrk(s);
q = sbrk(0);
blocksize = (intptr_t)q - (intptr_t)q;

A student asked how to find the pointer address of the desired block to be inserted into freelist[i].

That is asking the question backward. Using the pointers p and q from above, p is the desired pointer. What you need to do is find the correct value of i. Specifically, what you want to do is find the largest value of i such that:

If this works, you can add the block pointed to by p to the appropriate freelist. That may be as simple as calling buddyfree(p,i). Having done that, if you didn't dispose of the whole block, advance p by 1<<i and then go through the whole exercise again.

As I said in lecture, you will find that there's a pattern here. You will deallocate larger and larger free blocks up until the largest block that fits in size s, and then smaller and smaller blocks. Except in rare cases where the whole block, by blind luck, happens to be aligned, if the initial block size s is a power of two, the largest free block you find will be half that size.

A student asked: "why call buddyfree() to put blocks on the free list inside enlargeheap(); why not just put them directly on the free list?"

First, note that buddyfree() includes the code to link a block to the free list, so it avoids the need to duplicat this code. There is another reason to use it: Suppose the call to sbrk() returns a region of memory that includes a block that is the buddy of a block already on the free list. That block should be merged with its buddy when it is put on the free list and buddyfree() does this.

Note that enlargeheap() cannot just do this:

buddyfree( sbrk( 1 << i ), i);

The address returned by sbrk() is unconstrained. A call to sbrk(32) for example, might return 42 (decimal), allocating a block of size 32 that ends at address 73. Under the rules for the buddy system, this would have to be treated as follows:

On a 32-bit machine, the minimum block size under the buddy system is 4 bytes (one pointer in a free block), so you should not try to free blocks of size 2 and 1. Check the value of sizeof(void*) to find the minimum block size.

A student asked if the logic of enlargeheap() depends on whether it is creating an initial heap or enlarging an already existing heap. It does not!

A student asked for a hint to help figure out what the error was. Not having explained any of the debug output he sent me, I had to suggest a wild stab in the dark. Consider putting debug output in enlargeheap() so that, whenever a block at address p is added to freelist i your code tests to see if
    (p & ((1 << i) - 1)) == 0
and gripes loudly if this test fails. Any violation of this condition will break the buddy system code.

Make sure to delete your diagnostic and debugging support code before you turn in your work.

A student asked: "If I want to add a block of size s = 1<<i to the heap, why not just do p=sbrk(0) once, then keep incrementing p until it has i trailing zeros, then call brk(p+(1<<i)) to enlarge the heap?"

This is bad for two reasons, both having to do with gross inefficiency. First, it is computationally inefficient. This solution searches for a value of p with i trailing zeros using a linear search, when it could do it using a logarithmic search -- where the number of iterations is proportional to i.

And second, this wastes memory by simply discarding all the memory skipped over while incrementing p until the desired condition is met. In the worst case, it will waste half of the available memory. Good solutions should place the memory skipped over on the heap as smaller blocks -- they might be useful later to meet other demands on the heap.