Homework #3

CMPS 111, Fall 2007

Assigned: Nov. 1
Due: Wednesday, Nov. 7th at 10:00 PM

Please read the general homework page for guidelines and submission information. Homework must be submitted online.

All work on this homework must be your own. Please read (and follow!) the academic honesty policy for this class.

  1. You are given a virtual memory system where the hardware doesn't support the setting of referenced or dirty bits. How could you simulate them in a paging system? Assume that you have the usual page protection bits (read, write execute), but that hardware doesn't modify PTEs on each access. What is the tradeoff (speed, accuracy, etc.) of your system with respect to the standard system with referenced and dirty bits?
  2. [Modified from problem 4.5 in the text] Consider a swapping system in which memory consists of the following hole sizes in memory order (all sizes in KB): 10, 4, 18, 20, 7, 12, 17. Which hole is taken for each of these requests, assuming the requests are made in this order? Are there any requests that cannot be satisfied?
    1. 15 KB
    2. 19 KB
    3. 10 KB
    4. 5 KB
    You should do this allocation for each of first fit, best fit, next fit, and worst fit.
  3. A computer has a 40-bit virtual address, with the address split into a 16-bit top-level page table field and an 11-bit second-level page table field, with the remainder of the address being used as an offset into the page. Assume that physical addresses are still 32 bits long.
    1. How large are the pages?
    2. How big (in bytes) is the top-level page table?
    3. How much memory is required for the page tables for a (UNIX) process using 1400KB of code, 1600KB of data (heap), and 100KB of stack?
  4. Problem 4.22 from the text (page 265).
  5. Problem 4.33 from the text (page 266).
  6. Problem 4.35 from the text (page 267).
Last updated 1 Nov 2007 by Ethan L. Miller