Homework 4 Solutions

22C:116, Fall 2000

Douglas W. Jones

  1. A Problem: Do problem 12 on page 142 of Tannenbaum.
    An address is 32 bits, divided 9 + 11 + X; so X must be 12. Therefore, there are 212 = 4K memory addresses per page (probably bytes), and 220 = 1M pages per address space.

  2. A Problem: Do problem 14 on page 143 of Tannenbaum.
    A 32 bit address is divided a + b + c + d, where d is the offset within a page; there are 2d memory addresses (probably bytes) per page and 2a+b+c pages per address space.

  3. A Problem: Do problem 15 on page 143 of Tannenbaum.
    The expected address translation time is 100ns + k(500ns), where k is the probability of a miss in the translation lookaside buffer, assuming that we only begin the memory cycle if we detect a miss. If our target is an expected tranlation time of 200ns, we simply solve

    200ns = 100ns + k(500ns) --or-- 100ns = k(500ns) --or-- k = 0.2

    So, we need a miss-rate of 1 in 5.

    Note that, for some memory architectures, it may be possible to begin a memory cycle as we begin checking the lookaside buffer. If we get a hit in the lookaside buffer, we abort the memory cycle devoted to address translation. If we get a miss, we allow the memory cycle to run to completion. In this case, k = 0.4, but the hardware is harder to build.

  4. A Problem: Do problem 24 on page 144 of Tannenbaum.
    The program text (code) is 32K, divided into 4K pages, This takes an exact 8 pages, leaving 32K to be shared between data and stack. The data is 16386 bytes (2 bytes more than 4 pages), so it takes 5 pages. The stack is 15870 (514 bytes less than 4 pages), so it takes 4 pages. Therefore, we need 17 pages, but we have only 16. It won't fit.

    If our page size is 0.5K, however, it fits. In that case, we have a total of 128 pages, of which the text takes 64, the data takes 33 and the stack takes 31. Everything fits!

  5. A Problem: Do problem 25 on page 144 of Tannenbaum.
    The program generates 15,000 page faults, and each takes 2001 microsec. 15000x2001us = 30.015 seconds. Doubling the amount of memory halves the number of page faults, so with twice the memory, we will have only 7,500 page faults taking 15.0075 seconds.

    The program takes 60 seconds to run; 15,000 instructions in 30.015 seconds and 29,985,000 instructions in 29.985 seconds. When we halve the page fault rate, we change this to 29,992,500 instructions in 29.9925 seconds plus 7500 instructions in 15.0075 seconds. So, the total time is an even 45 seconds (demonstrating that Tannenbaum cooked his figures to make the answer come out even!)

  6. A Problem: A page fault handler may require disk I/O. Explain the interaction you would expect between the page fault handler and the scheduler when the ready list contains several processes, each with its own virtual address space. This is a two-way question! The page fault handler must initiate scheduling activity and the scheduler must manipulate the address space.
    When a page fault occurs:
    1. The page fault handler will probably request a write to clear out a page frame.
    2. The disk scheduler will include this write in its queue of pending disk requests.
    3. Some other process will run while the disk write is completed. (That other process may cause its own page faults).
    4. When the write is completed, the page fault handler will schedule a read for the page the user requested.
    5. The disk scheduler will include this read in its queue of pending disk requests.
    6. Some other process will run while the disk read is completed. (That other process may cause its own page faults).
    7. When the read is completed, the page fault handler will fix the user's page table and return to the user.