-@node Multilevel Feedback Scheduling, , , Project 1--Threads
-@section Multilevel Feedback Scheduling
+@node Multilevel Feedback Scheduling, Coding Standards, References, Top
+@appendix Multilevel Feedback Scheduling
This section gives a brief overview of the behavior of the Solaris 2.6
Time-Sharing (TS) scheduler, an example of a Multilevel Feedback Queue
lower priority queues. Processes at the same priority are usually
scheduled in a round-robin fashion.
-Such schedulers tend to be preemptible in order to support interactive
+Such schedulers tend to be preemptible to support interactive
processes. That is, a higher priority process is immediately
scheduled if a lower priority process is running on the CPU.
@end menu
@node Scheduling in Solaris
-@subsection Scheduling in Solaris
+@section Scheduling in Solaris
The Solaris operating system is based on Unix System V Release 4
(SVR4). Scheduling in Solaris, as in all SVR4-based schedulers, is
fifth column.
@node Class Independent Functionality
-@subsection Class Independent Functionality
+@section Class Independent Functionality
The class independent routines arbitrate across the scheduling
classes. This involves three basic responsibilities.
@end itemize
@node Time-Sharing Scheduling Class
-@subsection Time-Sharing Scheduling Class
+@section Time-Sharing Scheduling Class
The time-sharing scheduler in Solaris is an example of a multi-level
feedback queue scheduler. A job begins at priority 29. Compute-bound
time-slice before a starvation interval expires.
@node Dispatch Table
-@subsection Dispatch Table
+@section Dispatch Table
The durations of the time-slices, the changes in priorities, and the
starvation interval are specified in a user-tunable dispatch table.
increased to 50 or above when the starvation timer expires.
@node Implementation
-@subsection Implementation
+@section Implementation
For each job in the TS class, the following data structure is
maintained (we've removed a few of the fields for simplicity):
The @code{kthread_t} structure tracks the necessary information to
context-switch to and from this process. This structure is kept
-separate from the time-sharing class in order to separate the
+separate from the time-sharing class to separate the
mechanisms of the dispatcher from the policies of the scheduler.
There are seven interesting routines in the TS class:
@end table
@node Fairness
-@subsection Fairness
+@section Fairness
The Solaris time-sharing scheduler approximates fair allocations by
decreasing the priority of a job the more that it is scheduled.
the coarse job runs more frequently, it drops in priority at a faster
rate than the other two jobs.
+@ifnottex
@image{mlfqs1}
+@end ifnottex
+@iftex
+@image{mlfqs1, 3in}
+@end iftex
The impact of this policy on the relative execution times of the three
applications is shown in the next graph below. Because the coarse
the other applications, even though all three jobs require the same
amount of time in a dedicated environment.
+@ifnottex
@image{mlfqs2}
+@end ifnottex
+@iftex
+@image{mlfqs2, 3in}
+@end iftex
@node Project Requirements
-@subsection Project Requirements
+@section Project Requirements
For your project, you need to implement code that is similar in
functionality to the Solaris TS scheduler, but your code does not have