Assignment 12, due Nov. 22

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: Consider the buddy system implementation distributed in the skeleton solution to MP6, along with the mymalloc code that converts between the malloc()/free() API and the requirements of the buddy system.

    a) A design choice was made here, to have the free-list index passed to the buddy system interface routines instead of passing the size of the desired block. This makes mymalloc() do extra work computing the log2 of the block size. Does this lead to an overall savings in computational effort, or does it merely move work from buddyalloc() to mymalloc(). Explain. (0.5 points)

    b) In buddyfree() the code contains a loop searching the free list. Why wasn't the loop written like this?

    /* search for budy in free list */
    b = freelists[i];
    for (;;) { /* loop exit by break */
           if (b == NULL) {
                  /* put p at start of list */
                  *(void **)p = freelists[i];
                  freelists[i] = p;
                  /* quit loop */
           if (((intptr_t)p) == (((intptr_t)b) ^ (1 << i))) {
                  ... etc ...
                  /* free result of merger */
                  buddyfree( p, i + 1 );
           /* walk down list */
           b = *(void **)b;
    (0.5 points)

  2. Background: Consider these alternative ways to link two UNIX processes where one process produces data that is consumed by the other:

    a) Which of these options give (or gives) the programmer control over the size of the bounded buffer. (0.5 points)

    b) Which of these options has the potential to be more efficient, in terms of the number of system calls required to move the data? Explain. (Count only calls used to move data after the initial communication channel has been set up.) (0.5 points)

  3. Background: The Unix kernel was largely developed before semaphores were invented, and the semaphore services in the Unix kernel were added as afterthoughts. Many important Unix utilities such as sendmail were developed before before these afterthoughts were added. Named pipes are also an afterthought; in the original Unix, for two processes to communicate through a pipe, that pipe must have been created by an ancestor that forked to run the two in parallel.

    Classical Unix did, however, have the following services that are relevant here:

    Classical Unix applications (still, to this day) use what are called lock files for critical section synchronization. A lock is considered to be claimed (indicating that a process is in the associated critical seciton) if the lock file exists. Busy waiting is used to enter critical sections, with the CPU demand reduced by throttling back the polling rate using timers.

    a) Write a C function called delay1() that causes the calling process to wait one second. The only kernel calls required are mentioned above. (0.4 points)

    b) Give a fragment of C code to enter a critical seciton guarded by the lock file /usr/mail/lock -- your code should cally your delay1 routine each time it polls the lock. The only kernel calls required are mentioned above. (0.4 points)

    c) Give a fragment of C code to exit the critical seciton guarded by the lock file /usr/mail/lock. The only kernel calls required are mentioned above. (0.2 points)