Subversion Repositories shark

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
1676 tullio 1
\documentclass[english]{report}
2
\usepackage[T1]{fontenc}
3
\usepackage[latin1]{inputenc}
4
\usepackage{geometry}
5
\geometry{verbose,a4paper}
6
\usepackage{array}
7
\usepackage{makeidx}
8
\makeindex
9
\usepackage{graphicx}
10
 
11
\makeatletter
12
 
13
\usepackage{babel}
14
 
15
\newenvironment{intest}{\noindent\large\bf\hspace*{1pt}}
16
{\vspace*{-5pt}\\\line(1,0){433}}
17
 
18
\makeatother
19
 
20
\begin{document}
21
 
22
\thispagestyle{empty}
23
 
24
\begin{center}{\LARGE S.Ha.R.K. User Manual}\end{center}{\LARGE \par} \vfill{}
25
 
26
\begin{center}{\large Volume III}\end{center}
27
 
28
\begin{center}
29
S.Ha.R.K. Modules
30
\end{center}
31
\vfill{}
32
 
33
\begin{center}Written by\end{center}
34
 
35
\begin{center}Giorgio Buttazzo (giorgio at sssup.it)\end{center}
36
\begin{center}Paolo Gai (pj at sssup.it)\end{center}
37
\begin{center}Luigi Palopoli (luigi at hartik.sssup.it)\end{center}
38
\begin{center}Marco Caccamo (caccamo at sssup.it)\end{center}
39
\begin{center}Giuseppe Lipari (lipari at sssup.it) \end{center}
40
\begin{center}Tullio Facchinetti (tullio.facchinetti at unipv.it) \end{center}
41
\vfill{}
42
 
43
\begin{center}\includegraphics[width=2cm]{../common/sssup.ps}\end{center}
44
 
45
\begin{center}
46
Scuola Superiore di Studi e Perfezionamento S. Anna
47
\end{center}
48
 
49
\begin{center}RETIS Lab\end{center}
50
\begin{center}Via Carducci, 40 - 56100 Pisa\end{center}
51
\pagebreak
52
 
53
\tableofcontents{}
54
 
55
\begin{abstract}
56
The S.Ha.R.K. kernel provides a way to implement in a simple
57
way a lot of scheduling algorithms that have been proposed by the
58
Real-Time literature. This Volume simply contains a simple
59
description on which modules are available and how these modules
60
can be used. Moreover, to help the implementation of new modules,
61
a small description of the tricks used in the implementation is
62
also given.
63
\end{abstract}
64
 
65
%----------------------------------------------------------------------------
66
\chapter{Models}
67
%----------------------------------------------------------------------------
68
 
69
Task Models and Resource Models are the structures used by the
70
S.Ha.R.K. Kernel to isolate the scheduling parameter needed by the
71
various Scheduling Modules and Resource Modules.
72
 
73
To simplify the use of the Models, the Kernel provides a set of
74
macros that can be used to fill their various fields. In the
75
following paragraphs, the various models are described in detail.
76
All the Model definitions of this chapter can be found in the file
77
\texttt{include/kernel/model.h}.
78
 
79
Examples of Models initializations can be found in various
80
examples through this Volume.
81
 
82
%----------------------------------------------------------------------------
83
\section{HARD\_TASK\_MODEL}
84
%----------------------------------------------------------------------------
85
 
86
\begin{tt}
87
\begin{verbatim}
88
typedef struct {
89
    TASK_MODEL t;
90
    TIME mit;
91
    TIME drel;
92
    TIME wcet;
93
    int periodicity;
94
} HARD_TASK_MODEL;
95
\end{verbatim}
96
\end{tt}
97
 
98
A Hard Task model can be used to model periodic and sporadic
99
tasks. These tasks are usually guaranteed basing on their minimum
100
interarrival time (mit) and wcet, and may have a relative
101
deadline.
102
 
103
Table \ref{tab:HARD_TASK_MODEL_Macros} shows the macros that
104
applies to a \texttt{HARD\_TASK\_MODEL}.
105
 
106
\begin{table}
107
\begin{tabular}{|l|p{8cm}|}
108
\hline Macro name & Behaviour \\ \hline
109
 
110
hard\_task\_default\_model(m) & Default values for the Model
111
(periodic task, others = 0) \\ \hline
112
 
113
hard\_task\_def\_level(m,l) & Set the Model level to l. A Module
114
registered at level x can accept a Model only if it has level 0 or
115
x. The default value is 0. \\ \hline
116
 
117
hard\_task\_def\_arg(m,a) & Set the void * argument passed to
118
the task the first time it is activated. The default value is
119
NULL.\\ \hline
120
 
121
hard\_task\_def\_stack(m,s) & Set the task stack size. The default
122
value is 4096.\\ \hline
123
 
124
hard\_task\_def\_stackaddr(m,s) & If the stack is statically
125
allocated you can tell its address here. The default is NULL (no
126
pre-allocated stack).\\ \hline
127
 
128
hard\_task\_def\_group(m,g) & Set the task group to g. Task
129
grouping influences primitives like group\_activate() or
130
group\_kill()\\ \hline
131
 
132
hard\_task\_def\_usemath(m) & Declare that the task uses floating
133
point arithmetic.\\ \hline
134
 
135
hard\_task\_def\_system(m) & Declare that the task is a system
136
task. System tasks behaves differently at shutdown. See the
137
Architecture manual for details.\\ \hline
138
 
139
hard\_task\_def\_nokill(m) & Declare that the task can not be
140
killed. These tasks behaves differently at shutdown. See the
141
Architecture manual for details.\\ \hline
142
 
143
hard\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
144
JET informations for the task.\\ \hline
145
 
146
hard\_task\_def\_mit(m,p) & Set the Minimum Interarrival Time
147
(MIT) of the Model to p.\\ \hline
148
 
149
hard\_task\_def\_drel(m,d) & Set the relative deadline to
150
d.\\ \hline
151
 
152
hard\_task\_def\_wcet(m,w) & Set the Worst Case Execution Time to
153
w.\\ \hline
154
 
155
hard\_task\_def\_periodic(m) & Declare that the task is
156
Periodic.\\ \hline
157
 
158
hard\_task\_def\_aperiodic(m) & Declare that the task is Sporadic
159
(Aperiodic).\\ \hline
160
 
161
hard\_task\_def\_joinable(m) & Declare that the task is joinable
162
with task\_join()/pthread\_join().\\ \hline
163
 
164
hard\_task\_def\_unjoinable(m) & Declare that the task is not
165
joinable (is detached) with
166
task\_join()/pthread\_join().\\ \hline
167
 
168
hard\_task\_def\_trace(m) & Declare that the task has to be traced
169
by the Tracer.\\ \hline
170
 
171
hard\_task\_def\_notrace(m) & Declare that the task has not to be
172
traced by the Tracer.\\ \hline
173
\end{tabular}
174
\caption{HARD\_TASK\_MODEL Macros}
175
\label{tab:HARD_TASK_MODEL_Macros}
176
\end{table}
177
 
178
%----------------------------------------------------------------------------
179
\section{SOFT\_TASK\_MODEL}
180
%----------------------------------------------------------------------------
181
 
182
\begin{tt}
183
\begin{verbatim}
184
typedef struct {
185
    TASK_MODEL t;
186
    TIME period;
187
    TIME met;
188
    TIME wcet;
189
    int periodicity;
190
    int arrivals;
191
} SOFT_TASK_MODEL;
192
\end{verbatim}
193
\end{tt}
194
 
195
A Soft Task model can be used to model periodic and aperiodic
196
tasks usually not guaranteed or guaranteed basing on their period
197
and mean execution time (met). A Soft task can also record pending
198
activations if the arrivals are set to SAVE\_ACTIVATIONS. A wcet
199
field is also present for those servers that need it (i.e., TBS).
200
 
201
Table \ref{tab:SOFT_TASK_MODEL_Macros} shows the macros that
202
applies to a \texttt{SOFT\_TASK\_MODEL}.
203
 
204
\begin{table}
205
\begin{tabular}{|l|p{8cm}|}
206
\hline Macro name & Behaviour\\ \hline
207
 
208
soft\_task\_default\_model(m) & Default values for the Model
209
(periodic task, save arrivals, others = 0).\\ \hline
210
 
211
soft\_task\_def\_level(m,l) & Set the Model level to l. A Module
212
registered at level x can accept a Model only if it has level 0 or
213
x. The default value is 0.\\ \hline
214
 
215
soft\_task\_def\_arg(m,a) & Set the void * argument passed to
216
the task the first time it is activated. The default value is
217
NULL.\\ \hline
218
 
219
soft\_task\_def\_stack(m,s) & Set the task stack size. The default
220
value is 4096.\\ \hline
221
 
222
soft\_task\_def\_stackaddr(m,s) & If the stack is statically
223
allocated you can tell its address here. The default is NULL (no
224
pre-allocated stack).\\ \hline
225
 
226
soft\_task\_def\_group(m,g) & Set the task group to g. Task
227
grouping influences primitives like group\_activate() or
228
group\_kill()\\ \hline
229
 
230
soft\_task\_def\_usemath(m) & Declare that the task uses floating
231
point arithmetic.\\ \hline
232
 
233
soft\_task\_def\_system(m) & Declare that the task is a system
234
task. System tasks behaves differently at shutdown. See the
235
Architecture manual for details.\\ \hline
236
 
237
soft\_task\_def\_nokill(m) & Declare that the task can not be
238
killed. These tasks behaves differently at shutdown. See the
239
Architecture manual for details.\\ \hline
240
 
241
soft\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
242
JET informations for the task.\\ \hline
243
 
244
soft\_task\_def\_period(m,p) & Set the task period to
245
p.\\ \hline
246
 
247
soft\_task\_def\_met(m,d) & Set the task Mean Execution Time (MET)
248
to d.\\ \hline
249
 
250
soft\_task\_def\_wcet(m,w) & Set the Worst Case Execution Time to
251
w.\\ \hline
252
 
253
soft\_task\_def\_periodic(m) & Declare that the task is
254
Periodic.\\ \hline
255
 
256
soft\_task\_def\_aperiodic(m) & Declare that the task is Sporadic
257
(Aperiodic).\\ \hline
258
 
259
soft\_task\_def\_joinable(m) & Declare that the task is joinable
260
with task\_join()/pthread\_join().\\ \hline
261
 
262
soft\_task\_def\_unjoinable(m) & Declare that the task is not
263
joinable (is detached) with
264
task\_join()/pthread\_join().\\ \hline
265
 
266
soft\_task\_def\_trace(m) & Declare that the task has to be traced
267
by the Tracer.\\ \hline
268
 
269
soft\_task\_def\_notrace(m) & Declare that the task has not to be
270
traced by the Tracer.\\ \hline
271
 
272
soft\_task\_def\_save\_arrivals(m) & The task will save a pending
273
activation if it arrives when the task is already
274
active.\\ \hline
275
 
276
soft\_task\_def\_skip\_arrivals(m) & The task will ignore a
277
pending activation if it arrives when the task is already
278
active.\\ \hline
279
\end{tabular}
280
\caption{SOFT\_TASK\_MODEL Macros}
281
\label{tab:SOFT_TASK_MODEL_Macros}
282
\end{table}
283
 
284
\pagebreak
285
 
286
%----------------------------------------------------------------------------
287
\section{NRT\_TASK\_MODEL}
288
%----------------------------------------------------------------------------
289
 
290
\begin{tt}
291
\begin{verbatim}
292
typedef struct {
293
    TASK_MODEL t;
294
    int weight;
295
    TIME slice;
296
    int arrivals;
297
    int policy;
298
    int inherit;
299
} NRT_TASK_MODEL;
300
\end{verbatim}
301
\end{tt}
302
 
303
A NRT task has a weight and a time slice, plus a policy attribute.
304
It can be used to model Round Robin, Proportional Share, POSIX,
305
and Priority tasks.
306
 
307
Note that policy and inherit are inserted in the model to support
308
POSIX compliant scheduling without adding another Task Model;
309
weight can be used to contain the fixed priority of a task; slice
310
can be used to contain the RR slice of the task.
311
 
312
Table \ref{tab:NRT_TASK_MODEL_Macros} shows the macros that
313
applies to a \texttt{NRT\_TASK\_MODEL}.
314
 
315
\begin{table}
316
\begin{tabular}{|c|p{8cm}|}
317
\hline Macro name & Behaviour\\ \hline
318
 
319
nrt\_task\_default\_model(m) & Default values for the Model (save
320
arrivals, NRT\_RR\_POLICY, NRT\_EXPLICIT\_SCHED, others =
321
0).\\ \hline
322
 
323
nrt\_task\_def\_level(m,l) & Set the Model level to l. A Module
324
registered at level x can accept a Model only if it has level 0 or
325
x. The default value is 0.\\ \hline
326
 
327
nrt\_task\_def\_arg(m,a) & Set the void * argument passed to the
328
task the first time it is activated. The default value is
329
NULL.\\ \hline
330
 
331
nrt\_task\_def\_stack(m,s) & Set the task stack size. The default
332
value is 4096.\\ \hline
333
 
334
nrt\_task\_def\_stackaddr(m,s) & If the stack is statically
335
allocated you can tell its address here. The default is NULL (no
336
pre-allocated stack).\\ \hline
337
 
338
nrt\_task\_def\_group(m,g) & Set the task group to g. Task
339
grouping influences primitives like group\_activate() or
340
group\_kill()\\ \hline
341
 
342
nrt\_task\_def\_usemath(m) & Declare that the task uses floating
343
point arithmetic.\\ \hline
344
 
345
nrt\_task\_def\_system(m) & Declare that the task is a system
346
task. System tasks behaves differently at shutdown. See the
347
Architecture manual for details.\\ \hline
348
 
349
nrt\_task\_def\_nokill(m) & Declare that the task can not be
350
killed. These tasks behaves differently at shutdown. See the
351
Architecture manual for details.\\ \hline
352
 
353
nrt\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
354
JET informations for the task.\\ \hline
355
 
356
nrt\_task\_def\_weight(m,w) & Set the task weight to
357
w.\\ \hline
358
 
359
nrt\_task\_def\_slice(m,d) & Set the timeslice to
360
d.\\ \hline
361
 
362
nrt\_task\_def\_policy(m,p) & Set the policy of the task. p can be
363
NRT\_RR\_POLICY or NRT\_FIFO\_POLICY. (used for POSIX
364
scheduling)\\ \hline
365
 
366
nrt\_task\_def\_inherit(m,i) & Tell if the task should inherit the
367
same properties of the father. i can be NRT\_INHERIT\_SCHED or
368
NRT\_EXPLICIT\_SCHED. (used for POSIX scheduling)\\
369
\hline
370
 
371
nrt\_task\_def\_joinable(m) & Declare that the task is joinable
372
with task\_join()/pthread\_join().\\ \hline
373
 
374
nrt\_task\_def\_unjoinable(m) & Declare that the task is not
375
joinable (is detached) with
376
task\_join()/pthread\_join().\\ \hline
377
 
378
nrt\_task\_def\_trace(m) & Declare that the task has to be traced
379
by the Tracer.\\ \hline
380
 
381
nrt\_task\_def\_notrace(m) & Declare that the task has not to be
382
traced by the Tracer.\\ \hline
383
 
384
nrt\_task\_def\_save\_arrivals(m) & The task will save a pending
385
activation if it arrives when the task is already
386
active.\\ \hline
387
 
388
nrt\_task\_def\_skip\_arrivals(m) & The task will ignore a pending
389
activation if it arrives when the task is already
390
active.\\ \hline
391
\end{tabular}
392
\caption{NRT\_TASK\_MODEL Macros}
393
\label{tab:NRT_TASK_MODEL_Macros}
394
\end{table}
395
 
396
%----------------------------------------------------------------------------
397
\section{JOB\_TASK\_MODEL}
398
%----------------------------------------------------------------------------
399
 
400
\begin{tt}
401
\begin{verbatim}
402
typedef struct {
403
    TASK_MODEL t;
404
    TIME period;
405
    struct timespec deadline;
406
    int noraiseexc;
407
} JOB_TASK_MODEL;
408
\end{verbatim}
409
\end{tt}
410
 
411
This model implements a Job with an optional period and a starting
412
deadline (for the first activation). A Job task can raise a
413
XDEADLINE\_MISS exception; if the flag noraiseexc is != 0, the
414
exception is not raised.
415
 
416
This model is normally used with aperiodic servers: the aperiodic
417
server insert a guest task in another level with that model
418
calling \texttt{guest\_create} and \texttt{guest\_activate}. When
419
the task has to be removed, \texttt{guest\_end} is called.
420
 
421
Note that there is no capacity control on this model. Note that
422
the task that accept this task DOESN'T reactivate the task after a
423
period... There is NOT a guest\_endcycle defined for this model...
424
 
425
Table \ref{tab:JOB_TASK_MODEL_Macros} shows the macros that
426
applies to a \texttt{JOB\_TASK\_MODEL}.
427
 
428
\begin{table}
429
\begin{tabular}{|l|p{8cm}|}
430
\hline Macro name& Behaviour\\ \hline
431
 
432
job\_task\_default\_model(m,dl) & Default values for the Model
433
(period = 0, deadline = dl, noraiseexc = 0)\\ \hline
434
 
435
job\_task\_def\_level(m,l) & Set the Model level to l. A Module
436
registered at level x can accept a Model only if it has level 0 or
437
x. The default value is 0.\\ \hline
438
 
439
job\_task\_def\_arg(m,a) & Set the void * argument passed to the
440
task the first time it is activated. The default value is
441
NULL.\\ \hline
442
 
443
job\_task\_def\_stack(m,s) & Set the task stack size. The default
444
value is 4096.\\ \hline
445
 
446
job\_task\_def\_stackaddr(m,s) & If the stack is statically
447
allocated you can tell its address here. The default is NULL (no
448
pre-allocated stack).\\ \hline
449
 
450
job\_task\_def\_group(m,g) & Set the task group to g. Task
451
grouping influences primitives like group\_activate() or
452
group\_kill()\\ \hline
453
 
454
job\_task\_def\_usemath(m) & Declare that the task uses floating
455
point arithmetic.\\ \hline
456
 
457
job\_task\_def\_system(m) & Declare that the task is a system
458
task. System tasks behaves differently at shutdown. See the
459
Architecture manual for details.\\ \hline
460
 
461
job\_task\_def\_nokill(m) & Declare that the task can not be
462
killed. These tasks behaves differently at shutdown. See the
463
Architecture manual for details.\\ \hline
464
 
465
job\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
466
JET informations for the task.\\ \hline
467
 
468
job\_task\_def\_period(m,p) & Set the period to p.\\ \hline
469
 
470
job\_task\_def\_deadline(m,dl) & Set the deadline to
471
dl.\\ \hline
472
 
473
job\_task\_def\_noexc(m) & Set noraiseexc = 1.\\ \hline
474
 
475
job\_task\_def\_yesexc(m) & Set noraiseexc = 1.\\ \hline
476
 
477
job\_task\_def\_joinable(m) & Declare that the task is joinable
478
with task\_join()/pthread\_join().\\ \hline
479
 
480
job\_task\_def\_unjoinable(m) & Declare that the task is not joinable (is
481
detached) with task\_join()/pthread\_join().\\ \hline
482
 
483
job\_task\_def\_trace(m) & Declare that the task has to be traced
484
by the Tracer.\\ \hline
485
 
486
job\_task\_def\_notrace(m) & Declare that the task has not to be
487
traced by the Tracer.\\ \hline
488
\end{tabular}
489
\caption{HARD\_TASK\_MODEL Macros}
490
\label{tab:JOB_TASK_MODEL_Macros}
491
\end{table}
492
 
493
%----------------------------------------------------------------------------
494
\section{BDEDF\_RES\_MODEL (BlockDevice EDF resource model)}
495
%----------------------------------------------------------------------------
496
 
497
TBD
498
 
499
%----------------------------------------------------------------------------
500
\section{BDPSCAN\_RES\_MODEL (Block Device PSCAN resource model)}
501
%----------------------------------------------------------------------------
502
 
503
TBD
504
 
505
%----------------------------------------------------------------------------
506
\section{PC\_RES\_MODEL (Priority Ceiling Resource Model)}
507
%----------------------------------------------------------------------------
508
 
509
\begin{tt}
510
\begin{verbatim}
511
typedef struct {
512
    RES_MODEL r;
513
    DWORD priority;
514
} PC_RES_MODEL;
515
\end{verbatim}
516
\end{tt}
517
 
518
This Resource Model signal to the Priority Ceiling (PC) Module
519
that the task may use the PC protocol for some mutexes.
520
 
521
Note that the PC Module consider the tasks created without using
522
this resource models to have priority = MAX\_DWORD (the lowest).
523
 
524
The macro that can be used to setup the Resource Model are the
525
following:
526
 
527
\texttt{PC\_res\_default\_model(res, prio) }
528
 
529
Initializes a PC\_RES\_MODEL with a priority equal to prio.
530
 
531
\texttt{PC\_res\_def\_level(res,l)}
532
 
533
Set the Model level to l (in a way similar to what happens to task
534
models).
535
 
536
%----------------------------------------------------------------------------
537
\section{SRP\_RES\_MODEL (Stack Resource Policy resource model)}
538
%----------------------------------------------------------------------------
539
 
540
\begin{tt}
541
\begin{verbatim}
542
typedef struct {
543
    RES_MODEL r;
544
    DWORD preempt;
545
} SRP_RES_MODEL;
546
\end{verbatim}
547
\end{tt}
548
 
549
This Resource Model signal to the Stack Resource Policy (PC)
550
Module that the task will use the SRP protocol.
551
 
552
Note that the SRP Module does not influence the schedule of any
553
task that did not pass a SRP\_RES\_MODEL at its creation. The SRP
554
Module uses another resource model that is embedded into the mutex
555
structure. See \texttt{modules/srp/srp.c} for details.
556
 
557
The macro that can be used to setup the Resource Model are the
558
following:
559
 
560
\texttt{SRP\_res\_default\_model(res, pre) }
561
 
562
Initializes a SRP\_RES\_MODEL with a preemption level equal to
563
prio.
564
 
565
\texttt{SRP\_res\_def\_level(res,l)}
566
 
567
Set the Model level to l (in a way similar to what happens to task
568
models).
569
 
570
%----------------------------------------------------------------------------
571
\chapter{Mutex attributes}
572
%----------------------------------------------------------------------------
573
 
574
Every mutex attribute encode a particular mutex protocol, and one
575
of them must be passed to the mutex\_init() primitive to specify
576
the protocol used by a particular mutex. The following paragraphs
577
describe in detail the mutex attributes. Their definitions can be
578
found in \texttt{include/kernel/model.h}. Examples of use of mutex
579
attributes can be found later in this document.
580
 
581
%----------------------------------------------------------------------------
582
\section{PI\_mutexattr\_t (Priority Inheritance Mutex Attribute)}
583
%----------------------------------------------------------------------------
584
 
585
\texttt{typedef mutexattr\_t PI\_mutexattr\_t;}
586
 
587
The Priority Ceiling Mutex Attribute.
588
 
589
You can initialize that attribute using the static initializer
590
\texttt{PI\_MUTEXATTR\_INITIALIZER} or calling the macro
591
 
592
\texttt{PI\_mutexattr\_default(a)}
593
 
594
where a is the mutex attribute.
595
 
596
%----------------------------------------------------------------------------
597
\section{NPP\_mutexattr\_t (Non Preemptive Protocol Mutex Attribute)}
598
%----------------------------------------------------------------------------
599
 
600
\texttt{typedef mutexattr\_t NPP\_mutexattr\_t;}
601
 
602
The Non Preemptive Protocol Mutex Attribute. You can initialize
603
that attribute using the static initializer
604
\texttt{NPP\_MUTEXATTR\_INITIALIZER} or calling the macro
605
 
606
\texttt{NPP\_mutexattr\_default(a)}
607
 
608
where a is the mutex attribute.
609
 
610
%----------------------------------------------------------------------------
611
\section{PC\_mutexattr\_t (Priority Ceiling Mutex Attribute)}
612
%----------------------------------------------------------------------------
613
 
614
\texttt{typedef struct \{ mutexattr\_t a; DWORD ceiling; \}
615
PC\_mutexattr\_t;}
616
 
617
The Priority Ceiling Mutex Attribute.
618
 
619
You can initialize that attribute using the static initializer
620
\texttt{PC\_MUTEXATTR\_INITIALIZER} or calling the macro
621
 
622
\texttt{PC\_mutexattr\_default(at,c) }
623
 
624
where at is the mutex attribute, and c is the ceiling of the
625
mutex.
626
 
627
%----------------------------------------------------------------------------
628
\section{SRP\_mutexattr\_t (Stack Resource Policy Mutex Attribute)}
629
%----------------------------------------------------------------------------
630
 
631
\texttt{typedef mutexattr\_t SRP\_mutexattr\_t;}
632
 
633
The Stack Resource Policy Mutex Attribute. You can initialize that
634
attribute using the static initializer
635
\texttt{SRP\_MUTEXATTR\_INITIALIZER} or calling the macro
636
 
637
\texttt{SRP\_mutexattr\_default(a) }
638
 
639
where at is the mutex attribute.
640
 
641
%----------------------------------------------------------------------------
642
\section{NOP\_mutexattr\_t (No Protocol Mutex Attribute)}
643
%----------------------------------------------------------------------------
644
 
645
\texttt{typedef mutexattr\_t NOP\_mutexattr\_t;}
646
 
647
The No Protocol Mutex Attribute.
648
 
649
You can initialize that attribute using the static initializer
650
\texttt{NOP\_MUTEXATTR\_INITIALIZER} or calling the macro
651
 
652
\texttt{NOP\_mutexattr\_default(a) }
653
 
654
where at is the mutex attribute.
655
 
656
%----------------------------------------------------------------------------
657
\section{NOPM\_mutexattr\_t (No Protocol Multiple lock Mutex Attribute)}
658
%----------------------------------------------------------------------------
659
 
660
typedef mutexattr\_t NOPM\_mutexattr\_t;
661
 
662
The No Protocol Multiple lock Mutex Attribute. You can initialize
663
that attribute using the static initializer
664
\texttt{NOPM\_MUTEXATTR\_INITIALIZER} or calling the macro
665
 
666
\texttt{NOPM\_mutexattr\_default(a) }
667
 
668
where at is the mutex attribute.
669
 
670
%----------------------------------------------------------------------------
671
\chapter{Scheduling algorithms}
672
%----------------------------------------------------------------------------
673
 
674
%----------------------------------------------------------------------------
675
\section{DUMMY}
676
%----------------------------------------------------------------------------
677
 
678
\paragraph{Task Models Accepted:}
679
 
680
\begin{description}
681
\item [DUMMY\_TASK\_MODEL]- This Model is used only at system
682
startup to register the dummy task. It cannot be used by the other
683
modules.
684
\end{description}
685
 
686
\paragraph{Description:}
687
 
688
This Module implements a \texttt{dummy} task. A dummy task is a
689
task like all the other task that simply does an infinite loop,
690
does nothing inside.
691
 
692
Why we need such a Module? Look at the Scheduling Module
693
Architecture: when the Kernel needs to schedule a task, it asks to
694
all the registered modules if they have a task to schedule. The
695
hyphotesis is that there must be ALWAYS a task to schedule. The
696
dummy Scheduling Modules is used to register a module that have
697
always a task to schedule (the dummy task).
698
 
699
The dummy Module is not needed if you can ensure that there will
700
always be a task to schedule.
701
 
702
\paragraph{Exceptions Raised:}
703
 
704
\begin{description}
705
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
706
guest operation is called, the exception is raised. \item
707
[XUNVALID\_DUMMY\_OP]The dummy task can't be created, or
708
activated, or another (strange) problem occurred.
709
\end{description}
710
 
711
\paragraph{Usage:}
712
 
713
Usually the Dummy Module is the LAST scheduling module registered
714
in the function
715
 
716
\texttt{\_\_kernel\_register\_levels\_\_}.
717
 
718
Just insert the following line into
719
\texttt{\_\_kernel\_register\_levels\_\_} to register the Module:
720
 
721
\texttt{dummy\_register\_level();}
722
 
723
If you have a CPU where the HLT instruction works, you can use the
724
define \texttt{\_\_HLT\_WORKS\_\_}. If that \texttt{\#define} is
725
defined, the idle loop of the \texttt{dummy} task will use
726
\texttt{HLT}, maybe saving power.
727
 
728
\paragraph{Files:}
729
 
730
\texttt{modules/dummy/*}
731
 
732
\paragraph{Implementation hints:}
733
 
734
You can look at the code to learn how to create a new task at
735
startup using a \texttt{RUNLEVEL\_INIT} function.
736
 
737
%----------------------------------------------------------------------------
738
\section{IntDrive Interrupt Server}
739
%----------------------------------------------------------------------------
740
 
741
\input{intserver.tex}
742
 
743
\paragraph{Files:}
744
 
745
\texttt{modules/intdrive/*}
746
 
747
%----------------------------------------------------------------------------
748
\subsection{Implementation}
749
%----------------------------------------------------------------------------
750
 
751
\begin{intest}
752
INTDRIVE\_register\_level \index{INTDRIVE\_register\_level}
753
\end{intest}
754
 
755
\begin{description}
756
\item [\textbf{LEVEL INTDRIVE\_register\_level(TIME capacity, TIME q\_theta, int
757
U, int flags);}]
758
\item [\textbf{Description:}]This function registers the IntDrive module at
759
initialization time. This model should be usually registered as the first module
760
in the \texttt{\_\_kernel\_register\_levels\_\_} function.
761
\item [\textbf{Parameters:}]~
762
 
763
\begin{itemize}
764
\item \textbf{capacity}: the server capacity;
765
\item \textbf{q\_theta}: the server threshold;
766
\item \textbf{U}: the maximum bandwidth consumed by the server;
767
\item \textbf{flags}: a set of configuration options. Supported values are:
768
 
769
\begin{itemize}
770
\item \textbf{INTDRIVE\_CHECK\_WCET}: when a WCET overrun occurs, an exception
771
is raised.
772
\end{itemize}
773
 
774
\end{itemize}
775
 
776
\end{description}
777
 
778
\begin{intest}
779
INTDRIVE\_usedbandwidth \index{INTDRIVE\_usedbandwidth}
780
\end{intest}
781
 
782
\begin{description}
783
\item [\textbf{bandwidth\_t INTDRIVE\_usedbandwidth(LEVEL l);}]
784
\item [\textbf{Description:}]returns the bandwidth used by the IntDrive.
785
\end{description}
786
 
787
\begin{intest}
788
INTDRIVE\_set\_q\_theta \index{INTDRIVE\_set\_q\_theta}
789
\end{intest}
790
 
791
\begin{description}
792
\item [\textbf{TIME INTDRIVE\_set\_q\_theta(LEVEL l, TIME new\_q\_theta);}]
793
\item [\textbf{Description:}]changes the \texttt{q\_theta} value. Notice that
794
changing \texttt{q\_theta} does not affect the bandwidth used by the server, nor
795
the schedulability conditions for the application tasks.
796
\end{description}
797
 
798
\textbf{ATTENTION:} notice that IntDrive is based on the Lipari-Bini
799
hierarchical framework proposed in \cite{Lip03}. Therefore, the schedulability
800
tests used by the current scheduling modules are no more sufficient to guarantee
801
the schedulability. See \cite{Lip03} and \cite{Fac05} for more details.
802
 
803
%----------------------------------------------------------------------------
804
\section{EDF (Earliest Deadline First) }
805
%----------------------------------------------------------------------------
806
 
807
\paragraph{Task Models Accepted:}
808
 
809
\begin{description}
810
\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic). The
811
\texttt{wcet} and \texttt{mit} must be != 0. These parameters will
812
be used to set the Worst Case Execution Time (WCET) and Period of
813
the tasks. The \texttt{periodicity} can be either
814
\texttt{PERIODIC} or \texttt{APERIODIC}. drel field must be <=
815
mit.
816
 
817
\begin{description}
818
\item [NOTE:]A Relative Deadline of 0 is interpreted as MIT. \item
819
[NOTE:]The utilization of the task is computed as wcet/drel. \item
820
[NOTE:]\textbf{offset} field specifies a release offset relative
821
to task\_activate or group\_activate.
822
\end{description}
823
 
824
\end{description}
825
 
826
\paragraph{Guest Models Accepted:}
827
 
828
\begin{description}
829
\item [JOB\_TASK\_MODEL]- A single guest task activation. It must
830
be identified by an absolute deadline and a period. The
831
\texttt{period} field is ignored. \item [Description:]This module
832
schedules periodic and sporadic tasks based on their absolute
833
deadlines. The task guarantee is based on a simple utilization
834
approach. The utilization factor of a task is computed as
835
wcet/drel. (By default, drel = mit.) A periodic task must only be
836
activated once; subsequent activations are triggered by an
837
internal timer. By contrast, an sporadic task must be explicitely
838
activated for each instance. NO GUARANTEE is performed on guest
839
tasks. The guarantee must be performed by the level that inserts
840
guest tasks in the EDF level.
841
\end{description}
842
 
843
\paragraph{Exceptions raised:}
844
 
845
\begin{description}
846
\item [XDEADLINE\_MISS]If a task misses its deadline and the
847
\texttt{EDF\_ENABLE\_DL\_EXCEPTION} flag is set, this exception is
848
raised. Note that after raising that exception, the task can't be
849
put in execution again. The safest thing to do is to Shut Down the
850
system! This exception is also raised if a guest task miss its
851
deadline. \item [XWCET\_VIOLATION]If a task executes longer than
852
its declared wcet and the \texttt{EDF\_ENABLE\_WCET\_EXCEPTION}
853
flag is set, this exception is raised and the task is put in the
854
\texttt{EDF\_WCET\_VIOLATED} state. To reactivate it, use
855
\texttt{EDF\_task\_activate} via task\_activate or manage directly
856
the EDF data structure. Note that the exception is not handled
857
properly, an \texttt{XDEADLINE\_MISS} exception will also be
858
raised at the period end. \item [XACTIVATION]If a sporadic task is
859
activated with a rate that is greather than the rate declared in
860
the model, this exception is raised and the task is NOT activated.
861
This exception is also raised if we are trying to activate a
862
periodic task stopped with \texttt{task\_delay}. \item
863
[XUNVALID\_GUEST]This exception is raised if a
864
\texttt{guest\_endcycle} or \texttt{guest\_sleep} guest calls are
865
called.
866
\end{description}
867
 
868
\paragraph{Usage:}
869
 
870
Usually this model is registered as one of the first Modules in
871
the \texttt{\_\_kernel\_register\_levels\_\_} function. To
872
register this module, just put this line into the
873
\texttt{\_\_kernel\_register\_levels\_\_} function:
874
 
875
\texttt{EDF\_register\_level(flag);}
876
 
877
where \texttt{flag} can be:
878
 
879
\begin{description}
880
\item [(No\_flags\_enabled)]- Deadline and wcet overruns are
881
ignored. Pending periodic jobs are queued and are eventually
882
scheduled with correct deadlines according to their original
883
arrival times. Sporadic tasks that arrive to often aresimply
884
dropped. \item [EDF\_ENABLE\_DL\_CHECK]- When a deadline overrun
885
occurs, the dl\_miss counter of the task is increased. Same
886
behavior for pending jobs as above. \item
887
[EDF\_ENABLE\_WCET\_CHECK]- When a wcet overrun occurs, the
888
wcet\_miss counter of the task is increased. Same behavior for
889
pending jobs as above. \item [EDF\_ENABLE\_DL\_EXCEPTION]- When a
890
deadline overrun occurs, an exception is raised. \item
891
[EDF\_ENABLE\_WCET\_EXCEPTION]- When a wcet overrun occurs, an
892
exception is raised. \item [EDF\_ENABLE\_ACT\_EXCEPTION]When a
893
periodic or sporadic task is activated too often, an exception is
894
raised.
895
\end{description}
896
 
897
The functions \texttt{EDF\_get\_dl\_miss},
898
\texttt{EDF\_get\_wcet\_miss}, \texttt{EDF\_get\_act\_miss}, and
899
EDF\_get\_nact can be used to find out the number of missed
900
deadlines, the number of wcet overruns, the number of skipped
901
activations, and the number of currently queued periodic
902
activations.
903
 
904
\begin{description}
905
\item [EDF\_DISABLE\_ALL]- All checks disabled \item
906
[EDF\_ENABLE\_GUARANTEE]- Guarantee test enabled.
907
 
908
When enabled, an acceptance test
909
($\sum\frac{WCET_{i}}{Period_{i}}<1$) is performed; Deadline miss
910
exceptions are raised in any case.
911
 
912
\item [EDF\_ENABLE\_ALL]- All checks enabled
913
\end{description}
914
 
915
The EDF Module provides also addictional functions:
916
 
917
\begin{description}
918
\item [\textbf{bandwidth\_t EDF\_usedbandwidth(LEVEL l);}]
919
It returns the used bandwidth, where l is the level at which the
920
EDF Module is registered.
921
\item [\textbf{int EDF\_get\_dl\_miss(PID p);}]
922
It returns the deadline miss counter.
923
\item [\textbf{int EDF\_get\_wcet\_miss(PID p);}]
924
It returns the wcet miss counter.
925
\item [\textbf{int EDF\_get\_act\_miss(PID p);}]
926
It returns the activation miss counter.
927
\end{description}
928
 
929
\paragraph{Files:}
930
 
931
\texttt{modules/edf/*}
932
 
933
\paragraph{Implementation hints:}
934
 
935
It uses the CONTROL\_CAP field to keep track of the task execution
936
time. It implements a ZOMBIE state for ended tasks. It post a
937
single OSLib event for each task for deadline/reactivation/zombie
938
detection. The \texttt{guest\_endcycle} and \texttt{guest\_sleep}
939
guest calls are not implemented.
940
 
941
\begin{description}
942
\item [NOTES:]~
943
\end{description}
944
 
945
\begin{enumerate}
946
\item Relative deadlines \textbf{drel <= mit} may be specified.
947
\item An offset
948
>
949
 
950
time. To synchronize a group of tasks, assign suitable offsets and
951
then use the group\_activate function. \item This level doesn't
952
manage the main task. \item The level uses the priority and
953
timespec\_priority fields. \item The guest tasks don't provide the
954
guest\_endcycle function.
955
\end{enumerate}
956
 
957
%----------------------------------------------------------------------------
958
\section{POSIX (fixed priority FIFO/RR scheduler)}
959
%----------------------------------------------------------------------------
960
 
961
\paragraph{Task Models Accepted:}
962
 
963
\begin{description}
964
\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. If the
965
\texttt{inherit} field is set to \texttt{NRT\_INHERIT\_SCHED}, the
966
scheduling properties of the running task are inherited (as
967
required by the POSIX standard). Else, the \texttt{slice} field is
968
used to set the time slice of the task (if \texttt{slice} is set
969
to 0, the default value is used); the \texttt{weight} field is
970
used to set the task priority; the \texttt{policy} field is used
971
to set the policy of the task (\texttt{NRT\_RR\_POLICY} for
972
Round-Robin or \texttt{NRT\_FIFO\_POLICY} for FIFO); the
973
\texttt{arrivals} field can be set to \texttt{SAVE\_ARRIVALS} or
974
\texttt{SKIP\_ARRIVALS}.
975
\end{description}
976
 
977
\paragraph{Description:}
978
 
979
This module schedule his tasks following the POSIX scheduler as
980
described by the standard IEEE 1003.1c. This Module is typically
981
used by the POSIX primitives for their scheduling pourposes. For
982
example, the pthread\_create function calls the task\_createn
983
function passing a NRT\_TASK\_MODEL filled with the correct
984
parameters.
985
 
986
The Module can create the \texttt{\_\_init\_\_} task, that is
987
typically used to call the Standard C \texttt{main()} function.
988
 
989
\paragraph{Exceptions Raised:}
990
 
991
\begin{description}
992
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
993
guest operation is called, the exception is raised.
994
\end{description}
995
 
996
\paragraph{Usage:}
997
 
998
To register this module, just put this line into the
999
\texttt{\_\_kernel\_register\_levels\_\_} function:
1000
 
1001
\texttt{POSIX\_register\_level(slice, createmain, mb,
1002
prioritylevels);}
1003
 
1004
where \texttt{slice} is the default timeslice for the POSIX tasks scheduled
1005
using the Round-Robin policy, \texttt{createmain} is \texttt{POSIX\_MAIN\_YES}
1006
or \texttt{POSIX\_MAIN\_NO} if you want that the POSIX Module creates or not the
1007
\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct multiboot\_info
1008
*} the Kernel passed to the \texttt{\_\_kernel\_register\_levels\_\_}
1009
function, and prioritylevels are the number of different priority levels
1010
supported by the Module \footnote{The POSIX standard requires a minimum of 32
1011
priority levels}.
1012
 
1013
The POSIX Module provides also some addictional function, that are
1014
used to implement the behaviour of various POSIX primitives:
1015
 
1016
\texttt{int POSIX\_sched\_yield(LEVEL l);}
1017
 
1018
This function forces the running task to go to his queue tail,
1019
then calls the scheduler and changes the context. It is used by
1020
the \texttt{sched\_yield()} primitive.
1021
 
1022
\texttt{int POSIX\_get\_priority\_max(LEVEL l);}
1023
 
1024
This function returns the maximum level allowed for the POSIX
1025
level. It is used by the \texttt{sched\_get\_priority()}
1026
primitive.
1027
 
1028
\texttt{int POSIX\_rr\_get\_interval(LEVEL l);}
1029
 
1030
This function returns the default timeslice for the POSIX level.
1031
It is used by the \texttt{sched\_rr\_get\_interval()} primitive.
1032
 
1033
\texttt{int POSIX\_getschedparam(LEVEL l, PID p, int *policy,
1034
int *priority);}
1035
 
1036
This functions returns some paramaters of a task; \texttt{policy}
1037
is set to \texttt{NRT\_RR\_POLICY} or \texttt{NRT\_FIFO\_POLICY};
1038
priority is set in the range \texttt{{[}0..prioritylevels{]}}. The
1039
function returns \texttt{ENOSYS} or \texttt{ESRCH} if there are
1040
problems. The function must be called with interrupts disabled and
1041
is used by the \texttt{pthread\_getschedparam()} primitive.
1042
 
1043
\texttt{int POSIX\_setschedparam(LEVEL l, PID p, int policy, int
1044
priority);}
1045
 
1046
This functions sets some paramaters of a task; \texttt{policy}
1047
must be set to \texttt{NRT\_RR\_POLICY} or
1048
\texttt{NRT\_FIFO\_POLICY}; priority must be set in the range
1049
\texttt{{[}0..prioritylevels{]}}. The function returns
1050
\texttt{ENOSYS}, \texttt{EINVAL} or \texttt{ESRCH} if there are
1051
problems. The function must be called with interrupts disabled and
1052
is used by the \texttt{pthread\_setschedparam() primitive}.
1053
 
1054
\paragraph{Files:}
1055
 
1056
\texttt{modules/posix/*}
1057
 
1058
\paragraph{Implementation hints:}
1059
 
1060
The implementation of this module is directly derived from the RR
1061
scheme.
1062
 
1063
%----------------------------------------------------------------------------
1064
\section{RM (Rate Monotonic)}
1065
%----------------------------------------------------------------------------
1066
 
1067
\paragraph{Task
1068
Models Accepted:}
1069
 
1070
\begin{description}
1071
\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic). The
1072
\texttt{wcet} and \texttt{mit} must be != 0. These parameters will
1073
be used to set the Worst Case Execution Time (WCET) and Period of
1074
the tasks. The \texttt{periodicity} can be either
1075
\texttt{PERIODIC} or \texttt{APERIODIC}. The Relative Deadline is
1076
ignored (deadlines are equal to periods).
1077
\end{description}
1078
 
1079
\paragraph{Guest Models Accepted:}
1080
 
1081
\begin{description}
1082
\item [JOB\_TASK\_MODEL]- A single guest task activation. It must
1083
be identified by an absolute deadline and a period.
1084
\end{description}
1085
 
1086
\paragraph{Description:}
1087
 
1088
This module schedule his tasks following the classic RM scheme as
1089
described by Liu and Layland. The task guarantee is based on the
1090
factor utilization approach. The tasks scheduled are periodic and
1091
sporadic. The sporadic tasks are like hard task with periodicity
1092
set to \texttt{APERIODIC}; they are guaranteed as a periodic task
1093
with period equal to the minimum interarrival time. All the task
1094
are put in a queue and the scheduling is based on the period
1095
value.
1096
 
1097
No Guarantee is performed on guest tasks. The guarantee must be
1098
performed by the level that inserts guest tasks in the RM level.
1099
 
1100
If a RM task does not respect its WCET and deadline constraints,
1101
then the Module will raise an exception. Note that the deadline
1102
exception is not recoverable, so the Module will be in an
1103
inconsistent state after a Deadline Miss. Deadline Miss in this
1104
Module are treated as unrecoverable errors.
1105
 
1106
If you try to activate a Periodic task that is not sleeping,
1107
nothing happens.
1108
 
1109
\paragraph{Exceptions Raised:}
1110
 
1111
\begin{description}
1112
\item [XDEADLINE\_MISS]If a task miss his deadline, the exception
1113
is raised. Note that after raising that exception, the task can't
1114
be put in execution again. The safest thing to do is to Shut Down
1115
the system! This exception is also raised if a guest task miss its
1116
deadline. \item [XWCET\_VIOLATION]If a task doesn't end the
1117
current cycle before if consume the \texttt{wcet}, an exception is
1118
raised, and the task is put in the \texttt{RM\_WCET\_VIOLATED}
1119
state. To reactivate it, use \texttt{RM\_task\_activate} via
1120
task\_activate or manage directly the RM data structure. Note that
1121
the exception is not handled properly, an \texttt{XDEADLINE\_MISS}
1122
exception will also be raised at the period end. \item
1123
[XACTIVATION]If a sporadic task is activated with a rate that is
1124
greather than the rate declared in the model, this exception is
1125
raised and the task is NOT activated. This exception is also
1126
raised if we are trying to activate a periodic task stopped with
1127
\texttt{task\_sleep} before the deadline in which the
1128
\texttt{task\_sleep} is called. \item [XUNVALID\_GUEST]This
1129
exception is raised if a \texttt{guest\_endcycle} or
1130
\texttt{guest\_sleep} guest calls are called.
1131
\end{description}
1132
 
1133
\paragraph{Usage:}
1134
 
1135
Usually this model is registered as one of the first Modules in
1136
the \texttt{\_\_kernel\_register\_levels\_\_} function. To
1137
register this module, just put this line into the
1138
\texttt{\_\_kernel\_register\_levels\_\_} function:
1139
 
1140
\texttt{RM\_register\_level(flag);}
1141
 
1142
where \texttt{flag} can be:
1143
 
1144
Restrictions and special features:
1145
 
1146
\begin{description}
1147
\item [(No\_flags\_enabled)]- Deadline and wcet overruns are
1148
ignored. Pending periodic jobs are queued and are eventually
1149
scheduled with correct deadlines according to their original
1150
arrival times. Sporadic tasks that arrive to often are simply
1151
dropped. \item [RM\_ENABLE\_DL\_CHECK]- When a deadline overrun
1152
occurs, the dl\_miss counter of the task is increased. Same
1153
behavior for pending jobs as above. \item
1154
[RM\_ENABLE\_WCET\_CHECK]- When a wcet overrun occurs, the
1155
wcet\_miss counter of the task is increased. Same behavior for
1156
pending jobs as above. \item [RM\_ENABLE\_DL\_EXCEPTION]- When a
1157
deadline overrun occurs, an exception is raised. \item
1158
[RM\_ENABLE\_WCET\_EXCEPTION]- When a wcet overrun occurs, an
1159
exception is raised. \item [RM\_ENABLE\_ACT\_EXCEPTION]When a
1160
periodic or sporadic task is activated too often, an exception is
1161
raised. \item [RM\_DISABLE\_ALL]- Wcet and Guarantee test disabled
1162
\item [RM\_ENABLE\_GUARANTEE]- Guarantee test enabled (when
1163
enabled, an acceptance test ($\sum\frac{WCET_{i}}{Period_{i}}<1$)
1164
is performed; Deadline miss exceptions are raised in any case.
1165
Note that, for reasons of semplicity, the test that has been
1166
implemented IS NOT the test for RM, but only a simple acceptance
1167
test. \item [RM\_ENABLE\_ALL]- Wcet and Guarantee test enabled
1168
\end{description}
1169
The RM Module provides also addictional functions:
1170
 
1171
\begin{description}
1172
\item [\textbf{bandwidth\_t RM\_usedbandwidth(LEVEL l);}]
1173
It returns the used bandwidth, where l is the level at which the
1174
RM Module is registered.
1175
\item [\textbf{int RM\_get\_dl\_miss(PID p);}]
1176
It returns the deadline miss counter.
1177
\item [\textbf{int RM\_get\_wcet\_miss(PID p);}]
1178
It returns the wcet miss counter.
1179
\item [\textbf{int RM\_get\_act\_miss(PID p);}]
1180
It returns the activation miss counter.
1181
\end{description}
1182
 
1183
\paragraph{Files:}
1184
 
1185
\texttt{modules/rm/*}
1186
 
1187
\paragraph{Implementation hints:}
1188
 
1189
The implementation of this module is very similar to the
1190
implementation of the EDF Module.
1191
 
1192
\paragraph{NOTE}
1193
 
1194
\begin{enumerate}
1195
\item Relative deadlines drel <= mit may be specified. \item An offset > 0 will
1196
delay the activation of the task by the same amount of time. To synchronize a
1197
group of tasks, assign suitable \item offsets and then use the group\_activate
1198
function. \item This level doesn't manage the main task. \item The level uses
1199
the priority and timespec\_priority fields. \item The guest tasks don't provide
1200
the guest\_endcycle function. \item At init time, the user can specify the
1201
behavior in case ofdeadline and wcet overruns. The following flags are
1202
available:
1203
\end{enumerate}
1204
 
1205
%----------------------------------------------------------------------------
1206
\section{RR (Round Robin)}
1207
%----------------------------------------------------------------------------
1208
 
1209
\paragraph{Task Models Accepted:}
1210
 
1211
\begin{description}
1212
\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. The \texttt{slice}
1213
field is used to set the time slice of the task. If \texttt{slice}
1214
is set to 0, the default value is used. The \texttt{weight},
1215
\texttt{arrivals}, \texttt{policy} and \texttt{inherit} fields are
1216
ignored.
1217
\end{description}
1218
 
1219
\paragraph{Description:}
1220
 
1221
This module schedule his tasks following the classic round-robin
1222
scheme. The default timeslice is given at registration time and is
1223
a a per-task specification. The default timeslice is used if the
1224
\texttt{slice} field in the \texttt{NRT\_TASK\_MODEL} is 0.
1225
 
1226
If a task is activated when it is already active (its instance is
1227
not yet finished on a \texttt{task\_endcycle} or
1228
\texttt{task\_sleep}), nothing happens.
1229
 
1230
If you need to remember the pending activations you can use the
1231
\texttt{RR2} scheduling module.
1232
 
1233
The Module can create the \texttt{\_\_init\_\_} task, that is
1234
typically used to call the Standard C \texttt{main()} function.
1235
 
1236
\paragraph{Exceptions Raised:}
1237
 
1238
\begin{description}
1239
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1240
guest operation is called, the exception is raised.
1241
\end{description}
1242
 
1243
\paragraph{Usage:}
1244
 
1245
To register this module, just put this line into the
1246
\texttt{\_\_kernel\_register\_levels\_\_} function:
1247
 
1248
\texttt{RR\_register\_level(slice, createmain, mb);}
1249
 
1250
where \texttt{slice} is the default timeslice for the RR tasks,
1251
\texttt{createmain} is \texttt{RR\_MAIN\_YES} or
1252
\texttt{RR\_MAIN\_NO} if you want that RR creates or not the
1253
\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct
1254
multiboot\_info *} the Kernel passed to the
1255
\texttt{\_\_kernel\_register\_levels\_\_} function.
1256
 
1257
You can use more than one RR Scheduling Module to simulate a
1258
Multilevel scheduling policy. The RR Module does not add any
1259
addictional function.
1260
 
1261
\paragraph{Files:}
1262
 
1263
\texttt{modules/rr/*}
1264
 
1265
\paragraph{Implementation hints:}
1266
 
1267
This is one of the simplest scheduling module. It can be useful to
1268
learn how to create the \_\_init\_\_ task at startup time. It uses
1269
the CONTROL\_CAP field. It supports negative task capacities (that
1270
can happen when using shadows; for that reason, the scheduler has
1271
a while inside, and the timeslices ar added and not assigned). No
1272
Guarantee is performed at task creation.
1273
 
1274
%----------------------------------------------------------------------------
1275
\section{RR2 (Round Robin with pending activations)}
1276
%----------------------------------------------------------------------------
1277
 
1278
\paragraph{Task Models Accepted:}
1279
 
1280
\begin{description}
1281
\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. The \texttt{slice}
1282
field is used to set the time slice of the task. If \texttt{slice}
1283
is set to 0, the default value is used. The \texttt{arrivals}
1284
field is used to say if the activations have to be saved
1285
(\texttt{SAVE\_ARRIVALS}) or skipped (\texttt{SKIP\_ARRIVALS}).
1286
The \texttt{weight}, \texttt{policy} and \texttt{inherit} fields
1287
are ignored.
1288
\end{description}
1289
 
1290
\paragraph{Description:}
1291
 
1292
The Module is identical to the RR Scheduling Module, except that
1293
task activations can be saved if a task was created with the
1294
arrivals field equal to SAVE\_ARRIVALS.
1295
 
1296
\paragraph{Exceptions Raised:}
1297
 
1298
See the RR Scheduling Module.
1299
 
1300
\paragraph{Usage:}
1301
 
1302
See the RR Scheduling Module, changing every occurrence of RR with
1303
RR2.
1304
 
1305
\paragraph{Files:}
1306
 
1307
\texttt{modules/rr2/*}
1308
 
1309
\paragraph{Implementation hints:}
1310
 
1311
With respect to the RR Scheduling Module, it adds a pending
1312
activation counter (nact) for each task.
1313
 
1314
%----------------------------------------------------------------------------
1315
\section{RRSOFT (hard/SOFT Round Robin)}
1316
%----------------------------------------------------------------------------
1317
 
1318
\paragraph{Task Models Accepted:}
1319
 
1320
\begin{description}
1321
\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic).
1322
Only the periodicity and the mit parameters are used to know if
1323
the task is periodic/sporadic and to set the task period. The task
1324
timeslice is set to the default value. \item [SOFT\_TASK\_MODEL]-
1325
Soft Tasks (Periodic and Sporadic). Only the periodicity, arrivals
1326
and period parameters are used to know if the task is
1327
periodic/sporadic, to set the task period and to know if the
1328
pending activations should be saved. The task timeslice is set to
1329
the default value. \item [NRT\_TASK\_MODEL]- Non-Realtime Tasks.
1330
The \texttt{slice} field is used to set the time slice of the
1331
task. If \texttt{slice} is set to 0, the default value is used.
1332
The \texttt{arrivals} field is used to say if the activations have
1333
to be saved (\texttt{SAVE\_ARRIVALS}) or skipped
1334
(\texttt{SKIP\_ARRIVALS}). The \texttt{weight}, \texttt{policy}
1335
and \texttt{inherit} fields are ignored.
1336
\end{description}
1337
 
1338
\paragraph{Description:}
1339
 
1340
This module can be used as a polymorphic module that can accept
1341
Hard, Soft or NRT Task Models. The policy used to schedule the
1342
tasks is the same of RR2, plus the fact that SOFT and HARD tasks
1343
can be periodic, so they can be automatically activated at each
1344
instance.
1345
 
1346
This Module is very useful if you want to replace another Module
1347
that accept Hard of Soft tasks with a round-robin scheduler, for
1348
example to compare a scheduling algorithm with the plain round
1349
robin.
1350
 
1351
\paragraph{Exceptions Raised:}
1352
 
1353
\begin{description}
1354
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1355
guest operation is called, the exception is raised.
1356
\end{description}
1357
 
1358
\paragraph{Usage:}
1359
 
1360
To register this module, just put this line into the
1361
\texttt{\_\_kernel\_register\_levels\_\_} function:
1362
 
1363
\texttt{RRSOFT\_register\_level(slice, createmain, mb, models);}
1364
 
1365
where \texttt{slice} is the default timeslice for the RR tasks,
1366
\texttt{createmain} is \texttt{RR\_MAIN\_YES} or
1367
\texttt{RR\_MAIN\_NO} if you want that RR creates or not the
1368
\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct
1369
multiboot\_info *} the Kernel passed to the
1370
\texttt{\_\_kernel\_register\_levels\_\_} function, and
1371
\texttt{models} specifies the kind of Models accepted by the
1372
Module. The \texttt{models} value can be an or of the values of
1373
the following constants: \texttt{RRSOFT\_ONLY\_HARD},
1374
\texttt{RRSOFT\_ONLY\_HARD}, \texttt{RRSOFT\_ONLY\_HARD}.
1375
 
1376
You can use more than one RR Scheduling Module to simulate a
1377
Multilevel scheduling policy. The RR Module does not add any
1378
addictional function.
1379
 
1380
\paragraph{Files:}
1381
 
1382
\texttt{modules/rrsoft/*}
1383
 
1384
\paragraph{Implementation hints:}
1385
 
1386
The implementation of the Module is similar to RR2 plus the
1387
implementation of the reactivation for periodic tasks.
1388
 
1389
%----------------------------------------------------------------------------
1390
\chapter{Aperiodic servers}
1391
%----------------------------------------------------------------------------
1392
 
1393
%----------------------------------------------------------------------------
1394
\section{CBS (Constant Bandwidth Server)}
1395
%----------------------------------------------------------------------------
1396
 
1397
\paragraph{Task Models Accepted:}
1398
 
1399
\begin{description}
1400
\item [SOFT\_TASK\_MODEL]- Soft Tasks (Periodic and Sporadic). The
1401
\texttt{met} and \texttt{period} must be != 0. These parameters
1402
will be used to set the Mean Execution Time (MET) and the Period
1403
of the tasks. The \texttt{periodicity} can be either
1404
\texttt{PERIODIC} or \texttt{APERIODIC}. The \texttt{arrivals}
1405
field can be either \texttt{SAVE\_ARRIVALS} or
1406
\texttt{SKIP\_ARRIVALS}. The \texttt{wcet} field is ignored (Worst
1407
case execution times are not used by CBS).
1408
\end{description}
1409
 
1410
\paragraph{Description:}
1411
 
1412
This module schedule his tasks following the CBS algorithm. The
1413
task guarantee is based on the factor utilization approach. The
1414
tasks scheduled are periodic and sporadic. The sporadic tasks are
1415
like hard task with periodicity set to \texttt{APERIODIC}. All the
1416
task are put as guest task in the scheduling queue of another
1417
Module (typically that Module is an EDF Module).
1418
 
1419
A CBS server is attached to each task, with the parameters passed
1420
in the \texttt{SOFT\_TASK\_MODEL}.
1421
 
1422
If you try to activate a Periodic task that is not sleeping, a pending
1423
activation is recorded \footnote{If the task was created with the
1424
\texttt{SAVE\_ARRIVALS} option... }.
1425
 
1426
\paragraph{Exceptions Raised:}
1427
 
1428
\begin{description}
1429
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1430
guest operation is called, the exception is raised.
1431
\end{description}
1432
 
1433
\paragraph{Usage:}
1434
 
1435
To register this module, just put this line into the
1436
\texttt{\_\_kernel\_register\_levels\_\_} function:
1437
 
1438
\texttt{CBS\_register\_level(flag, master);}
1439
 
1440
where \texttt{flag} can be:
1441
 
1442
\begin{description}
1443
\item [CBS\_DISABLE\_ALL]- Guarantee test disabled. \item
1444
[CBS\_ENABLE\_GUARANTEE]- Guarantee test enabled (when enabled, an
1445
acceptance test ($\sum\frac{met_{i}}{period_{i}}<1$) is performed;
1446
Deadline miss exceptions are raised in any case. \item
1447
[CBS\_ENABLE\_ALL]- Guarantee test enabled.
1448
\end{description}
1449
and \texttt{master} is the level to that the CBS is attached. At
1450
the moment, you can attach a CBS Module either to an \texttt{EDF}
1451
or an \texttt{EDFACT} Module. The CBS Module can be registered as
1452
the last scheduling Module after the \texttt{DUMMY} Module (this
1453
because the CBS Module does not use background time, and because
1454
when a CBS task is ready it is inserted in another queue!).
1455
 
1456
The CBS Module provides also an addictional function, that can be
1457
used to get the used bandwidth by the Module and the pending
1458
activations of a task. The prototypes of these function are:
1459
 
1460
\texttt{bandwidth\_t CBS\_usedbandwidth(LEVEL l);}
1461
 
1462
where l is the level at which the CBS Module is registered.
1463
 
1464
\texttt{int CBS\_get\_nact(LEVEL l, PID p);}
1465
 
1466
Returns the number of pending activations of a task. No control is
1467
done if the task is not a CBS task! (l is the level at which the
1468
CBS Module is registered, p is the PID of the task).
1469
 
1470
\paragraph{Files:}
1471
 
1472
\texttt{modules/cbs/*}
1473
 
1474
\paragraph{Implementation hints:}
1475
 
1476
CBS implementation is similar to the EDF implementation except
1477
that a capacity exaustion postpones a deadline, and that the
1478
deadline event is simply a reactivation. This is one of the only
1479
Modules where the \texttt{task\_eligible} task calls is defined
1480
non-void.
1481
 
1482
%----------------------------------------------------------------------------
1483
\section{HARD\_CBS}
1484
%----------------------------------------------------------------------------
1485
 
1486
This Module is very similar to the standard CBS, but it implements
1487
the Hard Reservation algorithm.
1488
 
1489
\begin{description}
1490
\item [Files:]\texttt{modules/hardcbs/*}
1491
\end{description}
1492
 
1493
%----------------------------------------------------------------------------
1494
\section{DS (Deferrable Server)}
1495
%----------------------------------------------------------------------------
1496
 
1497
\paragraph{Task Models Accepted:}
1498
 
1499
\begin{description}
1500
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
1501
\texttt{periodicity} can be only \texttt{APERIODIC}. The
1502
\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
1503
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
1504
\end{description}
1505
 
1506
\paragraph{Description:}
1507
 
1508
This module schedule its tasks following the Deferrable Server
1509
Algorithm. All the aperiodic requests are served on a FCFS basis.
1510
The Module can be configured to use only its budget or to also use
1511
the idle time left by the higher level Modules. The Module can be
1512
configured to save or skip task activations. The Module can be
1513
attached to either a RM or an EDF Module.
1514
 
1515
\paragraph{Exceptions Raised:}
1516
 
1517
\begin{description}
1518
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1519
guest operation is called, the exception is raised.
1520
\end{description}
1521
 
1522
\paragraph{Usage:}
1523
 
1524
To register this module, just put this line into the
1525
\texttt{\_\_kernel\_register\_levels\_\_} function:
1526
 
1527
\texttt{DS\_register\_level(flag, master, Cs, per);}
1528
 
1529
where \texttt{flag} can be:
1530
 
1531
\begin{description}
1532
\item [DS\_DISABLE\_ALL]- Guarantee test disabled; Background
1533
scheduling disabled. \item [DS\_ENABLE\_BACKGROUND]- Background
1534
scheduling enabled. \item [DS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
1535
test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
1536
is performed. This flag have to be used if the Module is attached
1537
to an EDF Module. \item [DS\_ENABLE\_ALL\_EDF]- EDF guarantee test
1538
enabled, Background scheduling disabled. \item
1539
[DS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
1540
an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
1541
have to be used if the Module is attached to a RM Module. \item
1542
[DS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
1543
scheduling disabled.
1544
\end{description}
1545
\texttt{master} is the level to that the DS Module is attached. At
1546
the moment, you can attach a DS Module either to an \texttt{EDF},
1547
\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
1548
\texttt{per} are the budget and the period of the deferrable
1549
server. If it is configured to do not use background time, the DS
1550
Module can be registered as the last scheduling Module after the
1551
\texttt{DUMMY} Module. Otherwise, it should be put in the middle
1552
of the list to catck the idle time left by higher level Modules.
1553
 
1554
The DS Module provides also an addictional function, that can be
1555
used to get the used bandwidth by the Module. The prototype of the
1556
function is:
1557
 
1558
\texttt{bandwidth\_t DS\_usedbandwidth(LEVEL l);}
1559
 
1560
where l is the level at which the DS Module is registered.
1561
 
1562
\paragraph{Files:}
1563
 
1564
\texttt{modules/ds/*}
1565
 
1566
\paragraph{Implementation hints:}
1567
 
1568
The DS Module uses a FIFO queue to enqueue the ready tasks. Only
1569
the first task is inserted into the queue of the Master Level. The
1570
Module does not use the CONTROL\_CAP field, but it handles its
1571
capacity event by itself. The budget of the module is recharged
1572
every DS period, and is kept into an internal data structure of
1573
the module, and not in the wcet and avail\_time fields of every
1574
task. Note that the idle time is recognized when the DS scheduler
1575
is called. In that case, no capacity event is posted. The
1576
implementation is very similar to the PS Module implementation.
1577
 
1578
%----------------------------------------------------------------------------
1579
\section{PS (Polling Server)}
1580
%----------------------------------------------------------------------------
1581
 
1582
\paragraph{Task Models Accepted:}
1583
 
1584
\begin{description}
1585
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
1586
\texttt{periodicity} can be only \texttt{APERIODIC}. The
1587
\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
1588
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
1589
\end{description}
1590
 
1591
\paragraph{Description:}
1592
 
1593
This module schedule its tasks following the Polling Server
1594
Algorithm. All the aperiodic requests are served on a FCFS basis.
1595
The Module can be configured to use only its budget or to also use
1596
the idle time left by the higher level Modules. The Module can be
1597
configured to save or skip task activations. The Module can be
1598
attached to either a RM or an EDF Module.
1599
 
1600
\paragraph{Exceptions Raised:}
1601
 
1602
\begin{description}
1603
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1604
guest operation is called, the exception is raised.
1605
\end{description}
1606
 
1607
\paragraph{Usage:}
1608
 
1609
To register this module, just put this line into the
1610
\texttt{\_\_kernel\_register\_levels\_\_} function:
1611
 
1612
\texttt{PS\_register\_level(flag, master, Cs, per);}
1613
 
1614
where \texttt{flag} can be:
1615
 
1616
\begin{description}
1617
\item [PS\_DISABLE\_ALL]- Guarantee test disabled; Background
1618
scheduling disabled. \item [PS\_ENABLE\_BACKGROUND]- Background
1619
scheduling enabled. \item [PS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
1620
test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
1621
is performed. This flag have to be used if the Module is attached
1622
to an EDF Module. \item [PS\_ENABLE\_ALL\_EDF]- EDF guarantee test
1623
enabled, Background scheduling disabled. \item
1624
[PS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
1625
an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
1626
have to be used if the Module is attached to a RM Module. \item
1627
[PS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
1628
scheduling disabled.
1629
\end{description}
1630
\texttt{master} is the level to that the DS Module is attached. At
1631
the moment, you can attach a PS Module either to an \texttt{EDF},
1632
\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
1633
\texttt{per} are the budget and the period of the deferrable
1634
server. If it is configured to do not use background time, the PS
1635
Module can be registered as the last scheduling Module after the
1636
\texttt{DUMMY} Module. Otherwise, it should be put in the middle
1637
of the list to catck the idle time left by higher level Modules.
1638
 
1639
The PS Module provides also an addictional function, that can be
1640
used to get the used bandwidth by the Module. The prototype of the
1641
function is:
1642
 
1643
\texttt{bandwidth\_t PS\_usedbandwidth(LEVEL l);}
1644
 
1645
where l is the level at which the PS Module is registered.
1646
 
1647
\paragraph{Files:}
1648
 
1649
\texttt{modules/ps/*}
1650
 
1651
\paragraph{Implementation hints:}
1652
 
1653
The PS Module uses a FIFO queue to enqueue the ready tasks. Only
1654
the first task is inserted into the queue of the Master Level. The
1655
Module does not use the CONTROL\_CAP field, but it handles its
1656
capacity event by itself. The budget of the module is recharged
1657
every PS period, and is kept into an internal data structure of
1658
the module, and not in the wcet and avail\_time fields of every
1659
task. Note that the idle time is recognized when the PS scheduler
1660
is called. In that case, no capacity event is posted. The
1661
implementation is very similar to the DS Module implementation.
1662
 
1663
%----------------------------------------------------------------------------
1664
\section{SS (Sporadic Server)}
1665
%----------------------------------------------------------------------------
1666
 
1667
\paragraph{Task Models Accepted:}
1668
 
1669
\begin{description}
1670
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
1671
\texttt{periodicity} can be only \texttt{APERIODIC}. The
1672
\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
1673
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
1674
\end{description}
1675
 
1676
\paragraph{Description:}
1677
 
1678
This module schedule its tasks following the Sporadic Server
1679
Algorithm. The Module can be configured to save or skip task
1680
activations. The Module can be attached to either a RM or an EDF
1681
Module. The module has been written by Marco Gigante. Please
1682
contact the author for more informations.
1683
 
1684
\paragraph{Exceptions Raised:}
1685
 
1686
\begin{description}
1687
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1688
guest operation is called, the exception is raised.
1689
\end{description}
1690
 
1691
\paragraph{Usage:}
1692
 
1693
To register this module, just put this line into the
1694
\texttt{\_\_kernel\_register\_levels\_\_} function:
1695
 
1696
\texttt{SS\_register\_level(flag, master, Cs, per);}
1697
 
1698
where \texttt{flag} can be:
1699
 
1700
\begin{description}
1701
\item [SS\_DISABLE\_ALL]- Guarantee test disabled; Background
1702
scheduling disabled. \item [SS\_ENABLE\_BACKGROUND]- Background
1703
scheduling enabled. \item [SS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
1704
test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
1705
is performed. This flag have to be used if the Module is attached
1706
to an EDF Module. \item [SS\_ENABLE\_ALL\_EDF]- EDF guarantee test
1707
enabled, Background scheduling disabled. \item
1708
[SS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
1709
an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
1710
have to be used if the Module is attached to a RM Module. \item
1711
[SS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
1712
scheduling disabled.
1713
\end{description}
1714
 
1715
\texttt{master} is the level to that the SS Module is attached. At
1716
the moment, you can attach a SS Module either to an \texttt{EDF},
1717
\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
1718
\texttt{per} are the budget and the period of the deferrable
1719
server. If it is configured to do not use background time, the SS
1720
Module can be registered as the last scheduling Module after the
1721
\texttt{DUMMY} Module. Otherwise, it should be put in the middle
1722
of the list to catck the idle time left by higher level Modules.
1723
 
1724
The SS Module provides also some addictional function, that can be
1725
used to get the used bandwidth by the Module and its available
1726
capacity. The prototypes of the functions are:
1727
 
1728
\texttt{bandwidth\_t SS\_usedbandwidth(LEVEL l);}
1729
 
1730
where l is the level at which the SS Module is registered.
1731
 
1732
\texttt{int SS\_availCs(LEVEL l);}
1733
 
1734
Returns tha available capacity of the Module
1735
 
1736
\paragraph{Files:}
1737
 
1738
\texttt{modules/ss/*}
1739
 
1740
\paragraph{Implementation hints:}
1741
 
1742
The implementation of the Module is quite complex. Please refer to
1743
the comments in the source code.
1744
 
1745
%----------------------------------------------------------------------------
1746
\section{TBS (Total Bandwidth Server)}
1747
%----------------------------------------------------------------------------
1748
 
1749
\paragraph{Task Models Accepted:}
1750
 
1751
\begin{description}
1752
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
1753
\texttt{wcet} must be != 0. The \texttt{periodicity} can be either
1754
\texttt{PERIODIC} or \texttt{APERIODIC}. The \texttt{arrivals}
1755
field can be either \texttt{SAVE\_ARRIVALS} or
1756
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
1757
\end{description}
1758
 
1759
\paragraph{Description:}
1760
 
1761
This module schedule his tasks following the TBS algorithm. The
1762
task guarantee is based on the factor utilization approach. The
1763
tasks scheduled are only sporadic. Each task has a deadline
1764
assigned with the TBS scheme,
1765
$d_{k}=\max(r_{k},d_{k-1})+\frac{wcet}{U_{s}}$
1766
 
1767
The tasks are inserted in an EDF level (or similar), and the TBS
1768
level expects that the task is scheduled with the absolute
1769
deadline passed in the guest model.
1770
 
1771
The acceptance test is based on the factor utilization approach.
1772
The theory guarantees that the task set is schedulable if
1773
$U_{p}+U_{s}\leq1$ so it is sufficient to add the Us to the
1774
bandwidth used by the upper levels.
1775
 
1776
\paragraph{Exceptions Raised:}
1777
 
1778
\begin{description}
1779
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
1780
guest operation is called, the exception is raised. \item
1781
[XDEADLINE\_MISS]If a task miss his deadline, the exception is
1782
raised. Normally, a TBS task can't cause the raise of such
1783
exception because if it really use more time than declared a
1784
\texttt{XWCET\_VIOLATION} is raised instead. \item
1785
[XWCET\_VIOLATION]If a task doesn't end the current cycle before
1786
if consume the wcet, an exception is raised, and the task is put
1787
in the \texttt{TBS\_WCET\_VIOLATED} state. To reactivate it, call
1788
\texttt{TBS\_task\_activate} using \texttt{task\_activate} or
1789
manage directly the TBS data structure. Note that if the exception
1790
is not handled properly, an \texttt{XDEADLINE\_MISS} exception
1791
will also be raised at the absolute deadline...
1792
\end{description}
1793
 
1794
\paragraph{Usage:}
1795
 
1796
To register this module, just put this line into the
1797
\texttt{\_\_kernel\_register\_levels\_\_} function:
1798
 
1799
\texttt{TBS\_register\_level(flag, master, num, den);}
1800
 
1801
where \texttt{flag} can be:
1802
 
1803
\begin{description}
1804
\item [TBS\_DISABLE\_ALL]- Guarantee test disabled. \item
1805
[TBS\_ENABLE\_GUARANTEE]- Guarantee test enabled (when enabled,
1806
the acceptance test is performed); Deadline miss exceptions are
1807
raised in any case. \item [TBS\_ENABLE\_WCET\_CHECK]- WCET check
1808
enabled. \item [TBS\_ENABLE\_ALL]- Guarantee test and WCET check
1809
enabled.
1810
\end{description}
1811
and \texttt{master} is the level to that the TBS is attached. num
1812
and den are the reserved bandwidth ($U_{s}=\frac{num}{den}$) for
1813
the TBS server. At the moment, you can attach a TBS Module either
1814
to an \texttt{EDF} or an \texttt{EDFACT} Module. The TBS Module
1815
can be registered as the last scheduling Module after the
1816
\texttt{DUMMY} Module (this because the TBS Module does not use
1817
background time, and because when a TBS task is ready it is
1818
inserted in another queue!).
1819
 
1820
The TBS Module provides also some addictional functions, that can
1821
be used to get the used bandwidth by the Module and the pending
1822
activations of a task. The prototypes of these function are:
1823
 
1824
\texttt{bandwidth\_t TBS\_usedbandwidth(LEVEL l);}
1825
 
1826
where l is the level at which the TBS Module is registered.
1827
 
1828
\texttt{int TBS\_get\_nact(LEVEL l, PID p);}
1829
 
1830
Returns the number of pending activations of a task. No control is
1831
done if the task is not a TBS task! (l is the level at which the
1832
TBS Module is registered, p is the PID of the task).
1833
 
1834
\paragraph{Files:}
1835
 
1836
\texttt{modules/tbs/*}
1837
 
1838
\paragraph{Implementation hints:}
1839
 
1840
The TBS implementation uses a FIFO queue for serving the aperiodic
1841
requests of the Module's tasks. Only the first task is put in the
1842
ready queue of the master module.
1843
 
1844
%----------------------------------------------------------------------------
1845
\chapter{Sharing resource access protocols}
1846
%----------------------------------------------------------------------------
1847
 
1848
%----------------------------------------------------------------------------
1849
\section{CABS}
1850
%----------------------------------------------------------------------------
1851
 
1852
\paragraph{Description:}
1853
 
1854
This module implements the Cyclical Asynchronous Buffers as
1855
described in the Volume I of the User Manual.
1856
 
1857
Note that the Maximum number of CABs that can be created is
1858
MAX\_CAB (defined in include/modules/cabs.h).
1859
 
1860
\paragraph{Usage:}
1861
 
1862
To register this module, just put this line into the
1863
\texttt{\_\_kernel\_register\_levels\_\_} function:
1864
 
1865
\texttt{CABS\_register\_module();}
1866
 
1867
\paragraph{Files:}
1868
 
1869
\texttt{modules/cabs/*}
1870
 
1871
%----------------------------------------------------------------------------
1872
\section{HARTPORT}
1873
%----------------------------------------------------------------------------
1874
 
1875
\paragraph{Description:}
1876
 
1877
This module implements the Communication Ports as described in the
1878
Volume I of the User Manual.
1879
 
1880
\paragraph{Usage:}
1881
 
1882
To register this module, just put this line into the \texttt{\_\_init\_\_} task
1883
\footnote{or in any other task; in any case this function has to be called
1884
before using the port primitives}:
1885
 
1886
\texttt{HARTPORT\_init();}
1887
 
1888
\paragraph{IMPORTANT: }
1889
 
1890
Remember that to get the ports running, you need to register also
1891
the SEM module!
1892
 
1893
\paragraph{Files:}
1894
 
1895
\texttt{modules/hartport/*}
1896
 
1897
%----------------------------------------------------------------------------
1898
\section{NOP (NO Protocol)}
1899
%----------------------------------------------------------------------------
1900
 
1901
\paragraph{Resource Models Accepted:}
1902
 
1903
None.
1904
 
1905
\paragraph{Description:}
1906
 
1907
The NOP Module implements a binary semaphore using the mutex
1908
interface. If a task owns a mutex, it can not lock that mutex
1909
again until it has unlocked it. This protocol can produce priority
1910
inversions and chained blocking.
1911
 
1912
\paragraph{Exceptions Raised:}
1913
 
1914
None
1915
 
1916
\paragraph{Usage:}
1917
 
1918
To register this module, just put this line into the
1919
\texttt{\_\_kernel\_register\_levels\_\_} function:
1920
 
1921
\texttt{NOP\_register\_module();}
1922
 
1923
The NOP protocol uses the default mutex mechanism provided by the
1924
Kernel. In that way, the NOP behaviour for a mutex can be set at
1925
run-time, and the applications can choose the protocol of their
1926
mutexes without changing the task source code.
1927
 
1928
To initialize a NOP mutex, you need to call \texttt{mutex\_init()}
1929
passing a previously initialized \texttt{NOP\_mutexattr\_t}.
1930
 
1931
In the following example, the demo task uses two resources,
1932
labeled with \texttt{m1} and \texttt{m2}, and accesses three
1933
different critical sections:
1934
 
1935
\begin{tt}
1936
\begin{verbatim}
1937
#include <modules/nop.h>
1938
...
1939
 
1940
mutex_t m1,m2;
1941
...
1942
 
1943
void *demo(void *arg) {
1944
    ...
1945
 
1946
    mutex_lock(&m1);
1947
 
1948
    /* critical section of m1 */
1949
    ...
1950
 
1951
    mutex_unlock(&m1);
1952
    ...
1953
 
1954
    mutex_lock(&m1);
1955
 
1956
    /* only m1 locked */
1957
    ...
1958
 
1959
    mutex_lock(&m2);
1960
 
1961
    /* m1 and m2 locked */
1962
    ...
1963
 
1964
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
1965
    mutex_unlock(&m1);
1966
    ...
1967
 
1968
    return 0;
1969
}
1970
 
1971
...
1972
 
1973
int main(int argc, char **argv) {
1974
    HARD_TASK_MODEL m;
1975
    PID p0, p1, p2;
1976
 
1977
    NOP_mutexattr_t a;
1978
 
1979
    /* Initialize the NOP mutexes */
1980
    NOP_mutexattr_default(a);
1981
    mutex_init(&m1, &a);
1982
    mutex_init(&m2, &a);
1983
    ...
1984
 
1985
    /* Create the task */
1986
    hard_task_default_model(m);
1987
    hard_task_def_mit(m, 1000000);
1988
    hard_task_def_wcet(m, 80000);
1989
    p0 = task_create("DEMO", demo, &m, NULL);
1990
    ...
1991
}
1992
\end{verbatim}
1993
\end{tt}
1994
 
1995
Critical sections must be properly nested (like Chinese boxes):
1996
hence the order of the \texttt{mutex\_unlock(m1)} and
1997
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
1998
modifying the corresponding \texttt{mutex\_lock()}.
1999
 
2000
\paragraph{Note:}
2001
 
2002
NOP Mutexes can be statically allocated. See
2003
\texttt{include/modules/nop.h} for details.
2004
 
2005
\paragraph{Note:}
2006
 
2007
A task can use NOP mutexes with other mutexes with different
2008
protocol (for example, PI, PC, SRP mutexes). We don't know the
2009
behaviour of that choice, but, if you want to try, it works!
2010
 
2011
\paragraph{Files:}
2012
 
2013
\texttt{modules/nop/*}
2014
 
2015
\paragraph{Implementation hints:}
2016
 
2017
The implementation of the NOP mutexes is similar to the internal
2018
semaphores.
2019
 
2020
%----------------------------------------------------------------------------
2021
\section{NOPM (NO Protocol Multiple lock)}
2022
%----------------------------------------------------------------------------
2023
 
2024
\paragraph{Resource Models Accepted:}
2025
 
2026
None.
2027
 
2028
\paragraph{Description:}
2029
 
2030
The NOP Module implements a binary semaphore using the mutex
2031
interface. If a task owns a mutex, it can lock that mutex again.
2032
It is like the NOP Module, but the owner of the mutex can issue
2033
multiple lock/unlock on mutex. This protocol can produce priority
2034
inversions and chained blocking.
2035
 
2036
\paragraph{Exceptions Raised:}
2037
 
2038
None
2039
 
2040
\paragraph{Usage:}
2041
 
2042
To register this module, just put this line into the
2043
\texttt{\_\_kernel\_register\_levels\_\_} function:
2044
 
2045
\texttt{NOPM\_register\_module();}
2046
 
2047
The NOPM protocol uses the default mutex mechanism provided by the
2048
Kernel. In that way, the NOPM behaviour for a mutex can be set at
2049
run-time, and the applications can choose the protocol of their
2050
mutexes without changing the task source code.
2051
 
2052
To initialize a NOPM mutex, you need to call
2053
\texttt{mutex\_init()} passing a previously initialized
2054
\texttt{NOPM\_mutexattr\_t}.
2055
 
2056
In the following example, the demo task uses two resources,
2057
labeled with \texttt{m1} and \texttt{m2}, and accesses three
2058
different critical sections:
2059
 
2060
\begin{tt}
2061
\begin{verbatim}
2062
#include <modules/nopm.h>
2063
...
2064
 
2065
mutex_t m1, m2;
2066
...
2067
 
2068
void *demo(void *arg) {
2069
    ...
2070
 
2071
    mutex_lock(&m1);
2072
 
2073
    /* critical section of m1 */
2074
    ...
2075
 
2076
    mutex_unlock(&m1);
2077
    ...
2078
 
2079
    mutex_lock(&m1);
2080
 
2081
    /* only m1 locked */
2082
    ...
2083
 
2084
    mutex_lock(&m2);
2085
 
2086
    /* m1 and m2 locked */
2087
    ...
2088
 
2089
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
2090
    mutex_unlock(&m1);
2091
    ...
2092
 
2093
    return 0;
2094
}
2095
 
2096
...
2097
 
2098
int main(int argc, char **argv) {
2099
    HARD_TASK_MODEL m;
2100
    PID p0, p1, p2;
2101
 
2102
    NOPM_mutexattr_t a;
2103
 
2104
    /* Initialize the NOP mutexes */
2105
    NOPM_mutexattr_default(a);
2106
    mutex_init(&m1, &a);
2107
    mutex_init(&m2, &a);
2108
    ...
2109
 
2110
    /* Create the task */
2111
    hard_task_default_model(m);
2112
    hard_task_def_mit(m, 1000000);
2113
    hard_task_def_wcet(m, 80000);
2114
    p0 = task_create("DEMO", demo, &m, NULL);
2115
    ...
2116
}
2117
\end{verbatim}
2118
\end{tt}
2119
 
2120
Critical sections must be properly nested (like Chinese boxes):
2121
hence the order of the \texttt{mutex\_unlock(m1)} and
2122
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
2123
modifying the corresponding \texttt{mutex\_lock()}.
2124
 
2125
\paragraph{Note:}
2126
 
2127
A task can use NOPM mutexes with other mutexes with different
2128
protocol (for example, PI, PC, SRP mutexes). We don't know the
2129
behaviour of that choice, but, if you want to try, it works!
2130
 
2131
\paragraph{Files:}
2132
 
2133
\texttt{modules/nopm/*}
2134
 
2135
\paragraph{Implementation hints:}
2136
 
2137
The implementation of the NOPM mutexes is similar to the NOP
2138
implementation, except that it counts the numer of times a task
2139
locked a mutex.
2140
 
2141
%----------------------------------------------------------------------------
2142
\section{NPP (Non Preemptive Protocol)}
2143
%----------------------------------------------------------------------------
2144
 
2145
\paragraph{Resource Models Accepted:}
2146
 
2147
None.
2148
 
2149
\paragraph{Description:}
2150
 
2151
The NPP Module implements a binary semaphore using the mutex
2152
interface. The difference with the NOP Module is that when a task
2153
lock a NPP mutex, it became non-preemptive as it called the
2154
\texttt{task\_nopreempt()} primitive. Critical section can be
2155
nested.
2156
 
2157
\paragraph{Exceptions Raised:}
2158
 
2159
\begin{description}
2160
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
2161
ends and it owns one or more mutexes.
2162
\end{description}
2163
 
2164
\paragraph{Usage:}
2165
 
2166
To register this module, just put this line into the
2167
\texttt{\_\_kernel\_register\_levels\_\_} function:
2168
 
2169
\texttt{NPP\_register\_module();}
2170
 
2171
The NPP protocol uses the default mutex mechanism provided by the
2172
Kernel. In that way, the NPP behaviour for a mutex can be set at
2173
run-time, and the applications can choose the protocol of their
2174
mutexes without changing the task source code.
2175
 
2176
To initialize a NPP mutex, you need to call \texttt{mutex\_init()}
2177
passing a previously initialized \texttt{NPP\_mutexattr\_t}.
2178
 
2179
In the following example, the demo task uses two resources,
2180
labeled with \texttt{m1} and \texttt{m2}, and accesses three
2181
different critical sections:
2182
 
2183
\begin{tt}
2184
\begin{verbatim}
2185
#include <modules/npp.h>
2186
...
2187
 
2188
mutex_t m1,m2;
2189
...
2190
 
2191
void *demo(void *arg) {
2192
    ...
2193
 
2194
    mutex_lock(&m1);
2195
 
2196
    /* critical section of m1 */
2197
    ...
2198
 
2199
    mutex_unlock(&m1);
2200
    ...
2201
 
2202
    mutex_lock(&m1);
2203
 
2204
    /* only m1 locked */
2205
    ...
2206
 
2207
    mutex_lock(&m2);
2208
 
2209
    /* m1 and m2 locked */
2210
    ...
2211
 
2212
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
2213
    mutex_unlock(&m1);
2214
    ...
2215
 
2216
    return 0;
2217
}
2218
 
2219
...
2220
 
2221
int main(int argc, char **argv) {
2222
    HARD_TASK_MODEL m;
2223
    PID p0, p1, p2;
2224
    NPP_mutexattr_t a;
2225
 
2226
    /* Initialize the NOP mutexes */
2227
    NPP_mutexattr_default(a);
2228
    mutex_init(&m1,&a);
2229
    mutex_init(&m2,&a);
2230
    ...
2231
 
2232
    /* Create the task */
2233
    hard_task_default_model(m);
2234
    hard_task_def_mit(m, 1000000);
2235
    hard_task_def_wcet(m, 80000);
2236
    p0 = task_create("DEMO", demo, &m, NULL);
2237
    ...
2238
}
2239
\end{verbatim}
2240
\end{tt}
2241
 
2242
Critical sections must be properly nested (like Chinese boxes):
2243
hence the order of the \texttt{mutex\_unlock(m1)} and
2244
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
2245
modifying the corresponding \texttt{mutex\_lock()}.
2246
 
2247
\paragraph{Note:}
2248
 
2249
A task can use NPP mutexes with other mutexes with different
2250
protocol (for example, PI, PC, SRP mutexes; except for nested
2251
critical sections). We don't know the behaviour of that choice,
2252
but, if you want to try, it works!
2253
 
2254
\paragraph{Files:}
2255
 
2256
\texttt{modules/npp/*}
2257
 
2258
\paragraph{Implementation hints:}
2259
 
2260
The implementation of the NPP Module counts the number of locks a
2261
task issued and uses
2262
\texttt{task\_preempt()}/\texttt{task\_nopreempt()} to implement
2263
the protocol.
2264
 
2265
%----------------------------------------------------------------------------
2266
\section{PC (Priority Ceiling)}
2267
%----------------------------------------------------------------------------
2268
 
2269
\paragraph{Resource Models Accepted:}
2270
 
2271
\begin{description}
2272
\item [PC\_RES\_MODEL]- Task priority. This model have to be used
2273
to tell to the PC Module that a task have to be scheduled
2274
following the PC rules. The model can be passed at creation time
2275
to more than one task, and it only contains the priority
2276
information.
2277
\end{description}
2278
 
2279
\paragraph{Description:}
2280
 
2281
This Module implements the Priority Ceiling (PC) Protocol. This
2282
mechanism can be easily applied to Fixed Priority Scheduling to
2283
bound blocking times and to eliminate chained blocking and
2284
deadlocks.
2285
 
2286
\paragraph{Exceptions Raised:}
2287
 
2288
\begin{description}
2289
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
2290
ends and it owns one or more PC mutexes.
2291
\end{description}
2292
 
2293
\paragraph{Usage:}
2294
 
2295
To register this module, just put this line into the
2296
\texttt{\_\_kernel\_register\_levels\_\_} function:
2297
 
2298
\texttt{PC\_register\_module();}
2299
 
2300
The PC protocol uses the default mutex mechanism provided by the
2301
Kernel. In that way, the PC behaviour for a mutex can be set at
2302
run-time, and the applications can choose the protocol of their
2303
mutexes without changing the task source code.
2304
 
2305
To initialize a PC mutex, you need to call \texttt{mutex\_init()}
2306
passing a previously initialized \texttt{PC\_mutexattr\_t}, that
2307
contains the ceiling of the mutex.
2308
 
2309
To apply the Priority Ceiling protocol to a task, you need to tell the Module
2310
what is the priority of that task \footnote{Also a task that have to be
2311
scheduled using the PC rules but without using any PC mutex must declare its
2312
priority!}. That information is given ti the Module using a Resource Model of
2313
type \texttt{PC\_RES\_MODEL} at task creation time (in other words, to the
2314
\texttt{task\_createn} primitive). That model have to be previously initialized
2315
with the priority of the task.
2316
 
2317
Note that the priority value used by the PC Module may differ from
2318
the priority of the scheduling algorithm that really schedule the
2319
tasks. Typically, priorities are set to the same (or equipollent)
2320
values.
2321
 
2322
In the following example, the demo task uses two resources,
2323
labeled with \texttt{m1} and \texttt{m2}, and accesses three
2324
different critical sections:
2325
 
2326
\begin{tt}
2327
\begin{verbatim}
2328
#include <modules/pc.h>
2329
...
2330
 
2331
mutex_t m1,m2;
2332
...
2333
 
2334
void *demo(void *arg)  {
2335
    ...
2336
 
2337
    mutex_lock(&m1);
2338
 
2339
    /* critical section of m1 */
2340
    ...
2341
 
2342
    mutex_unlock(&m1);
2343
    ...
2344
 
2345
    mutex_lock(&m1);
2346
 
2347
    /* only m1 locked */
2348
    ...
2349
 
2350
    mutex_lock(&m2);
2351
 
2352
    /* m1 and m2 locked */
2353
    ...
2354
 
2355
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
2356
    mutex_unlock(&m1);
2357
    ...
2358
 
2359
    return 0;
2360
}
2361
...
2362
 
2363
int main(int argc, char **argv) {
2364
    HARD_TASK_MODEL m;
2365
    PID p0, p1, p2;
2366
 
2367
    PC_mutexattr_t a;
2368
    PC_RES_MODEL r;
2369
 
2370
    /* Initialize the SRP mutexes */
2371
    PC_mutexattr_default(a,1); /* 1 is the pr. level */
2372
    mutex_init(&m1,&a);
2373
    mutex_init(&m2,&a);
2374
    ...
2375
 
2376
    /* Create the task */
2377
    hard_task_default_model(m);
2378
    hard_task_def_mit(m, 1000000);
2379
    hard_task_def_wcet(m, 80000);
2380
    PC_res_default_model(r, 1); /* set the task Priority */
2381
 
2382
    p0 = task_create("DEMO", demo, &m, &r);
2383
    ...
2384
}
2385
\end{verbatim}
2386
\end{tt}
2387
 
2388
Critical sections must be properly nested (like Chinese boxes):
2389
hence the order of the \texttt{mutex\_unlock(m1)} and
2390
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
2391
modifying the corresponding \texttt{mutex\_lock()}.
2392
 
2393
The Module also provides three functions that are used to
2394
implement similar POSIX functions. Typically the user does not
2395
need to call them.
2396
 
2397
\texttt{int PC\_get\_mutex\_ceiling(const mutex\_t *mutex, DWORD
2398
*ceiling);}
2399
 
2400
This function gets the ceiling of a PC mutex, and it have to be
2401
called only by a task that owns the mutex. Returns -1 if the mutex
2402
is not a PC mutex, 0 otherwise.
2403
 
2404
\texttt{int PC\_set\_mutex\_ceiling(mutex\_t *mutex, DWORD
2405
ceiling, DWORD *old\_ceiling);}
2406
 
2407
This function sets the ceiling of a PC mutex, and it have to be
2408
called only by a task that owns the mutex. Returns -1 if the mutex
2409
is not a PC mutex, 0 otherwise.
2410
 
2411
\texttt{void PC\_set\_task\_ceiling(RLEVEL r, PID p, DWORD
2412
priority);}
2413
 
2414
This function sets the priority of a task.
2415
 
2416
\paragraph{Note:}
2417
 
2418
The Real-Time Literature typically found a feasibility test for
2419
the scheduling only in the case that all hard tasks use the PC
2420
protocol. Note that the Module is written in a way that only the
2421
tasks that declared their Priority will use the PC protocol. If a
2422
task that does not have a Priority, it is not scheduled using the
2423
PC protocol, also if it is inserted in the same scheduling queue
2424
of PC tasks.
2425
 
2426
\paragraph{Note:}
2427
 
2428
A task can use PC mutexes with other mutexes with different
2429
protocol (for example, PI, SRP, NOP mutexes). We don't know the
2430
behaviour of that choice, but, if you want to try, it works!
2431
 
2432
\paragraph{Files:}
2433
 
2434
\texttt{modules/pc/*}
2435
 
2436
\paragraph{Implementation hints:}
2437
 
2438
The PC Module uses the shadow mechanism to implement its
2439
behaviour. It keeps track of all the locked mutexes to block
2440
(setting the shadow field to the mutex owner) a task that requires
2441
a lock on a mutex with ceiling less than the system ceiling. When
2442
unlocking, all the shadows are reset. At that point they will try
2443
again to reaquire the mutex, that time starting from the highest
2444
priority task in the scheduling queue.
2445
 
2446
%----------------------------------------------------------------------------
2447
\section{PI (Priority Inheritance)}
2448
%----------------------------------------------------------------------------
2449
 
2450
\paragraph{Resource Models Accepted:}
2451
 
2452
None.
2453
 
2454
\paragraph{Description:}
2455
 
2456
This Module implements the Priority Inheritance mechanism. This
2457
mechanism can be easily applied to Fixed Priority Scheduling to
2458
bound blocking times.
2459
 
2460
\paragraph{Exceptions Raised:}
2461
 
2462
\begin{description}
2463
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
2464
ends and it owns one or more PI mutexes.
2465
\end{description}
2466
 
2467
\paragraph{Usage:}
2468
 
2469
To register this module, just put this line into the
2470
\texttt{\_\_kernel\_register\_levels\_\_} function:
2471
 
2472
\texttt{PI\_register\_module();}
2473
 
2474
The PI protocol uses the default mutex mechanism provided by the
2475
Kernel. In that way, the PI behaviour for a mutex can be set at
2476
run-time, and the applications can choose the protocol of their
2477
mutexes without changing the task source code.
2478
 
2479
To initialize a PI mutex, you need to call \texttt{mutex\_init()}
2480
passing a previously initialized \texttt{PI\_mutexattr\_t}.
2481
 
2482
In the following example, the demo task uses two resources,
2483
labeled with \texttt{m1} and \texttt{m2}, and accesses three
2484
different critical sections:
2485
 
2486
\begin{tt}
2487
\begin{verbatim}
2488
#include <modules/pi.h>
2489
...
2490
 
2491
mutex_t m1,m2;
2492
...
2493
 
2494
void *demo(void *arg) {
2495
    ...
2496
 
2497
    mutex_lock(&m1);
2498
 
2499
    /* critical section of m1 */
2500
    ...
2501
 
2502
    mutex_unlock(&m1);
2503
    ...
2504
 
2505
    mutex_lock(&m1);
2506
 
2507
    /* only m1 locked */
2508
    ...
2509
 
2510
    mutex_lock(&m2);
2511
 
2512
    /* m1 and m2 locked */
2513
    ...
2514
 
2515
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
2516
    mutex_unlock(&m1);
2517
    ...
2518
 
2519
    return 0;
2520
}
2521
...
2522
 
2523
int main(int argc, char **argv) {
2524
    HARD_TASK_MODEL m;
2525
    PID p0, p1, p2;
2526
 
2527
    PI_mutexattr_t a;
2528
 
2529
    /* Initialize the SRP mutexes */
2530
    PI_mutexattr_default(a);
2531
    mutex_init(&m1,&a);
2532
    mutex_init(&m2,&a);
2533
    ...
2534
 
2535
    /* Create the task */
2536
    hard_task_default_model(m);
2537
    hard_task_def_mit(m, 1000000);
2538
    hard_task_def_wcet(m, 80000);
2539
    p0 = task_createn("DEMO", demo, &m, NULL);
2540
    ...
2541
}
2542
\end{verbatim}
2543
\end{tt}
2544
 
2545
Critical sections must be properly nested (like Chinese boxes):
2546
hence the order of the \texttt{mutex\_unlock(m1)} and
2547
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
2548
modifying the corresponding \texttt{mutex\_lock()}.
2549
 
2550
\paragraph{Note:}
2551
 
2552
A task can use PI mutexes with other mutexes with different
2553
protocol (for example, SRP, PC, NOP mutexes). We don't know the
2554
behaviour of that choice, but, if you want to try, it works!
2555
 
2556
\paragraph{Files:}
2557
 
2558
\texttt{modules/pi/*}
2559
 
2560
\paragraph{Implementation hints:}
2561
 
2562
This is the simplest protocol that can be implemented using the
2563
shadows mechanism. The implementation set the shadow field when a
2564
task blocks, and reset it when the mutex is unlocked. At that
2565
point, the highest priority free task will lock the mutex.
2566
 
2567
%----------------------------------------------------------------------------
2568
\section{SEM (POSIX Semaphores)}
2569
%----------------------------------------------------------------------------
2570
 
2571
\paragraph{Description:}
2572
 
2573
This module implements the POSIX Semaphores as described in the
2574
Volume I of the User Manual.
2575
 
2576
\paragraph{Usage:}
2577
 
2578
To register this module, just put this line into the
2579
\texttt{\_\_kernel\_register\_levels\_\_} function:
2580
 
2581
\texttt{SEM\_register\_module();}
2582
 
2583
\paragraph{Files:}
2584
 
2585
\texttt{modules/sem/*}
2586
 
2587
\paragraph{Implementation hints:}
2588
 
2589
The implementation uses a fixed number of semaphores (note that
2590
Internal Semaphores does not!). Note the use of
2591
\texttt{task\_testcancel()} to implement the cancellation points.
2592
 
2593
%----------------------------------------------------------------------------
2594
\section{SRP (Stack Resource Policy)}
2595
%----------------------------------------------------------------------------
2596
 
2597
\paragraph{Resource Models Accepted:}
2598
 
2599
\begin{description}
2600
\item [SRP\_RES\_MODEL]- Preemption levels. This model have to be
2601
used to tell to the SRP Module that a task have to be scheduled
2602
following the SRP rules. The model can be passed at creation time
2603
to more than one task, and it only contains the preemption level
2604
information.
2605
\end{description}
2606
 
2607
\paragraph{Description:}
2608
 
2609
\emph{Stack Resource Policy} (SRP) is a mutual exclusion mechanism
2610
suitable for hard real-time tasks, that can be used with static or
2611
dynamic scheduling algorithms. Its main feature is the property
2612
that a task is blocked not when it tries to use the resource, but
2613
when it tries to preempt another task owning the shared resource.
2614
This early blocking simplifies the protocol implementation and
2615
reduces the number of context switches, increasing the system
2616
efficiency.
2617
 
2618
This SRP implementation provides a simplified version of the protocol, suitable
2619
only for single-unit resources, that defines a particular behaviour for the
2620
\texttt{mutex\_XXX} primitives. Moreover, it is implemented using the shadows
2621
mechanism (described in the S.Ha.R.K. architecture manual), so there is no
2622
restriction on the Task Models of the tasks that will use SRP \footnote{However,
2623
note that a schedulability test is only available for EDF and RM schedulers.}.
2624
 
2625
SRP is implemented associating a dynamic priority $p(\tau)$ and a
2626
preemption level $\pi(\tau)$ to each task $\tau$. If an EDF
2627
scheduler is used to schedule the tasks that use SRP, we can say
2628
that the priority $p(\tau)$ of task $\tau$ is proportional to
2629
$1/d$, where $d$ is the task's absolute deadline, while the
2630
preemption level $\pi(\tau)$ is proportional to $1/D$, where $D$
2631
is the tasks's relative deadline.
2632
 
2633
Each resource is assigned a dynamic \emph{priority ceiling}
2634
$C_{R}$, defined as:
2635
\[
2636
C_{R}=max\{0\},\;\{\pi(\tau):R\in R(\tau)\, and\, Rsbusy\}
2637
\]
2638
 
2639
\noindent where $R(\tau)$ is the set of all resources used by task
2640
$\tau$. According to this definition, if a resource is free, its
2641
ceiling is 0; if a resource is busy, its ceiling is the maximum
2642
among the preemption levels of tasks using it. A \emph{System
2643
Ceiling} $\Pi_{S}$ is also defined as the maximum ceiling among
2644
all the resources:
2645
\[
2646
\Pi_{S}\;=\; max_{r}\{ C_{r}\;:\; r=1,\ldots,m\}.
2647
\]
2648
 
2649
Starting from these definitions, the SRP works according to the
2650
following rule:
2651
 
2652
\begin{quote}
2653
\emph{The execution of a task is delayed until it becomes the task
2654
having the highest priority and its preemption level is strictly
2655
greater than the system ceiling.}
2656
\end{quote}
2657
 
2658
Two tests are needed to allow a task to execute: a test on its
2659
priority (i.e., the deadline, which is dynamically assigned) and a
2660
test on the preemption level (which is statically determined).
2661
 
2662
The SRP protocol ensures that a task $\tau$, once started, cannot
2663
be blocked on any resource until it terminates. Consequently, SRP
2664
avoids unbounded priority inversion, blocking chains, and
2665
deadlocks. It also reduces the number of context switches and
2666
simplifies the implementation of the mechanism.
2667
 
2668
Since the SRP may be applied on various Scheduling Modules with
2669
different scheduling policies, no guarantee or blocking time
2670
calculations are performed by the Kernel.
2671
 
2672
The tasks that use SRP mutexes must declare the use of a shared
2673
resource, using the provided resource modules.
2674
 
2675
Finally, note that this implementation of SRP is NOT compatible
2676
with the join primitive. If a task that uses SRP mutexes calls
2677
\texttt{task\_join} or \texttt{pthread\_join}, the result is
2678
undefined.
2679
 
2680
\paragraph{Exceptions Raised:}
2681
 
2682
\begin{description}
2683
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
2684
ends and it owns one or more SRP mutexes. \item
2685
[XSRP\_UNVALID\_LOCK]This exception is raised when a task try to
2686
lock a srp mutex but it don't have the privilege.
2687
\end{description}
2688
 
2689
\paragraph{Usage:}
2690
 
2691
To register this module, just put this line into the
2692
\texttt{\_\_kernel\_register\_levels\_\_} function:
2693
 
2694
\texttt{SRP\_register\_module();}
2695
 
2696
The SRP protocol uses the default mutex mechanism provided by the
2697
Kernel. In that way, the SRP behaviour for a mutex can be set at
2698
run-time, and the applications can choose the protocol of their
2699
mutexes without changing the task source code.
2700
 
2701
To initialize a SRP mutex, you need to call \texttt{mutex\_init()}
2702
passing a previously initialized \texttt{SRP\_mutexattr\_t}.
2703
 
2704
To use a SRP mutex, you need to tell the Module two kind of
2705
informations:
2706
 
2707
\begin{itemize}
2708
\item First, every task that have to be scheduled following the SRP rules must
2709
have a (fixed) preemption level \footnote{Also a task that have to be scheduled
2710
using the SRP rules but without using any SRP mutex must declare its preemption
2711
level!}.
2712
\item Second, every task must declare the mutexes that it will use during its
2713
life.
2714
\end{itemize}
2715
 
2716
All the two informations have to be given to the Module using
2717
Resource Models.
2718
 
2719
To set a task preemption level you need to pass an
2720
\texttt{SRP\_RES\_MODEL} at task creation time (in other words, to
2721
the \texttt{task\_createn} primitive). That model have to be
2722
previously initialized with the preemption level of the task.
2723
 
2724
To declare that a task will use a particular mutex, you have to
2725
pass another Resource Model at task creation time. The Model you
2726
need to pass is returned by the following function:
2727
 
2728
\texttt{RES\_MODEL *SRP\_usemutex(mutex\_t *m);}
2729
 
2730
where \texttt{m} is the SRP mutex the task will use.
2731
 
2732
In the following example, the demo task uses two resources,
2733
labeled with \texttt{m1} and \texttt{m2}, and accesses three
2734
different critical sections:
2735
 
2736
\begin{tt}
2737
 
2738
\begin{verbatim}
2739
 #include <modules/srp.h>
2740
...
2741
 
2742
mutex_t m1,m2;
2743
...
2744
 
2745
void *demo(void *arg) {
2746
    ...
2747
 
2748
    mutex_lock(&m1);
2749
 
2750
    /* critical section of m1 */
2751
    ...
2752
 
2753
    mutex_unlock(&m1);
2754
    ...
2755
 
2756
    mutex_lock(&m1);
2757
    /* only m1 locked */
2758
    ...
2759
 
2760
    mutex_lock(&m2);
2761
 
2762
    /* m1 and m2 locked */
2763
    ...
2764
 
2765
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
2766
    mutex_unlock(&m1);
2767
    ...
2768
 
2769
    return 0;
2770
}
2771
...
2772
 
2773
int main(int argc, char **argv) {
2774
    HARD_TASK_MODEL m;
2775
    PID p0, p1, p2;
2776
 
2777
    SRP_mutexattr_t a;
2778
    SRP_RES_MODEL r;
2779
 
2780
    /* Initialize the SRP mutexes */
2781
 
2782
    SRP_mutexattr_default(a);
2783
    mutex_init(&m1,&a);
2784
    mutex_init(&m2,&a);
2785
    ...
2786
 
2787
    /* Create the task */
2788
    hard_task_default_model(m);
2789
    hard_task_def_mit(m, 1000000);
2790
    hard_task_def_wcet(m, 80000);
2791
    SRP_res_default_model(r, 3); /* set the task Preemption level */
2792
    p0 = task_createn("DEMO", demo, &m, &r, SRP_usemutex(&m1),
2793
SRP_usemutex(&m2), NULL);
2794
    ...
2795
}
2796
\end{verbatim}
2797
\end{tt}
2798
 
2799
Critical sections must be properly nested (like Chinese boxes):
2800
hence the order of the \texttt{mutex\_unlock(m1)} and
2801
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
2802
modifying the corresponding \texttt{mutex\_lock()}.
2803
 
2804
\paragraph{Note:}
2805
 
2806
The Real-Time Literature typically found a feasibility test for the scheduling
2807
only in the case that all hard tasks use the SRP protocol. Note that the Module
2808
is written in a way that only the tasks that declared their Preemption Level
2809
will use the SRP protocol. If a task that does not have a Preemption Level
2810
\footnote{i.e., it was created without passing a \texttt{SRP\_RES\_MODEL} to the
2811
\texttt{task\_createn} primitive.}, it is not scheduled using the SRP protocol,
2812
also if it is inserted in the same scheduling queue of SRP tasks.
2813
 
2814
\paragraph{Note:}
2815
 
2816
A task can use SRP mutexes with other mutexes with different
2817
protocol (for example, PI, PC, NOP mutexes). We don't know the
2818
behaviour of that choice, but, if you want to try, it works!
2819
 
2820
\paragraph{Files:}
2821
 
2822
\texttt{modules/srp/*}
2823
 
2824
\paragraph{Implementation hints:}
2825
 
2826
Notes about the implementation of SRP are inserted in the heading
2827
the source file \texttt{modules/srp/srp.c}.
2828
 
2829
%----------------------------------------------------------------------------
2830
\chapter{File system Modules}
2831
%----------------------------------------------------------------------------
2832
 
2833
%----------------------------------------------------------------------------
2834
\section{BD\_EDF}
2835
%----------------------------------------------------------------------------
2836
 
2837
TBD
2838
 
2839
%----------------------------------------------------------------------------
2840
\section{BD\_PSCAN}
2841
%----------------------------------------------------------------------------
2842
 
2843
TBD
2844
 
2845
\printindex{}
2846
 
2847
\bibliographystyle{alpha}
2848
\bibliography{../common/biblio}
2849
 
2850
\end{document}