Spring 2012 -- Junfeng Yang

Homework 5 is due 04/11 at 12:01am EDT

The written problems are to be done individually. The programming problems are also to be done individually. All homework submissions and discussions are to be made via Courseworks.

Individual Written Problems (40 pts)

Exercise numbers refer to the course textbook, Modern Operating Systems. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.

  1. MOS 5.24

    Disk requests come in to the disk driver for cylinders 10, 22, 20, 2, 40, 6, and 38, in that order. A seek takes 6 mes per cylinder moved. How much seek time is needed for

    (a) First-come, first served.
    (b) Closest cylinder next.
    (c) Elevator algorithm (initially moving upward).

    In all cases, the arm is initially at cylinder 20.

  2. MOS 5.25

    A slight modification of the elevator algorithm for scheduling disk requests is to always scan in the same direction, In what respect is this modified algorithm better than the elevator algorithm?

  3. MOS 5.15

    A RAID can fail if two or more of its drives crash within a short time interval. Suppose that the probability of one drive crashing in a given hour is p. What is the probability of a k-drive RAID failing in a given hour?

  4. MOS 5.21

    Consider a magnetic disk consisting of 16 heads and 400 cylinders. This disk is divided into four 100-cylinder zones with the cylinders in different zones containing 160, 200, 240, and 280 sectors, respectively. Assume that each sector contains 512 bytes, average seek time between adjacent cylinders is 1 msec, and the disk rotates at 7200 RPM. Calculate the (a) disk capacity, (b) optimal track skew, and (c) maximum data transfer rate.

  5. MOS 4.5

    Some operating systems provide a system call rename to give a file a new name. Is there any difference at all between using this call to rename a file and just copying the file to a new file with the new name, followed by deleting the old one?

  6. MOS 4.11 & 4.12

    One way to use contiguous allocation of the disk and not suffer from holes is to compact the disk every time a file is removed. Since all files are contiguous, copying a file requires a seek and rotational delay to read the file, followed by the transfer at full speed. Writing the file back requires the same work. Assuming a seek time of 5 msec, a rotational delay of 4 msec, a transfer rate of 8 MB/sec, and an average file size of 8 KB, (a) how long does it take to read a file into main memory then write it back to the disk at new location? (b) Using these numbers, how long would it take to compact half of a 16-GB disk? (c) Dose compacting the disk ever make any sense?

  7. MOS 4.19

    Free disk space can be kept track of using a free list or a bit map. Disk addresses require D bits. For a disk with B blocks, F of which are free, state the condition under which the free list uses less space than the bitmap. For D having the value 16 bits, express your answer as a percentage of the disk space that must be free.

  8. MOS 4.21

    What would happen if the bitmap or free list containing information about free disk blocks was completely lost due to a crash? Is there any way to recover from this disaster, or is it bye-bye disk? Discuss your answers for a UNIX and the FAT-16 file system separately.

Programming Assignment: Copy-on-Write Fork (60 pts)

In this programming assignment, you'll implement the copy-on-write fork in xv6.

The files needed for this assignment are distributed using the Git distributed version control software. To learn about Git, take a look at the Git user's manual, or, if you are already familiar with other version control systems, you may find this Git overview useful.

To get started, run the following commands

$ git clone http://debug.cs.columbia.edu/xv6.git xv6 -b hw5

Submission instructions

When you are ready to hand in your solution, put your UNI in conf.mk, commit all your changes, and run make handin in the xv6 directory. This will generate hw5-programming-<your uni>.tar.gz for you, which you can then upload via courseworks. This tar ball includes a snapshot of all xv6 source code and a patch generated using git diff origin/hw5 hw5. Thus, be sure you commit all your changes (including the new files you add) before running make handin. Double-check the patch in the generated tar ball. It should contain all your changes in the source code.

We will be grading your solutions with a grading program. You can run make grade to test your solutions with the grading program. Note that it takes a while to run the test programs, so please be patient.


xv6 doesn't do copy-on-write when forking processes. Instead, it copies all pages of the parent process when creating a child process. This approach creates three problems. First, copying an entire address space can take a long time. Second, it wastes memory because the parent and the child processes share a large portion of their address spaces. For instance, they share all code pages. Third, the copying is useless when a forked child immediately calls exec() to run a program, which comes up frequently for shell programs.

In this assignment, you'll implement a copy-on-write fork() for xv6. When a process calls fork(), instead of duplicating the entire address space, your fork() should share the pages between the parent and the child processes. When either process writes to a shared page, your implementation should detect this write, and give this process a private copy of the page when necessary.

To detect when a write to a shared page occurs, you should use page protection. Specifically, you should set up the page tables for the parent and the child appropriately so that a write to a shared page causes a page fault. Then, you should modify the xv6 page fault handler so that you can distinguish copy-on-write page faults from other page faults.

To simplify the assignment, assume all processes are single-threaded.

You don't need to implement any new system calls for this assignment. Instead, modify the existing fork() implementation in xv6.

You'll need to get the faulting address in the page fault handler. This address is stored in the cr2 register.

You may want to use reference counting to keep track of whether a page is shared. Make sure you correctly synchronize the accesses to the reference counters to avoid race conditions.

Hint: What do you have to do after you modify a page table entry? Recall that the TLB may have a cached copy of the entry you just modified, and you have to make these two copies consistent. You can do so by flushing the TLB or just the entries that become inconsistent.