Homework 3 Solutions

22C:116, Fall 1998

1. Part A: The major differences between the implementation of semaphores given in the assignment and the implementation given at the end of the notes for lecture 3 are as follows:
   • The implementation in the notes enforces mutual exclusion by enabling and disabling interrupts. The implementation given in the assignment does not do this because (so long as UNIX signals are not involved) there is no need, within one UNIX process, to do so.

   • The implementation in the notes gives no details about how the process state is saved or restored, but it implies that the subroutine call or interrupt service routine entry saves the state, and that the return restores the state. The implementation given in the assignment saves and restores the caller's state using setjmp() and longjmp().

   • The implementation of wait() given in the notes does not allow for the possibility that the ready list might become empty, for example, because of a deadlock. The implementation given in the assignment allows for this and reports a "possible deadlock" error.

   Part B: It is desirable to include a completely different definition of the type semaphore in the header file than is included with the C source code so that the user of the header file is isolated from all details of the implementation of semaphores. This problem was hard for some students because they assumed that the header file threads.h should have been included in threads.c; in fact, many "fixed" threads.c to correct this "error" and then found that the suggested alternative definition of the semaphore data type lead to a compile time! In fact, the omission of an include file for threads.h in the file threads.c was deliberate!

   Part C: No answer given!

2. For the Fibonacci boundary tag algorithm, where free blocks are of sizes {1 2 3 5 8 13 21 34 ... }. Given a block at address a and of size n, where you know that n is a Fibonacci number, and given that pred(n) and succ(n) are functions that yield the previous and the next Fibonacci number, there are two possible sets of addresses and sizes for the potential buddies of a block:
   • If a block of size n is broken into a block of size pred(n) followed by a block of size pred(pred(n)) -- largest block first -- then the rule for buddies is:

     There are two possible buddies of a block of size n at address a:

     • a smaller block of size pred(n) at address a+n.
     • a larger block of size succ(n) at address a-succ(n).

   • If a block of size n is broken into a block of size pred(pred(n)) followed by a block of size pred(n) -- smallest block first -- then the rule for buddies is:

     There are two possible buddies of a block of size n at address a:

     • a smaller block of size pred(n) at address a-pred(n).
     • a larger block of size succ(n) at address a+n.

3. The answer to problem 11 from Chapter 3 in the text:

   The virtual address has the following format:

           19               13
   |__________________|____________|
       page number     thing in page
   

   I have deliberately avoided mention of the nature of the addressed object by using the term "thing in page". The machine could have a word-addressable memory with 8K words per page, or it could have a byte-addressable memory with 8K bytes per page, or it could have a bit addressable memory with 8K bits per page. None of the answer depends on this!

   This implies that there are 2¹⁹ or about 0.5 million pages per address space. If the entire page table is copied from memory to the MMU at the start of each timeslice, 0.5 million entries must be copied. If it takes 100 nanoseconds to copy each entry, the time to copy the entire map will be 50 milliseconds. If we make a new copy every 100 milliseconds, we must spend 50 percent of the CPU time making these copies!