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} |