Page 425 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes arrays, the scheduler simply swaps the pointers, so the expired arrays now become active, and
vice versa. This method ensures that low priority tasks will not starve (except when real-time
FIFO threads completely hog the CPU, which is unlikely to happen). Different priority levels are
assigned different timeslice values. Linux assigns higher quanta to higher priority processes. For
instance, tasks running at priority level 100 will receive the time quanta of 800 msec, whereas
tasks at priority level of 139 will receive 5 msec. The idea behind this scheme is to get processes
out of the kernel fast. If a process is trying to read a disk file, making it wait for a second between
read calls will slow it down enormously. It is far better to let it run immediately after each
request is completed, so that it can make the next one quickly. Similarly, if a process was blocked
waiting for keyboard input, it is clearly an interactive process, and as such should be given a
high priority as soon as it is ready in order to ensure that interactive processes get good service.

Figure 14.10: Illustration of Linux Runqueue and Priority Arrays

In this light, CPU-bound processes basically get any service that is left over when all the I/O
bound and interactive processes are blocked. Since Linux (or any other OS) does not know
apriori whether a task is I/O- or CPU-bound, it relies on continuously maintaining interactivity
heuristics. In this manner, Linux distinguishes between static and dynamic priority. The threads’
dynamic priority is continuously recalculated, so as to (1) reward interactive threads, and (2)
punish CPU-hogging threads. The maximum priority bonus is ~5, since lower priority values
correspond to higher priority received by the scheduler. The maximum priority penalty is +5.
More specifically, the scheduler maintains a sleep_ avg variable associated with each task.
Whenever a task is awaken, this variable is incremented, whenever a task is preempted or its
quantum expires, this variable is decremented by the corresponding value. This value is used
to dynamically map the task’s bonus to values from ~5 to +5. The Linux scheduler recalculates
the new priority level as a thread is moved from the active to the expired list. The scheduling
algorithm described in this section refers to the 2.6 kernel, and was first introduced in the unstable
2.5 kernel. Earlier algorithms exhibited poor performance in multiprocessor settings and did
not scale well with an increased number of tasks. Since the description presented in the above

418 LOVELY PROFESSIONAL UNIVERSITY