Homework 5 is due 04/13 at 12:01am EDT
Individual written problems are to be done individually. Group
programming problems are to be done in your assigned programming
groups. 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.
- MOS 5.24
- MOS 5.25
- MOS 5.15
- MOS 5.21
- MOS 4.5
- MOS 4.11 & 4.12
- MOS 4.19
- MOS 4.21
Please complete and submit a private group programming assignment evaluation. The evaluation should be in a separate file called evaluation.txt that is submitted with your individual written assignment submission.
Programming Assignment: Copy-on-Write Fork (60 pts)
Programming assignments are to be done in your assigned groups in xv6. For the programming problems, you are required to write README documenting your files and codes. 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://repair.cs.columbia.edu/git/xv6 xv6
$ cd xv6
$ git checkout -b hw5 origin/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-<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.
Description
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 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?