About Priority Scheduling

"Scheduling" refers to controlling which thread gets to run at any given time. The original version of the Pintos operating system uses a simple round-robin scheduler. A process switch occurs when a thread calls thread_yield, when a thread blocks, or during a timer interrupt when the current time slice has expired. The round-robin scheduler simply switches to the thread that is at the front of the list of ready threads. When a thread is created or unblocked, or its time-slice expires, that thread is added to the back of the ready list.

However, it is common for operating systems to assign "priorities" to threads. A priority is just a number between 0 and some maximum (63 in Pintos). The running thread should always be the thread that has the largest priority among all runnable threads.

There are several versions of priority scheduling. As the first part of this assignment, you will implement the most basic version, which has a number of problems. But the basic version can be used as the starting point for more realistic schedulers. As a second assignment, you will implement a more realistic version of priority scheduling: MLFQS. (The last part of Pintos Project 1 would be to implement another type of priority scheduling; we will probably not do that part.)

In the basic version of priority scheduling, a thread is assigned a priority when it is created. It can change its own priority later by calling the function thread_set_priority(). For now, those are the only ways that the priority of a thread can change.

What happens if there are multiple threads with the same priority? The scheduler should still schedule those threads using the round-robin algorithm.

One of the problems with basic priority scheduling is starvation: If there are always higher priority threads to run, a lower priority thread might not ever get to run at all. Another problem is that a thread that spends a lot of time waiting on IO will not get a fair share of CPU time, compared to a thread of equal priority that spends all of its time computing (because the IO-bound thread will often block after using only a small part of its time-slice, while the compute-bound thread will always use its full time slice). An MLFQ scheduler is meant to solve these problems. In an MLFQS, a thread no longer controls its own priority. Instead, the operating systems adjusts the priorities of all threads to try to ensure that every thread gets a fair share of CPU time.

Pintos Part 2: Implement Basic Priority Scheduling in Pintos OS

The first part of this assignment is to implement the basic version of priority scheduling. You will need to work (at least) in the files threads/threads.c and threads/sync.c.

You should build on the work that you did for Lab 4. Some of the tests for the priority scheduler also require the alarm functionality from that lab. (If you didn't succeed in implementing thread_sleep, you might want to consult with me about getting a copy of my solution.)

Think about what needs to happen... When the scheduler selects a new thread to run from the ready list, it should be the highest priority thread in that list. When a thread is created, if its priority is greater than the priority of the currently running thread, then the new thread should start running immediately. If a thread changes its own priority and if there is a thread of higher priority on the ready list, then the higher priority thread should run. When a thread that is waiting on a semaphore, lock, or condition variable is unblocked, and if that thread has higher priority than the currently running thread, then the unblocked thread should run immediately. (If you did not implement sleep using semaphores, you also need to worry about what happens when a thread wakes from sleep.)

You need to implement all of that functionality. Before you start, you should make sure that you understand how the round-robin scheduler works. You will need to understand the data structures that are used for the ready list and for the lists of waiting threads for semaphores, locks, and condition variables. And you will need to know what functions like schedule() and thread_yield() do.

The tests for the priority scheduler are named priority-change, priority-preempt, alarm-priority, priority-fifo, priority-sema, and priority-condvar. Remember that you can run a test with a command such as

pintos run priority-change

or

pintos -v -- run priority-change

To run all the tests and report on whether your implementation passes each test, give the following command in the build directory:

make check-priority

You should concentrate on getting a working implementation, without worrying too much about efficiency. For example, real operating systems often use a separate list for each priority, but you are not required to do that for this assignment. (My solution only uses one ready list for all runnable threads.)

One warning: After you implement the MLFQ scheduler, it will be possible for the priority of a thread to change while it is blocked. And one note: You might want to look again at the API in lib/kernel/list.h.

Pintos Part 3: Implement an MLFQS

The second part of this assignment is to add an MLFQS (multilevel feedback queue scheduler) to Pintos. The resulting operating system should be able to run either the basic priority scheduler or the MLFQ scheduler. The choice is made when Pintos boots. By default, it will run the basic priority scheduler. To make it use the MLFQ scheduler, you need to add the kernel option -mlfqs to the command that is used to run Pintos. For example:

pintos -v -- -mlfqs run mlfqs-load-1

(The meaning of "--" in the command is that options that come before the "--" are options to the virtual machine in which Pintos will be run. Options that come after the "--" are part of the command that the Pintos kernel itself reads when it boots.)

The kernel has a global variable named thread_mlfqs that it sets to true if the -mlfqs option is present. Otherwise, thread_mlfqs is false. The code that implements MLFQS should only run if thread_mlfqs is true. Furthermore, when thread_mlfqs is true, the function thread_set_priority should have no effect, since under MLFQS, threads do not set their own priorities. However, it is still true under MLFQS that a higher priority thread should always run in preference to a lower priority thread.

You will implement an MLFQS that is similar to the one used in BSD Unix, version 4.4. The details are discussed in Appendix B of the Pintos documentation. The basics are summarized here.

As the documentation notes, "priority, nice, and ready_threads are integers, but recent_cpu and load_avg are real numbers. Unfortunately, Pintos does not support floating-point arithmetic in the kernel, because it would complicate and slow the kernel. Real kernels often have the same limitation, for the same reason. This means that calculations on real quantities must be simulated using integers." Section B.6 explains how to do that. I have implemented the formulas from Section B.6 as a set of macros in the header file fixed_arithmetic.h. You can find a copy in /classes/cs431, which you can add to the threads directory in the Pintos source and #include in threads.h or threads.c.

Although threads do not set their own priority, they do set their own "niceness." The niceness is an integer in the range -20 to 20. The niceness value of a thread modifies its priority. Positive niceness increases the priority; negative niceness decreases it. (Negative niceness is really the opposite of niceness.) You need to implement the functions thread_get_nice and thread_set_nice in threads.c.

In addition to niceness and priority every thread will have a property named recent_cpu, which represents the proportion of CPU time that the thread has been given recently. There will be also a global variable, shared by all threads, named load_average which represents the number of runnable threads, averaged over the recent past. While niceness and priority are integers, recent_cpu and load_average are real numbers that must be implemented as integers using the fixed arithmetic techniques from Section B.6.

In order to support the MLFQS test programs, you must implement the functions thread_get_load_average and thread_get_recent_cpu. The first function must return the (real number) load average, multiplied by 100, and rounded to the nearest integer. The second function returns the (real number) recent_cpu of the current thread, multiplied by 100 and rounded to the nearest integer.

Here is a specification of the calculations that are needed to set and update the values of niceness, load_average, recent_cpu, and priority:

• The niceness of the initial thread is set to 0. Other threads inherit the niceness value from their parent (the thread that calls thread_create to create the thread). After creation, the niceness only changes when a thread calls thread_set_nice.
• The priority of a thread (for MLFQS) is first calculated when it is created. It will be immediately recalculated when the thread calls thread_set_nice. In addition, the priority of every thread (running, ready, or blocked, except the idle thread) is recalculated every fourth clock tick. The formula for calculating priority is:

  priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
  

  Note that priority must be truncated to an integer and clamped to the range 0 to PRI_MAX (which is 63). (Also note that for the basic scheduler, the initial priority of a thread is set from a parameter in thread_create.)
• The recent_cpu of the initial thread is set to 0. Other threads inherit the recent_cpu value from their parent when they are created. For every timer tick, the recent_cpu value of the current thread is increment by 1, unless it is the idle thread. Furthermore, once every second, the recent_cpu for every thread is recalculated using the formula

  recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice
  

  Note that "every second" means that this should happen exactly when timer_ticks() % TIMER_FREQ == 0, and not at any other time. This is required for some of the test programs.
• The load_average is 0 at system boot. Every second, it is recalculated using the formula

  load_avg = (59/60)*load_avg + (1/60)*ready_threads
  

  where ready_threads is the number of runnable threads, not counting the idle thread. That is, the count includes the threads on the ready list, and it includes the current thread if the current thread is not the idle thread.

If you follow these specifications carefully (using fixed arithmetic for the calculations), it need not take a lot of time to implement the MLFQ scheduler. However, it is easy to make mistakes that can lead to time-consuming debugging. So think first and work carefully!

The test programs for the MLFQS are named mlfqs-load-1, mlfqs-load-60, mlfqs-load-avg, mlfqs-recent-1, mlfqs-fair-2, mlfqs-fair-20, mlfqs-nice-2, mlfqs-nice-10, and mlfqs-block. You can run the tests individually. Be sure to include the -mlfqs option in the pintos command, as described above. To run all the tests and check whether your solution passes, you can use the command

make check-mlfqs

in the build directory.