Overview
In this programming assignment, you'll implement priority scheduling algorithm in XV6.
The existing scheduler in xv6 is a Round-Robin (RR) scheduler. On each timer interrupts, the interrupt handler switches to the kernel scheduler, which then selects the next available process to run. This scheduler, while simple, is too primitive to do anything interesting.
Assignment
In this assignment, you'll implement an advanced scheduler that schedules processes based on their priorities. Each process has a priority, and the scheduler always picks the process with the highest priority. The scheduler does RR scheduling for processes with equal priorities. Note: to simplify the assignment, assume all processes are single-threaded.
To implement this scheduler you will need to implement the following system calls:
- int nice(int incr);
- int getpriority();
- int setpriority(int new_priority);
Your scheduler will support five possible priority classes, identified by integers 0, 1, 2, 3, 4. The smaller the integer, the higher the priority. For example, 0 represents the highest priority. nice(incr) system call increases or decreases the priority of the current process by incr. The argument incr may be either positive or negative. For example, if the priority of the current process is 1, and after calling nice(1), the priority will become 2. The system call, nice(incr) , should return 0 only when it successfully increases or decreases the priority of the current process, and should return -1 if the priority exceeds the priority range [0, 4] or upon any other failures.
The system call getpriority() retrieves the priority of the current process, and setpriority(new_priority) sets new priority for the current process. These system calls should return 0 only if it successfully sets the priority, and should return -1 otherwise.
Your implementation must satisfy the following requirements. Your scheduler uses multiple queues of processes. Each queue is associated with a priority class, and it contains all processes with this priority. Only the processes in the RUNNABLE state should be in one of the ready qeueus. On each timer interrupt or when the current process yields the CPU (e.g., via a call to yield()), the scheduler puts the current process to the back of the corresponding queue. It then schedules the process from the front of the ready queue with the highest priority. If the ready queue with the highest priority is empty, the scheduler goes to the next queue, and so on.
Your queues should only store processes in the RUNNABLE state. For example, if a process calls sleep(), it should not stay in the ready queue, until it is woken up. The scheduler should put processes just created or woken up to the back of the corresponding ready queue.
The init process will initially has priority 0 as it was spawned. When some process calls fork(), the child process should inherit the priority of the parent process
Note that to simplify this assignment, we do not ask you to implement per-CPU ready queues. In stead, you keep a global array of ready queues, and the scheduler running on each CPU all grab processes from this global array.
If you need a place to start looking to change the scheduler, look in the proc.c file.
Combining with part 1
The purpose of the first part of this assignment was to create a parallel processing environment that would adequately test the scheduler.
Now we need to change what we did in part 1 so that it uses priorities.
Change the low priority program from part 1 so that when it runs the first thing it does is set its own priority to the lowest priority. Do the same thing for the high priority program except that it is set for the highest priority.
When you run forkExecTest the behavior of the program should now be different from part 1 - specifically, instead of the low priority and high priority programs interweaving the high priority programs should interweave first then the low priority programs should interweave.
Make sure to take out the sleeps in both programs or your schedule may skip processes when they are in SLEEPING state.
What to turn in
For this assignment you will need to create a README file that details every file that you changed from the original XV6 source code. Specifically, have the README file have an entry for each file similar to the following:
- file name that was changed/created
- how that file was changed
With the README file inside the XV6 directory compress the directory - either zip it or tar it - and turn the compressed file.
I DO NOT recommend using "make dist" and "make tar" as there are some bugs that we need to sort out.
Before turning in your project uncompress the file in another directory and test it.
https://www.dropbox.com/s/n3e82cjslj6ye3i/xv6-part-1.zip?dl=0