Flashcards in Linux_Scheduling Deck (23):
Prior to kernel version 2.5, the Linux kernel ran a variation of the traditional ....?
UNIX scheduling algorithm.
Two problems with the traditional UNIX scheduler are...?
that it does not provide adequate support for SMP systems and that it does not scale well as the number of tasks on the system grows.
With Version 2.5, the scheduler was overhauled, and the kernel now provides a scheduling algorithm that runs in...?
constant time—known as O(1)—regardless of the number of tasks on the system.
The newer scheduler also provides increased support for..?
SMP, including processor affinity and load balancing, as well as providing fairness and support for interactive tasks.
The Linux scheduler is a pre-emptive, priority-based algorithm with two separate priority ranges:
a real-time range from 0 to 99 and a nice value ranging from 100 to 140. These two ranges map into a global priority scheme wherein numerically lower values indicate higher priorities.
Unlike schedulers for many other systems, including Solaris and Windows XP, Linux assigns...?
higher-priority tasks longer time quanta and lower-priority tasks shorter time quanta. The relationship between priorities and time-slice length.
A runnable task is considered eligible for execution on the CPU as long as it has...?
time remaining in its time slice.
When a task has exhausted its time slice, it is considered...?
expired and is not eligible for execution again until all other tasks have also exhausted their time quanta.
The kernel maintains a list of all runnable tasks in a ...?
run queue data structure.
Because of its support for SMP, each processor maintains its own run...?
queue and schedules itself independently.
Each run queue contains two priority arrays...?
active and expired.
The active array contains all tasks with
time remaining in their time slices, and the expired array contains all expired tasks.
Each of these priority arrays contains a list of tasks indexed according to...?
The scheduler chooses the task with the...?
highest priority from the active array for execution on the CPU.
(On multiprocessor machines, this means that each processor is scheduling the highest-priority task from its own run queue structure. )
all tasks have exhausted their time slices (that is, the active array is empty), the...?
two priority arrays are exchanged; the expired arrya becomes the active array, and vice versa.
Linux implements real-time scheduling as defined by...?
POSIX.1b, which is described in Section 5.4.2.
Real-time tasks are assigned...?
All other tasks have dynamic priorities that are based on their...?
nice values plus or minus the value 5.
The interactivity of a task determines whether the value 5 will be...?
added to or subtracted from the nice value.
A task’s interactivity is determined by how long it has been...?
been sleeping while waiting for I/O.
Tasks that are more interactive typically have longer sleep times and therefore are more likely to have ...?
adjustments closer to −5, as the scheduler favours interactive tasks.
(The result of such adjustments will be higher priorities for these tasks.)
Conversely, tasks with shorter sleep times are often more CPU-bound and thus will have...?
their priorities lowered.