Homework 4

Due Date: June 8, 1999
Points: 100

Short-Answer Questions

These can be answered in a sentence or two, and are intended to reinforce important points.

  1. (4 points) What is the difference between segmentation and paging?

  2. (4 points) Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames. How many bits are there in the logical address? In the physical address?

Long-Answer Questions

These questions require some thought and longer answers than the short-answer questions. They are intended to have you use the concepts discussed in class, to be sure you understand them and can work with them

  1. (12 points) A virtual memory has a page size of 1024 words, eight virtual pages, and four physical page frames. The page table is as follows:
    virtual pagepage frame
    03
    11
    2not in main memory
    3not in main memory
    42
    5not in main memory
    60
    7not in main memory


    1. Make a list of all virtual addresses that will cause page faults.
    2. What are the physical addresses for 0, 3728, 1023, 1024, 1025, 4096, and 7800?

  2. (25 points) Consider the following page reference string:
    1 2 3 4 1 5 6 2 1

    How many page faults would occur for the following replacement algorithms, assuming first 4, and then 7 frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.
    1. First In First Out (FIFO)
    2. Optimal (OPT, MIN)
    3. Least Recently Used (LRU)
    4. Not Recently Used, Not Used Recently (NRU, NUR); assume all references to pages 2, 4, and 6 are writes.
    5. Clock

  3. (20 points) Consider a demand paged system with the following time-measured utilizations:
    CPU utilization20%
    Paging disk97.7%
    Other I/O devices5%
    Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.
    1. Install a faster CPU.
    2. Install a bigger paging disk.
    3. Increase the degree of multiprogramming.
    4. Decrease the degree of multiprogramming.
    5. Install faster, other I/O devices.

  4. (20 points) Consider the reference string
    w = 1234523432442444
    Assuming the working set replacement strategy, determine the minimum window size such that the string generates at most five page faults. Show which pages are in memory at each reference, as well as which pages are being brought into, and removed from, memory.

  5. (15 points) You are the president of Cheapo Computronics, Inc., and your star hardware designer has suggested a brilliant idea: Implement segmentation, but let the least significant m bits of a virtual adress be used to select the segment, and let the other bits determine the offset. Should the designer retire or get a raise? Why?

Extra Credit

  1. (10 points) Prove that Belady's anomaly cannot occur in a stack algorithm.

  2. (15 points) A particular database program repeatedly scans an array of 1,000 pages. Each scan starts with page 0 and continues to page 999. There is only enough main store to hold 100 pages. None of the page replacement policies we discussed does very well. Suggest a different policy that will do as well as the optimal page replacement policy OPT for this program.

Send email to cs150@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562


Page last modified on 5/27/99