Subversion Repositories shark

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
1676 tullio 1
%----------------------------------------------------------------------------
2
\chapter{Models}
3
%----------------------------------------------------------------------------
4
 
5
In this chapter we will described in detail the Models used in the
6
Generic Kernel. For a general description of the Models see
7
Section \ref{oview_Models}.
8
 
9
%----------------------------------------------------------------------------
10
\section{Data structures}
11
\label{Modelli_MetodologiaOOP}
12
%----------------------------------------------------------------------------
13
 
14
The approach used in the definition of the kernel data structures
15
is similar to that used in Object Oriented Languages.
16
 
17
In fact, there are many situations in which the kernel needs to
18
define data structures that can be thought as a \emph{base class},
19
which will be extended by the Modules that use it. For example,
20
the Kernel has to manage Task Models to know the stack size of a
21
task, but it does not have to know fields like priorities,
22
deadlines, and so on. Such data have to be stored into the task
23
model, because they represent a QoS specification for the Module
24
that will handle the task.
25
 
26
For this reason, the Generic Kernel only defines a C
27
\texttt{struct} that contains only the information that it needs
28
(and that is common to all the derived structures). If a Module
29
needs to extend that base class, it creates another
30
\texttt{struct} whose first field specifies the base class
31
type%
32
\footnote{In this way the derived struct will inherit the fields
33
from the base
34
class.%
35
}, whereas the other fields extend the base class.
36
 
37
In this way, both the Generic Kernel and the Modules can accept a
38
pointer to the base class to access the required information.
39
 
40
When the Kernel primitives are used, a pointer to a derived class
41
is passed instead of a pointer to the base class. Because the
42
first field of a derived class is of the base class type, the
43
pointer passed addresses the correct memory structure (the C
44
structures are stored using the declaration order), and the
45
Generic Kernel can safely handle the generic part of the
46
structure.
47
 
48
Viceversa, when a Module interface function receives from the
49
Generic Kernel a pointer to a base class, it will cast explicitly
50
the struct to the correct derived type, getting the extensions of
51
the derived class.
52
 
53
As it can be seen, this approach is a way to implement single
54
inheritance and polymorphism in the C language.
55
 
56
%----------------------------------------------------------------------------
57
\section{Task Models }
58
%----------------------------------------------------------------------------
59
 
60
The Task Models are implemented, as described in the previous
61
paragraph, through extensions to a base class. In the following
62
paragraph base class is described with the main extensions to it.
63
 
64
The Task Models that are included in the official distribution of
65
the Kernel are declared into the file
66
\texttt{include/kernel/model.h}.
67
 
68
%----------------------------------------------------------------------------
69
\subsection{\texttt{TASK\_MODEL}}
70
\label{Modelli_TASK_MODEL}
71
%----------------------------------------------------------------------------
72
 
73
This is the base structure for the Task Models. Its definition is
74
showed in Figure \ref{Modelli_struct_TASK_MODEL}.
75
 
76
\begin{figure}
77
\begin{center}
78
\begin{minipage}{6cm}
79
\begin{verbatim}
80
typedef struct {
81
    WORD pclass;
82
    LEVEL level;
83
    size_t stacksize;
84
    void *stackaddr;
85
    WORD group;
86
    void *arg;
87
    DWORD control;
88
} TASK_MODEL;
89
\end{verbatim}
90
\end{minipage}
91
\end{center}
92
\label{Modelli_struct_TASK_MODEL}
93
\caption{the \texttt{struct TASK\_MODEL}.}
94
\end{figure}
95
 
96
In the following paragraph each field of that structure is described.
97
 
98
\begin{description}
99
\item [\texttt{pclass}]this field contains an identifier that represents the
100
real (derived) type of the structure. The \texttt{pclass} fields of the derived
101
class that are included into the official distribution are included into the
102
file \texttt{include/kernel/model.h}. The \texttt{pclass} field is a 16 bit
103
integer \item [\texttt{level}]this field identifies a particular level to which
104
the task must be inserted in preference. 0 means ``all levels'' \footnote{We
105
recall that the Scheduling Modules are organized in levels. The Task Models are
106
used when a task is created and they are passed to the Modules to find a Module
107
that can handle the Model. All the Modules accepts Models in which the
108
\texttt{level} field are 0 or the level number in which the Module is
109
registered. In this way it is possible to distinguish Task Models that are
110
related to different Modules when there are many Modules that can accept the
111
same Model.}.
112
\item [\texttt{stacksize}]this is the dimension (in bytes)
113
required for the stack of the task to be created. The Generic
114
Kernel provides allocation and deallocation of the stack of the
115
tasks (only if the parameter \texttt{stackaddr} is not specified).
116
\item [\texttt{stackaddr}]this is a memory pointer that can be used as stack for
117
the task to be created. If this parameter is specified, the \texttt{stacksize}
118
field is ignored when a task is created. The memory pointed by
119
\texttt{stackaddr} is not deallocated at the termination of the task
120
(deallocation must be done by the creating task. There is no check on the
121
dimension of the memory area pointed by \texttt{stackaddr}.
122
\item [\texttt{group}]the tasks in the Generic
123
Kernel are divided into groups. The group of a task is specified
124
when a task is created, using this field. A group is a number that
125
is common to a set of tasks in the system. This identifier is used
126
by the primitives \texttt{group\_activate} and
127
\texttt{group\_kill} to activate or kill a set of tasks in an
128
atomic way.
129
\item [\texttt{arg}]the body of a task created into
130
the system is a function that accepts a \texttt{void~*}
131
parameter. That parameter is passed at the first activation of a
132
task and it is specified in this field.
133
\item [\texttt{control}]this field contains a set of flags that represents
134
features of the task to be created and represents also some particular states of
135
a running task. Flags are set by the user at creation time or they can be set by
136
some primitives. The defined flags are:
137
 
138
\begin{description}
139
\item [\texttt{USE\_FPU}]This flag is used by the OS Lib to notify
140
the system that the task uses in its code some floating point
141
operation. This information is used by the OS Lib to guarantee
142
that the FPU state is saved at each context switch. \item
143
[\texttt{NO\_KILL}]If this flag is set the task cannot be killed
144
through a \texttt{task\_kill} primitive. This flag is also used at
145
the shutdown of the kernel (see Section \ref{Kernel_TaskUtente}),
146
and it can be specified only at the task creation. \item
147
[\texttt{NO\_PREEMPT}]If this flag is set, the running task cannot
148
be preempted by another task, but it can be interrupted by a
149
device handler. In other words, the scheduler is disabled. This
150
flag is modified by the primitives \texttt{task\_preempt} and
151
\texttt{task\_nopreempt}. \item [\texttt{SYSTEM\_TASK}]If set this
152
flag marks the task as a system task. It can be specified only at
153
creation time. The fact that a task is or not a system task
154
affects the system shutdown (see Section \ref{Kernel_TaskUtente}).
155
\item [\texttt{JET\_ENABLED}]This flag can be set only at task
156
creation time and when set specifies that the Generic Kernel must
157
register the Job Execution Time statistics. \item
158
[\texttt{TASK\_JOINABLE}]This flag is set if another task can wait
159
for the task termination through the \texttt{task\_join} primitive
160
(see Section \ref{Kernel_Join}). \item
161
[\texttt{STACKADDR\_SPECIFIED}]This flag is set by the creation
162
primitive if the \texttt{stackaddr} field was specified. At
163
termination time, if this flag is not set, the stack space is
164
deallocated by the Kernel; otherwise, the stack space is left
165
according to the POSIX standard. \item [\texttt{TRACE\_TASK}]This
166
flag is set if the tracer has to monitor the task events. \item
167
[\texttt{KILLED\_ON\_CONDITION}]This flag is used in the
168
implementation of the condition variables. This flag is set by the
169
Generic Kernel if a task is killed while it is blocked on a
170
condition variable. In this case the task must be rescheduled to
171
reaquire the mutex linked to the condition variable. \item
172
[\texttt{KILL\_ENABLED}]This flag is set if the cancellation (in a
173
POSIX meaning) is or not enabled. \item
174
[\texttt{KILL\_DEFERRED}]This flag is set if the cancellation (in
175
a POSIX meaning) is deferred (the cancellation is asynchronous if
176
not). \item [\texttt{KILL\_REQUEST}]This flag registers a
177
cancellation request made with one of these primitives:
178
\texttt{task\_kill}, \texttt{group\_kill},
179
\texttt{pthread\_testcancel}. \item [\texttt{CONTROL\_CAP}]This
180
flag is used in the Scheduling Modules to tell Generic Kernel to
181
generate an OS Lib event when the running task terminates its
182
capacity. \item [\texttt{TASK\_DOING\_SIGNALS}]This flag is set by
183
the Generic Kernel when the task is executing a signal handler.
184
This flag is used only in the function
185
\texttt{kern\_deliver\_pending\_signals}, contained in the file
186
\texttt{kernel/signal.c}. \item [\texttt{FREEZE\_ACTIVATION}]This
187
flag blocks the task activations done through the primitives
188
\texttt{task\_activate} and \texttt{group\_activate}.
189
 
190
 
191
The flag is modified by the primitives \texttt{task\_block\_activation} and
192
\texttt{task\_unblock\_activation}.
193
 
194
\item [\texttt{WAIT\_FOR\_JOIN}]This flag is set when a task
195
terminates, but only if a task is joinable. The flag is used to
196
register that the task is terminated and it is waiting for someone
197
to do a join on it to die. \item
198
[\texttt{DESCRIPTOR\_DISCARDED}]This flag is used in the
199
implementation of the join primitive, and it is set by the
200
primitive \texttt{task\_create} to notify that a task descriptor,
201
whose task is terminated and is waiting for a join, has been
202
chosen and discarded for the creation of a new task. \item
203
[\texttt{SIGTIMEOUT\_EXPIRED}]This flag is set for the task
204
blocked on a \texttt{sigtimedwait} primitive, when the timeout
205
event fires.
206
\end{description}
207
 
208
\end{description}
209
 
210
The internal data structures of a \texttt{TASK\_MODEL} should be
211
used only into the Generic Kernel and into the Modules. For this
212
reason the system provides a set of macros that can be used to set
213
the required values in a base class object. In all the described
214
macros the parameter \texttt{m} is a \texttt{TASK\_MODEL}. The
215
macro are described below:
216
 
217
\begin{description}
218
\item [\texttt{task\_default\_model(m,p)}]This macro initializes
219
the Model \texttt{m} to a default value. The \texttt{pclass} of
220
\texttt{m} becomes equal to the \texttt{p} parameter. \item
221
[\texttt{task\_def\_level(m,l)}]This macro specifies the
222
scheduling level \texttt{l} of Model \texttt{m}. \item
223
[\texttt{task\_def\_arg(m,a)}]This macro specifies the parameter
224
passed to the first activation of the task initialized with Model
225
\texttt{m}. \item [\texttt{task\_def\_stack(m,s)}]This macro is
226
used to specify the stack dimension of the task initialized with
227
Model \texttt{m}. \item [\texttt{task\_def\_stackaddr(m,s)}]This
228
macro is used to specify a memory address pointer to be used as a
229
stack for the task initialized with Model \texttt{m}. \item
230
[\texttt{task\_def\_group(m,g)}]This macro is used to specify the
231
group of tasks initialized with Model \texttt{m}. \item
232
[\texttt{task\_def\_usemath(m)}]This macro is used to specify that
233
the task initialized with Model \texttt{m} uses the mathematical
234
coprocessor. \item [\texttt{task\_def\_system(m)}]This macro is
235
used to specify that the task that is initialized with Model
236
\texttt{m} is a system task. \item
237
[\texttt{task\_def\_nokill(m)}]This macro is used to specify that
238
the task initialized with Model \texttt{m} cannot be killed. \item
239
[\texttt{task\_def\_ctrl\_jet(m)}]This macro is used to specify
240
that the task initialized with Model \texttt{m} requires the
241
monitoring of the job execution time. \item
242
[\texttt{task\_def\_joinable(m)}]This macro is used to specify
243
that the task initialized with Model \texttt{m} can be passed as a
244
parameter into the join primitive. \item
245
[\texttt{task\_def\_unjoinable(m)}]This macro is used to specify
246
that the task initialized with Model \texttt{m} cannot be passed
247
as parameter into the join primitive. \item
248
[\texttt{task\_def\_trace(m)}]This macro is used to specify that
249
the task initialized with Model \texttt{m} is a task for which the
250
system tracer will register some information about the events
251
related to it. \item [\texttt{task\_def\_notrace(m)}]This macro is
252
used to specify that the task initialized with Model \texttt{m} is
253
a task for which the system tracer will not register any
254
information.
255
\end{description}
256
 
257
%----------------------------------------------------------------------------
258
\subsection{Used conventions}
259
%----------------------------------------------------------------------------
260
 
261
In normal situations the final user never needs to instantiate an
262
object of type \texttt{TASK\_MODEL}, but objects of a type derived
263
from it. Also the macro described in the previous paragraph cannot
264
be used directly; instead, there are similar macros redefined for
265
the derived types.
266
 
267
The standard used in the inheritance of a Model from the base
268
model are the following:
269
 
270
\begin{enumerate}
271
 
272
\item The name of the derived class is obtained from the name of the base class
273
by adding a prefix. For example, the task Model for the Soft task is called
274
\texttt{SOFT\_TASK\_MODEL}.
275
 
276
\item The first field of a derived structure is a structure with name \texttt{t}
277
and type \texttt{TASK\_MODEL}.
278
 
279
\item The specific parameters added to the models (e.g., period, wcet, etc.) are
280
inserted as normal fields after the first field. These fields represent a
281
specification of the Quality of Service required by a task to the system at
282
creation time. The Scheduling Modules can be structured in a way that they may
283
use only a subset of the fields of a Model \footnote{For example, to create a
284
Soft Task Model it is useful to insert two parameters like period and mean
285
execution time; these parameters are mandarory for the Scheduling Module that
286
implements CBS, whereas they are ignored by a Scheduling Module that implements
287
a Polling Server.}. This approach limits the growth of the number of Models and
288
achieves better independence of the applications from the task models
289
\footnote{For example, an Application can use a Soft Task Model specifying all
290
the Model parameters, without knowing which Scheduling Module is really used,
291
e.g. CBS or Polling Server).}.
292
 
293
\item The macros defined for the \texttt{TASK\_MODEL} struct and described in
294
the previous paragraph must also be defined for the new model. They should be
295
rewritten with a name derived from the old name, like the example below:
296
\begin{center}
297
\fbox{\tt{
298
 \#define soft\_task\_def\_level(m,l) task\_def\_level((m).t,l)
299
}}
300
\end{center}
301
 
302
\item The new model should provide a set of private macros similar to those
303
provided with the \texttt{TASK\_MODEL} to handle the new fields of the derived
304
structure. For example, if the new model has a field called \texttt{period}
305
(that contains for example a reactivation period), the new macro should be
306
similar to the one shown below:
307
\begin{center} \fbox{\tt{
308
 \#define soft\_task\_def\_period(m,p) (m).period = (p)
309
}}
310
\end{center}
311
\end{enumerate}
312
 
313
The five rules described above simplify the definition of new
314
models allowing the user to cut and paste the code of a similar
315
model and to modify some prefixes.
316
 
317
%----------------------------------------------------------------------------
318
\subsection{Examples of Models currently integrated into the Kernel}
319
%----------------------------------------------------------------------------
320
 
321
Currently the Kernel defines a set of Task Models directly derived
322
from the base TASK\_MODEL class. In the following paragraphs they
323
are briefly described (for their definition look in the file
324
\texttt{include/kernel/model.h}).
325
 
326
\begin{description}
327
\item [\texttt{HARD\_TASK\_MODEL}]~
328
 
329
 
330
This Task Model can be used to model Hard Periodic and Sporadic tasks. A Hard
331
Periodic Task \footnote{The \texttt{periodicity} field of the model must be set
332
to \texttt{PERIODIC}.} is a task guaranteed using an activation period and a
333
wcet \footnote{Worst Case Execution Time.}, whereas a Hard Sporadic Task
334
\footnote{The \texttt{periodicity} field of the model must be set to
335
\texttt{APERIODIC}.} is an aperiodic task guaranteed on a minimum interarrival
336
time and a wcet.
337
 
338
The Model allows the specification of a relative deadline. If not
339
specified, the deadline is assumed to be equal to the next
340
reactivation time (as in the classical task model proposed by Liu
341
and Layland \cite{Liu73}).
342
 
343
The Model also allows a release offset to be specified. This means
344
that any activation should be delayed by the given offset.
345
 
346
\end{description}
347
 
348
A Module that accepts tasks with this Model can raise the
349
following exceptions:
350
 
351
\begin{description}
352
\item [\texttt{XDEADLINE\_MISS}]This exception is raised if the
353
task misses a deadline.
354
 
355
\begin{description}
356
\item [\texttt{XWCET\_VIOLATION}]This exception is raised if the
357
task tries to use more CPU time than declared.
358
 
359
\item [\texttt{XACTIVATION}]This exception is raised if a sporadic task is
360
activated with a frequency greater than that declared.
361
\end{description}
362
 
363
\item [\texttt{SOFT\_TASK\_MODEL}]
364
 
365
 
366
This Task Model is used to specify the QoS required by a soft
367
task. A soft task is a periodic or aperiodic task, which is
368
handled by a server with a given (guaranteed) bandwidth (i.e.,
369
which allocates a budget Qs every interval Ts).
370
 
371
A soft task can specify, using a specific field, if it wants to save or skip
372
pending activations. A pending activation occurs when a task is activated before
373
the end of its current instance \footnote{It may happen when the reserved
374
bandwidth is less than the maximum task's utilization.}. The Scheduling Modules
375
can choose whether to handle or not this situation. Pending activations
376
influence the behavior of the \texttt{task\_sleep} and \texttt{task\_endcycle}
377
primitives.
378
 
379
The Soft Task Model has also a field which contains a wcet. This
380
field can be required by some algorithm that requires this
381
information (for example, the TBS algorithm.
382
 
383
Usually, the Modules that accept the soft task model do not raise
384
any exception.
385
 
386
\item [\texttt{NRT\_TASK\_MODEL}]
387
 
388
This Task Model is typically used to support non real-time
389
computations performed by tasks without temporal requirements.
390
 
391
Typical Modules that use these Models are Modules that implement
392
scheduling algorithms like Round Robin, Proportional Share,
393
priority scheduling, and POSIX scheduling.
394
 
395
The model has also a field to specify whether a Task have to save
396
or skip pending activations.
397
 
398
Finally, the Model has two other fields (\texttt{inherit} and \texttt{policy})
399
used in the implementation of the POSIX scheduling algorithm \footnote{This is
400
one of the (rare) cases in which the Task Model depends on a specific Scheduling
401
Module.}.
402
 
403
\item [\texttt{JOB\_TASK\_MODEL}]
404
 
405
This Task Model is normally used by an Aperiodic Server to pass a
406
task to a Master Module. It is not explicitly used in the
407
Application code.
408
 
409
This Model extends the Base Model with a deadline and a period. A
410
Job is a single a task instance which starts and stops without
411
synchronization points in between.
412
 
413
Typically, an aperiodic server inserts a Job in the Master Module
414
to ask for service. When that task ends its instance or it blocks
415
on a synchronization variable, the Job dies and it is newly
416
recreated when the task is reactivated or when it resumes from
417
blocking.
418
 
419
There are no fields that specify computation times (i.e., wcet,
420
met) because the Aperiodic Servers that use that Model generally
421
handle a budget.
422
 
423
The Model contains another field that specifies whether a Master
424
Module should raise a deadline exception when a deadline is
425
reached and the Job is still alive.
426
 
427
\end{description}
428
 
429
%----------------------------------------------------------------------------
430
\section{Resource Models}
431
\label{Modelli_RES_MODEL}
432
%----------------------------------------------------------------------------
433
 
434
The resource Models are implemented in a way similar to the Task
435
Models. The difference between Task Models and Resource Models is
436
that it is not possible to group a set of fields common to all
437
Resource Handlers. For this reason, the C structure that
438
represents the base class of a Resource Model contains only a
439
field that provides information about the real type of a Resource
440
Model. As done for the Task Models, that field is called
441
\texttt{rclass}.
442
 
443
The Resource Models available in the kernel are used in the
444
implementation of the Priority Ceiling Protocol and the Stack
445
Resource Policy.
446
 
447
In the case of Priority Ceiling, the Resource Model only adds a
448
static priority of the task to be created.
449
 
450
In the case of SRP, the Resource Model only adds the definition of
451
the Preemption Level of the task.
452
 
453
The Resource Models contained into the official distribution of
454
the Kernel are included into the file
455
\texttt{include/kernel/model.h}.
456
 
457
%----------------------------------------------------------------------------
458
\section{Mutex attributes}
459
%----------------------------------------------------------------------------
460
 
461
The protocol used by a mutex is decided when the mutex is
462
initialized (at run time).
463
 
464
To implement the mutex initialization in a modular fashion we
465
derived a structure, called \texttt{mutexattr\_t}, from a base
466
structure similar to that used in the Resource Models
467
 
468
We derived a set of mutex attributes to be used in the
469
initialization of a mutex (a mutex is contained in a
470
\texttt{mutex\_t} type, which is similar to the POSIX's
471
\texttt{pthread\_mutex\_t}).
472
 
473
The Mutex Attributes are declared into the file
474
\texttt{include/kernel/model.h}.