Homework #3

CMPS 111, Spring 2008

Assigned: May 22
Due: Wednesday, May 28th at 11:59 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 3.20 from the text (page 251).
  5. Problem 3.34 from the text (page 252).
  6. On the Mac and Windows, double-clicking a file automatically launches the program that knows how to deal with the file, and hands the file as a parameter to the program. List two different ways the operating system could know which file to run. Which approach do you believe is better? How could you change the mapping? For example, suppose you wanted to open text files with emacs rather than Microsoft Word.
  7. Defragmentation is the process of reorganizing the data on a disk to improve performance.
    1. Clearly, defragmentation is necessary for contiguous allocation. How can it improve performance for file systems that use indexed allocation?
    2. Describe (in high-level outline form) how you might defragment an ext2 / ext3 file system. How could you make sure the file system remains consistent throughout the whole process? In other words, how could you prevent a crash during defragmentation from corrupting the file system and losing data? HINT: think about the order in which you might want to do disk operations to move a file to a new location on the disk.
  8. Consider a Unix (FFS / ext2 / ext3) file system with 12 direct pointers in each inode and 4 KB file blocks, and a maximum file system size of 2 terabytes (2000 GB).
    1. How much overhead would be needed to store index blocks for a 100 MB file, not including the inode itself? What percentage of total file size would the overhead be? Remember that blocks must be allocated in their entirety if any part of the block is needed.
    2. On average, how many 4 KB blocks would have to be read to get a random block from the (100 MB) file? Again, assume the inode is already in memory and doesn't need to be read from disk. HINT: figure out how many blocks can be read for each of direct, single, double, triple indirect and compute the average from this information.
Last updated 21 May 2008 by Darrell Long or perhaps by Stephanie Jones