Homework 4

22C:116, Fall 1998

Due Wednesday Sept 23, 1998, in class

Douglas W. Jones
  1. Background: The dining philosopher's problem is the basis of the cover illustration on Tannenbaum's text and it is discussed, at length, on pages 57 to 59 of the text. There are many solutions to this problem!

    A quick examination of the dining philosopher's problem shows that it is never possible for more than two philosophers to eat at one time. Therefore, one solution which is guaranteed to be deadlock free involves adding two tokens to the table, perhaps salt shakers. If each philosopher first collects a salt shaker before attempting to collect forks, then eats, and then puts the salt shaker back, it will be possible for up to two philosophers to eat at once.

    Part A: Explain any difference in performance you would expect between the above solution to the dining philosopher's problem and the solution in Figure 2.20 of the text. Would one solution sometimes allow two philosophers to dine in parallel when the other forces one or the other to wait?

    Part B: Consider the following implementation of the think() operation for use under our example thread package:

    void think()
    {
        int i;
        do {
            thread_relinquish();
        while (random() & 7);
    }
    
    Using this version of relinquish (with appropriate initialization of the random number generator), and using thread_semaphore objects to implement the synchronization required for forks and salt shakers, implement the above solution to the dining philosopher's problem under our thread manager.

  2. Background: Refer to the discussion of the clock algorithm in the notes and on page 111 in the text. Assume a machine with the following characteristics:

    The MMU has t TLB entries, the main memory has space for f page frames, and the address space allows p pages, where t < f < p. Each TLB entry has three fields, a valid bit, a page number, and a frame number.

    The MMU will request a page fault if no TLB entry contains a valid entry matching the page requested. If two valid TLB entries match, the MMU will behave nondeterministically.

    Part A: What data structures are required to implement clock replacement under this hardware? Give as much detail as possible, given only the above information.

    Part B: Give pseudocode, in terms of the above, for the page fault trap handler. This should use all of the detail about data structures from part A, and it should implement clock replacement.