CS550 Operating Systems, Spring 2024 Programming Project 3: Copy on Write to xv6 kernel
CS 550 Operating Systems, Spring 2024 Programming Project 3 (PROJ3)
There are two parts in this project: coding and Q&A. In the first part, you will add the feature of CoW (Copy on Write) to the xv6 OS kernel. In the second part, you will answer the questions about xv6 memory management and your CoW implementation.
1 Baseline source code
You will work on the base code that needs to be cloned/downloaded from your own private GitHub repository. Make sure you read this whole section, as well as the grading guidelines (Section 5), before going to the following link at the end of this section.
• Go to the link at the end of this section to accept the assignment.
• Work on and commit your code to the default branch of your repository. Do not create a new branch. Failure to do so will lead to problems with the grading script and 5 points off of your project grade.
2 xv6 memory management - coding (70 points)
2.1 Copy-on-write (CoW)
As we discussed in class, the fork() syscall creates an exact copy of the parent process. xv6 implements it using the “direct copying” approach, which simply makes a copy of the parent’s memory and other resources. However, as we know, this way is not efficient. In this project, you are going to add to the xv6 OS kernel the CoW functionality which should work exactly as introduced in class.
A user library function named “int enable cow(int enable)” and the corresponding system call should be added to control whether the CoW functionality is enabled (enable cow(1) enables CoW and enable cow(0) disables CoW).
Here are some hints for completing the work:
2.2
•
•
•
In xv6, when a process calls fork() to create a new copy of itself, the kernel creates a new page table for the child process and clones all the pages of the parent by calling copyuvm(). Look at fork() and copyuvm() for more details.
Here one key piece of work is that you will need to implement your own copyuvm() that has the CoW support, along with other changes to enable CoW in xv6.
When either the parent process or the child process tries to write to a read-only page, the CPU will raise a page fault exception. The faulting address can be retrieved from the control register cr2. You can use function rcr2() to get the faulting virtual address.
Function flush tlb all() can be used to flush the TLB. Testing your CoW implementation
The test program source code (cowtest.c) has been given in the base code. The three test cases are explained as follows.
1. The parent process creates one child processes. Before fork(), the parent checks the number of free memory frames1 (short as “NFMF” in the following) (suppose it is v1).
After fork(), the parent just checks NFMF (suppose it is v2).
The child first sleeps for some time (to let the parent finish its job), then checks the NFMF
(suppose it is v3).
After the parent calls wait() for its child process, it checks the NFMF (suppose it is v4).
A correct CoW implementation should have the following:
-
(a) v1 == v4, otherwise memory frames leak happened with your implementation.
-
(b) v2 == v3, and the value of (v1−v2) when with CoW (i.e., your implementation) should
be smaller than that when without CoW (i.e., the base code).
1To check the NFMF, call function get free frame cnt(), which returns the number of free memory frames at the time of calling.
2
-
The parent process creates one child process. Before fork(), the parent checks the NFMF (v1).
After fork(), the parent checks the NFMF (v2), reads a global variable, and checks the NFMF (v3) again.
The child first sleeps for some time (to let the parent finish its job), then checks the NFMF (v4), modifies the global variable, and checks the NFMF (v5) again;
After the parent calls wait() for its child process, it checks the NFMF (v6). A correct CoW implementation should have the following:
(a) v1 == v6, otherwise memory frames leak happened with your implementation. (b) v2==v3==v4,andv4−v5==1.
-
The parent process creates one child processes, and there is a global array A that spans two pages (page size is 4096 byte). Before fork(), the parent checks the NFMF (v1).
After fork(), the parent checks the NFMF (v2), modifies an array element of A that is located on the first page, and checks the NFMF (v3) again;
The child first sleeps for some time (to let parent finish its job), then checks the NFMF (v4), modifies an array element of A that also locates in the first page, and checks the NFMF (v5). Then the child modifies an array element of A that is located on the second page, and checks the NFMF (v6) again;
After the parent calls wait() for its child process, it checks the NFMF (v7). A correct CoW implementation should have the following:
(a) v1 == v7, otherwise memory frames leak happened with your implementation. (b) v2−v3==1,v3==v4==v5,andv5−v6==1.
The following is an sample output of the test program with a correct CoW implementation:
$ cowtest
>>>>>>>>>>>>>>>>> WITHOUT COW <<<<<<<<<<<<<<<<<<<<<<
----- Test case 1 -----
[prnt] v1 = 56730
[prnt] v2 = 56657
[chld] v3 = 56657
[prnt] v4 = 56730
=====> v1 = v4 ? YES
=====> v1 - v2 = 73
----- Test case 2 -----
[prnt] v1 = 56730
[prnt] v2 = 56657
[prnt] read global_var, global_var=0
[prnt] v3 = 56657
[chld] v4 = 56657
[chld] modified global_var, global_var=100
3
[chld] v5 = 56657
[prnt] v6 = 56730
=====> v1 = v6 ? YES
=====> v1 - v2 = 73
=====> v4 - v5 = 0
----- Test case 3 -----
[prnt] v1 = 56730
[prnt] v2 = 56657
[prnt] modified one element in the 1st page, global_array[0]=111
[prnt] v3 = 56657
[chld] v4 = 56657
[chld] modified one element in the 1st page, global_array[0]=222
[chld] v5 = 56657
[chld] modified two elements in the 2nd page, global_array[2047]=333
[chld] v6 = 56657
=====> v5 - v6 = 0
[prnt] v7 = 56730
=====> v1 = v7 ? YES
=====> v1 - v2 = 73
=====> v2 - v3 = 0
>>>>>>>>>>>>>>>>> WITH COW <<<<<<<<<<<<<<<<<<<<<<
----- Test case 1 -----
[prnt] v1 = 56730
[prnt] v2 = 56662
[chld] v3 = 56662
[prnt] v4 = 56730
=====> v1 = v4 ? YES
=====> v1 - v2 = 68
----- Test case 2 -----
[prnt] v1 = 56730
[prnt] v2 = 56662
[prnt] read global_var, global_var=0
[prnt] v3 = 56662
[chld] v4 = 56662
[chld] modified global_var, global_var=100
[chld] v5 = 56661
[prnt] v6 = 56730
=====> v1 = v6 ? YES
=====> v1 - v2 = 68
=====> v4 - v5 = 0
----- Test case 3 -----
[prnt] v1 = 56730
[prnt] v2 = 56662
[prnt] modified one element in the 1st page, global_array[0]=111
[prnt] v3 = 56661
[chld] v4 = 56661
[chld] modified one element in the 1st page, global_array[0]=222
[chld] v5 = 56661
[chld] modified two elements in the 2nd page, global_array[2047]=333
4
[chld] v6 = 56660
=====> v5 - v6 = 1
[prnt] v7 = 56730
=====> v1 = v7 ? YES
=====> v1 - v2 = 68
=====> v2 - v3 = 1
(Continue to next page ...)
5
3 xv6 memory management - Q&A (30 points)
Answer the following questions about system call implementation.
-
Q1: (5 points) What is the page size with xv6? Use xv6’s code to support your answer.
-
Q2: (5 points) Does xv6 use linear paging or multi-level paging? If multi-level paging, how many levels are there? Use xv6’s code to support your answer.
-
Q3: (10 points) The original xv6 use the “direct copying” approach when forking. In other words, the forking needs to copy every page of the parent process for the child process. Show the code that achieves this functionality and explain this code.
-
Q4: (10 points) Explain with code about how your CoW implementation works.
Key in your answers to the above questions with the text editor you prefer, export them in a PDF file named “xv6-mem-mechanisms.pdf”, and submit the file to the assignment link in Brightspace.
(Continue to next page ...)
6
4 Submit your work
Once your code in your GitHub private repository is ready for grading, submit a text file named “DONE” (and the previous “xv6-mem-mechanisms.pdf”) to the assignment link in Brightspace. We will not be able to know your code in your GitHub reposi- tory is ready for grading until we see the “DONE” file in Brightspace. Forgetting to submit the “DONE” file will lead to a late penalty applied, as specified later in the “Grading” section.
Important notes:
-
If you have referred to any form of online materials or resources when completing this project (code and Q&A), please state all the references in this “DONE” file. Failure to do so, once detected, will lead to zero points for the entire project and further penalties depending on the severity of the violation.
-
To encourage (discourage) early (late) starts on this project, the instructor and the TAs will not respond to questions related to the project on the due date.
Suggestion: Test your code thoroughly on a CS machine before submitting. (Continue to next page ...)
7
5 Grading
The following are the general grading guidelines for this and all future projects.
-
(1) The code in your repository will not be graded until a “DONE” file is submitted
to Brightspace.
-
(2) The submission time of the “DONE” file shown on the Brightspace system will be used to determine if your submission is on time or to calculate the number of late days. Late penalty is 10% of the points scored for each of the first two days late, and 20% for each of the days thereafter.
-
(3) If you are to compile and run the xv6 system on the department’s remote cluster, remember to use the baseline xv6 source code provided by our GitHub classroom. Compiling and running xv6 source code downloaded elsewhere can cause 100% CPU utilization on QEMU.
Removing the patch code from the baseline code will also cause the same problem. So make sure you understand the code before deleting them.
If you are reported by the system administrator to be running QEMU with 100% CPU uti- lization on QEMU, 10 points off.
-
(4) If the submitted patch cannot successfully patched to the baseline source code, or the patched code does not compile:
1 2 3 4 5 6 7 8 9
TA will try to fix the problem (for no more than 3 minutes);
if (problem solved)
1%-10% points off (based on how complex the fix is, TA’s discretion);
else
TA may contact the student by email or schedule a demo to fix the problem;
if (problem solved)
11%-20% points off (based on how complex the fix is, TA’s discretion);
else
All points off;
So in the case that TA contacts you to fix a problem, please respond to TA’s email promptly or show up at the demo appointment on time; otherwise the line 9 above will be effective.
-
(5) If the code is not working as required in the project spec, the TA should take points based on the assigned full points of the task and the actual problem.
-
(6) Lastly but not the least, stick to the collaboration policy stated in the syllabus: you may discuss with you fellow students, but code should absolutely be kept private. Any kind of cheating will result in zero point on the project, and further reporting.
8
