代做CS 550、代写c++，Java编程语言

日期：2024-03-23 09:48

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