|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 779-780 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 779
748
CASE STUDY 1: UNIX, LINUX, AND ANDROID
CHAP. 10
Flags
CPU
Static_prio
<
>
Active
Expired
<
>
Priority 0
Array[0]
Priority 139
Priority 0
Array[1]
Priority 139
P
P
P
P
P
P
P
P
P
P
P
P
(a)
Per CPU runqueue in the
Linux O(1) scheduler
35
26
47
10
30
38
62
3
27
45
86
NIL
NIL
NIL
NIL
NIL
NIL
NIL
NIL
NIL
NIL
NIL
NIL
(b) Per CPU red-black tree in
the CFS scheduler
Figure 10-10.
Illustration of Linux runqueue data structures for (a) the Linux
O(1) scheduler, and (b) the Completely Fair Scheduler.
slow it down enormously.
It is far better to let it run immediately after each re-
quest 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.
In this light, CPU-bound processes basical-
ly 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 a priori 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’ dy-
namic priority is continuously recalculated, so as to (1) reward interactive threads,
and (2) punish CPU-hogging threads. In the O(1) scheduler, the maximum priority
bonus is
−
5, since lower-priority values correspond to higher priority received by
the scheduler. The maximum priority penalty is +5.
The scheduler maintains a
sleep
avg
variable associated with each task. Whenever a task is awakened, this
variable is incremented. Whenever a task is preempted or when its quantum ex-
pires, this variable is decremented by the corresponding value. This value is used
Page 780
SEC. 10.3
PROCESSES IN LINUX
749
to dynamically map the task’s bonus to values from
−
5 to +5. The scheduler recal-
culates the new priority level as a thread is moved from the active to the expired
list.
The O(1) scheduling algorithm refers to the scheduler made popular in the
early versions of the 2.6 kernel, and was first introduced in the unstable 2.5 kernel.
Prior 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 paragraphs indicates that a scheduling decision can be made through access
to the appropriate active list, it can be done in constant O(1) time, independent of
the number of processes in the system.
However, in spite of the desirable property
of constant-time operation, the O(1) scheduler had significant shortcomings.
Most
notably, the heuristics used to determine the interactivity of a task, and therefore its
priority level, were complex and imperfect, and resulted in poor performance for
interactive tasks.
To address this issue, Ingo Molnar, who also created the O(1) scheduler, pro-
posed a new scheduler called
Completely Fair Scheduler
or
CFS
.
CFS was
based on ideas originally developed by Con Kolivas for an earlier scheduler, and
was first integrated into the 2.6.23 release of the kernel. It is still the default sched-
uler for the non-real-time tasks.
The main idea behind CFS is to use a
red-black tree
as the runqueue data struc-
ture. Tasks are ordered in the tree based on the amount of time they spend running
on the CPU, called
vruntime
.
CFS accounts for the tasks’ running time with
nanosecond granularity.
As shown in Fig. 10-10(b), each internal node in the tree
corresponds to a task. The children to the left correspond to tasks which had less
time on the CPU, and therefore will be scheduled sooner, and the children to the
right on the node are those that have consumed more CPU time thus far.
The
leaves in the tree do not play any role in the scheduler.
The scheduling algorithm can be summarized as follows. CFS always sched-
ules the task which has had least amount of time on the CPU, typically the leftmost
node in the tree. Periodically, CFS increments the task’s
vruntime
value based on
the time it has already run, and compares this to the current leftmost node in the
tree. If the running task still has smaller
vruntime
, it will continue to run. Other-
wise, it will be inserted at the appropriate place in the red-black tree, and the CPU
will be given to task corresponding to the new leftmost node.
To account for differences in task priorities and ‘‘niceness,’’ CFS changes the
effective rate at which a task’s virtual time passes when it is running on the CPU.
For lower-priority tasks, time passes more quickly, their
vruntime
value will in-
crease more rapidly, and, depending on other tasks in the system, they will lose the
CPU and be reinserted in the tree sooner than if they had a higher priority value. In
this manner, CFS avoids using separate runqueue structures for different priority
levels.
In summary, selecting a node to run can be done in constant time, whereas
inserting a task in the runqueue is done in O(log(
N
)) time, where
N
is the number
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
