CSE 120: Homework #4

Winter 2007

Out: 2/15
Due: 2/27

  1. Nachos VM Worksheet

  2. Chapter 8: 8.9, 8.12

    8.9  Consider a paging system with the page table stored in memory.

       a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
       b. If we add TLBs, and 75 percent of all page-table references are found in the TLBs, what is the effective memory reference time? (Assume that finding a page-table entry in the TLBs takes zero time, if the entry is there.)

    8.12  Consider the following segment table:


    What are the physical addresses for the following logical addresses?

        a. 0,430
        b. 1,10
        c. 2,500
        d. 3,400
        e. 4,112

  3. Chapter 9: 9.10

    9.10  Consider a demand-paging system with the following time-measured utilizations:

        CPU utilization: 20%
        Paging disk: 97.7% (demand, not storage)
        Other I/O devices: 5%

    For each of the following, say whether it will (or is likely to) improve CPU utilization. Briefly explain your answers.

       a. Install a faster CPU
       b. Install a bigger paging disk
       c. Increase the degree of multiprogramming
       d. Decrease the degree of multiprogramming
       e. Install more main memory
       f. Install a faster hard disk, or multiple controllers with multiple hard disks
       g. Add prepaging to the page-fetch algorithms
       h. Increase the page size

  4. Consider the following information about a virtual memory system that employs both paging and segmentation. Let |s1|, |s2|, |p| and |w| denote the length, in bits, of each of the four address components. Hence, n = |s1| + |s2| + |p| + |w|.

       a. What is the value of |w|?
       b. What is the maximum number of pages per segment and what is the corresponding value of |p|?
       c. Using the determined values of |w| and |p|, which of the following is choices for |s1| and |s2| is preferable?

      |s1| = |w| and |s2| = n - |p| - |w|
      |s2| = |w| and |s1| = n - |p| - |w|

    Would either choice result in a larger virtual address space? Explain.

  5. If a large number of programs is kept in main memory, then there is almost always another ready program when a page fault occurs. Thus, CPU utilization is kept high. If, however, we allocate a large memory space to each of a few programs, then each program produces a smaller number of page faults. Thus, CPU utilization is kept high. Are these two arguments correct? Which policy, if either, should be preferred? Why?

  6. [Crowley] Suppose we have an average of one page fault every 20,000,000 instructions, a normal instruction takes 2 nanoseconds, and a page fault causes the instruction to take an additional 10 milliseconds. What is the average instruction time, taking page faults into account? Redo the calculation assuming that a normal instruction takes 1 nanosecond instead of 2 nanoseconds.

  7. [Crowley] Suppose we have a computer system with a 44-bit virtual address, page size of 64K, and 4 bytes per page table entry.
    1. How many pages are in the virtual address space?
    2. Suppose we use two-level paging and arrange for all page tables to fit into a single page frame. How will the bits of the address be divided up?
    3. Suppose we have a 4 GB program such that the entire program and all necessary page tables (using two-level pages from above) are in memory. (Note: It will be a lot of memory.) How much memory, in page frames, is used by the program, including its page tables?

  8. [Tanenbaum] If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string 0172327103 if the four frames are initially empty? Now repeat this problem for LRU.

  9. [Java Monitors] As additional practice with monitors, the final problem will be solving one of the midterm synchronization problems using Java monitors.

    A group of students are studying for the CSE 120 midterm. The students can study only while eating pizza. If a student finds that the pizza is gone, the student waits until another pizza arrives. The first student to discover that the group is out of pizza phones Leucadia Pizzeria to order another Meat Combo pizza and then waits for the pizza to arrive. Each pizza has S slices.

    Implement GetSlice and DeliverPizza methods to properly synchronize student threads and the pizza delivery thread using Java monitor mechanisms (Wait and Notify/NotifyAll). Your solution should be in the form of a Java class that compiles and runs. Your solution should avoid deadlock and phone Leucaida (i.e., wake up the delivery thread) exactly once each time a pizza is exhausted. No piece of pizza may be consumed by more than one student.

    Below are five Java files to help you with the implementation. Your job is to implement the guts of the monitor in the fourth file, PizzaMonitor.java. The fifth file, BSem.java, is an example program showing how to use notify and wait.

    1. First, here's the top level program, StudyGroup.java. It's the most complex of the lot. When you run it, you supply as arguments the number of slices per pizza and the list of student names, e.g.:
         java StudyGroup 8 Amako Byun Cheyenne Dmitrii Eija

      When you test your program, try it both with more slices per pizza than students (like above) and more students than slices per pizza.

    2. Next is the life of a studying student, Student.java. Note that this extends Thread. When the "start" method on an object of this class is invoked, the thread starts running by executing the method "run".
    3. And then the pizzeria, Luecadia.java. It is also a thread.
    4. Here's the monitor that you will implement, PizzaMonitor.java. It has two entry methods; one for students and one for pizzerias. Note that this monitor does nothing; you need to add the variables and the code for the two methods. This file is the one that you will modify to solve the problem.
    5. Finally, here is an example program, BSem.java, that shows the use of notify and wait in Java.

marzullo@cs.ucsd.edu, voelker@cs.ucsd.edu