The main goal for this project is to modify the MINIX 3 scheduler to be more flexible. You must implement a new type of priority scheduler.

This project will also teach you how to experiment with operating system kernels, and to do work in such a way that might crash a computer. You'll get experience with modifying a kernel, and may end up with an OS that doesn't work, so you'll learn how to manage multiple kernels, at least one of which works. 
Basics
The goal of this assignment is to get everyone up to speed on modifying MINIX 3 and to gain some familiarity with scheduling. In this assignment you are to implement a multi-level priority scheduler for user-level processes.

The multi-level priority scheduler used in this project will have three queues that operate in a round-robin fashion. Processes in a higher priority queue run more often than processes in a low priority queue, but all processes do get to run. (There is no starvation, and no need for aging/balancing.)

Re-Compiling the Minix Source Code
To get you started, here is the process for recompiling the Minix kernel and booting using the new kernel.

Boot up your Minix VM and login. 
Let's start by making a clean copy of the Minix source code, just in case we have problems later and want to see it.
cd /usr 
cp -ar src src-orig

cd /usr/src 
This is the location of all the Minix source code. Take a look around if you want. 
cd tools 
make 
There are a lot of options when you want to rebuild Minix. This lists all of them. 
make clean install 
This will rebuild the entire kernel and install it. 
shutdown 
Restart the VM. When the intro menu appears, press "2". 
If you don't press anything, 2 will be chosen by default.

If you've been making changes to the Minix source and your new kernel doesn't boot properly (this will happen a lot...) then restart the VM and press "1" when the intro menu comes up. This will boot a knonw good copy of the kernel and allow you to try and fix your code errors.

Details
Unless explicitly specified, all source code can be found in /usr/src/.

In this project, you will modify the scheduler for MINIX. This should mostly involve modifying code in kernel/proc.c specifically the sched() and pick_proc() functions (and perhaps enqueue() and dequeue()and balance_queues(), depending on your implementation). You may also need to modify kernel/proc.h to add elements to the proc structure and modify queue information (NR_SCHED_QUEUES, TASK_Q, IDLE_Q, etc.). Process priority is set in do_getsetpriority() in servers/pm/misc.c, which calls do_nice() in kernel/system/do_nice.c. You might be better off just using the nice() system call , which calls do_nice() directly. You'll probably want to modify what do_nice() does-for our new scheduler, nice() can be used to raise or lower the priority of a process. 

The current MINIX scheduler is relatively simple. It maintains 16 queues of "ready" processes, numbered 0-15. Queue 15 is the lowest priority (least likely to run). Queue 0 is the highest priority, and contains several kernel tasks that never get a lower priority. Queues 1-14 contain all of the other processes. Processes have a maximum priority (remember, higher priorities are closer to 0), and should never be given a higher priority than their maximum priority. You're going to need to add 3 queues to the existing 16 for a total of 19 queues. Your solution, however, should only use the new queues for user processes and use the existing Minix scheduling code for system processes. The easiest solution is to use the top 16 queues for system processes using the existing code, and to use the new queues for user processes. You can identify system processes by seeing if the SYS_PROC bit is set in a process's p_priv->s_flags variable. 

Multiple Round-Robin Queues

The algorithm you need to implement for user processes uses three round robin queues. Processes are placed into the first queue when they are created. They are moved between queues if their priority is adjusted using the setpriority(pri) system call. Set priority will set the priority of a process to pri. Since there are only three queues, there are only three priority levels: 0 (the highest priority), 1 and 2. For example, calling setpriority(1) will cause a process to change to priority 1 and get places in the appropriate queue. Processes only change priority explicitly, they do not change priority automatically.


The scheduler runs all of the processes in the first queue once and then runs a single process from the second queue. After all of the processes in the second queue have run, a process from the third queue is selected to run. This can be implemented in several ways; one possibility is to include a "pseudo-process" in the first queue that, when at the front of the queue, causes a process from the second queue to be run (also repeated in the second queue to run a process in the third queue).

Assume the following processes are in the three queues:


Queue 1: P1 , P2 , P3 
Queue 2: P4 , P5 
Queue 3: P6 , P7

The scheduler would run processes in this order:
P1 , P2 , P3 , P4 , P1 , P2 , P3 , P5 , P6 , P1 , P2 , P3 , P4 ...

To do this, you should add three additional queues to kernel/proc.c. System processes are scheduled by the same mechanism they use currently, but user processes are scheduled by being initially placed into queue 1, with a later move to queue 2 (or from queue 2 to queue 3). You can do this by modifying sched() and pick_proc() in kernel/proc.c. You might also need to modify enqueue() and dequeue(), and should feel free to modify any other files you like. 


New processes are created and initialized in kernel/system/do_fork.c. This is probably the best place to initialize any data structures, if needed.