Project 1: Threads
******************

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. Additionally, you will use at least part of this increased functionality in future assignments.

You will be working in primarily in the threads directory for this assignment, with some work in the devices directory on the side.  Compilation should be done in the threads directory.

Before you read the description of this project, you should read all of the following sections: Introduction, Coding Standards, Project Documentation, Debugging Tools, and Development Tools.  You should at least skim the material in Threads Tour.  To complete this project you will also need to read Multilevel Feedback Scheduling.

Understanding Threads
=====================

The first step is to read and understand the initial thread system. Pintos, by default, implements thread creation and thread completion, a simple scheduler to switch between threads, and synchronization primitives (semaphores, locks, and condition variables).

However, there's a lot of magic going on in some of this code, so if you haven't already compiled and run the base system, as described in the introduction (see Introduction), you should do so now.  You can read through parts of the source code by hand to see what's going on.  If you like, you can add calls to printf almost anywhere, then recompile and run to see what happens and in what order.  You can also run the kernel in a debugger and set breakpoints at interesting spots, single-step through code and examine data, and so on.  See i386-elf-gdb, for more information.

When a thread is created, you are creating a new context to be scheduled. You provide a function to be run in this context as an argument to thread_create. The first time the thread is scheduled and runs, it will start from the beginning of that function and execute it in the context. When that function returns, that thread completes. Each thread, therefore, acts like a mini-program running inside Pintos, with the function passed to thread_create acting like main.

At any given time, Pintos is running exactly one thread, with the others switched out.  The scheduler decides which thread to run next when it needs to switch between them.  (If no thread is ready to run at any given time, then the special ``idle'' thread runs.)  The synchronization primitives are used to force context switches when one thread needs to wait for another thread to do something.

The exact mechanics of a context switch are pretty gruesome and have been provided for you in threads/switch.S (this is 80X86 assembly; don't worry about understanding it).  It involves saving the state of the currently running thread and restoring the state of the thread we're switching to.

Using the gdb debugger, slowly trace through a context switch to see what happens (see i386-elf-gdb).  You can set a breakpoint on the schedule function to start out, and then single-step from there. (gdb might tell you that schedule doesn't exist, which is arguably a gdb bug. You can work around this by setting the breakpoint by filename and line number, e.g. break thread.c:LN where LN is the line number of the first declaration in schedule.)  Be sure to keep track of each thread's address and state, and what procedures are on the call stack for each thread. You will notice that when one thread calls switch_threads, another thread starts running, and the first thing the new thread does is to return from switch_threads.  We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand why the switch_threads that gets called is different from the switch_threads that returns.

Warning: In Pintos, each thread is assigned a small, fixed-size execution stack just under 4 kB in size.  The kernel does try to detect stack overflow, but it cannot always succeed.  You may cause bizarre problems, such as mysterious kernel panics, if you declare large data structures as non-static local variables, e.g. int buf[1000];.  Alternatives to stack allocation include the page allocator in threads/palloc.c and the block allocator in threads/malloc.c.  Note that the page allocator doles out 4 kB chunks and that malloc has a 2 kB block size limit.  If you need larger chunks, consider using a linked structure instead.

Code
====

Here is a brief overview of the files in the threads directory.  You will not need to modify most of this code, but the hope is that presenting this overview will give you a start on what code to look at.

loader.S
loader.h
     The kernel loader.  Assembles to 512 bytes of code and data that the PC BIOS loads into memory and which in turn loads the kernel into memory, does basic processor initialization, and jumps to the beginning of the kernel.  You should not need to look at this code or modify it.

kernel.lds.S
     The linker script used to link the kernel.  Sets the load address of the kernel and arranges for start.S to be at the very beginning of the kernel image.  Again, you should not need to look at this code or modify it, but it's here in case you're curious.

start.S
     Jumps to main.

init.c
init.h
     Kernel initialization, including main, the kernel's ``main program.''  You should look over main at least to see what gets initialized.

thread.c
thread.h
     Basic thread support.  Much of your work will take place in these files.  thread.h defines thread, which you will modify in the first three projects.

switch.S
switch.h
     Assembly language routine for switching threads.  Already discussed above.

palloc.c
palloc.h
     Page allocator, which hands out system memory in multiples of 4 kB pages.

malloc.c
malloc.h
     A very simple implementation of malloc and free for the kernel.

interrupt.c
interrupt.h
     Basic interrupt handling and functions for turning interrupts on and off.

intr-stubs.pl
intr-stubs.h
     A Perl program that outputs assembly for low-level interrupt handling.

synch.c
synch.h
     Basic synchronization primitives: semaphores, locks, and condition variables.  You will need to use these for synchronization through all four projects.

test.c
test.h
     Test code.  For project 1, you will replace this file with your test cases.

io.h
     Functions for I/O port access.  This is mostly used by source code in the devices directory that you won't have to touch.

mmu.h
     Functions and macros related to memory management, including page directories and page tables.  This will be more important to you in project 3.  For now, you can ignore it.

devices code
------------

The basic threaded kernel also includes these files in the devices directory:

timer.c
timer.h
     System timer that ticks, by default, 100 times per second.  You will modify this code in Problem 1-1.

vga.c
vga.h
     VGA display driver.  Responsible for writing text to the screen. You should have no need to look at this code.  printf will call into the VGA display driver for you, so there's little reason to call this code yourself.

serial.c
serial.h
     Serial port driver.  Again, printf calls this code for you, so you don't need to do so yourself.  Feel free to look through it if you're curious.

disk.c
disk.h
     Supports reading and writing sectors on up to 4 IDE disks.  This won't actually be used until project 2.

intq.c
intq.h
     Interrupt queue, for managing a circular queue that both kernel threads and interrupt handlers want to access.  Used by the keyboard and serial drivers.

lib files
---------

Finally, lib and lib/kernel contain useful library routines.  (lib/user will be used by user programs, starting in project 2, but it is not part of the kernel.)  Here's a few more details:

ctype.h
inttypes.h
limits.h
stdarg.h
stdbool.h
stddef.h
stdint.h
stdio.c
stdio.h
stdlib.c
stdlib.h
string.c
string.h
     Implementation of the standard C library.  See C99, for information on a few recently introduced pieces of the C library that you might not have encountered before.  See Unsafe String Functions, for information on what's been intentionally left out for safety.

debug.c
debug.h
     Functions and macros to aid debugging.  See Debugging Tools, for more information.

random.c
random.h
     Pseudo-random number generator.

round.h
     Macros for rounding.

syscall-nr.h
     System call numbers.  Not used until project 2.

kernel/list.c
kernel/list.h
     Doubly linked list implementation.  Used all over the Pintos code, and you'll probably want to use it a few places yourself in project 1.

kernel/bitmap.c
kernel/bitmap.h
     Bitmap implementation.  You can use this in your code if you like, but you probably won't have any need for project 1.

kernel/hash.c
kernel/hash.h
     Hash table implementation.  Likely to come in handy for project 3.

kernel/console.c
kernel/console.h
     Implements printf and a few other functions.

Debugging versus Testing
========================

When you're debugging code, it's useful to be able to be able to run a program twice and have it do exactly the same thing.  On second and later runs, you can make new observations without having to discard or verify your old observations.  This property is called ``reproducibility.''  The simulator we use, Bochs, can be set up for reproducibility, and that's the way that pintos invokes it by default.

Of course, a simulation can only be reproducible from one run to the next if its input is the same each time.  For simulating an entire computer, as we do, this means that every part of the computer must be the same.  For example, you must use the same disks, the same version of Bochs, and you must not hit any keys on the keyboard (because you could not be sure to hit them at exactly the same point each time) during the runs.

While reproducibility is useful for debugging, it is a problem for testing thread synchronization, an important part of this project.  In particular, when Bochs is set up for reproducibility, timer interrupts will come at perfectly reproducible points, and therefore so will thread switches.  That means that running the same test several times doesn't give you any greater confidence in your code's correctness than does running it only once.

So, to make your code easier to test, we've added a feature, called ``jitter,'' to Bochs, that makes timer interrupts come at random intervals, but in a perfectly predictable way.  In particular, if you invoke pintos with the option -j SEED, timer interrupts will come at irregularly spaced intervals.  Within a single SEED value, execution will still be reproducible, but timer behavior will change as SEED is varied.  Thus, for the highest degree of confidence you should test your code with many seed values.

On the other hand, when Bochs runs in reproducible mode, timings are not realistic, meaning that a ``one-second'' delay may be much shorter or even much longer than one second.  You can invoke pintos with a different option, -r, to make it set up Bochs for realistic timings, in which a one-second delay should take approximately one second of real time.  Simulation in real-time mode is not reproducible, and options -j and -r are mutually exclusive.

Tips
====

There should be no busy-waiting in any of your solutions to this assignment.  Furthermore, resist the temptation to directly disable interrupts in your solution by calling intr_disable or intr_set_level, although you may find doing so to be useful while debugging.  Instead, use semaphores, locks and condition variables to solve synchronization problems.  Read the tour section on synchronization (see Synchronization) or the comments in threads/synch.h if you're unsure what synchronization primitives may be used in what situations.

Given some designs of some problems, there may be one or two instances in which it is appropriate to directly change the interrupt levels instead of relying on the given synchroniztion primitives.  This must be justified in your DESIGNDOC file.  If you're not sure you're justified, ask!

While all parts of this assignment are required if you intend to earn full credit on this project, keep in mind that Problem 1-2 (Join) will be needed for future assignments, so you'll want to get this one right.  We don't give out solutions, so you're stuck with your Join code for the whole quarter.  Problem 1-1 (Alarm Clock) could be very handy, but not strictly required in the future.  The upshot of all this is that you should focus heavily on making sure that your implementation of thread_join works correctly, since if it's broken, you will need to fix it for future assignments.  The other parts can be turned off in the future if you find you can't make them work quite right.

Also keep in mind that Problem 1-4 (the MLFQS) builds on the features you implement in Problem 1-3, so to avoid unnecessary code duplication, it would be a good idea to divide up the work among your team members such that you have Problem 1-3 fully working before you begin to tackle Problem 1-4.

Problem 1-1: Alarm Clock
========================

Improve the implementation of the timer device defined in devices/timer.c by reimplementing timer_sleep. Threads call timer_sleep(X) to suspend execution until time has advanced by at least X timer ticks.  This is useful for threads that operate in real-time, for example, for blinking the cursor once per second.  There is no requirement that threads start running immediately after waking up; just put them on the ready queue after they have waited for approximately the right amount of time.

A working implementation of this function is provided.  However, the version provided is poor, because it ``busy waits,'' that is, it spins in a tight loop checking the current time until the current time has advanced far enough.  This is undesirable because it wastes time that could potentially be used more profitably by another thread.  Your solution should not busy wait.

The argument to timer_sleep is expressed in timer ticks, not in milliseconds or any another unit.  There are TIMER_FREQ timer ticks per second, where TIMER_FREQ is a macro defined in devices/timer.h.

Separate functions timer_msleep, timer_usleep, and timer_nsleep do exist for sleeping a specific number of milliseconds, microseconds, or nanoseconds, respectively, but these will call timer_sleep automatically when necessary.  You do not need to modify them.

If your delays seem too short or too long, reread the explanation of the -r option to pintos (see Debugging versus Testing).

Problem 1-2: Join
=================

Implement thread_join(tid_t) in threads/thread.c.  There is already a prototype for it in threads/thread.h, which you should not change.  This function causes the currently running thread to block until the thread whose thread id is passed as an argument exits.  If A is the running thread and B is the argument, then we say that ``A joins B.''

Incidentally, we don't use struct thread * as thread_join's parameter type because a thread pointer is not unique over time.  That is, when a thread dies, its memory may be, whether immediately or much later, reused for another thread.  If thread A over time had two children B and C that were stored at the same address, then thread_join(B) and thread_join(C) would be ambiguous.  Introducing a thread id or tid, represented by type tid_t, that is intentionally unique over time solves the problem.  The provided code uses an int for tid_t, but you may decide you prefer to use some other type.

The model for thread_join is the wait system call in Unix-like systems.  (Try reading the manpages.)  That system call can only be used by a parent process to wait for a child's death.  You should implement thread_join to have the same restriction. That is, a thread may only join its immediate children.

A thread need not ever be joined.  Your solution should properly free all of a thread's resources, including its thread, whether it is ever joined or not, and regardless of whether the child exits before or after its parent.  That is, a thread should be freed exactly once in all cases.

Joining a given thread is idempotent.  That is, joining a thread T multiple times is equivalent to joining it once, because T has already exited at the time of the later joins.  Thus, joins on T after the first should return immediately.

Calling thread_join on an thread that is not the caller's child should cause the caller to return immediately.

Consider all the ways a join can occur: nested joins (A joins B, then B joins C), multiple joins (A joins B, then A joins C), and so on.  Does your join work if thread_join is called on a thread that has not yet been scheduled for the first time?  You should handle all of these cases. Write test code that demonstrates the cases your join works for. Don't overdo the output volume, please!

Be careful to program this function correctly.  You will need its functionality for project 2.

Once you've implemented thread_join, define THREAD_JOIN_IMPLEMENTED in constants.h. See Conditional Compilation, for more information.

Problem 1-3: Priority Scheduling
================================

Implement priority scheduling in Pintos.  Priority scheduling is a key building block for real-time systems.  Implement functions thread_set_priority to set the priority of the running thread and thread_get_priority to get the running thread's priority. (This API only allows a thread to examine and modify its own priority.)  There are already prototypes for these functions in threads/thread.h, which you should not change.

Thread priority ranges from PRI_MIN (0) to PRI_MAX (59). The initial thread priority is passed as an argument to thread_create.  If there's no reason to choose another priority, use PRI_DEFAULT (29).  The PRI_ macros are defined in threads/thread.h, and you should not change their values.

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 woken up first.  A thread may set its priority at any time.

One issue with priority scheduling is ``priority inversion'': if a high priority thread needs to wait for a low priority thread (for instance, for a lock held by a low priority thread, or in thread_join for a thread to complete), and a middle priority thread is on the ready list, then the high priority thread will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is to have the waiting thread ``donate'' its priority to the low priority thread while it is holding the lock, then recall the donation once it has acquired the lock. Implement this fix.

You will need to account for all different orders that priority donation and inversion can occur.  Be sure to handle multiple donations, in which multiple priorities are donated to a thread.  You must also handle nested donation: given high, medium, and low priority threads H, M, and L, respectively, 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.

You only need to implement priority donation when a thread is waiting for a lock held by a lower-priority thread.  You do not need to implement this fix for semaphores, condition variables, or joins, although you are welcome to do so.  However, you do need to implement priority scheduling in all cases.

You may assume a static priority for priority donation, that is, it is not necessary to ``re-donate'' a thread's priority if it changes (although you are free to do so).

Problem 1-4: Advanced Scheduler
===============================

Implement Solaris's multilevel feedback queue scheduler (MLFQS) to reduce the average response time for running jobs on your system. See Multilevel Feedback Scheduling, for a detailed description of the MLFQS requirements.

Demonstrate that your scheduling algorithm reduces response time relative to the original Pintos scheduling algorithm (round robin) for at least one workload of your own design (i.e. in addition to the provided test).

You must write your code so that we can turn the MLFQS on and off at compile time.  By default, it must be off, but we must be able to turn it on by inserting the line #define MLFQS 1 in constants.h.  See Conditional Compilation, for details.

FAQ
===

 1. I am adding a new .h or .c file.  How do I fix the Makefiles?

     To add a .c file, edit the top-level Makefile.build. You'll want to add your file to variable DIR_SRC, where DIR is the directory where you added the file.  For this project, that means you should add it to threads_SRC, or possibly devices_SRC if you put in the devices directory.  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, the modified version should be automatically copied to threads/build/Makefile when you re-run make.  The opposite is not true, so any changes will be lost the next time you run make clean from the threads directory.  Therefore, you should prefer to edit Makefile.build (unless your changes are meant to be truly temporary).

     There is no need to edit the Makefiles to add a .h file.

 2. How do I write my test cases?

     Test cases should be replacements for the existing test.c file.  Put them in a threads/testcases directory. See TESTCASE, for more information.

 3. Why can't I disable interrupts?

     Turning off interrupts should only be done for short amounts of time, or else you end up losing important things such as disk or input events.  Turning off interrupts also increases the interrupt handling latency, which can make a machine feel sluggish if taken too far. Therefore, in general, setting the interrupt level should be used sparingly.  Also, any synchronization problem can be easily solved by turning interrupts off, since while interrupts are off, there is no concurrency, so there's no possibility for race condition.

     To make sure you understand concurrency well, we are discouraging you from taking this shortcut at all in your solution.  If you are unable to solve a particular synchronization problem with semaphores, locks, or conditions, or think that they are inadequate for a particular reason, you may turn to disabling interrupts.  If you want to do this, we require in your design document a complete justification and scenario (i.e. exact sequence of events) to show why interrupt manipulation is the best solution.  If you are unsure, the TAs can help you determine if you are using interrupts too haphazardly.  We want to emphasize that there are only limited cases where this is appropriate.

     You might find devices/intq.h and its users to be an inspiration or source of rationale.

 4. Where might interrupt-level manipulation be appropriate?

     You might find it necessary in some solutions to the Alarm problem.

     You might want it at one small point for the priority scheduling problem.  Note that it is not required to use interrupts for these problems.  There are other, equally correct solutions that do not require interrupt manipulation.  However, if you do manipulate interrupts and correctly and fully document it in your design document, we will allow limited use of interrupt disabling.

 5. What does ``warning: no previous prototype for `FUNCTION'' 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.

Problem 1-1: Alarm Clock FAQ
----------------------------

 1. Why can't I use most synchronization primitives in an interrupt handler?

     As you've discovered, you cannot sleep in an external interrupt handler.  Since many lock, semaphore, and condition variable functions attempt to sleep, you won't be able to call those in timer_interrupt.  You may still use those that never sleep.

     Having said that, you need to make sure that global data does not get updated by multiple threads simultaneously executing timer_sleep.  Here are some pieces of information to think about:

      a. Interrupts are turned off while timer_interrupt runs.  This means that timer_interrupt will not be interrupted by a thread running in timer_sleep.

      b. A thread in timer_sleep, however, can be interrupted by a call to timer_interrupt, except when that thread has turned off interrupts.

      c. Examples of synchronization mechanisms have been presented in lecture. Going over these examples should help you understand when each type is useful or needed.  See Synchronization, for specific information about synchronization in Pintos.

 2. What about timer overflow due to the fact that times are defined as integers? Do I need to check for that?

     Don't worry about the possibility of timer values overflowing.  Timer values are expressed as signed 63-bit numbers, which at 100 ticks per second should be good for almost 2,924,712,087 years.

 3. The test program mostly works but reports a few out-of-order wake ups.  I think it's a problem in the test program.  What gives?

     This test is inherently full of race conditions.  On a real system it wouldn't work perfectly all the time either.  There are a few ways you can help it work more reliably:

       * Make time slices longer by increasing TIME_SLICE in timer.c to a large value, such as 100.

       * Make the timer tick more slowly by decreasing TIMER_FREQ in timer.h to its minimum value of 19.

     The former two changes are only desirable for testing problem 1-1 and possibly 1-3.  You should revert them before working on other parts of the project or turn in the project.

 4. Should p1-1.c be expected to work with the MLFQS turned on?

     No.  The MLFQS will adjust priorities, changing thread ordering.

Problem 1-2: Join FAQ
---------------------

 1. Am I correct to assume that once a thread is deleted, it is no longer accessible by the parent (i.e. the parent can't call thread_join(child))?

     A parent joining a child that has completed should be handled gracefully and should act as a no-op.

Problem 1-3: Priority Scheduling FAQ
------------------------------------

 1. Doesn't the priority scheduling lead to starvation? Or do I have to implement some sort of aging?

     It is true that strict priority scheduling can lead to starvation because thread may not run if a higher-priority thread is runnable. In this problem, don't worry about starvation or any sort of aging technique.  Problem 4 will introduce a mechanism for dynamically changing thread priorities.

     This sort of 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.

 2. After a lock has been released, does the program need to switch to the highest priority thread that needs the lock (assuming that its priority is higher than that of the current thread)?

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

 3. If a thread calls thread_yield and then it turns out that it has higher priority than any other threads, does the high-priority thread 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.

 4. If the highest priority thread is added to the ready to run list it should start execution immediately.  Is it immediate enough if I wait until next timer interrupt occurs?

     The highest priority thread should run as soon as it is runnable, preempting whatever thread is currently running.

 5. What happens to the priority of the donating thread?  Do the priorities get swapped?

     No.  Priority donation only changes the priority of the low-priority thread.  The donating thread's priority stays unchanged.  Also note that priorities aren't additive: if thread A (with priority 5) donates to thread B (with priority 3), then B's new priority is 5, not 8.

 6. Can a thread's priority be changed while it is sitting on the ready queue?

     Yes.  Consider this case: low-priority thread L currently has a lock that high-priority thread H wants.  H donates its priority to L (the lock holder).  L finishes with the lock, and then loses the CPU and is moved to the ready queue.  Now L's old priority is restored while it is in the ready queue.

 7. Can a thread's priority change while it is sitting on the queue of a semaphore?

     Yes.  Same scenario as above except L gets blocked waiting on a new lock when H restores its priority.

 8. Why is p1-3.c's FIFO test skipping some threads?  I know my scheduler is round-robin'ing them like it's supposed to.   Our output starts out okay, but toward the end it starts getting out of order.

     The usual problem is that the serial output buffer fills up.  This is causing serial_putc() to block in thread A, so that thread B is scheduled.  Thread B immediately tries to do output of its own and blocks on the serial lock (which is held by thread A).  Now that we've wasted some time in scheduling and locking, typically some characters have been drained out of the serial buffer by the interrupt handler, so thread A can continue its output. After it finishes, though, some other thread (not B) is scheduled, because thread B was already scheduled while we waited for the buffer to drain.

     There's at least one other possibility.  Context switches are being invoked by the test when it explicitly calls thread_yield. However, the time slice timer is still alive and so, every tick (by default), a thread gets switched out (caused by timer_interrupt calling intr_yield_on_return) before it gets a chance to run printf, effectively skipping it.  If we use a different jitter value, the same behavior is seen where a thread gets started and switched out completely.

     Normally you can fix these problems using the same techniques suggested on problem 1-1 (see Out of Order 1-1).

 9. What happens when a thread is added to the ready list which has higher priority than the currently running thread?

     The correct behavior is to immediately yield the processor.  Your solution must act this way.

 10. What should thread_get_priority return in a thread while its priority has been increased by a donation?

     The higher (donated) priority.

 11. Should p1-3.c be expected to work with the MLFQS turned on?

     No.  The MLFQS will adjust priorities, changing thread ordering.

 12. printf in sema_up or sema_down makes the system reboot!

     Yes.  These functions are called before printf is ready to go. You could add a global flag initialized to false and set it to true just before the first printf in main.  Then modify printf itself to return immediately if the flag isn't set.

Problem 1-4: Advanced Scheduler FAQ
-----------------------------------

 1. 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.

     You can also adjust the number of timer ticks per time slice by modifying TIME_SLICE in devices/timer.c.

 2. Do I have to modify the dispatch table?

     No, although you are allowed to. It is possible to complete this problem (i.e. demonstrate response time improvement) without doing so.

 3. When the scheduler changes the priority of a thread, how does this affect priority donation?

     Short (official) answer: Don't worry about it. Your priority donation code may assume static priority assignment.

     Longer (unofficial) opinion: If you wish to take this into account, however, your design may end up being ``cleaner.''  You have considerable freedom in what actually takes place. I believe what makes the most sense is for scheduler changes to affect the ``original'' (non-donated) priority.  This change may actually be masked by the donated priority.  Priority changes should only propagate with donations, not ``backwards'' from donees to donors.

 4. What is meant by ``static priority''?

     Once thread A has donated its priority to thread B, if thread A's priority changes (due to the scheduler) while the donation still exists, you do not have to change thread B's donated priority. However, you are free to do so.

 5. Do I have to make my dispatch table user-configurable?

     No.  Hard-coding the dispatch table values is fine.