Task 1: Scheduling
******************

In this assignment, we give you a minimally functional thread system. Your job is to extend the functionality of this system to gain a better understanding of synchronization problems.

You will be working primarily in the threads directory for this assignment. Compilation should be done in the threads directory.

Before you read the description of this task, you should read all of the following sections: Introduction, Task 0--Codebase, Coding Standards, Debugging Tools, and Development Tools.  You should at least skim the material from PintOS Loading through Memory Allocation, especially Synchronization.  To complete this task you will also need to read 4.4BSD Scheduler.

You must build task 1 on top of a working task 0 submission as some of the task 1 test rely on a non-busy waiting implementation of timer_sleep().

Background
==========

Now that you've become familiar with PintOS and its thread package, it's time to work on one of the most critical component of an operating system: the scheduler.

Working on the scheduler requires you to have grasped the main concepts of both the threading system and synchronization primitives. If you still feel uncertain about these topics, you are warmly invited to refer back to Understanding Threads and Synchronization and to carefully read the code in the corresponding source files.

Development Suggestions
=======================

In the past, many groups divided the assignment into pieces, then each group member worked on his or her piece until just before the deadline, at which time the group reconvened to combine their code and submit.  This is a bad idea.  We do not recommend this approach.  Groups that do this often find that two changes conflict with each other, requiring lots of last-minute debugging.  Some groups who have done this have turned in code that did not even compile or boot, much less pass any tests.

localgitpolicy

You should expect to run into bugs that you simply don't understand while working on this and subsequent tasks.  When you do, reread the appendix on debugging tools, which is filled with useful debugging tips that should help you to get back up to speed (see Debugging Tools).  Be sure to read the section on backtraces (see Backtraces), which will help you to get the most out of every kernel panic or assertion failure.

Requirements
============

Design Document
---------------

When you submit your work for task 1, you must also submit a completed copy of the task 1 design document. You can find a template design document for this task in pintos/doc/threads.tmpl and also on CATe. You are free to submit your design document as either a .txt or .pdf file. We recommend that you read the design document template before you start working on the task. See Task Documentation, for a sample design document that goes along with a fictitious task.

Setting and Inspecting Priorities
---------------------------------

Implement the following functions that allow a thread to examine and modify its own priority. Skeletons for these functions are provided in threads/thread.c.

 -- Function: int thread_get_priority (void)
     Returns the current thread's effective priority.

 -- Function: void thread_set_priority (int NEW_PRIORITY)
     Sets the current thread's priority to NEW_PRIORITY.

     If the current thread no longer has the highest priority, yields.

Priority Scheduling
-------------------

Implement priority scheduling in PintOS. When a thread is added to the ready list that has a higher priority than the currently running thread, the current thread should immediately yield the processor to the new thread.  Similarly, when threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be awakened first.  A thread may raise or lower its own priority at any time, but lowering its priority such that it no longer has the highest priority must cause it to immediately yield the CPU. In both the priority scheduler and the advanced scheduler you will write later, the running thread should be that with the highest priority.

Thread priorities range from PRI_MIN (0) to PRI_MAX (63). Lower numbers correspond to lower priorities, so that priority 0 is the lowest priority and priority 63 is the highest. The initial thread priority is passed as an argument to thread_create.  If there's no reason to choose another priority, new threads should use PRI_DEFAULT (31).  The PRI_ macros are defined in threads/thread.h, and you should not change their values.

Priority Donation
-----------------

One issue with priority scheduling is ``priority inversion''.  Consider high, medium, and low priority threads H, M, and L, respectively.  If H needs to wait for L (for instance, for a lock held by L), and M is on the ready list, then H will never get the CPU because the low priority thread will not get any CPU time.  A partial fix for this problem is for H to ``donate'' its priority to L while L is holding the lock, then recall the donation once L releases (and thus H acquires) the lock.

Implement priority donation.  You will need to account for all different situations in which priority donation is required.  In particular, be sure to handle:

  * multiple donations: multiple priorities can be donated to a single thread.

  * nested donations: if H is waiting on a lock that M holds and M is waiting on a lock that L holds, then both M and L should be boosted to H's priority.  If necessary, you may impose a reasonable limit on depth of nested priority donation, such as 8 levels.

You must implement priority donation for locks. You do not need to implement priority donation for the other PintOS synchronization constructs. However, you do need to implement priority scheduling in all cases.

Finally, you should review your implementations of thread_get_priority and thread_set_priority to make sure that they exhibit the correct behaviour in the presence of dontations. In particular, in the presence of priority donations thread_get_priority must return the highest donated priority.

You do not need to provide any interface to allow a thread to directly modify other threads' priorities. The priority scheduler is also not used in any later task.

Advanced Scheduler
------------------

Implement a multilevel feedback queue scheduler similar to the 4.4BSD scheduler to reduce the average response time for running jobs on your system. See 4.4BSD Scheduler, for detailed requirements.

Like the priority scheduler, the advanced scheduler chooses the thread to run based on priorities.  However, the advanced scheduler does not do priority donation.  Thus, we recommend that you have the priority scheduler working, except possibly for priority donation, before you start work on the advanced scheduler.

You must write your code to allow us to choose a scheduling algorithm policy at PintOS startup time.  By default, the priority scheduler must be active, but we must be able to choose the 4.4BSD scheduler with the -mlfqs kernel option.  Passing this option sets thread_mlfqs, declared in threads/thread.h, to true when the options are parsed by parse_options, which happens early in main.

When the 4.4BSD scheduler is enabled, threads no longer directly control their own priorities.  The PRIORITY argument to thread_create should be ignored, as well as any calls to thread_set_priority, and thread_get_priority should return the thread's current priority as set by the scheduler.

The advanced scheduler is not used in any later task.

FAQ
===

How much code will I need to write?

     Here's a summary of our reference solution, produced by the diffstat program.  The final row gives total lines inserted and deleted; a changed line counts as both an insertion and a deletion.

      threads/fixed-point.h |  120 ++++++++++++++++++
      threads/synch.c       |   88 ++++++++++++-
      threads/thread.c      |  196 ++++++++++++++++++++++++++----
      threads/thread.h      |   19 ++
      4 files changed, 397 insertions(+), 26 deletions(-)

     The reference solution represents just one possible solution.  Many other solutions are also possible and many of those differ greatly from the reference solution.  Some excellent solutions may not modify all the files modified by the reference solution, and some may modify files not modified by the reference solution.

     fixed-point.h is a new file added by the reference solution.

Do we need a working Task 0 to implement Task 1?

     Yes.

How do I update the Makefiles when I add a new source file?

     To add a .c file, edit the top-level Makefile.build. Add the new file to variable DIR_SRC, where DIR is the directory where you added the file.  For this task, that means you should add it to threads_SRC or devices_SRC.  Then run make.  If your new file doesn't get compiled, run make clean and then try again.

     When you modify the top-level Makefile.build and re-run make, the modified version should be automatically copied to threads/build/Makefile.  The converse is not true, so any changes will be lost the next time you run make clean from the threads directory.  Unless your changes are truly temporary, you should prefer to edit Makefile.build.

     A new .h file does not require editing the Makefiles.

What does warning: no previous prototype for `FUNC' mean?

     It means that you defined a non-static function without preceding it by a prototype.  Because non-static functions are intended for use by other .c files, for safety they should be prototyped in a header file included before their definition.  To fix the problem, add a prototype in a header file that you include, or, if the function isn't actually used by other .c files, make it static.

What is the interval between timer interrupts?

     Timer interrupts occur TIMER_FREQ times per second.  You can adjust this value by editing devices/timer.h.  The default is 100 Hz.

     We don't recommend changing this value, because any changes are likely to cause many of the tests to fail.

How long is a time slice?

     There are TIME_SLICE ticks per time slice.  This macro is declared in threads/thread.c.  The default is 4 ticks.

     We don't recommend changing this value, because any changes are likely to cause many of the tests to fail.

How do I run the tests?

     See Testing.

Why do I get a test failure in pass?

     You are probably looking at a backtrace that looks something like this:

          0xc0108810: debug_panic (lib/kernel/debug.c:32)
          0xc010a99f: pass (tests/threads/tests.c:93)
          0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33)
          0xc010a8cf: run_test (tests/threads/tests.c:51)
          0xc0100452: run_task (threads/init.c:283)
          0xc0100536: run_actions (threads/init.c:333)
          0xc01000bb: main (threads/init.c:137)

     This is just confusing output from the backtrace program.  It does not actually mean that pass called debug_panic.  In fact, fail called debug_panic (via the PANIC macro).  GCC knows that debug_panic does not return, because it is declared NO_RETURN (see Function and Parameter Attributes), so it doesn't include any code in fail to take control when debug_panic returns.  This means that the return address on the stack looks like it is at the beginning of the function that happens to follow fail in memory, which in this case happens to be pass.

     See Backtraces, for more information.

How do interrupts get re-enabled in the new thread following schedule?

     Every path into schedule disables interrupts.  They eventually get re-enabled by the next thread to be scheduled.  Consider the possibilities: the new thread is running in switch_thread (but see below), which is called by schedule, which is called by one of a few possible functions:

       * thread_exit, but we'll never switch back into such a thread, so it's uninteresting.

       * thread_yield, which immediately restores the interrupt level upon return from schedule.

       * thread_block, which is called from multiple places:

            - sema_down, which restores the interrupt level before returning.

            - idle, which enables interrupts with an explicit assembly STI instruction.

            - wait in devices/intq.c, whose callers are responsible for re-enabling interrupts.

     There is a special case when a newly created thread runs for the first time.  Such a thread calls intr_enable as the first action in kernel_thread, which is at the bottom of the call stack for every kernel thread but the first.

What should I expect from the Task 1 code-review?

     The code-review for this task will be conducted with each group in-person. Our Task 1 code-review will cover four main areas: functional correctness, efficiency, design quality and general coding style.

       * For functional correctness, we will be looking to see if your implementation of priority scheduling strictly obeys the rule that "the highest priority ready thread will always be running" and that all cases of priority inversion are being correctly handled by your system for priority donations. We will also be checking if your updated code for locks is free of any race conditions, paying specific attention to the lock_acquire and lock_release functions, as well as the interplay between them.

       * For efficiency, we will be looking at the complexity characteristics of your modified code for semaphores, as well the steps you have taken to minimise the time spent inside your timer interrupt handler.

       * For design quality, we will be looking at the stability and robustness of any changes you have made to the core PintOS kernel (e.g. thread_block, thread_unblock and thread_yield) and the accuracy of the priority updates in your BSD scheduler.

       * For general coding style, we will be paying attention to all of the usual elements of good style that you should be used to from last year (e.g. consistent code layout, appropriate use of comments, avoiding magic numbers, etc.) as well as your use of git (e.g. commit frequency and commit message quality). In this task, we will be paying particular attention to the readability of your fixed-point mathematics abstraction within your BSD scheduler.

Priority Scheduling FAQ
-----------------------

Doesn't priority scheduling lead to starvation?

     Yes, strict priority scheduling can lead to starvation because a thread will not run if any higher-priority thread is runnable. The advanced scheduler introduces a mechanism for dynamically changing thread priorities.

     Strict priority scheduling is valuable in real-time systems because it offers the programmer more control over which jobs get processing time.  High priorities are generally reserved for time-critical tasks. It's not ``fair,'' but it addresses other concerns not applicable to a general-purpose operating system.

What thread should run after a lock has been released?

     When a lock is released, the highest priority thread waiting for that lock should be unblocked and put on the list of ready threads. The scheduler should then run the highest priority thread on the ready list.

If the highest-priority thread yields, does it continue running?

     Yes.  If there is a single highest-priority thread, it continues running until it blocks or finishes, even if it calls thread_yield. If multiple threads have the same highest priority, thread_yield should switch among them in ``round robin'' order.

What happens to the priority of a donating thread?

     Priority donation only changes the priority of the donee thread.  The donor thread's priority is unchanged. Priority donation is not additive: if thread A (with priority 5) donates to thread B (with priority 3), then B's new priority is 5, not 8.

Can a thread's priority change while it is on the ready queue?

     Yes.  Consider a ready, low-priority thread L that holds a lock. High-priority thread H attempts to acquire the lock and blocks, thereby donating its priority to ready thread L.

Can a thread's priority change while it is blocked?

     Yes.  While a thread that has acquired lock L is blocked for any reason, its priority can increase by priority donation if a higher-priority thread attempts to acquire L.  This case is checked by the priority-donate-sema test.

Can a thread added to the ready list preempt the processor?

     Yes.  If a thread added to the ready list has higher priority than the running thread, the correct behaviour is to immediately yield the processor.  It is not acceptable to wait for the next timer interrupt. The highest priority thread should run as soon as it is runnable, preempting whatever thread is currently running.

How does thread_set_priority affect a thread receiving donations?

     It sets the thread's base priority.  The thread's effective priority becomes the higher of the newly set priority or the highest donated priority.  When the donations are released, the thread's priority becomes the one set through the function call.  This behaviour is checked by the priority-donate-lower test.

Doubled test names in output make them fail.

     Suppose you are seeing output in which some test names are doubled, like this:

          (alarm-priority) begin
          (alarm-priority) (alarm-priority) Thread priority 30 woke up.
          Thread priority 29 woke up.
          (alarm-priority) Thread priority 28 woke up.

     What is happening is that output from two threads is being interleaved.  That is, one thread is printing "(alarm-priority) Thread priority 29 woke up.\n" and another thread is printing "(alarm-priority) Thread priority 30 woke up.\n", but the first thread is being preempted by the second in the middle of its output.

     This problem indicates a bug in your priority scheduler.  After all, a thread with priority 29 should not be able to run while a thread with priority 30 has work to do.

     Normally, the implementation of the printf() function in the PintOS kernel attempts to prevent such interleaved output by acquiring a console lock during the duration of the printf call and releasing it afterwards.  However, the output of the test name, e.g., (alarm-priority), and the message following it is output using two calls to printf, resulting in the console lock being acquired and released twice.

Advanced Scheduler FAQ
----------------------

How does priority donation interact with the advanced scheduler?

     It doesn't have to.  We won't test priority donation and the advanced scheduler at the same time.

Can I use one queue instead of 64 queues?

     Yes.  In general, your implementation may differ from the description, as long as its behaviour is the same.

Some scheduler tests fail and I don't understand why.  Help!

     If your implementation mysteriously fails some of the advanced scheduler tests, try the following:

       * Read the source files for the tests that you're failing, to make sure that you understand what's going on.  Each one has a comment at the top that explains its purpose and expected results.

       * Double-check your fixed-point arithmetic routines and your use of them in the scheduler routines.

       * Consider how much work your implementation does in the timer interrupt.  If the timer interrupt handler takes too long, then it will take away most of a timer tick from the thread that the timer interrupt preempted.  When it returns control to that thread, it therefore won't get to do much work before the next timer interrupt arrives.  That thread will therefore get blamed for a lot more CPU time than it actually got a chance to use.  This raises the interrupted thread's recent CPU count, thereby lowering its priority. It can cause scheduling decisions to change.  It also raises the load average.