Linux_Scheduling

Question 1

Prior to kernel version 2.5, the Linux kernel ran a variation of the traditional ….?

Answer 1

UNIX scheduling algorithm.

Question 2

Two problems with the traditional UNIX scheduler are…?

Answer 2

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.

Question 3

With Version 2.5, the scheduler was overhauled, and the kernel now provides a scheduling algorithm that runs in…?

Answer 3

constant time—known as O(1)—regardless of the number of tasks on the system.

Question 4

The newer scheduler also provides increased support for..?

Answer 4

SMP, including processor affinity and load balancing, as well as providing fairness and support for interactive tasks.

Question 5

The Linux scheduler is a pre-emptive, priority-based algorithm with two separate priority ranges:

Answer 5

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.

Question 6

Unlike schedulers for many other systems, including Solaris and Windows XP, Linux assigns…?

Answer 6

higher-priority tasks longer time quanta and lower-priority tasks shorter time quanta. The relationship between priorities and time-slice length.

Question 7

A runnable task is considered eligible for execution on the CPU as long as it has…?

Answer 7

time remaining in its time slice.

Question 8

When a task has exhausted its time slice, it is considered…?

Answer 8

expired and is not eligible for execution again until all other tasks have also exhausted their time quanta.

Question 9

The kernel maintains a list of all runnable tasks in a …?

Answer 9

run queue data structure.

Question 10

Because of its support for SMP, each processor maintains its own run…?

Answer 10

queue and schedules itself independently.

Question 11

Each run queue contains two priority arrays…?

Answer 11

active and expired.

Question 12

The active array contains all tasks with

Answer 12

time remaining in their time slices, and the expired array contains all expired tasks.

Question 13

Each of these priority arrays contains a list of tasks indexed according to…?

Answer 13

priority.

Question 14

The scheduler chooses the task with the…?

Answer 14

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

Question 15

all tasks have exhausted their time slices (that is, the active array is empty), the…?

Answer 15

two priority arrays are exchanged; the expired arrya becomes the active array, and vice versa.

Question 16

Linux implements real-time scheduling as defined by…?

Answer 16

POSIX.1b, which is described in Section 5.4.2.

Question 17

Real-time tasks are assigned…?

Answer 17

static proprieties.

Question 18

All other tasks have dynamic priorities that are based on their…?

Answer 18

nice values plus or minus the value 5.

Question 19

The interactivity of a task determines whether the value 5 will be…?

Answer 19

added to or subtracted from the nice value.

Question 20

A task’s interactivity is determined by how long it has been…?

Answer 20

been sleeping while waiting for I/O.

Question 21

Tasks that are more interactive typically have longer sleep times and therefore are more likely to have …?

Answer 21

adjustments closer to −5, as the scheduler favours interactive tasks.

(The result of such adjustments will be higher priorities for these tasks.)

Question 22

Conversely, tasks with shorter sleep times are often more CPU-bound and thus will have…?

Answer 22

their priorities lowered.

Question 23

A task’s dynamic priority is recalculated when the task has exhausted its…?

Answer 23

time quantum and is to be moved to the expired array. Thus, when the two arrays are exchanged, all tasks in the new active array have been assigned new priorities and corresponding time slices.