forked from markkampe/Operating-Systems-Reading
-
Notifications
You must be signed in to change notification settings - Fork 0
/
realtime.html
204 lines (204 loc) · 9.31 KB
/
realtime.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
<html>
<head>
<title>Real-Time Scheduling</title>
</head>
<body>
<center><h1>Real Time Scheduling</h1></center>
<H2>Introduction</h2>
<P>
Priority based scheduling enables us to give better service to
certain processes. In our discussion of multi-queue scheduling,
priority was adjusted based on whether a task was more interactive
or compute intensive. But most schedulers enable us to give any
process any desired priority. Isn't that good enough?
<P>
Priority scheduling is inherently a <em>best effort</em> approach.
If our task is competing with other high priority tasks, it may
not get as much time as it requires. Sometimes best effort isn't
good enough:
<UL>
<li>During reentry, the space shuttle is aerodynamically
unstable. It is not actually being kept under control
by the quick reflexes of the well-trained pilots, but
rather by guidance computers that are collecting attitude
and acceleration input and adjusting numerous spoilers
hundreds of times per second.</li>
<li>Scientific and military satellites may receive precious and
irreplaceable sensor data at extremely high speeds. If
it takes us too long to receive, process, and store one
data frame, the next data frame may be lost.</li>
<li>More mundanely, but also important, many manufacturing
processes are run by computers nowadays. An assembly line
needs to move at a particular speed, with each step being
performed at a particular time. Performing the action too
late results in a flawed or useless product.</li>
<li>Even more commonly, playing media, like video or audio,
has real time requirements. Sound must be produced at a
certain rate and frames must be displayed frequently enough
or the media becomes uncomfortable to deal with.
</UL>
<P>
There are many computer controlled applications where delays in
critical processing can have undesirable, or even disastrous consequences.
</P>
<H2>What are Real-Time Systems</h2>
<P>
A real-time system is one whose correctness depends on timing as well as functionality.
</P>
<P>
When we discussed more traditional scheduling algorithms, the metrics
we looked at were <em>turn-around time</em> (or throughput),
<em>fairness</em>, and mean <em>response time</em>. But real-time
systems have very different requirements, characterized by different metrics:
<ul>
<li> <em>timeliness</em> ... how closely does it meet its timing requirements
(e.g. ms/day of accumulated tardiness)</li>
<li> <em>predictability</em> ... how much deviation is there in delivered timeliness</li>
</ul>
And we introduce a few new concepts:
<ul>
<li> <em>feasibility</em> ... whether or not it is possible to meet the requirements
for a particular task set</li>
<LI><em>hard real-time</em>
... there are strong requirements
that specified tasks be run a specified intervals (or within a
specified response time). Failure to meet this requirement
(perhaps by as little as a fraction of a micro-second) may result
in system failure.
<LI><em>soft real-time</em> ... we may
want to provide very good (e.g. microseconds) response time, the
only consequences of missing a deadline are degraded performance
or recoverable failures.
</LI>
</UL>
<P>
It sounds like real-time scheduling is more critical and difficult than
traditional time-sharing, and in many ways it is. But real-time systems
may have a few characteristics that make scheduling easier:
</P>
<ul>
<LI>We may actually know how long each task will take to run.
This enables much more intelligent scheduling.</li>
<li><em>Starvation</em> (of low priority tasks) may be acceptable.
The space shuttle absolutely must sense attitude and acceleration and adjust
spoiler positions once per millisecond. But it probably doesn't
matter if we update the navigational display once per millisecond
or once every ten seconds. Telemetry transmission is probably
somewhere in-between.
Understanding the relative criticality of each task gives us the
freedom to intelligently shed less critical work in times of
high demand.
</li>
<li>The work-load may be relatively fixed.
Normally high utilization implies long queuing delays,
as bursty traffic creates long lines. But if the incoming
traffic rate is relatively constant, it is possible to
simultaneously achieve high utilization and good response time.
</li>
</ul>
<H2>Real-Time Scheduling Algorithms</h2>
<P>
In the simplest real-time systems, where the tasks and their execution times
are all known, there might not even be a scheduler. One task might simply
call (or yield to) the next. This model makes a great deal of sense in a
system where the tasks form a producer/consumer pipeline (e.g. MPEG
frame receipt, protocol decoding, image decompression, display).
</P>
<P>
In more complex real-time system, with a larger (but still fixed) number
of tasks that do not function in a strictly pipeline fashion, it may be
possible to do <em>static</em> scheduling.
Based on the list of tasks to be run, and the expected completion time
for each, we can define (at design or build time) a fixed schedule
that will ensure timely execution of all tasks.
</P>
<P>
But for many real-time systems, the work-load changes from moment to moment,
based on external events. These require <em>dynamic</em> scheduling.
For <em>dynamic</em> scheduling algorithms, there are two key questions:
</P>
<ol type="1">
<LI>how they choose the next (ready) task to run
<ul>
<li>shortest job first</li>
<li>static priority ... highest priority ready task</li>
<li>soonest start-time deadline first (ASAP)</li>
<li>soonest completion-time deadline first (slack time)</li>
</ul>
</li>
<LI>how they handle overload (infeasible requirements)
<ul>
<li>best effort</li>
<li>periodicity adjustments ... run lower priority tasks less often.</li>
<li>work shedding ... stop running lower priority tasks entirely.</li>
</ul>
</li>
</ol>
<P>
Preemption may also be a different issue in real-time systems.
In ordinary time-sharing, preemption is a means of improving
mean response time by breaking up the execution of long-running,
compute-intensive tasks.
A second advantage of preemptive scheduling, particularly important
in a general purpose timesharing system, is that it prevents a
buggy (infinite loop) program from taking over the CPU.
The trade-off, between improved response time and increased overhead
(for the added context switches), almost always favors preemptive scheduling.
This may not be true for real-time systems:
<UL>
<LI> preempting a running task will almost surely cause it to
miss its completion deadline.</li>
<LI> since we so often know what the expected execution time
for a task will be, we can schedule accordingly and should
have little need for preemption.</li>
<LI> embedded and real-time systems run fewer and simpler
tasks than general purpose time systems, and the code
is often much better tested ... so infinite
loop bugs are extremely rare.</li>
</UL>
</P>
<P>
For the least demanding real time tasks, a sufficiently lightly loaded
system might be reasonably successful in meeting its deadlines.
However, this is achieved simply because the frequency at which
the task is run happens to be high enough to meet its real time
requirements, not because the scheduler is aware of such requirements.
A lightly loaded machine running a traditional scheduler can often
display a video to a user's satisfaction, not because the scheduler
"knows" that a frame must be rendered by a certain deadline, but
simply because the machine has enough cycles and a low enough work
load to render the frame before the deadline has arrived.
</P>
<H2>Real-Time and Linux</H2>
<P>
Linux was not designed to be an embedded or real-time operating system,
but many tasks that were once-considered embedded applications now
require the capabilities (e.g. file systems, network protocols) of
a general purpose operating system. As these requirements have
increased and processors have gotten faster, increasingly many
embedded and real-time applications have moved to Linux.
</P>
<P>
To support these applications Linux now
supports a real-time scheduler, which can be enabled with
<a href="http://man7.org/linux/man-pages/man2/sched_setscheduler.2.html">
sched_setscheduler(2)</a>, and is described in this
<a href="http://www.linuxjournal.com/magazine/real-time-linux-kernel-scheduler">
Linux Journal Article</a>.
This real-time scheduler does not provide quite the same level of response-time
guarantees that more traditional Real-Time-OSs do, but they are adequate for
many soft real-time applications.
</P>
<P>
What about Windows? Conventional wisdom states that Windows is not well
suited for real time needs, offering no native real time scheduler and too
many ways in which desired real time deadlines might be missed.
Windows favors general purpose throughput over meeting deadlines,
as a rule. With sufficiently low load, a Windows system may,
nonetheless, provide fast enough service for some soft real time
requirements, such as playing music or video.
One should be careful in relying on Windows for critical real time
operations, however, as it is not designed for that purpose.
</P>
</body>
<html>