In this project, you'll implement a simplified Multi-level Feedback Queue (MFQ) scheduler in xv6.

Start by reading Chapter 5 of the xv6 book. This is a very good guide to the details of how scheduling and context switches are implemented in xv6. The default and only scheduling policy in xv6 is round-robin. Every runnable process gets an equal CPU time-slice, regardless of priority.

You will build an MFQ scheduler with three priority queues: the top queue (numbered 0) has the highest priority and the bottom queue (numbered 2) has the lowest priority. When a process uses up its time-slice (counted as a number of ticks), it should be downgraded to the next (lower) priority level.

Your "standard" system already has all the tools you need. To begin, open a Terminal and type the following: By default, your command shell is bash and your current working directory is /home/student.

    cd ~/cs350
    mkdir pa4
    cd pa4
    wget --user=USERNAME --password=PASSWORD http://bourbon.usc.edu/cs350-m25/programming/pa4/xv6-pa4-src.tar.gz

where USERNAME and PASSWORD are the username and password used to access protected content from our class web site.

After you have downloaded the xv6-pa4-src.tar.gz file, do:

    tar xvf xv6-pa4-src.tar.gz
    cd xv6-pa4-src

Now you are all set up!

You need to understand how scheduler works in xv6. Most of the code for the scheduler is quite localized and can be found in proc.c, where you should first look at the routine scheduler(). It's essentially looping forever and for each iteration, it looks for a runnable process across the ptable. If there are multiple runnable processes, it will select one according to some policy. The vanilla xv6 does no fancy things about the scheduler; it simply schedules processes for each iteration in a round-robin fashion. For example, if there are three processes A, B and C, then the pattern under the vanilla round-robin scheduler will be:

    A B C A B C ...

where each letter represents a process scheduled within a timer tick.

Another relevant file is trap.c. The function trap(struct trapframe *tf) handles all the interrupts. The vanilla xv6 simply forces a process to yield at each timer interrupt (tick). You may want to do more than that to implement MLFQ.

Tips for PA4: (read at the end again):

• Many students find this project to be the most difficult one all semester. You are strongly encouraged to start early.
• You may find it helpful to include a “position of last element in queue” variable and a counter for ticks.
• Remember that once a process has finished running, it should be removed from the queue!
• In the last part of this assignment, some simple I/O and CPU-intensive tasks are printing and adding, respectively

Make sure you watch the lecture that covers the PA4 slides.

To make your life easier and our testing easier, you should run xv6 on only a single CPU (the default is two). To do this, in your Makefile, replace CPUS := 2 with CPUS := 1. When the grader grade this assignment, the grader will only grade with CPUS := 1.

It is much easier to deal with fixed-sized arrays in xv6 than linked-lists. For simplicity, we recommend that you use arrays to represent each priority level (queue). For example, define the following variables to represent the three priority queues:

    struct proc* q0[NPROC];
    struct proc* q1[NPROC];
    struct proc* q2[NPROC];

Your MFQ scheduler must follow these precise rules:

1. It must have three priority levels, numbered from 0 (highest) down to 2 (lowest).
2. On every xv6 timer tick the highest priority RUNNABLE process is scheduled to run.
3. If there are more than one process on the same priority level, then your scheduler should schedule all the processes at that particular level in a round robin fashion
4. The time-slice for priority 0 should be 1 timer tick. The times-slice for priority 1 is 2 timer ticks; for priority 2, it is 8 timer ticks.
5. When a timer tick occurs, whichever process was currently using the CPU should be considered to have used up an entire timer tick's worth of CPU. That is, if a process is running and its total ticks (since it was created) is n-1 before it yields the CPU, the nth tick—the one that was about to occur before the process yielded the CPU—should not count towards the total ticks or the current time-slice ticks. (Yes, a process could game the scheduler by repeatedly relinquishing the CPU just before the timer tick occurs, therefore preventing its time-slice from ever being exhausted; ignore this!)
6. When a new process arrives, it should be placed at the end the priority 0 queue (highest priority).
7. At priorities 0, and 1, after a process consumes its time-slice it should be downgraded one priority level. Whenever a process is moved to a lower priority level, it should be placed at the end of the queue.
8. If a process wakes up after voluntarily giving up the CPU (e.g., by performing I/O or sleeping before the time slice is up) it stays at the same priority level. Place this process at the end of its queue; it should not preempt a process with the same priority.
9. Your scheduler must never preempt a lower priority process if a higher priority process is available to run.
10. You need to implement the priority boosting mechanism to avoid starvation, which will be used to increase a priority of a process that has not been scheduled in a while. The goal is to avoid starvation, which happens when a process never receives CPU time because higherpriority processes keep arriving.
11. After a RUNNABLE process has been waiting in the lowest priority queue for 50 ticks or more, move the process to the end of the highest priority queue. This method of priority boosting is called aging.

For this project, you need to create a new system call to help you debug the scheduler and to help you obtain information about how multiple processes are scheduled over time.

    int getpinfo(int pid)

This routine takes as input an ID of a process (pid) and prints some basic scheduling information about the process to the terminal: the ticks at which it is scheduled, how long it runs before it gives up the CPU, what priority it has each time it is scheduled, etc. This function returns -1 in case of error and 0 in case of success. A process should call this function at the very end of its execution to get a full view of its scheduling record.

You'll need to fill in all the pieces of information somehow in the kernel and print the results for the user. You have done this in PA1. You may want to stare at the routines like int argint(int n, int *ip) in syscall.c for some hints.

To get the information mentioned above, there are several changes that we suggest you make to xv6.

• You’ll probably need to define a structure in the kernel to record scheduling information for a process at each tick. This will give you the necessary information to plot the graphs in part 3.
• You may also want to add some new fields in the proc struct as described below. These fields are not particularly useful for plotting the graphs in part 3 but can be used for debugging your MLFQ scheduler.

      int times[3];    // number of times each process was scheduled at each of 3 priority queues
      int ticks[3];    // number of ticks each process used the last time it was scheduled in each
                       //     priority queue (cannot be greater than the time-slice for each queue)
      uint wait_time;  // number of ticks each RUNNABLE process waited in the lowest priority queue

• If you’re using the number of ticks as the index to an array, please be careful that this number may exceed NTICK after a while and overflow your array (this may happen without any errors being emitted), leading to nonsensical results. You probably want to figure out a way to allow a process to start a tick variable itself, and to allow other processes to join this process's "timeline" by sharing that tick variable (you can do so through system calls).

For your reference, getpinfo() would produce an output similar to this (your formatting does not need to match that of the reference output, but you must include the same information):

    PSTAT_START
    *********
    name = CPUintensive, pid = 5
    wait time = 0
    ticks = {1, 2, 8}
    times = {1, 1, 3}
    *********
    start=1, duration=1, priority=0
    start=2, duration=0, priority=1
    start=2, duration=0, priority=1
    start=2, duration=0, priority=1
    start=2, duration=0, priority=1
    start=2, duration=0, priority=1
    start=2, duration=0, priority=1
    start=2, duration=0, priority=1
    start=4, duration=8, priority=2
    start=12, duration=8, priority=2
    PSTAT_END

Please note that we will not grade the wait time, ticks and times rows in the above printout (i.e., rows 4, 5, and 6 above) because their values can be implementation dependent.

In addition to implementing the MFQ scheduler, you must design three user-level test programs to show that that your scheduler works correctly.

Writing tests for xv6 is a good exercise in itself, however, it is a bit challenging. This is a good chance to practice creating test cases and think comprehensively!

Your tests for xv6 are essentially user programs that execute at the user level. Create three user level programs (pa4-mixed.c, pa4-aging.c, and pa4-cheat.c) with different workloads to demonstrate behavior of your scheduler. In particular,

pa4-mixed.c

Implement a mixed workload that includes an I/O intensive parent process and a CPU intensive child process.

The pseudo code should look like the following:

    pid = fork()
    if (pid > 0) then
        io_intensive(num_ios);
        wait()
        getpinfo(getpid());
        exit()
    else
        cpu_intensive(num_millions);
        getpinfo(getpid());
        exit()
    end-if

The total running time should be around but less than 100 ticks. Please see the printout below for an example. In the above code, you can tweek num_ios and num_millions to control the running time of your parent and child processes.

The cpu_intensive() function can like the following:

    static void cpu_intensive(int num_millions)
    {
        volatile unsigned long long k = 0;
        for (int i = 0; i < num_millions*1000000; i++)
        {
            k++;
        }
    }

The io_intensive() function can like the following:

    static void io_intensive(int num_itr)
    {
        for (int i = 0; i < num_itr; i++)
        {
            printf(99, "\n");
        }
    }

pa4-aging.c

Implement a workload that demonstrates how priority boost can improve performance of a long running CPU bound process

The pseudo code should look like the following:

    pid = fork()
    if (pid > 0) then
        for (i = 0; i < 10; i++)
            if (fork() == 0) then
                cpu_intensive(num);
                getpinfo(getpid());
                exit();
            end-if
        end-for
        cpu_intensive(num);
        for (i = 0; i < 11; i++)
            wait()
        end-for
        getpinfo(getpid());
        exit()
    else
        cpu_intensive(num);
        getpinfo(getpid());
        exit()
    end-if

What's important to see is that for at least one process, the priority changed from 2 to 0 at least once. In the above code, you can tweek num to control the running time of your processes. The total running time should be less than 500 ticks.

pa4-cheat.c

Implement a workload that demonstrates how MFQ scheduler can be gamed. You must create a child process and the child process must always run at the highest priority. Please don't call getpinfo() in the parent process and only call getpinfo() in the child process.

A process manages to stay in the highest priority queue by yielding the CPU before its time slice expires. Hint: you can create a loop that iteratively calls sleep(1) to relinquish the processor before the timer interrupt occurs. The number of ticks will not be updated, and the process will stay in the highest priority queue.

Your child process must run for at least 30 ticks.

Your tests should compile and run (i.e., you should modify the Makefile to compile them into executable xv6 programs called pa4-mixed, pa4-aging, and pa4-cheat. The programs should print out the process statistics by calling getpinfo().

You should make three graphs that show timelines of the processes in each of your three tests, including which queue each process is on, and how much CPU time (ticks) they received.

You can use whatever graphing tool you would like ("gnuplot" is a fine, basic choice). Name the printout of your test programs pa4-mixed.out, pa4-aging.out and pa4-cheat.out and produce graphs for them (in PDF format). Your graphs must be named pa4-mixed-parent.pdf, pa4-mixed-child.pdf, and pa4-aging.pdf.

Please describe the workload that you ran to create your graph and explain why your graph shows the results that it does in the pa4-README.txt, which is part of your PA4 submission.

To obtain the info for your graph, you should use the getpinfo() system call. Use the graphs to prove to us that your scheduler is working as desired.

If you run pa4-mixed and you get the following for the parent process (I/O intensive):

    PSTAT_START
    *********
    name = pa4-mixed, pid = 3
    wait time = 0
    ticks = {1, 2, 4}
    times = {7, 1, 3}
    yield count = 4
    willing yields count = 7
    wait count = 0
    *********
    start=203, duration=0, priority=0
    start=204, duration=0, priority=0
    start=204, duration=0, priority=0
    start=204, duration=0, priority=0
    start=204, duration=0, priority=0
    start=204, duration=0, priority=0
    start=204, duration=1, priority=0
    start=205, duration=2, priority=1
    start=210, duration=8, priority=2
    start=226, duration=8, priority=2
    start=242, duration=4, priority=2
    PSTAT_END

and the following for the child process (CPU intensive):

    PSTAT_START
    *********
    name = pa4-mixed, pid = 4
    wait time = 0
    ticks = {1, 2, 8}
    times = {1, 1, 7}
    yield count = 9
    willing yields count = 0
    wait count = 0
    *********
    start=207, duration=1, priority=0
    start=208, duration=2, priority=1
    start=218, duration=8, priority=2
    start=234, duration=8, priority=2
    start=246, duration=8, priority=2
    start=254, duration=8, priority=2
    start=262, duration=8, priority=2
    start=270, duration=8, priority=2
    start=278, duration=8, priority=2
    PSTAT_END

Then your graphs should look like the following:

A crude (but acceptable) version of the above graph can be manually created/edited with this Excel file (pa4-mixed-parent.xls). Please choose Print To PDF in Excel to create a PDF file (you should print in landscape mode and have the whole graph fit on one page).

A crude (but acceptable) version of the above graph can be manually created/edited with this Excel file (pa4-mixed-child.xls). Please choose Print To PDF in Excel to create a PDF file (you should print in landscape mode and have the whole graph fit on one page).

It would be perfectly fine if you subtract the start tick value by the smallest ticket value in the printout.

The grading guidelines has been made available. Please run the commands in the grading guidelines on a standard 32-bit Ubuntu 16.04 system. It is possible that there are bugs in the guidelines. If you find bugs, please let the instructor know as soon as possible. (Note: if I change the grading guidelines, I will make an announcement in the class Piazza. Please remember that you are required to read my posts in the class Piazza.)

The grading guidelines is the only grading procedure we will use to grade your program. No other grading procedure will be used. Please note that the grader may use a different set of test programs and commandline arguments when grading your submission. (We may make minor changes if we discover bugs in the script or things that we forgot to test.) It is strongly recommended that you run your code through the commands in the grading guidelines.

• Please read the general programming FAQ if you need a refresher on file I/O and bit/byte manipulications in C.

If you have made all your code changes in-place (which you are requied to do), it will be very easy to create a gzipped tarfile for submission using the Bistro system. To create your submission file, just do the following:

    make pa4-submit

and the following command should run:

    tar cvzf pa4-submit.tar.gz \
            Makefile \
            pa4-README.txt \
            proc.c proc.h \
            trap.c \
            syscall.c syscall.h \
            sysproc.c \
            defs.h \
            pstat.h stat.h \
            user.h \
            usys.S \
            pa4-mixed.c pa4-mixed.out pa4-mixed-parent.pdf pa4-mixed-child.pdf \
            pa4-aging.c pa4-aging.out pa4-aging.pdf \
            pa4-cheat.c pa4-cheat.out

Please note that you are not permitted to change any other existing files. If you submit another existing file, it will be deleted before grading. If you give instructions to the grader to modify another existing file (other than Config.mk), it will disregarded.

A pa4-README.txt template file is provided here. You must save it as your pa4-README.txt file and follow the instructions in it to fill it out with appropriate information and include it in your submission. You must not delete a single line from w1-README.txt. Please make sure that you satisfy all the README requirements.

To check the content of pa4-submit.tar.gz, you can use the following command:

    tar tvzf pa4-submit.tar.gz

Please read the output of the above command carefully to see what files were included in pa4-submit.tar.gz and what are their file sizes and make sure that they make sense.

Please enter your USC e-mail address and your submission PIN below. Then click on the Browse button and locate and select your submission file (i.e., pa4-submit.tar.gz). Then click on the Upload button to submit your pa4-submit.tar.gz. (Be careful what you click! Do NOT submit the wrong file!) If you see an error message, please read the dialogbox carefully and fix what needs to be fixed and repeat the procedure. If you don't know your submission PIN, please visit this web site to have your PIN e-mailed to your USC e-mail address.

When this web page was last loaded, the time at the submission server (merlot.usc.edu) was 28Nov2025-01:56:12. Reload this web page to see the current time on merlot.usc.edu.

USC Email:

 @usc.edu

Submission PIN:

Event ID (read-only):

Submission File Full Path:

 

 
If the command is executed successfully and if everything checks out, a ticket will be issued to you to let you know "what" and "when" your submission made it to the Bistro server. The next web page you see would display such a ticket and the ticket should look like the sample shown in the submission web page (of course, the actual text would be different, but the format should be similar). Make sure you follow the Verify Your Ticket instructions to verify the SHA1 hash of your submission to make sure what you did not accidentally submit the wrong file. Also, an e-mail (showing the ticket) will be sent to your USC e-mail address. Please read the ticket carefully to know exactly "what" and "when" your submission made it to the Bistro server. If there are problems, please contact the instructor.

It is extreme important that you also verify your submission after you have submitted pa4-submit.tar.gz electronically to make sure that every you have submitted is everything you wanted us to grade. If you don't verify your submission and you ended up submit the wrong files, please understand that due to our fairness policy, there's absolutely nothing we can do.

Finally, please be familiar with the Electronic Submission Guidelines and information on the bsubmit web page.