THE VISOPSYS MULTITASKER AND SCHEDULER
OVERVIEW
Visopsys is a multitasking operating system kernel. In lay terms this means
that the kernel's "scheduler" -- a small piece of independent code inside the
kernel -- parcels out small packets of time to all of the running programs in very rapid
succession. One such running program is the operating system kernel itself.
Since a single garden- variety microprocessor (such as x86 chips from AMD, Cyrix, or
Intel) can only do one thing at a time, the illusion of multiple processes working
simultaneously is achieved through this rapid switching between tasks. This is
called "task switching" or "context switching". If the
multitasker is doing its job properly, and the work load is not too great, the user should
never perceive that these switches are even occurring.
What follows is a more technical description of the method by which Visopsys'
scheduler performs these context switches.
Visopsys' scheduler combines a number of common ideas into a cohesive algorithm.
Its major features include:
- Pre-emptive
- Arbitrary number of priority queues
- Fair scheduling algorithm, except for the highest- and lowest- priority queues
- Real- time scheduling in the highest- priority queue
- Background scheduling in the lowest- priority queue
Following is a description of the algorithm by which Visopsys' scheduler
determines task execution order.
There will be two "special" queues in the multitasker. The first
(highest- priority) queue will be the "real time" queue. When there are
any processes running and ready at this priority level, they will be serviced to the
exclusion of all processes from other queues. Not even the kernel process will reside in
this queue.
The last (lowest- priority) queue will be the "background" queue.
Processes in this queue will only receive processor time when there are no ready processes
in any other queue. Unlike all of the "normal" or "middle" queues, it
will be entirely possible for processes in this background queue to starve.
Because of the existence of these two special- case queues, there must be a
minimum of 3 priority queues in the Visopsys multitasker.
The number of priority queues will be flexibly based on a configuration macro in
the multitasker's header file, and other than the minor restriction outlined above, is
arbitrary. Increasing the number of priority queues introduces no extra overhead
into the kernel (i.e. there really aren't separate queues). However, regardless of
the number of queues, the "special" queues mentioned above will always exhibit
their distinct behaviors.
Thus, using these multiple priority queues, the Administrator can exercise a very
fine-grained control over the performance of the various processes in the system.
Amongst all of the processes in the "normal" priority queues, there will
be a fair approach to scheduling. This fair algorithm utilizes a weighting scheme.
When the scheduler gains control of the processor, each waiting task's weight is
calculated. In the general case, the task with the highest weight "wins"
and is granted the next timeslice.
Among the variables which contribute to a process' weight will be the following:
priority, waiting time, and "shortness". Shortness will be implemented
later (shortest job first), so for now we will concentrate on priority and waiting time.
The formula will look like this:
weight = (task priority * priority ratio) + waiting time
[ 0 is the highest possible priority value. In the calculation above,
"task priority" is actually the inverse of the task's real priority value.
It is calculated as: the lowest possible priority value minus the task's priority
value. So, for example, if the range of possible priority values was 0 (highest)
through 7 (lowest), a highest- priority task would be: 7 - 0 = 7. ]
The task's priority will be multiplied by the "priority ratio".
The priority ratio determines the importance of priority vs. waiting time in the scheduler
queues. A priority ratio of zero, for example, would give higher- priority processes
no advantage over lower- priority ones, and waiting time alone would determine execution
order. By contrast, a very high ratio would ensure that lower- priority tasks must
wait a very long time before usurping the timeslice of a higher- priority task.
To this value will be added the current waiting time. The waiting time of
each task in the queue starts at zero. Each time a task is passed over for execution
by the scheduler, its waiting time value is increased by one. Whenever a task is
selected to run by the scheduler, its waiting time value is subsequently reset to zero.
After performing this simple calculation for each waiting task, the scheduler can
select the "winner" by running the task with the highest weight.
For example, if we have 4 possible priority levels, the priority ratio is set to
3, and we have two tasks waiting as follows:
Task #1: priority=0, waiting time=7
Task #2: priority=2, waiting time=12
then
task1Weight = ((4 - 0) * 3) + 7 = 19
<- winner
task2Weight = ((4 - 2) * 3) + 12 = 18
Thus, even though task 2 has been waiting considerably longer, task 1's higher
priority wins. However in a slightly different scenario -- using the same constants
-- if we had:
Task 1: priority=0, waiting time=7
Task 2: priority=2, waiting time=14
then
task1Weight = ((4 - 0) * 3) + 7 = 19
task2Weight = ((4 - 2) * 3) + 14 = 20 <- winner
In this case, task 2 gets to run since it has been waiting long enough to overcome
task 1's higher priority. This possibility helps to ensure that no processes will starve.
A tie between the highest-weighted tasks is resolved by round- robin queue order.
|