代做CS 550、代写c++，Java编程语言
- 首页 >> C/C++编程 CS 550 Operating Systems, Spring 2024
Programming Project 2 (PROJ2)
Out: 2/25/2024, SUN
Due date: 3/23/2024, SAT 23:59:59
There are two parts in this project: coding and Q&A. In the coding part, you will implement a
functionality that changes the outcomes of race conditions after forking in xv6, and implement an
MLFQ-like scheduler for xv6. In the Q&A part, you will need to answer the questions about xv6
process scheduling.
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.
Assignment link: https://classroom.github.com/a/2n4W593t
(Continue to the next page.)
1
2 Process scheduling in xv6 - coding (70 points)
2.1 Race condition after fork() (20 points)
As we discussed in class, after a fork(), either the parent process or the child process can be
scheduled to run first. Some OSes schedule the parent to run first most often, while others allow
the child to run first mostly. As you will see, the xv6 OS schedules the parents to run first after
fork()s mostly. In this part, you will change this race condition to allow user programs to specify
which process should run first (i.e., be the winner) after fork() returns.
2.1.1 The test driver program and the expected outputs
The baseline code has included a test driver program fork rc test that allows you to check
the race condition after a fork(). The program is implemented in fork rc test.c. In the
program, the parent process repeatedly calls fork(). After fork(), the parent process prints
string a “parent” when it runs, and the child process prints a string “child” and exits.
The program takes one argument to specify which process should be the “winner” process after
fork() returns. Here is the usage of the program:
$ fork_rc_test
Usage: fork_rc_test 0|1
0: Parent is scheduled to run most often
1: Child is scheduled to run most often
When calling the program using ”fork rc test 0”, the parent process is the fork winner and is
scheduled to run first after fork() most often, which is the default behavior with xv6. You will
see output like the following:
$ fork_rc_test 0
Setting parent as the fork winner ...
Trial 0: parent! child!
Trial 1: parent! child!
Trial 2: parent! child!
Trial 3: pare child! nt!
Trial 4: parent! child!
Trial 5: parent! child!
...
Trial 45: child! parent!
Trial 46: parent! child!
Trial 47: parent! child!
Trial 48: parent child! !
Trial 49: pare child! nt!
Note that in the above output, the parent did not always run first. But it was so for most trials.
What determines which process runs first after the fork? Think about the reason. You will answer
a related question later in the Q&A part (Section 3).
When calling the program using ”fork rc test 1”, the child process is the fork winner and is
scheduled to run first after fork() most often. With a correct implementation, the expected
output of the test driver program looks like:
2
$ fork_rc_test 1
Setting child as the fork winner ...
Trial 0: child! parent!
Trial 1: child! parent!
Trial 2: child! parent!
Trial 3: c parent! hild!
Trial 4: child! parent!
Trial 5: child! parent!
...
Trial 45: child! parent!
Trial 46: child! parent!
Trial 47: child! parent!
Trial 48: child! parent!
Trial 49: child! parent!
2.1.2 What to do
(1) Figure out what to do to change the race condition to enable the feature of changing fork
winner.
(2) Implement a system call that sets the fork winner.
(3) Implement a user space wrapper function for the above system call, and declare it in “user.h”.
This wrapper function’s prototype should be
int fork_winner(int winner);
This function takes one argument:
• If the argument is 0 (i.e., fork winner(0)), the parent process is the winner and
should be scheduled first after fork() most often (this is the default behavior);
• If the argument is 1 (i.e., fork winner(1)), the child process is the winner and should
be scheduled first after fork() most often.
Note: for the proper compilation of the base code, the fork rc test program has a stub
implementation for the wrapper function above. Remember to comment it out after developing
your own solution.
Tips: understanding the code for fork and CPU scheduling is key. The actual code that changes
the race condition (excluding the system-call-related code) can be less than 2 LOC.
(Continue to next page.)
3
2.2 MLFQ scheduling (50 points)
The default scheduler of xv6 adopts a round-robin (RR) policy. In this part, you are going to
implement a scheduler that adopts a scheduling algorithm similar to the MLFQ scheduling policy
we discussed in class.
Specifically, the MLFQ-like process scheduler should work following the rules below:
• Rule 1: There are three different scheduling priorities: 3, 2, and 1, with 3 being the highest
and 1 being the lowest.
• Rule 2: At any given time, the scheduling priority of a process is set to one of the three
values above.
• Rule 3: Runnable processes are scheduled based on their scheduling priorities: processes
with higher priorities will be scheduled before those with lower priorities. RR is used for
scheduling processes that have the same priority.
• Rule 4: When a process is forked, its scheduling priority is set to 3, and its priority is
changed using the following rule.
• Rule 5: Except for the lowest priority (i.e., priority 1), each priority is associated with a
scheduling allotment, which is the number of times that a process with this priority can be
scheduled before the process is demoted to the next lower priority. For example,
– When a process is created, its scheduling priority is set to 3. When this process has
been scheduled x times since its scheduling priority was set to 3, its scheduling priority
is demoted to 2. Therefore, the scheduling allotment for priority 3 is x. The default
value of x is 2.
– When a process with scheduling priority 2 has been scheduled y times since its scheduling priority was set to 2, its scheduling priority is demoted to 1. Therefore, the scheduling allotment for priority 2 is y. The default value of y is 4.
• Rule 6: After a process’s scheduling priority is demoted to 1, it stays with that priority
until it completes.
• Rule 7: When user code uses the set sched() interface to set the scheduling policy to
MLFQ, the scheduler should be reset as if it is a fresh start. This means that the scheduling
priority of the existing processes should be reset back to 3.
2.2.1 The test program, test cases and their expected output
(1) To help you implement and debug, a scheduling tracing functionality has been added to the
base code. When this tracing functionality is enabled, the kernel prints a string like the
following every time before a process is scheduled.
[MLFQ] PID:7|PRT:3
The above string means the MLFQ scheduler is going to schedule the process with PID 7, and
the process’s scheduling priority is 3. With this scheduling tracing functionality, you can see
the sequence of processes that the scheduler schedules.
4
(2) The code (schdtest.c) for test program that will be used for grading (schdtest) has been
provided. This code is not supposed to be changed except for commenting out or removing
the stub functions at the top. Reading and understanding this test program and each of the
test cases will be helpful.
(3) Five test cases are used in the test program. Each of this test cases and their expected output
are described as follows.
• Test case 1: In this test case, the parent process enables the scheduling tracing functionality, sets the scheduler type to the default one (i.e., RR), creates 3 child processes,
each of which performs some long computation, and waits for their completion. When
all three child process complete, the parent process disables the scheduling tracing. The
expected scheduling tracing output is as follows:
>>>>> Test case 1: testing default scheduler (RR) ...
Parent: child (pid=4) created!
Parent: child (pid=5) created!
Parent: child (pid=6) created!
[RR] PID:4|PRT:0 -> [RR] PID:5|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:4|PRT:0 -> [RR] PID:5|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:4|PRT:0 -> [RR] PID:5|PRT:0 -> [RR] PID:6|PRT:0 ->
...
[RR] PID:3|PRT:0 -> [RR] PID:6|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:6|PRT:0 -> [RR] PID:6|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:3|PRT:0 ->
Since the RR scheduler does not use scheduling priority, the scheduling priority of individual processes should be set to 0 when RR is in effect. From the output we can see
that the RR was indeed the scheduling policy.
• Test case 2: In this test case, the parent process enables the scheduling tracing functionality, sets the scheduler type to MLFQ, creates 3 child processes, each of which performs
some long computation, and waits for their completion. When all three child process
complete, the parent process disables the scheduling tracing. The expected scheduling
tracing output is as follows:
>>>>> Test case 2: testing MLFQ scheduler with default allotment ...
Parent: child (pid=7) created!
Parent: child (pid=8) created!
Parent: child (pid=9) created!
[MLFQ] PID:7|PRT:3 -> [MLFQ] PID:8|PRT:3 -> [MLFQ] PID:9|PRT:3 ->
[MLFQ] PID:7|PRT:3 -> [MLFQ] PID:8|PRT:3 -> [MLFQ] PID:9|PRT:3 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:8|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:8|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
...
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:8|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:3|PRT:3 -> [MLFQ] PID:8|PRT:1 ->
[MLFQ] PID:3|PRT:3 -> [MLFQ] PID:9|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
5
[MLFQ] PID:9|PRT:1 -> [MLFQ] PID:9|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
[MLFQ] PID:9|PRT:1 -> [MLFQ] PID:3|PRT:2 ->
The default allotments are used in this test case. Therefore, as shown in the scheduling
tracing output, the three child processes started with priority 3 at the beginning. They
were scheduled in an RR manner 2 times and were demoted to priority 2 (because the
default allotment for priority 3 is 2). While their scheduling priority was 2, they were
scheduled in an RR manner 4 times and then were demoted to priority 1 (because the
default allotment for priority 2 is 4).
Note that the PID of the parent process is 3 in this example. The parent process was
not scheduled until the end of the trace because it was waiting for the child processes’
completion. It was scheduled three times at the end (see the last three lines in the output),
each of which was returning from wait() when one of the child processes exited.
• Test case 3: This is a repeat of test case 1.
• Test case 4: In this test case, the parent process enables the scheduling tracing functionality, sets the scheduler type to MLFQ, creates 3 child processes, each of which performs
some long computation, and waits for their completion. In the middle of the long computation, one of the three child process (whose PID is multiples of 3) forks a grand-child
process which is termed as “runtime generated process” in the test code, and waits for
its completion. When all three child process complete, the parent process disables the
scheduling tracing. The expected scheduling tracing output is as follows:
>>>>> Test case 4: testing MLFQ scheduler with runtime generated process ...
Parent: child (pid=13) created!
Parent: child (pid=14) created!
Parent: child (pid=15) created!
[MLFQ] PID:13|PRT:3 -> [MLFQ] PID:14|PRT:3 -> [MLFQ] PID:15|PRT:3 ->
[MLFQ] PID:13|PRT:3 -> [MLFQ] PID:14|PRT:3 -> [MLFQ] PID:15|PRT:3 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
...
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:16|PRT:3 -> [MLFQ] PID:16|PRT:3 -> [MLFQ] PID:16|PRT:2 ->
[MLFQ] PID:16|PRT:2 -> [MLFQ] PID:16|PRT:2 -> [MLFQ] PID:16|PRT:2 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
...
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:3|PRT:3 -> [MLFQ] PID:14|PRT:1 ->
[MLFQ] PID:16|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:3|PRT:3 ->
[MLFQ] PID:16|PRT:1 -> [MLFQ] PID:16|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
...
[MLFQ] PID:16|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
...
[MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:3|PRT:2 ->
6
This test case is similar to test case 2 but with a new process generated during runtime.
In the above output, the PID of the runtime-generated process is 16, and the PID of the
runtime-generated process’s parent is 15. If one understands the expected output of test
case 2, the above output for this test case should be easily understandable.
• Test case 5: This test case is similar to test case 2 but with different allotments than
the default one. The allotments of priority 3 and 2 are set to 4 and 8 before the test, and
they are set back to the default values after the test. The expected scheduling tracing
output is as follows:
>>>>> Test case 5: testing MLFQ scheduler with new allotments ...
Parent: child (pid=17) created!
Parent: child (pid=18) created!
Parent: child (pid=19) created!
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:1 -> [MLFQ] PID:18|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
[MLFQ] PID:17|PRT:1 -> [MLFQ] PID:18|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
...
[MLFQ] PID:17|PRT:1 -> [MLFQ] PID:18|PRT:1 -> [MLFQ] PID:3|PRT:3 ->
[MLFQ] PID:3|PRT:3 -> [MLFQ] PID:17|PRT:1 -> [MLFQ] PID:3|PRT:3 ->
[MLFQ] PID:3|PRT:3 -> [MLFQ] PID:19|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
[MLFQ] PID:19|PRT:1 -> [MLFQ] PID:19|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
[MLFQ] PID:19|PRT:1 -> [MLFQ] PID:3|PRT:2 -> [MLFQ] PID:3|PRT:2 ->
Again, the above output should be easily understandable if one understands that of test
case 2.
2.2.2 What to do
(1) If you run the test program included in the base code, you’ll notice that the output of the OS
kernel scheduling tracing messages is mixed with the messages printed by the parent process.
This is because scheduling context switches happen as the parent process is forking child
processes. To ensure that the test program can generate a nicely formatted output as shown
above, your job is to implement a functionality that allows user programs to pause scheduling
different processes.
• Write a system call that pauses process scheduling. When process scheduling is paused,
the OS will keep running the current process until process scheduling is enabled again.
• Write the corresponding system call user space wrapper function, and declare it in
“user.h”. The wrapper function’s prototype should be:
7
void pause_scheduling(int pause);
– Description: This function pauses process scheduling.
– Arguments: This function takes one arguments.
– pause: To pause process scheduling, set this argument to 1. To enable process
scheduling, set this argument to 0.
– Return value: This function has no return value.
(2) Implement the functionality that allows user programs to set the allotments of different
scheduling priorities.
• Write a system call that sets the allotments of a scheduling priority.
• Write the corresponding system call user space wrapper function, and declare it in
“user.h”. The wrapper function’s prototype should be:
int mlfq_set_allotment(int priority, int allotment);
– Description: This function sets allotment of the “priority” (first arg) to “allotment”
(second arg).
– Arguments: This function takes two arguments.
– priority: the scheduling priority of which the allotment is to set.
– allotment: the new allotment value.
– Return value: On successfully setting the allotment for the priority, this function
returns 0. The function returns -1 on failures.
.
(3) Implement the MLFQ scheduling policy, remove the stub functions defined at the beginning
of schdtest.c (by simply removing the “STUB FUNCS” macro definition), and test your
implementation.
Note: Your implementation should keep the patch that fixes the always-100% CPU utilization
problem. If your code causes the problem to re-occur, 10 points off (see the 4th point in the
“Grading” section for details).
2.2.3 Tips
You may have noticed that the MLFQ scheduling policy you are going to implement is referred
to as MLFQ-like scheduling policy in the above description. The difference between the MLFQ
policy you will be implementing in this project and the MLFQ policy you learned in class is that
the MLFQ policy in this project does not mandate using different queues for different scheduling
priorities. Therefore, you are allowed to keep the current single-queue design intact in xv6 and
implement the required MLFQ logic. In other words, here the ”Q” is not necessarily physical
queues that are backed by queue data structures. It can be logical queues as well.
Learning in xv6 code how process scheduling context switches happen will be helpful for implementing the functionality of pausing process scheduling.
(Continue to next page.)
8
3 Process scheduling in xv6 - Q&A (30 points)
Answer the following questions about process scheduling implementation.
Q1: (10 points) Does xv6 kernel use cooperative approach or non-cooperative approach to gain
control while a user process is running? Explain how xv6’s approach works using xv6’s code.
Q2: (10 points) After fork() is called, why does the parent process run before the child process
in most of the cases? But in some cases, the child does run first. In what scenario will the
child process run before the parent process after fork()?
Q3: (10 points) When the scheduler de-schedules an old process and schedules a new process, it
saves the context (i.e., the CPU registers) of the old process and load the context of the new
process. Show the code which performs these context saving/loading operations. Show how
this piece of code is reached when saving the old process’s and loading the new process’s
context.
Key in your answers to the above questions with any the editor you prefer, export them in a PDF
file named “xv6-sched-mechanisms.pdf”, and submit the file to the assignment link in Brightspace.
9
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-sched-mechanisms.pdf”) to the assignment
link in Brightspace. We will not be able to know your code in your GitHub repository 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.
10
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 utilization 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 TA will try to fix the problem (for no more than 3 minutes);
2 if (problem solved)
3 1%-10% points off (based on how complex the fix is, TA’s discretion);
4 else
5 TA may contact the student by email or schedule a demo to fix the problem;
6 if (problem solved)
7 11%-20% points off (based on how complex the fix is, TA’s discretion);
8 else
9 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.
11
Programming Project 2 (PROJ2)
Out: 2/25/2024, SUN
Due date: 3/23/2024, SAT 23:59:59
There are two parts in this project: coding and Q&A. In the coding part, you will implement a
functionality that changes the outcomes of race conditions after forking in xv6, and implement an
MLFQ-like scheduler for xv6. In the Q&A part, you will need to answer the questions about xv6
process scheduling.
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.
Assignment link: https://classroom.github.com/a/2n4W593t
(Continue to the next page.)
1
2 Process scheduling in xv6 - coding (70 points)
2.1 Race condition after fork() (20 points)
As we discussed in class, after a fork(), either the parent process or the child process can be
scheduled to run first. Some OSes schedule the parent to run first most often, while others allow
the child to run first mostly. As you will see, the xv6 OS schedules the parents to run first after
fork()s mostly. In this part, you will change this race condition to allow user programs to specify
which process should run first (i.e., be the winner) after fork() returns.
2.1.1 The test driver program and the expected outputs
The baseline code has included a test driver program fork rc test that allows you to check
the race condition after a fork(). The program is implemented in fork rc test.c. In the
program, the parent process repeatedly calls fork(). After fork(), the parent process prints
string a “parent” when it runs, and the child process prints a string “child” and exits.
The program takes one argument to specify which process should be the “winner” process after
fork() returns. Here is the usage of the program:
$ fork_rc_test
Usage: fork_rc_test 0|1
0: Parent is scheduled to run most often
1: Child is scheduled to run most often
When calling the program using ”fork rc test 0”, the parent process is the fork winner and is
scheduled to run first after fork() most often, which is the default behavior with xv6. You will
see output like the following:
$ fork_rc_test 0
Setting parent as the fork winner ...
Trial 0: parent! child!
Trial 1: parent! child!
Trial 2: parent! child!
Trial 3: pare child! nt!
Trial 4: parent! child!
Trial 5: parent! child!
...
Trial 45: child! parent!
Trial 46: parent! child!
Trial 47: parent! child!
Trial 48: parent child! !
Trial 49: pare child! nt!
Note that in the above output, the parent did not always run first. But it was so for most trials.
What determines which process runs first after the fork? Think about the reason. You will answer
a related question later in the Q&A part (Section 3).
When calling the program using ”fork rc test 1”, the child process is the fork winner and is
scheduled to run first after fork() most often. With a correct implementation, the expected
output of the test driver program looks like:
2
$ fork_rc_test 1
Setting child as the fork winner ...
Trial 0: child! parent!
Trial 1: child! parent!
Trial 2: child! parent!
Trial 3: c parent! hild!
Trial 4: child! parent!
Trial 5: child! parent!
...
Trial 45: child! parent!
Trial 46: child! parent!
Trial 47: child! parent!
Trial 48: child! parent!
Trial 49: child! parent!
2.1.2 What to do
(1) Figure out what to do to change the race condition to enable the feature of changing fork
winner.
(2) Implement a system call that sets the fork winner.
(3) Implement a user space wrapper function for the above system call, and declare it in “user.h”.
This wrapper function’s prototype should be
int fork_winner(int winner);
This function takes one argument:
• If the argument is 0 (i.e., fork winner(0)), the parent process is the winner and
should be scheduled first after fork() most often (this is the default behavior);
• If the argument is 1 (i.e., fork winner(1)), the child process is the winner and should
be scheduled first after fork() most often.
Note: for the proper compilation of the base code, the fork rc test program has a stub
implementation for the wrapper function above. Remember to comment it out after developing
your own solution.
Tips: understanding the code for fork and CPU scheduling is key. The actual code that changes
the race condition (excluding the system-call-related code) can be less than 2 LOC.
(Continue to next page.)
3
2.2 MLFQ scheduling (50 points)
The default scheduler of xv6 adopts a round-robin (RR) policy. In this part, you are going to
implement a scheduler that adopts a scheduling algorithm similar to the MLFQ scheduling policy
we discussed in class.
Specifically, the MLFQ-like process scheduler should work following the rules below:
• Rule 1: There are three different scheduling priorities: 3, 2, and 1, with 3 being the highest
and 1 being the lowest.
• Rule 2: At any given time, the scheduling priority of a process is set to one of the three
values above.
• Rule 3: Runnable processes are scheduled based on their scheduling priorities: processes
with higher priorities will be scheduled before those with lower priorities. RR is used for
scheduling processes that have the same priority.
• Rule 4: When a process is forked, its scheduling priority is set to 3, and its priority is
changed using the following rule.
• Rule 5: Except for the lowest priority (i.e., priority 1), each priority is associated with a
scheduling allotment, which is the number of times that a process with this priority can be
scheduled before the process is demoted to the next lower priority. For example,
– When a process is created, its scheduling priority is set to 3. When this process has
been scheduled x times since its scheduling priority was set to 3, its scheduling priority
is demoted to 2. Therefore, the scheduling allotment for priority 3 is x. The default
value of x is 2.
– When a process with scheduling priority 2 has been scheduled y times since its scheduling priority was set to 2, its scheduling priority is demoted to 1. Therefore, the scheduling allotment for priority 2 is y. The default value of y is 4.
• Rule 6: After a process’s scheduling priority is demoted to 1, it stays with that priority
until it completes.
• Rule 7: When user code uses the set sched() interface to set the scheduling policy to
MLFQ, the scheduler should be reset as if it is a fresh start. This means that the scheduling
priority of the existing processes should be reset back to 3.
2.2.1 The test program, test cases and their expected output
(1) To help you implement and debug, a scheduling tracing functionality has been added to the
base code. When this tracing functionality is enabled, the kernel prints a string like the
following every time before a process is scheduled.
[MLFQ] PID:7|PRT:3
The above string means the MLFQ scheduler is going to schedule the process with PID 7, and
the process’s scheduling priority is 3. With this scheduling tracing functionality, you can see
the sequence of processes that the scheduler schedules.
4
(2) The code (schdtest.c) for test program that will be used for grading (schdtest) has been
provided. This code is not supposed to be changed except for commenting out or removing
the stub functions at the top. Reading and understanding this test program and each of the
test cases will be helpful.
(3) Five test cases are used in the test program. Each of this test cases and their expected output
are described as follows.
• Test case 1: In this test case, the parent process enables the scheduling tracing functionality, sets the scheduler type to the default one (i.e., RR), creates 3 child processes,
each of which performs some long computation, and waits for their completion. When
all three child process complete, the parent process disables the scheduling tracing. The
expected scheduling tracing output is as follows:
>>>>> Test case 1: testing default scheduler (RR) ...
Parent: child (pid=4) created!
Parent: child (pid=5) created!
Parent: child (pid=6) created!
[RR] PID:4|PRT:0 -> [RR] PID:5|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:4|PRT:0 -> [RR] PID:5|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:4|PRT:0 -> [RR] PID:5|PRT:0 -> [RR] PID:6|PRT:0 ->
...
[RR] PID:3|PRT:0 -> [RR] PID:6|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:6|PRT:0 -> [RR] PID:6|PRT:0 -> [RR] PID:6|PRT:0 ->
[RR] PID:3|PRT:0 ->
Since the RR scheduler does not use scheduling priority, the scheduling priority of individual processes should be set to 0 when RR is in effect. From the output we can see
that the RR was indeed the scheduling policy.
• Test case 2: In this test case, the parent process enables the scheduling tracing functionality, sets the scheduler type to MLFQ, creates 3 child processes, each of which performs
some long computation, and waits for their completion. When all three child process
complete, the parent process disables the scheduling tracing. The expected scheduling
tracing output is as follows:
>>>>> Test case 2: testing MLFQ scheduler with default allotment ...
Parent: child (pid=7) created!
Parent: child (pid=8) created!
Parent: child (pid=9) created!
[MLFQ] PID:7|PRT:3 -> [MLFQ] PID:8|PRT:3 -> [MLFQ] PID:9|PRT:3 ->
[MLFQ] PID:7|PRT:3 -> [MLFQ] PID:8|PRT:3 -> [MLFQ] PID:9|PRT:3 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:2 -> [MLFQ] PID:8|PRT:2 -> [MLFQ] PID:9|PRT:2 ->
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:8|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:8|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
...
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:8|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
[MLFQ] PID:7|PRT:1 -> [MLFQ] PID:3|PRT:3 -> [MLFQ] PID:8|PRT:1 ->
[MLFQ] PID:3|PRT:3 -> [MLFQ] PID:9|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
5
[MLFQ] PID:9|PRT:1 -> [MLFQ] PID:9|PRT:1 -> [MLFQ] PID:9|PRT:1 ->
[MLFQ] PID:9|PRT:1 -> [MLFQ] PID:3|PRT:2 ->
The default allotments are used in this test case. Therefore, as shown in the scheduling
tracing output, the three child processes started with priority 3 at the beginning. They
were scheduled in an RR manner 2 times and were demoted to priority 2 (because the
default allotment for priority 3 is 2). While their scheduling priority was 2, they were
scheduled in an RR manner 4 times and then were demoted to priority 1 (because the
default allotment for priority 2 is 4).
Note that the PID of the parent process is 3 in this example. The parent process was
not scheduled until the end of the trace because it was waiting for the child processes’
completion. It was scheduled three times at the end (see the last three lines in the output),
each of which was returning from wait() when one of the child processes exited.
• Test case 3: This is a repeat of test case 1.
• Test case 4: In this test case, the parent process enables the scheduling tracing functionality, sets the scheduler type to MLFQ, creates 3 child processes, each of which performs
some long computation, and waits for their completion. In the middle of the long computation, one of the three child process (whose PID is multiples of 3) forks a grand-child
process which is termed as “runtime generated process” in the test code, and waits for
its completion. When all three child process complete, the parent process disables the
scheduling tracing. The expected scheduling tracing output is as follows:
>>>>> Test case 4: testing MLFQ scheduler with runtime generated process ...
Parent: child (pid=13) created!
Parent: child (pid=14) created!
Parent: child (pid=15) created!
[MLFQ] PID:13|PRT:3 -> [MLFQ] PID:14|PRT:3 -> [MLFQ] PID:15|PRT:3 ->
[MLFQ] PID:13|PRT:3 -> [MLFQ] PID:14|PRT:3 -> [MLFQ] PID:15|PRT:3 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:2 -> [MLFQ] PID:14|PRT:2 -> [MLFQ] PID:15|PRT:2 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
...
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:16|PRT:3 -> [MLFQ] PID:16|PRT:3 -> [MLFQ] PID:16|PRT:2 ->
[MLFQ] PID:16|PRT:2 -> [MLFQ] PID:16|PRT:2 -> [MLFQ] PID:16|PRT:2 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
...
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
[MLFQ] PID:13|PRT:1 -> [MLFQ] PID:3|PRT:3 -> [MLFQ] PID:14|PRT:1 ->
[MLFQ] PID:16|PRT:1 -> [MLFQ] PID:14|PRT:1 -> [MLFQ] PID:3|PRT:3 ->
[MLFQ] PID:16|PRT:1 -> [MLFQ] PID:16|PRT:1 -> [MLFQ] PID:16|PRT:1 ->
...
[MLFQ] PID:16|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
...
[MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 ->
[MLFQ] PID:15|PRT:1 -> [MLFQ] PID:15|PRT:1 -> [MLFQ] PID:3|PRT:2 ->
6
This test case is similar to test case 2 but with a new process generated during runtime.
In the above output, the PID of the runtime-generated process is 16, and the PID of the
runtime-generated process’s parent is 15. If one understands the expected output of test
case 2, the above output for this test case should be easily understandable.
• Test case 5: This test case is similar to test case 2 but with different allotments than
the default one. The allotments of priority 3 and 2 are set to 4 and 8 before the test, and
they are set back to the default values after the test. The expected scheduling tracing
output is as follows:
>>>>> Test case 5: testing MLFQ scheduler with new allotments ...
Parent: child (pid=17) created!
Parent: child (pid=18) created!
Parent: child (pid=19) created!
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:3 -> [MLFQ] PID:18|PRT:3 -> [MLFQ] PID:19|PRT:3 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:2 -> [MLFQ] PID:18|PRT:2 -> [MLFQ] PID:19|PRT:2 ->
[MLFQ] PID:17|PRT:1 -> [MLFQ] PID:18|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
[MLFQ] PID:17|PRT:1 -> [MLFQ] PID:18|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
...
[MLFQ] PID:17|PRT:1 -> [MLFQ] PID:18|PRT:1 -> [MLFQ] PID:3|PRT:3 ->
[MLFQ] PID:3|PRT:3 -> [MLFQ] PID:17|PRT:1 -> [MLFQ] PID:3|PRT:3 ->
[MLFQ] PID:3|PRT:3 -> [MLFQ] PID:19|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
[MLFQ] PID:19|PRT:1 -> [MLFQ] PID:19|PRT:1 -> [MLFQ] PID:19|PRT:1 ->
[MLFQ] PID:19|PRT:1 -> [MLFQ] PID:3|PRT:2 -> [MLFQ] PID:3|PRT:2 ->
Again, the above output should be easily understandable if one understands that of test
case 2.
2.2.2 What to do
(1) If you run the test program included in the base code, you’ll notice that the output of the OS
kernel scheduling tracing messages is mixed with the messages printed by the parent process.
This is because scheduling context switches happen as the parent process is forking child
processes. To ensure that the test program can generate a nicely formatted output as shown
above, your job is to implement a functionality that allows user programs to pause scheduling
different processes.
• Write a system call that pauses process scheduling. When process scheduling is paused,
the OS will keep running the current process until process scheduling is enabled again.
• Write the corresponding system call user space wrapper function, and declare it in
“user.h”. The wrapper function’s prototype should be:
7
void pause_scheduling(int pause);
– Description: This function pauses process scheduling.
– Arguments: This function takes one arguments.
– pause: To pause process scheduling, set this argument to 1. To enable process
scheduling, set this argument to 0.
– Return value: This function has no return value.
(2) Implement the functionality that allows user programs to set the allotments of different
scheduling priorities.
• Write a system call that sets the allotments of a scheduling priority.
• Write the corresponding system call user space wrapper function, and declare it in
“user.h”. The wrapper function’s prototype should be:
int mlfq_set_allotment(int priority, int allotment);
– Description: This function sets allotment of the “priority” (first arg) to “allotment”
(second arg).
– Arguments: This function takes two arguments.
– priority: the scheduling priority of which the allotment is to set.
– allotment: the new allotment value.
– Return value: On successfully setting the allotment for the priority, this function
returns 0. The function returns -1 on failures.
.
(3) Implement the MLFQ scheduling policy, remove the stub functions defined at the beginning
of schdtest.c (by simply removing the “STUB FUNCS” macro definition), and test your
implementation.
Note: Your implementation should keep the patch that fixes the always-100% CPU utilization
problem. If your code causes the problem to re-occur, 10 points off (see the 4th point in the
“Grading” section for details).
2.2.3 Tips
You may have noticed that the MLFQ scheduling policy you are going to implement is referred
to as MLFQ-like scheduling policy in the above description. The difference between the MLFQ
policy you will be implementing in this project and the MLFQ policy you learned in class is that
the MLFQ policy in this project does not mandate using different queues for different scheduling
priorities. Therefore, you are allowed to keep the current single-queue design intact in xv6 and
implement the required MLFQ logic. In other words, here the ”Q” is not necessarily physical
queues that are backed by queue data structures. It can be logical queues as well.
Learning in xv6 code how process scheduling context switches happen will be helpful for implementing the functionality of pausing process scheduling.
(Continue to next page.)
8
3 Process scheduling in xv6 - Q&A (30 points)
Answer the following questions about process scheduling implementation.
Q1: (10 points) Does xv6 kernel use cooperative approach or non-cooperative approach to gain
control while a user process is running? Explain how xv6’s approach works using xv6’s code.
Q2: (10 points) After fork() is called, why does the parent process run before the child process
in most of the cases? But in some cases, the child does run first. In what scenario will the
child process run before the parent process after fork()?
Q3: (10 points) When the scheduler de-schedules an old process and schedules a new process, it
saves the context (i.e., the CPU registers) of the old process and load the context of the new
process. Show the code which performs these context saving/loading operations. Show how
this piece of code is reached when saving the old process’s and loading the new process’s
context.
Key in your answers to the above questions with any the editor you prefer, export them in a PDF
file named “xv6-sched-mechanisms.pdf”, and submit the file to the assignment link in Brightspace.
9
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-sched-mechanisms.pdf”) to the assignment
link in Brightspace. We will not be able to know your code in your GitHub repository 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.
10
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 utilization 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 TA will try to fix the problem (for no more than 3 minutes);
2 if (problem solved)
3 1%-10% points off (based on how complex the fix is, TA’s discretion);
4 else
5 TA may contact the student by email or schedule a demo to fix the problem;
6 if (problem solved)
7 11%-20% points off (based on how complex the fix is, TA’s discretion);
8 else
9 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.
11