CSE logo University of Washington Computer Science & Engineering
 CSE 410 Computer Systems - Homework 8 - Spring 2010
  CSE Home   About Us    Search    Contact Info 

Due: Thursday, June 3, at 11 pm.

Some questions mostly about virtual memory and paging, but also a bit about deadlock. Adopted or adapted from exercises in Patterson and Hennessy and in Silberschatz et al.

  1. (Silberschatz 7.10 [8th] / 7.1 [7th]) Consider the traffic deadlock that we looked at in lecture (linked here). (See fig. 7.9 in Silberschatz 7th or 8th ed. for a less messy version that still illustrates the problem.)
    1. Show that the four necessary conditions for deadlock hold in this example.
    2. State a simple rule for avoiding deadlock in this system.

  2. (Silberschatz 7.22 [8th] / 7.14 [7th]) A single-lane bridge connects the two Vermont villages of North Tunbridge and South Tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked if a northbound and a southbound farmer get on the bridge at the same time (Vermont farmers are stubborn and are unable to back up). Using semaphores, design an algorithm that prevents deadlock. You do not be concerned about starvation (the situation in which northbound farmers prevent southbound farmers from using the bridge, or vice versa). Can you come up with a solution that also prevents starvation as well as deadlock?

  3. Consider a virtual memory system with the following properties: What is the total size of the page table for each process on this processor under the following assumptions: single-level page table; the valid, protection, dirty, and use bits take a total of 4 bits; and that all the virtual pages are in use. (Assume that disk addresses of pages on disk are not stored in the page table.

  4. Suppose we have a two-dimensional array A: 
    int A[][] = new int[100][100];
    where A[0][0] is at location 200 in a paged memory system with pages of size 200, and each int occupies one memory location. As is true in Java, the array is stored in row-major order, meaning that the ints in row 0 occupy the first 100 locations assigned to the array, row 1 occupies the next 100 locations, and so forth. A small process that manipulates the array resides in page 0 (locations 0 to 199). Thus every instruction fetch will be from page 0.

    Assume that we run each of the following nested loops on a memory system that has three total page frames. How many page faults are generated by each of the following array-initialization loops, using LRU replacement and assuming that the first page frame contains the process code and the other two are initially empty? 
    1. for (int j = 0; j < 100; j++)
  for (int i = 0; i < 100; i++)
    A[i][j] = 0;

    2. for (int i = 0; i < 100; i++)
  for (int j = 0; j < 100; j++)
    A[i][j] = 0;

  5. Consider a paging system with a single-level page table stored in memory.
    1. If a simple memory reference takes 100 nanoseconds, how long does a paged memory reference take? (Assume that there are no caches involved.)
    2. If we add a TLB (translation lookaside buffer) and 96% of all page table references are found in the TLB, what is the effective memory reference time? (Assume that retrieving a page-table entry from the TLB can be done in zero time if the entry is present.)

  6. Assume that we have a demand-paged memory. Memory access time is 100 nanoseconds. It takes 8 milliseconds to handle a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified and has to be written out to disk. Assume that the page to be replaced is modified 70% of the time. What is the maximum acceptable page-fault rate (fraction of memory references that generate a page fault) for an effective access time of no more than 200 nanoseconds?

  7. Suppose we have a demand-paging system. It seems to be running slowly and when we measure the percentage of time that parts of the system are in use, we get the following numbers: Which, if any, of the following will probably improve CPU utilization? Explain your answer.
    1. Install a faster CPU
    2. Get a larger paging disk
    3. Get a faster paging disk
    4. Increase the number of active processes
    5. Decrease the number of active processes
    6. Install more main memory

Turn-in Instructions: Use the turn-in drop box link on the main course web page to submit a file containing your solutions. You can use any common file format, including plain text, word, or pdf. If you wish, you could also scan in a hand-written solution and submit that, but if you do that, please be sure your handwriting is neat and legible. Please be sure to include your name at the top of your answers.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Hal Perkins]