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
205
206
207
208
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<HTML>
<HEAD>
<TITLE>AARM95 - The Task Dispatching Model</TITLE>
<META NAME="Author" CONTENT="JTC1/SC22/WG9/ARG, by Randall Brukardt, ARG Editor">
<META NAME="GENERATOR" CONTENT="Arm_Form.Exe, Ada Reference Manual generator">
<STYLE type="text/css">
DIV.paranum {position: absolute; font-family: Arial, Helvetica, sans-serif; left: 0.5 em; top: auto}
TT {font-family: "Courier New", monospace}
DT {display: compact}
DIV.Normal {font-family: "Times New Roman", Times, serif; margin-bottom: 0.6em}
DIV.Wide {font-family: "Times New Roman", Times, serif; margin-top: 0.6em; margin-bottom: 0.6em}
DIV.Annotations {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-bottom: 0.6em}
DIV.WideAnnotations {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-top: 0.6em; margin-bottom: 0.6em}
DIV.Index {font-family: "Times New Roman", Times, serif}
DIV.SyntaxSummary {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-bottom: 0.4em}
DIV.Notes {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-bottom: 0.6em}
DIV.NotesHeader {font-family: "Times New Roman", Times, serif; margin-left: 2.0em}
DIV.SyntaxIndented {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-bottom: 0.4em}
DIV.Indented {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-bottom: 0.6em}
DIV.CodeIndented {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-bottom: 0.6em}
DIV.SmallIndented {font-family: "Times New Roman", Times, serif; margin-left: 10.0em; margin-bottom: 0.6em}
DIV.SmallCodeIndented {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-bottom: 0.6em}
DIV.Examples {font-family: "Courier New", monospace; margin-left: 2.0em; margin-bottom: 0.6em}
DIV.SmallExamples {font-family: "Courier New", monospace; font-size: 80%; margin-left: 7.5em; margin-bottom: 0.6em}
DIV.IndentedExamples {font-family: "Courier New", monospace; margin-left: 8.0em; margin-bottom: 0.6em}
DIV.SmallIndentedExamples {font-family: "Courier New", monospace; font-size: 80%; margin-left: 15.0em; margin-bottom: 0.6em}
UL.Bulleted {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-right: 2.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.SmallBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.NestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.SmallNestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-right: 8.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.IndentedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-right: 8.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.CodeIndentedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.CodeIndentedNestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-right: 8.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.SyntaxIndentedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.NotesBulleted {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.NotesNestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
DL.Hanging {font-family: "Times New Roman", Times, serif; margin-top: 0em; margin-bottom: 0.6em}
DD.Hanging {margin-left: 6.0em}
DL.IndentedHanging {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-top: 0em; margin-bottom: 0.6em}
DD.IndentedHanging {margin-left: 2.0em}
DL.HangingInBulleted {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-right: 2.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.HangingInBulleted {margin-left: 4.0em}
DL.SmallHanging {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-top: 0em; margin-bottom: 0.6em}
DD.SmallHanging {margin-left: 7.5em}
DL.SmallIndentedHanging {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-top: 0em; margin-bottom: 0.6em}
DD.SmallIndentedHanging {margin-left: 2.0em}
DL.SmallHangingInBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.SmallHangingInBulleted {margin-left: 5.0em}
DL.Enumerated {font-family: "Times New Roman", Times, serif; margin-right: 0.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.Enumerated {margin-left: 2.0em}
DL.SmallEnumerated {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.SmallEnumerated {margin-left: 2.5em}
DL.NestedEnumerated {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-right: 2.0em; margin-top: 0em; margin-bottom: 0.5em}
DL.SmallNestedEnumerated {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
</STYLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFF0" LINK="#0000FF" VLINK="#800080" ALINK="#FF0000">
<P><A HREF="AA-TOC.html">Contents</A> <A HREF="AA-0-29.html">Index</A> <A HREF="AA-D-2.html">Previous</A> <A HREF="AA-D-2-2.html">Next</A></P>
<HR>
<H1> D.2.1 The Task Dispatching Model</H1>
<DIV Class="Paranum"><FONT SIZE=-2>1</FONT></DIV>
<DIV Class="Normal"> [The task dispatching model specifies preemptive
scheduling, based on conceptual priority-ordered ready queues.] </DIV>
<H4 ALIGN=CENTER>Dynamic Semantics</H4>
<DIV Class="Paranum"><FONT SIZE=-2>2</FONT></DIV>
<DIV Class="Normal"> A task runs (that is, it becomes a <I>running
task</I>) only when it is ready (see <A HREF="AA-9-2.html">9.2</A>) and
the execution resources required by that task are available. Processors
are allocated to tasks based on each task's active priority.</DIV>
<DIV Class="Paranum"><FONT SIZE=-2>3</FONT></DIV>
<DIV Class="Normal"> It is implementation defined whether, on a multiprocessor,
a task that is waiting for access to a protected object keeps its processor
busy. </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>3.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Implementation defined: </B>Whether,
on a multiprocessor, a task that is waiting for access to a protected
object keeps its processor busy.</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>4</FONT></DIV>
<DIV Class="Normal"> <A NAME="I6779"></A><A NAME="I6780"></A><A NAME="I6781"></A><A NAME="I6782"></A><I>Task
dispatching</I> is the process by which one ready task is selected for
execution on a processor. This selection is done at certain points during
the execution of a task called <I>task dispatching points</I>. A task
reaches a task dispatching point whenever it becomes blocked, and whenever
it becomes ready. In addition, the completion of an <FONT FACE="Arial, Helvetica">accept_statement</FONT>
(see <A HREF="AA-9-5-2.html">9.5.2</A>), and task termination are task
dispatching points for the executing task. [Other task dispatching points
are defined throughout this Annex.] </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>4.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Ramification: </B>On multiprocessor
systems, more than one task can be chosen, at the same time, for execution
on more than one processor, as explained below. </FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>5</FONT></DIV>
<DIV Class="Normal"> <A NAME="I6783"></A><A NAME="I6784"></A><A NAME="I6785"></A><A NAME="I6786"></A><A NAME="I6787"></A><A NAME="I6788"></A><I>Task
dispatching policies</I> are specified in terms of conceptual <I>ready
queues</I>, task states, and task preemption. A ready queue is an ordered
list of ready tasks. The first position in a queue is called the <I>head
of the queue</I>, and the last position is called the <I>tail of the
queue</I>. A task is <I>ready</I> if it is in a ready queue, or if it
is running. Each processor has one ready queue for each priority value.
At any instant, each ready queue of a processor contains exactly the
set of tasks of that priority that are ready for execution on that processor,
but are not running on any processor; that is, those tasks that are ready,
are not running on any processor, and can be executed using that processor
and other available resources. A task can be on the ready queues of more
than one processor. </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>5.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Discussion: </B>The core language
defines a ready task as one that is not blocked. Here we refine this
definition and talk about ready queues. </FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>6</FONT></DIV>
<DIV Class="Normal"> <A NAME="I6789"></A>Each processor also has one
<I>running task</I>, which is the task currently being executed by that
processor. Whenever a task running on a processor reaches a task dispatching
point, one task is selected to run on that processor. The task selected
is the one at the head of the highest priority nonempty ready queue;
this task is then removed from all ready queues to which it belongs.
</DIV>
<DIV Class="Paranum"><FONT SIZE=-2>6.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Discussion: </B>There is always
at least one task to run, if we count the idle task. </FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>7</FONT></DIV>
<DIV Class="Normal"> <A NAME="I6790"></A>A preemptible resource is
a resource that while allocated to one task can be allocated (temporarily)
to another instead. Processors are preemptible resources. Access to a
protected object (see <A HREF="AA-9-5-1.html">9.5.1</A>) is a nonpreemptible
resource. <A NAME="I6791"></A>When a higher-priority task is dispatched
to the processor, and the previously running task is placed on the appropriate
ready queue, the latter task is said to be <I>preempted</I>. </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>7.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Reason: </B>A processor that
is executing a task is available to execute tasks of higher priority,
within the set of tasks that that processor is able to execute. Write
access to a protected object, on the other hand, cannot be granted to
a new task before the old task has released it. </FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>8</FONT></DIV>
<DIV Class="Normal"> <A NAME="I6792"></A><A NAME="I6793"></A>A new
running task is also selected whenever there is a nonempty ready queue
with a higher priority than the priority of the running task, or when
the task dispatching policy requires a running task to go back to a ready
queue. [These are also task dispatching points.] </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>8.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Ramification: </B>Thus, when
a task becomes ready, this is a task dispatching point for all running
tasks of lower priority. </FONT></DIV>
<H4 ALIGN=CENTER>Implementation Permissions</H4>
<DIV Class="Paranum"><FONT SIZE=-2>9</FONT></DIV>
<DIV Class="Normal"> An implementation is allowed to define additional
resources as execution resources, and to define the corresponding allocation
policies for them. Such resources may have an implementation defined
effect on task dispatching (see <A HREF="AA-D-2-2.html">D.2.2</A>). </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>9.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Implementation defined: </B>The
affect of implementation defined execution resources on task dispatching.</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>10</FONT></DIV>
<DIV Class="Normal"> An implementation may place implementation-defined
restrictions on tasks whose active priority is in the Interrupt_Priority
range. </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>10.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Ramification: </B>For example,
on some operating systems, it might be necessary to disallow them altogether.
This permission applies to tasks whose priority is set to interrupt level
for any reason: via a pragma, via a call to Dynamic_Priorities.Set_Priority,
or via priority inheritance. </FONT></DIV>
<DIV Class="NotesHeader"><FONT SIZE=-1>NOTES</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>11</FONT></DIV>
<DIV Class="Notes"><FONT SIZE=-1>7 Section 9 specifies under
which circumstances a task becomes ready. The ready state is affected
by the rules for task activation and termination, delay statements, and
entry calls. <A NAME="I6794"></A>When a task is not ready, it is said
to be blocked.</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>12</FONT></DIV>
<DIV Class="Notes"><FONT SIZE=-1>8 An example of a possible
implementation-defined execution resource is a page of physical memory,
which needs to be loaded with a particular page of virtual memory before
a task can continue execution.</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>13</FONT></DIV>
<DIV Class="Notes"><FONT SIZE=-1>9 The ready queues are purely
conceptual; there is no requirement that such lists physically exist
in an implementation.</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>14</FONT></DIV>
<DIV Class="Notes"><FONT SIZE=-1>10 While a task is running,
it is not on any ready queue. Any time the task that is running on a
processor is added to a ready queue, a new running task is selected for
that processor.</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>15</FONT></DIV>
<DIV Class="Notes"><FONT SIZE=-1>11 In a multiprocessor system,
a task can be on the ready queues of more than one processor. At the
extreme, if several processors share the same set of ready tasks, the
contents of their ready queues is identical, and so they can be viewed
as sharing one ready queue, and can be implemented that way. [Thus, the
dispatching model covers multiprocessors where dispatching is implemented
using a single ready queue, as well as those with separate dispatching
domains.]</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>16</FONT></DIV>
<DIV Class="Notes"><FONT SIZE=-1>12 The priority of a task
is determined by rules specified in this subclause, and under <A HREF="AA-D-1.html">D.1</A>,
``<A HREF="AA-D-1.html">Task Priorities</A>'', <A HREF="AA-D-3.html">D.3</A>,
``<A HREF="AA-D-3.html">Priority Ceiling Locking</A>'', and <A HREF="AA-D-5.html">D.5</A>,
``<A HREF="AA-D-5.html">Dynamic Priorities</A>''.</FONT></DIV>
<HR>
<P><A HREF="AA-TOC.html">Contents</A> <A HREF="AA-0-29.html">Index</A> <A HREF="AA-D-2.html">Previous</A> <A HREF="AA-D-2-2.html">Next</A> <A HREF="AA-TTL.html">Legal</A></P>
</BODY>
</HTML>
|
